CSE Roadmap

Core tier · about 4 hours · 8 parts

Part 4 of 8 · 2 min read

The bottleneck

Many servers, one count.

A single server can count in a variable. The trouble starts with many servers and many threads. The Xu book names two challenges.

Race condition. The naive steps are: read the counter, check if one more would break the limit, then write the new value. Suppose the counter is 3 and two requests arrive together. Both read 3. Both decide it is fine. Both write 4. The true count should be 5, so a request was lost from the count and the limit leaks. This is the check-then-act race of Level 5 in the low-level track.

Locks fix it but slow everything, since every request waits in line. The book offers two better ways:

  • A script that runs inside the store. The store runs one script at a time without interruption, so read, check and write happen as one step. The book mentions Lua scripts for Redis.
  • A sorted set in the store, used for the sliding-log method. Each request adds a timestamp, old ones are removed, and the size is checked, all as store commands that can be combined atomically.

In pseudocode, the atomic step for a fixed-window counter looks like this:

ATOMIC at the store, for key K with limit L and window W:
    n = increment(K)
    if n == 1: set_expiry(K, W)       # first request in the window starts the clock
    return n <= L                     # allowed or refused

Because the whole block runs without anyone cutting in, two servers asking at once get n = 4 and n = 5, never both 4.

Synchronisation. The web tier is stateless, so one client's requests may reach any of many limiter servers. If each limiter kept its own counters, limiter 1 would know nothing of what limiter 2 saw. The client could send 100 requests through each of 10 limiters and get 1,000 through.

One fix is sticky sessions, which route a client to one limiter. The book calls this a poor choice because it is neither scalable nor flexible. The better fix is a central store that all limiters share. Each check is a call to the store.

A worked example (made up). Limit: 5 requests per minute. Client A sends 3 requests to limiter 1 and 3 to limiter 2 within the same minute. With private counters, each limiter sees 3, so all 6 pass and the limit leaks by one. With a shared store, the sixth request sees a count of 6 and is refused.

To handle 500,000 operations per second, the store is sharded (Level 4) by client key: a hash of the key picks one of 8 nodes. All requests for one client go to one node, so its counter is never split. Each node also has a replica that takes over if it fails.

Check yourself: 1. Describe the race with a counter at 3 and two requests. 2. Why are sticky sessions a poor fix for synchronisation? 3. Why shard by client key and not by request?