02. Rate Limiter — Low-Level Design¶

~20 min read · Part 3 of 4 (Overview → HLD → LLD → Q&A)

The HLD named the boxes. This file opens the three that carry the design's weight — the algorithm (token bucket versus sliding window), the distributed counter in Redis, and the local-versus-global enforcement split — and pins down the data, the math, and the concurrency corners where a rate limiter actually breaks.

Data models¶

The authoritative state is per key per policy, and it is short-lived by construction. Two algorithms want two shapes; this design ships the sliding-window-counter as default and the token bucket for burst-shaped limits, so both are shown.

Sliding-window-counter (default). Two integer counts and the window boundary, stored under one Redis key per {api_key, route} descriptor:

KEY:  rl:{api_key}:{route}          # hashes to one shard; {api_key} in braces = hash tag
VALUE (hash):
  cur_window   : 1751540400         # unix second of the current 1 s window
  cur_count    : 37                 # requests counted so far in the current window
  prev_count   : 82                 # requests counted in the immediately previous window
TTL: 2 s                            # two windows; expires itself, no sweeper needed

Three deliberate choices. The hash tag {api_key} forces every descriptor for a key onto the same shard, so a key's counters are co-located and one Lua script can touch them atomically. Only two counts are kept — current and previous — because the sliding-window-counter approximates the true sliding window from those two, which is the whole memory saving over a log. And the TTL is two windows, so an idle key's state evaporates on its own; there is no background reaper on the hot path.

Token bucket (for burst-shaped limits). Two values — tokens available and the last refill time:

KEY:  tb:{api_key}:{route}
VALUE (hash):
  tokens       : 42.5               # fractional tokens currently in the bucket
  last_refill  : 1751540400.812     # unix time (ms) of the last refill computation
TTL: ceil(capacity / rate) + 1 s    # long enough that a full bucket never expires mid-idle

Tokens are stored fractional so refill is exact between requests rather than rounding down and slowly leaking capacity. last_refill is stored so refill is computed lazily at read time — no timer ticks per key, which at 1M keys would be a million timers.

Policy (read constantly, written rarely, lives in the config store not Redis):

policy(api_key, route) -> {
  limit: 100, window_s: 1, burst: 50,
  algorithm: "sliding_window" | "token_bucket",
  on_error: "fail_open" | "fail_closed"
}

Component internals¶

Component 1 — The enforcement decision (gateway side)¶

Responsibility: produce an allow/deny in under a millisecond, using the local layer first and the shared counter only when needed, and degrade deliberately when the shared counter is unreachable.

class Limiter:
    def check(api_key, route) -> Decision(allow: bool, remaining: int, retry_after: float)
    def _local_precheck(key) -> LOCAL_DENY | UNSURE     # in-memory token bucket
    def _shard_check(key, policy) -> Decision            # one atomic Redis call
    def _fallback(key, policy) -> Decision               # local bucket as ceiling

def check(self, api_key, route):
    policy = self.policy_cache.get(api_key, route)
    if self._local_precheck((api_key, route)) is LOCAL_DENY:
        return Decision(allow=False, remaining=0, retry_after=policy.reset)
    try:
        return self._shard_check((api_key, route), policy)   # authoritative
    except ShardUnavailable:
        if policy.on_error == "fail_open":
            return self._fallback((api_key, route), policy)  # local ceiling, ~share
        return Decision(allow=False, remaining=0, retry_after=1.0)  # fail_closed

The order matters: the local pre-check runs first so a key already known to be over-limit is denied without a round-trip, and the shard check is authoritative for everything else. _fallback is the fail-open branch — it enforces the per-server share locally rather than letting everything through.

Component 2 — The distributed counter (Redis, atomic)¶

Responsibility: read the counters, compute the rate, and increment-or-reject in a single atomic hop, so 50 gateways racing on the same key can never interleave a lost update.

The read-compute-write must be atomic. Doing it as three separate commands (GET, compute in the gateway, SET) opens a lost-update race: two gateways read cur_count = 99, both decide "under 100, allow," both write 100, and two requests passed on the hundredth slot. A Lua script runs on the Redis node, so the whole decision is one indivisible operation on the shard that owns the key:

-- KEYS[1] = rl:{api_key}:{route}   ARGV = now, window_s, limit
local now      = tonumber(ARGV[1])
local window   = tonumber(ARGV[2])
local limit    = tonumber(ARGV[3])
local cur_win  = math.floor(now / window)
local h        = redis.call('HMGET', KEYS[1], 'cur_window', 'cur_count', 'prev_count')

local stored_win = tonumber(h[1]) or cur_win
local cur_count  = tonumber(h[2]) or 0
local prev_count = tonumber(h[3]) or 0

if stored_win ~= cur_win then                 -- window rolled over
  if stored_win == cur_win - 1 then
    prev_count = cur_count                     -- last window becomes "previous"
  else
    prev_count = 0                             -- gap: old data is irrelevant
  end
  cur_count = 0
end

local elapsed = (now % window) / window        -- fraction into current window [0,1)
local rate    = prev_count * (1 - elapsed) + cur_count

if rate >= limit then
  return {0, 0}                                 -- deny; do not increment
end
cur_count = cur_count + 1
redis.call('HMSET', KEYS[1], 'cur_window', cur_win,
           'cur_count', cur_count, 'prev_count', prev_count)
redis.call('EXPIRE', KEYS[1], window * 2)
return {1, limit - math.ceil(rate) - 1}         -- allow + remaining

Computing now inside the script (or passing the store's clock) means all 50 gateways share one reference clock for the boundary, sidestepping their individual skew. The EXPIRE rides in the same script, so there is no window where a counter exists without a TTL — a classic bug when INCR and EXPIRE are separate commands and a crash between them leaks the key forever.

Component 3 — The local token bucket (fast-path and fallback)¶

Responsibility: decide without the network when it safely can, and become the enforcement ceiling when the shard is gone.

class LocalBucket:               # per (key, route), in gateway memory
    tokens: float
    last_refill: float
    capacity: float              # = per-server share, e.g. limit / fleet_size
    rate: float                  # = limit / fleet_size per second

    def try_consume(now) -> bool:
        self.tokens = min(self.capacity,
                          self.tokens + (now - self.last_refill) * self.rate)
        self.last_refill = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

In fast-path mode it is advisory: a key that keeps failing try_consume is flagged LOCAL_DENY so its flood stops hitting the shard. In fallback mode it is the limit: capacity and rate are set to the per-server share (limit / 50), so 50 gateways each enforcing 2/s approximate the global 100/s without any coordination.

Core algorithm — sliding-window-counter, walked with the scenario¶

Take the threaded scenario: 100 requests/second for one API key, checked on the shard that owns it. Windows are 1 second wide. Walk a request that arrives 400 ms into a window.

The previous 1 s window [t, t+1) counted prev_count = 82 requests. The current window [t+1, t+2) has counted cur_count = 30 so far. The clock is at t+1.400, so elapsed = 0.40 — the request is 40% of the way through the current window.
Estimate the rate over the trailing 1 s as a weighted blend: the current window contributes all its count, and the previous window contributes the fraction that still overlaps the trailing second. rate = prev_count × (1 − elapsed) + cur_count = 82 × 0.60 + 30 = 49.2 + 30 = 79.2.
79.2 < 100, so allow, and cur_count becomes 31. remaining ≈ 100 − 80 = 20.
Now push it. Suppose bursts keep arriving and 30 ms later cur_count has climbed to 51 while elapsed is 0.43: rate = 82 × 0.57 + 51 = 46.7 + 51 = 97.7, still under — allow. A few more and rate = 82 × 0.55 + 55 = 45.1 + 55 = 100.1 ≥ 100 — deny, with retry_after set to the time until the previous window's weight decays enough to free a slot, roughly (rate − limit + 1) / prev_count of a second.
Contrast the fixed window it replaces. A fixed-window counter would have read cur_count = 55 < 100 and allowed, blind to the 82 that arrived in the last 600 ms. That is the boundary burst: 82 then 55 is 137 requests inside one trailing second, all "legal" to a fixed window. The sliding-window-counter's blend catches it. The approximation's only error is assuming the previous window's 82 were spread evenly; in practice that error is a fraction of a percent, which is why it beats the exact-but-800 MB log.

Now connect it to the fleet. All 50 gateways route this key to the same shard, so cur_count and prev_count are the one shared truth — gateway 7 incrementing to 80 is immediately visible to gateway 34's next check. That co-location is why the count adds up to 100 across the fleet instead of 100-per-server. The local buckets only ever subtract load from this shard by denying obvious over-limit traffic early; they never fork the authoritative count.

Sequence diagram — two gateways racing on the 100th request¶

GW-7          GW-34         Shard(rl:{key})              Backend
 │  req A       │                 │                         │
 ├──────────────┼── EVAL Lua ────▶│  cur_count=99, rate=99  │
 │              │  req B          │  99<100 → ++ → 100       │
 │              ├── EVAL Lua ────▶│  (queued behind A;       │
 │◀─ allow(rem0)┼─────────────────┤   Lua is atomic)         │
 ├──────────────┼─────────────────┼── forward A ───────────▶│
 │              │                 │  now cur_count=100       │
 │              │◀─ deny, retry ──┤  rate=100 ≥ 100 → deny   │
 │              ├─ 429 + Retry-After (B never reaches backend)│

Two gateways submit the 99th-slot and 100th-slot requests at the same instant. Because each EVAL is atomic on the shard, they cannot interleave: A runs fully (reads 99, allows, writes 100), then B runs (reads 100, denies). Exactly one request takes the last slot; the race that a GET-then-SET would lose is resolved by the store.

Concurrency and edge cases¶

Lost update on the boundary slot: two gateways both reading cur_count = 99 and both allowing is the core race. Solved by making read-compute-write one atomic Lua EVAL on the shard, so the second caller sees the first's write. Never split it into GET + client-side compare + SET.
INCR without EXPIRE: if the counter is created by one command and the TTL set by another, a crash in between leaves a key that never expires and silently locks a customer out after their window should have reset. The Lua script sets the value and the EXPIRE in the same atomic block, closing the gap.
Clock skew across 50 gateways: if each gateway used its own clock to pick the window, drifting clocks would double- or under-count at boundaries. The window arithmetic runs inside the shard's Lua using one clock, so all gateways agree on which window a request falls in.
Idempotency and retries: a client retry after a timeout is a new request and legitimately consumes a token — the limiter counts arrivals, not logical operations, so it does not (and should not) dedupe retries. A client that treats a 429 as a reason to retry immediately makes things worse; the Retry-After header exists to push well-behaved clients to back off instead.
Fail-open drift: while a shard is down and gateways enforce the local share (2/s each), traffic that happens to concentrate on 10 of the 50 gateways is capped at 10 × 2 = 20/s — legitimate traffic wrongly throttled — while perfectly even traffic is capped near the true 100/s. This under-shoot is the accepted cost of fail-open-with-a-ceiling; it is bounded and self-heals the instant the shard returns and the shared count resumes.
Counter expiry mid-burst: because state TTLs after two windows, a key idle for >2 s starts fresh at prev_count = 0. That is correct — an idle key has no recent rate — and the Lua's stored_win gap check zeroes stale prev_count rather than blending in a count from minutes ago.
Hot legitimate key: a key with a very high limit (say 10,000/s) can saturate its single shard. Splitting its counter across N shards, each enforcing limit/N, spreads the ops but reintroduces the fleet-factor error at small scale; it is worth it only when one key's op load actually threatens a shard, not by default.