Readyset Internals: The left-right pattern: lock-free cache

Readyset serves cached reads without ever taking a lock. It is one of the questions we get asked most often, so we wanted to write it down properly and put real numbers behind it.

The moment where a writer makes new data visible to every reader is a single atomic store. On the machine we measured on, that store takes about 1.2 nanoseconds. No reader waits for it, and no writer waits for a reader. This post explains how that works and shows the measurements.

What we'll cover

• Why a lock around hot cache data falls apart under load.
• The left-right pattern Readyset uses instead, with an animation.
• Where Readyset actually triggers the swap in production.
• The measured cost of the swap, against the exact crate Readyset ships.
• The honest costs, because there always are some.

The problem with a lock

Most caches put a lock around their hot data. Readers grab it, writers grab it, and once you have real traffic everyone is waiting on everyone else. On a machine with a lot of cores it gets worse, because that single lock keeps bouncing between CPUs and your throughput stops climbing no matter how many cores you add.

That last part is the one people underestimate. Even a "fast" lock that nobody is contending for still forces the cache line holding the lock word to migrate between cores. Add readers and the line ping-pongs, and the read path that was supposed to be cheap starts spending its time on coherence traffic instead of on your data.

The left-right idea

We do it differently. The pattern is called left-right. The animation below covers it better than words can, but here is the short version.

We keep two copies of the map. One is the read side, one is the write side. Readers follow a pointer to the read side and start reading. No lock, nothing to wait on. The writer works on the other copy, the one no reader is touching. When it's done it flips a single pointer, and from that point new readers see the new data. Then it replays the same changes onto the old copy so the two stay in sync for the next flip.

The only shared, synchronized step in the whole dance is that pointer flip. Everything else happens on a copy that the other side is not looking at.

Where this lives in Readyset

What's a crate? If you don't write Rust: a crate is just Rust's word for a package, a reusable unit of library code you pull in as a dependency, the way you would a package in npm or a gem in Ruby. A program like Readyset is assembled from hundreds of them.

The crate that matters here is left-right, a small open-source crate that implements exactly the two-copies-and-one-pointer trick from the animation above. Our own reader-map crate wraps it with the map operations a cache reader needs. So when we say "the swap", we mean the operation inside left-right, and Readyset uses version 0.11.7 of it.

The atomic swap that publishes a change is a single instruction: one atomic store that flips which copy readers point at. Everything else around it exists only to make that one store safe.

A reader takes the lock-free path: it follows the pointer to the current read copy, reads a consistent snapshot, and is done. A writer cannot reuse a copy until the readers that were on it have moved off, and it knows they have by watching those readers' progress, not by holding a lock over them.

In production the swap is driven by the dataflow engine, not per row. Upstream changes are batched and coalesced before they reach the reader, then the swap happens once per batch (after a normal pass, after a backfill fills a hole, or after an eviction). So the swap we measure is exactly the operation that runs every time Readyset makes a batch of upstream changes visible to your queries.

Measuring the swap

To put a number on it, we measured the exact crate and version Readyset uses, left-right 0.11.7, on its own. So the swap we time is the same swap that runs in a Readyset reader node. All the numbers below come from an Apple M3 Max with 16 cores.

A few words first, because the labels in the tables below are jargon:

• oplog (operation log): the running list of changes the writer has made to its copy but has not yet shown to readers. It is the "operation log" box in the animation.
• swap: the single atomic store that flips the read pointer from one copy to the other. This is the actual left-to-right switch, the thing readers observe.
• publish: the full operation that makes a batch visible. It waits for readers to leave the old copy, does the swap, then replays the batch onto the now-stale copy.
• replay: re-applying that batch of changes to the old copy after the swap, so the two copies match again before the next flip.
• empty oplog (why we measure it): we publish with nothing pending, so the only work left is the swap and its bookkeeping. That isolates the cost of the flip itself, with no data movement mixed in.

With that vocabulary, the measurements cover four things: the raw atomic store on its own; a publish with an empty oplog and no readers; a publish as the batch of pending writes grows; and a publish while readers hammer the read side.

The pointer flip itself

The flip readers observe is a single atomic store, about 1.2 ns. A full publish with nothing to replay and no readers in the way costs about 10 ns, which is the bookkeeping around the swap. That is the whole "switch from left to right". It does not depend on how much data the map holds, because we are moving a pointer, not copying a map.

Making real writes visible

The interesting cost is not the flip, it is replaying the batch of changes onto the stale copy afterward so the two sides match. That scales with the size of the batch, not with the size of the cache:

pending ops in the batch	publish p50	publish p99	ns per op
1	42 ns	42 ns	42.00 ns
16	250 ns	334 ns	15.62 ns
256	3500 ns	4709 ns	13.67 ns
4096	61542 ns	79375 ns	15.02 ns
65536	1274458 ns	2370167 ns	19.45 ns

The per-op cost is flat, roughly 13 to 20 nanoseconds per row, all the way up. A publish that makes a 256-row batch visible finishes in about 3.5 microseconds. This is why Readyset batches: amortizing the per-batch overhead across many rows keeps the marginal cost per row in the low tens of nanoseconds.

Under reader pressure

A publish has to wait for any reader still on the old copy to finish before it reuses that copy. So the last question is what happens when readers are busy. Here we keep several reader threads reading as fast as they can and publish one change at a time:

reader threads	publish p50	publish p99
0	41 ns	42 ns
1	125 ns	542 ns
2	125 ns	375 ns
4	333 ns	542 ns
8	500 ns	959 ns

Eight threads doing nothing but reading as fast as they can, and the writer still publishes in about half a microsecond. The cost grows slowly because the writer only waits for readers that were already mid-read when it wanted to swap, and a read is short. Crucially, look at it from the other direction: the readers never stalled. Their latency does not appear in this table because the swap never blocked them. That is the whole point.

So why is it fast

Three reasons, and the numbers above are each of them.

The read path never synchronizes on anything. No lock to acquire, no compare-and-swap on the hot path, no contention between readers. Reads scale with cores instead of fighting over one lock word.

Readers and writers are never in each other's way, because they are literally on different copies. The only shared step is that one pointer swap, and we measured it at around a nanosecond.

There is no cache-line ping-pong on the read side. Nobody is hammering a shared lock, so the CPU caches stay calm and reads stay cheap even when a writer is busy publishing behind them.

The honest costs

There are two, and they are easy to state.

We hold the data twice. Two copies of the map means roughly double the memory for that index. For a cache that trades memory for read latency, that is usually a fine trade, but it is real and you should size for it.

A write is not visible until the next swap. Between the moment a writer applies a change to its copy and the moment it publishes, readers still see the old value. For a read-heavy cache this is exactly the consistency model you already expect, but it is the reason we are careful about which queries we cache. A path that has to read its own writes immediately is not a good fit, and we do not cache those.

We like this design because it is not clever for the sake of being clever. It keeps the read path honest, and the cost is easy to explain. That last part matters more than we'd like to admit.