CSE Roadmap

Core tier · about 4 hours · 8 parts

Part 2 of 8 · 3 min read

Requirements and numbers

Ask first, then count.

Think of a bouncer at the door of a club. The bouncer must know how many people each group may bring, must decide quickly, and must still work when a hundred people arrive at once. A rate limiter is that bouncer for API calls.

The Xu book states the job in one line: a rate limiter caps how many requests a client may send in a period, and requests over the cap are blocked. Examples from the book are a limit of 2 posts per second per user, 10 accounts per day from one IP address, and 5 gift claims per week from one device.

Questions to ask, with the answers assumed here.

  1. Where does it run? On the server side. Clients cannot be trusted, since requests can be forged.
  2. What is it limited by? A client key, which may be a user id, an IP address or an API key. Rules can differ per endpoint.
  3. How big is the system? Large. Assume 10 million active clients and a peak of 500,000 requests per second across all API servers (made up to show the idea).
  4. Must it work across many servers? Yes.
  5. Is it a separate service or part of the code? Left open, so the design decides.
  6. Must users be told? Yes, a clear error and when to retry.

Requirements.

  • R1. Limit requests by key and by rule, such as 100 per minute per user on one endpoint.
  • R2. Decide in about 2 ms or less, since the check is on every request path.
  • R3. Work across many API servers, with one shared view of each client.
  • R4. If the limiter itself fails, the API keeps serving.
  • R5. Refused clients get a clear answer and a retry hint.
  • R6. Use little memory per client.
  • R7. Rules can change without a deploy.

Numbers. Each rule per client needs a small record: a count and a time. Say 60 bytes with the key (made up). With 10 million clients and 3 rules each, that is 10,000,000 × 3 × 60 bytes = 1.8 GB. That fits in the memory of one cache node, so the data size is not the problem. Two copies for safety make about 3.6 GB.

Load is the real problem. At 500,000 requests per second, and one atomic store operation per request, the store must do 500,000 operations per second. One cache node does perhaps 100,000 such operations per second (made up). So at least 5 nodes are needed, and 8 gives room for peaks and uneven keys. The key lesson: counters are small, but they are hit very often, so split them across nodes by client key.

Rate limiter

A rate limiter is a component that counts requests per client and refuses those above an agreed limit.

Example: a gateway that lets a user call "post message" 10 times per minute and answers the eleventh call with an error.

Check yourself: 1. Why is the client side a poor place to limit? 2. Why is counter memory small but store load large? 3. How many store nodes does 500,000 operations per second need at 100,000 each?