Skip to content
Tutorials Center
My learning

Topics

Lesson 69 of 77 ยท Projects

Project: Build a Rate Limiter and LRU Cache

Implement a token bucket, a sliding window rate limiter and an O(1) LRU cache in Node.js with injected clocks and assert-based tests, the way interviewers expect.

Two small components show up in low-level design interviews again and again: a rate limiter (allow at most N requests per time window) and an LRU cache (keep the most recently used items, evict the oldest). Each takes 15 to 30 lines, yet each hides design choices that separate a quick answer from a strong one: how to test code that depends on time, what happens at the edges of a window, and how to get O(1) operations.

In this project you will build three pieces: a token bucket, a sliding-window-log limiter and an LRU cache, all in plain Node.js with no packages. Everything runs on the site. The honest limit: these are single-process, in-memory versions. A real limiter shared by many servers keeps its counters in a shared store such as Redis, which we only discuss. For the distributed story, see System Design: Rate Limiters, Feeds and Chat and Low-Level Design: Parking Lot, Elevator and Cache.

Three building blocks

Token bucket Tokens refill steadily. Bursts allowed.
Sliding window Count requests in the last N seconds.
LRU cache Evict the least recently used key.
1 / 2

Rule one: never read the clock directly

A limiter that calls Date.now() inside its logic is hard to test: you would have to sleep for real seconds. Instead, pass the clock in as a function. Production code passes Date.now; tests pass a fake that you move forward by hand. This single habit makes time-dependent code deterministic, and interviewers notice it.

The token bucket

Picture a bucket that holds up to capacity tokens. It refills at refillPerSecond. Each request takes one token; if the bucket is empty, the request is rejected. The result: a steady average rate with bursts up to the capacity.

You do not need a timer to refill the bucket. Keep the token count and the time of the last update. When a request arrives, compute how much time has passed, add the tokens earned (capped at capacity), then decide. This lazy refill costs O(1) time and O(1) memory per key.

Node.js Token bucket with a fake clock

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or process.stdin), it gets the next line from this box.

The first three requests drain the bucket, the fourth is rejected, half a second later there is only half a token, and at one second a full token has been earned. Each key gets its own bucket, stored in a Map. A real service must also delete idle buckets, or memory grows with every user it has ever seen.

The sliding-window log

A fixed window counter ("100 requests per minute, reset on the minute") is simple but has a flaw: a client can send 100 requests at 12:00:59 and 100 more at 12:01:00, which is 200 requests in two seconds. The sliding window log fixes this by storing the timestamp of every accepted request and counting only those in the last windowMs.

On each call: drop timestamps older than now - windowMs, then allow the request if fewer than limit remain. It is exact, but memory per key is O(limit), so it suits small limits. Larger systems approximate it with a sliding window counter that blends two fixed windows.

Node.js Sliding window log and the fixed-window flaw

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or process.stdin), it gets the next line from this box.

The fixed window lets all six through, because the burst straddles the 1000 ms boundary and lands in two different windows. The sliding log allows only three. log.shift() is O(n) on an array; for a tiny limit that is fine, and you can mention a queue or ring buffer if asked.

Choosing between the limiters

Algorithm Memory per key Bursts Accuracy
Token bucket O(1) Allowed, up to capacity Good average rate
Fixed window O(1) Up to 2x at a boundary Coarse
Sliding window log O(limit) Never above the limit Exact

There is no single winner. Say what the product needs: an API that tolerates short bursts fits a token bucket; a strict "N per minute" contract fits the sliding window. Also decide what to return: HTTP 429 with a Retry-After header is the usual answer.

The LRU cache in O(1)

An LRU cache has a capacity. get(key) returns the value and marks the key as most recently used. put(key, value) inserts or updates, and when the cache is over capacity it evicts the least recently used key. Both operations must be O(1).

The classic answer combines a hash map (find an entry in O(1)) with a doubly linked list (move an entry to the front and drop the tail in O(1)). A JavaScript Map remembers insertion order, so there is a shortcut: to mark a key as recently used, delete it and insert it again; the first key in the map is always the oldest. Show the shortcut, then be ready to explain the linked list version.

Node.js LRU cache with a Map, and the linked-list version

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or process.stdin), it gets the next line from this box.

Trace it: after put a, put b, the order is a, b. get a makes it b, a. put c overflows the capacity of 2 and evicts the oldest, b. Both versions give the same result, and b is gone. In the linked list version, sentinel head and tail nodes remove special cases for an empty list or a single node.

Testing it properly

Tests are part of the answer. Use Node's built-in assert and cover the edges: the first request, the exact limit, rejection, recovery after time passes, separate keys, updating an existing cache key, and eviction order. Assertions that pass silently and a final success line keep the output short.

Node.js Tests with node:assert

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or process.stdin), it gets the next line from this box.

What is real and what is simplified

The algorithms are the real ones; the surroundings are not.

  • One process. Our Map lives in one Node process. With ten servers behind a load balancer, each would allow its own quota. The fix is a shared store (often Redis, with an atomic script or counter) or sticky routing.
  • Concurrency. Node runs JavaScript on one thread, so allow is atomic here. In a language with threads you would add locking, and in a shared store you need atomic operations.
  • Memory growth. Real limiters expire idle keys. A real cache may also add a time-to-live per entry.
  • Fairness and abuse. Keying by IP penalizes people behind one NAT; keying by user needs authentication first.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why is the clock passed into the limiter as a function?

    Injecting the clock removes real sleeping from tests and makes time-dependent behavior repeatable.
  2. 2. A fixed-window limiter allows 100 requests per minute. What is its main weakness?

    Requests at the end of one window and the start of the next are counted separately, so a short burst can double the intended rate.
  3. 3. Which pair of structures gives an LRU cache O(1) get and put?

    The map finds a node in O(1); the doubly linked list moves it to the front and removes the tail in O(1).
  4. 4. How does a token bucket refill without any timer?

    Lazy refill stores the token count and last update time, then adds elapsed time multiplied by the rate, capped at the capacity.
  5. 5. Your limiter works on one server. What changes with ten servers behind a load balancer?

    In-memory state is per process. Without a shared store, each server enforces its own quota, so the real limit is multiplied.

Summary

  • Inject the clock so time-based logic is testable.
  • Token bucket: lazy refill, O(1) per key, allows bursts up to the capacity.
  • Sliding window log: exact, O(limit) memory, fixes the fixed-window boundary burst.
  • LRU cache: hash map plus doubly linked list, or a Map that keeps insertion order.
  • Test edges: first call, exact limit, recovery, independent keys, update and eviction order.
  • State clearly that in-memory limiters are per process; distributed limiters need shared, atomic state.

Next: Project: Design and Prototype a URL Shortener.