The question this answers
How do I let readers proceed without a lock while a writer is changing the same structure?
A subscription table read on every one of 12,000 requests per second, updated a few dozen times an hour when a subscription is added or cancelled.
One atomic reference to the current table version. The table objects themselves are immutable once published; the only mutable memory in the design is that single reference slot.
A reader that has taken the reference sees a complete, self-consistent table for its whole request, and no update is ever lost — the published version reflects every committed write in some serial order.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
Readers never wait; the writer never blocks a reader
The shape is three moves. A reader loads the current pointer once and works against whatever version it got. A writer clones the current version, applies its change to the clone, and stores the clone into the pointer. Old versions stay alive and correct as long as somebody still holds them, and are reclaimed when the last holder lets go.
What that buys is asymmetry, and asymmetry is the point. Read cost is one atomic load — no lock, no waiting, no cache line bouncing between cores under a write lock. Write cost is a full clone of the structure. You would never choose that for a write-heavy workload, and you would almost always choose it for 12,000 reads per second against 30 writes per hour.
The Operating Systems domain owns the kernel version of this mechanism — Copy-on-Write there covers how fork shares pages read-only and copies a page on the first write fault. That is the same idea implemented in the MMU with page granularity. This lesson is about choosing it as an application-level concurrency strategy, where the granularity is a data structure and the fault is a branch you wrote yourself.
The schedule that eats an update
Copy-on-write is safe for readers by construction. It is not automatically safe for writers, and the naive clone-modify-store loop has a lost update sitting inside it that survives every read-side test you write.
Two writers both load v2, both clone it, both apply their own change to their own clone, and both store. The second store wins and the first writer's change is gone — with no error, no exception and no log line, because from each writer's point of view everything succeeded. This is exactly the lost update of Optimistic Concurrency Control, and the fix is the same: do not store unconditionally, compare-and-swap against the version you read, and retry when it moved.
The other trap is retention. Every in-flight reader pins a version. If a reader can run for minutes — a long report, a stuck request, a paused debugger — and the writer publishes every few seconds, you retain every version in between. The design that looked memory-neutral becomes an unbounded retention leak, and it presents as growing heap with no obvious owner. See Safe Publication: Handing Over a Finished Object for the ordering half and be explicit about the lifetime half.
| # | Writer 1 (add sub #900) | Writer 2 (cancel sub #14) | Reader | State |
|---|---|---|---|---|
| 1 | base = current.load() -> v2 | · | · | current=v2 w1base=v2 |
| 2 | · | base = current.load() -> v2 | · | current=v2 w2base=v2 |
| 3 | clone v2, add #900 -> vA (private) | · | · | current=v2 |
| 4 | · | clone v2, cancel #14 -> vB (private) | · | current=v2 |
| 5 | current.store(vA) | · | · | current=vA has900=yes has14=yes |
| 6 | · | · | current.load() -> vA; serves request | current=vA |
| 7 | · | current.store(vB) | · | current=vB has900=no has14=no ✕ Subscription #900 was added, the write returned success, and it is no longer in the published table. Nothing failed. |
When the clone is too big: share the parts nobody touched
Whole-structure cloning is fine at 40k entries and ruinous at 40 million. The escape is structural sharing: instead of copying the structure, copy only the path from the root to the changed node and point the new root at the old, untouched subtrees. A write costs O(log n) small nodes; every previously published root remains a complete, valid version.
That is the same trick a database plays with MVCC: Multi-Version Concurrency Control over in Database Engineering, one level down: rows carry versions, readers see the snapshot valid at their start, and writers create new row versions rather than overwriting. The reason the analogy is worth carrying is that the failure modes transfer intact — long-running readers pin old versions, and version cleanup is a real background cost in both designs.
Whichever granularity you pick, the reclamation question does not go away: when is it safe to free a version? A refcounted pointer answers it automatically at the cost of an atomic increment on every read, which can itself become the contended cache line. Epoch-based or hazard-pointer reclamation avoids that at a substantial jump in complexity, and is where "we implemented copy-on-write" quietly becomes "we implemented a memory reclamation scheme". Price that before starting.
1std::atomic<std::shared_ptr<const Table>> current;2 3// Reader: one atomic load, no lock, never blocks, never blocked.4std::shared_ptr<const Table> snapshot() {5 return current.load(std::memory_order_acquire);6}7 8// Writer: clone, mutate the clone, publish only if nobody moved the pointer.9void apply(const Change& c) {10 for (;;) {11 auto base = current.load(std::memory_order_acquire);12 auto next = std::make_shared<Table>(*base); // the copy in copy-on-write13 next->apply(c);14 if (current.compare_exchange_weak(15 base, std::const_pointer_cast<const Table>(next),16 std::memory_order_release, std::memory_order_acquire))17 return;18 // base was refreshed by the failed CAS; loop and rebuild on the new version.19 // Under heavy write contention this loop is the failure mode, not the fix.20 }21}Key points
- Readers take one atomic load and hold a complete version for their whole unit of work. They never block and are never blocked.
- Writers clone, modify privately and publish with a single pointer store — the structure behaves as immutable even though it changes.
- The read path being lock-free says nothing about the write path: two unconditional stores lose an update. Use compare-and-swap or serialize writers.
- Cost is one full clone per write, which is why the pattern belongs to read-dominated state and nowhere else.
- Old versions live as long as readers hold them; long-running readers turn version retention into a memory leak.
The loop, answered
Every field is required, which is why no lesson here can recommend concurrency without naming the interleaving that breaks it, the complexity it adds, and the simpler thing to consider first.
- • Hold the structure behind a single atomic reference; treat every published version as immutable.
- • A reader performs one acquire load and uses that snapshot for the whole request.
- • A writer loads the current version as its base, clones it, and applies the change to the private clone.
- • The writer publishes with a release compare-and-swap against the base it read; if the pointer moved, it discards the clone and retries from the new base.
- • A version becomes unreachable when the pointer moves past it and the last reader drops it; reclamation is by refcount, epoch, or a garbage collector.
- • Reader crosses a swap: R loads ptr (v2); W publishes v3; R continues against v2 — R sees a slightly stale but entirely consistent table, which is the intended semantics.
- • Reader loads twice: R loads ptr (v2) for the plan; W publishes v3; R loads ptr (v3) for the execution — internally inconsistent request. Snapshot once.
- • Two writers, unconditional store: W1 and W2 both base on v2, both store; the loser's change vanishes silently. This is a lost update.
- • Two writers, CAS: W1 and W2 both base on v2; W1 CAS succeeds; W2 CAS fails, reloads vA, re-clones, re-applies, CAS succeeds — both changes survive, W2 paid two clones.
- • Long reader: R holds v2 for 4 minutes while W publishes 240 versions — every version from v2 onward is retained, and the heap grows by 240 clones.
- • Guarantees readers a complete, self-consistent version with no lock and no waiting, for as long as they hold the reference.
- • Guarantees readers never see a partially applied change, because changes are applied to a structure no reader can reach.
- • Does NOT guarantee readers see the latest version — a snapshot is stale the instant after it is taken, by design.
- • Does NOT guarantee write atomicity across multiple structures. Two independently copy-on-write structures swapped separately can be observed mid-way by a reader that reads both.
- • Does NOT guarantee writers do not lose updates. Only the compare-and-swap (or a writer mutex) provides that.
- • Does NOT bound memory. The number of live versions is the number of distinct versions still referenced, which is a property of your slowest reader.
- • Read path: none, beyond the shared cache line holding the pointer, which is read-mostly and therefore cheap.
- • Refcounted pointers reintroduce contention exactly where you removed it — every reader increments and decrements the same counter, and that line becomes hot at high read rates.
- • Write path: writers contend with each other through the CAS. At low write rates the loop almost never spins; at high write rates it degenerates into repeated wasted clones.
- • Allocator and memory bandwidth are the hidden contention points, because every write is a full-structure allocation and traversal.
- • Lost update between two writers using an unconditional store — silent, and invisible to any read-path test.
- • Unbounded version retention when a reader holds a snapshot far longer than the publication interval; presents as a heap leak with no leaked object.
- • Live-lock-ish write starvation: under sustained write contention a slow writer's CAS keeps failing while faster writers keep winning.
- • Unsafe publication if the store is not a release (or the load not an acquire): a reader can follow the new pointer to a not-yet-visible field.
- • Version skew inside one request when the pointer is loaded more than once.
- • ABA on a raw pointer scheme where a freed version's address is reused — the reason production implementations use refcounts, epochs or hazard pointers. See The ABA Problem: The Value Came Back.
- • Read-dominated shared state with a workable clone cost: routing tables, permission sets, subscription lists, compiled rules, in-memory indexes.
- • When readers must not block under any circumstances — a request path where a write lock would put a tail-latency spike on every reader.
- • When snapshot semantics are actually desirable: a long computation that should see one stable version rather than a shifting one.
- • When you want immutability's properties on a structure that genuinely does change, a few times a day.
- • Write-heavy state: every write is a full clone, so the cost is O(n) per write against O(1) for a mutex-guarded in-place update.
- • Very large structures where the clone does not fit twice in memory, or where the traversal blows the cache on every write.
- • Workloads that need read-your-own-writes — a reader with an older snapshot legitimately does not see the write it just made.
- • When any single reader can hold a snapshot for an unbounded time, because that turns version count into an unbounded quantity.
- • Ratio of reads to writes on the structure — the number that decides whether the pattern applies at all.
- • Live version count and the age of the oldest live snapshot; the second one is the leading indicator of the retention failure.
- • CAS retry rate on the write path. A retry rate above a few percent means writers are contending and the clone cost is being paid more than once per logical write.
- • Allocation bytes per write and p99 write latency, which together tell you whether the clone is affordable at the current structure size.
- • Reader-side p99 before and after: if it did not improve, the lock you removed was not the one that mattered.
- • You are now maintaining a versioning scheme with explicit lifetimes, plus a reclamation story for old versions.
- • The write path is a retry loop, which means it must be idempotent with respect to its own base — recomputing the change against a fresh base, not replaying a diff blindly.
- • Memory-ordering choices become load-bearing: the release/acquire pair is not decoration, and getting it wrong produces a bug that appears only on weakly ordered hardware.
- • Debugging requires knowing which version a given request saw, which means versions need ids and logs need to carry them.
- • A read-write lock: far simpler, no cloning, no versions, no reclamation — at the cost of readers blocking during writes and writers potentially starving. See Read/Write Locks, Honestly.
- • Full immutability with a scheduled rebuild, when writes can be batched into a periodic reload rather than applied individually. See Immutability as a Concurrency Strategy.
- • A plain mutex, when the structure is small enough that the critical section is a handful of nanoseconds.
- • Push the problem to a store that already solves it — a database with MVCC: Multi-Version Concurrency Control gives snapshot reads and conflict detection you do not have to write.
- • Per-shard structures, so that most writes touch a different shard and contention drops without any versioning at all.
What people believe, and what is true
Copy-on-write means the read path is lock-free, so the whole thing is lock-free.
Only reads are. Writers still need CAS-with-retry or a mutex among themselves, and the naive store loses updates in a way no read-path test detects.
It is the same thing the kernel does for fork.
It is the same idea at a different granularity and with a different trigger — the kernel copies a 4 KB page on a write fault detected by the MMU. Here you copy a structure at a branch you wrote. See Copy-on-Write in Operating Systems for the kernel mechanism.
Old versions get freed as soon as the pointer moves.
They get freed when the last reader drops them. One slow reader retains its version and every version is a full clone, which is how the pattern leaks.
Go deeper
Overview
Readers point at the current version and never wait. A writer copies it, changes the copy, and swaps the pointer. Old readers keep using the old version until they finish.
Practical
Use it for read-dominated structures with occasional whole-structure updates. Snapshot once per request. Serialize writers with a mutex if writes are rare — it is simpler than a CAS loop and costs nothing at 30 writes an hour.
Advanced
Replace whole-structure cloning with structural sharing when the structure is large, and treat version retention as a first-class budget: track live version count and oldest-snapshot age as metrics, not as an afterthought.
Internals
The publication needs a release store and an acquire load. Reclamation with raw pointers needs epochs or hazard pointers to answer "is any reader still inside this version"; refcounting answers it automatically but puts an atomic RMW on the hottest read path in the system.