CMU 15-445

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

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

• CheckWritePage

  • HIT, record access
  • Free memory, load
  • Evict

Links

• C++ Move Semantics