R17 — Infrastructure design walkthroughs: rate limiter, API gateway, scheduler, key-value store

This is where the pack stops building mechanisms and starts using them. R0 to R16 built the general tools. R17 to R22 use those tools on general design questions, and R23 and R24 prepare the low-level design round. After that, R25 to R28 turn to the payments domain and the payments round.

A senior design interview rarely stays inside payments. At some point — often as a warm-up, or to see how deep you can go — the interviewer asks you to design a piece of infrastructure: a rate limiter, an API gateway, a job scheduler or a key-value store. None of these needs new theory. Each one reuses tools from R2 to R16 under tight constraints: idempotency, leases and fencing, consistent hashing, quorums, circuit breakers, the outbox. You are graded on whether you reach for the right tool and can explain why.

Like every walkthrough in the pack, including the payments round in R28, these are written as transcripts — conversations between an interviewer and you. That is because the real test is in the follow-up questions: the pushback on your algorithm, the dependency that fails, the moment you say "I would not build that, I would use this instead".

How to use these walkthroughs

Read each walkthrough once, for the flow of the conversation. Then re-read the lesson blocks that follow each exchange. Each block says what the interviewer was testing, explains the idea in a few sentences, and gives you one line to remember. Where an idea is already taught elsewhere in the pack, the block points there instead of teaching it again. All numbers are assumptions chosen to make the arithmetic easy to follow, not measurements of a real system.

Every walkthrough here, and the payments designs in R28, follows the same 45-minute shape: agree the scope, do the arithmetic, design the normal path, design the data model, and then spend most of the time on what happens when things fail.

Walkthrough 1 — Rate limiter, distributed across a gateway fleet

Interviewer: Design a distributed rate limiter.

You: Before drawing anything, I want to pin down the scope. "Rate limiter" can mean a small library inside one service. It can also mean a platform that protects hundreds of APIs. These are the questions that change the architecture:

If you leave it to me, here is what I will assume, in plain terms:

• What it is. One rate limiter shared by all our public APIs, used by many customer companies ("tenants") at once.
• Where it runs. In the API gateway — the front door every request passes through — so no individual service has to implement limits itself.
• Where the counts live. In a Redis cluster: a very fast in-memory store that every gateway machine can read and update.
• What it counts. Requests per API key, per user, per IP address, per endpoint and per pricing tier. One request can be checked against several rules at once — say, "100 per second for this key" and "10 per second on the payments endpoint".
• How strict. Close enough, not perfect: for a few seconds a caller might get up to about 2% more than their limit — 102 requests instead of 100.
• How big. Up to 500,000 limit checks per second, 50 million different callers active in an hour, three regions, and a new or changed rule must take effect within 5 seconds.
• What if the limiter breaks. By default we fail open — let requests through — so a limiter outage does not take every API down with it. For login, one-time passwords and anything that moves money we fail closed — block — because letting attackers through there is worse than a short outage.

Interviewer: You keep saying "approximate is fine". Why does exactness matter so much?

You: Because being exact is the most expensive thing you can ask of a rate limiter. To count perfectly, every gateway machine has to check one shared counter before letting a request through. There are three ways to arrange that counter, and each costs something different:

My default is the middle option — a shared counter per region — and I switch only the very busiest keys to local counting, where each gateway takes a small batch of allowance and spends it locally. The reason this is acceptable: rate limits exist for fairness and protection, not accounting. Letting 102 requests through instead of 100 harms nobody. The exception is a quota that is also a bill — "you paid for 1 million calls this month" — which deserves stricter, slower counting.

What's being probed: whether you scope the problem before designing, and whether you can argue for a looser guarantee.

Concept — coordination costs latency. When many machines must agree on one number, they have to talk to each other. The tighter the agreement — exact, global, right now — the more round trips they need. A tighter agreement also means the system stalls more when a link fails. Rate limits are a natural place to relax. Relaxing lets each region, or each machine, decide alone most of the time. It is the same latency-versus-consistency dial as R0's CAP discussion, turned towards speed.

Takeaway: Buy speed and availability by accepting a small, bounded overshoot.

Interviewer: Requirements?

You: Functionally, the limiter must:

• check each request in-line against all matching rules;
• support these dimensions: key, user, IP or CIDR (a range of IP addresses), endpoint, tier, and combinations of them;
• support windows from per-second to per-day, with burst sizes;
• support weighted cost, so an expensive endpoint consumes 10 tokens instead of one;
• return HTTP 429 with Retry-After and X-RateLimit-* headers;
• offer an admin API with hot reload, so rule changes apply without a restart;
• allow per-tenant overrides;
• emit throttle events for dashboards and abuse detection;
• offer a shadow mode that logs would-be denials without blocking anything.

Non-functionally, I give each line a number, because each number becomes a decision later:

• p99 added latency under 1 ms in-region (p99 means the slowest 1% of requests). This rules out a database call per request.
• Must not reduce API availability. This forces a degraded mode.
• No unbounded overshoot under races. This forces atomic updates.
• 500K checks/s, scalable to 5M. Rules converge on every gateway within 5 s. One noisy tenant cannot affect another.

Out of scope:

• L3/L4 DDoS (floods at the network and transport layers) — that is the scrubbing provider's job;
• billing;
• ML bot detection;
• concurrency limiting of in-flight requests, which I would mention as an extension.

Interviewer: Isn't this just load shedding with extra steps?

You: No. Rate limiting asks "is this caller over its contract?"; load shedding asks "is the system overloaded right now?" Rate limiting enforces per-caller fairness, even when the fleet is idle. Load shedding drops low-priority traffic, no matter who sent it. So one protects customers from each other, and the other protects the system from everyone. You run both. Load shedding is R14's territory.

Capacity

Interviewer: Size it.

You: My assumptions:

• 10 billion requests a day.
• Peak traffic is 4× the average.
• One Redis script call per request, covering all of a caller's rules.
• 50M active keys per hour.
• About 120 bytes per bucket key.
• 100K rules of about 500 bytes each.
• Three regions.

1. Average: 10B / 86,400 ≈ 116K QPS (queries per second). Peak is ×4 ≈ 460K, so plan for 500K checks/s.
2. The largest region takes half of that: about 250K script calls/s.
3. A short Lua script on one Redis primary runs at roughly 50–80K calls/s, because Redis is single-threaded. At a conservative 50K, we need 5 primaries at minimum. So plan 8–10 per region, each with a replica.
4. Memory: 50M keys × 120 B = 6 GB. This stays steady, because idle keys expire. That is tiny.
5. Rules: 100K × 500 B ≈ 50 MB raw, about 150 MB once indexed. That fits in every gateway's heap, so rule lookup never leaves the node.
6. Throttle events: if 2% are denied, that is 10K events/s × 300 B = 3 MB/s to Kafka. Easy.

Interviewer: Why not store every timestamp and be exact?

You: That is the sliding window log — it stores a timestamp for every request in the window. The arithmetic kills it. A 1,000/min limit holds up to 1,000 entries × ~60 B = 60 KB per key. For 10M heavy keys, that is 600 GB against 6 GB for token buckets. Therefore, token bucket.

The limiter is QPS-bound, not storage-bound. In other words, it runs out of operations per second long before it runs out of space. The hard parts are latency, hot keys and behaviour under failure.

What's being probed: whether you turn traffic into shard counts and find the real bottleneck.

Concept — throughput-bound vs storage-bound. The state here is just two numbers per caller. But it changes on every request. So the limit is operations per second per Redis shard, not bytes stored. Redis runs commands on one thread per shard. So throughput grows by adding shards, not by buying a bigger box. Every estimate should end in "therefore". For example: 600 GB versus 6 GB, therefore token bucket; 150 MB of rules, therefore cache them on every gateway.

Takeaway: Find the resource that runs out first, size for that one, and end every number with "therefore".

API and data model

Interviewer: What does the API look like?

You: There are two surfaces.

• The in-line check: RateLimiter.Check(descriptors[], cost). It returns allow or deny, the remaining allowance, the reset time and the retry-after delay.
• A rules admin API: list and read rules; POST /v1/rules with an Idempotency-Key; PUT with If-Match: <version>; soft delete; and GET /v1/rules/snapshot?sinceVersion=41 so gateways can catch up.

A rule looks like this:

{
  "name": "pro-tier-payments-create",
  "match": { "tier": "pro", "method": "POST", "path": "/v1/payments" },
  "keyBy": ["apiKey"],
  "algorithm": "TOKEN_BUCKET",
  "limit": 100, "window": "1s", "burst": 200, "cost": 1,
  "mode": "ENFORCE",
  "failMode": "CLOSED"
}

We apply idempotency on create (R3) and optimistic concurrency on update, both to config. Idempotency means sending the same create twice has the same effect as sending it once. Optimistic concurrency means an update succeeds only if the version has not changed since you read it. The first stops duplicate creates. The second stops two operators silently overwriting each other.

A throttled client sees:

HTTP/1.1 429 Too Many Requests
Retry-After: 1
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1790000001

Retry-After comes straight out of the token bucket: (cost − tokens) / rate. We round it up, because rounding down invites a retry that fails again. When several rules apply, the headers report the most restrictive one. SDKs add jitter (a small random delay), so retries do not all land on the same second.

Interviewer: Where does each piece of state live?

You: There are two very different kinds of data.

Counters go in Redis, not a database. We need 500K atomic updates a second at sub-millisecond latency. And losing a counter on failover only resets one caller's window. Not Memcached either, because it has no server-side scripting. Without that, there is no way to make a multi-step bucket update atomic.

Interviewer: Your key has curly braces in it.

You: Those are Redis Cluster hash tags. Redis Cluster spreads keys across 16,384 slots. Only the part inside {…} is hashed to pick the slot. So all of one caller's keys land on one shard. This matters because Redis only runs a multi-key Lua script when every key is in the same slot. As a result, one script call checks both of a caller's rules atomically.

The cost: a giant caller becomes a giant shard. I will come back to that. Every key gets a TTL (time to live — an expiry timer) of about twice its full-refill time. That is why 50M hourly keys need only 6 GB.

What's being probed: matching each store to its access pattern, and practical Redis Cluster knowledge.

Concept — durable config vs ephemeral counters. Rules are precious and change rarely. So they belong in a relational database with history. Counters are written on every request and are worthless after a minute. So they belong in memory with an expiry. Hash tags then let you choose which keys must live together, so they can change atomically. This is R10's partitioning trade-off in miniature: co-location buys atomicity but costs balance.

Takeaway: Precious data gets a database; hot disposable data gets memory with a TTL; co-locate what must change together.

High-level design

Interviewer: Draw it and walk me through an allowed request.

You: The design splits into two parts. The data plane runs on every request. The control plane is used rarely. It is easier to walk through than to describe. Follow an allowed request through the gateway filter to Redis and back. Then follow a throttled one. Then watch a rule change propagate.

The allowed request, step by step:

1. The client sends GET /v1/orders with its API key. The edge applies coarse per-IP limits.
2. The gateway authenticates the request and resolves tenant acme, tier pro.
3. The limiter filter matches rules from its in-memory table, version 42. Two rules match: per-key 100 rps (requests per second) with burst 200, and per-endpoint 1,000 rps for the tenant.
4. It builds both keys with the same hash tag and calls EVALSHA once.
5. Redis runs the bucket script atomically for both keys. It returns allowed=1, remaining=41.
6. The gateway sets headers from the most restrictive rule and proxies the request. Added latency: about 0.3–0.6 ms.

The throttled request: the script finds tokens < cost. It decrements nothing and returns a retry delay. The gateway returns 429, and the backend is never called. A throttle event goes to Kafka asynchronously.

Interviewer: Why the gateway? Wouldn't a sidecar or a library be cleaner? Before or after auth?

You: Each placement fits a different job, so I would layer them.

Enforce each limit at the earliest layer that knows enough to enforce it. On auth, I would do both. A cheap IP limit runs before auth, and it protects the auth service itself. The per-key limit runs after auth, because it needs the caller's identity.

What's being probed: the data plane / control plane split, and a defensible layered placement.

Concept — data plane vs control plane. The data plane handles every request, so it must be tiny: a local rule lookup, one Redis call, done. The control plane — rules, versions, audit — runs rarely and can be slow. So a slow admin database never slows an API call. And a rules-service outage only pauses edits. Walkthrough 2 builds an entire product on this split. R1 introduces the gateway's place in the architecture.

Takeaway: Keep the per-request path tiny; push everything else to the control plane.

Deep dives

Interviewer: Which algorithm?

You:

O(1) means a small, fixed amount of memory per key, whatever the traffic. R14 teaches the mechanics of token and leaky buckets and of the window algorithms. Here, the decision is per use case:

• Token bucket by default.
• Sliding window counter for long windows, where burst semantics confuse customers.
• The log only for low-volume exact limits.
• The leaky queue only for outbound shaping.

Interviewer: A fixed window is one INCR. Why not ship that?

You: The problem is the boundary. Say the limit is 100 per minute. A client sends 100 requests at 12:00:59 and 100 at 12:01:00. That is 200 in two seconds. Also, every client's window resets at the same instant, so retries pile up on the minute.

The sliding window counter keeps O(1) memory and fixes this. It blends the previous window's count with the current one. For example: the previous window had 80, the current one has 30, and we are 25% into the current window. That gives 80 × 0.75 + 30 = 90, so we allow the request.

And if fixed windows are used anywhere, INCR and EXPIRE must run in one script. Otherwise a crash between them leaves a key that never expires, and the caller stays blocked for ever.

Interviewer: Fifty gateways hit the same bucket. What stops them all spending the last token?

You: A GET followed by a SET races: both gateways read one token, and both allow the request. WATCH/MULTI/EXEC is atomic, but retries explode on hot keys. So I move the decision to where the data lives and run it as one indivisible step. That step is a Lua script, which Redis executes as a single command on the shard.

-- KEYS[1] = bucket key; ARGV = capacity, refill rate (tokens/s), cost
local capacity, rate, cost = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3])
local t   = redis.call('TIME')                         -- server time: no gateway skew
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)

local s      = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(s[1]) or capacity
local ts     = tonumber(s[2]) or now
tokens = math.min(capacity, tokens + math.max(0, now - ts) * rate / 1000)  -- lazy refill

local allowed, retryMs = 0, 0
if tokens >= cost then tokens = tokens - cost; allowed = 1
else retryMs = math.ceil((cost - tokens) * 1000 / rate) end

redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(capacity / rate * 1000) * 2)       -- idle keys vanish
return { allowed, math.floor(tokens), retryMs }

Load it once with SCRIPT LOAD. Then call EVALSHA, and fall back to EVAL on NOSCRIPT. Keep the script short, because a slow script blocks the whole shard. Spring Cloud Gateway's RedisRateLimiter is publicly documented as using exactly this kind of Lua token bucket.

Interviewer: The script is atomic. What else can go wrong?

You:

What's being probed: the read-modify-write race, and the partial-failure and clock traps beyond it.

Concept — atomic read-modify-write. Any "read, decide, write back" sequence is unsafe when two actors run it at once. Redis runs one command at a time per shard, and a Lua script counts as one command. So nothing can slip in between its read and its write. When one request touches several counters, the same unit must check all of them before committing any. This is the all-or-nothing guarantee R2 discusses. Here it is cheap, because everything sits on one shard. Finally, let one authority — the Redis server — tell the time.

Takeaway: Move the decision to the data, check all then commit all, and let one clock decide.

Interviewer: How do you stay under 1 ms at p99? And one tenant just went to 300K requests a second.

You: Here is the budget:

• local rule match: 10–50 µs;
• key building: 10 µs;
• same-AZ (availability zone) round trip: 150–300 µs;
• script: 10–30 µs.

That is about 0.3 ms at p50 (the median). To keep it there:

• Use pooled, multiplexed, non-blocking connections (Lettuce).
• Every check is a write, so it must hit the primary. So spread primaries across AZs.
• Set a 2–5 ms hard timeout with a circuit breaker per shard. A circuit breaker stops calling a failing shard, so requests fail fast instead of waiting.

The limiter must never add 100 ms.

The hot key — one tenant on one shard

The 300K tenant is the real problem. All its keys share a hash tag, so they land on one shard. That shard tops out at 50–80K calls a second. So it melts, for every tenant on it. The fix is a hybrid of local and global counting:

• Each gateway keeps a local bucket and leases a batch from Redis. It runs DECRBY 500 every 50 ms, or when it runs low. So Redis sees a few thousand ops a second instead of 300K.
• Overshoot is bounded by gateways × batchSize. So batches are kept to a small fraction of the limit, around 1%.
• Alternatives: async sync, where each gateway enforces limit / N and a coordinator rebalances shares every few hundred milliseconds. Or K sub-buckets, key#0..K-1, each holding limit / K.
• Only rules flagged highVolume, or keys detected above a QPS threshold, use the hybrid. A local pre-filter denies early once the local bucket is empty, so rejected traffic never reaches Redis.

What's being probed: latency awareness, and handling a hot key without giving up correctness entirely.

Concept — token leasing. Think of a bank. Instead of asking the central counter for every token, each gateway withdraws a roll and spends from its own till. The centre sees one withdrawal per roll. Tokens sitting in tills are your overshoot. That overshoot is bounded by roll size times the number of tills. This is R10's hot-key problem: hashing spreads keys, but not the load on a single key. Here it is solved by batching the coordination rather than splitting the data.

Takeaway: Lease tokens in batches to trade a bounded overshoot for a cooler shard.

Interviewer: An operator raises a tenant's limit. How does every gateway know within five seconds?

You:

1. The operator sends PUT /v1/rules/r_9f2c with If-Match: "v41".
2. The rules service validates it. It then writes version 42 plus an audit row in one Postgres transaction.
3. After the commit, it publishes rules.version=42 via a transactional outbox — the event is saved in the same transaction and sent afterwards. So the publish cannot be lost. This is exactly R4's pattern.
4. Each gateway fetches the changes since version 41 and builds a new immutable rule table. It then swaps an AtomicReference to point at the new table. There are no locks on the hot path.
5. The next request uses the new limit. Bucket state in Redis is kept. The new capacity applies on the next refill, because capacity is a script argument.
6. A gateway that missed the push catches up on its 30-second poll. Target: 99% within 2 s, all within 5 s.

Matching uses a trie or hash map on (tier, method, pathPattern). So it costs O(path segments), not O(rules). All applicable rules apply, and tenant overrides carry higher priority. The IP comes only from the hop our own edge wrote into X-Forwarded-For.

Safety measures:

• Validation refuses a zero limit on a critical path unless mode=BLOCK.
• New rules start in shadow mode.
• Changes go to one region first.
• Rollback takes one click.

Walkthrough 2 develops the immutable swap fully.

Interviewer: Three regions, a 1,000 rps limit. Per region or global?

You: Per region by default, with each region's limit sized to its share. GeoDNS pins most callers to one region anyway. Global synchronous coordination adds 50–150 ms and a single point of failure, so I would almost never use it.

For contractual daily or hourly quotas, I use local enforcement with async reconciliation. Each region broadcasts its counts every second and subtracts the other regions' usage. So the error is about one second of traffic. That is noise against 86,400.

If a contract demands an exact global limit, I route that tenant to a home region. That is better than putting the speed of light on every request.

Failures and scale

Interviewer: A Redis primary just died. What happens to API traffic?

You: This is the failure to get right, because a limiter outage must not become an API outage.

1. EVALSHA times out at 5 ms, or the breaker for that shard is already open.
2. Rules with failMode=OPEN fall back to the local bucket at globalLimit / gateways, with a small multiplier. The current gateway count comes from service discovery.
3. Rules with failMode=CLOSED — login, OTP, transfers — return 429 or 503 rather than allow unlimited attempts.
4. limiter_degraded metrics fire. We page someone if it lasts a minute.
5. Redis promotes the replica within seconds. The breaker half-opens, probes, then closes. Lost counter writes only hand a few callers a fresher bucket.

If the whole cluster is down, we use local-only enforcement everywhere, and edge limits still protect the backends.

What's being probed: a designed degraded mode, with fail-open versus fail-closed as a per-endpoint business decision.

Concept — fail-open vs fail-closed. When a check cannot run, you have two choices. You let traffic through, which protects availability. Or you stop it, which protects security. A product listing fails open. Login and money movement fail closed, because unlimited password guesses or unlimited transfer attempts are worse than a brief outage. R14's circuit breaker makes either choice fast, instead of waiting on timeouts.

Takeaway: Decide per endpoint what "broken" means, and fail fast either way.

Interviewer: Other bottlenecks?

You:

• A saturated shard: add more primaries, reshard, and use leasing for heavy rules.
• The rules service dies: gateways keep the last rules in memory and on disk. Edits pause, but enforcement continues.
• A dropped push: the 30-second poll catches it.
• Analytics: it is an async bounded queue. On overflow it drops events and counts the drops. It never blocks a request.
• After a regional failover: traffic lands on cold, full buckets. So edge limits and backend autoscaling absorb the surge.

The question for every box is "if this disappears, what still works?" That is R13's static stability.

Curveballs

Interviewer: An attacker sets X-Forwarded-For to a random IP on every request.

You: We key on the address our own edge appended — the last trusted hop. We never use the client-supplied value. And once a caller is authenticated, I would limit by API key. IP is for unauthenticated endpoints like login.

Interviewer: Simple floods are caught. Credential stuffing (trying stolen username and password pairs) across thousands of IPs?

You: The limiter sees every decision, so it becomes a sensor. Throttle and allow events stream to Kafka. An abuse detector aggregates them by key, IP, ASN and endpoint. It spots what no single rule sees. For example: many API keys from one IP, or a high login failure ratio across an ASN.

It then creates a temporary block rule through the rules service. That rule reaches every gateway in seconds, through the normal path. Observe, decide, enforce, observe again.

What's being probed: trust boundaries, and whether you see the limiter as part of a feedback loop.

Concept — trust boundaries and closed-loop protection. Anything a client sends can be forged. That includes headers that claim to describe the client. Only what your own edge wrote is trustworthy. Static limits get learned and evaded. So you aggregate decisions over time and feed the conclusions back as rules. That closes the loop, and it reuses the rule pipeline you already built.

Takeaway: Trust only what your edge wrote, and turn limiter decisions back into rules.

Quick reference

The 60-second version

Limits are enforced in layers. Coarse per-IP limits run at the edge. Per-key and per-tier limits run as a gateway filter after authentication. Business limits run in the service.

Rules live in Postgres, versioned and audited. They are published through an outbox and swapped atomically into every gateway's memory.

The default algorithm is a token bucket: two numbers per key, burst-friendly, weighted cost and a natural Retry-After. Buckets are held in a sharded Redis Cluster. Each check is one atomic Lua call of about 0.3 ms. Hash tags keep a caller's keys on one slot. At 500K checks a second, that is 8–10 primaries per region and a few gigabytes of memory.

Hot keys lease batches of tokens to the gateways. This trades a bounded overshoot for a cool shard. If Redis fails, most endpoints fail open to local buckets, while login and money movement fail closed. Regions enforce locally, with async reconciliation for global quotas.

Building it on AWS: API Gateway, Lambda and ElastiCache

The design above is cloud-neutral. If the platform runs on AWS, most of it maps onto managed services, and the first two layers need no code at all.

flowchart LR
  C["Client"] --> W["AWS WAF<br/>per-IP rate rule"]
  W --> G["API Gateway (REST)<br/>usage plan + API key"]
  G --> A["Lambda authorizer<br/>our rules"]
  A <--> R[("ElastiCache<br/>Redis / Valkey<br/>counters")]
  P["AppConfig<br/>rules"] -.->|polled, cached in memory| A
  A -->|Allow| B["Backend"]
  A -->|Deny| X["429 + Retry-After"]

Use the built-in limits first, and add the Redis authorizer only for the rules they cannot express.

Turn off authorizer caching for the rate limiter. API Gateway normally reuses an authorizer's answer for a few minutes. A cached "Allow" lets requests through without being counted, so the rate-limiting authorizer must run with a cache time of zero — and that means its latency is added to every request.

Step through the build below. Each step shows the explanation on the left and the code or configuration on the right — highlighted lines are the ones the step is about. It goes from the plan, through the built-in throttling, the ElastiCache store and the Lua script, the rules in AppConfig, to the Lambda authorizer, wiring it to the API with a proper 429, and testing it.

Running this in production

• Start every new rule in shadow mode, check who it would have blocked, then enforce it.
• Keep the authorizer fast: reuse the Redis connection, use timeouts of tens of milliseconds, and give a busy API provisioned concurrency to avoid cold starts.
• Decide fail-open or fail-closed per route, in code, before the first outage forces the decision.
• Watch the authorizer's duration and error rate alongside API Gateway's 4XXError metric; a jump in either is the limiter, not the backend.

Walkthrough 2 — API gateway, as a multi-tenant platform

Interviewer: Design an API gateway.

You: First, what kind of gateway? These are the questions whose answers change the diagram:

Interviewer: A platform used by many teams and external customers. Multi-region. Pick numbers.

You: Then here are my assumptions:

• Traffic direction: north-south only. North-south means traffic coming in from clients outside; east-west means traffic between our own services.
• Protocols: HTTP/1.1, HTTP/2, gRPC, and WebSocket pass-through.
• Load: 600K RPS (requests per second) at peak, across three regions.
• Latency: the gateway adds under 10 ms at p99, not counting upstream time. p99 means 99% of requests are at least this fast.
• Size: 10K routes, 1M API keys, 50K OAuth clients.
• Config changes: live on every node within 5 seconds, with no restart.
• Tokens: issued by an external IdP (identity provider).
• Regions: active-active, and each region can run on its own.

And it does not handle service-to-service traffic. East-west traffic wants a proxy next to each service. That is what a service mesh's sidecars give you — a sidecar is a small proxy running beside each service, handling mTLS (both sides prove their identity), retries and telemetry between services. A central gateway in that path adds an extra hop to every internal call. It also becomes everyone's bottleneck. Gateway for the edge, mesh for the inside, with clear ownership of each.

What's being probed: scoping an infrastructure component, and knowing where a gateway ends and a mesh begins.

Concept — north-south vs east-west. Traffic arriving from clients needs edge concerns. These are public TLS, API keys, quotas for paying customers, and WAF rules (a web application firewall that blocks known attack patterns). Traffic between services needs fast mutual trust instead, and it is far larger in volume. If you mix the two, the front door becomes a chokepoint for every trip down the hallway. R1.3 places the gateway among the building blocks; this walkthrough builds it.

Takeaway: Ask the questions that change the diagram, and keep the gateway at the edge.

Interviewer: Requirements.

You: Functionally, most of the work is plugins in a chain. Each request passes through them in order:

• routing by host, path, method, header and weight;
• TLS and mTLS termination (decrypting the connection at the gateway);
• authentication by JWT with cached JWKS (the IdP's published signing keys), OAuth2 introspection (asking the IdP whether a token is valid), API keys and client certs;
• authorisation by scopes and tenant entitlement;
• rate limits and usage plans;
• request and response transformation, including REST to gRPC;
• aggregation;
• timeouts, retries, breakers and bulkheads;
• canary and blue-green routing;
• logs, metrics and traces;
• a control plane with versioning, validation, audit and rollback;
• streaming pass-through.

Non-functionally, the targets are:

• overhead p50 under 2 ms and p99 under 10 ms;
• 99.99% data-plane availability;
• stateless nodes;
• config propagation under 5 s, and atomic per node (each node switches to the new config all at once, never half-way);
• deny unknown routes by default;
• tenant isolation.

Out of scope: issuing tokens, the mesh, CDN-scale caching, the developer portal and billing invoices. We only emit usage records.

Two lines drive the whole design: p99 overhead under 10 ms, and the data plane keeps serving if the control plane is down. The first rules out a database lookup per request. The second forces a split into two parts. The data plane is the part that handles each request. The control plane is the part that stores, manages and distributes config.

Capacity

Interviewer: Traffic, node count, bandwidth.

You: One node has 8 vCPUs and runs non-blocking code. It handles 15K RPS at 60% CPU, with TLS, JWT and rate limiting included. So 600K peak needs 40 nodes.

Each region has three AZs (availability zones — separate data centres). Losing one zone must not overload the other two, so I multiply by 1.5, which gives 60. Then I add 20% for bursts. That comes to about 72 nodes, 24 per region, 8 per AZ.

Average traffic is 200K RPS. 200K × 86,400 seconds = 17.3 billion requests a day. Each request is about 2 KB in and 8 KB out, so peak is 6 GB/s globally. That is 1.2 Gbps per node, which is comfortable on a 10 Gbps NIC (network card). So CPU, not network, is the limit. Most of that CPU goes on TLS handshakes and signature checks. Here are memory, logs and metrics:

The conclusion that matters: all hot-path config fits in memory on every node. The hot path is the code every request runs through. Because it all fits, "no remote call per request" is realistic.

What's being probed: whether estimates include failure headroom and end in decisions.

Concept — zone headroom and metric cardinality. If one of three zones dies, two zones must carry the load of three. So you provision 1.5× up front. Then you add burst room, because spikes do not wait for autoscaling.

Cardinality means how many distinct series a metric has. A time-series store keeps one series per combination of labels. So labelling by route is fine, but labelling by API key multiplies the count by a million. R15 covers why "who and which one" belongs in logs, and "how much and how fast" belongs in metrics.

Takeaway: Size for peak, multiply for a lost zone, add burst room — and every estimate should end in a decision.

API and data model

Interviewer: What APIs does this expose?

You: The data plane carries the tenants' APIs, plus health endpoints.

The control plane has an admin API. This is where tenants configure things:

• POST /admin/v1/services;
• POST /admin/v1/routes, and PATCH to change a route;
• POST …/canary;
• consumers and keys (the secret is shown once and stored hashed);
• usage plans;
• POST /admin/v1/config/rollouts and …/rollback;
• paginated usage;
• a gRPC ConfigService.StreamConfig that nodes subscribe to.

{
  "name": "orders-get",
  "match": { "hosts": ["api.example.com"], "pathPrefix": "/v1/orders", "methods": ["GET"] },
  "upstream": { "service": "orders-svc", "timeoutMs": 800,
                "retries": { "attempts": 2, "on": ["connect-failure", "503"], "budgetPercent": 20 } },
  "plugins": [
    { "name": "jwt", "config": { "issuer": "https://idp.example.com", "requiredScopes": ["orders:read"] } },
    { "name": "rate-limit", "config": { "by": "consumer", "plan": "gold" } },
    { "name": "circuit-breaker", "config": { "failureRatePct": 50, "minCalls": 50, "openSeconds": 30 } }
  ]
}

Every change produces a new config version. Versions are immutable (never edited after creation) and always increase. Creates take an Idempotency-Key, so a retried create does not make a duplicate. Updates send If-Match with the version. If an editor is working from an old version, they get a 412 error. That stops them from silently overwriting a colleague's change.

Interviewer: Where does each piece of data live?

You:

API keys are long random strings, so a fast hash is enough. bcrypt is for low-entropy human passwords, which are easy to guess. The key is shown once because the platform genuinely cannot show it again — it only keeps the hash.

Interviewer: Postgres is right there. A primary-key lookup per request is cheap.

You: One lookup is cheap. 600K a second is not. Once you include waiting for a connection from the pool, it eats the tail of a 10 ms budget.

Worse, it makes the database a hard dependency of every API on the platform. A Postgres failover would become a platform outage. Keys change rarely, so they are replicated to each node through the same push channel as config. A revoked key reaches every node within the 5-second target.

What's being probed: availability coupling, not just latency.

Concept — hot-path dependencies multiply risk. Every remote system on the request path adds its own slow tail and its own failure rate. Their availabilities multiply. For example, three dependencies at 99.95% each give a combined availability worse than any one of them.

Moving read-mostly data into local memory removes both the latency and the failure mode. The price is a few seconds of staleness. This is R12's "should I cache this?" answered yes, with push invalidation (the source tells nodes when data changes).

Takeaway: Read-mostly data on the hot path is replicated to the node, not fetched per request.

High-level design

Interviewer: Draw it.

You: There are two planes:

• A stateless data plane handles every request from memory.
• A control plane manages config and pushes it to nodes. It is never on the request path.

Walk a request through it: DNS to a region, an L4 balancer to a node, the filter chain, then the upstream. Then watch a config change travel from the admin API to the nodes.

The pieces:

• GeoDNS or anycast sends clients to the nearest healthy region.
• An L4 balancer spreads TCP connections across nodes in every AZ. L4 means it works at the connection level and does not read HTTP.
• Gateway nodes run a non-blocking event loop — Envoy, Netty, or Spring Cloud Gateway on Reactor Netty. They do the smart L7 work, meaning they read HTTP paths, headers and tokens.
• The control plane compiles config into immutable snapshots and streams them to nodes over gRPC.
• S3 holds the last-known-good snapshots.
• The IdP publishes JWKS and an introspection endpoint.
• A regional Redis holds shared counters.
• Service discovery feeds the lists of upstream endpoints.
• Kafka takes logs, usage and spans, so logging never blocks a request.

Here is one authenticated request, end to end:

1. GET /v1/orders/42 with a bearer JWT reaches a node via DNS and the L4 balancer.
2. TLS terminates, using session resumption to skip a full handshake. The node assigns X-Request-Id and starts a trace span from traceparent.
3. The router matches against a precompiled table: first a host map, then a path trie, then method and header checks. If the route is unknown, it returns 404 without touching an upstream.
4. The JWT filter reads kid (the key ID). It finds the key in the in-memory JWKS cache. It verifies the signature, exp, nbf, iss and aud.
5. Authorisation checks orders:read against the route policy.
6. The rate-limit filter takes a token from the local bucket for (consumer, route). If the bucket is empty, it returns 429.
7. The balancer picks a healthy endpoint by least-requests or peak EWMA (a moving average of latency). It sends the request over a pooled mTLS connection and adds X-Consumer-Id.
8. Response filters run. Logs and metrics go to Kafka asynchronously. Overhead: 1–3 ms.

In the common case, nothing in steps 2–7 leaves the node. The only exception is an occasional token lease from Redis.

What's being probed: a short request path, and knowing where each millisecond goes.

Concept — L4 vs L7, and compiled lookups. An L4 balancer forwards connections without understanding HTTP. The gateway is the L7 layer that reads paths, headers and tokens. So the managed piece stays simple and fast, and the logic lives in software you control. R14 covers balancing algorithms.

A trie is a tree that walks the path one segment at a time. So matching cost depends on the length of the path, not on the 10K routes.

Takeaway: Dumb and fast at L4, smart at L7, and every per-request lookup precompiled into memory.

Deep dives

Interviewer: Why separate the planes so strictly?

You:

Nodes keep the last applied snapshot in memory and on disk. If the control plane dies, they serve config that is stale but valid. This is called static stability. It is publicly described for Envoy's xDS, Kong's hybrid mode and in AWS's own guidance.

How should config reach the nodes? There are three options:

• Nodes poll the DB. This makes the DB a hot dependency.
• Nodes poll S3 with ETags. This is simple, but propagation time equals the poll interval.
• Push over gRPC streams. This gives seconds-level propagation, and each node sends an ACK (accepted) or NACK (rejected).

I take push, with S3 as the boot source and fallback. Reconnects are jittered (spread out by a random delay), so a control-plane restart does not cause a reconnect storm.

What's being probed: the static stability principle, and push vs pull.

Concept — static stability. A system is statically stable if it keeps working, unchanged, when a dependency goes away that it uses only for changes. The gateway needs the control plane to learn new config, not to serve traffic. So losing the control plane costs only the ability to change things. R13 and R14 use the same principle; here it is the founding decision.

Takeaway: The control plane can fail; the data plane must not notice.

Interviewer: What runs on each request, in what order?

You: Two rules. Cheap rejections come before expensive work. And each filter runs after the filter that gives it what it needs.

JWT details:

• Cache JWKS with a TTL.
• On an unknown kid, refresh once, single-flight and rate-limited. Single-flight means only one refresh runs at a time, however many requests ask. This stops attackers forcing refresh storms by sending random kids.
• Pin the algorithm to RS256/ES256. Reject alg: none, and reject HS/RS confusion attacks.
• Allow about 30 seconds of clock skew on exp and nbf.

Interviewer: A customer's laptop is stolen. Their JWTs are valid for an hour.

You: That is the weak spot. A JWT cannot be revoked locally, because the gateway never asks anyone whether it is still valid. There are three levers:

• Short lifetimes: 5–15 minutes, with a refresh token that the IdP can revoke.
• A pushed deny-list of revoked jtis (token IDs), sent through the config channel. It reaches every node in under 5 seconds. Each entry is only held until that token would expire anyway.
• Opaque tokens with cached introspection for sensitive routes. The result is cached until min(exp, 60 s).

For the stolen laptop: use the deny-list now, and short lifetimes as the policy.

What's being probed: filter ordering by cost, and the stateless-token trade-off.

Concept — self-contained vs reference tokens. A JWT is like a ticket with the date printed on it. It can be checked without calling the box office, but a stolen one works until it expires. An opaque token is like a ticket number that the usher must look up. It is slower, but it can be cancelled instantly. Real systems keep tokens short-lived, so "until it expires" is a small window. They also add a small revocation list for emergencies.

Takeaway: JWTs trade revocation for speed; short lifetimes and a deny-list buy most of it back.

Interviewer: Why an event loop rather than thread-per-request?

You: A gateway mostly waits. Thread-per-request blocking (Zuul 1, or a servlet plus RestTemplate) needs one thread for each request in flight. So 10K slow upstream calls mean 10K threads, and the gateway stalls. An event loop uses one thread per core and juggles tens of thousands of connections. Java 21 virtual threads are viable for moderate QPS, but you need care around pinning (when a virtual thread gets stuck to an OS thread).

Here is the budget for the 10 ms p99:

• resumed TLS: 0.3 ms;
• parse and match: 0.1 ms;
• JWT verify: 0.1–0.3 ms;
• local rate limit: 0.05 ms;
• transform and LB: 0.1 ms;
• logging enqueue: 0.05 ms;
• the rest is slack for GC and queueing.

The rules:

• Never block the event loop — no JDBC, no blocking clients, no synchronous logging.
• Stream bodies rather than buffer them.
• Pool upstream connections.
• Tune for low GC pause.

A gateway mostly waits; an event loop waits for thousands of requests at once, as long as nothing blocks it.

Interviewer: A plan says 100 RPS. You have 24 nodes in a region.

You: Walkthrough 1 is the full answer; here it is as a gateway plugin. Use a token bucket per (consumer, route), because "100 RPS, burst 200" is a token bucket. There are three choices for where the state lives:

• Local only, at limit / nodes each. This works poorly when the balancer spreads traffic unevenly.
• Redis on every request. This is exact, but adds 0.5 ms and 200K ops/s.
• Local buckets leasing from Redis. Each node takes a batch of tokens at a time. This is within a few percent of exact, at a tenth of the Redis traffic.

onRequest(key):
  b = local[key]
  if b.tokens > 0: b.tokens--, return ALLOW
  if b.leaseInFlight: return b.failOpen ? ALLOW : DENY
  lease = redis.eval(TAKE_BATCH, key, batch=min(50, plan.rate/nodes))
  if lease == 0: return DENY (429)
  b.tokens = lease - 1; return ALLOW

Monthly quotas are counted from usage events. They are enforced with a pushed "over quota" flag. A lag of a few seconds is fine for a monthly limit.

Multi-tenancy is a hierarchy: tenant → consumers → keys → plan. Each tenant has a concurrency cap. Premium or noisy tenants get dedicated node pools.

Interviewer: Redis goes down. Open or closed?

You: Open for most plans — requests are allowed through. But each node keeps a local hard cap, so a flood cannot reach upstreams unchecked. Over-admission is limited to the leased tokens not yet used.

For a contractual limit, such as a payments API, I would make Redis-per-request a per-plan option and accept the extra half-millisecond. Fail closed on security, fail open on fairness. Authentication must never fail open. Rate limiting is not a security boundary.

Interviewer: The inventory service has a bad deploy and starts timing out.

You: A slow upstream can use up gateway resources. That failure can then cascade to unrelated routes. Naive retries make it worse, because they multiply load. So I use the layers from R14, configured at the gateway:

The incident, step by step:

1. Calls start hitting the 800 ms timeout.
2. Budgeted retries fire, but only on idempotent methods (ones safe to repeat).
3. Outlier detection ejects the worst pods.
4. The route failure rate crosses 50%, so the breaker opens. Requests now fail in microseconds instead of waiting.
5. The fallback serves cached stock or a 503.
6. The bulkhead has already kept event-loop threads and pools free for every other route.
7. After 30 s, the breaker goes half-open and sends probes. It closes again on success.

The arithmetic to say aloud: if three layers each retry three times, one user request becomes 27 calls at the bottom. So retry at one layer only.

What's being probed: stopping one failing service from taking down the platform, without retries making it worse.

Concept — the resilience stack at the edge. Each mechanism has one job:

• Timeouts limit the wait.
• Bulkheads limit the blast radius.
• Breakers stop the bleeding.
• Budgets stop retry storms.
• Outlier detection is the per-host version: it removes one sick pod while the service stays up.

R14 teaches each mechanism. The gateway is where they are configured per route, once, for every team.

Takeaway: Timeouts, bulkheads, breakers, budgets — and retries at exactly one layer.

Interviewer: How does a change reach 72 nodes safely, and how do canaries work?

You: Config compiles into an immutable snapshot. It contains listeners, routes, upstreams, consumers and plugins. Nodes apply it atomically. They build the new structures off the request path, then swap one reference.

Endpoint updates change far more often, because pods scale up and down. So they travel separately as small deltas (only the changes). That way a pod restart does not rebuild the route table.

Treat config like a code deploy

1. An engineer moves the orders-svc canary weight from 0% to 5%, sending If-Match: "v1842".
2. The control plane validates the change: schema, route conflicts, and whether the upstream exists. It writes the change and the audit entry in one transaction. It compiles snapshot v1843 to S3.
3. The rollout controller pushes v1843 to the canary node group first.
4. Each node swaps atomically. In-flight requests finish on the old table. The node sends an ACK or NACK.
5. After a bake period watching errors and latency, the controller pushes to the rest in waves — or pushes v1842 back.
6. Disconnected nodes reconnect, report their version, and receive the latest.

The canary options:

• By percentage: hash a stable user ID, so a user does not flip between versions.
• By header: serves internal testers.
• Blue-green: flip one route target in one version, and keep blue warm.
• Mirroring: copy traffic to the new version, for safe reads only.

Automated analysis compares v2 against v1 and rolls back on a regression. R16 is the general version of this.

In Spring Cloud Gateway, which I know well, the canary and resilience take a few lines:

@Bean
public RouteLocator routes(RouteLocatorBuilder rlb) {
  return rlb.routes()
    .route("orders-canary", r -> r.path("/v1/orders/**").and().header("X-Canary", "true")
        .uri("lb://orders-v2"))
    .route("orders-v1", r -> r.path("/v1/orders/**").and().weight("orders", 95)
        .filters(f -> f
          .requestRateLimiter(c -> c.setRateLimiter(redisRateLimiter()).setKeyResolver(consumerKey()))
          .circuitBreaker(c -> c.setName("orders").setFallbackUri("forward:/fallback/orders"))
          .retry(rc -> rc.setRetries(2).setMethods(HttpMethod.GET)
                         .setStatuses(HttpStatus.SERVICE_UNAVAILABLE)))
        .uri("lb://orders-v1"))
    .route("orders-v2", r -> r.path("/v1/orders/**").and().weight("orders", 5)
        .uri("lb://orders-v2"))
    .build();
}

Routes refresh at runtime through RefreshRoutesEvent, or through a custom RouteDefinitionRepository backed by the config store. A GlobalFilter with Ordered handles JWT and tenant headers.

What's being probed: whether config changes get atomic apply, staged rollout and automatic rollback.

Concept — atomic snapshot swap. Imagine a node editing its live table one entry at a time. It could serve a request using a route that points at an upstream not yet defined. Instead, build the whole table on the side and flip one pointer. Then nobody ever sees a mix, and rollback is just pointing back. Most outages come from changes, so canary waves with automatic rollback remove a major source of outages.

Takeaway: Build new config on the side, swap one pointer, roll out in waves.

Interviewer: Mobile wants one call for the home screen instead of three.

You: Simple generic fan-out, yes. The edge filters run once. Then users, orders and recommendations are called in parallel. Each call has its own timeout and breaker. The results are combined under a total deadline of 500 ms.

• If recommendations time out, return recommendations: [] with partial: true.
• If users fail, the page cannot render, so return 502.

But client-specific business logic belongs in a BFF service owned by the client team (BFF means backend for frontend). Otherwise the gateway becomes a monolith that every team must change. If many clients want flexible response shapes, that points to GraphQL federation. I cap fan-out concurrency and body sizes, because aggregation is the main source of memory pressure.

Observability in one breath:

• RED metrics (rate, errors, duration) per route and upstream;
• sampled structured logs, with all errors kept;
• W3C trace propagation;
• gateway time split from upstream time, because customers will blame the gateway for slow upstreams.

WebSockets authenticate on the upgrade request and run on a separate pool. On deploy, they drain using close frames and jittered reconnects.

Security:

• WAF first;
• size limits;
• TLS 1.2+;
• mTLS to upstreams with short-lived certs, so upstreams only trust the gateway;
• strip any client-supplied X-Consumer-Id and X-Forwarded-* headers before setting them fresh.

Failures and scale

Interviewer: Where does it break?

You:

Multi-region works like this:

• Each region runs a full data plane, Redis, and a control-plane read replica.
• The primary control plane and the Postgres primary live in one region.
• Snapshots replicate to S3 in every region.

If you lose the primary region, you promote a replica while the data planes keep serving. Rate limits are per region. Config RPO is seconds (RPO is how much recent data you can lose). Traffic RTO is under a minute (RTO is how long recovery takes).

Almost every "what if this disappears?" answer is the same: traffic keeps flowing, and something gets slightly worse. Only the stateless nodes and the balancer are truly critical. Those are spread across zones and regions.

Curveballs

Interviewer: Why build any of this? Why not a managed gateway?

You: For one team that needs a gateway, I would recommend exactly that. You get TLS, keys, throttling and logging with no fleet to run. In exchange, you accept vendor limits and per-call pricing.

Here we are the product. We have many teams and external customers. We need control over plugins and latency, and we run multi-cloud. At 17 billion requests a day, per-call pricing gets very expensive. So we self-host — but built on a proven proxy core like Envoy or Netty, never an HTTP proxy written from scratch.

What's being probed: build-versus-buy judgement, and whether you can argue against your own design.

Concept — build vs buy. Building gives you control and lower unit cost at very high scale. But it costs engineering time, and on-call duty for ever. Buying gives you speed, and someone else carries the pager. But you live with their limits and pricing. The deciders are scale, whether the thing is your product, and constraints like multi-cloud or compliance. Even when building, you assemble proven parts.

Takeaway: Buy unless it is your product or your scale makes renting too expensive; even then, build on proven cores.

Quick reference

The 60-second version

A stateless data plane handles every request from memory. A control plane manages config and is never on the request path. So a control-plane outage freezes changes but not traffic.

Nodes run a non-blocking event loop and an ordered filter chain:

• TLS and trace context;
• WAF;
• route match from a precompiled trie;
• local JWT verification or hashed key lookup;
• authorisation;
• token-bucket limits leasing from a regional Redis;
• transformation;
• load balancing behind timeouts, budgeted retries, breakers and bulkheads;
• then async logging.

All of this adds one to three milliseconds.

Config compiles into immutable, versioned snapshots. They are pushed over gRPC streams in canary waves and applied with an atomic swap. Each node ACKs, and bad changes roll back automatically. S3 is the boot source.

About 24 nodes per region, across three AZs at 1.5× headroom, sit behind anycast and L4 balancers. Traffic to upstreams uses mTLS, and each region is isolated from the others.

Walkthrough 3 — Distributed job scheduler, cron to execution

Interviewer: Design a distributed job scheduler.

You: "Scheduler" can mean very different systems. So I ask some questions first:

Interviewer: Multi-tenant internal platform. You pick the rest.

You: I will support three schedule types: cron with a time zone, one-off delayed, and fixed-rate.

There are three kinds of target: an HTTP callback, a message on a tenant's queue, or a container on our workers. All three are the same thing underneath — "dispatch a payload to an executor".

My other choices:

• Jobs fire within 2 seconds at p99 and within 10 s at p99.9.
• Delivery is at-least-once, with an idempotency key on every job. An idempotency key is a unique ID the target uses to spot and ignore repeats.
• Jobs last from 100 ms to several hours.
• We run in a primary region with a warm standby.

Interviewer: Why not crontab on a couple of servers?

You: One box is a single point of failure. If it dies, jobs silently stop. With two boxes, every job fires twice. Crontab also gives no retries, no history, no quotas, no per-job time zones, and cannot hold 20 million definitions.

The real problem is one logical clock, many machines, exactly one firing per time slot, and nothing lost when machines die. Every answer to that comes from R8's toolbox: a single leader, partitioned ownership, or the database as coordinator. I will start with the database as coordinator — the simplest correct design — and add machinery only where the numbers force it.

Interviewer: Requirements.

You: The functional requirements are:

• Create, update, pause, resume and delete job definitions.
• Schedules: cron with an IANA time zone (a standard zone name such as Asia/Kolkata), one-off, and fixed interval.
• A manual "run now".
• Per-job retry with exponential backoff and jitter. Exponential backoff means each retry waits longer than the last. Jitter adds a random delay so retries do not all arrive together.
• A timeout per attempt.
• A DLQ (dead-letter queue — a holding place for jobs that keep failing) after all retries are used up.
• A misfire policy for missed runs: FIRE_ALL, FIRE_ONCE or SKIP.
• A concurrency policy for overlapping runs: ALLOW, FORBID or REPLACE.
• Priorities and per-tenant quotas.
• Run history.

The non-functional requirements are:

• 20M active definitions and 50M executions a day, with bursts at the top of each minute.
• p99 firing latency under 2 s.
• Scheduler failover in under 15 s.
• Tenant isolation.

There are also two correctness promises that pull against each other:

• No lost jobs. A committed definition must fire.
• No double-firing in normal operation. Duplicates happen only in failure cases. They are bounded, and they carry the same idempotency key.

Interviewer: Which is it — no double-firing, or duplicates allowed? Can't you promise exactly-once?

You: There are two layers.

The scheduler creates exactly one run per (job, scheduled time). A unique key in the database enforces that.

Execution of an arbitrary side effect cannot be exactly-once. For example, a worker calls an endpoint and the call succeeds. Then the worker dies before recording it. Now nobody can tell whether the job ran. That is R0's unknown outcome.

So I promise at-least-once plus a stable key. That is effectively-once if the target honours the key, because exactly-once is at-least-once plus idempotency at the receiver, which is R3's whole argument.

What's being probed: why exactly-once delivery is impossible for external side effects, and whether you state both correctness promises.

Concept — liveness vs safety in a scheduler. "Never lose" pushes you to retry. "Never duplicate" pushes you to hold back. The honest answer is to never lose, and to make duplicates rare, bounded and harmless. You do that with an idempotency key that the target checks. Writing this down as a requirement shapes every later choice.

Takeaway: Promise "never lost" and "rarely duplicated, always de-dupable" — explicitly.

Capacity

Interviewer: Size it.

You: My assumptions:

• 20M definitions of about 1 KB each.
• 50M runs a day.
• About 60% of cron jobs sit on minute or hour boundaries.
• 500 B per run record.
• 1.1 attempts per run.
• 2 KB average dispatched payload.
• 90 days of hot history.

1. Average: 50M / 86,400 ≈ 580 runs/s.
2. Top of the minute: the busiest boundary holds 100K runs, mostly due in the first 5 s → 20K runs/s. That is a 35× peak-to-average ratio. It happens because people write 0 0 * * * far more often than 17 3 * * *.
3. Write amplification (one action causing many writes): mark the run queued, mark it running, mark it finished, insert the next run row, plus a heartbeat or two. That is about 5 writes per run. At peak, 5 × 20K = 100K writes/s. This number, not storage, is what forces sharding.
4. Storage: definitions take ~20 GB. History grows by 41 GB/day, so ~3.7 TB stays hot over 90 days. Over five years that is ~15 TB in Parquet. Logs at 500 GB/day go to object storage, never to the database.
5. Due index: only the next 10 minutes need to be in memory. At the top of the hour that is up to ~3M entries × 100 B ≈ 300 MB.

Interviewer: Midnight UTC. Lots of tenants schedule "daily at 00:00".

You: Say that is 5% of daily runs: 2.5M. Firing them all in 10 s means 250K/s. Paying for that capacity for something that happens once a day is waste.

So I provision about 50K dispatches/s and let the backlog drain in about 50 s. High-priority jobs go first through reserved capacity. Low-priority jobs get a default jitter window that spreads them out.

My planning numbers: steady at ~600/s, with spikes of 20–50K/s lasting seconds.

What's being probed: finding the number that drives the design, and shaping load rather than buying capacity for it.

Concept — spike times amplification. Averages hide the real load. Multiply the peak by the number of writes each run causes, and you get the figure that decides sharding. A short, bounded backlog is fine if you decide who waits. Priority classes protect critical jobs. Jitter spreads out "around midnight" work. Think of boarding groups at an airport instead of a wider door.

Takeaway: Size for the spike times the write amplification, then shape the spike with priorities and jitter.

API and the job specification

Interviewer: Show me the API.

You: The API has these features:

• Auth is scoped to the tenant.
• Every mutation takes an Idempotency-Key.
• Lists use cursor pagination.

The endpoints:

• POST /v1/jobs to create a job.
• GET and PATCH (with If-Match, so an update only applies to the version you last saw).
• :pause and :resume.
• Soft DELETE (marks the job deleted instead of erasing it).
• :trigger for a manual run.
• Run history.
• :cancel on a run.
• An internal Worker.Lease / Heartbeat / Complete RPC for workers.

A job definition has five parts, each answering one question: who owns it, when it fires, what it triggers, how the scheduler should behave, and who hears about failure.

{
  "name": "nightly-settlement-report",
  "description": "Builds the previous business day's settlement report",
  "owner": { "team": "payments-ops", "oncall": "slack:#payments-oncall" },
  "labels": { "domain": "settlement", "env": "prod" },

  "schedule": {
    "type": "CRON",
    "expression": "30 2 * * *",
    "timeZone": "Asia/Kolkata",
    "startAt": "2026-10-12T00:00:00+05:30",
    "endAt": null,
    "skipCalendar": "IN_BANK_HOLIDAYS"
  },

  "target": {
    "type": "HTTP",
    "http": {
      "url": "https://reports.internal/v1/settlement-report",
      "method": "POST",
      "auth": { "secretRef": "reports-api-token" }
    },
    "payload": {
      "businessDate": "{{scheduledDate}}",
      "region": "IN",
      "format": "CSV"
    }
  },

  "execution": {
    "timeoutSeconds": 1800,
    "retry": { "maxAttempts": 5, "initialBackoffMs": 2000, "maxBackoffMs": 300000, "jitter": "FULL" },
    "concurrencyPolicy": "FORBID",
    "misfirePolicy": "FIRE_ONCE",
    "priority": "NORMAL",
    "idempotencyKey": "{{jobId}}:{{scheduledAt}}"
  },

  "notifications": {
    "onFailure": ["slack:#payments-oncall"],
    "onDeadLetter": ["pagerduty:payments-ops"]
  },

  "enabled": true
}

The other schedule and target shapes:

{ "type": "ONE_OFF",    "at": "2026-10-06T14:30:00+05:30" }
{ "type": "FIXED_RATE", "every": "PT15M", "anchor": "2026-10-06T00:00:00Z" }

{ "type": "QUEUE",
  "queue": { "system": "KAFKA", "topic": "settlement.commands", "key": "{{jobId}}" },
  "payload": { "businessDate": "{{scheduledDate}}" } }

{ "type": "CONTAINER",
  "container": { "image": "registry.internal/recon:1.4.2", "args": ["--date", "{{scheduledDate}}"],
                 "cpu": "1", "memory": "2Gi" } }

every is an ISO-8601 duration — PT15M means 15 minutes. anchor fixes the grid, so runs land on :00, :15, :30 and :45 instead of drifting from whenever the job was created.

Shaping the specification

• Keep the job's kind inside target.type. A separate jobType field could disagree with it.
• Make schedule an object whose type decides its fields — a one-off needs a time, cron needs an expression and a time zone, fixed-rate needs an interval.
• Keep the target's data (payload) apart from the scheduler's own behaviour (execution).
• Leave server-assigned fields out of the request: jobId, version, status and nextRunAt come back in the response.

Build the payload from the scheduled time, never from "now". {{scheduledDate}} and {{scheduledAt}} are filled from the run's slot. If an outage delays the 2 October run until 3 October, it must still build the 2 October report — and a retry must send the same idempotency key. With "now", a late or retried run quietly does the wrong day's work.

The response adds the server-assigned fields: jobId, version: 1, status: ACTIVE and nextRunAt: 2026-10-11T21:00:00Z. The first run is 02:30 on Monday 12 October in Kolkata, which is 21:00 UTC on the previous day — and the API always answers in UTC.

Suppose a client's create request times out and the client retries. It gets the same jobId back, so there is no second nightly report.

Interviewer: What can a job actually trigger?

You: The scheduler only knows when. It holds no business logic. So every job carries a target: what to trigger, and with what data. At fire time the scheduler creates a run and hands the target to an executor — "deliver this payload here". The real work, such as building the settlement report, lives in the target system.

There are three kinds of target:

Underneath, all three are the same operation: dispatch a payload to an executor. So the scheduler core stays identical whatever the job does.

Getting targets right

• Send the idempotency key with every delivery. Execution is at-least-once, so the target must recognise a repeat and ignore it.
• Keep secrets out of the payload. The target names a secret, such as "auth": {"secretRef": "reports-api-token"}, and the worker fetches it at run time. Sign HTTP calls, or use the tenant's IAM role.
• Allowlist where HTTP calls may go, so no tenant can aim a job at internal admin endpoints (SSRF — server-side request forgery).
• Cap the payload, say at 256 KB. For anything larger, pass a pointer such as an S3 key.
• Give each target its own timeout and circuit breaker, so one team's slow endpoint cannot hold up the workers everyone else needs.

We do not run tenant code inside the scheduler process. Quartz does this in Java — a job is a class that runs on the scheduler node. That suits one application, but on a shared platform one tenant's bug or memory leak would stop everyone's scheduling. Tenant code runs only behind one of the three targets. AWS EventBridge Scheduler follows the same shape: a schedule plus a target such as a Lambda function, an SQS queue, a Step Functions workflow or an ECS task.

The simple design

Interviewer: Those are the targets. Before you shard anything — what is the simplest design that is correct?

You: One PostgreSQL database coordinates everything. There is no etcd, no Kafka and no in-memory timer. The key idea is to keep what a job is apart from each time it runs:

• schedule_details holds the definition — the job specification above. It is written only when someone creates, edits or pauses a job.
• scheduled_execution holds one row per run. Each schedule always has exactly one row waiting for its next slot, plus the rows of its past runs.

flowchart LR
  C["Client / team"] -->|create, edit, pause| API["Job API"]
  subgraph PG["PostgreSQL"]
    SD[("schedule_details<br/>definitions")]
    EX[("scheduled_execution<br/>one row per run")]
  end
  API -->|one transaction| SD
  API -->|first run row| EX
  RN["Runners × 2–3<br/>poll every second"] -->|claim due rows,<br/>insert the next row| EX
  WK["Workers"] -->|claim queued rows,<br/>lease, heartbeat, result| EX
  WK -->|payload + Idempotency-Key| T["Target<br/>HTTP / queue / container"]
  RP["Reaper"] -->|expired leases →<br/>RETRY_WAIT| EX
  EX -.->|lag, failures, DEAD| AL["Alerts"]

The definition says what the job is; the waiting row is what makes it fire.

Interviewer: Show me the tables.

You:

CREATE TABLE schedule_details (
  id         BIGINT PRIMARY KEY,          -- the jobId in the API
  tenant_id  TEXT   NOT NULL,
  name       TEXT   NOT NULL,
  schedule   JSONB  NOT NULL,             -- type, cron expression, time zone, start/end
  target     JSONB  NOT NULL,             -- HTTP / queue / container + payload
  execution  JSONB  NOT NULL,             -- timeout, retry, misfire, concurrency, priority
  status     TEXT   NOT NULL,             -- ACTIVE | PAUSED | DELETED
  version    INT    NOT NULL
);

CREATE TABLE scheduled_execution (
  id               BIGINT PRIMARY KEY,
  schedule_id      BIGINT NOT NULL REFERENCES schedule_details(id),
  scheduled_at     TIMESTAMPTZ NOT NULL,  -- this run's slot, always UTC
  status           TEXT NOT NULL,         -- see the lifecycle below
  attempt          INT  NOT NULL DEFAULT 1,
  next_attempt_at  TIMESTAMPTZ,           -- when a retry may start
  worker_id        TEXT,
  lease_token      BIGINT NOT NULL DEFAULT 0,
  lease_expires_at TIMESTAMPTZ,
  UNIQUE (schedule_id, scheduled_at)
);

-- only rows waiting to fire are indexed, so polling stays fast however big the history grows
CREATE INDEX due_idx ON scheduled_execution (scheduled_at) WHERE status = 'SCHEDULED';

UNIQUE (schedule_id, scheduled_at) means the database itself refuses a second run for the same slot, however confused the runners get. It is the last line of defence against double-firing — and it gives every run a natural idempotency key, schedule_id:scheduled_at.

A run's life:

SCHEDULED ──► QUEUED ──► RUNNING ──► SUCCEEDED
    │                       │ ├─► failed, retryable ──► RETRY_WAIT ──► RUNNING (next attempt)
    │                       │ ├─► failed, last attempt or fatal ──► DEAD
    │                       │ └─► lease expired (worker gone) ──► RETRY_WAIT
    ├─► SKIPPED   (previous run still going, concurrency policy FORBID)
    ├─► MISSED    (slot passed during an outage, misfire policy)
    └─► CANCELLED (schedule edited, paused or deleted)

Interviewer: Walk one run through it.

You:

1. Create. The API writes the definition and the first run row in one transaction. A schedule never exists without its next run — the guarantees below explain why this matters.

BEGIN;
INSERT INTO schedule_details (...) VALUES (...);                     -- id 7
INSERT INTO scheduled_execution (schedule_id, scheduled_at, status)
VALUES (7, '2026-10-11 21:00Z', 'SCHEDULED');                         -- 02:30 Kolkata
COMMIT;

2. Claim and chain. Every second, each runner runs the same transaction. The next row is inserted when a run fires, not when it finishes, so a slow or stuck run can never delay or block the next one.

BEGIN;
  -- 1. take up to 100 due rows that no other runner holds
  SELECT id, schedule_id, scheduled_at FROM scheduled_execution
  WHERE status = 'SCHEDULED' AND scheduled_at <= now()
  ORDER BY scheduled_at LIMIT 100
  FOR UPDATE SKIP LOCKED;

  -- 2. hand them to the workers
  UPDATE scheduled_execution SET status = 'QUEUED' WHERE id IN (...);

  -- 3. chain each recurring schedule's next run (computed in code from cron + time zone)
  INSERT INTO scheduled_execution (schedule_id, scheduled_at, status)
  VALUES (...)
  ON CONFLICT (schedule_id, scheduled_at) DO NOTHING;
COMMIT;

FOR UPDATE locks the rows a runner takes. SKIP LOCKED makes other runners skip those rows instead of waiting, so each due row goes to exactly one runner. "Due" is judged by the database's now(), so the runners' own clocks never matter.

3. Claim the run. Workers find QUEUED rows — and RETRY_WAIT rows whose next_attempt_at has passed — the same way, with SKIP LOCKED.

UPDATE scheduled_execution
   SET status = 'RUNNING', worker_id = 'w-1',
       lease_token = lease_token + 1,
       lease_expires_at = now() + interval '30 seconds'
 WHERE id = :id AND status IN ('QUEUED', 'RETRY_WAIT')
RETURNING lease_token;          -- zero rows: another worker got it first

The lease says how long the worker may hold the run. The lease token is a fencing token: a number that goes up on every claim, so a write from an older claim can be recognised and refused. R8 teaches fencing; this is where it earns its keep.

4. Execute. The worker calls the target with the payload and Idempotency-Key: 7:2026-10-11T21:00:00Z, built from scheduled_at. A long job sends a heartbeat every 10 seconds: UPDATE … SET lease_expires_at = now() + interval '30 seconds' WHERE id = :id AND lease_token = :mine.

5. Record. UPDATE … SET status = 'SUCCEEDED' WHERE id = :id AND lease_token = :mine. A failure writes RETRY_WAIT with a backoff, or DEAD after the last attempt.

6. Reap. The reaper looks for status = 'RUNNING' AND lease_expires_at < now(). Each such run gets RETRY_WAIT, attempt + 1, a jittered next_attempt_at and a bumped lease_token, which makes the vanished worker's claim worthless.

Step through it below. Each tab is a scenario: the happy path first, then two runners racing, crashes, failing targets, edits and an outage.

Interviewer: Why do the workers read from the table? Wouldn't a queue be cleaner?

You: A queue is the next step up, but it adds a gap. Suppose the runner commits QUEUED and then crashes before publishing to the queue. The run is stranded: the table says queued, but no message exists. You would then need a sweeper that re-publishes rows stuck in QUEUED — the outbox pattern from R4. Reading from the table has no such gap. Every hand-off is a committed row, so whichever process dies, the next one carries on from the table.

Interviewer: State precisely what this design guarantees.

You: Four guarantees, each enforced in one specific place:

BEGIN;
INSERT INTO processed_requests (idempotency_key, result)
VALUES ('7:2026-10-11T21:00:00Z', NULL)
ON CONFLICT (idempotency_key) DO NOTHING;   -- 0 rows: already done, return the stored result
-- ... build the report, move the money, send the file ...
UPDATE processed_requests SET result = ... WHERE idempotency_key = ...;
COMMIT;

Exactly one run per slot, delivered at least once, with an exactly-once effect — the last part is a contract the scheduler shares with the target.

What's being probed: whether the simplest design is still correct under concurrency, and whether every hand-off is durable.

Concept — the chain of next runs. A recurring schedule is a chain: each run, as it fires, creates the next. The chain is only safe if creating the next link is atomic with claiming the current one — one transaction, both or neither. A unique key on (schedule_id, scheduled_at) makes each link impossible to duplicate. Locks with SKIP LOCKED let any number of runners and workers share one table as a work queue. Leases and tokens make a vanished worker's run recoverable and a zombie worker harmless.

Takeaway: Claim and chain in one transaction, let a unique key refuse duplicates, and make every hand-off a committed row.

Scenarios — what can happen while it runs

Interviewer: Now break it. What can go wrong while it is working?

You: Here is each situation, what happens, and what protects us:

Every failure ends one of three ways: a little late, retried with the same key, or DEAD with someone paged — never silently lost, never knowingly doubled.

What's being probed: whether you can walk failures through the design instead of asserting it is "highly available".

Concept — failure walk-throughs. For each component, ask what happens if it dies before its commit, after its commit, or comes back after you thought it was dead. Transactions cover "before", committed rows cover "after", and fencing tokens cover "came back". Whatever is left — an action that happened but was never recorded — is handled by idempotency at the receiver.

Takeaway: Walk every component through "dies before commit, dies after commit, comes back late", and name the mechanism for each.

Shortcomings, and how to fix them

Interviewer: It is correct. Where does it fall short?

You: It is right for a single company's jobs or an internal platform up to roughly a thousand fires a second. Against our targets — 20K runs a second at the top of the minute — these break first:

Start with the simple design, and add each fix only when a metric says you need it — schedule lag for the timing wheel, write load for sharding, lock waits for partitioned ownership, tenant complaints for fairness.

What's being probed: whether you can see your own design's limits and grow it step by step, rather than starting with the most complex version.

Concept — evolve, don't front-load. Each fix trades simplicity for capacity: shards bring routing and rebalancing, ownership brings a coordination service and fencing, a broker brings a second source of truth to keep in step. Interviewers reward a design that is correct first and then scaled by named bottlenecks, because that is how real systems are built and kept running.

Takeaway: Be correct with the fewest moving parts, then add machinery one measured bottleneck at a time.

Scaling up — the full design

Interviewer: We do need the 20K-a-second spike. Show me the scaled-up version.

You: It keeps the same two tables, the same lifecycle and the same unique key. What changes is who finds due rows, how they reach workers, and how much one database has to carry. These are the fixes from the table above, in detail.

In the scaled-up design, workers no longer write to the database directly; they report through a small Worker.Lease / Heartbeat / Complete RPC.

Interviewer: Why is there a leaseToken in the worker completion?

{ "executionId": 1042, "attempt": 2, "leaseToken": 4711,
  "outcome": "FAILED", "error": { "code": "UPSTREAM_503", "retryable": true } }

You: It is the same fencing token as in the simple design — a number that goes up each time someone new takes ownership, so old owners can be detected and rejected.

Every claim increments it. The server applies a heartbeat or completion only if the token still matches. So a worker that paused past its lease and then wakes up cannot overwrite the result of the worker that took over. R8 teaches fencing; this is where it earns its keep.

Interviewer: The data model.

You:

Both tables for one schedule live on the same shard, so claiming a run and inserting the next one is still a single local transaction. The unique key on (schedule_id, scheduled_at) is still the last line of defence against double-firing.

Interviewer: 100K writes a second. Why not Cassandra or DynamoDB from day one?

You: The hot path does three things, and they must happen atomically (all together or not at all):

• Claim the due row only if it is still SCHEDULED — a compare-and-set (CAS), meaning "update only if the value is still what I expect".
• Insert the next row if it does not exist.
• Check the shard epoch.

SQL does that with a transaction, a unique key and SKIP LOCKED. A wide-column store needs a lightweight transaction or a conditional write for each step. That is slower and harder to combine.

The data is only 20 GB. So I shard for write throughput, not size. 1,024 logical shards over several Postgres clusters can handle 100K writes/s with batching. I would move to time-bucketed Cassandra or DynamoDB only if write volume or multi-region needs outgrew that.

What's being probed: whether keys and indexes encode the correctness rules, and whether you choose a store by the operations it must do.

Concept — natural keys and choosing by operation. A run is identified by which job and which instant. Making that the primary key makes run creation idempotent at the one place every writer meets. This is R3's idempotency boundary pushed into the schema. The store question is: which operations must be atomic, and which store makes them cheap? Size then decides how many shards you need, not which technology (R10).

Takeaway: Let a unique constraint be the last line against duplicates, and pick the store that makes your critical atomic step simple.

The scaled-up architecture

Interviewer: Draw it and walk a job firing.

You: The split is "deciding when" versus "executing". Every arrow between components is a durable hand-off, so nothing is held only in memory.

Walk a job from definition through the shard owner, the dispatcher and Kafka to a worker. Then kill a scheduler and watch its shards move. (This animation uses the older names: "jobs" is schedule_details and "runs" is scheduled_execution.)

The pieces:

• The stateless Job API, as before. It validates the cron and zone and writes the definition with its first run row.
• The sharded schedule_details and scheduled_execution tables, still the source of truth.
• etcd, holding shard leases with epochs. A lease is a lock that expires on its own after a set time.
• Scheduler nodes — the runners, grown up. Each owns a subset of the 1,024 shards. They find due rows, claim them and chain the next run.
• The Redis due index, or an in-memory timing wheel.
• A dispatcher. It applies per-tenant buckets, concurrency caps and priority.
• Kafka priority topics.
• Worker pools. They claim a run with a lease, execute it, send heartbeats and report the result.
• A lease reaper and retry timer, which finds runs whose lease expired and schedules retries.
• The DLQ.
• An events topic into ClickHouse for history and metrics.

A job firing:

1. Scheduler S1 owns shard 37 at epoch 12. Every few seconds, it loads SCHEDULED rows with scheduled_at <= now() + 10 min into its wheel.
2. At fire time, it pops due entries, up to 500 at once.
3. It runs one transaction per batch, exactly like the simple runner plus one check: UPDATE scheduled_execution SET status = 'QUEUED' WHERE id IN (…) AND status = 'SCHEDULED', which is a compare-and-set; insert each schedule's next row with ON CONFLICT DO NOTHING; and check that the shard epoch is still 12.
4. The dispatcher checks the tenant's bucket and concurrency count. It publishes to tasks.normal; the QUEUED row is the outbox, so if Kafka is down the publish is simply retried. If the tenant is over quota, it sets next_attempt_at a few seconds out instead of dropping the run.
5. A worker consumes the message and claims the run:

UPDATE scheduled_execution
   SET status = 'RUNNING', worker_id = 'w-88',
       lease_token = lease_token + 1, lease_expires_at = now() + interval '30 seconds'
 WHERE id = :id AND status IN ('QUEUED', 'RETRY_WAIT')
RETURNING lease_token;
-- zero rows → another worker has it; ack and skip

6. It calls the target with idempotency key schedule_id:scheduled_at and a per-attempt timeout. For long jobs, it sends a heartbeat every 10 s.
7. On success, it runs SET status = 'SUCCEEDED' WHERE id = :id AND lease_token = :mine, emits RunSucceeded, and commits the Kafka offset.

One subtlety on create. A job due 30 seconds from now would sit invisible until the next refill. So when a new job's first run lands inside the lookahead window, the Job API also writes it straight into the due index. The periodic refill and a slow SQL sweep catch anything that slips through.

What's being probed: separating "deciding when" from "executing", with every hand-off durable.

Concept — the run row as the hand-off. The scheduler only decides that a run exists. Workers do the heavy, variable work. A durable queue sits between them, so a slow job never delays firing. Every step records its state before moving on. So whichever component dies, the next one resumes from the row. A QUEUED row is R4's outbox — the intent to publish, committed together with the state change.

Takeaway: The scheduler creates runs, queues and workers execute them, and the database records every hand-off.

Deep dives

Interviewer: How do you find which of 20M jobs are due each second, at p99 under 2 s, through the top-of-minute spike?

You:

My choice has two levels:

• SQL is the source of truth.
• Every 5 s, each shard owner loads the next 10 minutes into a timing wheel.
• The wheel ticks every 100 ms to 1 s.
• A slower sweep looks for SCHEDULED rows with scheduled_at < now() − 30 s, so it catches anything the fast path missed.

while (ownsShard(shard, epoch)) {
    if (now().isAfter(nextRefill)) {
        executionRepo.findDue(shard, now().plus(LOOKAHEAD))
               .forEach(e -> wheel.addIfAbsent(e.id(), e.scheduledAt()));
        nextRefill = now().plusSeconds(5);
    }
    for (Entry e : wheel.tickAndCollectDue(now())) {
        fireInTx(shard, epoch, e.executionId(), e.fireAt());   // claim + insert next row, batched
    }
    sleep(Duration.ofMillis(100));
}

With batches of 500 per transaction, 50K fires a second becomes about 100 transactions a second across all shards.

Interviewer: That is a lot of moving parts. Why not keep the simple design's polling?

You: Under about 1K jobs a second, I would — that is exactly the simple design above. At 50K fires a second, three things start to hurt: the polling query, the hot end of the scheduled_at index, and the lock churn. Start with SKIP LOCKED, and add the wheel when the metrics say polling is the bottleneck.

What's being probed: standard timer structures, combining a fast path with a durable source of truth, and admitting the simple option is right at smaller scale.

Concept — timing wheels and SKIP LOCKED. A timing wheel is like a clock face made of buckets. Inserting a task drops it into slot (fireTime / tick) mod size in O(1). Each tick fires one slot. Stacked wheels move far-future tasks down to finer wheels as their time gets closer. Because the wheel forgets everything on restart, it is only a short-horizon cache over the database. SKIP LOCKED lets many pollers use a plain table as a safe work queue. That works until physics gets in the way, because every poll scans the same hot end of the index.

Takeaway: Database for truth, timing wheel for the next few minutes, sweep for safety — and SKIP LOCKED until load says otherwise.

Interviewer: Multiple scheduler nodes. How does each due job fire exactly once?

You: There are three options:

• A single leader with hot standbys. This is the simplest story. But it caps throughput, and failover pauses everything.
• Leaderless competing pollers — the simple design. These need no coordination service. But they make the database the coordinator.
• Partitioned ownership with leases. This scales horizontally, and a failure only touches that node's shards.

I take the third, with defence in depth (several layers of protection):

• 1,024 logical shards over ~20 nodes, so rebalancing moves small units.
• Ownership lives in etcd under a 10-second lease. Each acquisition increments an epoch, which is a monotonic (always increasing) fencing token.
• Fencing: every fire transaction checks the shard epoch inside the same DB transaction. So a stale owner's writes fail.
• Idempotent run creation: the (schedule_id, scheduled_at) key with ON CONFLICT DO NOTHING.
• CAS on the claim (WHERE status = 'SCHEDULED'), so two nodes cannot both claim the same run.

The failover, and the zombie

1. S1 owns shards 0–127. It renews its lease every 3 s against a 10 s TTL (time to live).
2. S1 crashes, or gets cut off from etcd by a network partition. Its renewals stop.
3. After the TTL, etcd deletes its keys. Watchers see this.
4. S2 acquires shard 37 at epoch 13.
5. S2 rebuilds the due index from SQL. It does not blindly trust anything in Redis.
6. Rows that fell due during the 10–15 s gap are simply overdue SCHEDULED rows. S2 fires them. For longer gaps, it applies the misfire policy.
7. If S1 was alive but partitioned, its writes carry epoch 12. The DB rejects them. The unique key stops duplicate runs anyway.

Interviewer: If etcd already guarantees one lease holder, why the DB checks?

You: Because a lease only tells the holder what to believe. A process that paused past its TTL does not know its lease has expired.

A lease is a promise; the fencing check at the database is the enforcement. This is the argument in Martin Kleppmann's well-known analysis of distributed locks, and it is the core of R8. The unique key and the claim CAS are seatbelts, in case fencing itself has a bug.

What's being probed: that distributed locks are only advisory and must be enforced at the resource.

Concept — partitioned ownership plus fencing. Cut the work into many small shards. Give each shard one owner at a time, recorded in a consensus store. Many small shards make rebalancing smooth. The danger is the zombie: a node that froze, lost its lease, and wakes up still acting as owner. So every write carries its epoch, and the database refuses older ones.

Takeaway: Leases decide who should own work; fencing tokens enforce it where the data lives.

Interviewer: A worker takes a job and crashes halfway.

You: The rules first.

• Dispatch is at-least-once. The Kafka offset commits only after the worker records the result.
• Leases default to 30 s, with a heartbeat every lease/3: UPDATE scheduled_execution SET lease_expires_at = now() + 30s WHERE id = ? AND lease_token = ?. So long jobs send heartbeats instead of getting long leases.
• Every worker write carries lease_token. Where the target can check it, the token is passed to the target too.
• The worker enforces a per-attempt timeout. Lease expiry is the server-side backstop.
• The result is effectively-once. Each run has a stable key that stays the same across retries. When the target is our own database, the effect and the status go in one transaction, which is truly exactly-once for that store. Kafka's transactions only cover Kafka-to-Kafka.

The crash:

1. Worker w-88 holds run R at lease_token=5 and stops sending heartbeats.
2. The reaper for R's shard selects status='RUNNING' AND lease_expires_at < now() FOR UPDATE SKIP LOCKED.
3. R is on attempt 1 of 5. The reaper sets RETRY_WAIT, attempt=2, and next_attempt_at = now + backoff with full jitter. It also bumps lease_token to 6, which invalidates the old lease.
4. The retry timer re-dispatches the run. w-91 claims it at lease_token=7.
5. If w-88 wakes up and reports with token 5, its update matches zero rows. The idempotency key protects the target.
6. At maxAttempts, the run goes DEAD and moves to the DLQ, and the tenant is alerted.

The states are the same lifecycle as in the simple design; only the hand-off from QUEUED to a worker now travels through Kafka.

Over a network, you cannot tell a dead worker from a slow one. So the lease sidesteps the question:

• Assume the worker is dead when its heartbeat stops.
• Fence off the old owner.
• Let the idempotency key absorb the slow-but-alive worker that finishes anyway.

Interviewer: A downstream is down for ten minutes and 200K jobs target it.

You: Backoff is min(maxBackoff, initial × multiplier^(attempt−1)) with full jitter. Full jitter means a uniformly random wait between zero and that value. So when the downstream recovers, retries do not arrive in synchronised waves.

Retries are not sleeps inside workers. A failed run is written as RETRY_WAIT, and the same due-index machinery re-dispatches it. So workers stay free, and retries survive restarts.

Errors are classified:

• Timeouts, 5xx and 429 are retried.
• Validation and auth failures go straight to the DLQ.

A circuit breaker per target host pauses dispatch when that host fails more than half its calls in a minute. A circuit breaker is a switch that stops calls to a failing service for a while. This way we stop burning attempts. When the breaker half-opens (lets a few test calls through) and they succeed, the retries arrive spread out, not as a 200K wall. R14 covers backoff, jitter and breakers in general.

Interviewer: Tenant A schedules 2M jobs at midnight. Tenant B's critical payment job is due the same second.

You: I use several tools together:

• Priority topics high, normal and low, consumed with weights of roughly 6:3:1, plus reserved capacity for high.
• A per-tenant token bucket in the dispatcher. Over-limit runs are deferred, not dropped, which keeps the "never lost" promise.
• A per-tenant concurrency counter. It is reconciled periodically against RUNNING rows, because counters drift when workers crash.
• Partition keys of tenant_id + job_id for very large tenants, so one tenant does not hot-spot a partition.
• Dedicated pools for the most critical tenants.
• An optional jitterSeconds on schedules, on by default for low priority. 2.5M fires spread over 60 s is about 40K/s.

So A's runs defer a few seconds at a time, while B's job takes reserved high-priority capacity.

What's being probed: retries that help recovery instead of causing a second outage, and stopping one tenant from starving another.

Concept — durable retries and fairness. A retry stored as state with a due time is just another scheduled run. So it gets the scheduler's durability for free. Fairness uses three different tools. Buckets cap each tenant's rate. Priorities order the work that is allowed through. Bulkheads (separate, walled-off capacity) give critical tenants their own resources. Deferring over-quota work keeps the no-loss promise.

Takeaway: Back off with jitter, stop calling a target that is clearly down, and rate-limit, prioritise and isolate per tenant — deferring, never dropping.

Interviewer: "Every day at 02:30 New York time." What happens on DST change days?

You: Store the cron and the IANA zone. Compute the next fire in local time with a library such as Spring's CronExpression over ZonedDateTime. Convert that to a UTC instant and store it as the next row's scheduled_at.

Compute only the next instance. Compute it from scheduled_at, not from now(), so drift never builds up.

Governments change DST rules. So keep tzdata (the time-zone rules database) current, and recompute the affected waiting rows when it changes.

On clock skew (machines' clocks disagreeing slightly):

• Fire decisions use NTP-synced host clocks. But correctness never depends on comparing clocks across machines. It comes from unique keys, CAS and lease tokens.
• One authority judges lease expiry: the database's now().
• Workers measure with a monotonic clock (one that never jumps backwards). They treat their own lease as expired at two-thirds of TTL, and stop side effects if a heartbeat fails.
• Use NTP slewing (adjusting the clock gradually), not stepping (jumping it). A big backward jump only delays firing.

Missed runs: a run counts as misfired if it is more than a threshold late, 60 s by default. The policies:

• FIRE_ALL creates every missed slot. Hourly accruals need this. It is capped at about 100 and rate-limited.
• FIRE_ONCE, the default, fires one run now and records the rest as MISSED.
• SKIP waits for the next slot.

One-off jobs always fire on recovery, unless they carry an expireAfter.

What's being probed: treating time as a domain with sharp edges, and keeping correctness out of clocks.

Concept — wall-clock time vs instants. An instant is a point on one global timeline. "02:30 New York" maps to an instant through rules that change twice a year, and sometimes by government decree. So store the user's intent, schedule in UTC instants, and define a policy for the odd days. Physical clocks disagree slightly. So one authority judges leases, and monotonic clocks measure durations. This is the same discipline as R26's business dates, which are never your server's midnight.

Takeaway: Store intent in local time, schedule in UTC instants, and keep correctness out of clocks.

Interviewer: Quickly — how do users know their jobs are healthy?

You: We measure:

• Schedule lag (dispatched_at − scheduled_at) per shard.
• Due backlog.
• Consumer lag per priority.
• Success, retry and DLQ rates per tenant.
• Lease expirations per minute (these signal crashes or GC pauses).
• Ownership changes.

Alerts fire on lag p99 above 5 s, on any shard unowned for 30 s, and on DLQ spikes. There is also a per-job dead man's switch: it fires when an expected success does not arrive by a deadline. This matters because the worst scheduling failure is silence. R15 covers alerting on absence.

Failures and scale

Interviewer: Where does the scaled-up design break?

You:

When etcd is down, the scheduler stops firing rather than risk firing twice, because late is recoverable and a duplicate payment is not.

Interviewer: The primary region goes down.

You: The standby region has async DB replicas, mirrored Kafka and idle schedulers. We promote the DB. The standby schedulers take the shards in their own etcd. The misfire policy handles the gap.

RPO (how much data we can lose) equals the replication lag. RTO (how long recovery takes) is minutes. But there is a trap.

Fencing only works inside one consensus domain

Each of the two regions has its own etcd. Their epochs cannot be compared, so a split brain (both regions thinking they are in charge) can double-fire. The options:

• Controlled failover, decided by a human.
• Shard epochs in a globally consistent store, at a latency cost.
• Active-active, with each tenant's jobs firing only in a home region.

Meanwhile, idempotency keys contain the damage.

What's being probed: failing safe over failing dangerous, and seeing that single-region fencing does not extend across regions.

Concept — failing safe and consensus domains. Choose the harmless failure. A scheduler that cannot prove it owns a shard stops. That produces lateness instead of duplicates. A fencing token only means something inside the consensus system that issued it. Across regions, you have three choices: a human decides, a global store issues the tokens, or partitioning removes the conflict — R13's home-region idea.

Takeaway: Fail toward "late" rather than "twice", and across regions use controlled failover or home regions.

Curveballs

Overlapping runs, edits with a run in flight, and missed slots are covered in the scenarios table above.

Interviewer: On AWS with managed services? And how do you test correctness?

You: On AWS:

• EventBridge Scheduler for triggers. It publicly supports cron, rate and one-time schedules, with time zones and flexible windows.
• SQS, with visibility timeouts acting as leases.
• Lambda or ECS workers.
• DynamoDB for state.

The cost is less control over fairness and cost at very high volume.

Testing:

• Property tests for cron and DST across zones.
• Fault injection: kill schedulers and workers, pause processes past the lease TTL, and partition etcd.
• While doing that, continuously check the invariants (rules that must always hold): no lost runs, no duplicate run rows, and bounded duplicate executions.
• Jepsen-style tests for fencing.

Distributed systems fail in the gaps between components. So you write the invariants down, and break the system on purpose while checking them.

Quick reference

The 60-second version

Start simple. A Job API writes each definition to schedule_details together with its first run row in scheduled_execution. Two or three runners poll every second with FOR UPDATE SKIP LOCKED. In one transaction each claims due rows, marks them QUEUED, and inserts each schedule's next run. A unique key on (schedule_id, scheduled_at) refuses duplicates.

Workers claim queued rows with a lease and a fencing token, call the target with an idempotency key built from scheduled_at, and send heartbeats for long jobs. A reaper retries runs whose lease expired. Failures retry with jittered backoff, then go DEAD and page the owner. Missed slots follow a per-job misfire policy.

That is correct up to roughly a thousand fires a second. Past that, shard both tables by schedule_id, give each shard one owner through etcd leases with epoch fencing, load the next ten minutes into a timing wheel, dispatch through Kafka with the row as the outbox, and add per-tenant priorities and quotas. When coordination is lost, the system fails toward late, never twice.

Walkthrough 4 — Distributed key-value store, Dynamo-style at petabyte scale

Interviewer: Design a distributed key-value store.

You: A few answers change the whole shape of the design, so I'll ask those first:

Interviewer: Assume the simplest reasonable answers.

You: Then the API is get, put and delete, with a consistency level chosen per request. Keys are up to 256 bytes. Values are up to 1 MB, typically 10 KB.

We hold about 1 PB today and a few PB in five years. The load leans towards reads, 70/30. The store is AP by default with tunable consistency. AP means it stays available during a partition, even if copies briefly disagree. Each request picks ONE, QUORUM or ALL.

It runs in several datacentres, with async cross-region replication, so remote copies update in the background. The target is p99 under 10 ms inside one DC at QUORUM. There are no cross-partition range scans and no multi-key transactions. AP, point lookups and petabyte scale point to the Dynamo family. Naming the family gives me a known checklist for the rest of the hour.

What's being probed: finding the questions that change the design, and recognising the system family.

Concept — design-forking questions and system families. Some questions fork the design into different paths: - "Range scans?" decides hash versus range partitioning. - "AP or CP?" decides leaderless quorums versus a leader per shard. - "CAS?" decides whether you need consensus at all.

Storage designs fall into a few families: - Leaderless replicated: Dynamo, Cassandra, Riak. - Leader-per-shard consensus: etcd, TiKV, CockroachDB. - Ordered range-partitioned: Bigtable, HBase.

When you name one, you inherit its building blocks and its trade-offs.

Takeaway: Ask the forking questions, then name the family you are building.

Interviewer: Requirements.

You: The functional side is tiny:

• put(key, value, [context]).
• get(key), which may return several conflicting versions.
• delete as a tombstone — a marker that says "this key was deleted", stored like a normal write.
• A consistency level per request.
• An optional TTL (time to live, after which the key expires).
• Membership changes without downtime, so nodes can join or leave while the store runs.

The real spec is non-functional:

• Writes succeed even with some replicas down, at 99.99%+ availability.
• Thousands of nodes and petabytes of data.
• No acknowledged write is lost to one node or disk failure. The replication factor is 3, so each key has three copies.
• Single-digit ms p99.
• Tunable consistency. It is strong when R + W > N. Here N is the number of copies, W is how many must confirm a write, and R is how many must answer a read.
• No master in the data path.
• Self-healing.
• Rolling upgrades and observable repair.

Out of scope: SQL, joins, secondary indexes, multi-key ACID, and objects over 1 MB. Large objects belong in a blob store, with a pointer kept here.

Interviewer: A lot of teams want strong consistency. Why not make it CP?

You: It depends on the data, which is why I asked. During a partition you have two choices. You accept writes on both sides, or you refuse some writes to stay consistent.

A cart or a session store should never refuse a write. A stale read is cheap; a lost sale is not. A lock or a balance must never show two truths.

So I don't pick once for everything. The main store is AP with tunable consistency per request, and QUORUM with N = 3 is strong enough for most callers. Keyspaces that truly need linearizability or compare-and-set go to a separate Raft-based tier. Raft is a consensus protocol: the replicas agree on one leader and one order of writes. Sending only those keyspaces there is better than slowing every write in the main store.

What's being probed: CAP as a choice per use case, not a global switch.

Concept — CAP and PACELC. CAP says that during a partition you choose consistency or availability. PACELC adds that even without a partition you trade latency against consistency, because waiting for more replicas is slower. Tunable consistency lets each request choose its own point on that curve. R0 and R10 carry the theory.

Takeaway: Make consistency a per-request dial, and send true CP needs to a consensus system.

Capacity

Interviewer: Keys, traffic, nodes.

You: My assumptions:

• 1 PB of logical data (before copies).
• About 10 KB per record, including metadata.
• N = 3.
• 500K reads and 200K writes a second on average, with peaks at 3×.
• 5% of writes create new keys.
• 8 TB usable per node. Each node has 16 TB of NVMe, kept half full so compaction has room to work.
• +30% on disk for compaction and tombstones.
• Bloom filters at 10 bits per key.

1. Keys: 10^15 / 10^4 = ~100 billion.
2. Peak client ops: 1.5M reads + 600K writes = 2.1M/s.
3. Replica ops: writes × N = 1.8M; QUORUM reads touch R = 2 replicas (one returns data, one returns a digest) = 3.0M; ~4.8M replica ops/s.
4. Write bandwidth at peak: 6 GB/s logical, 18 GB/s replicated.
5. Growth: 10K new keys/s × 10 KB = 8.6 TB/day logical; assume TTL and deletes remove 80%, so ~0.6 PB/year net — about 4 PB in five years.
6. Nodes today: 1 PB × 3 × 1.3 / 8 TB ≈ 500; in five years, 15.6 PB / 8 TB ≈ 2,000.
7. Per node: 4.8M / 500 ≈ 9.6K ops/s. Comfortable.

The cluster is storage-bound, not CPU-bound. Disk sets the node count, and the QPS per node ends up modest. So we optimise for density.

The memory budget works out:

• Bloom filters fit: 100B keys × 3 × 10 bits ≈ 375 GB cluster-wide, ~0.75 GB a node.
• Memtables take 1–2 GB.
• Index summaries and the key cache take 2–4 GB.
• The rest is page cache, on nodes with 64–128 GB.

Network: about 36 MB/s in and 30 MB/s out per node. That leaves a 10–25 Gbps NIC plenty of room for streaming and repair. This matters, because rebuilding a node moves terabytes.

What's being probed: the hidden multipliers in estimation, and headroom for background work.

Concept — amplification factors. The clients' numbers are not what the cluster sees: - Writes multiply by N. - Quorum reads multiply by R. - Bytes on disk multiply by compaction and tombstone overhead.

Then ask which resource runs out first — here, disk. Leave headroom on network and disk. For example, a design that uses 90% of the NIC for clients falls over the first time a node is rebuilt. R10 covers the Bloom filter itself.

Takeaway: Multiply by replication and overhead, find the resource that sets the node count, and keep headroom for repair.

API and data model

Interviewer: The API?

You: In reality it is a binary protocol. For readability I'll show an HTTP facade:

• GET, PUT, DELETE /v1/kv/{key}?consistency=QUORUM.
• A capped batch get.
• GetTokenMap() for partition-aware drivers, which route each request to the right node themselves.
• Admin calls: AddNode, DecommissionNode, Repair.

PUT /v1/kv/cart:user42?consistency=QUORUM&ttl=86400
X-KV-Context: a8Fz...        (opaque vector clock from the previous read)
Idempotency-Key: 6f1c-...

HTTP/1.1 200 OK
X-KV-Acks: 2/3
X-KV-Context: b91Q...

In vector-clock mode, a read can return several values plus a context. A vector clock is version metadata that records which writes each version has seen.

If the store can hold concurrent versions, the API has to say so honestly. So before writing, the client tells the server which version it read, the way If-Match carries an ETag. Otherwise the server cannot tell "updating what I saw" from "writing blind".

Interviewer: A put times out. Did it happen?

You: Unknown. There are two different errors:

• UnavailableException means there were not enough live replicas to even try. The write definitely did not happen.
• TimeoutException means the coordinator tried, but fewer than W replicas acked in time. The coordinator is the node handling this request. The write may have landed on some replicas. If so, it will spread later through read repair, hints or anti-entropy (background repair that compares replicas).

A timeout is not a failure; it is an unknown outcome. This is R0's central problem.

So the client retries idempotently or reads the value back. Idempotent means repeating the request has the same effect as doing it once. A same-value put is naturally idempotent under last-write-wins. The Idempotency-Key also de-duplicates retries at the coordinator. This is R3 applied to storage.

Interviewer: What does each node persist?

You:

[token 8B][key_len][key][timestamp 8B][flags: tombstone|ttl][ttl][vclock_len][vclock][value_len][value]

Every record carries its own timestamp and tombstone flag. This is because replicas merge versions cell by cell.

Interviewer: Why LSM rather than a B-tree?

You: With an LSM tree, a write is just a commit-log append plus a memtable insert. A memtable is a sorted in-memory table that is later flushed to disk as an SSTable. So writes get high throughput on any disk. Immutable SSTables are also easy to stream and snapshot, which matters for rebalancing and repair.

The price is read amplification (a read may check several files) and background compaction (merging files). Bloom filters and the compaction strategy keep both bounded.

A B-tree wins for read-heavy, update-in-place workloads, where low space amplification matters more than write throughput. R10 and R11 compare the engines in general.

What's being probed: the metadata a replicated store needs beyond the data itself.

Concept — metadata for convergence. A single-node database needs only the value. A replicated one also needs: - a timestamp or vector clock, to order versions; - a tombstone, because an absent row cannot replicate; - hints, for missed writes; - a token map, so every node knows who owns what.

Each one exists to solve one failure mode.

Takeaway: In a replicated store, every record carries what it needs to be merged later.

High-level design

Interviewer: Draw it.

You: There is no master: every node holds the full ring, and whichever node receives a request coordinates it. Walk a put fanning out to three replicas, then a quorum read with a digest mismatch, then a replica dying and a hint replaying when it comes back.

The pieces:

• A partition-aware driver. It caches the token map and sends each request straight to an owning replica, which saves a hop. Simple clients can use a load-balancer path instead.
• The coordinator. This is a role per request, not a special node. It builds the preference list (the ordered list of replicas for the key), fans out, and waits for R or W answers. It also resolves versions, repairs, and writes hints.
• Replicas A, B, C. These are the first three distinct physical nodes clockwise on the ring, spread across racks.
• Node D, outside the list. It takes writes for a down replica under sloppy quorum, where a stand-in node accepts writes for a missing one. It also receives streams during scale-out.
• Gossip with a phi-accrual detector. Gossip is nodes passing state to random peers. Phi accrual is a failure detector that scores how suspicious a silence is.
• The LSM engine on each node.
• Anti-entropy repair with Merkle trees.
• A remote DC ring, fed by one forwarded copy per DC.

Interviewer: A put and a get, end to end.

You: First the put, with N = 3 and W = 2:

1. The driver computes murmur3("cart:42") and sends the request to owner B, which coordinates.
2. B builds the rack-aware preference list [A, B, C] and assigns a timestamp.
3. B sends the write to all three in parallel.
4. Each replica appends to its commit log (group commit every ~10 ms), inserts into the memtable and acks.
5. At two acks the client gets success.
6. The third ack arrives later, or the coordinator writes a hint.

Now the get, with R = 2:

1. The coordinator picks the two fastest live replicas by recent latency.
2. It asks B for the data and asks C only for a digest (a hash of the value).
3. Each replica checks the memtable, then SSTables from newest to oldest. It skips any SSTable whose Bloom filter says "not here".
4. If B's data hashes to C's digest, the coordinator returns it.
5. If not, it fetches C's full value and picks the newest (or keeps siblings — the conflicting versions). It returns that and writes the winner back to the stale replica. This is read repair.

Blocking read repair waits for that write-back before replying. So a later QUORUM read cannot go back in time. R6 teaches read repair, and its demo shows the digest mismatch.

What's being probed: a symmetric, masterless architecture, and tracing the data path when replicas disagree.

Concept — symmetric nodes and digest reads. Every node runs the same code and plays every role, so there is no master to fail over. The price is that every node must know the layout. That is why the token map is small and gossiped.

Reading one value plus one hash halves read bandwidth. Also, every read of a key whose replicas disagree heals that key as a side effect.

Takeaway: "Coordinator" is a role, not a node; read one value plus a digest, and repair on mismatch.

Deep dives

Interviewer: How do you spread 100 billion keys over 500 nodes? Why not hash(key) % n?

You: Because changing n from 500 to 501 remaps almost every key. At a petabyte, that is catastrophic.

Consistent hashing places keys and nodes on a ring, and each key belongs to the next node clockwise. Vnodes (virtual nodes) give each physical node many small positions on the ring.

I'd use Murmur3 over a 64-bit token space, with about 16 vnodes per node. Public facts: the 2007 Dynamo paper introduced virtual nodes. Cassandra's default num_tokens moved from 256 to 16 in 4.0, with a token allocation algorithm, to cut repair overhead.

preferenceList(key, N):
  t = murmur3(key); list = []
  for vnode in ring.walkClockwiseFrom(t):
      node = vnode.physical
      if node not in list and rackOK(node, list): list.append(node)
      if len(list) == N: break
  return list

R10 teaches the ring itself — the modulo problem, the clockwise walk, a node joining and why vnodes even it out.

Interviewer: N, R and W. Why does QUORUM give consistency?

You: If R + W > N, every read set overlaps every write set in at least one replica. So a read always sees the latest acknowledged write.

Interviewer: So QUORUM is linearizable, and you don't need Raft.

You: No — this is the common trap. Overlap is necessary, but not sufficient. Here is why:

• Concurrent writes are resolved by last-write-wins. With clock skew, an older write can win.
• Sloppy quorums put writes outside the home set of replicas. So a read of the home set misses them.
• A partial write that "failed" can resurface later via repair.
• Without blocking read repair, two reads can go back in time.

Quorums give overlap, consensus gives order — and compare-and-set and locks need order. That is exactly why Cassandra's lightweight transactions run Paxos (another consensus protocol) per key. R8 teaches Raft.

What's being probed: why consistent hashing and vnodes exist, the pigeonhole argument behind quorums, and its limits.

Concept — quorum intersection vs consensus. Picture three seats. Any two groups of two seats must share a seat. So the read always sees one copy of the latest write. Raising W slows writes, and raising R slows reads.

But overlap says nothing about the order of concurrent writes, and linearizability needs a single order. A consensus protocol puts every write into one log through one leader. That is what makes CAS safe. The price is pauses during elections.

Takeaway: R + W > N forces overlap; anything needing a single agreed order needs consensus.

Interviewer: Two clients write the same key at once on different replicas. Which wins?

You:

compare(a, b):
  if all(a[n] <= b[n]) and any(a[n] < b[n]): return a_before_b   # b wins
  if all(b[n] <= a[n]) and any(b[n] < a[n]): return b_before_a   # a wins
  if a == b: return equal
  return concurrent                                               # keep both siblings

Public facts: the Dynamo paper used vector clocks and returned siblings to the application. The cart merged them by union, so deleted items could reappear. Riak later moved to dotted version vectors and added CRDTs.

My choice:

• LWW by default, with server-side or hybrid logical clocks and tight NTP (clock sync).
• Vector-clock mode per keyspace, for applications that can merge.
• CRDT counters for counters.

For example, in a cart, concurrent adds from two devices must both survive, so it uses vector clocks or a set CRDT. For a profile field, the latest edit should win, so it uses LWW.

What's being probed: telling "later" from "concurrent", and choosing a resolution per data type.

Concept — happened-before. Wall clocks drift, so "highest timestamp wins" can pick the wrong write. A vector clock keeps a counter per node: - If every counter in A is at most B's, then A happened before B. - If each has a counter the other lacks, they were written without knowledge of each other. The store keeps both, and the application merges them.

Takeaway: LWW is simple but lossy; vector clocks detect true concurrency so nothing is silently dropped.

Interviewer: Replica C dies. What happens to writes, and how does C catch up?

You:

1. C's heartbeats stop. The phi-accrual score crosses its threshold, and nodes mark C down locally.
2. A put for cart:42 arrives. Under strict quorum, we write to A and B, so W = 2 is met, and store a hint for C. A hint is a saved copy of the write, to hand over later.
3. Under sloppy quorum, Dynamo-style: if two of three are down, we write to D and count it towards W. D holds the data tagged "belongs to C".
4. C returns, and gossip spreads the news. Hint holders replay their hints, throttled, and then delete them.
5. Hints expire after about 3 hours. A longer outage needs Merkle-tree repair.

Sloppy quorum keeps writes available, but it breaks R + W > N. This is because a read can hit home replicas that never got the write. Cassandra does not count hints towards the consistency level, except at ANY. I default to strict quorum plus hints, so the overlap guarantee holds.

A Merkle tree is a tree of hashes over key ranges. Two replicas compare roots first, then descend only into branches that differ. They stream just the leaf ranges that diverge. Incremental repair marks SSTables that are already repaired. R6 teaches read repair, anti-entropy and Merkle trees in full.

Interviewer: How does every node know who is alive? Why not remove a dead node at once?

You: Every second, each node gossips its view — generation, heartbeat, state, tokens, load — with one to three random peers. State reaches all 2,000 nodes in O(log n) rounds, which is seconds. Seeds are entry points for joining, not masters.

Phi accrual turns gaps in heartbeats into a suspicion score. It compares each gap with that node's usual rhythm, so a slow network does not cause false alarms.

Down is local and temporary; removal is an explicit admin action. This is because most failures are restarts or GC pauses (stalls while memory is cleaned up), and removing a node moves terabytes. Dynamo made the same choice.

What's being probed: the layered self-healing toolkit, the cost of sloppy quorum, and conservative failure detection.

Concept — healing in layers, suspicion in degrees. The healing layers: - Hints are fast and cheap for short outages. - Read repair heals hot keys as a side effect. - Merkle trees catch everything else, by comparing summaries before data.

Gossip spreads state like office rumours. An adaptive suspicion score replaces a fixed timeout. Marking a node down is cheap and reversible, so it is automatic. Removal is expensive, so a human does it.

Takeaway: Hints for short outages, read repair for hot keys, Merkle trees for the rest — suspect quickly, remove deliberately.

Interviewer: One level deeper. How do reads stay fast and how do deletes work?

You: The write path is: commit log, memtable, ack. When a memtable is full, it flushes to an immutable SSTable.

The read path is: memtable, key cache, then each SSTable from newest first. For each SSTable it checks the Bloom filter, index summary, partition index and data block. It merges cells by timestamp.

"Amp" means amplification: how much extra work or space the engine uses beyond the raw data.

A delete writes a tombstone with a timestamp. It replicates like any write. It is kept for a grace period, such as 10 days.

The tombstone trap: zombie data

Suppose a replica is down longer than the grace period and misses the delete. Meanwhile, the tombstone is compacted away on the other replicas. When the replica returns, its old value comes back and "repairs" the others.

Rule: run full repair more often than the grace period, and never return a node that was down longer than that without replacing it.

For large values, key-value separation (WiscKey-style) keeps only pointers in the LSM, to cut write amplification. Beyond 1 MB, values go to a blob store.

Interviewer: Traffic doubles. Add capacity without downtime.

You:

1. Start node E with the seed list. It learns the ring by gossip.
2. E picks ~16 tokens to balance load and enters JOINING. The pending ranges spread by gossip.
3. Coordinators dual-write those ranges to the current owners and to E, so E misses nothing.
4. Current owners stream SSTable sections to E. This is bulk file transfer, not row by row.
5. E goes NORMAL. The token map updates, and drivers refresh.
6. Old owners run cleanup for ranges they no longer own.

Because of vnodes, many peers each send a small slice in parallel. Throttle streaming, and add one node at a time. Bulk-copy the old data, dual-write the new, then flip ownership.

Failures and scale

Interviewer: A flash sale sends 500K reads a second to one key.

You: Consistent hashing spreads keys, not the load on a single key. In order, I would:

1. Spread reads across all N replicas, if the caller accepts ONE.
2. Add a short-TTL cache in the driver or a front tier (R12).
3. Keep k copies, key#0..k, and read one at random.
4. For write-hot keys, split the value into sub-keys and merge on read, or use a counter CRDT.
5. Rate-limit abusive tenants — Walkthrough 1 again.

Interviewer: Multi-region, and losing a whole region.

You: Each DC holds three replicas. Writes at LOCAL_QUORUM ack after two local replicas confirm. The coordinator then forwards one copy to each remote DC, which fans it out locally. So the client never waits on the WAN.

Strong cross-region reads need EACH_QUORUM (a quorum in every DC), and they pay WAN latency. Cross-DC conflicts resolve the same way as local ones.

If we lose a DC, we fail over via DNS or the global balancer, then rebuild by streaming from the surviving DCs. Data that needs zero RPO (no data loss) across region loss uses synchronous EACH_QUORUM.

And replication is not backup. A bad deploy that corrupts values, or a truncate, replicates everywhere in seconds. So periodic SSTable snapshots go to object storage.

What's being probed: that hashing balances keys but not hotness, keeping latency local while replicating globally, and knowing replication is not backup.

Concept — hot keys, local quorums and snapshots. A wildly popular key must stop being one key. Cache it near clients, or copy it under different names so the hash spreads it.

Cross-region round trips would blow a 10 ms budget. So LOCAL_QUORUM acks locally and ships the write in the background. It accepts a small window of possible loss if a region fails (R13).

Only point-in-time snapshots protect you against your own mistakes.

Takeaway: Cache, copy or split the hot key; quorum locally, replicate asynchronously, and snapshot because replication copies mistakes too.

Curveballs

Interviewer: How do you stop a slow replica ruining p99?

You: At high fan-out, the slowest replica sets the response time. So rare stalls — GC, a noisy neighbour, a compaction burst — dominate the tail.

Route reads by recent latency. When a request passes the p99 threshold, send a speculative retry to another replica and take whichever answer comes first. This costs a few percent extra load for a much shorter tail. R14 covers hedging; the scatter-gather demo there shows why the slowest shard wins.

Interviewer: When would you tell the team not to build this, and use a Raft-based store?

You: When the requirement includes linearizable reads and writes, compare-and-set, leases or locks, or multi-key transactions. Per-key Paxos approximates some of this, but slowly and awkwardly.

So I would split it:

• This leaderless design for always-writable, high-throughput, multi-DC data — carts, sessions, user state, feature data.
• A Raft-based store for metadata, locks, money and anything needing CAS. Use etcd for small metadata, and TiKV or CockroachDB for large data.

Many platforms run both side by side. In a payments system, the ledger is firmly on the second list.

What's being probed: tail-latency instincts, and judgement about the limits of your own design.

Concept — choosing between AP and CP systems. Leaderless AP stores shine when write availability and throughput matter more than a single global order. Consensus stores shine when correctness depends on everyone agreeing on one order — for example, "only one holder of this lock". A senior engineer picks per data set. They are also comfortable saying that part of the product should not live in the system they just designed.

Takeaway: Leaderless for always-writable data, Raft for anything that needs a single agreed order.

Quick reference

The 60-second version

This is a leaderless, Dynamo-style store. Any node coordinates any request, and there is no master in the data path.

Keys hash onto a ring with virtual nodes. Each key lives on three distinct physical nodes clockwise, spread across racks.

Consistency is a per-request dial. QUORUM's R = W = 2 overlaps because R + W > N. But overlap is not order, so anything needing compare-and-set goes to a Raft-based store.

Conflicts resolve by last-write-wins by default. Vector clocks or CRDTs are used where concurrent updates must survive.

Failures heal in three layers: hints for short outages, read repair on reads, and Merkle-tree anti-entropy for everything else. Repair runs inside the tombstone grace period.

Gossip with phi accrual tracks membership. A new node takes small slices from many peers, under dual writes. Each node runs an LSM engine.

About 500 nodes hold a petabyte at RF 3 today. Regions replicate asynchronously at LOCAL_QUORUM, backed by snapshots.

What to say in the interview

"Infrastructure questions are tests of which mechanism you reach for, so I'd scope until I find the requirement that forces the architecture — the latency budget, the guarantee, what happens when a dependency dies — and do the arithmetic aloud to find the resource that runs out first. Then I keep the per-request path tiny and everything slow on a control plane that can fail without traffic noticing. The guarantees go where the data lives: an atomic script on the counter, a unique key and a fencing token in the database, a quorum or a consensus log depending on whether I need overlap or order. And for every box I say what still works when it disappears, and which way it fails — open or closed, late rather than twice."