Shulou(Shulou.com)06/01 Report--

I. data structure

1. Buffer is managed by an array BufferDescriptor [] array. The array is created by the function InitBufferPool and has a size of NBuffers members, namely BufferDesc. The array is managed by StrategyControl after creation, with firstFreeBuffer as the chain header pointing to the first member of the linked list, lastFreeBuffer pointing to the end of the linked list, and all free list members are strung together by freeNext, and the value is the array subscript.

The BufferDescriptor array is applied in shared memory and shared by all processes. You can see that the BufferDescriptors addresses of the two processes are the same:

Process 1: (gdb) p BufferDescriptors$1 = (BufferDescPadded *) 0xa615fb80 (gdb) p * BufferDescriptors$2 = {bufferdesc = {tag = {rnode = {spcNode = 1664, dbNode = 0, relNode = 1262}, forkNum = MAIN_FORKNUM, blockNum = 0}, buf_id = 0, state = {value = 2199126016}, wait_backend_pid = 0, freeNext =-2, content_lock = {tranche = 53, state = {value = 536870912}, waiters = {head = 2147483647, tail = 2147483647} Pad = "\ 200"} process 2: (gdb) p BufferDescriptors$1 = (BufferDescPadded *) 0xa615fb80 (gdb) p * BufferDescriptors$2 = {bufferdesc = {tag = {rnode = {spcNode = 1664, dbNode = 0, relNode = 1262}, forkNum = MAIN_FORKNUM, blockNum = 0}, buf_id = 0, state = {value = 2199126016}, wait_backend_pid = 0, freeNext =-2, content_lock = {tranche = 53, state = {value = 536870912}, waiters = {head = 2147483647 Tail = 2147483647}}, pad = "\ 200"}

2. At the same time, these array members are managed through a ring. Used when performing large table scans. It is managed by the strategy- > buffers [] array, which stores the value after + 1 of the subscript of the BufferDescriptors [] array, and each time the buf descriptor is taken, the selection starts with the strategy- > current value. After the selected ones are not available, traverse backwards in turn, traverse to the beginning, and then choose from the beginning, that is, to form a ring. Whether the standards are available or not will be detailed later.

Here's the BufferDesc member variable:

BufferTag tag is the mapping of a descriptor corresponding to the physical page of the disk. That is, space ID+database ID+ file ID-forkNum (table file or fsm file or vm file)-page number

Buf_id is the subscript of the buffer array BufferBlocks []

State is a status flag, including the refcount and usagecount of the buffer and whether the valid is valid or not

Wait_backend_pid: if the tuple that process A needs to delete is accessed by another process, that is, when refcount > 0, process A cannot physically delete the tuple. The system records the ID of the process on wait_backend_id, then adds pin to the buffer block and blocks itself. When refcount is 1, the last process that uses the buffer block releases the buffer, a message is sent to the wait_backend_id process.

FreeNext is the subscript of the next node of the linked list

Content_lock is a buffer lock, which is locked when the process accesses the buffer block, reads with LW_SHARE locks, and writes with LW_ Excluse locks.

Second, shared buffer allocation mechanism

1. Preparation in advance:

1) there are four cases of this buffer allocation: lookup from hash table SharedBufHash, lookup from ring buffer, lookup from free list and allocation from eviction policy.

2) the hash table SharedBufHash is also global in shared memory and is public to all processes. The following are the hash tables printed by the server-side processes of the two session connections.

(gdb) p SharedBufHash$1 = (HTAB *) 0x87f5b04 (gdb) p SharedBufHash$1 = (HTAB *) 0x87f5b04

3) the hash table is also created in InitBufferPool:

StrategyInitialize- > InitBufTable (NBuffers + NUM_BUFFER_PARTITIONS)-> SharedBufHash = ShmemInitHash

4) the entry in the hash table is: [BufferTag,id], that is, the key value is the flag of the physical disk page, and id is the ID of the corresponding buffer.

5) first, you need to create a newTag that corresponds to a page of the physical file.

6) calculate the key value newHash of hash table from newTag to function BufTableHashCode

7) there are 128 buffer partition locks, which are obtained by polling through the key value of hash

8) add LW_SHARED lock to the buffer partition corresponding to the key value at this time

2. Enter the first way to get buffer descriptors: SharedBufHash shared by all processes

1) find the corresponding buffer from the hash table SharedBufHash according to newTag

2) buf_id > 0 means that the data page is found in the hash table, that is, the corresponding data page is loaded into memory

3) get the buffer descriptor BufferDescriptors [BUF _ id)] .bufferdesc according to buf_id

4) hold the corresponding buffer pin through the function PinBuffer, and then release the partition lock of buffer

That is, the refcount+1,usagecount of buf's state will be + 1 according to the situation, and the specific process will be analyzed below.

5) if pin fails, TRUE is returned by StartBufferIO judgment, and the buffer is invalid. In this case, foundPtr is false, and the corresponding buf; is returned as false, indicating that someone else is using it, and the corresponding buf is returned directly. FoundPtr indicates whether it is hit in the buffer

3. If it does not exist in the hash table, it needs to be read from disk. First release buf's partition lock and enter the loop.

1) StrategyGetBuffer takes out a buf descriptor, as shown below.

2) PinBuffer_Locked changes the refcount+1 of buf

3) if the buf is a dirty block BM_DIRTY, add LW _ SHARED lock to buf- > content_ lock. If locking fails, release pin and return 1). Lock successfully according to whether strategy is empty or not.

4) use the ring buffer, that is, the strategy is not empty: get the lsn of the dirty buf page in the BM_LOCKED lock, determine whether the log has been written to disk according to the lsn, if not, delete the buf from the ring buffer; release the buf- > content_lock lock and pin, and return 1) cycle to select.

5) if the ring buffer is used and the log is brushed or not, call FlushBuffer to write dirty data to the disk, and finally release the buf- > content_lock lock.

6) then go to 4, and also to 4 when the page is not dirty

4. Replace it with your own tag

1) obtain the oldTag of buf first, and who has used it. The newPartitionLock of its oldPartitionLock and newTag are locked sequentially, and only one lock is added if the same is the same. LW_EXCUSIVE

2) insert the entry corresponding to newTag into the hash table SharedBufHash

3) buf_id > = 0, indicating that the entry is already in the hash table. After the locks of unpin and oldPartitionLock are released, acquire the old Buf and release newPartitionLock after pin.

4) if pin fails, TRUE is returned by StartBufferIO judgment, and the buffer is invalid. In this case, foundPtr is false, and the corresponding buf; is returned as false, indicating that someone else is using it, and the corresponding buf is returned directly. FoundPtr indicates whether to hit 5) buf_idtag=newTag in the buffer, and finally releases the related lock

6) otherwise, you need to release the relevant lock, delete the entry corresponding to newTag from the hash table, and return to 3 for selection.

3. Several subfunctions 1, PinBuffer

1. If the state of buffer is BM_LOCKED, you need to wait. The lock is a pin lock.

2. GetPrivateRefCountEntry acquires ref. If ref is not NULL, it means that someone else is using it, and then TRUE. Is that how you understand it? You need to understand this function.

3. The atomic operation reads the state value old _ buf_state and saves it as buf_state

4. Refcount+1 of buf_state

5. Under the default policy, that is, select an idle descriptor from free list, and under buf_state 's usagecount+1; ring buffer policy, the usagecount of buf_state is kept at 1.

6. Replace the value of buf- > state with the value of buf_state through CAS operation

7. The TRUE returned by the function indicates that the data of the buffer is valid, that is, the legitimate data has been loaded into memory; the returned false indicates that the data is invalid, that is, the data is not loaded into memory

2. StartBufferIO: enable IO and set the buf status to BM_IO_IN_PROGRESS

1. Each buffer has an IO lock (BufferIOLWLockArray [(bdesc)-> buf_id]). Lock

2. To obtain the buf_state status, you need to set it to BM_LOCKED first.

3. The buf is already BM_IO_IN_PROGRESS at this time, that is, it is reading and writing. The WaitIO waits for the state to change after the above two locks are released.

4. ForInput is TRUE: to write inside, it needs to be! BM_VALID. If BM_VALID indicates that someone has written legal data into it, FALSE: it needs to be read out, and if it is! BM_DIRTY, it means that someone has written it. Release two locks and return

5. Set buf_state to BM_IO_IN_PROGRESS.

6. Return TRUE, which means that the data in buf is invalid and can be used. False, indicating that someone else is using it

3 、 StrategyGetBuffer

1. If you use strategy, take a free descriptor from the ring buffer: bufnum=strategy- > buffers [strategy-> current]; buf = GetBufferDescriptor (bufnum-1); GetBufferFromRing returns NULL if it is not available, otherwise it returns the buf directly.

2. If the ring buffer failed to fetch buffer, go to free list to fetch it.

3. StrategyControl- > firstFreeBuffer > 0, list is not empty at this time

4. First apply for the spin lock StrategyControl- > buffer_strategy_lock, and determine the linked list again. If StrategyControl- > firstFreeBufferfirstFreeBuffer points to the buffer descriptor, delete the node from free list.

6. Release the StrategyControl- > buffer_strategy_lock lock

7. If the refcount and usagecount of the buf are both 0, it means we can use it. If strategy is not NULL, put the buf in the ring buffer and return the buffer descriptor; otherwise, loop to step 4 again.

8. At this time, the free list is fetched once, but nothing is available. The buf is fetched through the clock algorithm, that is, loop StrategyControl- > nextVictimBuffer, to see if it is available. Similarly, if found, put the strategy in the ring buffer according to whether it is NULL or not. After all the buf has been checked, an error will be reported if it is still not available: no unpinned buffers available

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.