CSE Roadmap

Core tier · about 4 hours · 6 parts

Part 2 of 6 · 2 min read

Requirements

Allow or refuse, per client, fast.

Think of a bouncer at a club. The room holds 100, and the bouncer lets people in only while there is space, or only a few per minute. People who are turned away are told so, and may try again later. A rate limiter does that for requests.

The book gives the purpose in one line: a rate limiter caps how many requests a client may send in a period, and requests above the cap are blocked, with HTTP status 429 (too many requests).

Questions and the answers assumed here:

  1. Limited by what? A client key, such as a user id or an IP address. Each key has its own count.
  2. What is the answer to a call? Allowed or refused.
  3. Which rules? A limit and a time window, such as 5 per minute. Different endpoints may have different rules.
  4. How strict? Bursts for a short time are fine for some APIs and not for others, so the algorithm should be replaceable.
  5. Many threads? Yes.
  6. Out of scope: sharing counters between servers, and the configuration file.

The numbered requirements:

  • R1. tryAcquire says whether one more request may go through now, and counts it if so.
  • R2. A refused request does not use up quota.
  • R3. Each client key has its own limiter.
  • R4. The algorithm is chosen by configuration and can be swapped.
  • R5. The limiter reads time from a clock that a test can control.
  • R6. Many threads can call it safely.

The nouns are limiter, client key, window, limit, token and clock. The key design choice is the interface:

interface RateLimiter { boolean tryAcquire(); }

One method, one answer. Each algorithm is a class that implements it, so the choice of algorithm is a strategy (Level 4, module 1).

Rate limiter

A rate limiter decides, for each request, whether the client has stayed within its allowed number of requests per period.

Example: a login endpoint that allows 5 attempts per minute per user.

Check yourself: 1. Why does a refused request not use quota? 2. Which pattern lets the algorithm change? 3. Which status code do refused HTTP requests get?