Cache and Buffer Pool Manager

The present post is about Caches and the Buffer Pool Manager for a database named SparrowDB that I am building. The programming language is Rust. The DB is a SQL relational database I wish to take from scratch to distributed. If you wish to come along for the ride, I will post weekly on my thoughts, struggles and completed work. Disclaimer: A lot of what I know and some parts of this blog comes from lessons by Andy Pavlo from CMU who made a youtube course, and I highly recommend you learn from him if you desire to work with database internals.

Cache Policies:

There are several types of caches we could consider eg. course-grained and fine-grained, but we will only consider the former category. Furthermore we will only use LRU-K in this project, but I wish to give an honourable mention to frequency based cache policies such as Q2 and LFU. The LRU-K is an improvement on the LRU policy as it avoids thrashing in the database cache where we evict a page only to read it again in the next read or we perform poor eviction when the working set exceeds the capacity of the cache. LRU-K evicts the page whose K-backward distance is the maximum of all the pages in the buffer, where we compute k-distance as the difference between the current timestamp and the timestamp of the kth previous access. We keep a history of the accesses to the pages. Please note that we call the Page the memory that is managed in the virtual memory and the Frame is the memory that is on-disk (stable storage). Buffer Pool Manager: We use a Buffer Pool Manager (in a disk-orientate DBMS) to manage data for fast access when requested from a user, by using cached data that is hot and evicting data that is cold to the disk.

The important thing to note is that the Buffer Pool Manager will manage the Pages and acts as a Cache that reads in tuples and their pages from frames on disk. When a Page that was on Disk is requested we use the Meta data for the location on disk and then read the relevant data to a page in virtual memory (see image above). If the Cache is full, then whatever page that has the maximum K-backward distance will be Evicted to the disk. In so doing we manage the disk better than the Operating System could. We effectively get a multiple of 2 for our memory storage since we keep memory in RAM (eg. 1GB) and on disk with the help of the Buffer Pool Manager (an additional 1GB).

So what would this look like in rust code? Note I will not provide full implementation details here (please see the repo for details on SparrowDB), but i will provide definitions that one can reason about. The BufferPoolManager is the container for the Replacement Policy where the LRUKReplacer takes responsibility to perform the cache eviction policy (its a structure of its own definition so I can replace it with the Q2 policy when I choose to). The Page is a represention of the memory on disk, but held within the BufferPoolManager and its read when required or Evicted when it satifies the above mentioned properties.

Please note the code does not display correctly in the code tags in html, but you can find the code in the repo at the link provided above.

  pub struct BufferPoolManager {
    num_frames: usize,
    next_page: AtomicUsize,
    bpm_latch: Arc>,
    atomic_counter: AtomicUsize,
    latch: Arc>,
    frames: Vec,
    page_table: HashMap,
    free_frames: Vec,
    replacer: Box,
}

The Replacer is shown with the nodes that it holds which are individual nodes of memory LRUNode.

struct LRUKReplacer {
    node_store: HashMap,
    current_timestamp: usize,
    current_size: usize,
    replacer_size: usize,
    k_: usize,
    latch: Arc>,
}

struct LRUNode {
    history: Vec,
    k_: usize,
    fid: FrameId,
    is_evictable: bool,
}

The Page is part of the storage module within the project and has the following definition:

pub struct Page {
    id: usize,
    pub data: Mutex>,
    pin_count: AtomicUsize,
    is_dirty: AtomicBool,
}

I will not show the full code here as its too much to show, but I will mention some important parts. The mark_dirty function self.is_dirty.store(true, Ordering::Release) of structure Page is done with a release on the storage by some thread, so that means that another parallel thread that reads this value must do so using is_dirty.load(Ordering::Acquire) or Ordering::SeqCst or it will not see the change to the value on is_dirty. This should be kept in mind as it can cause much confusion in multi-threaded execution. The image below shows this operation on different threads and is called the "happens-before" relationship between threads.

If the store operation on the is_dirty is done with Relaxed Ordering instead, the following diagram shows the result, where the thread 2 will not see the change to thread 1 and could read an old value.

If you like this post please do look for the other blogs I have done and will do. I focus on concurrent systems so I hope this was helpful, and happy coding !!