Database Buffer Management

Petro is a storage engine that I am building to learn more about databases and this article explores the bufferpool management layer. The bufferpool is a write-back cache that sits between the disk layer and the index management layer. It has only one job, keep frequently accessed pages in memory. If it does its job well then the database will be more performant and there will be minimal disk read/write requests.

Bufferpool management has two components; a bufferpool and a page replacement policy. The bufferpool is an array of 4kb slots called frames and the page replacement policy determines what page to evict when the bufferpool is full. A good replacement policy ensures that popular pages stay in memory longer.

Bufferpool

The bufferpool also has a page table which maps page ids to frame indices. When then index layer asks for a page, we get the corresponding frame position from the page table. If the page table doesn’t have the page id and the bufferpool is not full, a disk request is made to fetch the page from disk.

The page’s data is then loaded into some frame and the page table is updated with the page id and frame position. Otherwise, if the page table already had the page entry, we get the frame position and index into the frames array to get the page’s data.

Writing pages happen in a similar manner. We first check if the page is in the page table. If not, we load the page into memory then write to it. The bufferpool pins frames during reading and writing in order to avoid eviction of pages that are actively used.

When the bufferpool is full and we need to load a page into memory, the bufferpool uses the page replacement policy to determine what page to evict. The replacement policy will say something like evict page 2. Then the bufferpool manager will use the page table to find the frame in which page 2’s data was stored and clean the frame.

The cleaned frame will then be added to an array of free frames maintained by the bufferpool. Before evicting a page the bufferpool always checks if there are any free frames. If the freeframe array is empty it then invokes the replacement policy to figure out what page to evict.

Page Replacement Policy

Petro uses the LRU-K page replacement algorithm which is an improvement on the LRU algorithm and tracks the last k accesses of some item. LRU is prone to sequential flooding, where a sequential scan will lead to eviction of other pages which are popular even though were not recently accessed.

For example, we always want to have our index pages to be in memory most of the time because we read/write to them frequently. LRU is incosiderate of this fact and it will evict most them during a sequential scan but LRU-k takes a page’s popularity into consideration and won’t recommend the eviction of most of the index pages.