A database can't keep the whole table in memory, so it keeps a fixed-size cache of recently-used disk pages -- Postgres calls this shared_buffers, DuckDB calls it its buffer manager. When the cache is full and a new page needs to come in, something has to be evicted; this exercise uses the simplest reasonable policy, least-recently-used (LRU).

Implement BufferPool.get(page_id), BufferPool.put(page_id, data, dirty=True), and BufferPool.flush(page_id):

• get(page_id) returns the page's cached data, or None if it isn't cached. A successful get counts as "using" that page, but it's a READ -- it must never change a page's dirty status.
• put(page_id, data, dirty=True) inserts or updates a page and sets its dirty flag (pass dirty=False when loading a page fresh from disk -- it starts out matching what's on disk, so there's nothing to write back yet). If the pool is already at capacity and page_id isn't already cached, evict the least-recently-used page first (the one that hasn't been get or put in the longest time) -- flushing it first if it's dirty.
• flush(page_id): if page_id is cached AND dirty, call self._flush_callback(page_id, data) and clear its dirty bit. No-op if page_id isn't cached, or is cached but already clean.

The missing link: eviction can lose data if you're not careful

A page is dirty the moment it's modified in memory and stops matching what's actually on disk. If a buffer pool evicts a dirty page to make room for something else without first writing it back, that write is gone forever -- the in-memory version simply vanishes, and disk still has the stale data. A correct eviction policy isn't just "pick the least-recently-used page" -- it's "pick the least-recently-used page, and if it's dirty, write it back before dropping it." Real systems even distinguish these costs: evicting a clean page is free (disk already has an identical copy), while evicting a dirty page requires an actual write, which is why some systems proactively flush dirty pages in the background before they'd ever need to be evicted under pressure.

Example

written = []
pool = BufferPool(capacity=2, flush_callback=lambda pid, data: written.append(pid))
pool.put(1, "a")           # dirty
pool.put(2, "b", dirty=False)  # loaded from disk, clean
pool.put(3, "c")           # evicts 1 -- dirty, so flush_callback(1, "a") runs first
written                    # -> [1]

Constraints

• Capacity is fixed and always >= 1.
• Updating an already-cached page's data (via put) should not evict anything.
• flush_callback may be None (the default) -- in that case, a dirty page's write is simply never observed by anything outside the pool, but eviction must still proceed (no exception) and must still clear the dirty bit.

Real-world grounding

• Postgres's buffer manager: src/backend/storage/buffer/bufmgr.c -- worth knowing: Postgres doesn't use exact LRU, it uses a cheaper approximation called "clock sweep" for performance under concurrency. This exercise teaches the concept LRU represents; real systems trade a little precision for speed. Search that file for BM_DIRTY to see the real dirty-bit flag this exercise's _dirty set represents, and FlushBuffer for the real write-back-before-eviction path.
• DuckDB's buffer manager: src/storage/buffer_manager.cpp