Choose the page that leaves a full pool with the clock: a reference bit on every frame, set by each hit, and a hand that sweeps the frames clearing bits until it finds an unpinned page whose bit is already 0. Show the hand, the bits and the pins with pager clock.
Until now, which page leaves a full pool has been up to you. Most first versions pick the page that came in first, or the next frame in turn. That is simple, it is correct, and it is bad at the one thing a cache is for.
Think of what a query does to a B+Tree. Every lookup starts at the root. With 16 frames and a table of a few hundred leaves, the root is the single most used page in the database. First in, first out does not know that. The root came in early, so it is among the first to be thrown out, and the next lookup reads it straight back from the file. The pages a workload uses most are exactly the ones that have been in the pool longest, and an order-of-arrival policy evicts them for that reason.
What you want is the page that has gone longest without being used. Tracking that exactly means reordering a list on every single hit, which is a lot of work for the most common event in the pool. The clock gets most of the benefit for almost none of the cost: one bit per frame, set on a hit, and a hand that only moves when something has to leave.
From this stage the choice is no longer yours. The contract fixes it exactly, so the counters are exact with any pool, and the tests can watch the hand move.
Picture the frames in a circle with a hand pointing at one of them. Each frame has a reference bit. A hit sets the bit of its frame to 1, and that is all a hit costs.
When a page must come in and there is an empty frame, it goes to the lowest-numbered one, its bit set to 1, and the hand stays where it is. When there is no empty frame, the hand sweeps:
The new page takes the victim's frame with its bit set to 1, and the hand moves one past it. A page that was used since the hand last went by survives one more revolution. A page nobody touched in a whole revolution leaves.
If every frame is pinned the sweep can never stop, so it does not start: the request is 01201 and the hand stays where it was.
The worked sequence of the contract, on a file of five pages with --cache-pages 3. Opening reads page 0 into frame 0 with its bit at 1, before the first command:
| Command | What happens | Frame 0 | Frame 1 | Frame 2 | Hand |
|---|---|---|---|---|---|
| open | page 0 read, lowest empty frame | page 0, bit 1 | empty | empty | 0 |
pager get 1 | miss, lowest empty frame | page 0, bit 1 | page 1, bit 1 | empty | 0 |
pager get 2 | miss, lowest empty frame | page 0, bit 1 | page 1, bit 1 | page 2, bit 1 | 0 |
pager get 3 | miss, no empty frame: the hand clears frames 0, 1 and 2, comes back to frame 0, finds bit 0 and evicts page 0 | page 3, bit 1 | page 1, bit 0 | page 2, bit 0 | 1 |
pager get 1 | hit: set the bit | page 3, bit 1 | page 1, bit 1 | page 2, bit 0 | 1 |
pager get 4 | miss: frame 1 is cleared, frame 2 has bit 0, page 2 leaves | page 3, bit 1 | page 1, bit 0 | page 4, bit 1 | 0 |
Page 2 leaves, not page 1, because page 1 was used again after the hand last went by. Leave out that pager get 1 and page 1 is the one that goes. Evicting in the order pages came in would have thrown out page 1 either way.
The first sweep goes all the way round. When every bit is 1, the hand clears all of them and comes back to where it started. That is expected: all three pages had been used since the last sweep, which was never.
Least recently used. LRU evicts the page whose last use is oldest, exactly. It needs every hit to move its page to the front of a list, and on a busy pool that list becomes the bottleneck. The clock approximates it with one bit. PostgreSQL uses a clock with a small usage count in place of the bit; MySQL's InnoDB uses an LRU list split in two, so that one big scan cannot flush the hot pages out; LRU-K and 2Q are other answers to the same problem.
The state of the clock is small: one bit per frame, and one frame number.
Only when no frame is empty does the hand move.
A page that fails its checksum makes room like any other.
The full definition is on the output contract page, section 25.
| Input | Output |
|---|---|
pager clock | [PAGER] Clock: hand=<i> frames=<n>, then for each frame in order [PAGER] Frame <i>: page=<p> ref=<0 or 1> pin=<k> or [PAGER] Frame <i>: empty |
pager clock requests nothing. pager frames does not change: it lists pages, in page order; pager clock lists frames, in frame order. From this stage the counters after the pager commands of section 23 are exact with any pool.
The worked sequence, on the five-page file of the earlier stages:
$droid --db notes.db --cache-pages 3Welcome to droid!>pager get 1[PAGER] Get page 1: CACHE_MISS (loaded from disk)>pager get 2[PAGER] Get page 2: CACHE_MISS (loaded from disk)>pager get 3[PAGER] Get page 3: CACHE_MISS (loaded from disk)>pager clock[PAGER] Clock: hand=1 frames=3[PAGER] Frame 0: page=3 ref=1 pin=0[PAGER] Frame 1: page=1 ref=0 pin=0[PAGER] Frame 2: page=2 ref=0 pin=0>pager get 1[PAGER] Get page 1: CACHE_HIT>pager get 4[PAGER] Get page 4: CACHE_MISS (loaded from disk)>pager clock[PAGER] Clock: hand=0 frames=3[PAGER] Frame 0: page=3 ref=1 pin=0[PAGER] Frame 1: page=1 ref=0 pin=0[PAGER] Frame 2: page=4 ref=1 pin=0>.exitexiting.. good bye!
Things to notice. After page 3 came in, the hand was at 1, not 0: it moves one past the frame it filled. The hit on page 1 set its bit back to 1, which is what saved it: the sweep for page 4 cleared it instead of evicting it, and moved on to page 2.
The page above is the same for every language. These are the only language-specific hints.
std::vector<bool> saves space, but a plain bool in the frame struct is simpler to read and debug.usize and the frames in a Vec; the sweep is a loop with an index, not an iterator, because it wraps round and stops in the middle.usize that wraps at frames.len. A labelled while loop that breaks out with the victim keeps the sweep readable.