Low-level design · Libraries and infrastructure

Rate limiter with pluggable algorithms

Reported in several places
SDE-2 (off-campus); internship; Principal (Poland)
Strategy
Factory
Sliding window
Token bucket
3 sources

Two or more independent public pages, at least one a candidate write-up.

The prompt

Design a rate limiter for an API. Given requests that carry millisecond timestamps, decide for each one whether it is allowed, for example when a user may send at most two pings per second. Reports describe this both as a short pseudocode design and as a concrete function, so be ready to show a small class design and to compare the algorithms you could plug in.

Restated in our own words, not a quote from Atlassian or any page. The answer below is written for this site.

Try it first.The answer is covered until you pick. Talk it through against a 60 minute clock, or just read it.

Clarify first

Pin the scope down before you name a single class.

Questions worth asking before you write a line:

What identifies the caller: a user id, an API key, an IP address? Assume an opaque string key.
Is there one limit or several, such as per second and per minute? Assume one named rule has one limit, and many rules can be registered side by side.
One process or a fleet of servers? Assume one process, and say what changes for a fleet.
Should a rejected caller learn when to try again? Assume yes.
How exact must the count be at window edges? Assume the owner of each rule chooses the algorithm, and that a request exactly one window old no longer counts.

In scope: the limiter interface, three algorithms, a factory that validates the spec, a service that holds named rules, and an injected clock. Out of scope: shared storage across servers, hot reload of configuration, HTTP headers and metrics.

Entities and relationships

Who owns what, and who talks to whom.

Clock is an injected collaborator with now() in milliseconds. Tests use a manual clock, so no test ever sleeps.
Limiter is the interface: tryAcquire(key) returns a decision. Every algorithm implements it.
Decision is a small value: allowed plus retryAfterMs, so callers can build a retry hint.
FixedWindowLimiter, SlidingWindowLogLimiter and TokenBucketLimiter implement Limiter. Each owns a map from key to its own small state and reads the shared clock.
createLimiter is a factory that turns a plain spec such as { type: "bucket", capacity: 3 } into a limiter.
RateLimiterService has many named rules, each one limiter, and exposes check(rule, key). Callers never see the algorithm.

The design

The class map, the main flow and the patterns that earn their place.

Rate limiter class mapThe service talks only to the Limiter interface. A factory picks the algorithm and one clock is shared.

At start-up the service asks the factory to build one limiter for each named rule.
The factory returns one of the three algorithms, typed only as a Limiter.
A request calls check with a rule name and a key such as a user id.
The service forwards to the rule's limiter, which reads the clock and decides.

Open on the whiteboardAll 2 diagrams on one tidy board, with a step-by-step walkthrough.

The core of the design is one narrow interface and several interchangeable algorithms. RateLimiterService only knows Limiter.tryAcquire(key), so choosing fixed window, sliding log or token bucket is a one line change in a rule's spec. That is the Strategy pattern, and the factory keeps construction details out of the service.

The three algorithms trade accuracy against cost:

Fixed window keeps a count per key and resets it when the window number changes. It is O(1) in time and memory, but a caller can send the full limit just before a boundary and again just after it, so up to twice the limit passes in a short span.
Sliding window log keeps the timestamps of accepted requests, drops those at or before now - window, and compares the remaining count with the limit. It is exact, costs O(limit) memory per key, and each timestamp is added and removed once. Array shift is linear on long arrays, so a large limit wants a ring buffer.
Token bucket stores a token balance and the time of the last refill. On each call it adds elapsed * rate tokens, capped at capacity, then spends one. The balance is kept in thousandths of a token, so whole-number rates stay exact and retryAfterMs is not off by a rounding error. It is O(1), allows a burst up to capacity, and then settles to the refill rate. If the clock steps backwards the bucket neither refills nor goes negative.

Main flow: the caller invokes check(rule, key), the service looks up the rule's limiter, the limiter reads the clock exactly once so the whole decision uses a single timestamp, updates its state for that key, and returns a decision. A denied decision carries retryAfterMs, for example the time until the oldest logged request leaves the window.

Two choices matter. First, denied requests are not recorded in the sliding log, otherwise a client that keeps retrying would never recover. Second, the clock is injected, so the two-pings-per-second example is a plain function over a list of timestamps.

Concurrency: each decision is a read-modify-write on per-key state. In this single-threaded model that is atomic. A real service needs a lock per key or an atomic compare-and-set, and across servers a shared store with atomic operations, or a local limiter with the limit divided between nodes. The trade-off I made is accuracy and simplicity per process over cross-server precision.

The code

Runnable JavaScript, with the checks it passes.

atlassian-rate-limiter.js

class ManualClock {
  constructor(start = 0) {
    this.time = start;
  }
  now() {
    return this.time;
  }
  set(time) {
    this.time = time;
  }
}

function allowed() {
  return { allowed: true, retryAfterMs: 0 };
}

function denied(retryAfterMs) {
  return { allowed: false, retryAfterMs };
}

class FixedWindowLimiter {
  constructor(clock, limit, windowMs) {
    this.clock = clock;
    this.limit = limit;
    this.windowMs = windowMs;
    this.windows = new Map();
  }
  tryAcquire(key) {
    const now = this.clock.now();
    const start = Math.floor(now / this.windowMs) * this.windowMs;
    let state = this.windows.get(key);
    if (!state || state.start !== start) {
      state = { start, count: 0 };
      this.windows.set(key, state);
    }
    if (state.count >= this.limit) return denied(start + this.windowMs - now);
    state.count += 1;
    return allowed();
  }
}

class SlidingWindowLogLimiter {
  constructor(clock, limit, windowMs) {
    this.clock = clock;
    this.limit = limit;
    this.windowMs = windowMs;
    this.logs = new Map();
  }
  tryAcquire(key) {
    const now = this.clock.now();
    const log = this.logs.get(key) || [];
    while (log.length > 0 && log[0] <= now - this.windowMs) log.shift();
    this.logs.set(key, log);
    if (log.length >= this.limit) return denied(log[0] + this.windowMs - now);
    log.push(now);
    return allowed();
  }
}

class TokenBucketLimiter {
  constructor(clock, capacity, refillPerSecond) {
    this.clock = clock;
    this.capacity = capacity;
    this.refillPerSecond = refillPerSecond;
    this.buckets = new Map();
  }
  tryAcquire(key) {
    const now = this.clock.now();
    const bucket = this.buckets.get(key) || { balance: this.capacity * 1000, updatedAt: now };
    const elapsed = Math.max(0, now - bucket.updatedAt);
    bucket.balance = Math.min(this.capacity * 1000, bucket.balance + elapsed * this.refillPerSecond);
    bucket.updatedAt = Math.max(now, bucket.updatedAt);
    this.buckets.set(key, bucket);
    if (bucket.balance < 1000) return denied(Math.ceil((1000 - bucket.balance) / this.refillPerSecond));
    bucket.balance -= 1000;
    return allowed();
  }
}

function positive(value, name, whole) {
  if (!Number.isFinite(value) || value <= 0 || (whole && !Number.isInteger(value))) {
    throw new Error(name + " must be a positive " + (whole ? "integer" : "number"));
  }
}

function createLimiter(spec, clock) {
  if (spec.type === "fixed" || spec.type === "sliding") {
    positive(spec.limit, "limit", true);
    positive(spec.windowMs, "windowMs", false);
  } else if (spec.type === "bucket") {
    positive(spec.capacity, "capacity", true);
    positive(spec.refillPerSecond, "refillPerSecond", false);
  }
  if (spec.type === "fixed") return new FixedWindowLimiter(clock, spec.limit, spec.windowMs);
  if (spec.type === "sliding") return new SlidingWindowLogLimiter(clock, spec.limit, spec.windowMs);
  if (spec.type === "bucket") return new TokenBucketLimiter(clock, spec.capacity, spec.refillPerSecond);
  throw new Error("unknown limiter type " + spec.type);
}

class RateLimiterService {
  constructor(clock) {
    this.clock = clock;
    this.rules = new Map();
  }
  addRule(name, spec) {
    if (this.rules.has(name)) throw new Error("rule exists: " + name);
    this.rules.set(name, createLimiter(spec, this.clock));
    return this;
  }
  check(rule, key) {
    const limiter = this.rules.get(rule);
    if (!limiter) throw new Error("unknown rule " + rule);
    return limiter.tryAcquire(key);
  }
}

function classifyPings(timestamps, spec) {
  const clock = new ManualClock();
  const limiter = createLimiter(spec, clock);
  return timestamps.map((time) => {
    clock.set(time);
    return limiter.tryAcquire("user").allowed;
  });
}

Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.

Try your own input

Write JavaScript that calls the code above and prints with console.log. It runs after the solution.

Extend it

The change requests an interviewer throws next.

How would you enforce two rules at once, such as 2 per second and 100 per minute, without spending a token on the first rule when the second one denies?
How do you stop memory from growing when millions of keys appear once and never return?
How would the same limit hold across several servers behind a load balancer, and what do you give up?
How would you cut the sliding log to constant memory per key while staying close to exact, for example with two adjacent window counters?
Which algorithm would you pick for a login endpoint and which for a public search API, and why?

Where candidates slip

The mistakes this problem punishes.

These mistakes are what this problem tends to punish:

Calling the system clock inside the limiter, which makes the behaviour impossible to test deterministically.
Off-by-one errors at the window edge: whether a request exactly one window old still counts must be decided and tested.
Recording denied requests in the sliding log, so a client that retries is blocked for ever.
Using one global counter instead of state per key.
Returning only a boolean, which gives callers no retry hint.
Presenting fixed window as exact without naming the boundary burst, or letting idle keys accumulate state with no eviction plan.

Have a go before you read.

Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.

Always show the answer straight away

Now make it stick

Sketch the class map on the whiteboard Run a mock interview

Where this was reported

Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.

Read these chapters first

Rate limiting & throttling

Now make it stick

Where this was reported

Read these chapters first

More on libraries and infrastructure