Systems Design
Systems Design

Arguing a trade-off: feeds, rate limits, retries and back-pressure

Full · ~50 min
After this unit you can
  • Argue a trade-off out loud: name the options, the requirement or number that decides, what you give up, and what would change your mind
  • Choose fan-out on write, on read, or a hybrid for a feed from follower counts and the read:write ratio, with the arithmetic shown
  • Compare token-bucket, fixed-window and sliding-window rate limiters by burst behaviour and memory, and fix a token bucket driven by an injected clock
  • Keep retries from making an outage worse: retry at one layer only, with capped exponential backoff and jitter
  • Apply back-pressure: bound queues and how long work waits in them, shed load early, and answer 429/503 with Retry-After instead of buffering without limit

Read

Simple
1 / 3

The four parts of a trade-off argument

Flag

"It depends" is where a design answer starts, not where it ends. A trade-off argument a reviewer can actually check has four parts:

  1. The options — at least two real ones, named concretely.
  2. The deciding fact — the requirement or number that tips it. Not "scale"; which number.
  3. What you give up — the cost of the option you pick, said out loud before anyone asks.
  4. What would change your mind — the measurement or event at which you'd switch.

A small example — how long should a cached product page live?

Options: a 5-minute TTL, or delete-on-write plus a 1-hour TTL as a safety net. Deciding fact: prices change a few times a day, and the requirement says a shopper may see a price up to a minute old — but never pay a different price than the one shown, which checkout re-reads from the database anyway. Give up: delete-on-write means every price update has to know about the cache — one more thing a new write path can forget. Change my mind: if a second service starts writing prices without going through our code, deletes become unreliable and I'd drop to a short TTL alone.

Notice what isn't in it: "Redis is fast", "best practice", "it scales". Each line is about this system's numbers and requirements, which is what makes it possible to disagree with one line instead of the whole answer.

Part 4 is the one most often skipped, and it's the most useful. It turns a decision into a monitor: "if the hit ratio drops below 90%", "if one account passes 100k followers", "if p99 exceeds 50 ms". A design that names its own reversal point can be revisited calmly instead of in an incident.

Medium
1 / 3

Choosing a feed design by arithmetic

Flag

Assumptions first, every one labelled:

Posts:              10M a day                       (assumption)  →     116 posts/s
Followers per post: 200 on average                  (assumption)
Feed opens:         500M a day                      (assumption)  →   5,800 reads/s
Followed accounts:  200 per user on average         (assumption)

Fan-out on write: every post is copied into 200 timelines.

writes: 116 posts/s × 200 followers   ≈ 23,000 timeline inserts/s
reads:  5,800/s, each one lookup of a prebuilt list

Fan-out on read: every feed open queries 200 accounts' recent posts.

writes: 116 inserts/s
reads:  5,800/s × 200 followed accounts ≈ 1.16 million per-account lookups/s, plus a merge each

Sending those as 200 separate queries is the N+1 shape from the Databases track's N+1 queries unit. Batching them into one WHERE author_id = ANY($1) query saves the round trips, but the database still reads 200 accounts' recent posts for every open.

Write fan-out turns 1.16M lookups/s on the latency-sensitive path (someone is staring at a spinner) into 23k inserts/s on a path that can be asynchronous: the post is accepted immediately and workers fill timelines behind it. That's usually the right trade for a read-heavy feed. Two numbers break it.

Huge accounts. Averages hide the tail. An account with 10 million followers turns one post into 10 million inserts. If the fan-out workers sustain 50,000 inserts/s in total (an assumption — measure yours), the last follower sees the post 200 seconds later, and every other post queues behind it meanwhile. The usual answer is a hybrid: fan out on write for ordinary accounts, but don't fan out posts from accounts above a follower threshold. Instead, at read time, merge in the recent posts of the few huge accounts the reader follows. Most users follow only a handful of huge accounts, so the read-time merge stays small.

Inactive followers. Fan-out on write does work for every follower, including ones who never open the app again. Skipping fan-out to users inactive for a while — and building their timeline on read when they return — removes work nobody would see. Because a timeline is a materialized view, rebuildable from posts and follows (Azure's pattern calls such views disposable), "build it on demand" is always a valid fallback.

Write the decision in the four parts: options push, pull, hybrid; deciding fact reads outnumber posts 50:1 and the follower distribution has a long tail; give up storage for timelines and a second code path for huge accounts; change my mind if fan-out lag at p99 exceeds the freshness requirement, lower the threshold.

Complex
1 / 2

Back-pressure, bounded queues and load shedding

Flag

An overloaded service doesn't just get slower; it gets less useful per request. AWS's Builders' Library article on load shedding separates throughput — requests arriving per second — from goodput: the requests answered without error and fast enough for the client to use the answer. Past an inflection point, latency climbs until it passes the clients' timeout, and from then on the server does full work for answers nobody is waiting for. Throughput stays high; goodput collapses.

Load shedding protects goodput by rejecting the excess early and cheaply, so the requests it accepts finish before their clients give up. A fast 503 — or 429 for a client over its quota — with Retry-After is a feature: the server telling callers to slow down. That signal travelling upstream is back-pressure, and it beats silently queueing their work.

Queues are where overload hides. Every server has some — a framework's executor queue, the operating system's socket buffers, a load balancer's surge queue — and an unbounded one converts overload into latency until everything times out. The article's rules:

  • Bound the queue, and bound the time a request may wait in it. On dequeue, check its age and drop it if its client has surely given up; working on it spends capacity the next request needs.
  • Propagate deadlines. If the client says how long it will wait, each hop can pass the remaining time along and skip work that can't finish in time.
  • Fail fast rather than queue at the edge. AWS notes that its Classic Load Balancer queued surges while the Application Load Balancer rejects excess traffic.

Asynchronous systems get a longer-lasting version. AWS's article on queue backlogs describes bimodal behaviour: with no backlog a queue is fast; once arrivals outrun processing, every message waits behind the backlog. And recovery is slower than intuition says:

arrivals 1,000/s; consumers handle 1,200/s; consumers down for 1 hour
backlog:     1,000/s × 3,600 s                      = 3.6 million messages
spare rate:  1,200 − 1,000 (arrivals don't stop)    = 200/s
drain time:  3,600,000 / 200                        = 18,000 s = 5 hours

A one-hour outage became six hours of late processing. The article's rule of thumb agrees: recovering from an hour-long outage takes double the normal capacity for another hour. Its defences: measure the age of messages, not just the count; when users want fresh data, work newest-first or move old messages to a separate backlog queue; and throttle each tenant, so one noisy producer can't build a backlog that everyone waits behind.

Quiz

In a review, a teammate argues: "Let's put sessions in Redis — it's fast and it scales." What's missing from that as a trade-off argument?

Flag

Feed opens outnumber posts about 50 to 1, and most accounts have a few hundred followers. Which feed design fits?

Flag

With pure fan-out on write, one account with 30 million followers posts. What goes wrong, and what's the usual fix?

Flag

A public API should let a client send 20 requests at once after being idle, but hold it to 10 per second on average. Which limiter states exactly that?

Flag

Four app servers share one token bucket per client in Redis. Each request reads the bucket with one command, refills and decides in Node, then writes the new token count back with another. Under load, a client with 1 token left gets several concurrent requests allowed. Why, and what's the fix?

Flag

A request passes through 4 service layers to a database, and each layer makes up to 3 attempts. The database starts timing out under load. What's the worst case, and the fix?

Flag

1,000 clients lose their connection to a service at the same instant. Each retries with exponential backoff — wait 100 ms, then 200 ms, then 400 ms — and no jitter. What does the recovering service see?

Flag

Under overload, a service's in-memory request queue grows to 60 seconds of work, while its clients time out after 5 seconds. What's the best change?

Flag

Fill in the blank

Refill a token bucket for the time that passed, keeping the fraction but never exceeding the capacity.

Flag
tokens = Math.(capacity, tokens + elapsedSeconds * refillPerSecond);

A request was denied. Report how long until the bucket holds one whole token.

Flag
retryAfterMs = Math.ceil((( - tokens) / refillPerSecond) * 1000);

Deny a request over its rate limit, and tell the client when to come back (in seconds).

Flag
HTTP/1.1  Too Many Requests
: 2
Content-Type: application/json

Wait before retry number attempt (0, 1, 2, …): exponential growth, capped, then randomised.

Flag
const delayMs = Math.random() * Math.min(capMs, baseMs * 2 ** );

Predict the output

// Fixed window: 100 requests per calendar minute, one counter per window.
const LIMIT = 100, WINDOW_MS = 60_000;
const counters = new Map<string, number>();

function allow(key: string, nowMs: number): boolean {
  const windowKey = `${key}:${Math.floor(nowMs / WINDOW_MS)}`;
  const count = (counters.get(windowKey) ?? 0) + 1;
  counters.set(windowKey, count);
  return count <= LIMIT;
}

let allowed = 0;
for (let i = 0; i < 100; i++) if (allow("u", 59_900)) allowed++; // 0.1 s before the minute ends
for (let i = 0; i < 100; i++) if (allow("u", 60_100)) allowed++; // 0.1 s after
console.log(allowed);
Flag
// Estimate — pure fan-out on write
followers_of_this_account = 10_000_000
fan_out_inserts_per_second = 50_000   // total worker throughput (assumption)

seconds_until_the_last_follower_sees_the_post = ?
Flag
// Estimate — a queue whose consumers were down for an hour
arrivals_per_second  = 1_000
consumer_capacity    = 1_200   // messages/s when running
outage_seconds       = 3_600

hours_to_drain_the_backlog_after_consumers_return = ?
Flag

Challenge

Fix a token-bucket rate limiter

Flag

rate-limiter.ts is a token-bucket limiter of the kind an API gateway puts in front of a service. Each client key gets a bucket that holds up to capacity tokens and refills continuously at refillPerSecond. A request takes one token; when there isn't a whole token, it's denied with a retryAfterMs the server can send back as 429 Too Many Requests plus a Retry-After header. So capacity is the largest burst a client can send at once, and refillPerSecond is the average rate it can keep up forever.

The clock is injected: now() returns milliseconds, and the tests replace it with a fake clock they advance by hand. Nothing sleeps, so the results never depend on how fast the test machine is — the same seam you'd use for anything time-based.

The limiter works for a single client in a quick demo and is wrong in four ways:

  1. One bucket for everyone — the key is ignored, so one noisy client exhausts the bucket and every other client is denied too.
  2. No cap — refill adds tokens for all the elapsed time without stopping at capacity, so a client that was idle for an hour can fire thousands of requests at once.
  3. Lost fractions — each call floors the refill to whole tokens and then resets the refill clock, throwing the fraction away. A client that polls every 300 ms at 1 token/s earns 0.3 tokens per call, floors it to 0, and never gets a token again. Keeping only whole tokens some of the time isn't enough either: drop 0.2 of a token every 1.2 s and the client gets five requests where it earned six.
  4. Wrong wait — retryAfterMs is the time until the bucket is full, not until the next token, so well-behaved clients wait far longer than they need to.

Your task

Edit rate-limiter.ts so the tests pass:

  • A new key can send capacity requests at once; the next one is denied
  • Each key has its own bucket — one busy key never denies another
  • A bucket never holds more than capacity tokens, however long the key sits idle
  • Partial tokens carry over: a client polling every 300 ms at 1 token/s still averages one request per second
  • A denied request reports retryAfterMs as the time until the next whole token, counting any partial token already refilled (and 0 when allowed)
  • A denied request doesn't spend a token

Loading the in-browser editor…

Further reading