# Rate Limiter

Course: [Low-Level Design](https://www.devtutorials.ai/learn/system-design/lld) · Section: LLD Case Studies
Source: https://www.devtutorials.ai/learn/system-design/lld/case-studies/rate-limiter

> Build a per-user token bucket rate limiter with lazy refill and an injectable clock, tested with a fake clock.

On a busy Friday night, a faulty mobile application begins sending thousands of “Where is my order?” requests every second. If QuickBite processes every request, the service may become slow for all users.

A rate limiter controls how many requests a user or application can send within a period of time. It allows requests that stay within the limit and temporarily rejects requests that exceed it. A rejected request commonly receives the HTTP status code 429, which means Too Many Requests.

In the high-level design, the rate limiter was placed between users and the QuickBite service. In this case study, you will design the class that performs the rate-limiting checks.

The class will use a token bucket. Each user receives a bucket containing a limited number of tokens. Every request uses one token, and tokens are added back gradually. This allows short bursts of requests while stopping a continuous flood.

**In simple words:** you will build a rate limiter that allows normal traffic and blocks users or applications that send too many requests.

## What You Will Learn

In this case study, you will:

1. See why counting per calendar minute lets bursts through.
2. Build a token bucket that refills from elapsed time.
3. Pass a clock in, so time can be tested instantly.
4. Keep one bucket per user.
5. Build the limiter in the sandbox and pass the hidden tests.

The class you build here is exactly what runs inside the HLD rate limiter service, one bucket per user. In a real deployment the buckets live in Redis so every server shares them.

## Step 1: Agree on the Requirements

Before designing the classes, confirm what the rate limiter must do.

### What It Must Do

- Create a rate limiter with a bucket capacity, refill rate, and clock.
- Give each user a separate token bucket.
- Start each bucket with the maximum number of tokens.
- Use one token for every allowed request.
- Add tokens back gradually without exceeding the bucket’s capacity.
- Return `true` when a request is allowed and `false` when it should be rejected.

A rejected request can be returned to the client with HTTP status 429, which means Too Many Requests.

### What We Leave Out

- Sharing buckets across servers (Redis, from the HLD lesson).
- Different limits per endpoint (an exercise below covers plans).
- Telling the client exactly when to retry (an exercise below covers it).

Leaving things out on purpose is not lazy. It keeps the design small enough to finish, and you can say how you would add them later.

## Step 2: Find the Classes

A simple trick: underline the **nouns** in the requirements. Most of them become classes. The **verbs** become methods.

| Class | Its one job |
|---|---|
| RateLimiter | Finds the user's bucket and decides allow or reject |
| Bucket | Holds one user's tokens and the time of the last request |
| Clock | Tells the time; a fake one is used in tests |

<LldDiagram caption="The class diagram for this design." code={"classDiagram\n  class RateLimiter {\n    -capacity: number\n    -refillPerSecond: number\n    -buckets: Map~string, Bucket~\n    +allow(userId) boolean\n  }\n  class Bucket {\n    +tokens: number\n    +last: number\n  }\n  class Clock {\n    <<interface>>\n    +now() number\n  }\n  RateLimiter *-- Bucket : one per user\n  RateLimiter --> Clock : asks the time"} />

## Step 3: Build the Key Parts

### Why Not Just Count per Minute?

The simplest limiter counts requests in each calendar minute. But a user can send the whole limit at 0:59 and again at 1:00. Step through it with a limit of 5 per minute:

Here is the same idea in code:

```ts runnable title="A fixed window allows a burst at the edge"
// Max 5 requests per minute, counted per calendar minute.
function fixedWindow(times: number[], limit: number): number {
  const counts = new Map<number, number>();
  let allowed = 0;
  for (const t of times) {
    const minute = Math.floor(t / 60);
    const n = counts.get(minute) ?? 0;
    if (n < limit) { counts.set(minute, n + 1); allowed++; }
  }
  return allowed;
}

// 5 requests at 0:59 and 5 more at 1:00 - ten requests in two seconds.
const times = [59, 59, 59, 59, 59, 60, 60, 60, 60, 60];
console.log("allowed:", fixedWindow(times, 5));
```

Expected output:

```text
allowed: 10
```

All ten requests got through in two seconds, even though the limit is "5 per minute".

### The Token Bucket

Picture a bucket of tokens. Each request takes one token. Tokens drip back in at a steady speed, but the bucket never overflows. Short bursts are allowed (up to the bucket size), but the long-run speed is capped.

Here is a bucket that holds 3 tokens and gets 1 token back each second. Step through seven requests:

Here is the same idea in code:

```ts runnable title="A token bucket: tokens drip back in over time"
let tokens = 3;
const capacity = 3;
const refillPerSecond = 1;

function tryRequest(): string {
  if (tokens >= 1) { tokens -= 1; return "allowed"; }
  return "rejected (429)";
}
function wait(seconds: number): void {
  tokens = Math.min(capacity, tokens + seconds * refillPerSecond);
}

console.log(tryRequest(), tryRequest(), tryRequest(), tryRequest());
wait(2);
console.log(tryRequest(), tryRequest(), tryRequest());
```

Expected output:

```text
allowed allowed allowed rejected (429)
allowed allowed rejected (429)
```

### Refill Without a Timer

We do not need a background timer to add tokens. When a request arrives, work out how many tokens were earned since the last one: **earned = seconds passed × refill speed**, capped at the capacity. The bucket only needs two fields: its `tokens` and the time of its `last` update.

Here is the same idea in code:

```ts runnable title="Refill lazily, from the time since the last request"
class Bucket {
  constructor(public tokens: number, public last: number) {}
}

function refill(b: Bucket, now: number, capacity: number, perSecond: number): void {
  const earned = ((now - b.last) / 1000) * perSecond;
  b.tokens = Math.min(capacity, b.tokens + earned);
  b.last = now;
}

const b = new Bucket(0, 0);
refill(b, 1500, 10, 2);
console.log("after 1.5 s:", b.tokens);
refill(b, 60000, 10, 2);
console.log("after a minute:", b.tokens);
```

Expected output:

```text
after 1.5 s: 3
after a minute: 10
```

**Easy way to remember:** the bucket size is **how big a burst** you allow. The refill speed is **how fast, on average**, a user may go.

### Make Time Testable

If the limiter calls `Date.now()` itself, a test must really wait seconds. Pass a **clock** in instead (dependency inversion), and tests can jump forward instantly. The limiter depends on a small `Clock` interface. The real service uses a `SystemClock` that returns `Date.now()`. A test uses a `FakeClock` whose time it sets by hand: adding 5000 to it "waits" five seconds with no real waiting.

<LldDiagram caption="The limiter depends on the Clock interface, not on Date.now(). Tests swap in a FakeClock." code={"classDiagram\n  class RateLimiter {\n    -clock: Clock\n    +allow(userId) boolean\n  }\n  class Clock {\n    <<interface>>\n    +now() number\n  }\n  class SystemClock {\n    +now() number\n  }\n  class FakeClock {\n    +t: number\n    +now() number\n  }\n  RateLimiter --> Clock : asks the time\n  Clock <|.. SystemClock : real service\n  Clock <|.. FakeClock : tests"} />

Here is the same idea in code:

```ts runnable title="Pass the clock in, so tests control time"
interface Clock {
  now(): number;
}
class FakeClock implements Clock {
  t = 0;
  now(): number { return this.t; }
}
class SystemClock implements Clock {
  now(): number { return Date.now(); }
}

const fake = new FakeClock();
fake.t += 5000; // "wait" five seconds instantly
console.log("fake time:", fake.now());
console.log("real clock is a number:", typeof new SystemClock().now());
```

Expected output:

```text
fake time: 5000
real clock is a number: number
```

### One Bucket per User

The limiter keeps a `Map` from user id to bucket. Step through two users sharing one limiter:

Here is the same idea in code:

```ts runnable title="One bucket per user, created on first use"
const buckets = new Map<string, number>();

function take(user: string, capacity: number): boolean {
  const left = buckets.get(user) ?? capacity;
  if (left < 1) return false;
  buckets.set(user, left - 1);
  return true;
}

console.log(take("asha", 2), take("asha", 2), take("asha", 2));
console.log(take("ravi", 2));
```

Expected output:

```text
true true false
true
```

Every new user adds a bucket, and buckets that are never removed slowly fill memory. A real service deletes buckets that stay full and unused for a while, or stores them with an expiry time.

## Lab: Build It

Build the `RateLimiter` class using the token-bucket rules explained in this case study.

The automated tests use a fake clock, which allows the tests to control time without waiting in real time. The tests send several requests, move the clock forward, and check whether tokens are refilled correctly for each user.

Follow these steps:

1. Use a `Map` to store one bucket for each user. Each bucket should record the number of available tokens and the time of the last update.
2. When a new user sends a request, create a full bucket for that user.
3. Each time `allow(userId)` is called, calculate how many tokens have been earned since the last update.
4. Add the earned tokens without allowing the total to exceed the bucket’s capacity.
5. If at least one token is available, remove one token and return `true`.
6. If no tokens are available, return `false`.

Open the lab in the sandbox and run the tests after each step. When a test fails, the message explains which rate-limiting rule is not working correctly.

## Predict the Output

<CsPredict id="rate-1" code={"double tokens = 2, capacity = 2, perSecond = 1;\nbool Allow() { if (tokens >= 1) { tokens -= 1; return true; } return false; }\nConsole.WriteLine($\"{Allow()} {Allow()} {Allow()}\");\ntokens = Math.Min(capacity, tokens + 5 * perSecond);\nConsole.WriteLine(tokens);"} expected={"True True False\n2"} why="Two tokens allow two requests; the third is refused. After 5 seconds, 5 tokens were earned, but the bucket is capped at its capacity of 2." />

## Common Mistakes

| Mistake | Wrong | Correct | Why it happens |
|---|---|---|---|
| Fixed window | Count requests per calendar minute. | A token bucket. | It is the first idea and easy to code. |
| No cap | Tokens keep piling up overnight. | Math.min(capacity, ...). | Short tests never wait long enough. |
| Real clock inside | Date.now() in allow(). | Pass a Clock in. | It works, until you need to test it. |
| One bucket for all | One noisy user blocks everyone. | A Map of buckets per user. | A single bucket passes single-user tests. |
| Buckets never removed | The map grows with every visitor forever. | Expire idle buckets. | Memory problems take weeks to show. |

## Practice

## What to Remember

- A **token bucket** allows short bursts and caps the steady rate.
- **Capacity** is the burst; **refill speed** is the average limit.
- Refill **lazily** from the time since the last request.
- Pass a **clock** in so tests control time.
- Keep **one bucket per user**.

## Further Reading

These are the sources used to check this case study:

- [Wikipedia: Token bucket](https://en.wikipedia.org/wiki/Token_bucket): the algorithm.
- [MDN: 429 Too Many Requests](https://developer.mozilla.org/en-US/docs/Web/HTTP/Status/429): the response a limited client gets.
- [Stripe: Scaling your API with rate limiters](https://stripe.com/blog/rate-limiters): how a real company uses token buckets.

Next: **Splitwise**. You will build a ledger that splits bills between friends and settles them with the fewest payments.