Design a Distributed Rate Limiter

This page is one interview loop in three rounds. All three rounds design the same system. Each round opens with the interviewer raising the scope, and the design from the round before has to evolve to meet it.

You can start at any round. Rounds 2 and 3 open with a "Where we left off" summary that catches you up.

Loop Opener: What Is a Rate Limiter?

You Already Know One: the Bouncer With a Clicker

A club has room for so many people. The bouncer at the door holds a clicker and lets in, say, 100 people an hour. Person 101 waits outside and is told when to come back. The bouncer isn't there to be unkind to person 101. He's there so that the people already inside have a good night, and so the club doesn't break its fire rules.

A rate limiter does the same job for an API: it counts the requests each client makes in a period of time, and it refuses the ones over the limit. APIs need this for three reasons:

The answer to a refused request is the HTTP status 429 Too Many Requests, usually with a Retry-After header that says how many seconds to wait.

What Changes When the Limiter Is Distributed

One bouncer at one door is easy. Now give the club 50 doors, each with its own bouncer, and a guest who can walk in through any of them. If each bouncer keeps his own clicker, the guest who uses all 50 doors gets in 50 times as often as the rule allows.

That's exactly our situation. An API runs on many gateway servers behind a load balancer, and a client's requests land on all of them. So two questions drive the whole loop:

• Who holds the clicker? The count must be shared, or it isn't a limit.
• What if the clicker breaks? The limiter sits in front of every request. If it is slow, the whole API is slow. If it is down and we wait for it, the whole API is down.

The Question the Whole Loop Answers

How do we count fairly across many machines, on every request, without adding latency or becoming the thing that causes the outage?

The answer gets sharper every round:

• Round 1: one shared counter in a fast store, updated atomically, and a plan for when it fails.
• Round 2: many counters per request, live rules, hot counters kept local, and layers from the edge to the service.
• Round 3: limits that span regions, quotas that bill, attackers who spread out, and backends that need protection from everyone at once.

---

Round 1 · Mid-level · "Protect One Public API"

~35 min · SDE II (L5) · 1 region, 3 AZs · ~10K requests/s peak · ~1M users · limiter adds < 5 ms

R1.1 Establish Design Scope

The interviewer says: "Our public API keeps getting hammered by a few users. Design a rate limiter for it." Before we draw anything, we ask questions, and we say out loud what each answer changes.

Out of scope for this round:

• Tenants and pricing tiers (a free customer and a paying customer with different limits).
• Different costs per route (an export that costs more than a read).
• Changing limits while the system runs, without a deploy.
• More than one region.

R1.2 Functional Requirements, Derived Step by Step

We read the problem one phrase at a time and turn each phrase into a requirement:

Not yet: different limits per customer or plan, weighted routes, and limit changes without a deploy. The interviewer may bring these back.

R1.3 Non-Functional Requirements: the Questions

Numbers come in R1.7. For now, the questions and why each matters:

• Latency. The check runs on every request, before any real work. Whatever it costs is added to every call the API serves. Our budget is under 5 ms added at P99, and we want about 1 ms typically.
• Availability. The limiter failing must not fail the API. A limiter that turns a cache hiccup into a total outage has done more damage than any abusive user.
• Accuracy. A small overshoot is fine. Two times the limit is not.
• Memory. A constant amount per key, whatever the user's request rate. An algorithm whose memory grows with traffic gets more expensive exactly when we are under attack.

R1.4 The API

There is no public endpoint for the limiter. It is an internal check that the gateway calls on every request. Written as a call:

jsonCopy
{
  "call": "check",
  "key": "user:u_1001",
  "rule": "api-per-user",
  "cost": 1
}

jsonCopy
{
  "allowed": true,
  "remaining": 17,
  "retry_after_s": 0,
  "reset_after_s": 2
}

remaining is the budget left after this request. retry_after_s is how long to wait before a request of this cost can succeed (0 when allowed). reset_after_s is how long until the budget is completely full again.

What the client sees is the HTTP response. A refused request:

httpCopy
HTTP/1.1 429 Too Many Requests
Content-Type: application/problem+json
Retry-After: 1
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 12

{
  "type": "https://api.example.com/errors/rate-limited",
  "title": "Too many requests",
  "detail": "User u_1001 is over 100 requests per minute. Retry after 1 second.",
  "retry_after_seconds": 1
}

Which of these headers are standards, and which are habits?

Retry-After on a 200 response means nothing, so we only send it on 429. The X-RateLimit-* headers go on every response, so a well-behaved client can slow down before it hits the limit.

Recap

• One internal check per request: check(key, cost) → allowed, remaining, retry_after.
• Limits: 100 per minute per user on the API, 5 per minute per account on login, short bursts allowed.
• About 1M users and 10,000 requests per second at peak; small overshoot fine.
• Under 5 ms added; the limiter failing must never take the API down.
• Refusals are 429 with Retry-After.

Let's build it, starting with the simplest thing that works.

R1.5 Design Evolution: From a Local Counter to a Shared, Atomic Limiter

Every step below follows the same pattern: a problem, your turn to think, the answer, and what the answer costs us. The cost is always the next problem.

Step 1.0: The Baseline

Each gateway server counts in its own memory: a map from user ID to "requests this minute". No network, no dependency, a few nanoseconds per check.

Synthesizing vector architecture diagram...

What's good about it: it is as fast as a limiter can be, and it can't fail on its own. For one server, it is the right answer.

What it costs us: we have six gateway servers, and the load balancer spreads each user's requests across all of them. Each server lets the user have 100 per minute, so the user gets up to 6 × 100 = 600 per minute. With N servers, a user gets up to N times the limit, and N grows every time we scale out.

Step 1.1: A User Got Six Times Their Limit

Primitive: Distributed Cache Patterns & Eviction

Step 1.2: Which Algorithm?

The refill, in pseudocode. We store the tokens left and the time we last updated them. We don't refill on a timer; we compute the refill when the next request arrives:

textCopy
check(key, cost, capacity, rate, ttl):
    now   = current time, in seconds with microseconds
    state = read(key)                               # { tokens, ts } or nothing
    if state is nothing:
        tokens = capacity                           # a new bucket starts full
    else:
        elapsed = max(0, now - state.ts)            # never negative
        tokens  = min(capacity, state.tokens + elapsed * rate)
    if tokens >= cost:
        tokens      = tokens - cost
        allowed     = true
        retry_after = 0
    else:
        allowed     = false
        retry_after = ceil((cost - tokens) / rate)  # seconds until enough tokens
    write(key, { tokens, ts: now }, expire after ttl)
    return allowed, floor(tokens), retry_after

The numbers, proved. With capacity $b = 20$ and rate $r = 100/60 \approx 1.667$ tokens per second:

• A page load of 15 calls passes at once: 15 ≤ 20.
• An empty bucket is full again after $b / r = 20 / 1.667 = 12$ seconds.
• The most a user can send in any 60-second window is a full bucket plus a minute of refill: $20 + 100 = 120$, which is 1.2× the per-minute figure. That ceiling is set by the capacity. Capacity 100 would allow 200 in a minute, the same 2× as the fixed window. The capacity is how much overshoot we allow, so we keep it small.
• A request that finds 0.4 tokens waits $(1 - 0.4) / 1.667 = 0.36$ s, sent as Retry-After: 1 (whole seconds, rounded up).

The trade-offs in one table:

Go deeper: the GCRA (generic cell rate algorithm) is a token bucket written with a single number per key: the "theoretical arrival time" of the next allowed request. A request is allowed if it arrives no earlier than that time minus the burst allowance. It behaves like a token bucket and saves one field, at the cost of being harder to explain in an interview.

Primitive: Distributed Rate Limiting

Step 1.3: Ten Requests All Saw One Token Left

Is TIME inside a script safe? It used to be a problem, and the reason is worth knowing. Redis once replicated scripts verbatim: it sent the script text to replicas, which ran it again. A script that reads the clock would then compute a different answer on the replica. So Redis refused a write after TIME in a script unless the script switched to effects replication (replicating the resulting writes instead of the script), which Redis 3.2 made possible with redis.replicate_commands(). Redis 5.0 made effects replication the default, and Redis 7.0 removed verbatim replication entirely. On the engines we'd choose (Redis OSS 7.x or Valkey 7.2+; effects replication has been the default since Redis 5.0 anyway), a script can read TIME and write: the replica receives "set tokens to 17.35, ts to …", never the script.

One subtlety remains. After a failover (step 1.4), the new primary's clock may differ from the old one's by a small amount δ. If it is behind, elapsed is clamped to 0 and the bucket just refills slightly late. If it is ahead, each bucket gains at most δ × rate extra tokens, once. With node clocks within a few milliseconds of each other (an assumption: we don't manage ElastiCache's clocks), that's a small fraction of a token.

Go deeper: the atomic-command alternative. The fixed window needs no script: INCR the counter and set its expiry, and compare the returned count. INCR is itself atomic. That's why fixed windows are popular: they need only atomic commands. The token bucket reads and writes two fields with arithmetic in between, which is why it needs a script.

Step 1.4: The Cache Is Down. Is the Whole API Down?

The fallback's arithmetic. A local limit of $L / N$ per gateway (rounded up) keeps the fleet-wide total near $L$ but can refuse an honest user early if their requests happen to hit the same gateway. For login, with $L = 5$ and $N = 6$, one real user who mistypes twice on the same gateway is refused on the second try until the minute passes. For a security limit, during a cache outage, we accept that.

Primitive: Circuit Breaker, Bulkhead & Fault Tolerance · Drill: Circuit breaker cascading thread stall

Step 1.5: Throttled Clients Retry Instantly

Step 1.6: Memory Keeps Growing

Round 1 Step Summary

R1.6 Architecture v1

Now the concepts get AWS names.

Synthesizing vector architecture diagram...

Follow a request down the left: the load balancer picks a gateway, the gateway makes one call to the cache primary, and only an allowed request continues to the backend. Every gateway in every AZ talks to the same primary, which is what makes the count shared. The dotted arrow is replication to the replica in another AZ, which takes over if the primary fails.

The pieces:

• Gateways: six servers, two per AZ, behind an Application Load Balancer. The limiter is a filter inside the gateway process (or a sidecar on the same host), so the only network hop it adds is to the cache.
• Cache: ElastiCache with cluster mode off: one primary and one replica in a different AZ, with Multi-AZ automatic failover. Private subnets; only the gateways' security group can reach it; clients authenticate to it (ElastiCache supports role-based access control users and IAM authentication) and talk TLS.
• Stored state per key, one small hash per bucket:

Trace: the three outcomes of a check.

Synthesizing vector architecture diagram...

The third branch is the one that matters most. A timeout adds at most 3 ms and then gets out of the way. Once the circuit breaker opens, later requests skip the call entirely until a probe succeeds. For the login limit, the third branch uses the local fallback instead of forwarding blindly.

R1.7 Numbers

Checks per second. One check per request: 10,000 per second at peak. We assume average traffic is about a third of peak, ~3,300 per second, the same ratio the other loops use.

Memory per key. Our estimate for one bucket, stored as a small hash:

$$1{,}000{,}000 \text{ keys} \times 96 \text{ B} = 96 \text{ MB}$$

That assumes all 1M users were active in the same minute, which is a very safe upper bound: with a 60 s TTL, only users active in the last minute have a key.

Store operations against capacity. One script call per check: 10,000 calls per second at peak. We plan on about 60,000 script calls per second per Redis node for a script this small. That is an assumption to load-test, not a published figure: throughput depends on the script, the node type, TLS and the client. At our assumption, peak uses $10{,}000 / 60{,}000 \approx 17\%$ of one node.

Node choice. Memory isn't the constraint (96 MB), and neither is throughput. We want steady CPU (not a burstable t-class node that runs out of CPU credits under sustained load) at a low price: cache.m7g.large (2 vCPUs, 6.38 GiB). ElastiCache reserves 25% of memory by default (reserved-memory-percent) for background work like snapshots and replication, leaving about $6.38 \times 0.75 \approx 4.8$ GiB for data: 50 times what we need. On a 2-vCPU node, the host's own background processes share the CPU with the engine, so we watch both EngineCPUUtilization and CPUUtilization.

One replica, for failover, not for reads. Every check writes, so every check goes to the primary; the replica exists only to take over if the primary fails.

Latency. A round trip inside one region is typically well under a millisecond in the same AZ and around a millisecond across AZs (an assumption to measure in our region). The script itself runs in microseconds. So a typical check costs about 1 ms, and the worst case before the breaker opens is the 3 ms timeout. Both are inside the 5 ms budget.

Monthly cost (us-east-1 on-demand prices, 730 hours a month; ElastiCache for Valkey nodes are priced 20% lower than these Redis OSS prices):

We don't count the gateways or the load balancer: the API needs them anyway, for routing and authentication. The limiter adds a cache and a filter.

R1.8 Trade-Offs

Local vs shared counting

Fail open vs fail closed

The algorithm trade-offs are in the table in step 1.2.

R1.9 Failure Modes

R1.10 Pillar Check

R1.11 Round 1 Rubric and Follow-Ups

What a strong mid-level (L5) answer shows

• Asks what to limit by, how exact, and whether bursts are allowed, and explains how each answer changes the design.
• Explains why local counts fail behind a load balancer (N× the limit).
• Compares the algorithms and chooses one with a reason; knows the fixed window's 2× edge burst.
• Proves the token bucket's numbers: 12 s to refill, at most capacity + rate × window in any window.
• Makes the check atomic in the store, and uses the store's clock.
• Treats "what if the limiter is down" as a first-class question, and decides per limit.
• Sets a TTL, and knows why TTL ≥ capacity ÷ rate makes expiry harmless.

Follow-up questions

1. "Why not use the sliding window log? It's exact." Answer: its memory grows with the request rate. At 100 requests per active user, and assuming around 64 bytes per stored timestamp, 1M active users is about $1{,}000{,}000 \times 100 \times 64 \text{ B} = 6.4$ GB, against 96 MB for token buckets. Worse, if the log records every attempt (some implementations do, so that refused requests still count against the client), an attacker sending 10,000 requests a minute makes us store 10,000 entries for them: the algorithm is most expensive exactly when we're under attack. We asked in R1.1 and "a small overshoot is fine", so exactness isn't worth that.

2. "Your capacity is 20 but your limit is 100 a minute. What does X-RateLimit-Remaining say?" Answer: the tokens in the bucket, at most 20. It's the true answer to "how many can I send right now?", but a client reading "limit 100, remaining 20" might be confused. We say in the docs that Remaining counts tokens available now, and we send RateLimit-Policy: "per-user";q=100;w=60 so the policy itself is explicit.

3. "Could we skip the cache and use DynamoDB for the counters?" Answer: it would work, with a conditional write per check. But each DynamoDB write is a few milliseconds, against our 1 ms target, and a single item's partition supports about 1,000 writes per second, so one very busy key hits a ceiling. DynamoDB also has no server-side clock in conditions: we would have to pass the gateway's time, which brings back step 1.3's clock problem. We'd pay per request, too: at 3,300 writes a second on average, about $5,400 a month at $0.625 per million writes, against $231 for the cache.

Interview gotchas from this round's wrong answers

---

Round 2 · Senior · "A Multi-Tenant Gateway for the Whole Company"

~40 min · Senior SDE (L6) · 1 region, 3 AZs · ~167K requests/s peak · ~50M buckets · limiter P99 < 2 ms · 99.99%

R2.0 Where We Left Off

This is what the candidate says aloud in the first 60 seconds of Round 2. If you're starting here, it's everything you need from Round 1.

Round 1 in 60 seconds. "We built a rate limiter for one public API: about 10,000 requests a second at peak, 1M users, one region, three AZs. Each user has a token bucket, capacity 20 and 100 tokens a minute, so bursts pass and nobody gets more than 120 in any minute. Login has its own bucket, 5 attempts a minute per account. The buckets live in ElastiCache, one primary and one replica, so all six gateways share one count. Each check is one atomic script in the cache that refills, decides and writes, using the cache's clock, so there is no check-then-act race and gateway clocks don't matter. Every key expires after 60 seconds, which is longer than a full refill, so expiry never grants extra tokens. Checks time out after 3 ms behind a circuit breaker. When the cache is unreachable, the API limit fails open with an alarm, and the login limit falls back to a local limit on each gateway. Refusals are 429 with Retry-After. About $265 a month. Three costs are still open: every request pays one round trip to one node, a very busy key would sit on one node, and the limits are in a config file."

Architecture v1, compact

textCopy
 clients ──► ALB ──► 6 gateways (2 per AZ), limiter filter + local fallback
                        │ one EVALSHA per request, 3 ms timeout, circuit breaker
                        ▼
              ElastiCache primary (AZ a) ──replicates──► replica (AZ b)
              key rl:user:<id>:api → { tokens, ts }, TTL 60 s

Round 1 step summary

Open costs: one round trip per request to one node; a hot key lives on one node; rules in config files.

R2.1 The Scope Raise

Interviewer: "Your limiter worked, so now every API in the company goes through our gateway. Our customers are tenants on Free, Pro and Enterprise plans, each with different limits. Some routes are much more expensive than others: an export costs us about ten times a read. The security team must be able to change a rule during an attack and have it take effect in seconds. We also want limits per IP address at the edge. The company serves about 500,000 requests a second at peak across three regions, and each region runs its own gateway stack, so design one region's: about 167,000 a second. The limiter's decision must take under 2 ms at P99, and the gateway must be up 99.99% of the time."

A scope raise is not the end of scoping. Before we fix anything, we ask back, and we say what each answer changes, just as in R1.1.

Scope change

The "Not yet" list from R1.2 is now mandatory: limits per customer and plan, weighted routes, and limit changes without a deploy.

R2.2 What Breaks in the Round 1 Design

R2.3 New Requirements and API Additions

The rule model. A rule says which bucket to use, which requests it applies to, how big the bucket is and how fast it refills, what each request costs, and what to do when it's empty. Rules live in a versioned rule set:

yamlCopy
rule_set: public-api
version: 1842
rules:
  - id: ip-unauthenticated
    dimension: ip                  # bucket key: the client IP set by our edge
    match: { authenticated: false }
    limit: { rate_per_s: 20, burst: 40 }
    cost: 1
    kind: security                 # never leased; local fallback if the cache is down
    action: reject

  - id: tenant-plan
    dimension: tenant
    match: { authenticated: true }
    limit_by_tier:
      free:       { rate_per_s: 10,   burst: 20 }
      pro:        { rate_per_s: 100,  burst: 200 }
      enterprise: { rate_per_s: from_contract, burst: 2x_rate }
    cost_by_route:
      "POST /v1/exports": 10
      default: 1
    kind: capacity                 # may be leased; fails open if the cache is down
    action: reject

  - id: route-exports
    dimension: tenant+route
    match: { route: "POST /v1/exports" }
    limit: { rate_per_s: 5, burst: 5 }
    cost: 1
    kind: capacity
    action: reject

  - id: login-per-account
    dimension: account
    match: { route: "POST /v1/login" }
    limit: { rate_per_s: 0.0833, burst: 5 }    # 5 per minute
    cost: 1
    kind: security
    action: reject

How a request is evaluated.

1. Resolve identity once: the tenant and tier from the verified token, or the client IP from our edge (step 2.5).
2. Collect the matching rules. An export by a Pro tenant matches tenant-plan (cost 10) and route-exports (cost 1).
3. Short-circuit locally first. If a matching bucket is in the gateway's "denied until" cache (step 2.3) or its leased tokens cover the request, no network call is needed.
4. Check every remaining bucket in one atomic call (step 2.1). All must pass, or none are charged.
5. Return the most restrictive answer: the smallest remaining and the largest retry_after among the buckets.

Validation rules (checked when a rule set is saved, not at request time):

• Every cost is at most its bucket's burst. A request costing 10 against a burst of 5 could never pass: a silent, permanent outage for that route.
• Every bucket's TTL is at least burst ÷ rate (Round 1's rule), computed by the system, not typed by a person.
• A new version that tightens a limit for more than a set share of traffic needs a second approver (R2.8).

The rule-management API. Versions go up by one on every change, and a write must name the version it is based on:

httpCopy
PUT /v1/rule-sets/public-api HTTP/1.1
Host: ratelimit-admin.internal
If-Match: "1841"
Content-Type: application/yaml

rule_set: public-api
rules: [...]

httpCopy
HTTP/1.1 200 OK
ETag: "1842"
Content-Type: application/json

{ "rule_set": "public-api", "version": 1842, "rollout": "canary", "effective_fleet_wide_within_s": 5 }

If someone else saved version 1842 first, this request gets 412 Precondition Failed, and they must re-read and re-apply their change. Two security engineers editing during an incident can't silently overwrite each other.

Headers per tier. The response headers describe the bucket closest to empty, and the draft RateLimit-Policy field can list every policy that applied:

httpCopy
HTTP/1.1 200 OK
X-RateLimit-Limit: 5
X-RateLimit-Remaining: 3
X-RateLimit-Reset: 1
RateLimit-Policy: "tenant-plan";q=100;w=1, "route-exports";q=5;w=1
RateLimit: "route-exports";r=3;t=1

R2.4 Design Evolution: Hot Keys, Live Rules and Layers

Step 2.1: One Request Must Pass IP, Tenant and Route Limits

Primitive: Distributed Rate Limiting

Step 2.2: Security Changed a Rule and Half the Fleet Still Uses the Old One

Step 2.3: A 100K-Requests/s Tenant Pinned One Cache Shard

Synthesizing vector architecture diagram...

The gateway talks to the shard once per block, not once per request. When the tenant is over its limit, the gateway refuses locally until the time the shard gave it, so a runaway tenant's refusals cost the cache almost nothing.

Primitive: Distributed Cache Patterns & Eviction · Drill: Sharding tenant hotspot

Step 2.4: The Cache Failed Over and Every Gateway Reconnected at Once

Drill: WebSocket reconnect thundering herd

Step 2.5: Attackers Rotate IPs and Forge X-Forwarded-For

Primitive: API Gateway & Reverse Proxy · Drill: Rate limiting a partner API

Step 2.6: Limiter Latency Creeps Above 2 ms at Peak

Round 2 Step Summary

R2.5 Architecture v2

Synthesizing vector architecture diagram...

Follow a request top to bottom: CloudFront and WAF drop floods, the load balancer admits only CloudFront's traffic, and the gateway's limiter filter decides with one call to the shard that holds the tenant's keys (or none, when a lease covers it). The dotted arrows are off the request path: gateways poll the rule store every second, and every version is also saved to S3 so a gateway can start without the rule store. Each shard's replica sits in a different AZ from its primary (not drawn).

Trace 1: a weighted, multi-bucket check.

Synthesizing vector architecture diagram...

Trace 2: a live rule change. A security engineer saves version 1843 (unauthenticated IP limit 20/s with burst 40 → 5/s with burst 10) with If-Match: "1842". The conditional write moves the current pointer to 1843 and writes the S3 snapshot. Within a second, each gateway's poll sees 1843, fetches it, validates it, and swaps it in. The first request from an attacking IP after the swap refills that IP's bucket at 5/s and clamps its tokens to the new burst of 10. No gateway restarts; no bucket resets; a delayed copy of version 1842 arriving later is ignored because 1842 < 1843.

Trace 3: a cache failover. Shard 3's primary fails. Checks for keys on shard 3 time out at 3 ms; after five in a row, each gateway's breaker for shard 3 opens. For about a sixth of keys, capacity rules fail open (counted, alarmed) and security rules use the local fallback; leased blocks keep serving. ElastiCache promotes shard 3's replica in another AZ within seconds. Gateways probe with jittered backoff, refresh the slot map once, reconnect their two connections, and close their breakers. The other five shards never noticed.

R2.6 Numbers and Cost

Traffic. The company's peak is 500,000 requests a second across three regional stacks, so each region plans for $500{,}000 / 3 \approx 166{,}667$, which we round to ~167K requests/s at peak. Average is about a third of peak, ~55.6K/s, which is $55{,}556 \times 2{,}629{,}800 \text{ s} \approx 146$ billion requests a month in this region.

Gateways. We plan on 12,000 requests a second per gateway node (an assumption to load-test). With 24 nodes, 8 per AZ, peak runs at $167{,}000 / 24 \approx 7{,}000$ per node (58%), and after losing an AZ, $167{,}000 / 16 \approx 10{,}400$ per node (87%), with no new nodes needed.

Memory, re-derived from the fact source's figures:

$$50{,}000{,}000 \text{ buckets} \times 96 \text{ B} = 4.8 \text{ GB of data}$$ $$4.8 \text{ GB} \times 2 \text{ (primary + replica)} \times 1.5 \text{ (buffer)} = 14.4 \text{ GB of memory across the cluster}$$

The 50M is an upper bound: it counts every bucket seen in a day as if all were alive at once, while TTLs of a minute or less keep far fewer alive. What decides the node type is memory per primary: $4.8 \text{ GB} / 6 = 0.8$ GB of data per shard, or 1.2 GB with the 1.5× buffer. If our 96-byte estimate turns out to be 200 bytes (R1.7's warning), that's 10 GB of data, 1.67 GB per shard, 2.5 GB with the buffer.

Shards, from operations per shard. One script call per request before leasing, so 167K calls/s at peak. At our assumed 60,000 calls per second per shard (to load-test):

$$\left\lceil \frac{167{,}000}{60{,}000} \right\rceil = 3 \text{ shards, each at } \frac{167{,}000}{3 \times 60{,}000} \approx 93\% \text{ at peak}$$

Three shards leave no headroom for bursts, uneven key spread or a slow shard. We choose 6 primary shards: $167{,}000 / 6 \approx 27{,}800$ calls/s each, 46% of the assumption at peak. We size this without counting on leasing, because leasing is an optimization we may switch off (for example, if a tenant disputes its limit and we want exact enforcement while we investigate). And each shard gets one replica in a different AZ, so losing an AZ promotes replicas but leaves all six shards with a primary: capacity doesn't drop.

Node type. Each primary needs about 1.2 GB (2.5 GB at worst) and CPU for one busy engine thread. We choose cache.m7g.xlarge (4 vCPUs, 12.93 GiB; about 9.7 GiB usable after the default 25% reservation). Four vCPUs keep the host's background processes and network handling off the engine thread's core, which AWS notes can matter on 2-vCPU nodes. We don't need a memory-optimized r-family node: the fact source's cache.r6g.xlarge (26.32 GiB) buys about twice the memory we could ever use.

How much leasing removes. Assume about 200 tenants run above 500 requests a second and together carry half the peak, ~83.5K requests/s. With block sizes of a quarter-second of each gateway's share, each such tenant costs at most about 100 lease calls a second:

Leasing cuts total calls by about 38%, not 99%: the 99% is per hot key. What it really buys is the worst case: the runaway 100K/s tenant costs ~100 calls/s instead of 100,000 on one shard.

The per-request edge fee. AWS WAF charges $0.60 per million requests, plus $5 per web ACL and $1 per rule per month:

$146{,}000 \text{ million requests} \times \$0.60 \approx \$87{,}600 \text{ per month}$

That is list price for this region's traffic. (AWS Shield Advanced, at $3,000 a month per organization, includes up to 50 billion WAF requests a month; Round 3 uses it.) Large customers negotiate private pricing, so treat the absolute number as illustrative. The ratio is the lesson: the edge's per-request fee is about 25 times the limiter's own infrastructure.

Monthly cost (us-east-1 on-demand; CloudFront's own fees aren't counted, because the company already serves its APIs through CloudFront for TLS and edge routing):

R2.7 Trade-Offs

R2.8 Failure Modes

R2.9 Production Gotchas

R2.10 Pillar Check

Alarms and first actions

R2.11 Round 2 Rubric and Follow-Ups

What a senior (L6) answer adds over L5

• Models limits as rules with dimensions, costs and kinds, and checks several buckets in one atomic, all-or-nothing call.
• Knows why cluster mode needs hash tags, and what they cost (a tenant's keys on one shard).
• Solves the hot key with leasing, and states and proves the overshoot bound.
• Makes rule changes live and safe: versioned, monotonic, validated, canaried, and without resetting counters.
• Plans failover as a load event: fewer connections, per-shard breakers, jittered reconnects.
• Never trusts client-supplied IP headers, and places each limit at the layer that can see what it needs.
• Sizes shards from operations, nodes from memory per primary, and notices where the money really goes.

Follow-up questions

1. "Why not lease for every key? It saves calls everywhere." Answer: for a key that sees 2 requests a minute, a lease is a call that saves nothing, and every lease strands tokens on a gateway that may never use them. A Free tenant at 10/s with 24 gateways would need blocks of 1 token to keep its overshoot small, which is just a call per request with extra steps. Leasing pays off only when a key's rate per gateway is high enough that one call serves many requests.

2. "Two gateways hold 105-token leases for the big tenant, and the tenant goes quiet. What happens to those tokens?" Answer: each lease expires 10 seconds after it was taken, by that gateway's monotonic clock, and the gateway gives the unused tokens back with the give_back script, which adds them to the bucket capped at its capacity. While they were stranded, the tenant's bucket had up to 210 fewer tokens than it should have: a small undershoot. Only the gateway's own clock is involved, so clock differences between gateways don't matter here.

3. "Why is your IP limit keyed on the IP alone, and not per tenant?" Answer: it applies only to unauthenticated requests, where there is no tenant yet. For authenticated traffic, the tenant is the identity we trust; an enterprise tenant's requests may all come from a few NAT addresses, and a per-IP limit would throttle them wrongly. For those, per-IP volume is WAF's job at the edge, with known partner addresses excluded.

Interview gotchas from this round

---

Round 3 · Architect · "Global Limits, Billing Quotas and Real Attackers"

~45 min · Principal (L7) · 3 regions · ~500K requests/s peak · 99.999% for the gateway · quotas exact enough to bill · no cross-region call on the request path

R3.0 Where We Left Off

This is what the candidate says aloud in the first 60 seconds of Round 3. If you're starting here, it's everything you need from Rounds 1 and 2.

Round 2 in 60 seconds. "Every API in the company goes through our gateway. Each of three regions runs its own stack at about 167,000 requests a second at peak, 99.99%, with the limiter's decision under 2 ms at P99. Limits are rules with a dimension, a tier, a cost per route and a kind: capacity or security. One request checks several token buckets, IP, tenant and route, in one atomic all-or-nothing script, because all of a tenant's keys share a hash tag and live on one shard. ElastiCache runs in cluster mode with six shards, each with a replica in another AZ, sized at 46% of an assumed 60,000 calls a second per shard. Hot tenants lease blocks of about a quarter-second of tokens into gateway memory, so a runaway tenant costs the cache about 100 calls a second, with an overshoot bounded by gateways times 1.2 blocks, about 0.3 s of the limit. Rules live in a versioned store; gateways poll every second, only accept higher versions, and never reset buckets. Failover uses per-shard breakers and jittered reconnects; capacity rules fail open and security rules fall back to local limits. We trust only CloudFront's viewer address, and WAF and Shield take the floods. About $3,500 a month for the limiter, and $87,600 for WAF request fees. Four costs are still open: limits are per region; billing quotas don't exist; per-IP limits miss distributed attacks; and tenant limits don't protect a struggling backend."

Architecture v2, compact

textCopy
 clients ──► CloudFront + Shield + WAF (per-IP floods) ──► ALB (CloudFront only)
          ──► 24 gateways, 8 per AZ: rules v18xx, leases, denied cache, breakers, local fallback
                 │ one script per request (or per lease), keys rl:{tenant}:...
                 ▼
          ElastiCache cluster: 6 shards × (primary + replica), cache.m7g.xlarge
          rule store (DynamoDB, versioned) ──polled 1 s──► gateways; snapshots in S3
 × 3 regions, each on its own: a tenant's 1,000/s limit is 1,000/s in *each* region

Steps so far

Open costs: limits are per region; no billing quotas; per-IP limits miss distributed attacks; nothing protects a struggling backend.

R3.1 The Scope Raise

Interviewer: "We're consolidating into one global platform across three regions, and it must survive losing a whole region. Enterprise contracts now say 1,000 requests a second globally, not per region. Paid plans include monthly quotas that we bill against, so usage numbers go on invoices. Last month we had a credential-stuffing attack spread over 100,000 IP addresses, and not one of them crossed a per-IP limit. And last week our search service slowed down and fell over, even though no tenant was over its limit. The gateway must be up 99.999% of the time."

Again, we ask back before we design:

Scope change

R3.2 What Breaks in the Round 2 Design

R3.3 New Requirements and API Additions

Global limit definitions. A rule can now have scope: global, with settings for how its budget is split across regions:

yamlCopy
- id: tenant-global
  dimension: tenant
  scope: global                       # one budget across all regions
  match: { tier: enterprise }
  limit: { rate_per_s: from_contract, burst: 2x_rate }
  shares:
    floor_fraction: 0.05              # each live region always keeps 5% of the limit
    rebalance_every_s: 5
    max_step_fraction: 0.10           # a region's share moves at most 10% of the limit per rebalance
  kind: capacity

The metering model. Every gateway emits usage records; the billing system only ever reads totals derived from them.

A usage record (one per gateway per 5-second flush, carrying up to 1,000 tenants):

jsonCopy
{
  "record_id": "gw-use1-a07-1790424000123/000918273",
  "region": "us-east-1",
  "interval_start": "2031-03-01T09:30:00Z",
  "interval_s": 5,
  "month": "2031-03",
  "u": { "t_acme": 4821, "t_bluebird": 37 }
}

record_id is the gateway's identity (including its process start time, so a restarted process is a new identity) plus a sequence number that only goes up. Units are allowed requests weighted by cost, the same costs the limiter uses. The format is deliberately compact: the month and interval are stated once per record, and each tenant's count is one short map entry, about 24 bytes, so a record of 1,000 tenants is about 24 KB.

The quota usage table (a DynamoDB global table):

A tenant's usage for the month is the sum of its three items.

The usage API, for customers:

httpCopy
GET /v1/usage?month=2031-03 HTTP/1.1
Host: api.example.com
Authorization: Bearer <tenant token>

httpCopy
HTTP/1.1 200 OK
Content-Type: application/json

{
  "tenant": "t_acme",
  "month": "2031-03",
  "plan": "pro",
  "included_units": 10000000,
  "used_units": 9412288,
  "overage_units": 0,
  "as_of": "2031-03-12T14:05:30Z",
  "note": "Usage is complete up to as_of, usually within 5 minutes of now."
}

Abuse signals that rules can use, beyond IP address: the account being targeted, a client TLS fingerprint (JA4), a device or session token our login page issues, IP reputation (AWS publishes managed lists of known-bad and anonymizing addresses), and the ratio of failed to successful logins. A new rule kind: adaptive can tighten itself when a signal crosses a threshold (step 3.3).

Backend concurrency limits, declared per service and route, with priority classes:

yamlCopy
service: search
concurrency:
  mode: adaptive                  # the limit moves with measured latency
  target_latency_ms: 100
  min_limit: 20
  max_limit: 400
priority_classes:                 # shed from the bottom up
  - critical:    ["POST /v1/checkout", "POST /v1/login"]
  - normal:      ["GET /v1/search"]
  - best_effort: ["POST /v1/exports", "GET /v1/search/suggest"]

R3.4 Design Evolution: Global, Billable and Adaptive

Step 3.1: One Global Limit Across Three Regions

Primitive: Gossip Protocol & Failure Detection · Loop: Unique ID generator, step 3.1 (the same global-table trap, for leases)

Step 3.2: Monthly Quotas Must Bill Correctly

Primitive: Change Data Capture & Outbox · Message Queues vs Event Streams

Step 3.3: An Attack From 100,000 IPs, Each Under Every Limit

Primitive: Bot Defense, Sybil Resistance & Registration Abuse · Drill: Credential stuffing surge

Step 3.4: The Backend Is Slow, but Nobody Is Over Their Limit

Primitive: Circuit Breaker, Bulkhead & Fault Tolerance

Step 3.5: A Region Is Gone

Primitive: Cloud Disaster Recovery & Multi-Region Active-Active

Step 3.6: Should We Build This at All?

Round 3 Step Summary

R3.5 Global Architecture

Synthesizing vector architecture diagram...

Each region is complete on its own: its request path (CloudFront to gateway to cache to service) never leaves the region. Two small global tables carry everything that must cross regions, and each region writes only its own items in them: its usage rates for shares, and its quota totals. The Europe and Asia regions have the same shape as us-east-1, drawn compactly.

Trace 1: a global-limit check. t_acme (1,000/s globally) sends a request to eu-west-1. The gateway's rules say tenant-global, and the current share for eu-west-1 is 305/s (burst 610). The check is Round 2's ordinary script call against rl:{t_acme}:global at rate 305. Nothing crosses a region. In the background, every 5 seconds, eu-west-1 writes its own usage item (t_acme: 312.4/s), reads the other two from its local replica, recomputes, and moves its share up by at most 100/s.

Trace 2: a quota crossing.

Synthesizing vector architecture diagram...

Every write is an absolute total with a "never go down" condition, so replays are harmless. The flag reaches gateways through the same poll as rules. Tenant t_free9 was over its quota for about half a minute before the flag landed (330 units at its 10 a second); those ~330 requests are simply let go.

Trace 3: a region loss. ap-northeast-1 fails at 09:30:00. Its share-sync item stops changing; at 09:30:15 both other regions see it as stale. Route 53's health checks for it fail at about 09:30:30, so the survivors now have both signals and drop it from the share formula. A dead region's share is released at once (the 10% step limit applies to live regions): t_acme's shares go from 560 / 305 / 135 to $50 + 900 \times \tfrac{2}{3} = 650$ and $50 + 900 \times \tfrac{1}{3} = 350$ for us-east-1 and eu-west-1 (their floors plus their 2:1 traffic split), and then keep following traffic as ap-northeast-1's clients arrive. By about 09:32, most clients have moved. Each survivor's gateways run near 10,400 requests a second and its shards near 69%. ap-northeast-1's usage records wait in its stream; when it returns, its aggregator catches up from its checkpoint, and its quota items move forward to the right totals.

R3.6 Numbers and Cost

Per-region load.

Shard percentages are of the assumed 60,000 calls a second and ignore leasing (which removes about 38%); gateway percentages are of the assumed 12,000 requests a second per node. Both are assumptions to load-test before launch.

Share-sync traffic. About 500 tenants have global limits (an assumption). One region's item holds ~30 bytes per tenant, about 15 KB, which is 15 write units per write:

$3 \text{ regions} \times \tfrac{1}{5 \text{ s}} \times 15 \text{ units} \times 3 \text{ (1 local + 2 replicated writes)} = 27 \text{ units/s} \approx 71 \text{M/month} \times \$0.625/\text{M} \approx \$44$

Metering events. Each gateway flushes every 5 seconds. Assuming about 10,000 tenants are active on a gateway in any 5 seconds, a flush is 10 records of 1,000 tenant counts, ~24 KB each in the compact format from R3.3 (~24 B per count):

$$24 \text{ gateways} \times 10 \text{ records} \div 5 \text{ s} = 48 \text{ records/s} \approx 1.15 \text{ MB/s per region}$$

That's 48,000 tenant counts a second per region, from 167,000 requests: batching is what makes metering cheap. A Kinesis shard takes 1 MB/s or 1,000 records/s, so 1.15 MB/s needs 2 shards; we run 4 per region, for a region-loss load of 1.5× and headroom. Raw records are about $1.15 \text{ MB/s} \times 2{,}629{,}800 \text{ s} \approx 3.0$ TB a month per region, or about 0.6 TB compressed (assuming about 5× compression for repetitive JSON).

Quota table writes. Per region, 10,000 active tenants written every 5 minutes (33 writes/s) plus about 500 tenants above 80% of quota written every 30 seconds (17 writes/s) is 50 writes a second; each is replicated to two regions:

$3 \text{ regions} \times 50 \times 3 = 450 \text{ units/s} \approx 1.18 \text{B/month} \times \$0.625/\text{M} \approx \$740$

Edge volume. Average global traffic is about a third of peak, ~167K requests a second, which is $166{,}667 \times 2{,}629{,}800 \approx 438$ billion requests a month through WAF. With Shield Advanced ($3,000 a month per organization, 1-year commitment), up to 50 billion WAF requests a month for protected resources are included, along with the web ACL and rule fees:

$(438 - 50) \text{ billion} = 388{,}000 \text{ million} \times \$0.60 \approx \$233{,}000$

Without Shield Advanced, all 438 billion would cost about $263,000, so the $3,000 subscription saves about $30,000 in WAF fees, about $27,000 net of its own fee, before counting its DDoS response support. Its data-transfer-out usage fees depend on our egress volume, and we haven't included them.

Managed rules, scoped. Bot Control and ATP are billed for the requests they inspect, so we scope them to the login and sign-up routes with a scope-down statement. Assuming login and sign-up are about 20 million requests a month, 5 million of them login attempts, Bot Control (common) costs $10 plus $1 per million after the first 10 million: 10 + 10 \times \1 = $20. ATP is priced per 1,000 requests analyzed in tiers (\1.00 for the first 2 million a month, $0.70 for the next 3 million, then less); at an assumed 5 million login attempts a month, that's 2{,}000 + 2{,}100 + 10 = \4{,}110$. An hour of the attack from step 3.3 (1,670 attempts/s ≈ 6 million) would add about$6{,}000 \times $0.40 = $2{,}400$ at the next tier, unless cheaper rules in front of ATP refuse the attack first. That's why rule order is a cost decision too.

Monthly cost (us-east-1 on-demand prices used for all regions; others cost somewhat more):

The lesson in one line: the distributed limiter and metering cost about $12.5K a month; inspecting every request at the edge costs about 19 times that at list price. At this volume, the edge price is a negotiation, and which traffic needs which inspection is an architecture decision (R3.7).

R3.7 Trade-Offs

Rate limits, quotas and load shedding are three different tools.

The opening question was: how do we count fairly across many machines, on every request, without adding latency or becoming the thing that causes the outage? The answer now: count locally and atomically (one script per request in a shared cache, the store's clock), keep hot counts in memory (leases with a proved bound), coordinate off the request path (versioned rules, regional shares, metering streams), and decide in advance what each limit does when its store fails (fail open for capacity, fall back for security). Counting exactly is a separate system, for billing, and protecting a sick backend is a third.

R3.8 Failure Modes

R3.9 Runbook and Incident Response

Golden signals, per region OPS 8 · REL 6

Emergency rule override OPS 10

When an attack needs a new limit now, a security engineer saves a rule set with emergency: true, which skips the canary and needs a second approver. It still carries a version, so it can't be overwritten by a stale change, and it still passes validation:

httpCopy
PUT /v1/rule-sets/public-api HTTP/1.1
Host: ratelimit-admin.internal
If-Match: "1907"
X-Approved-By: sec-oncall-2
Content-Type: application/yaml

rule_set: public-api
emergency: true
expires_after: 4h          # reverts to version 1907's rules unless renewed
rules: [...]

The fleet has it within about 2 seconds. It expires after 4 hours unless renewed, so an emergency limit can't quietly become permanent.

Attack playbook SEC 10

1. Confirm. Is the login failure ratio up? Is the traffic spread over many IPs (step 3.3) or concentrated (per-IP rules should already be firing)? Check which WAF rules are matching.
2. Contain at the edge first. Turn on the challenge action for logins without a device token. Add a new, stricter rate-based rule rather than editing the existing one: AWS documents that changing a rate-based rule's settings resets its counts and can pause its rate limiting for up to a minute.
3. Tighten in the gateway. An emergency rule for the login route's adaptive thresholds.
4. Protect accounts. Force a second factor or password reset for accounts with a successful login from a suspicious client during the window.
5. Watch the cost. ATP is billed per login request it analyzes; make sure cheaper rules in front of it are refusing what they can.
6. Learn. A Correction of Error (COE) review: which signal would have caught it sooner?

Go deeper: CLI playbook

Plain commands an on-call engineer runs, one at a time. Replace names and IDs with real ones.

textCopy
# 1. Is a cache failover in progress, or just finished?
aws elasticache describe-events --source-type replication-group --source-identifier rl-use1 --duration 60

# 2. Shard layout and which nodes are primaries now
aws elasticache describe-replication-groups --replication-group-id rl-use1

# 3. Rehearse a failover of one shard (in a game day, never during an incident)
aws elasticache test-failover --replication-group-id rl-use1 --node-group-id 0003

# 4. Which IPs is a WAF rate-based rule limiting right now? (CloudFront web ACLs live in us-east-1)
aws wafv2 get-rate-based-statement-managed-keys --scope CLOUDFRONT --region us-east-1 --web-acl-name api-edge --web-acl-id 11111111-2222-3333-4444-555555555555 --rule-name ip-flood

# 5. The current rule-set pointer in a region
aws dynamodb get-item --region eu-west-1 --table-name rl-rules --key '{"rule_set": {"S": "public-api#current"}}' --consistent-read

# 6. A tenant's quota usage items for a month, all three regions (read from any replica)
aws dynamodb query --region eu-west-1 --table-name rl-quota-usage --key-condition-expression "pk = :p" --expression-attribute-values '{":p": {"S": "t_acme#2031-03"}}'

# 7. The metering stream's shard count and retention
aws kinesis describe-stream-summary --region eu-west-1 --stream-name rl-usage

# 8. Alarms currently firing for the limiter
aws cloudwatch describe-alarms --region eu-west-1 --state-value ALARM --alarm-name-prefix ratelimit

R3.10 Pillar Check

R3.11 Round 3 Rubric and Follow-Ups

What an architect (L7) answer adds over L6

• Separates rate limiting, quotas and load shedding, and gives each its own mechanism and accuracy target.
• Makes a global limit work without a cross-region call, with shares whose convergence time and error are stated.
• Knows how global tables resolve conflicts, and designs so that conflicts can't happen (one writer per item).
• Builds billing on at-least-once delivery plus idempotent absolute writes, and names the one loss it accepts.
• Treats distributed abuse as a signals problem, not a threshold problem, and places each signal at the layer that can see it.
• Decides what happens in a partition in terms of the customer's contract, per kind of limit.
• Does the build-vs-buy comparison against specific capabilities, and finds where the money really goes.

Follow-up questions

1. "Why not make the quota counter part of the limiter's script? It's already running per request." Answer: the script's state lives in a cache that expires keys, evicts under pressure, fails over with seconds of lost writes, and is skipped entirely when a breaker opens. Each of those is fine for a limit and wrong for an invoice. The metering pipeline is durable (the stream), replayable (checkpoints and the archive) and idempotent (absolute totals), and it's off the request path, so a problem there never slows a request.

2. "A tenant sends all its traffic to one region to get a bigger share. Can it game the global limit?" Answer: no. Shares split one limit $L$; wherever the traffic goes, the shares still add up to $L$. Concentrating traffic just moves the share to that region, 10% of $L$ per rebalance. The only gain is the brief overshoot while shares move, at most one step for one interval.

3. "Your share-sync writes rates every 5 seconds. Why not every 100 ms?" Answer: it would converge faster, but replication takes around a second anyway, so shares couldn't be fresher than that; and writes would go up 50×. Five seconds with a 10% step converges within the 30 seconds the business accepted, for about $44 a month. The right interval comes from the business's tolerance, not from "as fast as possible".

---

Loop Closer: Interview Strategy for All Three Rounds

How to Run Each 60-Minute Round

For how to spend a single 45-minute round, see the 45-minute interview blueprint.

The Two Sentences That Matter Most

• Opening a round: "Before I pick an algorithm: what do we limit by, how exact must it be, are bursts allowed, and what should happen to the API when the limiter itself fails?"
• When the scope is raised: "Here's what breaks in the current design, and here's the order I'll fix it in, starting with anything that could take the API down or let an attacker through."

Well-Architected Review Sheet

Interviewers rarely ask "which pillar is this?". They ask the pillar's question in plain words. Rehearse one sentence per row.

Rubric Across Levels