CSE Roadmap

Core tier · about 4 hours · 8 parts

Part 5 of 8 · 2 min read

Deep dive

The method, the rules and what the client sees.

Choosing the method. The five methods (Level 1, page 7) trade memory, accuracy and burst handling. A short guide:

Need Method Reason
Allow short bursts, little memory Token bucket Two numbers per client, and bursts pass while tokens last. The book says large companies use it
Steady output speed Leaking bucket A queue drained at a fixed rate
Simplest and cheapest Fixed window One counter, but a burst at the window edge can pass twice the limit
Exact in any rolling window Sliding window log Keeps timestamps, so memory grows with the limit
Close to exact and cheap Sliding window counter An estimate from two counters. The book cites a test of 400 million requests where only about 0.003 per cent were wrongly allowed or refused

For an API with bursty clients, the token bucket is a fine default. The number of buckets per client depends on the rules: one per endpoint, one per IP address, or a single global bucket for a total cap.

Where the rules live. Rules are data, not code. A rule says which key, which unit of time and how many requests. The book shows an example from the Lyft open-source limiter, where one rule allows 5 marketing messages per day and another limits login tries per minute. The rules sit in files or a database. Workers read them and keep a copy in a local cache on each limiter, so that checking a rule is a memory read and not a network call. When a rule changes, the copies refresh within a few seconds.

What the client sees. A refused request gets status 429. The book says to also send headers that help the client behave: how many calls remain in the window, what the limit is, and how many seconds to wait before retrying. A well-behaved client then slows down instead of hammering. The limiter may also drop the request, or put it in a queue to be handled later, depending on the product.

Full flow with the pieces.

client --> gateway [middleware] --> API servers
              |  rules cache (refreshed from rules store)
              +--> counter store, 8 shards by client key, each with a replica
              +--> 429 + headers when over the limit

Check yourself: 1. Which method fits a client that sends short bursts? 2. Why does each limiter keep a local copy of the rules? 3. Which headers help a refused client?