CLOCK

CLOCK gives each entry a single reference bit. A hit sets the bit and does nothing else. When space is needed, a hand walks the entries in arrival order: an entry whose bit is set gets a second chance: its bit is cleared and the hand moves on. The first entry with a clear bit is evicted.

The result tracks LRU closely while making reads pure. That is the whole appeal: LRU has to reorder a shared list on every hit, so concurrent readers contend. CLOCK writes one bit that nobody else needs to see. Operating systems have used it since Multics for exactly this reason.

When to use it

• When the cache is read from many threads. This is the reason CLOCK exists: a hit sets one bit, so readers need no lock and no list surgery. Under contention CLOCK routinely beats exact LRU in throughput while giving up very little hit rate.
• As a drop-in for LRU where the write on hit has become the bottleneck.
• When you want LRU-like behaviour with one bit of metadata per entry rather than two pointers.
• In kernels, page caches and buffer pools, where it is already the conventional answer and will surprise nobody reading your code.

When not to use it

• When scans pass through. CLOCK inherits LRU’s central weakness: a sweep of fresh keys fills the cache with entries that will never be reused, and they each get a second chance on the way out. SIEVE and S3-FIFO fix this and are just as cheap on the hit path.
• When you need exact recency. CLOCK’s bit cannot distinguish “used once, long ago” from “used constantly”: both are just “set”. LFU and W-TinyLFU keep counts instead.
• When eviction latency must be bounded per call. A single eviction can walk the entire cache if every bit is set, which is O(n) for that one call even though the amortised cost is O(1). A latency-sensitive path may not want that tail.
• If you are choosing between CLOCK and SIEVE for a new system: SIEVE is the same cost, simpler to implement, and better on web-shaped workloads. CLOCK’s advantage is familiarity.

How it works

Entries sit in arrival order with one reference bit each. The hand is the front of that order.

onAccess(key, hit):
    if hit:  referenced[key] = 1        # the entire hit path
    else:    append key with referenced = 0

evict():
    loop:
        entry = take from the front
        if referenced[entry]:
            referenced[entry] = 0       # second chance
            append entry to the back
        else:
            return entry

This is the queue formulation, usually called second-chance. It is the same algorithm as the textbook circular buffer with a rotating hand: re-examining an entry and pushing it back is exactly what advancing the hand past it does, and the queue’s front is the hand. The queue form is written here because it is easier to read and easier to reproduce identically in three languages.

Tie-breaking. Among entries with clear bits, the oldest is evicted, and the sweep visits entries strictly in arrival order.

Parameters

Complexity

O(1) amortised for access and eviction. A hit is a single byte write. A single eviction may walk up to n entries when every bit is set, but each step it takes clears a bit, so n consecutive evictions cost O(n) in total.

C memory: 43.8 bytes per entry at capacity 1000, measured with pb_cache_clock.memory_bytes: 8 for the key, 1 for the reference bit, 4 for the order ring, 4 for the free stack, and about 27 for the hash table. Slightly less than LRU’s 46.8, because one bit replaces a second list link.

Source

Corbató, A paging experiment with the Multics system (MIT Project MAC, 1968).

Related: LRU is what CLOCK approximates. SIEVE is CLOCK with one change: survivors are not moved to the back. It is better on web workloads. FIFO is CLOCK with the reference bit removed.

Notes

No patents.

CLOCK, second-chance and “the clock algorithm” are the same thing. Descriptions differ in whether they draw a circular buffer with a hand or a queue with re-insertion. The eviction sequence is identical, and this entry documents the equivalence rather than picking a side.

CLOCK-Pro is a substantially different and more complex algorithm that distinguishes hot from cold pages by reuse distance. It shares the name and little else.