Buffer Pools: Separate Residency, Ownership, and Durability

A page can be old enough to evict, still in use by a reader, and contain changes that have never reached storage. One “cached” boolean cannot express those three facts. This module builds the state needed to make a safe decision.

You should already know what a disk page and an LSN represent. After the lesson, you should be able to trace pin counts and recency independently, explain why a dirty page needs special handling, and implement the buffer-pool simulator without confusing its eviction trace with actual durable writes.

Start with a failure

A query fetches page 7 and keeps a pointer to its bytes. A second query fetches page 7 too. The first query finishes. If the buffer manager marks the frame “unused” at that point, it may reuse the memory for page 9 while the second query is still reading it. The problem is not the eviction policy: the manager lost track of a live user.

Represent use with a count. Two fetches give pin=2; one unpin leaves pin=1. Only pin=0 makes the page an eviction candidate. A pin keeps a page resident; it does not grant a transaction permission to read or modify its contents. Concurrency protection and transactional locks solve different problems.

The smallest useful state

Keep a map from page ID to frame metadata and a separate ordering of resident pages by their last fetch. A real frame also contains the page's bytes. The exercise needs only this metadata:

State	Question it answers	What changes it
Resident mapping	Is this page already cached?	Load / eviction
Pin count	How many outstanding fetches use it?	Fetch / unpin
Dirty flag	Has this resident copy been modified?	Dirty unpin in the exercise
Recency position	How recently was it fetched?	Successful fetch

The distinction between a frame, its current page, dirty state, and pin count follows the conventional buffer-manager model described in Berkeley's buffer management notes. The exact recency and extra-unpin rules below are this exercise's contract.

Write these invariants before writing the simulator:

1. The resident map contains at most capacity distinct pages when capacity is positive. The recency list contains each resident page exactly once.
2. A pin count is never negative. Repeated fetches increment it; they do not allocate duplicate frames.
3. An eviction removes only a zero-pin page and removes it from both structures.
4. During one residency, dirty can change from false to true, never back to false. A later clean unpin does not prove earlier writes were flushed.
5. The oldest eligible page is selected. The oldest resident page may be pinned.

These are independently testable. A correct LRU ordering does not compensate for a bad pin count, and correct pin counts do not repair a lost dirty flag.

Derive the transitions

On a cache hit, increment the page's pin count and move its existing entry to most recent. On a miss with room, create a clean frame with pin=1. On a full-pool miss, scan oldest to newest until you find pin=0. Record the victim's dirty flag, remove its frame, then load the requested page.

If every frame is pinned, there is no legal victim. The exercise stops with ok=false, preserving evictions already made. A larger engine might wait for a frame or fail the request; evicting a pinned page is not an acceptable fallback.

Unpin is deliberately permissive here: a missing page is ignored, a zero count stays zero, and dirty=true marks any resident page dirty. Unpin does not refresh recency. In an API with stricter ownership tracking, an unmatched unpin would usually be an error; implement the declared contract for this simulator.

Work the trace before implementing

Use capacity 2. Write the list left to right from least to most recent; * marks dirty. A tuple is (page, pin count).

Step	Operation	Recency list after operation	Explanation
1	fetch A	(A,1)	New clean frame
2	fetch B	(A,1), (B,1)	Pool now full
3	fetch A	(B,1), (A,2)	Hit; second pin and new recency
4	unpin A, dirty=true	(B,1), (A,1)*	A is still pinned
5	unpin B	(B,0), (A,1)*	B becomes eligible, recency unchanged
6	fetch C	(A,1)*, (C,1)	Evict clean B
7	unpin A	(A,0)*, (C,1)	Dirty flag remains set
8	fetch D	(C,1), (D,1)	Evict dirty A
9	fetch E	unchanged	Failure: both pages pinned

The output is [(B,false), (A,true)] and ok=false. There is no eviction for step 9 and no attempt to continue after it. Notice that fetch A changed both ownership and order, while unpin A changed ownership but not order.

Where WAL enters the real write path

The simulator reports a dirty eviction; it has no page bytes or log-flush operations. A real buffer manager must first make the relevant WAL durable, then write the dirty page before reusing its frame. Merely appending a log record to an in-memory buffer is insufficient. PostgreSQL's WAL introduction explains the log-before-data ordering.

With pageLSN=42 and the durable log ending at 39, a page write must wait until the durable log covers 42. After the page write completes, that page image can be regarded as clean if no concurrent modification superseded the written image. The WAL test is an ordering test, not a request to flush every database page.

Why does this order matter? If the page reaches storage with uncommitted bytes but the matching log disappears in a crash, recovery has no reliable description of what to undo. If a committed page has not reached storage but its redo log has, recovery can reconstruct it. The next module works through both cases.

A pin, a dirty flag, and a transaction lock therefore answer separate questions: “May I replace this frame?”, “Does this copy need writing?”, and “May this transaction access this data?” None can stand in for the others.

Implementation choices and costs

A map plus an ordered slice is enough to learn the state machine. Moving a hit to most recent and finding an eligible victim may each scan C frames. For M operations the simple implementation costs O(MC) time and O(C) resident metadata, plus the eviction output.

A doubly linked list with page-to-node lookup makes recency moves O(1), but a list containing pinned pages can still require a scan for an eligible victim. Maintaining only an eligible list introduces a new subtlety: a page's unpin time is not its last-fetch time. Any optimization must preserve the specified order.

LRU is also not universally the best policy. With capacity 2, the fetch/unpin sequence A,B,C,A,B,C has no hits after filling: every reuse arrives after its page was displaced. This follows directly from reuse distance. Improving the policy is a different task from proving pin and dirty handling correct.

Reconstruct and check

1. Pin counterexample. Capacity 1; fetch 5, fetch 5, unpin 5, fetch 6. What must happen?

Answer: The final fetch fails with no evictions. Page 5 has one remaining pin. A boolean “pinned” implementation that clears on unpin will get this wrong.

2. Recency counterexample. Capacity 2; fetch/unpin A, fetch/unpin B, fetch/unpin A, then unpin B again and fetch C. Which page leaves?

Answer: B. A's second fetch refreshed its position; the extra unpin of B did not. This distinguishes last access from last metadata operation.

3. Dirty counterexample. A is dirtied, unpinned, fetched again, then unpinned with dirty=false. Is its later eviction clean?

Answer: No. Dirty is accumulated with logical OR during residency. Only a completed write could justify clearing it, and this API has no flush operation.

4. Explain the boundary. A submitted solution reports the right victims and dirty flags. Has it proved WAL durability?

Answer: No. It has proved decisions about simulated frames. Durability needs log/page persistence state and crash tests, none of which this signature exposes.

Implement the problem, then reproduce the table using your own state variables. If you cannot explain each transition without looking at the code, revisit the invariants before optimizing the data structures.