Case Studies: Core Services

Requirements

Ask before drawing. These are the answers this design assumes; say them out loud and write them in a corner of the board.

Functional:

• Create a short link for a long URL; optionally with a custom alias (sho.rt/spring-sale) and an expiry date.
• Redirect: opening the short link sends the browser to the long URL.
• Click analytics for the link's owner: clicks per day, referrers, countries. Minutes of delay are fine.
• Owners can disable or delete a link (abuse reports need this too).

Non-functional:

• Redirects are the product. A broken short link is broken in every email, tweet and printed poster that contains it, so the redirect path targets 99.99% availability (about 52 minutes of downtime a year, see Availability, SLAs, SLOs and SLIs) and a p99 well under 50 ms at the server.
• A short code must never point to the wrong URL: durability and uniqueness matter more than creation latency.
• Codes should not be enumerable (people shorten private document links).
• Scale: design for 100 million new links a day. Bitly, the best-known shortener, said in a February 2026 press release that it handles "hundreds of millions" of links and QR codes a month, so 100 million a day (3 billion a month) is roughly ten times that, a comfortable interview target.

Out of scope unless asked: user accounts and billing, QR codes, link-in-bio pages, A/B redirects.

Estimates

The assumptions: 100M new links a day, 10 redirects per link created, a peak of 3× the average, 500 bytes per stored link (code, long URL averaging a few hundred bytes, owner, timestamps, indexes), links kept 5 years, and a cache holding the hottest 20% of the last 30 days of links.

// Assumptions (stated in the text): 100M new links a day, 10 redirects per link created,
// peak = 3x average, 500 bytes per stored link, keep links 5 years, the cache holds 20% of the last 30 days of links.
const DAY = 86_400;
const writesPerDay = 100e6;
const readsPerDay = writesPerDay * 10;
const peak = 3;
const bytesPerLink = 500;
const years = 5;

const writeQps = writesPerDay / DAY;
const readQps = readsPerDay / DAY;
const links = writesPerDay * 365 * years;
const storageTB = (links * bytesPerLink) / 1e12;
const fmt = (n) => Math.round(n).toLocaleString("en-US");

console.log(`writes: ${fmt(writeQps)}/s average, ${fmt(writeQps * peak)}/s peak`);
console.log(`redirects: ${fmt(readQps)}/s average, ${fmt(readQps * peak)}/s peak`);
console.log(`links after ${years} years: ${(links / 1e9).toFixed(1)} billion`);
console.log(`storage: ${storageTB.toFixed(1)} TB (x3 replicas = ${(storageTB * 3).toFixed(0)} TB)`);
for (const len of [6, 7, 8]) {
  const space = 62 ** len;
  const used = links / space;
  console.log(`${len} chars: ${(space / 1e9).toFixed(1)}B codes, ${used > 1 ? "too few" : `${(used * 100).toFixed(1)}% used after ${years} years`}`);
}
// Cache: the hottest 20% of the last 30 days of links (older links are rarely clicked).
const hotLinks = writesPerDay * 30 * 0.2;
console.log(`cache for ~${(hotLinks / 1e6).toFixed(0)}M hot links: ${((hotLinks * bytesPerLink) / 1e9).toFixed(0)} GB`);
// Egress: a redirect response is ~500 bytes of headers.
console.log(`redirect egress at peak: ${((readQps * peak * 500 * 8) / 1e6).toFixed(0)} Mbit/s`);

writes: 1,157/s average, 3,472/s peak
redirects: 11,574/s average, 34,722/s peak
links after 5 years: 182.5 billion
storage: 91.3 TB (x3 replicas = 274 TB)
6 chars: 56.8B codes, too few
7 chars: 3521.6B codes, 5.2% used after 5 years
8 chars: 218340.1B codes, 0.1% used after 5 years
cache for ~600M hot links: 300 GB
redirect egress at peak: 139 Mbit/s

API

Three public endpoints and one redirect. Creation is a normal JSON API; the redirect is a bare GET on the short domain so it works from any browser.

POST /api/v1/links
  Idempotency-Key: 6f1c…            (a retried create must not mint a second code)
  { "url": "https://shop.example.com/…", "alias": "spring-sale", "expiresAt": "2026-12-31T00:00:00Z" }
  -> 201 Created  { "code": "m0JvKvd", "shortUrl": "https://sho.rt/m0JvKvd", "expiresAt": "…" }
  -> 409 Conflict if the alias is taken; 400 if the URL is malformed or on a blocklist

GET /{code}
  -> 302 Found   Location: https://shop.example.com/…   Cache-Control: private, max-age=90
  -> 404 Not Found if unknown; 410 Gone if disabled or expired

GET    /api/v1/links/{code}/stats?from=2026-10-01&to=2026-10-24   -> clicks per day, top referrers, countries
DELETE /api/v1/links/{code}                                        -> 204 (soft delete: the code is never reused)

The Idempotency-Key header makes a timed-out create safe to retry, as explained in Idempotency keys for APIs. The choice between 301 and 302 on the redirect is one of the deep dives below, because it decides whether you can count clicks at all.

Data model

The access pattern is almost entirely point lookups by code: "give me the URL for m0JvKvd". There are no joins on the hot path and no range scans. That favours a key-value or wide-column store partitioned by code (DynamoDB, Cassandra) or a relational database sharded by a hash of the code. Here is the logical schema in SQL:

CREATE TABLE links (
  code        varchar(16) PRIMARY KEY,      -- 7 chars generated, longer for custom aliases
  long_url    text        NOT NULL,
  owner_id    bigint,                        -- null for anonymous links
  created_at  timestamptz NOT NULL DEFAULT now(),
  expires_at  timestamptz,
  status      smallint    NOT NULL DEFAULT 0 -- 0 active, 1 disabled, 2 deleted
);
CREATE INDEX links_by_owner ON links (owner_id, created_at DESC);  -- "my links" page

CREATE TABLE id_ranges (                     -- the range allocator: one row
  name     text PRIMARY KEY,
  next_id  bigint NOT NULL
);
-- grab 1,000 ids atomically:
-- UPDATE id_ranges SET next_id = next_id + 1000 WHERE name = 'links' RETURNING next_id - 1000;

CREATE TABLE clicks_daily (                  -- written by the analytics pipeline, not the redirect path
  code    varchar(16),
  day     date,
  clicks  bigint NOT NULL,
  PRIMARY KEY (code, day)
);

Two details are worth saying. The links_by_owner index is a secondary index in a sharded system: if links is sharded by code, the owner's links are spread across every shard, so either keep a separate owner-keyed table or accept scatter-gather for that rare page (see Secondary indexes in a sharded system). And deleted codes are never reused: a reused code would silently send old links in old emails to someone else's page.

High-level design

Walk the board in this order:

1. Create: the client posts the long URL. The create service validates it (scheme, length, blocklist), takes the next id from its in-memory range (grabbing a new range from the allocator every 1,000 links), scrambles and encodes it, and writes code → long_url to the links store with a conditional "insert if absent". It returns the short URL. With a custom alias, the code is the alias and the conditional insert is what detects "taken".
2. Redirect: the browser requests GET /m0JvKvd. The redirect service looks the code up in Redis; on a hit (most requests, see below) it answers 302 immediately. On a miss it reads the links store, fills the cache, and answers.
3. Analytics: after answering, the redirect service publishes a click event (code, time, referrer, country from the IP, user agent) to Kafka without waiting for it. A stream job aggregates clicks per code per day into clicks_daily; raw events go to object storage for anything else.
4. Both services are stateless, so they scale horizontally behind the load balancer; all state lives in the allocator, the cache, the store and Kafka.

There are three families of approach. The model above ran two of them; this table puts all three next to each other.

The counter wins for this design because the numbers say so: at 1,157 writes a second, a check-and-retry read on every write is real load on the store, and it gets worse as the store fills; the counter's coordination cost is one allocator call per 1,000 links, about 1.2 allocator calls a second at average load. Ranges also survive server crashes cheaply: if app-2 dies holding ids 1,001–2,000, those unused ids are simply skipped. Out of 3.5 trillion codes, losing a few thousand per crash doesn't matter.

The allocator is now the thing to make reliable. It's one row, so a single strongly consistent database (or a ZooKeeper/etcd counter) is enough; give it a replica with automatic failover and make app servers grab their next range when they are 80% through the current one, so a short allocator outage never blocks creation. Unique ID generation compares this "ticket server" idea with Snowflake-style IDs, which avoid even the allocator by embedding the machine id in the number. Snowflake IDs are 64-bit and time-ordered, which would make codes 11 base62 characters long, so ranges suit a shortener better.

A redirect is a key lookup, so a cache in front of the store is obvious; the real question is how much traffic a cache of a given size absorbs. Click traffic is heavily skewed: a link in a viral post gets millions of clicks, most links get a handful. The usual model for that is a Zipf distribution, where the k-th most popular item gets traffic proportional to 1/k^s. The exponent for your traffic is something you'd measure; here are two plausible values (an assumption, not a measured property of any real shortener):

// How big must the redirect cache be? Clicks follow a power law: a few links get most of the traffic.
// Model: 1,000,000 links, clicks drawn from a Zipf distribution (exponent s), LRU caches of several sizes.
// Seeded PRNG (mulberry32), so every run prints the same numbers.
function mulberry32(a) {
  return () => {
    a |= 0; a = (a + 0x6d2b79f5) | 0;
    let t = Math.imul(a ^ (a >>> 15), 1 | a);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}
const LINKS = 1_000_000, CLICKS = 3_000_000;

function zipfSampler(s, rand) {
  const cdf = new Float64Array(LINKS);
  let sum = 0;
  for (let i = 0; i < LINKS; i++) cdf[i] = sum += 1 / (i + 1) ** s;
  return () => { // binary search for the first rank whose cumulative weight passes a uniform draw
    const u = rand() * sum;
    let lo = 0, hi = LINKS - 1;
    while (lo < hi) { const mid = (lo + hi) >> 1; if (cdf[mid] < u) lo = mid + 1; else hi = mid; }
    return lo;
  };
}

function hitRate(capacity, s) {
  const next = zipfSampler(s, mulberry32(42));
  // LRU as a doubly linked list over typed arrays (link ids are 0..LINKS-1; LINKS is the list's head sentinel).
  const prev = new Int32Array(LINKS + 1).fill(-1), nxt = new Int32Array(LINKS + 1).fill(-1);
  const H = LINKS; prev[H] = nxt[H] = H;
  const unlink = (x) => { nxt[prev[x]] = nxt[x]; prev[nxt[x]] = prev[x]; };
  const toFront = (x) => { prev[x] = H; nxt[x] = nxt[H]; prev[nxt[H]] = x; nxt[H] = x; };
  let size = 0, hits = 0;
  for (let i = 0; i < CLICKS; i++) {
    const link = next();
    if (prev[link] !== -1) { hits++; unlink(link); }
    else if (size >= capacity) { const old = prev[H]; unlink(old); prev[old] = -1; } // evict the tail
    else size++;
    toFront(link);
  }
  return hits / CLICKS;
}

for (const s of [0.8, 1.0]) {
  const row = [0.001, 0.01, 0.05, 0.2].map((f) => `${(f * 100).toString().padStart(4)}% -> ${(hitRate(LINKS * f, s) * 100).toFixed(1)}%`);
  console.log(`s=${s.toFixed(1)}  cache size -> hit rate:  ${row.join("   ")}`);
}

s=0.8  cache size -> hit rate:   0.1% -> 10.0%      1% -> 23.2%      5% -> 38.9%     20% -> 59.0%
s=1.0  cache size -> hit rate:   0.1% -> 40.3%      1% -> 58.5%      5% -> 71.6%     20% -> 82.2%

Three more things belong on the redirect path:

• Negative caching. Bots probe random codes. Cache "not found" for a short time (say 60 s) too, or every probe goes to the store. A Bloom filter of existing codes in front of the store is the other way to stop them (see Bloom filters).
• Hot links. A code going viral is a hot key: tens of thousands of hits a second on one Redis shard. A small in-process cache in each redirect server (a few thousand entries, a few seconds of TTL) absorbs it; Hot keys and cache stampedes covers the options.
• Edge caching. A CDN could answer redirects itself if the response were cacheable by shared caches. That is the strongest latency win and the biggest analytics loss (the clicks it answers never reach you, unless you process the CDN's logs), so this design sends Cache-Control: private: the browser may reuse the redirect for 90 seconds, shared caches may not. The same trade-off decides the status code.

301 or 302? RFC 9110 (the HTTP semantics standard, 2022) defines 301 Moved Permanently as heuristically cacheable: without explicit cache headers, browsers and proxies may store it and send later clicks straight to the long URL without asking you. 302 Found means "temporarily elsewhere" and isn't cached unless you say so. So:

Without explicit cache headers, the two behave like this:

In practice the explicit Cache-Control header matters more than the status code. Bitly, which sells click analytics, answers 301 with Cache-Control: private, max-age=90, and TinyURL answers 301 with Cache-Control: no-store (both checked with curl -I, October 2026): the header caps how long a browser may reuse the redirect, so the "permanent" status costs them little. This design answers 302 with the same short private max-age: the header does the real work, and 302 means a cache that ignores or loses the header still won't treat the link as permanent. The ability to disable a malicious link quickly matters more than the saved requests. (307/308 are the versions that forbid changing POST to GET; for plain link clicks, which are GETs, they behave the same as 302/301.)

Counting clicks synchronously (UPDATE … SET clicks = clicks + 1 on every redirect) would turn a 35,000-reads-a-second path into 35,000 writes a second on a handful of hot rows. Instead the redirect service publishes an event and moves on, which is the Pub/sub and fan-out pattern:

• Events go to a Kafka topic partitioned by code, so one consumer sees all clicks for a code in order. The catch is the viral link again: every click on it lands on one partition, so one broker and one consumer take tens of thousands of events a second while the rest idle. Click counts don't need per-code order, so the fixes are to partition by a hash of the event id (or randomly) and aggregate per code downstream (each consumer keeps partial counts, and the clicks_daily upsert adds them), or to pre-aggregate at the producer: each redirect server counts clicks per code in memory and publishes one "code, +n" event every few seconds.
• A stream job (Flink, Kafka Streams, or a plain consumer) keeps per-code counters in memory and flushes clicks_daily every minute: 35,000 events a second (2.1 million a minute) become one upsert per code clicked in that minute, so a viral link's thousands of clicks cost one write, not thousands. (The long tail of links clicked once or twice still costs about one write per click; batch those upserts.)
• "Unique visitors" per link is a count-distinct problem; a HyperLogLog per code per day estimates it with a standard error of 0.81% in at most 12 KB (Redis's implementation) (see HyperLogLog and count-min sketch).
• If Kafka is down, the redirect still works; the service buffers events in memory, can spool them to local disk to ride out a longer outage and replay them afterwards, and drops them only when that fills up. Losing some clicks is acceptable by the requirements; failing redirects is not. Say that priority out loud.

• Custom aliases share the code key space. The create service does a conditional insert of the alias; a clash returns 409. Reserve aliases that look like generated codes (exactly 7 base62 characters) for the generator, or a user could squat a future code.
• Expiry is checked on read (expires_at < now() → 410 Gone), and a background job deletes expired rows lazily. The cache entry's TTL should never outlive the link's expiry.
• Abuse. Shorteners hide phishing links. Check new URLs against a blocklist or a reputation service at creation time and re-scan popular links in the background; a disabled link answers 410 within the cache's TTL, which is another reason to keep TTLs short.
• Same URL twice. With counter ranges, two users shortening the same URL get two codes. That's usually what you want (separate analytics per owner). If you want dedup, keep a hash(long_url, owner) → code table and look it up first.

Trade-offs and what to say

Trade-offs to name before the interviewer does:

• Counter vs hash: the counter needs a small, highly available allocator; the hash needs a check on every write and grows more collisions over time. Ranges make the allocator cheap.
• 302 vs 301: you pay for every repeat click in exchange for accurate analytics and instant link changes.
• Consistency: a just-created link must redirect at once. Write to the store first, then return; the cache is filled on the first read, so for a generated code there's no stale entry to invalidate. A custom alias is the exception: if someone (or a bot) opened sho.rt/spring-sale before it existed, the cache holds a 60-second "not found" entry for it, so creating the alias must also delete that negative entry, or the new link answers 404 for up to a minute. Cross-region, either route creates to one home region and replicate (a link created in Europe may take a second to work in Asia), or allocate disjoint id ranges per region so each region creates locally.
• What breaks first at 10× scale: the hot-key path (viral links) and the cache size, not the database writes.

Requirements

Functional:

• Limit requests per key: API key, user id, IP address, or a combination (apiKey + endpoint).
• Several rules can apply to one request: a burst rule (20 per second) and a quota rule (10,000 per day). The request passes only if every rule passes.
• Rules are configured without a deploy and take effect within seconds.
• Rejected requests get 429 with Retry-After (429 comes from RFC 6585, which says the response may include Retry-After, a header defined in RFC 9110 as seconds or a date), and every response tells the client where it stands.

Non-functional:

• Low added latency: the limiter is on every request, so its p99 budget is a millisecond or less.
• Highly available: if the limiter's store is down, the API must not go down with it. Most rules fail open (allow) with a local fallback limit; security rules such as login attempts may fail closed.
• Approximate is acceptable for quota rules (a few percent over for a few seconds); exact for security rules.
• Scale: 1 million requests a second at peak across 200 gateway nodes, 5 million distinct callers active in any minute.

Real products show what "limits" look like: GitHub's REST API allows 5,000 requests an hour for an authenticated user and 60 an hour per IP unauthenticated, and Stripe's API allows 100 requests a second in live mode by default (both from their API docs, checked October 2026).

Estimates

Assumptions: 1M requests/s at peak through 200 gateways; 5M callers active in a minute; one sliding-window rule per caller, which is two counters (this window and the previous one); about 100 bytes per Redis counter including the key and Redis's own overhead; about 100,000 simple operations a second per Redis shard (a rule of thumb: the Redis docs' own redis-benchmark example shows about 180,000 SETs a second on their test machine, and real traffic with Lua scripts and network round trips gets less); a 1-second sync; and one attacker sending 20,000 requests a second.

// Assumptions (stated in the text): 1M requests/s at peak through 200 gateway nodes; 5M distinct callers
// active in any minute; one sliding-window rule per caller (2 counters: this window and the last);
// ~100 bytes per Redis counter including key and overhead; ~100k simple ops/s per Redis shard (rule of thumb);
// sync interval 1 s; an attacker sending 20,000 requests/s.
const peakRps = 1_000_000, gateways = 200, activeCallers = 5_000_000;
const bytesPerCounter = 100, opsPerShard = 100_000, syncSeconds = 1, attackerRps = 20_000;
const fmt = (n) => Math.round(n).toLocaleString("en-US");

const memoryGB = (activeCallers * 2 * bytesPerCounter) / 1e9;
console.log(`counter memory: ${memoryGB.toFixed(1)} GB (fits one Redis node; shard for throughput, not size)`);

// Exact: one atomic Lua call per request.
const exactOps = peakRps;
console.log(`exact: ${fmt(exactOps)} Redis calls/s -> ${Math.ceil(exactOps / opsPerShard)} shards, +1 network hop on every request`);

// Synced: each gateway sends one pipelined batch per second holding an INCRBY per caller it saw.
const trips = gateways / syncSeconds;
console.log(`synced: ${fmt(trips)} pipelined trips/s, 0 hops on the request path`);
// Worst case: every request a gateway saw in the interval came from a different caller.
const perGateway = (peakRps / gateways) * syncSeconds;
const worstCommands = (gateways * perGateway) / syncSeconds;
console.log(`synced worst case: ${fmt(perGateway)} distinct callers per gateway -> ${fmt(worstCommands)} INCRBY/s + reads of totals, pipelined`);

// The attacker is where the two differ most.
const attackerExact = attackerRps;
const attackerSynced = Math.min(gateways, attackerRps) / syncSeconds;
console.log(`attacker at ${fmt(attackerRps)} req/s costs ${fmt(attackerExact)} ops/s exact vs ${fmt(attackerSynced)} ops/s synced`);

counter memory: 1.0 GB (fits one Redis node; shard for throughput, not size)
exact: 1,000,000 Redis calls/s -> 10 shards, +1 network hop on every request
synced: 200 pipelined trips/s, 0 hops on the request path
synced worst case: 5,000 distinct callers per gateway -> 1,000,000 INCRBY/s + reads of totals, pipelined
attacker at 20,000 req/s costs 20,000 ops/s exact vs 200 ops/s synced

API

The limiter has two interfaces: the internal call the gateway makes per request, and what the client sees.

check(key = "apikey:9f2c", rules = ["burst", "daily"], cost = 1)
  -> { allowed: false, rule: "burst", limit: 20, remaining: 0, resetMs: 640 }

HTTP/1.1 200 OK
RateLimit-Policy: "burst";q=20;w=1, "daily";q=10000;w=86400
RateLimit: "burst";r=13;t=1

HTTP/1.1 429 Too Many Requests
Retry-After: 1
RateLimit: "burst";r=0;t=1
Content-Type: application/problem+json
{ "type": "https://api.example.com/problems/rate-limited", "title": "Too many requests", "rule": "burst" }

RateLimit-Policy and RateLimit come from the IETF draft "RateLimit header fields for HTTP" (draft-ietf-httpapi-ratelimit-headers-11, May 2026). As of October 2026 it is still an Internet-Draft, not an RFC, so many APIs send their own X-RateLimit-Limit, X-RateLimit-Remaining and X-RateLimit-Reset instead (GitHub does). Retry-After and 429 are standard. The cost parameter lets an expensive endpoint (a search, an export) spend more than one unit.

Data model

• Counters (Redis): rl:{apikey:9f2c}:burst:<window number> → integer, with a TTL of two windows so old windows clean themselves up. The braces are a Redis Cluster hash tag: only the part inside {} is hashed, so all of a caller's counters land on the same shard and one Lua script can touch them atomically.
• Rules (a config store or a small database, cached in every gateway): { id: "burst", match: { tier: "free" }, limit: 20, windowSec: 1, algorithm: "sliding-window", mode: "approximate", failMode: "open" }.
• Overrides: per-key exceptions (apikey:9f2c gets 10× for a migration weekend), in the same rules store.
• Nothing is durable in the counter store: losing it resets everyone's counts, which for rate limiting is harmless. So no replication-for-durability, just enough replicas for availability.

High-level design

1. Where it runs. In the API gateway (or a sidecar next to each service), so rejected requests never reach the services and every service gets limiting without writing code. A limiter inside each service works too, but every team has to adopt it, and abusive traffic has already reached them.
2. Per request: the gateway identifies the caller (API key from the header, user from the token, else the IP), finds the matching rules in its local rules cache, and checks each rule against its local view of the counts. Pass: forward and add the RateLimit headers. Fail: answer 429 itself.
3. Every second: each gateway sends one pipelined batch to the counter store: INCRBY its pending counts per key, read back the global totals for the keys it has seen recently. Its local view is now at most one second stale.
4. Exact rules (login attempts, OTP sends, money-moving endpoints) skip the local view and run the Lua script below against the store, synchronously. They are a small share of traffic, so their cost is small.
5. Rules change in the config store and are pushed to gateways (or polled every few seconds); a gateway that can't reach the config store keeps the last rules it had.

When the count must be exact, the check and the increment must happen atomically, or two gateways can both read "99" and both admit request 100. In Redis the standard way is a Lua script, which Redis runs without interleaving other commands. This is the sliding-window counter from the model, written for Redis:

-- KEYS[1] = this window's counter, KEYS[2] = the previous window's (same {hash tag}, so same cluster slot)
-- ARGV[1] = now in ms, ARGV[2] = window in ms, ARGV[3] = limit
local now, window, limit = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3])
local current = tonumber(redis.call('GET', KEYS[1]) or '0')
local previous = tonumber(redis.call('GET', KEYS[2]) or '0')
local overlap = 1 - (now % window) / window
local estimate = previous * overlap + current
if estimate >= limit then
  return {0, limit - math.ceil(estimate)}
end
redis.call('INCR', KEYS[1])
redis.call('PEXPIRE', KEYS[1], window * 2)
return {1, limit - math.ceil(estimate) - 1}

It was run against Redis 8.10.2 (in Docker) with this script: 100 requests at t = 1 s, a 101st, then 61 more at t = 90 s. Timestamps are passed in, not read from a clock, so the run is reproducible:

SCRIPT=$(cat sliding-window.lua)
check() { # check <now ms>: this window's key, the previous window's key, now, window, limit
  local w=$(( $1 / 60000 ))
  redis-cli EVAL "$SCRIPT" 2 "rl:{u42}:$w" "rl:{u42}:$((w - 1))" "$1" 60000 100 | paste -sd' ' -
}
for i in $(seq 100); do check 1000 > /dev/null; done
echo "101st request at t=1s:  $(check 1000)"
echo "first request at t=90s: $(check 90000)"
ok=0; for i in $(seq 60); do [[ $(check 90000) == 1* ]] && ok=$((ok + 1)); done
echo "60 more at t=90s, allowed: $ok"
echo "TTL of window 1 (ms): $(redis-cli PTTL 'rl:{u42}:1')"

101st request at t=1s:  0 0
first request at t=90s: 1 49
60 more at t=90s, allowed: 49
TTL of window 1 (ms): 119974

The model at the top is this design's default path. Three refinements make it production-grade:

• Sync what changed, read back what you use. A gateway only syncs keys it saw since the last sync, so a gateway serving 5,000 distinct callers a second sends a 5,000-command pipeline once a second, not 5 million.
• Split the limit for very hot keys. For a caller sending 20,000 requests a second, even a 1-second staleness lets through thousands of extra requests. A gateway can give itself a local share (limit / gateways, adjusted by how much of that caller's traffic it actually sees) and refuse locally once the share is used, without waiting for the sync.
• Cache rejections. Once a caller is over a fixed one-second limit, the gateway knows they will stay over for the rest of that second; it rejects them from memory without evaluating the rules again. That saves gateway CPU. The store cost is already capped by batching: each gateway sends at most one INCRBY per key per sync, however many requests that key made, which is what makes the attacker line in the estimates cost 200 ops/s rather than 20,000.

Rate limiting algorithms runs all of these side by side and shows the fixed window's boundary burst.

Trade-offs and what to say

• Accuracy vs cost: the sync interval is the dial. Name it, and say which rules get which setting.
• Fail open vs fail closed: an outage of the limiter must not become an outage of the API, except where allowing is the bigger risk.
• Where to run it: gateway (central, consistent, one place to configure) vs in each service (closer to the business rules, e.g. "per tenant per report"). Many systems do both: coarse limits at the gateway, fine ones in the service.
• What the client sees matters as much as the algorithm: Retry-After stops well-behaved clients from hammering you, and clients should retry with jittered backoff (see Retries, dead-letter queues and poison messages).

Requirements

Functional:

• put(key, value), get(key), delete(key). Keys up to a few hundred bytes, values up to about 1 MB (larger blobs belong in object storage).
• No transactions across keys, no range scans (a sorted, range-partitioned store is a different design).

Non-functional:

• Always writable: a write must succeed as long as any few nodes are up, even during network partitions. Conflicts are acceptable and resolved later.
• Tunable consistency per request: the caller can ask for stronger reads (R = N) when it needs them.
• Low, predictable latency: p99 single-digit milliseconds within a region. The Dynamo paper (Amazon, SOSP 2007) framed its targets the same way, as a 99.9th-percentile SLA, giving the example of answering within 300 ms for 99.9% of requests at 500 requests a second.
• Durable: three replicas, no single point of failure, survive a whole node or rack.
• Incremental scale: add a node and only its share of keys moves.
• Scale: 10 billion keys, about 1 KB each, 300,000 reads and 100,000 writes a second at peak.

Estimates

Assumptions: 10 billion items of about 1 KB (key plus value plus metadata); N = 3, W = 2, R = 2; nodes with 4 TB of SSD filled to at most 50% (an LSM store needs free space for compaction, and survivors must absorb a dead node's data); 300k reads and 100k writes a second at peak; about 20,000 replica operations a second per node (a rule of thumb for an SSD-backed LSM node; measure yours).

// Assumptions (stated in the text): 10 billion keys, 1 KB average value + key, N=3 replicas,
// nodes with 4 TB of SSD filled to at most 50% (room for compaction and for taking over a dead node's data),
// 300k reads/s and 100k writes/s at peak, W=2 and R=2, ~20k replica operations/s per node (rule of thumb).
const keys = 10e9, bytesPerItem = 1_000, N = 3, W = 2, R = 2;
const diskTB = 4, fill = 0.5, peakReads = 300_000, peakWrites = 100_000, opsPerNode = 20_000;

const rawTB = (keys * bytesPerItem) / 1e12;
const storedTB = rawTB * N;
const nodesForDisk = Math.ceil(storedTB / (diskTB * fill));
// Every write lands on all N replicas (W only decides how many we wait for). Every read is also sent
// to all N (the coordinator answers from the first R replies), so it costs N replica reads, not R.
const replicaOps = peakWrites * N + peakReads * N;
const nodesForOps = Math.ceil(replicaOps / opsPerNode);

console.log(`data: ${rawTB} TB raw, ${storedTB} TB with ${N} replicas`);
console.log(`nodes for disk: ${nodesForDisk} (${diskTB} TB each, filled to ${fill * 100}%)`);
console.log(`replica operations at peak: ${replicaOps.toLocaleString("en-US")}/s -> ${nodesForOps} nodes`);
const nodes = Math.max(nodesForDisk, nodesForOps);
console.log(`cluster: ${nodes} nodes; each holds ~${((storedTB / nodes) * 1000).toFixed(0)} GB`);
// When one node dies, its data is re-replicated from the others. Best case: every peer sends at once
// with 200 MB/s to spare, to many receivers. Then with each sender throttled to 24 MiB/s.
const perNodeGB = (storedTB / nodes) * 1000;
const rebuildMin = perNodeGB / (0.2 * (nodes - 1)) / 60;
console.log(`rebuild of one dead node, best case, ${nodes - 1} peers at 200 MB/s each: ~${rebuildMin.toFixed(1)} min`);
const throttledMin = perNodeGB / (((24 * 2 ** 20) / 1e9) * (nodes - 1)) / 60;
console.log(`same rebuild, each peer throttled to 24 MiB/s: ~${throttledMin.toFixed(1)} min`);

data: 10 TB raw, 30 TB with 3 replicas
nodes for disk: 15 (4 TB each, filled to 50%)
replica operations at peak: 1,200,000/s -> 60 nodes
cluster: 60 nodes; each holds ~500 GB
rebuild of one dead node, best case, 59 peers at 200 MB/s each: ~0.7 min
same rebuild, each peer throttled to 24 MiB/s: ~5.6 min

API

get(key)                       -> { values: [v1, v2?], context }   more than one value = concurrent writes to resolve
put(key, value, context)       -> ok | error                         context = the version vector from the get
delete(key, context)           -> ok                                  writes a tombstone, not an erase
options: { r: 1..N, w: 1..N, timeoutMs }                               per-request consistency

The context is the important part. A client reads, changes, and writes back with the version it read, so the store can tell "this write replaces version X" from "this write happened alongside version X without knowing about it". When it's the second case, a later get returns both values and the client (or a merge rule) resolves them. For a shopping cart, the merge is a union of items.

Data model

On each node, every key maps to (value, version vector, tombstone?), stored in a log-structured merge tree, the storage engine of Cassandra, ScyllaDB and RocksDB:

• Commit log (append-only): a write is durable on this node once the log is fsync'd. In this design each replica fsyncs before it acks, batching many writes per fsync (group commit). Cassandra's default is weaker and worth knowing: commitlog_sync: periodic acks writes at once and fsyncs every 10 s (its cassandra.yaml docs), relying on the other replicas to cover a crash in that window.
• Memtable (sorted, in memory): the write is applied here and acknowledged.
• SSTables (sorted, immutable files): the memtable is flushed when full; background compaction merges SSTables and drops overwritten values and expired tombstones.
• A Bloom filter per SSTable lets a read skip files that can't contain the key, which is why point reads stay fast even with many SSTables (see Bloom filters).

Cluster metadata is small: the ring (which node owns which token ranges), the membership list with each node's state, and the per-keyspace replication settings. Nodes spread it to each other by gossip: every second each node exchanges state with a few random peers, so a change reaches all 60 nodes in a handful of rounds without a central coordinator.

High-level design

1. Any node can coordinate. The client (or a smart client library that knows the ring) sends the request to a node; ideally one of the key's replicas, to save a hop.
2. Write: the coordinator sends the write to all N replicas in the preference list (stand-ins with hints for any that are down), and answers the client after W acknowledgements. Each replica appends to its commit log, updates its memtable, and acks.
3. Read: the coordinator sends the read to all N replicas and uses the first R replies (the estimates count all three replica reads), compares versions, returns the newest (or all concurrent siblings), and repairs stale replicas in the background.
4. Membership and failure detection run by gossip: each node tracks how recently it heard from each peer and marks a peer as down when it has been silent for too long relative to its usual rhythm (Cassandra uses a phi-accrual detector for this). Being marked down only affects routing; a node is removed from the ring only by an operator, because a long pause and a dead machine look the same from outside.
5. Background repair (Merkle-tree anti-entropy) catches whatever hints and read repair missed.

Hashing keys onto a ring with virtual nodes gives three properties at once, and an interviewer will want all three named:

• Incremental scaling: a new node takes over a slice of each existing node's ranges, so only about 1/(nodes + 1) of the keys move. Consistent hashing measures this movement against hash mod N, where almost every key moves.
• Balance: more positions per node evens out the load. The model's 8 positions gave a spread from 14,750 to 22,180 replicas per node; Cassandra 4.0 defaults to 16 tokens per node plus an allocation algorithm that places them for balance (allocate_tokens_for_local_replication_factor, default 3) instead of at random.
• Fast rebuilds: a dead node's ranges are scattered over all its peers, so all of them stream data in parallel (0.7 minutes in the estimates at best, about 5.6 with Cassandra's default streaming throttle).

Replication adds one rule: the preference list skips positions belonging to a node already in the list, and with racks or availability zones, it also skips nodes in a rack already used, so the three copies are in three failure domains. Losing a whole rack then costs one replica of each key, never all three.

R + W > N guarantees that every read set overlaps every write set in at least one replica, so a read sees the latest acknowledged write (as long as membership doesn't change mid-way and the hinted stand-ins aren't counted, see the gotcha below). Quorums: R + W > N simulates stale reads for each setting. Here the question is the other cost of quorums: latency. A quorum operation waits for the R-th fastest replica, so a single slow replica hurts more as R grows:

// Why (N,R,W) = (3,2,2) and not R=3? A quorum read waits for the R-th fastest of N replicas.
// Each replica's latency: 1 ms typical, with a 2% chance of a 40 ms stall (GC pause, compaction, busy disk).
// Seeded PRNG (mulberry32) so the output is reproducible.
function mulberry32(a) {
  return () => {
    a |= 0; a = (a + 0x6d2b79f5) | 0;
    let t = Math.imul(a ^ (a >>> 15), 1 | a);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}
const rand = mulberry32(7);
const replicaLatency = () => (rand() < 0.02 ? 40 : 0.6 + rand() * 0.8);
const pct = (sorted, p) => sorted[Math.min(sorted.length - 1, Math.floor(p * sorted.length))];

const TRIALS = 200_000;
for (const r of [1, 2, 3]) {
  const samples = [];
  for (let i = 0; i < TRIALS; i++) {
    const three = [replicaLatency(), replicaLatency(), replicaLatency()].sort((a, b) => a - b);
    samples.push(three[r - 1]); // the coordinator answers once the R-th reply arrives
  }
  samples.sort((a, b) => a - b);
  const slow = samples.filter((x) => x >= 40).length / TRIALS;
  console.log(`R=${r}: p50 ${pct(samples, 0.5).toFixed(2)} ms, p99 ${pct(samples, 0.99).toFixed(2)} ms, p99.9 ${pct(samples, 0.999).toFixed(2)} ms, stalled ${(slow * 100).toFixed(2)}%`);
}

R=1: p50 0.77 ms, p99 1.24 ms, p99.9 1.34 ms, stalled 0.00%
R=2: p50 1.01 ms, p99 1.37 ms, p99.9 40.00 ms, stalled 0.11%
R=3: p50 1.25 ms, p99 40.00 ms, p99.9 40.00 ms, stalled 5.84%

Two latency tricks follow directly from this: send the read to all three replicas and use the first two replies (rather than picking two and hoping; it costs a third replica read per read, which the estimates count), and for R = 1 reads, send a second "hedged" request if the first hasn't answered by the p95 time.

Merkle trees are what make anti-entropy affordable: two replicas holding 500 GB each compare a tree of hashes top-down and only descend into subtrees whose hashes differ, so a handful of differing keys costs a handful of hash comparisons per tree level instead of a full scan. Merkle trees builds one and finds the differing leaf.

Deletes need care. A delete writes a tombstone (a "deleted at version X" marker), not an erase, because an erased key on one replica looks exactly like a key that replica never received, and repair would copy the old value back. Tombstones are kept for a grace period and then dropped by compaction; in Cassandra that's gc_grace_seconds, 864,000 seconds (10 days) by default, and its docs warn that a node down for longer than that can bring deleted data back. That's why repairs must run more often than the grace period.

With concurrent writes to different replicas (two browser tabs updating the same cart during a partition), replicas end up with versions that neither supersedes. There are two families of answer:

• Last-write-wins (LWW): every write carries a timestamp and the highest wins. Simple, and what Cassandra does per column. The cost is silent data loss: of two concurrent cart updates, one disappears, and clock skew can make an older write win.
• Version vectors: each value carries a vector of per-node counters. If one vector is greater than or equal to the other in every entry, it supersedes it; otherwise the two are concurrent and both are kept as siblings for the client to merge. Dynamo's shopping cart merged siblings by union, which occasionally brought a deleted item back, which Amazon judged better than losing an added one. Time and ordering: Lamport and vector clocks runs the comparison.
• CRDTs are the third option for specific data types: counters, sets and maps whose merge is defined to always converge, so there are no siblings to resolve by hand (see Conflict resolution: last-write-wins and CRDTs).

For an interview, say which one you pick for the use case and what it costs: "LWW for user profiles, where losing one of two concurrent edits is acceptable; siblings merged by union for the cart, where losing an add is not".

Trade-offs and what to say

• AP vs CP. This design stays writable during partitions and pays with conflicts and eventual consistency. If the requirement is "a read must always see the latest write" (configuration, locks, account balances), use a consensus-based store instead: each key range is a Raft group with a leader, writes are linearizable, and a range without a majority stops taking writes (see CAP and PACELC in a design discussion and Leader election and consensus).
• Tunable consistency is the escape hatch: R = W = 2 by default, W = 1 for fire-and-forget metrics, R = 3 for the rare read that must see everything.
• LSM vs B-tree: LSM makes writes sequential and cheap and reads pay with merging across SSTables; a B-tree engine favours reads. A write-heavy, always-writable store is the textbook LSM case.
• What you'd monitor: hint backlog, read-repair rate, pending compactions, p99 per replica, and tombstone counts per read.

Requirements

Ask what the crawler is for, because it changes the priorities: a search engine wants fresh, important pages; an archive wants breadth; a price monitor wants a few sites very often. This design assumes a general-purpose crawler for a search index.

Functional:

• Start from seed URLs; fetch HTML pages; extract links; follow them within a configured scope (the whole web, or a list of domains).
• Store the raw pages for the indexing pipeline downstream.
• Recrawl pages so the stored copies stay fresh, more often for pages that change often or matter more.

Non-functional:

• Politeness: obey robots.txt (RFC 9309, 2022) and never send a host more than about one request a second unless it's known to handle more.
• Scale: 1 billion pages a month.
• Robustness: malformed HTML, slow or hostile servers, redirect loops and crawler traps must not stall or crash the crawl.
• Dedup: don't fetch the same URL twice in a cycle, don't store the same content twice.
• Extensible: new content types (PDF, images) plug in as new processors.

Out of scope unless asked: executing JavaScript to render single-page apps (a separate, much more expensive rendering tier), ranking and the index itself.

Estimates

Assumptions: 1 billion pages a month; the average stored page size taken from Common Crawl's August 2026 crawl, which its release notes describe as 2.14 billion pages and 360 TiB of uncompressed content; a 1-second delay per host; 10 billion distinct URLs seen over the crawler's life; a Bloom filter at 1% false positives; 30 links extracted per page.

// Assumptions (stated in the text): 1 billion pages a month; average stored page size taken from
// Common Crawl's August 2026 crawl (2.14 billion pages, 360 TiB uncompressed); 1 s politeness per host;
// 10 billion URLs ever seen; Bloom filter at 1% false positives; 30 links extracted per page.
const pagesPerMonth = 1e9, secondsPerMonth = 30 * 86_400;
const ccPages = 2.14e9, ccBytes = 360 * 2 ** 40;
const urlsSeen = 10e9, fpRate = 0.01, linksPerPage = 30;

const pagesPerSec = pagesPerMonth / secondsPerMonth;
const bytesPerPage = ccBytes / ccPages;
console.log(`fetch rate: ${pagesPerSec.toFixed(0)} pages/s average`);
console.log(`average page (Common Crawl): ${(bytesPerPage / 1e3).toFixed(0)} KB`);
console.log(`download: ${((pagesPerSec * bytesPerPage * 8) / 1e9).toFixed(2)} Gbit/s, storage ${((pagesPerMonth * bytesPerPage) / 1e12).toFixed(0)} TB a month (uncompressed)`);
// At 1 request per second per host, you need at least this many different hosts in flight at once.
console.log(`hosts in flight at 1 req/s each: at least ${Math.ceil(pagesPerSec)}`);
// URL dedup: 'have we seen it?' is asked for every extracted link.
console.log(`seen-URL checks: ${(pagesPerSec * linksPerPage).toFixed(0)}/s`);
// Bloom filter size: m = -n ln p / (ln 2)^2 bits, k = (m/n) ln 2 hash functions.
const bitsPerUrl = -Math.log(fpRate) / Math.LN2 ** 2;
console.log(`Bloom filter for ${urlsSeen / 1e9}B URLs at ${fpRate * 100}%: ${bitsPerUrl.toFixed(2)} bits each, ${((urlsSeen * bitsPerUrl) / 8 / 1e9).toFixed(1)} GB, k=${Math.round(bitsPerUrl * Math.LN2)}`);
// The exact alternative: a set of 8-byte URL fingerprints.
console.log(`exact set of 8-byte fingerprints: ${((urlsSeen * 8) / 1e9).toFixed(0)} GB`);

fetch rate: 386 pages/s average
average page (Common Crawl): 185 KB
download: 0.57 Gbit/s, storage 185 TB a month (uncompressed)
hosts in flight at 1 req/s each: at least 386
seen-URL checks: 11574/s
Bloom filter for 10B URLs at 1%: 9.59 bits each, 12.0 GB, k=7
exact set of 8-byte fingerprints: 80 GB

API

A crawler has no public request path. Its "API" is the control plane and the interfaces between components:

POST /crawls            { "seeds": ["https://news.example/"], "scope": { "domains": ["*.example"] },
                          "maxPages": 50000000, "recrawl": "adaptive" }        -> 201 { "crawlId": "c-17" }
GET  /crawls/c-17       -> { "fetched": 1203391, "queued": 8823004, "errors": { "5xx": 1210, "timeout": 377 } }

frontier.add(urls[], priority)          from the link extractor, after the URL filter and "seen?"
frontier.next(workerId) -> url | wait   to a fetcher: the next URL whose host is allowed now
frontier.done(url, status, nextDue)     after a fetch: record the outcome, schedule the recrawl

Data model

• URL table (a wide-column or key-value store, keyed by a 64-bit hash of the normalised URL): url, host, priority, last_fetched, next_due, http_status, content_hash, change_count. About 10 billion rows; this is the durable record behind the in-memory Bloom filter.
• Host table (small, cached in the frontier): host, robots.txt rules and when they were fetched, crawl delay, next_allowed_at, recent error rate, average response time.
• Raw pages: WARC files in object storage (the web-archive format Common Crawl publishes in), with an index from URL hash to file and offset.
• Content fingerprints: exact content hash and a SimHash per page, for duplicate and near-duplicate detection.

High-level design

1. Frontier → fetchers. A fetcher asks the frontier for work and gets a URL whose host is allowed now. Fetchers are many lightweight async workers (thousands of concurrent connections per machine), because most of a fetch is waiting on the network.
2. Fetch. Resolve the host through a local DNS cache (an uncached DNS lookup per page would add tens of milliseconds and hammer resolvers), check the cached robots.txt rules, download with strict timeouts and a size cap, follow a bounded number of redirects.
3. Store and parse. Write the raw response to a WARC file in object storage; parse the HTML for text, links and metadata (<link rel="canonical">, noindex, nofollow).
4. Content dedup. If the exact content hash was seen before (mirrors, ?sessionid= variants), record the URL as a duplicate and stop; near-duplicates are found with SimHash.
5. Link pipeline. Each link is resolved against the page URL, normalised, checked against scope and trap rules, then against "URL seen?". Survivors go to the frontier with a priority.
6. Recrawl. The URL store schedules each known URL's next_due; due URLs re-enter the frontier.
7. Distribution. Partition the frontier by host hash: every URL of a host goes to the same frontier node, so that node alone enforces the host's politeness and nothing needs coordinating across machines. Fetchers can live with their frontier partition. A node that dies loses only in-memory queues, which are rebuilt from the URL store.

This two-level layout comes from Mercator, the crawler Heydon and Najork described in 1999 (the textbook Introduction to Information Retrieval by Manning, Raghavan and Schütze walks through it), and it's still the standard answer:

• Front queues hold URLs by priority (PageRank-like importance, how often the page changes, how close it is to a seed). The selector takes from them with weights (say F1 70%, F2 20%, F3 10%), so low-priority work still makes progress.
• Back queues hold URLs by host, one host per queue. When a back queue runs empty, the selector refills it from the front queues; when a host has no queue yet, it gets one.
• The heap holds one entry per back queue, keyed by the host's next allowed fetch time. A fetcher pops the top; if its time is in the future, it waits; otherwise it takes the head URL of that host's queue and pushes the host back with now + delay. That's exactly the model's loop, with a heap instead of a sort.
• The delay adapts. A fixed 1 s is the starting point; the textbook refinement is a gap an order of magnitude larger than the host's most recent fetch time (a page that took 2 s to serve means waiting about 20 s), plus backing off sharply on 429 or 503. A big site that serves pages in 50 ms can be given a shorter delay, if its robots.txt doesn't say otherwise.
• Memory. Billions of queued URLs don't fit in RAM, so each queue keeps its head in memory and spills the rest to disk (or to the URL store), loading in batches.

URLs must be normalised before the "seen?" check, or the same page enters the frontier many times: lowercase the scheme and host, drop the default port and the #fragment, resolve ./ and ../, sort query parameters, and remove known tracking parameters (utm_*, session ids). The page's <link rel="canonical"> tells you which variant the site prefers.

Then two separate dedup checks:

Exact content hashes catch mirrors and trivially different URLs. Most duplicates aren't byte-identical, though: the same article with a different date in the footer or a different ad. SimHash maps a document to a 64-bit fingerprint such that similar documents differ in only a few bits. Google researchers showed it works for crawling (Manku, Jain and Das Sarma, "Detecting Near-Duplicates for Web Crawling", WWW 2007): for 8 billion pages, 64-bit fingerprints with a threshold of 3 differing bits was a good choice.

A Bloom filter can't forget, and it fills up. Two practical answers: rebuild it from the URL store periodically (the store is the source of truth), or use one filter per crawl cycle. And because it lives in memory, shard it by URL hash across a few machines and checkpoint it to disk.

RFC 9309 (2022) turned robots.txt from a 1994 convention into a standard. The rules a crawler must implement:

• Fetch /robots.txt per host (scheme + host + port) before crawling it, and match your user-agent's group of Allow / Disallow rules; the most specific (longest) matching rule wins.
• Cache it, but not for more than 24 hours unless the file is unreachable; standard HTTP caching headers may shorten that.
• Parse at least the first 500 KiB; content past your limit can be ignored.
• If robots.txt returns a 4xx (including 404), you may crawl everything. If it returns a 5xx or the server is unreachable, you must assume complete disallow; after a long outage (the RFC gives 30 days as an example) you may treat it as unavailable or keep using the cached copy.
• Crawl-delay is not in the RFC; many crawlers honour it anyway, as an upper bound on rate.

Politeness beyond robots.txt: identify yourself with a user-agent that links to a page explaining the crawler and how to block it, honour 429 and Retry-After, and cap concurrent connections per IP address as well as per host, because thousands of small sites often share one server.

Some sites generate an infinite number of URLs: a calendar with a "next month" link forever, faceted search with every combination of filters, session ids in every link, or a misconfigured server that answers /a/b/a/b/a/b/… with the same page. A crawler without defences spends its whole budget on one such site. Defences, each cheap:

• Per-host budgets: at most N pages per host per crawl cycle, set by the host's importance.
• URL limits: maximum length (a few hundred to 2,000 characters) and maximum path depth; reject paths with repeating segments.
• Content-based detection: many URLs on one host producing near-identical content (SimHash again) → lower that host's priority.
• Fetch limits: connect and read timeouts of a few seconds, a maximum body size, at most a handful of redirects, and only the content types you process.
• Isolation: parsing hostile HTML is untrusted-input processing; run parsers in a sandboxed process so a pathological page can only crash its worker.

The web changes unevenly: a news home page changes every few minutes, an old blog post never. Recrawling everything every month wastes most fetches; recrawling nothing makes the index stale. The standard approach is to estimate each page's change rate from history (did the content hash change between the last fetches?) and schedule next_due accordingly: halve the interval when a page has changed, double it (up to a cap) when it hasn't, weighted by importance. Conditional requests (If-Modified-Since, If-None-Match) let unchanged pages answer 304 Not Modified with no body, which saves bandwidth on both sides. Sitemaps (sitemap.xml with lastmod) are a hint from the site about what changed.

Trade-offs and what to say

• Bloom filter vs exact store for "seen?": 12 GB and 1% missed URLs, versus 80 GB of fingerprints (or a database lookup per link). Name the error and why it's acceptable here.
• Politeness vs freshness: you will sometimes know a page changed and still wait for its host's slot. Politeness wins; a crawler that gets blocked gets nothing.
• Partitioning by host keeps politeness local but makes very large hosts hot partitions; split the biggest hosts by path prefix with their share of the rate.
• BFS vs priority: pure breadth-first is simple and fair but spends equal effort on spam and on important pages; priority queues fix that at the cost of a scoring system.
• JavaScript rendering multiplies the cost per page many times over (a headless browser instead of an HTTP GET); render only for the hosts and pages where it changes the result.

Requirements

Functional:

• Services send a notification by type (order_shipped, login_code, weekly_digest, promo) to one user, a list, or a segment ("all users in Canada who bought in the last 30 days").
• Channels: push (iOS via APNs, Android via FCM), email, SMS, and an in-app inbox. Each type has default channels.
• User preferences per category and channel, plus quiet hours in the user's time zone; legal unsubscribe for marketing email.
• Templates with localisation; scheduled sends ("Tuesday at 10:00 in each user's time zone").
• Status per notification and channel: queued, sent, delivered, failed, opened.

Non-functional:

• Transactional messages are fast: a login code reaches the provider within a second or two, whatever else is going on.
• At-least-once delivery with dedup: never silently lose a transactional message; duplicates are rare and caught.
• Isolation: a campaign or a failing provider must not delay other traffic.
• Don't spam: per-user caps (no more than N promotional pushes a day) and digests for high-frequency events.
• Scale: 50 million daily active users.

Estimates

Assumptions: 50M daily active users; per user per day, 4 pushes, 0.5 emails, 0.05 SMS (mostly login codes); peak 5× average; 70% of push goes to Android devices through FCM; a marketing campaign to 30M Android devices; 1 KB per notification record kept 90 days. Two provider limits from their docs (October 2026): FCM's default quota of 600,000 messages per minute per project, and 100 SMS message parts a second for a US short code (AWS End User Messaging; US toll-free numbers get 3).

// Assumptions (stated in the text): 50M daily active users; per user per day 4 push, 0.5 email, 0.05 SMS;
// peak = 5x average; a marketing campaign to 30M Android devices; FCM's default quota of 600,000 messages a minute
// per project (Firebase docs, 2026); US short code 100 SMS parts/s (AWS End User Messaging docs, 2026);
// 1 KB per notification record kept 90 days; 70% of push goes to Android devices through FCM.
const dau = 50e6, DAY = 86_400, peak = 5;
const perUser = { push: 4, email: 0.5, sms: 0.05 };
const fcmPerMinute = 600_000, shortCodeMps = 100, campaign = 30e6, recordBytes = 1_000, keepDays = 90;
const fmt = (n) => Math.round(n).toLocaleString("en-US");

let total = 0;
for (const [channel, n] of Object.entries(perUser)) {
  const perDay = dau * n;
  total += perDay;
  console.log(`${channel.padEnd(5)} ${fmt(perDay).padStart(11)}/day  ${fmt(perDay / DAY).padStart(6)}/s avg  ${fmt((perDay / DAY) * peak).padStart(6)}/s peak`);
}
console.log(`all   ${fmt(total).padStart(11)}/day, history ${((total * recordBytes * keepDays) / 1e12).toFixed(1)} TB for ${keepDays} days`);
const fcmPeakPerMin = ((dau * perUser.push) / DAY) * peak * 0.7 * 60;
console.log(`FCM at peak: ${fmt(fcmPeakPerMin)}/min = ${((fcmPeakPerMin / fcmPerMinute) * 100).toFixed(0)}% of the default quota`);
// Campaign: how long at the default FCM quota?
console.log(`campaign to ${campaign / 1e6}M Android devices at ${fmt(fcmPerMinute)}/min: ${(campaign / fcmPerMinute).toFixed(0)} minutes`);
// SMS at peak versus one short code.
const smsPeak = ((dau * perUser.sms) / DAY) * peak;
console.log(`SMS peak ${smsPeak.toFixed(0)}/s vs ${shortCodeMps}/s per short code: ${Math.ceil(smsPeak / shortCodeMps)} short code(s), more if messages are multi-part`);

push  200,000,000/day   2,315/s avg  11,574/s peak
email  25,000,000/day     289/s avg   1,447/s peak
sms     2,500,000/day      29/s avg     145/s peak
all   227,500,000/day, history 20.5 TB for 90 days
FCM at peak: 486,111/min = 81% of the default quota
campaign to 30M Android devices at 600,000/min: 50 minutes
SMS peak 145/s vs 100/s per short code: 2 short code(s), more if messages are multi-part

API

POST /v1/notifications
  Idempotency-Key: order-5521-shipped
  { "type": "order_shipped", "userIds": ["u_ana"], "templateId": "shipped_v3",
    "data": { "orderId": 5521, "eta": "2026-10-27" }, "priority": "high", "sendAt": null }
  -> 202 Accepted  { "notificationId": "n_8d1e", "status": "queued" }

POST /v1/campaigns   { "segmentId": "seg_ca_buyers_30d", "templateId": "fall_promo", "sendAt": "2026-10-28T10:00",
                       "timeZone": "recipient", "ratePerMinute": 300000 }  -> 202 { "campaignId": "cmp_44" }

GET  /v1/notifications/n_8d1e        -> per-channel status: push delivered, email failed (dead-lettered)
GET  /v1/users/u_ana/preferences     PUT  /v1/users/u_ana/preferences
POST /v1/devices   { "platform": "android", "token": "fcm-token…", "appVersion": "5.2.0" }

The API answers 202 Accepted, not 200: accepting the request means "durably queued", and the actual sending happens asynchronously. The idempotency key is the producer's own event id (order-5521-shipped), which is exactly what the door check in the model uses.

Data model

• notifications: id, idempotency_key (unique), type, user_id, template_id, data, priority, created_at.
• deliveries: notification_id, channel, status, attempts, provider_message_id, last_error, updated_at. One row per channel, so "push delivered, email failed" is representable.
• preferences: user_id, category (transactional, social, marketing), channel, enabled, plus quiet_start, quiet_end, time_zone.
• devices: user_id, platform, token, last_seen, active. A user has several devices; tokens go stale and must be pruned.
• templates: id, version, locale, channel, subject, body.
• sent keys (Redis): eventId:user:channel with a TTL of a few days, for the worker-level dedup.

Preferences and devices are read on every notification, so they're cached (a few hundred bytes per user, 50M users, a few tens of GB).

High-level design

1. Accept. A producer calls the API (or publishes an event the notification service consumes). The service checks the idempotency key; if new, it stores the notification and acknowledges with 202. From this moment the message is durable.
2. Decide. It loads the user's preferences and devices (from cache), applies category rules (transactional ignores marketing opt-outs; marketing respects quiet hours and per-user caps), picks the channels, and renders each channel's template in the user's locale.
3. Fan out. One job per channel (and per device for push) goes onto that channel's queue, in the high or low lane by priority. Segment sends (campaigns) are expanded in batches by a separate campaign worker, at the campaign's configured rate, onto the low lane.
4. Send. Channel workers take jobs, check the sent-key for dedup, call the provider through a per-provider rate limiter, and record the outcome. Transient failures (429, 5xx, timeouts) are retried with backoff; permanent ones (invalid token, unsubscribed address) are recorded and not retried.
5. Track. Provider callbacks (email delivery and bounce webhooks, SMS delivery receipts) and client events (push opened) update the delivery log.

You can't get exactly-once delivery to a phone: the provider call can succeed and the acknowledgement can be lost. What you build is at-least-once with deduplication, as described in Idempotency and exactly-once:

• Durable before acknowledged. The 202 is sent only after the notification is stored (or the event committed to Kafka). A crash after that point delays the message; it can't lose it.
• Door dedup: a unique constraint on idempotency_key turns a producer's retry into a no-op, as with e1 in the model.
• Worker dedup: the sent-key eventId:user:channel is set after the provider accepts the message. A queue redelivery (worker died before acking, as with e2) finds the key and skips.
• The remaining window. A worker that crashes after the provider accepted the message but before writing the sent-key will send it again on redelivery. That window is milliseconds, so duplicates are rare, not impossible. Where a duplicate really hurts, pass a provider-side id where the provider supports one (for example, APNs shows notifications that share an apns-collapse-id as a single notification), or make the message itself idempotent ("Your code is 482913", not "Here's another code").
• Retries and the DLQ. Transient failures retry with exponential backoff and full jitter, capped at a few attempts or a time limit (a login code that arrives after 10 minutes is useless, so its retries stop early). Exhausted jobs go to a dead-letter queue with the error, for alerting and replay. A message that fails because of its own content (a template error) is a poison message: retrying won't help, so it goes to the DLQ at once.

The estimates showed why isolation is the core problem: one campaign is 50 minutes of FCM's full default quota. If campaigns and login codes shared one queue, every code sent during those 50 minutes would wait behind millions of promotions. So:

• Separate queues per channel, so a slow email provider backs up only email.
• Separate lanes per priority within a channel, with workers reserved for the high lane (or a weighted consumer that always drains high first).
• Rate limiting per provider, shared by all workers of that channel (the Design a rate limiter design, pointed outwards): FCM at, say, 90% of quota, leaving headroom so a burst of 429s can't happen. The campaign's own ratePerMinute sits under that.
• Separate provider accounts or sender numbers for transactional and marketing traffic where providers allow it, so marketing complaints or quota exhaustion can't affect codes. SMS short codes are a common example: one for codes, one for marketing.

Device tokens deserve their own maintenance loop: a token stops working when the app is uninstalled or the user reinstalls, and the provider usually tells you so on a later send (FCM answers UNREGISTERED; APNs answers 410 Unregistered, though not always promptly, as above). Mark it inactive immediately, or the system keeps paying for sends that can't arrive and the provider may throttle you for it. Apps should re-register their token on every launch so last_seen stays current.

• Per-user caps: a counter per user per category per day (the rate limiter again, keyed by user): "at most 3 marketing pushes a day".
• Quiet hours: marketing and social notifications for a user in quiet hours are delayed until the window ends (a delayed job, see Design a distributed job scheduler); transactional ones go now.
• Collapsing and digests: 40 likes in 10 minutes should be one notification ("Priya and 39 others liked your photo"). Hold social events per user for a short window and send a summary; on the device, push collapse keys replace older notifications with newer ones.
• Time zones: "10:00 local time" for a global campaign means 24+ separate send waves; the campaign worker computes each user's send time and schedules it.

Trade-offs and what to say

• Push vs pull: push notifications are best-effort (the provider and the OS can delay or drop them); the in-app inbox is the reliable record, fetched when the app opens.
• At-least-once vs at-most-once: for a login code a duplicate is harmless and a loss is not; for "you've been charged" a duplicate causes alarm, so dedup matters more than speed.
• One service vs per-channel services: one notification service with per-channel workers keeps preferences and dedup in one place; at very large scale, channels become separate services sharing the preference store.
• What breaks first: provider quotas and reputation, not your own throughput.