Database Storage, Buffer Manager & Files

In this chapter we will go through the storage manager of a DBMS before diving into the buffer manager.

Storage Manager of DBMS

The storage manager of a DBMS provides an interface between data stored in the database and the queries received by the DBMS.

It consists of the following components:

1. File & access methods manager
2. Buffer pool manager
3. Disk space manager

• Data is stored & retrieved in units called disk blocks (or pages).
  • Each block consists of one or more contiguous disk sectors.

File and access methods manager

This components is the file layer in the storage manager and deals with the organization and retrieval of data,

Disk Space manager

The disk space manager keeps track of pages used by the file layer.

Buffer manager

The buffer manager controls the reading / writing of the disk pages. It maintains a buffer pool of pages in memory.

The Buffer manager

The main memory allocated to a DBMS goes to the buffer pool. It is partitioned into block-sized pages called frames.

Clients of the buffer pool can do the following:

1. Request for a disk page to be fetched into the buffer pool
2. Release a disk page in the buffer pool

All data requested by other components in the DBMS is fetched from the buffer pool first before being returned to the requesting component.

A page in the buffer is dirty if it has been modified but not updated on the disk. When the dirty page is replaced, the changes will be written to the disk.

For each frame in the buffer pool, the buffer manager maintains the following information:

1. Pin Count: The number of clients whi are using the current page (Initialized to 0)
2. Dirty Flag: Whether the page is dirty (Initialized to false)

Some Terms

Handling a request for a page

The general algorithm is as follows, where P is the page requested. In this example, I will be using python to illustrate the algorithm.

def handle_page_request(page_id: int) -> Page:
    """Handles a request for a page"""
    # Check if the page is already in the buffer pool
    if page_id in buffer_pool:
        # If it is, increase the pin count (pinning)
        buffer_pool[page_id].pin_count += 1
        return buffer_pool[page_id]

    # If it is not, find a free frame
    free_frame = find_free_frame()

    # If there is a free frame, load the page into the buffer pool
    if free_frame is not None:
        buffer_pool[page_id] = Page(page_id, free_frame)
        return buffer_pool[page_id]

    # If there is no free frame, find a victim page (IE: Page to be removed)
    victim_page = find_victim_page() # Replacement Algorithm is applied.

    # If there are no pages to be removed, return an error
    if victim_page is None:
        raise BufferPoolFullError()

    # If the victim page is dirty, write it to disk
    if victim_page.dirty:
        write_page_to_disk(victim_page)

    # Remove the victim page from the buffer pool
    del buffer_pool[victim_page.page_id]

    # Load the page into the buffer pool
    buffer_pool[page_id] = Page(page_id, victim_page.frame_id)

    return buffer_pool[page_id]

Properties of the buffer manager

• When unpinning a page, the dirty flag should be updated if the page is dirty.
• A page in the buffer can only be replaced if its pin count is 0.
• Before replacing the page, the dirty flag should be checked.
  • If the page is dirty, it should be written to disk.
• The Buffer manager coordinates with the Transaction manager to ensure data correctness and recoverability.
  • For crash resilience.

Replacement Policies

The replacement policies decides which unpinned page to replace when the buffer pool is full. All the algorithms tries to help by reducing the number of disk I/Os used by guesses which page will not be used in the near future.

Here are some commonly used replacement policies:

1. Random
2. First-in-first-out (FIFO)
3. Most recently used (MRU)
4. Least recently used (LRU)
5. Clock (Variant of LRU)

There are also other replacement policies which are not stated here.

Random Replacement

This is the simplest replacement policy. It randomly selects a page to be replaced.

Fifo Replacement

This replacement policy replaces the page that has been in the buffer pool the longest.

• The first page that was loaded into the buffer pool will be the first to be replaced.
• This is usually implemented in the form of a queue.
• This caching policy is effectively only if the access pattern of the page is from the oldest to the newest.

Most Recently Used (MRU) Replacement

This replacement policy replaces the page that is accessed the most recently.

• The page that was accessed most recently will be the first to be replaced.
• When there is a cache hit, the page will be moved to be the first to be replaced.
• This access policy is good when there is are a bunch of pages accessed in a loop pattern.

Least Recently Used (LRU) Replacement

This replacement policy replaces the page that is accessed the oldest page.

• The page that was accessed the earliest will be the first to be replaced.
• When there is a cache hit, the page will be moved to be the last to be replaced.
• This access policy is good when the data that is most recently used is usually accessed again.

Clock Replacement

This replacement policy is a variant of LRU which is easier to implement.

• Each frame has a reference bit.
• This is turned on when its pin count becomes 0
• The first page that has referenced bit off and pin count = 0 will be replaced.

Click here to see an illustration of the algorithm (Figma)

Files

The file abstraction

• Each relation is a file of records
• Each record has a unique record identifier called RID
• Common file operations
  • Create a file
  • Delete a file
  • Insert a record
  • Delete a record with a given RID
  • Get a record with a given RID
  • Scan all records

File Formats

There are different ways to arrange the files in the disk.

1. Heap File: Unordered file
   1. There are 2 types of implementation of the Heap File
      1. Linked List implementation
      2. Page Directory Implementation
2. Sorted File: Records are ordered by some search key
3. Hash File: Records are located in blocks via a hash function

Page format

These are the possible page formats.

1. Fixed Length Records
   1. Implementations of Fix length records
      1. Packed Organization: Store records in contiguous slots
      2. Unpacked Organization: Use a bit array to maintain free slots
   2. Fields are stored consecutively.
2. Variable Length Records
   1. Implementation of Variable length records
      1. Slotted Page organization: Stores an array of RID pointers and store the records in a separate spae in memory
   2. Records are delimited with a special symbols OR there is an array of offsets at the beginning of the field.

One way to create an RID from the page format is using the formula RID = Page ID + Slot ID

Useful Links

1. Structure of Database Management Systems
2. Clock replacement policy
3. Illustration of the clock replacement algorithm