The Update That Vanished
Adding a counter looks like one action and is three. Two workers doing it at the same time can both read the same value, and one of the two additions disappears with nothing broken.
Here is the shortest possible version of the whole subject. A page view counter
is stored somewhere. Two requests arrive at the same instant. Each one adds one.
Afterwards the counter has gone up by one.
Nothing crashed. No error was logged. No component was unavailable. The code that
did it is three lines long and obviously correct when you read it.
One operation, three steps
Adding one to a stored number is never one action. It is fetch the current
value, compute a new value, store the new value. Those are three separate things
with gaps between them, and the worker can be interrupted in either gap.
| step | worker one's held value | worker two's held value | the stored counter | increments requested so far | what happened |
|---|---|---|---|---|---|
| 1 | 0 | 0 | 41 | 0 | Starting state. Nobody has read anything yet. |
| 2 | 41 | 0 | 41 | 1 | Worker one reads. It now holds 41, and the stored value is still 41. |
| 3 | 41 | 41 | 41 | 2 | Worker two reads, in the gap. It holds 41 as well, which is true at this instant and will not be true for long. |
| 4 | 42 | 41 | 42 | 2 | Worker one writes its result. The stored counter is correct right now. |
| 5 | 42 | 42 | 42 | 2 | Worker two writes its result, computed from a value that is now stale. Two requests, one increment. |
Why you will not find it in testing
The window between the read and the write is small. For an in-memory counter it
may be a few tens of nanoseconds; for a counter in a database behind a network
call it may be a few milliseconds. Two workers have to arrive inside the same
window for anything to go wrong.
- the expected number of colliding pairs in the period
- how many times the operation runs in the period
- the width of the dangerous window, from the read to the write
- the length of the period the operations are spread over
- the number of pairs of operations that could possibly collide
- the chance that any one pair lands close enough together
A test suite runs the operation a few hundred times, usually in sequence, and
passes. The system then runs it ten million times a day with real concurrency,
and the counter drifts by a few tenths of a percent a week. By the time anybody
investigates, the evidence is a number that is slightly wrong and no log line
anywhere that says why.
The same shape, wearing different clothes
Counters are the teaching example because they are easy to draw. The pattern is
much broader, and it covers anything that checks a condition and then acts on
what it saw.
| how often it appears, on | how bad the failure is, | how hard it is to notice | how easily the database | |
|---|---|---|---|---|
| add one to a counter | 4 | 2 | 3 | 4 |
| create the record if it | 3 | 4 | 4 | 3 |
| spend from a balance if | 3 | 3 | 2 | 4 |
| claim the next job from | 2 | 4 | 4 | 2 |
In each of these, two workers look at the world, both conclude that an action is
safe, and both act. The check was true when it was made. It stopped being true
before the action, and nothing told anybody.
The machine has its own ideas
One more complication, because it surprises people who have understood
everything above. Even without any interleaving of your steps, a worker can read
a value that another worker has already changed.
Each processor keeps its own copy of recently used memory. A write made on one
processor becomes visible to another only when the machine arranges for it to be,
and both the compiler and the processor are permitted to reorder operations that
appear independent. Two assignments made in one order can become visible to
another worker in the opposite order.
This is why every serious language now publishes a memory model, which is a
precise statement of when one worker's write is guaranteed to be seen by another.
The practical consequence is simple enough to remember: unless you have used
something the language promises will synchronise, you have no promise at all
about what another worker can see.
What to hold on to
An operation that reads and then writes has a gap in it, and a second worker
inside that gap makes the result wrong without breaking anything. The failure is
rare in proportion to how narrow the gap is, which means it survives testing and
arrives with traffic. The same shape appears wherever a check is followed by an
action. And separately from all of that, a worker is not guaranteed to see
another worker's writes at all unless something was done to make it so.
Recap
- Almost every operation that looks atomic is really a read, then a change, then a write, and the gap between the read and the write is the window in which another worker can ruin the result.
- These failures are rare by construction, because the window is microseconds wide, which means they survive testing, appear under load, and cannot be reproduced on demand.
- The pattern is not limited to counters. Anything that checks a condition and then acts on it has the same gap, which is where duplicate records and negative balances come from.
This is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents