# Rate Limiting — Part 1: Algorithms

Part 1 covers the core algorithms a single rate limiter can implement, working against one counter/bucket. Part 2 covers distributing that counter across multiple servers, choosing the right limiting scope (per-user/IP/global), and the client-facing contract (429 response + headers).

## 1. Why Rate Limit at All

An API without limits lets one caller — buggy client code in a retry loop, a scraper, or a deliberate abuser — consume unbounded capacity, degrading service for every other caller. Rate limiting caps how many requests a given caller may make in a given window, trading a small amount of legitimate-traffic friction for protection against runaway or abusive load.

## 2. Fixed Window Counter — Simple, With a Sharp Edge

The simplest approach: count requests in discrete, non-overlapping time windows (e.g. per calendar minute), reset the counter to 0 at each window boundary:

```ts
const counters = new Map<string, { count: number; windowStart: number }>();

function allowFixedWindow(key: string, limit: number, windowMs: number, now: number): boolean {
  const entry = counters.get(key);
  const currentWindowStart = Math.floor(now / windowMs) * windowMs;

  if (!entry || entry.windowStart !== currentWindowStart) {
    counters.set(key, { count: 1, windowStart: currentWindowStart });
    return true;
  }
  if (entry.count >= limit) return false;
  entry.count++;
  return true;
}
```

The sharp edge: a client can send `limit` requests in the last millisecond of one window, then `limit` more in the first millisecond of the next — `2 * limit` requests in a tiny real time span, even though each window individually respected its cap. This "boundary burst" is fixed window's well-known weakness.

## 3. Sliding Window — Smoothing the Boundary

A sliding window avoids the fixed-window edge by looking back exactly `windowMs` from *now*, not from a fixed calendar boundary — typically implemented as a log of recent request timestamps, pruned on each check:

```ts
const requestLogs = new Map<string, number[]>();

function allowSlidingWindow(key: string, limit: number, windowMs: number, now: number): boolean {
  const log = requestLogs.get(key) ?? [];
  const cutoff = now - windowMs;
  const recent = log.filter((t) => t > cutoff); // drop anything older than the window

  if (recent.length >= limit) {
    requestLogs.set(key, recent);
    return false;
  }
  recent.push(now);
  requestLogs.set(key, recent);
  return true;
}
```

This correctly bounds any `windowMs`-wide slice of time to `limit` requests, closing the boundary-burst gap — at the cost of storing a timestamp per request instead of a single integer (addressed at scale by an approximation, see Part 2's distributed-counter discussion).

## 4. Token Bucket — Allowing Controlled Bursts

Token bucket takes a different philosophy: instead of a hard per-window cap, a bucket holds up to `capacity` tokens, refilling at a steady `refillRate` (tokens/second), and each request consumes one token:

```ts
class TokenBucket {
  private tokens: number;
  private lastRefill: number;

  constructor(private capacity: number, private refillRatePerMs: number, now: number) {
    this.tokens = capacity;
    this.lastRefill = now;
  }

  tryConsume(now: number): boolean {
    const elapsed = now - this.lastRefill;
    this.tokens = Math.min(this.capacity, this.tokens + elapsed * this.refillRatePerMs);
    this.lastRefill = now;

    if (this.tokens >= 1) {
      this.tokens -= 1;
      return true;
    }
    return false;
  }
}
```

Unlike a fixed window, a client that's been idle can "save up" tokens (up to `capacity`) and spend them in a legitimate burst — useful for bursty-but-not-abusive traffic patterns (a client that fetches a batch of resources at page load, then goes quiet). The bucket's steady-state throughput is bounded by `refillRate` regardless of burst shape.

![Fixed window, sliding window, token bucket and leaky bucket compared: boundary bursts, weighted smoothing, controlled bursts and constant output rate](diagrams/01-algorithms.svg)

## 5. Leaky Bucket — the Inverse: Smoothing Output, Not Allowing Bursts

Leaky bucket models a queue that drains (processes requests) at a **constant** rate, no matter how bursty the input — requests that arrive faster than the drain rate queue up (or get rejected once the queue is full), rather than being allowed through in a burst:

```
Token bucket:  bucket holds TOKENS, refills over time, requests CONSUME a token -- bursts allowed up to capacity
Leaky bucket:  bucket holds REQUESTS (a queue), drains at a FIXED rate -- output is always smooth, bursts get queued/dropped, never let through faster than the drain rate
```

Token bucket is the more common choice for API rate limiting specifically (it naturally expresses "N requests per second, with some burst tolerance"); leaky bucket shows up more where the goal is strictly smoothing output rate regardless of arrival pattern (e.g. shaping outbound traffic to a downstream system that genuinely cannot handle bursts at all).

## Common Pitfalls

1. **Choosing fixed window without realizing the boundary-burst weakness.** Section 2's `2 * limit` edge case is a real, exploitable gap, not a theoretical curiosity — a client that knows the window boundary can double its effective limit deliberately.
2. **Implementing sliding window with an unbounded log.** Without pruning old entries on every check (as shown in section 3), the log grows forever for a high-volume key — always drop entries older than the window on each check, not periodically.
3. **Confusing token bucket and leaky bucket as the same thing with different names.** They model opposite things: token bucket controls how much can be CONSUMED (bursts allowed); leaky bucket controls how fast output DRAINS (bursts smoothed away, never passed through).
4. **Not accounting for elapsed time correctly in token bucket.** Refilling only on a fixed tick (rather than computing elapsed time since `lastRefill`, as section 4 does) under- or over-refills depending on how often `tryConsume` happens to be called.

## Quick Reference

```
Fixed window    -- simple counter per calendar window -- boundary-burst weakness (2x limit possible)
Sliding window   -- timestamp log, filtered to the last windowMs -- no boundary weakness, more storage
Token bucket      -- tokens refill steadily, requests consume one -- allows bounded bursts
Leaky bucket       -- fixed-rate drain queue -- smooths bursts away, output rate never exceeds drain rate
```

Continue to `api_rate_limiting_theory_2.md` for distributed rate limiting, scope choices (per-user/IP/global), and the 429 response contract.