Algorithms

CLOCK

Approximate-LRU cache eviction with a circular reference bit.

In plain terms

Each entry has a referenced bit. Eviction sweeps a clock hand; sets the bit to 0; evicts when it sees a 0. Used by Redis (allkeys-lru), Postgres buffer pool.

Origin

Fernando Corbato's CLOCK was first described in 1968 as the page-replacement policy for Multics. Postgres uses a variant in its buffer pool; Redis allkeys-lru uses it as approximate LRU.

Where it shows up in production

Postgres buffer pool Clock-sweep replacement — much cheaper than maintaining strict LRU on hot tables.
Redis allkeys-lru Sampled approximate LRU; CLOCK-like behaviour at scale.

On Semicolony

Simulator cache eviction

Sources & further reading

Article Wikipedia — Page replacement algorithms
Docs Cache eviction simulator (Semicolony)

Found this useful?