Skip to content
Tutorials Center
My learning

Topics

Lesson 56 of 77 ยท DevOps, Tools and System Design

System Design: Rate Limiters, Feeds and Chat

Practice classic system design problems: token bucket rate limiters, consistent hashing, news feed fan-out, cursor pagination, chat delivery and idempotency keys.

Once you know the building blocks, interviews ask you to combine them to solve well-known problems. The same handful of patterns shows up again and again: limit how fast clients may call you, spread data over many machines without chaos, build a feed, page through large results, deliver messages in real time, and survive retries without charging a card twice.

Every pattern here has a runnable Node stand-in (Node 24, single file, no packages). They are small single-process models of the algorithms, so they show the logic, not the distributed behavior of Redis, Kafka or a real cluster. Production architecture and configuration shown in plain blocks is read-only.

Five patterns to know

Rate limiter Protect the service from floods.
Consistent hashing Add servers, move little data.
Feed fan-out Write once, read fast.
Idempotency Retries without double effects.

Plus cursor pagination and chat delivery.

1 / 2

How would you design a rate limiter?

Short answer: Count requests per client (API key, user ID or IP) over time and reject extra ones with 429 Too Many Requests. Decide where it runs (API gateway or middleware), what the key is, which algorithm, and where the counters live. In a multi-server system the counters need to be shared (for example in Redis) and updated atomically, or each server enforces only its own slice of the limit.

The popular algorithms:

  • Fixed window counter: count per minute, reset on the minute. Simple, but a client can send a full quota at the end of one window and again at the start of the next (double the rate around the boundary).
  • Sliding window log: store each request's timestamp; exact, but uses more memory.
  • Sliding window counter: weighted combination of the current and previous window; cheap and close enough.
  • Token bucket: a bucket holds up to capacity tokens and refills at a steady rate. Each request takes one token. It allows bursts up to the capacity while enforcing a long-term average. Most interview answers pick this one.

Good answers also say what the client sees: a 429 status, a Retry-After header, and X-RateLimit-Remaining-style headers, and that failing open or closed when the limiter itself is down is a product decision.

Node.js Token bucket with a simulated 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 sliding window log is the precise alternative. Compare how each handles a boundary burst:

Node.js Fixed window vs sliding window at a boundary

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 consistent hashing and why is it used?

If you spread keys over N servers with hash(key) % N, adding or removing a server changes N and almost every key moves, which empties caches and triggers huge data transfers. Consistent hashing places both servers and keys on a ring (a hash space that wraps around). A key belongs to the first server clockwise from its position. When a server joins or leaves, only the keys in its arc move, roughly 1/N of the data. Real systems add virtual nodes: each server appears at many ring positions, which evens out the load and lets bigger machines take more.

Node.js How many keys move when a server is added?

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.

How would you design a news feed?

A feed shows posts from the people you follow, newest or most relevant first. The core decision is when to do the work:

  • Fan-out on read (pull): store posts by author; when you open your feed, fetch recent posts from everyone you follow and merge them. Writes are cheap, reads are slow, especially if you follow thousands of accounts.
  • Fan-out on write (push): when someone posts, copy the post ID into each follower's precomputed feed list (in a cache or fast store). Reads are a single lookup. But a celebrity with 50 million followers makes one post cause 50 million writes.
  • Hybrid: push for normal accounts, pull for celebrities, and merge at read time. This is the answer interviewers usually hope for.

Other talking points: store only post IDs in feed lists and hydrate content from a cache; feed lists have a bounded length (the latest few hundred); ranking can be added as a separate service; media goes to object storage plus a CDN.

Node.js Push vs pull: counting the work

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.

How should an API paginate large results?

Offset pagination (?page=5000&size=20, SQL OFFSET 100000) is simple but gets slower as the offset grows, because the database still walks past all skipped rows, and results shift when rows are inserted while the user pages (duplicates or skipped items). Cursor (keyset) pagination remembers the last item seen and asks for "the next 20 after this one": WHERE id < :last_id ORDER BY id DESC LIMIT 20. It stays fast with an index and gives stable pages. The trade-off: you cannot jump to "page 50" directly. Return an opaque next_cursor to the client.

SQL
-- Read-only
SELECT id, title FROM posts
WHERE id < 1042            -- cursor from the previous page
ORDER BY id DESC
LIMIT 20;
Node.js Offset vs cursor when new rows arrive

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.

How does a chat system deliver messages?

Chat needs low-latency, two-way communication, so clients keep a WebSocket (or similar persistent connection) to a chat server instead of polling. A typical flow, with the sender and receiver connected to different servers:

sequenceDiagram
    participant A as Alice's client
    participant S1 as Chat server 1
    participant Q as Message bus
    participant S2 as Chat server 2
    participant B as Bob's client
    A->>S1: send "hi" (id 77)
    S1->>Q: store and publish
    Q->>S2: deliver to Bob's server
    S2->>B: push "hi"
    B-->>S2: ack

A message crosses servers through a shared bus; the acknowledgement lets the system know when to stop retrying.

Points to make: a presence/routing service knows which server each user is connected to; messages are persisted first so offline users get them on reconnect; each message has a unique ID and a per-conversation sequence number to order messages and deduplicate retries; group chats fan out like feeds (small groups push, huge channels pull); delivery is at-least-once with client-side dedupe; push notifications cover users who are offline.

What is idempotency and how do idempotency keys work?

An operation is idempotent if doing it many times has the same effect as doing it once. GET, PUT and DELETE are idempotent by definition; POST /payments is not. The problem: a client sends a payment, the connection drops, and the client cannot tell whether it worked, so it retries. Without protection, the customer pays twice.

The fix is an idempotency key: the client generates a unique key per logical action and sends it with the request (often an Idempotency-Key header). The server stores the key with the result of the first execution; a repeat with the same key returns the stored result instead of running again. Details that earn points: store the key and the operation atomically (a unique constraint), handle a second request arriving while the first is still running, expire keys after a while, and reject the same key sent with a different request body.

Node.js A payment endpoint with idempotency keys

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.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why is a token bucket popular for API rate limiting?

    Tokens refill at a fixed rate and are spent per request, so idle clients can burst briefly, but the long-term rate is capped.
  2. 2. You add a fifth server to a cache cluster using hash(key) % N. What happens?

    Changing N changes almost every remainder. Consistent hashing limits the movement to roughly 1/N of the keys.
  3. 3. Which feed strategy suits a user with 50 million followers?

    One post would cause tens of millions of writes with pure push. Hybrid systems pull celebrity posts when a follower reads the feed.
  4. 4. What is the main weakness of offset pagination on a large, changing table?

    The database still scans skipped rows, and inserts between page requests move items across page boundaries. Keyset pagination avoids both.
  5. 5. A client retries POST /payments after a timeout, sending the same Idempotency-Key. What should the server do?

    The key identifies the logical operation. Storing the first result lets retries be safe.

Summary

  • Rate limiters count per client; token bucket allows bursts, sliding windows are precise, fixed windows have boundary spikes. Share counters atomically across servers.
  • Consistent hashing (with virtual nodes) moves only about 1/N of the keys when servers change.
  • Feeds: push for normal accounts, pull for celebrities, hybrid in practice; store IDs and hydrate from a cache.
  • Prefer cursor (keyset) pagination for large or changing data.
  • Chat uses persistent connections, persisted messages with IDs, and at-least-once delivery; idempotency keys make retries safe.

Next: Low-Level Design: Parking Lot, Elevator and Cache.