Clock Replacement

Why this stage exists

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.

What changes: a bit per frame and a hand

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:

• a pinned page is passed over, its bit left alone;
• a bit of 1 is set to 0, and the hand moves on: the page gets a second chance;
• a bit of 0 on an unpinned page: that is the victim.

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.

A full example

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:

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.

Output contract for this stage

The full definition is on the output contract page, section 25.

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.

What you should see when done

The worked sequence, on the five-page file of the earlier stages:

$droid --db notes.db --cache-pages 3
Welcome 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
>.exit
exiting.. 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.

Common bugs in this stage

• Moving the hand when a frame is empty. Filling an empty frame does not touch the hand. Only a sweep moves it.
• Leaving the hand on the victim's frame. After the new page goes in, the hand moves one past it. Otherwise the next sweep starts by clearing the page that just arrived.
• Clearing a pinned page's bit. The hand passes over a pinned page and leaves its bit alone.
• Sweeping forever. With every page pinned there is no victim. Check for that before sweeping, or stop after passing every frame once with nothing found, and restore nothing you changed: the hand must not move.
• Setting the bit to 0 for a new page. A page that just came in was just used: its bit is 1.
• Forgetting the empty frame after a bad page. When the page read for a frame fails its checksum, the victim is already gone and the frame stays empty. The next page goes there, without a sweep.

Language notes

The page above is the same for every language. These are the only language-specific hints.

• C: the bit can be a field of the frame struct next to its pin count and dirty flag. The hand is an unsigned index into the frames; moving past the last frame brings it back to the first.
• C++: the same. std::vector<bool> saves space, but a plain bool in the frame struct is simpler to read and debug.
• Rust: keep the hand as 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.
• Zig: the same shape, with the hand as a usize that wraps at frames.len. A labelled while loop that breaks out with the victim keeps the sweep readable.