You are told a data structure is read-mostly and should therefore be guarded by a shared/exclusive lock. How would you decide whether that is actually the right mechanism, and what alternatives would you weigh?
answer
- ratio + section length + core count
- reader counter is one hot cache line
- mutex is the baseline to beat
- snapshot swap: free reads, stale view, copy cost
- shorten the section before swapping the primitive
basics
~20 sMeasure first: read/write ratio, critical-section length, and core count. Mode separation only pays if reads dominate and sections are long enough to amortise the reader bookkeeping. Otherwise weigh a plain mutex, an immutable snapshot swapped atomically, sharded state, per-thread state with aggregation, or optimistic validated reads.
solid answer
~60 s'Read-mostly' alone does not justify mode separation. Three numbers decide it: the **read fraction**, the **critical-section length**, and the **concurrency level**. Shared mode buys reader parallelism but costs an extra atomic update to a shared reader counter on entry and exit; with nanosecond-scale reads on many cores, that one cache line becomes the bottleneck and a plain mutex often wins. So I would instrument acquisitions per second, hold-time and wait-time distributions per mode, and the actual ratio, then choose from a spectrum: - **Plain mutex** — short sections, moderate concurrency, simplest to reason about. - **Immutable snapshot** — writer builds a new version off-lock and swaps a reference; readers take nothing. Best when the data is small or rebuildable and readers tolerate slight staleness. - **Sharding** — split the structure by key so both the data and its locks spread across cores. - **Per-thread state with aggregation** — writers touch only their own slice; readers merge. Removes read-path contention entirely at the cost of approximate reads. - **Optimistic validated reads** — readers perform no writes, so they scale, but must be speculative-safe. - **Shared/exclusive lock** — genuinely long read sections over data too big to copy.
go deeper
Say you would check how often writes actually happen and how long a read holds the lock, and that a plain mutex may be sufficient.
Add the cost of shared acquisition and name at least one alternative such as an immutable snapshot or sharding.
Drive from measurements — ratio, hold time, core count — explain the reader-counter cache-line problem, and match alternatives to staleness tolerance and data shape.
Treat it as a data-ownership decision rather than a primitive selection: prefer designs where readers synchronise on nothing, quantify the staleness the product can absorb, and require a before/after measurement for any added invariant.
## Interrogate the claim before choosing the tool 'Read-mostly' is a description of a ratio, and a ratio is only one of the inputs. The full set: 1. **Read fraction.** Is it 70% or 99.9%? Mode separation only helps in proportion to how much time is spent in shared mode. Below roughly 90% reads, the benefit is usually swamped by the extra cost. 2. **Critical-section length.** This dominates. A shared acquire and release are two atomic read-modify-writes on the lock's reader state; if the read body itself is a few nanoseconds, you have doubled or tripled the cost to gain parallelism you did not need. If the read body is microseconds of traversal, the overhead is noise and the parallelism is real. 3. **Concurrency level.** On four cores, contention on the reader counter is mild. On sixty-four, every reader writing the same cache line means that line migrates between caches constantly, and read throughput can *fall* as you add cores — the pathology that makes naive shared/exclusive locks scale worse than a mutex. 4. **Staleness tolerance.** If readers can accept data that is a few milliseconds old, the cheapest mechanisms open up. If every read must see the latest committed write, they do not. 5. **Data size and shape.** Small and copyable enables snapshots. Large, pointer-rich, or incrementally mutated resists them. 6. **Write urgency.** If writes are refreshes that must land promptly, reader-preference starvation is a real risk and argues against a naive shared/exclusive lock. ## The spectrum of mechanisms **Plain mutex.** Cheapest per acquisition, one mental model, no mode policy, no starvation question, no upgrade hazard. For short sections it is frequently the fastest option in practice, and it should be the baseline any alternative must beat in a measurement. **Immutable snapshot / copy-on-write.** The writer builds a complete new version outside any lock and publishes it with a single atomic reference swap; readers dereference the current version and use it with no synchronisation on the read path at all. Read cost drops to essentially zero and scales perfectly. Costs: each write copies the whole structure (fine for occasional refreshes, terrible for a hot write path), and a reader holding an old version sees a slightly stale view — usually acceptable for configuration, routing tables, feature flags, and permission caches, which is exactly where 'read-mostly' claims usually originate. **Sharding.** Partition by key so that both data and locks are split N ways. Reads and writes to different shards proceed independently and the cache lines spread out. Costs: cross-shard operations need ordered multi-lock acquisition, and global operations must touch every shard or accept approximation. **Per-thread or per-core state with aggregation.** Each writer mutates only its own slice, so the write path has no contention at all; a reader sums or merges the slices. This is the standard shape for metrics and counters. Costs: reads are proportional to the thread count and see a slightly inconsistent composite, and memory scales with thread count. **Optimistic validated reads.** Readers snapshot a version counter, read, and re-check it. Readers issue no writes, so they scale and never block writers. Costs: the read body must be speculative-safe (no side effects, no acting on unvalidated values), and readers retry under write bursts, so a bounded fallback is needed. **Shared/exclusive lock.** Reach for it when read sections are genuinely long, the data is too large or too incrementally-mutated to snapshot, and readers must see the latest state. Then also choose the admission policy deliberately — reader-preference risks starving your writer, writer-preference makes recursive read acquisition unsafe — and monitor the exclusive-acquire tail. ## How I would run the decision Start from the simplest thing that is correct (a mutex), and instrument: acquisitions per second by mode, hold-time and wait-time histograms, and CPU time attributable to synchronisation. If the lock is not in the top contributors, stop — the choice does not matter and complexity is a real cost. If it is, look at *why*: if hold time is the problem, shorten the section or move computation and I/O out of it before changing the primitive at all. If the section is already minimal and readers still queue, then pick from the spectrum by staleness tolerance and data shape, and re-measure. Any replacement must be justified by a before/after number, because every option above except the mutex adds an invariant that future changes can silently violate.
- When is an immutable snapshot with an atomic reference swap clearly better than a shared/exclusive lock?When the data is small enough or rebuildable enough that copying it per write is cheap, writes are infrequent, and readers can tolerate briefly stale data — configuration, routing tables, feature flags, permission sets. Readers then take no lock at all and scale perfectly across cores, and there is no reader-counter cache line to contend on. It is a poor fit when writes are frequent or the structure is large, because every write pays a full copy.
- Read throughput fell when you moved from four cores to thirty-two, even though the workload is 99% reads under a shared/exclusive lock. Why?Every shared acquisition and release writes to the lock's reader-count state, so that single cache line is being modified by all thirty-two cores and migrates between their caches continuously. The readers never conflict on the data, only on the lock's own bookkeeping. Remedies are to remove reader writes entirely with a snapshot or an optimistic validated read, or to split the counter per shard or per core.
saying these in an interview costs you the question
- Chooses mode separation from the phrase 'read-heavy' with no measurement
- Never considers that a plain mutex may be faster
- Ignores that shared acquisition itself writes to a contended cache line
- Adopts a snapshot design without checking whether readers tolerate staleness
- Changes the primitive before shortening the critical section or removing I/O from it