Why is a store's unit of atomicity also the unit other callers wait on, and which callers wait under each execution model?
answer
- exclusion is how atomicity is paid for
- duration of the unit equals the wait
- everyone, or just that entry
- head-of-line blocking is the model, not a fault
- wider unit means longer exclusion
basics
~20 sAtomicity is bought by excluding others for the operation's duration, so that duration is their wait. Under run-to-completion every caller waits, whatever entry they wanted. Under per-entry locking only callers of that entry or its lock stripe wait.
solid answer
~50 sBoth execution models buy atomicity the same way underneath: for as long as one operation runs, somebody else is excluded. Under **one-operation-at-a-time execution**, the exclusion is the whole server - a single operation whose work is proportional to how much data it touches makes every caller wait, including those wanting unrelated entries. That is `head-of-line blocking`, and it is a property of the model rather than a fault. Under **per-entry locking**, the exclusion is the entry (or the stripe it hashes into), so the waiting is localised - but a hot entry then becomes a serialization point that more worker threads do not relieve. The design consequence is the same in both: **the unit of atomicity is the unit of waiting**, so you cannot widen atomicity for free. A bigger unit is a longer exclusion for whoever is behind it.
go deeper
Recall that while one operation is being applied, someone else is being held back - that exclusion is how the store makes the operation atomic in the first place.
Explain who is excluded under each model: every caller where operations run one at a time, callers of that entry or its lock stripe where worker threads lock entries.
Reason about duration distributions rather than averages, and show why a hot entry serializes under both models while only the bystanders differ. Say what bounds an operation's duration.
Frame it as a contract with the rest of the system: what maximum operation duration the tier commits to, what a request for a wider atomic unit costs every other caller, and what operators are shown when contention degrades latency instead of producing errors.
## The guarantee is not free, it is prepaid Per-operation atomicity feels free to a caller because nothing has to be declared to obtain it. Underneath, every store in this class pays for it the same way: **for the duration of one operation, somebody else is not allowed to proceed.** That single sentence explains almost everything about how these stores behave under load, and it is the reason the two execution models feel so different in production despite promising the same thing. ## Under one-operation-at-a-time execution: everybody is behind you When the server runs one operation to completion before starting the next, the set of callers excluded during an operation is *all of them*. The consequences: - An operation whose work is proportional to the amount of data it touches holds the stream for that whole time. Nothing about it is special-cased; it is simply the operation that is currently running. - Every other caller waits, **whatever entry they wanted**. A caller reading a tiny unrelated entry waits exactly as long as a caller wanting the entry being worked on. This is `head-of-line blocking`. - The waiting is invisible in the operation's own cost. The operation that was slow is not the operation that felt slow to most callers; they merely queued. What follows for design is that the *distribution* of operation durations matters more than the average. A stream of uniformly short operations makes this model extremely predictable. A single long one is felt by everyone. ## Under per-entry locking: only the contenders are behind you When worker threads execute concurrently and each holds the entry (or the stripe it falls into) for one operation's duration, the excluded set is much smaller: the callers that want that entry, plus anyone unlucky enough to want a different entry sharing the same lock stripe. But localised is not free either: - One entry receiving most of the traffic becomes a **serialization point**. Operations on it queue on its lock no matter how many worker threads exist, because they cannot overlap and still be atomic. - Threads blocked on that lock are not doing other work; a workload concentrated enough on one entry can occupy the pool and starve unrelated traffic indirectly, which looks server-wide even though the mechanism is not. - A coarse lock granularity widens the excluded set to entries that have nothing to do with each other. ## The asymmetry in one table | | One-operation-at-a-time | Per-entry locking | |---|---|---| | Who is excluded during an operation | Every caller | Callers wanting that entry or its stripe | | What a long operation costs | Server-wide waiting | Waiting on that entry, plus threads tied up | | Does adding workers help a hot entry | No such dial exists | No - they queue on the same lock | | Predictability lever | Keep every operation short | Keep hot entries' operations short, spread the rest | ## Why you cannot buy wider atomicity for free The tempting move, once you see that per-operation atomicity does not compose, is to ask for a bigger unit - make the operation do more, so more of your logic is inside the guarantee. That trade is real and sometimes right, but it is a trade, not a free upgrade, and the price is exactly the mechanism above: - A unit that runs twice as long excludes others for twice as long, and under run-to-completion "others" means the entire server. - A unit covering more entries holds more of the keyspace unavailable under per-entry locking, and increases the chance that some caller is blocked by it. - A unit whose duration depends on data the caller does not control has no bound at all, which is the same as saying the waiting has no bound. So the design rule falls out of the mechanism rather than from taste: **keep the unit small, keep its duration bounded by something you control, and get any wider guarantee you need by a route that does not lengthen the exclusion.** ## What this does not cover This is a property of the execution model, not a triage procedure. Finding out which operation in a live system is the long one, what a single oversized entry costs, and what an operator should watch are separate subjects with their own tooling. The value of the model here is predictive: before anything is slow, it tells you which callers *would* be affected on the store you are on, and it tells you that a request for more atomicity is always a request for someone else's patience.
- Why is head-of-line blocking described as a property of the model rather than a defect?Because it is the same mechanism that delivers the free guarantee. Where the server runs one operation to completion, nothing else executing is precisely what makes the operation atomic - so any operation that takes a long time necessarily makes others wait. Removing the waiting would mean removing the way atomicity is obtained.
- If contention lands on one entry, does the execution model still matter?Less than people expect. Callers wanting that entry serialize on it either way; only the bystanders differ - everyone waits under one-operation-at-a-time execution, while unrelated entries stay available under per-entry locking. Once traffic concentrates on one entry, the remaining lever in both models is how long each operation on it takes.
- Does making one operation do more work give a caller more atomicity at no cost?It gives a wider unit and a proportionally longer exclusion. Under run-to-completion the whole server waits it out; under per-entry locking more of the keyspace is held. It can be the right trade, but it is paid for in other callers' latency, and an operation whose duration depends on uncontrolled data leaves that cost unbounded.
saying these in an interview costs you the question
- Treats head-of-line blocking as a bug rather than the model's cost.
- Assumes only callers wanting the same entry ever wait.
- Expects more worker threads to make a hot entry faster.
- Believes a longer operation gives wider atomicity at no cost.
- Judges the model by average operation duration rather than the long tail.