Explain the copy-on-write technique for sharing a data structure between many concurrent readers and an occasional writer: what invariant lets readers run without locking, and what is its cost model?

## The construction Copy-on-write splits a mutable shared structure into two things: an immutable snapshot, and one mutable reference that says which snapshot is current. reader: s = load(current) # one atomic read use(s) ... # s never changes; no lock writer: under writer_lock: old = load(current) new = copy(old); mutate(new) store(current, new) # atomic publish Everything follows from the invariant that whatever current has ever pointed at is never modified again. ## Why readers need nothing A reader performs exactly one synchronizing operation: reading the reference. After that it holds a private handle to a structure that no one will touch, so any number of reads across any interleaving return mutually consistent data. This is why copy-on-write collections are the standard answer for listener/observer lists: iteration cannot observe a concurrent modification, since the version being iterated is frozen. It also gives a genuinely useful property that locking does not: a reader can hold a consistent multi-field snapshot for as long as it likes without blocking writers. Under a lock, a long read blocks updates; here it merely keeps an old version alive. ## What readers give up Staleness. A reader that took the reference before a publish will not see that update, and two readers may act on different versions simultaneously. Copy-on-write therefore provides *snapshot consistency*, not linearizable freshness. It suits data where being a few milliseconds behind is fine — configuration, routing, permissions caches — and is wrong for anything where a decision must reflect the latest write, such as a balance check. A subtle version of the same trap: a read-modify-write built on top (read the snapshot, compute, publish a new one) is not atomic unless the publish is guarded, which is the writer problem below. ## The writer side is the part people forget Copy-on-write makes readers lock-free; it says nothing about writers. Two writers that each copy the same old version and then publish will produce lost updates — the second publish overwrites the first entirely, which is worse than a normal lost update because it discards a whole structure. Fix it either with a lock held for the copy-mutate-publish sequence, or with a compare-and-swap on the reference plus retry from the freshly loaded version. Write throughput is the hard limit of the technique. Each write is O(n) copying plus allocation; with a burst of writes you get quadratic total work and a memory spike, and under a compare-and-swap loop you also get retries that throw away completed copies. A structure with frequent writes needs a different design (fine-grained locks, a concurrent structure, or partitioned ownership). ## Memory and reclamation During a write, both versions exist, so peak memory is roughly double the structure. Old versions must stay alive while any reader still holds them; in a garbage-collected runtime this happens automatically — the old version becomes unreachable when the last reader drops it. Without automatic reclamation you need a grace-period scheme that defers freeing until all pre-existing readers have finished, which is the essence of read-copy-update as used in operating-system kernels. A long-running reader that keeps a snapshot alive pins that memory, which is a real leak vector when snapshots are large and readers are long-lived. ## Reducing the copy cost Persistent (structurally shared) data structures make the copy proportional to the changed path rather than the whole structure — for a tree, O(log n) new nodes with the rest shared with the previous version. Sharing is only safe because old versions are immutable, so persistence and copy-on-write are natural partners. Batching helps too: apply many pending changes to one copy rather than copying per change. ## When to choose it Use it when reads vastly outnumber writes, the structure is small to moderate, and stale-by-a-moment is acceptable. Avoid it for write-heavy workloads, very large structures, or anywhere a reader must observe the newest value. State the read/write ratio when you propose it — that ratio is the whole argument.