If a store makes every operation atomic, why can two callers that read one entry, change it and write it back still lose a change?
answer
- atomic per operation, not per caller
- a read and a write are two
- the gap between them is unprotected
- another caller's write lands there
- last-writer-wins, and nothing is reported
basics
~20 sPer-operation atomicity covers one operation, not a caller's sequence. A read and a write are two operations, and other callers' operations run in the gap between them, so the later write lands whole and the earlier change is gone.
solid answer
~40 sThe store's free guarantee has a precise unit: **one operation**. Each of the four operations here - two reads and two writes - is applied as a whole, and no caller ever sees an entry halfway through one. But caller A's read and caller A's write are two separate operations, and between them the store is entitled to execute caller B's operations. Both callers read the same old value, both compute from it, both write, and the second write replaces the first change completely. That outcome has a name: `last-writer-wins`. Nothing reports it - both writes were accepted and both callers were told they succeeded. The gap is not a defect in the store; it is the exact edge of what per-operation atomicity promises.
go deeper
Recall the unit: one operation. A read and a write are two operations, so the value can change in between, and neither caller is told anything when one change replaces the other.
Explain where the gap comes from - the store sees two unrelated operations and may execute other callers' operations between them - and be able to walk a two-caller interleaving to its final stored value.
Show that you volunteer the boundary unprompted rather than being led to it, and that you can point at which workloads in a design depend on a value the caller just read. Note that the threading model does not change the exposure.
Frame it as a contract question: which invariants may rest on the store's free per-operation guarantee, which must be enforced somewhere that offers more, and how the system behaves when a silently overwritten change is the failure mode rather than an error.
## The guarantee you get for free An in-memory store of this class hands you one guarantee without being asked for anything: **a single operation is applied as a unit**. Whatever one operation does to the entry it touches, it does completely or not at all, and no other caller observes that entry halfway through it. You open nothing, declare nothing and hold nothing to get it. That is why engineers who have run one of these stores say "operations are atomic" almost as a reflex - and why so many of them then over-claim what it covers. The guarantee comes out of the execution model, and this class of store splits into two designs that reach it differently: - **One-operation-at-a-time execution (run-to-completion)** - the server starts an operation and finishes it before starting the next. No other operation executes in between, so nothing needs locking. Such stores commonly still use other threads for network handling or background housekeeping; what is serialized is the execution of the operations themselves. - **Per-entry locking** - several worker threads execute operations concurrently, and a thread holds a lock on the entry it is operating on (on some stores, on a stripe or bucket that the entry falls into) for the duration of that one operation. Both designs deliver the same per-operation promise to a caller. **Neither delivers anything wider**, and that is the whole of this question. ## Why your read and your write are not one thing A read-modify-write from application code is three steps in two places: the store performs the read, *your process* performs the modify, and the store performs the write. The store sees two unrelated operations arriving on a connection minutes or microseconds apart; it has no idea they belong together, because nothing in either one says so. So the moment your read operation completes: - under run-to-completion, the server is free to start whatever operation is next in line, including another caller's write to the entry you just read; - under per-entry locking, the lock your read was holding is released the instant that read finishes, and another thread may take it. Either way, the span between your read and your write is unprotected. The threading model changes *who else waits* while an operation runs; it does not change the fact that other callers' operations run between yours. ## The interleaving, step by step Take a quota counter standing at 10, and two service instances each adding one: | Order | Caller A | Caller B | Stored value | |---|---|---|---| | 1 | reads 10 | | 10 | | 2 | | reads 10 | 10 | | 3 | computes 11 in its own memory | | 10 | | 4 | | computes 11 in its own memory | 10 | | 5 | writes 11 | | 11 | | 6 | | writes 11 | 11 | Every one of those four store operations was atomic. The final value is 11, two increments were requested, and one of them is gone. ## What the caller is told Nothing. This is the part candidates most often get wrong, and it is worth stating flatly: 1. Caller A's write succeeded. It was a valid write of a valid value and the store applied it. 2. Caller B's write also succeeded, for exactly the same reason. 3. No error, no conflict, no warning, no counter of collisions is raised on the path either caller took. This is `last-writer-wins`: the later write lands whole, the earlier change disappears, and nothing reports it. The loss is only visible later, by comparing what the system believed it had written with what the entry actually holds - which in practice means it is visible as a wrong number, a dropped list member, or a field that reverted, long after the two callers have gone. ## Where the boundary actually bites Any workload where a caller's decision depends on what it just read: - a quota or usage counter incremented from application code; - a structured value fetched as bytes, deserialized, edited in one field and written back whole - the only shape available on stores whose server does not interpret values; - a membership set read, added to, and stored again; - a flag read as "free", then claimed by writing your own marker into it. In each case the entry is fine and each operation is fine; the *pair* is the exposure. ## What this leaf is not Stating the boundary is not the same as closing it. Closing it needs either a single operation that does the whole change, or something that detects that the entry moved underneath you, or a claim held across both steps - each with its own cost under contention, and each a separate subject. The point to carry away here is narrower and more durable: **per-operation atomicity does not compose**, and any design that assumes it does is relying on a guarantee no store in this class makes. ## Each of the four store operations was applied as a whole. The span from t1 to t5 was never a unit, and neither caller received any signal that a change had been overwritten ``` time caller A caller B stored value ---- --------------------------- --------------------------- ------------ t1 read entry -> 10 10 t2 read entry -> 10 10 t3 add 1 locally (11) 10 t4 add 1 locally (11) 10 t5 write entry = 11 11 t6 write entry = 11 11 four operations, all atomic, both writes reported success, final value 11 ```
- Is the gap wider on a store whose worker threads lock each entry than on one that runs operations one at a time?No - it is the same gap. It is created by the caller issuing two operations, not by the server's threading. What the threading model changes is who else waits while an operation runs: everyone, under run-to-completion; the callers touching that entry or its lock stripe, under per-entry locking.
- How does a caller detect that its change was overwritten?On the unprotected path, it does not. Both writes were accepted, so there is nothing to catch. The loss surfaces later as a wrong value - a count that drifts below what was counted, a set member that vanished - and attributing it back to a specific interleaving usually means reasoning about the design rather than reading a log.
- If each caller sent one operation that made the change on the server instead of reading and writing, would the gap still be there?Then each caller issues one operation, so the span this question is about does not exist. Whether that is available at all varies across this class: some stores understand their values and can change part of one, while others store opaque bytes, and on those a read-modify-write is the only shape there is. Which remedy to reach for, and what it costs when the entry is hot, is a separate subject.
Two clerks each copy the shop's stock total off the same whiteboard onto their own pad, subtract one, and walk back to write their number up. Each trip to the board is instant and orderly - nobody ever sees a half-written number - but the board ends up showing one sale, not two, and neither clerk is told a thing.
saying these in an interview costs you the question
- Says a read-then-write pair is safe because operations are atomic.
- Believes the store runs one caller's whole sequence before another caller's.
- Expects the store to reject or report the stale second write.
- Argues the gap cannot exist when the server executes one operation at a time.
- Calls the lost change a bug in the store rather than in the caller's design.