Rate Limiter

“Design a rate limiter.” The arithmetic can fit in ten lines; the design question is whether identity, time, burst policy, and shared state still agree when a request reaches the boundary. We will give those decisions explicit owners, compare two honest algorithms, and keep the transport layer outside the core.

Requirements

Fix what is being limited before choosing a counter. “N requests per window” is incomplete until the client key, boundary rule, and burst behavior are known.

Distributed coordination internals, billing or quota charging, HTTP headers, and the transport layer are out of scope. The model returns a domain decision; an Express, Next.js, RPC, or gateway adapter decides how that becomes a 429 response.

Clarifying questions to ask

These questions decide the client key, the algorithm, and the failure policy. Ask them before drawing a box named RateLimiter.

• Are we limiting by IP, user, or API key? The authenticated API key is the baseline because it follows a customer across devices. A public endpoint may fall back to IP. The key must include the policy scope, such as route and tier, when those scopes have separate allowances.
• Does one user share a limit across every route? No. A write endpoint and a cheap read endpoint can receive different RateLimitConfig values. Application setup selects a limiter for the route and tier instead of hiding route logic inside an algorithm.
• What does “N per window” mean at the boundary? A sliding window contains timestamps strictly newer than now - windowMs; a request exactly one window old has expired. A token bucket refills continuously at limit / windowMs.
• Fixed window, sliding window, or token bucket—and why? Fixed windows are cheap but can admit almost 2N calls around a boundary. Sliding windows smooth that edge by counting the trailing interval. Token buckets allow a declared burst and recover continuously.
• How much burst is acceptable? This baseline gives a token bucket capacity equal to limit. An idle client can spend that capacity at once, then earns tokens back at a steady rate. A product may separate burst capacity from refill rate when those promises differ.
• Are counters in memory or in a shared store such as Redis? The skeleton is one-process memory. Several application instances need shared, atomic read-modify-write operations; several local maps would each grant a full allowance.
• What happens when the shared store is down? Fail-open allows the request and protects availability, but it may exceed the limit. Fail-closed denies the request and protects a sensitive operation, but it can turn a store outage into an application outage. Choose per endpoint.
• Do rejected requests consume allowance? No. A token is removed only for an allowed request, and a sliding-window timestamp is appended only for an allowed request. Rejected attempts may still feed separate abuse metrics.
• Can the configuration change while clients have state? Yes in a real product, but the migration rule must be explicit. The compact model treats one limiter instance as one immutable policy; replacing its configuration creates or migrates state at the composition boundary.
• Which clock matters? A monotonic clock is a time source that never moves backward, which makes elapsed-time refill safe. Tests receive a manual clock seeded to a known value, while production supplies a monotonic adapter.
• How precise must retry-after be? Milliseconds are enough for this core. The transport may round up to whole seconds for a header, but it should never tell the client to retry earlier than the domain decision.
• Can two requests for the same client arrive together? Yes. The in-process method is synchronous; a shared-store implementation must make refill or eviction, capacity check, and consumption one atomic operation.

Entity extraction

Run the noun pass from requirements-to-classes against the clarified contract:

1. A caller asks a rate limiter whether one client ID may make a request.
2. A rate-limit configuration supplies a limit and a window for one policy scope.
3. A rate-limit strategy applies either a token-bucket or sliding-window algorithm.
4. A client state stores tokens and refill time, or accepted request timestamps.
5. A clock supplies the current time, and a decision carries allow, deny, and retry-after data.

Sort the nouns by identity, value, boundary, and varying behavior:

The verb pass puts each rule beside the facts it needs:

RateLimitStrategy is the Strategy pattern from strategy: configuration chooses one interchangeable algorithm, and the facade delegates through one contract. The client state is not another strategy; it is the mutable fact the selected algorithm protects.

Core class diagram

Seven nodes are enough to show the facade, both algorithms, policy, state, and time. Redis clients, middleware classes, metrics, and HTTP responses belong around this core.

The Strategy seam is selected at construction. Replacing token bucket with sliding window changes the implementation object, not RateLimiter.allow(). Existing state cannot be blindly reused across that swap because tokens and timestamp logs have different meanings; reset or migrate it deliberately.

Neither algorithm dominates every workload. Token bucket is attractive when short bursts are legitimate. Sliding window is attractive when the trailing-window promise matters more than its memory. A fixed-window counter is cheaper still, but two edge-adjacent bursts can cross its boundary.

Different routes and tiers receive different RateLimitConfig objects at application setup. One approach constructs a limiter per policy. Another registry maps a policy ID to a limiter. In either design, the state key must include enough scope to prevent a premium upload allowance from merging with a free-tier read allowance.

Where the limiter sits in middleware

The chain-of-responsibility lesson shows authentication, rate limiting, and the endpoint as ordered handlers. An Express or Next.js rate-limit middleware is the same Chain of Responsibility shape: it either short-circuits with a denial or calls next().

For an authenticated per-user or per-API-key policy, place authentication first so the limiter receives the canonical identity, then place rate limiting before the business handler so rejected traffic does not consume expensive work. A separate perimeter IP limiter may run before authentication for denial-of-service protection; that is another policy and another key, not a reason to blur both allowances.

Critical-flow sequence diagram

The flow worth drawing is “allow this request?” The strategy's middle step reads as refill for a bucket or timestamp eviction for a sliding window.

On the allow branch, the strategy consumes capacity before returning. On the deny branch, state remains valid and retryAfterMs points to the next natural opportunity: one token's refill time or the oldest accepted timestamp's expiry.

In a shared-store implementation, messages 3 through 7 form the atomic boundary. A separate read followed by a write can let two servers observe the same remaining token and both allow it.

TypeScript skeleton

The skeleton implements both algorithms behind one interface. ManualClock is seeded in its constructor and advances only when the test asks, so exhaustion and recovery require no sleeping.

export {};
 
interface RateLimitConfig {
  readonly limit: number;
  readonly windowMs: number;
}
 
interface RateLimitDecision {
  readonly allowed: boolean;
  readonly retryAfterMs: number | null;
}
 
interface Clock {
  now(): number;
}
 
class ManualClock implements Clock {
  public constructor(private currentMs: number) {
    if (!Number.isFinite(currentMs)) {
      throw new Error("initial time must be finite");
    }
  }
 
  public now(): number {
    return this.currentMs;
  }
 
  public advance(milliseconds: number): void {
    if (!Number.isFinite(milliseconds) || milliseconds < 0) {
      throw new Error("clock advance must be non-negative");
    }
    this.currentMs += milliseconds;
  }
}
 
interface TokenBucketState {
  readonly kind: "token-bucket";
  readonly config: RateLimitConfig;
  tokens: number;
  lastRefillMs: number;
}
 
interface SlidingWindowState {
  readonly kind: "sliding-window";
  readonly config: RateLimitConfig;
  readonly acceptedAt: number[];
}
 
type ClientState = TokenBucketState | SlidingWindowState;
 
interface RateLimitStrategy {
  createState(
    config: RateLimitConfig,
    now: number,
  ): ClientState;
 
  tryConsume(
    state: ClientState,
    now: number,
  ): RateLimitDecision;
}
 
function allowDecision(): RateLimitDecision {
  return { allowed: true, retryAfterMs: null };
}
 
function denyDecision(retryAfterMs: number): RateLimitDecision {
  return {
    allowed: false,
    retryAfterMs: Math.max(1, Math.ceil(retryAfterMs)),
  };
}
 
class TokenBucketStrategy implements RateLimitStrategy {
  public createState(
    config: RateLimitConfig,
    now: number,
  ): ClientState {
    return {
      kind: "token-bucket",
      config,
      tokens: config.limit,
      lastRefillMs: now,
    };
  }
 
  public tryConsume(
    state: ClientState,
    now: number,
  ): RateLimitDecision {
    if (state.kind !== "token-bucket") {
      throw new Error("token bucket received incompatible state");
    }
 
    const elapsedMs = Math.max(0, now - state.lastRefillMs);
    const tokensPerMs =
      state.config.limit / state.config.windowMs;
 
    state.tokens = Math.min(
      state.config.limit,
      state.tokens + elapsedMs * tokensPerMs,
    );
    state.lastRefillMs = Math.max(state.lastRefillMs, now);
 
    if (state.tokens >= 1) {
      state.tokens -= 1;
      return allowDecision();
    }
 
    return denyDecision((1 - state.tokens) / tokensPerMs);
  }
}
 
class SlidingWindowStrategy implements RateLimitStrategy {
  public createState(
    config: RateLimitConfig,
    _now: number,
  ): ClientState {
    return {
      kind: "sliding-window",
      config,
      acceptedAt: [],
    };
  }
 
  public tryConsume(
    state: ClientState,
    now: number,
  ): RateLimitDecision {
    if (state.kind !== "sliding-window") {
      throw new Error("sliding window received incompatible state");
    }
 
    const latest = state.acceptedAt.at(-1);
    if (latest !== undefined && now < latest) {
      throw new Error("clock must not move backwards");
    }
 
    const cutoff = now - state.config.windowMs;
    while (
      state.acceptedAt[0] !== undefined &&
      state.acceptedAt[0] <= cutoff
    ) {
      state.acceptedAt.shift();
    }
 
    if (state.acceptedAt.length < state.config.limit) {
      state.acceptedAt.push(now);
      return allowDecision();
    }
 
    const oldest = state.acceptedAt[0];
    if (oldest === undefined) {
      throw new Error("full window has no oldest timestamp");
    }
 
    return denyDecision(
      oldest + state.config.windowMs - now,
    );
  }
}
 
class RateLimiter {
  private readonly states = new Map<string, ClientState>();
  private readonly config: RateLimitConfig;
 
  public constructor(
    private readonly strategy: RateLimitStrategy,
    config: RateLimitConfig,
    private readonly clock: Clock,
  ) {
    if (!Number.isSafeInteger(config.limit) || config.limit <= 0) {
      throw new Error("limit must be a positive integer");
    }
    if (
      !Number.isSafeInteger(config.windowMs) ||
      config.windowMs <= 0
    ) {
      throw new Error("windowMs must be a positive integer");
    }
 
    this.config = Object.freeze({ ...config });
  }
 
  public allow(clientId: string): RateLimitDecision {
    const key = clientId.trim();
    if (key.length === 0) {
      throw new Error("client id is required");
    }
 
    const now = this.clock.now();
    if (!Number.isFinite(now)) {
      throw new Error("clock returned an invalid time");
    }
 
    let state = this.states.get(key);
    if (state === undefined) {
      state = this.strategy.createState(this.config, now);
      this.states.set(key, state);
    }
 
    return this.strategy.tryConsume(state, now);
  }
}
 
function formatDecision(decision: RateLimitDecision): string {
  if (decision.allowed) return "allow";
  return (
    "deny (retry after " +
    decision.retryAfterMs +
    "ms)"
  );
}
 
const clock = new ManualClock(10_000);
const freeTierConfig: RateLimitConfig = {
  limit: 3,
  windowMs: 3_000,
};
const limiter = new RateLimiter(
  new TokenBucketStrategy(),
  freeTierConfig,
  clock,
);
 
for (let request = 0; request < 4; request += 1) {
  console.log(formatDecision(limiter.allow("api-key-7")));
}
 
clock.advance(1_000);
console.log(
  "after 1000ms: " +
  formatDecision(limiter.allow("api-key-7")),
);
 
// The facade also accepts:
// new RateLimiter(new SlidingWindowStrategy(), config, clock)

allow allow allow deny (retry after 1000ms) after 1000ms: allow

The first three rapid requests spend the seeded bucket. The fourth sees zero tokens and reports the exact time needed to earn one token at three requests per three seconds. Advancing the manual clock by one second refills one token, so the next request recovers.

The bucket stores fractional tokens, which makes continuous refill explicit: half a window can earn half the configured allowance. An integer-token design can instead track accumulated time, but it still needs a declared rounding rule at the boundary.

The array-backed sliding window favors readability. At a high limit, use a deque, a double-ended queue with efficient removal at the front, or a timestamp array with a moving head. That data-structure change stays inside SlidingWindowStrategy.

Design-review checklist

This is where an interviewer turns a five-call demo into an operational boundary.

• Strategy seam: RateLimiter delegates state creation and consumption through RateLimitStrategy. A new algorithm does not change the facade, but changing algorithms requires a deliberate state reset or migration.
• Token bucket versus sliding window: Token bucket uses constant per-client state and permits bounded bursts. Sliding window gives a smoother exact trailing-window rule at the cost of timestamp memory and cleanup. Match the workload instead of declaring one universal winner.
• Per-client key design: Include the canonical client identity and policy scope. Decide how anonymous IPs, shared network addresses behind NAT, API-key rotation, route groups, and customer tiers affect fairness before concatenating a key.
• Configuration ownership: Keep limit and window immutable for one limiter instance. A policy registry may choose different instances for routes or tiers; it should version configuration when live state must survive a change.
• In memory versus shared storage: One Map is correct for one process only. Multiple instances need Redis or another shared store with atomic scripts, transactions, or compare-and-set semantics.
• Atomicity: Refill or eviction, capacity check, and consumption are one read-modify-write. Locking only the final decrement still lets concurrent requests make the same stale decision.
• Clock injection: Tests seed time, exhaust capacity, advance exactly to a boundary, and verify recovery without sleeping. Production should use a monotonic source for elapsed-time arithmetic.
• Fail-open versus fail-closed: Fail-open keeps an ordinary read endpoint available during a store outage but may exceed quota. Fail-closed protects sensitive or costly work but couples its availability to the limiter store.
• Retry-after semantics: Round outward at the transport boundary and document units. A fixed-window reset, next token, and oldest sliding timestamp describe different retry moments.
• Burst versus smoothness: Bucket capacity is a product promise, not an implementation accident. A large bucket can overwhelm a dependency even when its long-term refill rate looks safe.
• Memory lifecycle: Remove idle client state or expire it in the store. Sliding-window logs and unbounded client IDs can otherwise turn an admission control into a memory leak.
• Observability: Count allowed, denied, store-error, and fail-open decisions by policy. Avoid raw client IDs as metric labels because millions of unique labels make the metric expensive; logs can retain enough policy context to diagnose a denial.
• Testing exhaustion and recovery: Make N immediate calls, assert the next is denied, advance to just before and exactly at recovery, then assert allowance. Repeat for isolated clients and configuration scopes.
• Testing concurrency: Race more calls than the limit against the real shared-store adapter and assert the number allowed never exceeds the contract. Sequential unit tests cannot prove atomicity.
• Middleware order: For a user-keyed limit, authenticate first, then rate-limit, then invoke the handler. Test that denial short-circuits the chain and that the business handler sees no rejected request.
• With more time: Add a shared-state port, policy registry, configuration versioning, idle-state expiry, metrics, and transport adapters only after their consistency and failure contracts are named.

The limiter turns a vague traffic rule into a policy key, a time seam, replaceable algorithms, and one atomic decision. Chess is the final case study: a much larger prompt where the same ownership discipline keeps a board, pieces, and rule pipeline understandable.