Part 5 of 7 · 4 min read
Where the counters live
A fast shared store, two commands, the race condition and the fix.
Think of a notice board at the door of a club. Every door person must read and update the same board. If each had a private board, a guest could be admitted once at each door.
Counters need a home that is fast and shared. The book says a database is a poor choice, because disk access is slow. An in-memory store is better. It is fast and can expire entries on a timer. The book names Redis, which offers two commands that suit the job.
- INCR adds 1 to a counter.
- EXPIRE sets a timer after which the counter is deleted.
With these, a fixed window limiter is two lines of thought: increment the counter for user:7:minute:12:05, and set it to expire after 60 seconds.
The book's flow: the client sends a request to the rate limiter middleware. The middleware reads the counter from the store. If the limit is reached, the request is refused. If not, the request goes to the API servers and the counter is incremented and saved.
Two problems appear once many servers and many threads share the counters.
Race condition.
Race condition
A race condition is a bug where the result depends on the exact timing of two actions that overlap.
Example: two requests both read a counter, both add one, and both write it back, so one of the additions is lost.
The book gives the case. The counter is 3. Two requests read 3 at the same time. Each thinks the new value is 4 and writes 4. The correct value is 5.
A worked example with a limit. The limit is 4 per minute and the counter is 3.
- Request A reads 3. 3 + 1 = 4, which is within the limit.
- Request B reads 3 at the same moment. 3 + 1 = 4, also within the limit.
- Both are accepted, both write 4.
- Five requests have been counted as four. One request over the limit slipped through.
Locks would stop this, but the book warns that locks slow the system. It names two other fixes: a script that runs the read, the check and the write as one step inside the store (a Lua script in Redis), and the sorted set data structure. The general idea is that the check and the update must be one atomic step, one that nothing can interrupt.
Atomic operation
An atomic operation happens completely or not at all, with nothing able to cut in halfway.
Example: INCR reads, adds 1 and writes in one step. Two overlapping INCR calls always give 4 then 5, never 4 and 4.
A simple safe pattern for a fixed window: do the INCR first, look at the value that comes back, and refuse if it is above the limit. The read and the add are then one step.
Synchronisation. One limiter server cannot serve millions of users. With several limiter servers, each seeing a part of the traffic, a client's requests may reach different servers. If each keeps its own counts, none sees the whole. The book says to avoid sticky sessions for this (page 5), as they are neither scalable nor flexible, and to use a central store such as Redis that all limiter servers share.
A worked example of cost. Each check calls the shared store, 0.5 ms away on the inside network (made up). It adds 0.5 ms to every request. At 40,000 requests per second, that is 40,000 store operations per second, which one fast in-memory node can serve, but the store also needs a copy for safety. Rules are kept apart: the book keeps them in files on disk, and workers load them into a cache.
Failure. If the store is down, the limiter must decide.
- Fail open. Let everything through. The service is available, but unprotected.
- Fail closed. Refuse everything. The service is protected, but down.
The book asks for high fault tolerance: a problem in the limiter, such as the cache going offline, must not take down the whole system. This points to fail open for most APIs, and fail closed only where an overload would be dangerous, such as payments.
Read it as
Check and update must be one step. Otherwise two requests can both pass a limit that only one should.
Check yourself:
- Why can two requests both pass when the counter is one below the limit?
- What does a limiter do if the counter store fails, and what are the two choices?