Caches, Limits, Breakers

Ask a system design question down far enough and it stops being diagrams. "Design a URL shortener" ends in a cache with an eviction rule; "design an API gateway" ends in a rate limiter and a circuit breaker. The primitives are small — a class each — but each one carries an invariant that interviews are really about: recency, time-to-live, refill, quiet, failure. Build them once, correctly, and the big diagrams assemble from parts you trust.

Lazy beats scheduled

The unifying implementation decision: no timers. Every primitive below computes on read from (state, now) — expiry is checked when someone asks, refill is computed when a token is requested. A background sweeper would spread the logic across two places, race with reads, and make the behavior untestable without real waiting. Lazy evaluation puts the whole truth in one method and lets tests move the clock.

That last clause is the interview's quiet second question. A rate limiter that reads Date.now() itself cannot be tested at speed; one that takes now: () => number in its constructor is tested by advancing a variable. Inject the clock is the rule, and it is the difference between a primitive and a demo.

Recency: the LRU and its Map trick

The LRU cache's invariant: the Map's insertion order is the recency order — least recently used first. JavaScript's Map maintains insertion order, and delete-then-set moves a key to the newest end, so the whole algorithm is two moves:

get(key: string): number | undefined {
  if (!entries.has(key)) return undefined
  const value = entries.get(key) as number
  entries.delete(key)
  entries.set(key, value) // re-insert = newest
  return value
}

put(key: string, value: number): void {
  if (entries.has(key)) entries.delete(key)
  else if (entries.size >= capacity) {
    const oldest = entries.keys().next().value // first = least recent
    if (oldest !== undefined) entries.delete(oldest)
  }
  entries.set(key, value)
}

The two subtle moves: an update is a use (delete before set, so refreshing a value also refreshes recency — and never grows past capacity), and eviction reads the first key of iteration, which the Map guarantees is the oldest surviving insert. In an interview, deriving LRU from insertion order is worth more than reciting a doubly-linked-list implementation — it shows you know what the language already tracks.

} else if (entries.size >= capacity) {
  const oldest = entries.().next().value
  if (oldest !== undefined) entries.delete(oldest)
}

Refill, capped: the token bucket

Rate limiting has two canonical shapes. The sliding window log keeps timestamps and counts the recent ones — exact, but it stores one entry per accepted request. The token bucket stores two numbers: tokens refill continuously at a rate, each request consumes one, and the bucket never holds more than it started with.

tryConsume(): boolean {
  this.#refill()
  if (this.#tokens < 1) return false
  this.#tokens -= 1
  return true
}

#refill(): void {
  const elapsedMs = this.#now() - this.#lastRefillMs
  if (elapsedMs <= 0) return
  this.#tokens = Math.min(
    this.#capacity,
    this.#tokens + (elapsedMs / 1000) * this.#refillPerSecond
  )
  this.#lastRefillMs = this.#now()
}

The cap on the same line as the refill is the entire difference between a rate limiter and a savings account: without it, an idle bucket banks an unlimited burst, and the first second after idle exceeds the rate the limit promised. Fractional tokens accumulate on purpose — 500 ms at one-per-second is half a token, not zero, and rounding it away starves legitimate traffic. Lazy refill keeps the two numbers honest without a timer.

this.#tokens = Math.(
  this.#capacity,
  this.#tokens + (elapsedMs / 1000) * this.#refillPerSecond
)

Quiet and failure: debounce and the breaker

A trailing-edge debouncer fires once, waitMs after the last call — one pending slot, the newest call replaces it. Its sibling the throttle (at most once per interval) is a different promise; search boxes want debounce, scroll handlers want throttle, and mixing them up is a real bug people ship. The circuit breaker is the resilience answer to a dependency that is down: track consecutive failures, and past a threshold reject immediately with circuit open — without calling the task. After a timeout, one probe runs; its outcome closes or re-opens the circuit. The point is the fast rejection: every skipped call is a timeout the caller never waits for.

Both connect back to HTTP semantics, which is why they sit beside the HTTP exercises in this track: a breaker auto-retrying a timed-out request must only do it for idempotent methods — a GET, never a POST that already booked the ticket. Idempotency is not decoration in this material; it decides which failures are safe to retry.

How to debug all of them

Inject the clock and print the tuple the invariant lives in. LRU: print the Map's keys in order after each operation — they must read oldest-to-newest, and length must never exceed capacity. Token bucket: print (tokens, lastRefillMs) per check — tokens must never exceed capacity, never go negative, and elapsed must never be negative (a clock that jumps backwards breaks the math; decide and document what happens). Breaker: print the state on every call with its decision — a transition you cannot explain line-by-line is a bug you have not found yet. In the exercises for this concept, each review's hidden tests target exactly these invariants — the queue that stalls after a failure, the minimum that never comes back.

Where this bites

• Refill without the cap. Idle buckets bank unbounded bursts and the limit quietly stops limiting. Counter: the cap and the refill are one expression — min(capacity, tokens + gained) — never two statements that can drift apart.
• An update that is not a use. LRU put on an existing key that skips the delete lets the Map grow past capacity or strands a stale eviction order. Counter: delete-before-set on both get and put; recency is maintained at the moment of touch, not repaired later.
• Debounce where throttle belongs, or the reverse. The names travel together and the promises differ: last-call-waits versus at-most-once-per-interval. Counter: say the promise in the question's terms — "save after typing stops" versus "track at most 60 times a second" — and the structure names itself.
• A breaker that retries everything on timeout. Re-issuing a timed-out POST double-charges, double-books, double-sends — the failure and the success are indistinguishable to the caller. Counter: retry only what the method contract makes safe (idempotent by definition, not by hope), and let the breaker fail fast for the rest.