YuNing's Thought

CMU 15-445

3 min read

2025 Fall

Projects1: Buffer Pool Manager

ARC Cache Replacement Policy

  • Project #1 - Buffer Pool Manager | CMU 15-445/645 :: Intro to Database Systems (Fall 2025)

  • MRU List: tracks the frames and their corresponding pages that were accessed exactly once.

  • MFU List: tracks the frames and their corresponding pages that were accessed more than once

  • 2 Ghost List: tracks pages that are no longer in buffer pool, but are recently evicted.

  • replacer_size_: maximum number of frames that the replacer supports is the same as the size of the buffer pool.

  • curr_size_: current evictable size

  • mru_target_size_: adapts to the workload observed

  • Page vs Frame

    • In buffer pool: 1-1 mapping
    • Evicted page: no association with any frames

When performing RecordAccess

  1. Page in MRU/MFU: Cache Hit
  2. Page in MRU ghost: Adapt target size
    • No over replacer_size
    • If: MRU_Ghost.size >= MFU_Ghost.size: MRU_target_size += 1
    • Else: MRU_target_size += MFU_Ghost.size / MRU_Ghost.size
    • Hit
  3. Page in MFU ghost: same idea
  4. Page not in replacer:
    • MRU.size + MRU_Ghost.size == replacer_size: kill the last element in ghost list and add to the front of MRU
    • orMRU.size + MRU_Ghost.size + MFU.size + MFU_Ghost.size = 2 * replacer_size: kill the last element in the MFU Ghost list and add to front of MRU
    • or add to front of MRU

Evictable: when set manually, not automatically ATM

Disk Scheduler

EZ

Buffer Pool Manager

Only buffer pool manager call constructor
Fetch db pages from disk with DiskScheduler
Write dirty pages to disk

Buffer Pool

  • FrameHeader
  • FlushPage

  • FlushPageUnsafe

Page Guard

  • RAII

    • Thread Safe - no manual lock required for page

  • ReadPageGuard

    • no thread can be mutating the page when there’s read guard

  • WritePageGuard

  • CheckedWritePage

    • HIT, record access, set non-evictable, set is_dirty
    • Free memory, load
    • Evict

Project 2 - B+Tree

Very complicated

Internal

  • Key: indexed key
  • Value: Pageid

Leaf

  • Tombstone:
    • Key: num_tombstones_ (counting)
    • Value: index of tomb in leaf node
    • Change on insertion and rebuild

Insertion

  • Get root page form header
  • Find the appropriate leaf, be aware of tombstone
    • Leaf is not full, use read page guard — Optimistic
    • Leaf is full, upgrade read lock to write lock for the path
  • Split
    • Simple split
      • If path is empty:
        • We are at the root page: create
    • Multiple Split
      • Split leaf, but the parent internal page is also full
      • Insert into the parent internal page (to the remanning slot, then split the internal page)
        • Insert to the parent’s parent, repeat

Graph View

Backlinks