SIEVE

An eviction algorithm simpler than LRU, for web caches

One queue, one pointer and one bit per object. A hit only sets a bit, so it takes no lock, and replacing LRU with SIEVE in a cache library takes about 20 lines of code.

See it run Paper Code Blog post

1 bit: per object, plus one queue and one pointer
≤ 21: lines changed to replace LRU in four cache libraries
2×: the throughput of optimized LRU at 16 threads
45%: of 1,559 traces where it beats every state-of-the-art algorithm

SIEVE runs in

ClickHouse
TiDB
Ceph
BIND 9
Apache Druid
DragonflyDB
Turso
Jetpack Compose
Apache Ignite

See every adopter

How it works

A hand that sifts one queue

New objects join the head of a single queue. When the cache is full, a hand walks from the tail toward the head: objects that were used since it last passed keep their place, and the first one that was not is evicted.

Next requests

Hits: 0
Misses: 0
Miss ratio: –

visited since the hand last passed not visited. The demo uses a cache of six objects so that every move is easy to follow.

1 queue
New objects go in at the head

Objects stay in the order they arrived. Nothing is ever moved back to the head, so the queue never needs reordering.
1 bit
A hit sets one bit

A hit marks the object as visited. If the bit is already set there is nothing to do at all: no lock and no pointer updates on the hot path.
hand
The hand sifts

To make room, the hand walks from the tail toward the head, clearing the bits of visited objects, and evicts the first one that was not visited. Past the head, it wraps back to the tail.
vs CLOCK
Survivors stay put

CLOCK moves a surviving object back to the head with the new ones. SIEVE leaves it where it is, so popular objects settle near the tail and new ones that are not reused leave quickly.

Results

Simple to adopt, efficient and fast

On 1,559 traces with 247 billion requests, SIEVE beats every state-of-the-art eviction algorithm on more than 45% of them, and it does so with less code and more throughput than LRU.

13–18% fewer misses than LRU

Miss ratio on a Zipf workload

α = 1, one panel per cache size as a share of the working set. Lower is better.

Data table

A better building block

SIEVE inside other algorithms

Mean miss ratio reduction from FIFO across traces, before and after SIEVE replaces each algorithm’s LRU or FIFO queue. Higher is better.

Data table

About an hour of work

Lines changed to replace LRU

In four popular cache libraries, tests not included.

Library	Language	Lines	Hours
groupcache	Go	21	<1
mnemonist	JavaScript	12	1
lru-rs	Rust	16	1
lru-dict	Python + C	21	<1

16%faster than optimized LRU on one thread

2×its throughput at 16 threads, in Cachelib

Charts redrawn from the figures in the paper and the blog post.

Use it

The whole algorithm fits on a card

Pick a library in your language, or replay your own traces against SIEVE in libCacheSim.

SIEVE, in pseudocode

# request x, queue T, size C, hand p
if x in T:                       # hit
    x.visited = true
else:                             # miss
    if |T| == C:                   # cache full
        obj = p or tail(T)
        while obj.visited:
            obj.visited = false
            obj = obj.prev or tail(T)
        p = obj.prev
        discard obj                    # eviction
    insert x at head(T)
    x.visited = false               # insertion