Deconstructing the DuckDB Buffer System.. Part 1

Choosing Database Internals as my niche, I chose DuckDB as the open-source project to contribute to. I began deconstructing its buffer system(here's a link to it), starting with bufferpool.cpp.

Here's what I understood about the code.

The two core objects that are repeatedly mentioned:

• BufferPool: Provides/manages the underlying memory resource and the mechanisms needed to let the memory receptionist (BufferManager) use it.

• BlockMemory: Knows the status of blocks with respect to the relevant aspects. Different BlockMemory objects contain metadata about different blocks of memory.

Blocks are pinned when a user or a local function requests them, and are unpinned when they are no longer needed. An unpinned block gets placed in the eviction queue but not unloaded. They are evicted only under memory pressure.

The following is the trajectory of a freshly evicted(or dequeued) candidate:

Discard — a newer entry exists.

Leave block — the entry is current, but A is being used again.

Proceeding with the analysis of this file, I came across several implementation questions. This is my attempt at answering each of them:

What are eviction queues?

They are waiting queues for entries to be removed. Eviction is just one of the ways of deleting an object.

What are weak and shared ptrs?

A shared_ptr keeps a count of the number of owners(all the shared_ptrs pointing to the object) of the object to which it points. When this no. drops to 0, the object is destroyed.

A weak_ptr tracks (only) the lifetime of an object owned by some shared_ptr using functions like lock() and expire().

“BufferPool starts removing entries from these queues and tries to unload them.” What’s the different between removing and unloading?

Why does the eviction queue have a hierarchy according to which eviction is conducted?

There is a certain a cost to evicting entities. The eviction queue is thus divided into 3 based on how much they free at the cost of how much time is spend at the act of doing so.

In the case of a dead node, why would removing the old copy be expensive? What does ‘this queue entry is obsolete’ mean? Which one of the two is a dead node? What are sequence numbers?

Say a node A is evicted, and then taken out for use again, then evicted again. Thus the queue now has 2 entries of A. The older one(which is called the dead node) needs to be removed.

Searching for an entry mid-queue is expensive. Instead, a hash table called page directory hashes serial no.s to entries in the queue. This way, when A reappears in the eviction queue, it increments its hash value to 2. Later, when the older value reaches the tail, the sequence no.s of the dead node and the current hashed value of A are compared. If they match, the block is unloaded. If not, it is simply discarded, as the inequality indicates that the block at the tail is not its latest entry.

What does purging a queue mean?

Purging involves taking a batch out of the eviction queue, discarding dead nodes in bulk, and then putting it back into the queue. The newer batch becomes the newest entries; they are not removed and put back into the queue from the tail side.

Does the system constantly check every block to see which one it can push into the eviction queue?

No; once the reader count drops to zero, the function CanUnload() checks other conditions. A block is pushed to the eviction queue only when all the conditions hold.