Concept 3: Rate Limiting

System Design Bible — File 03 of 10 Difficulty: ★★☆☆☆ Prerequisites: Files 01–02, plus the concepts unpacked in Section 0 below.

Table of Contents#

0Prerequisites — What You Must Understand First#

Before rate limiting makes sense, you need four ideas solid. Each is short but load-bearing; skim-reading them is why the rest feels abstract.

0.1What "a request" actually costs the server#

When a client sends an HTTP request, the server doesn't just "answer it." It spends real, finite resources on it: a thread (or async task) is occupied for the duration; a socket / file descriptor is held open; CPU cycles parse, authenticate, and process it; memory buffers the request and response; and often a database connection is checked out from a small pool (typical pools are 10–100 connections total). Every server has a hard ceiling on each of these — you might have 200 worker threads and 50 DB connections, full stop. So "the server can do N requests per second" is not a vibe; it's a number set by whichever of these resources runs out first. Rate limiting exists because once any one of those pools is exhausted, the server can't accept the 201st concurrent request — it queues, then times out, then falls over. Hold this picture: a request is a lease on scarce resources, not a free question.

0.2Why "just add more servers" doesn't remove the need for limiting#

From File 01 you know we scale horizontally by adding servers behind a load balancer. So why limit at all — why not add capacity? Three reasons. (1) Some resources don't scale out: if 100 app servers all share one database, adding app servers just lets them overwhelm the database faster — the bottleneck moved, it didn't vanish. (2) Scaling takes minutes; attacks and spikes take seconds: autoscaling a fleet is a 2–5 minute operation, but a scraper or a retry storm floods you in milliseconds — you need an instant defense, and shedding load is instant. (3) Cost: scaling to absorb a malicious 100× spike means paying for 100× capacity to serve traffic you don't even want. Limiting is the cheap, immediate complement to scaling.

0.3The client's half of the contract: retries and backoff#

A server rarely talks to a single well-behaved client. Real clients retry when they get an error — mobile apps, SDKs, microservices calling each other. If a client retries immediately and forever, then the moment your server is slightly overloaded and starts erroring, every client retries, doubling or tripling the load exactly when you least want it — a self-reinforcing death spiral called a retry storm. The healthy pattern (which you'll see referenced throughout) is exponential backoff with jitter: after a failure, wait 1s; if it fails again, wait 2s; then 4s, 8s… (exponential), each with a random ± spread added (jitter, so a thousand clients don't all retry at the same instant and re-synchronize the storm). Rate limiting (server side) and backoff (client side) are two halves of one stability contract — a limiter only works if clients eventually back off; otherwise you just reject the same flood repeatedly.

0.4Redis, and why distributed counting needs it (from File 02)#

Rate limiting means counting ("how many requests has this key made?"). On one server that's a local variable. But you have many servers (File 01), and the limit is usually global ("1000/min per user across the whole fleet"), so the count must be shared state all servers can read and update. From File 02 you know Redis — an in-memory (RAM-fast, ~0.1–0.5 ms), single-threaded key-value store. Two properties matter here: it's fast enough to touch on every request, and because it's single-threaded, operations like INCR (increment) and Lua scripts run atomically — no two servers can interleave and corrupt the count. That atomicity is the entire reason Redis is the default home for a distributed counter (Section 4). If "atomic," "single-threaded," or "INCR" are fuzzy, re-read File 02 §2.5 before Section 4.

0.5Queueing theory — the actual reason systems collapse instead of degrading#

This is the deepest "why" in the file, and almost nobody teaches it. The naive expectation is that a server at 100% utilization is simply "fully used" — efficient, even. The reality is that response time does not rise linearly with load; it rises hyperbolically and goes vertical near saturation. Rate limiting exists because of the shape of that curve.

The core result. For a simple queueing system where work arrives randomly, the average time a request spends waiting is approximately:

   wait_time  ≈  service_time × ( ρ / (1 − ρ) )        where ρ = utilization (0 to 1)

Substitute real numbers, with a service time of 10 ms:

Read the last two rows. Going from 95% to 99% utilization — a mere 4 percentage points more traffic — makes your service five times slower. Going to 99.9% makes it fifty times slower. There is no "gracefully full" region. A system at 99% utilization is not "nearly optimal," it is milliseconds away from unbounded queueing, and the next small traffic increment does not cost you a small latency increment — it costs you the service.

Why the curve is shaped that way. Because arrivals are random, not evenly spaced. At 50% utilization the idle gaps are large enough to absorb the clumps. As utilization rises, the gaps shrink, so a clump of arrivals that would previously have been absorbed now has to wait behind the previous clump — and the queue from one clump has not drained before the next arrives. Near ρ = 1 the queue never fully drains, so waiting time grows without bound. This is not a property of bad software; it is arithmetic, and it applies to your thread pool, your database connection pool (§0.1), your disk, and the network card.

Little's Law, the other result you should be able to state: L = λ × W — the average number of requests in the system equals the arrival rate times the average time each spends there. It is unconditionally true for any stable system, which makes it a superb sanity check. If you receive 1,000 requests/sec and each takes 200 ms, you have 1000 × 0.2 = 200 requests in flight at all times — so you need at least 200 threads/connections, or you are already queueing. Run that multiplication before choosing a pool size; it converts a guess into arithmetic.

The two conclusions that justify this entire file:

0.6Time, clocks, and why windows are harder than they look#

Every algorithm in §3 is a statement about time, so you must know which clock is being read and how it lies.

Wall-clock time (System.currentTimeMillis(), time.time(), Redis's TIME) is "what time is it in the world." It is what you need for anything expressed in human terms ("resets at midnight"), and it is not monotonic: NTP adjustments, leap-second smearing, VM migrations, and manual changes can move it backwards. A rate limiter that computes elapsed = now − last_seen with a wall clock can get a negative elapsed time, which in a token-bucket refill computes a negative refill, or — worse, if the code clamps at zero — silently freezes the bucket.

Monotonic time (System.nanoTime(), time.monotonic(), CLOCK_MONOTONIC) only ever moves forward and measures elapsed duration, but it has no meaning across machines or across process restarts (it typically counts from boot). The rule: measure durations with a monotonic clock; express absolute deadlines with a wall clock; never mix them in one calculation.

Clock skew across machines is the distributed version of the problem. Two gateway nodes reading their own clocks will disagree by milliseconds normally, and by seconds when NTP is broken — which happens more often than you would like. In a sliding-window log (§3.2), node A writes a timestamp that node B considers to be in the future, and B's pruning logic either keeps entries it should drop or drops entries it should keep. Both directions are wrong, and the failure is silent and traffic-dependent — the worst debugging profile there is.

The mitigation is simple and you should state it by name: use one clock. Do the time arithmetic inside Redis — Redis's TIME command inside a Lua script gives every node the same reading, so skew between application nodes stops mattering entirely. (Note that Redis deliberately forbids calling TIME in older-style replicated scripts precisely because it makes them non-deterministic; modern Redis handles this with effect-based replication, and the practical answer is either to read TIME at the start of the script or to pass the server's time in as an argument.) Every serious distributed limiter does this, and knowing why — that the alternative is skew-dependent silent miscounting — is the interview-grade version of the answer.

Window alignment is the other time trap. If your fixed window is "each calendar minute," then every client in the world resets simultaneously, and you have manufactured a synchronized thundering herd at :00 of every minute — the same synchronization failure as cache avalanche (File 02 §6.2). Two fixes: derive the window start from a hash of the key so that different clients reset at different offsets, or use an algorithm with no shared boundary at all (token bucket, GCRA — §3.7), which is the better answer.

1Architectural Definition & "The Why"#

1.1The Plain Definition#

Rate limiting is the practice of controlling the rate at which clients (users, IPs, API keys, services) are allowed to consume a resource — typically "N requests per time window." When a client exceeds its allowance, further requests are rejected (usually with HTTP 429 Too Many Requests), delayed (throttled/queued), or degraded, rather than served.

Throttling is the closely-related term for slowing down rather than outright rejecting. Rate limiting is the enforcement of a quota; throttling is one way to enforce it (shape traffic to a ceiling).

1.2"The Why" — Protecting Finite Resources from Unbounded Demand#

Every backend has finite capacity — CPU, memory, DB connections, downstream API quotas. Demand, however, is unbounded: a buggy client in a retry loop, a viral spike, a scraper, a credential-stuffing attacker, or a DDoS can all send effectively infinite requests. Without a limiter, unbounded demand meets finite capacity and the result is collapse — the service falls over for everyone, including well-behaved users.

Rate limiting was invented/adopted to enforce fairness and stability:

Connecting to prior files: In File 02 we defended the database against avalanche/stampede miss-storms partly with rate limiting in front of the DB. Rate limiting is the generalized "protect the thing behind me from too much load" primitive, and it usually lives at the load balancer / API gateway (File 01).

2The Recursive Sub-Concept Tree#

2.1Sub-Concept: The Limiting Dimension (the "key")#

The core idea. A rate limit is always the answer to the question "how many requests has who made?" — and that word who is the thing you have to define precisely. You cannot limit "requests" as a global abstract blob, because you need separate running counters that reset independently: my 1000 requests must not use up your budget. So a limiter maintains one counter per identity, and the identity you count by is called the rate-limit key (it's literally the key in the Redis counter, e.g., ratelimit:user:42). Choosing what goes into that key is the single most important design decision in a limiter, because it decides who shares a budget with whom — and that determines fairness, resistance to abuse, and whether legitimate users get wrongly blocked. Let's walk through each option and, critically, why each has the trade-off it does.

Per IP address — key = the client's source IP. This is the easiest to implement because every request already carries a source IP; you need no login, no account, nothing. That's why it's the go-to for blunt, pre-authentication defense (a scraper hitting your public homepage, a volumetric DDoS). But it has two serious weaknesses rooted in how the internet actually works. First, NAT (Network Address Translation) and corporate/mobile proxies make many humans share one IP: an entire office building, a university, or a mobile carrier's users can all appear to your server as a single IP address. So an IP-based limit of "100/min" might be starving 5,000 real people who happen to sit behind one corporate gateway — you block innocents. Second, it's trivially evadable by a motivated attacker, because IP addresses are cheap and rotatable: cloud IPs, botnets, and residential-proxy services let an attacker spread their flood across thousands of IPs, so each individual IP stays under your limit while the aggregate still crushes you. Net: IP keying is a cheap first layer, never a complete answer.

Per user ID / account — key = the authenticated user's ID. This is fair in the way IP is not: the limit follows the human/account regardless of what network they're on, so the office building's 5,000 users each get their own budget, and an attacker can't dodge it by rotating IPs (they'd have to create thousands of accounts, which is a higher bar you can defend separately). The cost is that it requires authentication — you only know the user ID after you've verified their login/token, which means (a) it's useless for limiting unauthenticated endpoints like the login page itself (chicken-and-egg: you're trying to throttle login attempts but don't have a user until login succeeds), and (b) the auth step itself costs resources, so a flood of unauthenticated junk can still hurt you before user-keying kicks in. In practice you layer IP-keying on public/auth endpoints and user-keying on everything behind login.

Per API key / client ID — key = the API token identifying a calling application (not a human). This is the standard for API products (Stripe, Twilio, GitHub API), because your customer is a program, and the API key both authenticates it and identifies which paying account it belongs to. It's the cleanest of all: strong identity (the key is a secret credential, hard to forge), directly tied to a billing tier (so you can enforce "free tier = 100/day, enterprise = 1M/day" by looking up the key's plan), and not subject to the NAT problem (each integration has its own key). This is why it's the backbone of monetized APIs.

Per endpoint — key includes which route is being called, so different endpoints get different limits. The reason you need this: not all requests cost the same (recall §0.1 — a request is a lease on resources, and some leases are far heavier). A GET /health that returns a static "OK" costs almost nothing; a POST /search that scans a database or a GET /export that generates a 50MB report costs thousands of times more CPU, memory, and DB time. A single blanket "1000 requests/min" limit is wrong for both — it's absurdly loose for /export (100 concurrent exports would melt you) and needlessly tight for /health. So you tighten the expensive endpoints (/export: 5/min) and loosen the cheap ones. You rarely key only by endpoint; you combine it with an identity (next item).

Global — key = a single fixed constant, so all traffic shares one counter. Use this to protect a shared downstream dependency with a hard ceiling, regardless of who's calling. Example: your service calls a third-party payment API that permits only 500 requests/sec total across your whole company — exceed it and they start rejecting you. A global limiter caps your aggregate outbound rate to 500/s so you never trip their limit and get your account throttled. It's about protecting a resource that has an absolute limit, not about fairness between callers.

Composite — key = a combination of the above, e.g., (api_key, endpoint). This is what real systems almost always use, because you usually want several of the properties at once. (api_key + endpoint) means each customer gets a separate budget per endpoint: customer A hammering /search uses up only their /search budget, not their /export budget and not customer B's /search budget. You can go further — (user_id, endpoint, method) — to slice as finely as the abuse patterns require. The trade-off is counter explosion: every distinct key is a distinct counter in Redis, so (user × endpoint) for 10M users × 50 endpoints = up to 500M possible counters (mitigated by short TTLs so idle counters expire, but it's a real memory-and-cardinality consideration).

The decision, summarized. You're trading ease of implementation (IP needs nothing; user/API-key needs auth) against fairness (does one entity's abuse hurt innocents who share its key?) against abuse-resistance (how hard is the key to rotate/forge?). There is no single right key — production systems stack them: a coarse per-IP limit at the edge to shed volumetric junk cheaply, then a fair per-user/per-API-key limit behind auth, often made composite with the endpoint. Interviewers probe this precisely because naming "per user" without explaining why not just IP (the NAT and rotation problems) is the tell of someone who memorized a list versus understood the trade-off.

2.2Sub-Concept: Hard vs. Soft Limits; Rejection vs. Throttling vs. Shaping#

When a client crosses its limit, you have a choice about what "enforcement" means — and it's genuinely a choice, with different UX and safety implications, not a single fixed behavior.

Hard limit → reject. The strict version: once the counter says "over," the request is refused outright with a 429 Too Many Requests (§2.4). Nothing is processed; the client must wait and retry. This is the safest for you (zero extra work done for over-limit requests — you protect the backend maximally) and the correct default for abuse defense and hard capacity ceilings. Its downside is bluntness: a legitimate user who briefly spikes gets a hard error.

Soft limit → allow but flag. A gentler version: when the client crosses the threshold, you still serve the request, but you record the breach and act on it out-of-band — log a warning, emit a metric, bill overage charges, drop the request's priority, or send the customer a "you're approaching your limit" email. This is common in monetization ("we won't cut you off mid-launch, but you'll be invoiced for the overage") and in gradual rollouts of a new limit (observe who would be blocked before you actually block them). The trade-off is obvious: you're accepting the extra load and cost in exchange for a friendlier experience and better signal.

Throttling / shaping → delay, don't drop. Instead of rejecting the over-limit request, you hold it in a queue and release it later, at the permitted rate. The client's request eventually succeeds — it just takes longer. This smooths a bursty client into a steady stream rather than dropping their excess. It's ideal when the requests genuinely need to complete (you don't want to lose them) and a bit of added latency is acceptable — e.g., a batch job, or protecting a fragile downstream that needs a constant feed. The cost is that queuing adds latency and consumes memory (the queued requests sit somewhere), and under sustained overload the queue eventually fills and you're back to dropping. This delay-based enforcement is exactly what the leaky bucket algorithm (§3.5) implements.

How to choose: reject (hard) for abuse and hard ceilings where doing no work for bad traffic is the point; soft for monetization and safe rollouts; throttle/shape when the requests are legitimate and worth delaying rather than losing.

2.3Sub-Concept: Burst vs. Sustained Rate#

This distinction is why simplistic limiters feel wrong in practice, so it's worth understanding deeply. Real traffic is not smooth — it is bursty. A user opening your dashboard fires 20 API calls in the first 200 milliseconds (loading widgets, avatars, notifications) and then nothing for 30 seconds while they read. A mobile app coming back from background syncs a batch at once. This is normal, legitimate behavior. So a limit has to describe two different things:

Sustained (average) rate — the rate you can keep up forever, the long-run ceiling. "100 requests per second, on average, indefinitely." This is set by your steady-state capacity (§0.1): the rate at which your threads/DB/CPU can churn through work without a growing backlog.

Burst capacity — how big a momentary spike above the average you'll tolerate before clamping down. "You may fire up to 500 requests in a quick burst, then you're held to the 100/s sustained rate." This exists because short spikes are harmless: your server has buffers and brief idle capacity, so absorbing a 500-request burst that then goes quiet is fine — the average over any real window is still fine.

Why you need both, concretely. Imagine you only enforced the sustained rate as a rigid "no more than 100 in any given second." The dashboard user's legitimate 20-calls-in-200ms opening would be fine (20 < 100), but a slightly heavier page firing 150 calls on load would be wrongly blocked even though the user then sits idle for a minute — their true average is trivial. Conversely, if you only allowed bursts with no sustained cap, a client could sustain the burst rate forever and overwhelm you. So the right limit is "average X with bursts up to Y" — and the beautiful thing is that the token bucket algorithm (§3.4) models exactly this pairing natively: the bucket size is the burst capacity Y, and the refill rate is the sustained rate X. When you see token bucket described as "the most popular algorithm," this is why — it's the one that matches how real traffic actually behaves.

2.4Sub-Concept: The 429 Response & Retry-After#

The standard rejection is HTTP **429 Too Many Requests**. A well-behaved API includes headers so clients can adapt:

Well-designed limits are communicative — they tell clients how to behave, which reduces retry storms.

2.5Sub-Concept: Idempotency & Retries (why limiting and retrying interact)#

Clients retry failed/429'd requests. If they retry aggressively without backoff, they amplify the overload the limiter is trying to prevent (a retry storm). Correct client behavior is exponential backoff with jitter (wait 1s, 2s, 4s… plus randomness). Rate limiting on the server and backoff on the client are two halves of the same stability contract.

The retry-amplification arithmetic, because the number is worse than intuition suggests. Suppose a client retries up to 3 times. In healthy operation, load is 1×. The moment your service starts failing, every failed request becomes up to 4 requests — your load quadruples exactly when you have the least capacity to serve it. Now add a second tier: if service A calls service B, and both retry 3×, a single user request can become 16 requests at the bottom of the stack. Three tiers: 64. This is retry amplification, and it is how a brief blip becomes a total outage.

Three mitigations you should be able to name:

The interview-grade point: a rate limiter that returns 429 to clients that immediately retry has not shed load — it has converted expensive work into cheap work, which helps, but the flood continues. Load shedding only truly works when the client cooperates, which is why Retry-After (§2.4) and client-side backoff are part of the limiter's design, not separate concerns.

2.6Sub-Concept: Rate vs. Quota vs. Concurrency — three different limits people conflate#

These three answer different questions, protect against different failures, and are frequently confused in interviews. Get them straight.

A rate limit bounds requests per unit of time: "100 requests per second." It protects against throughput exhaustion — too much work arriving per second for your CPU, database, or downstream to keep up. Every algorithm in §3 implements this.

A quota bounds total consumption per long period, usually for billing rather than for stability: "1,000,000 requests per month," "50 GB of egress per day." The distinguishing property is that a quota has no burst behaviour and no smoothing intent — it is an accounting total, reset on a calendar boundary, and its enforcement is typically "you are cut off" or "you are billed for overage" (§2.2's soft limit). Implementation differs too: a quota counter must be durable (losing the month's count to a Redis restart is a billing incident), whereas a rate-limit counter is disposable by design. Do not store quotas in a cache with an eviction policy — that is File 02 §10.7's anti-recommendation appearing here in a new costume.

A concurrency limit bounds requests in flight simultaneously: "at most 50 concurrent requests per tenant." This is the one people forget, and it protects against a failure that rate limiting cannot touch. Consider: a tenant sends 10 requests per second, comfortably under a 100/s rate limit — but each request is a report that takes 60 seconds. By Little's Law (§0.5), they now hold 10 × 60 = 600 requests in flight, occupying 600 threads and 600 database connections. Your rate limiter is perfectly satisfied while your server has no threads left. Rate limits bound arrival; only concurrency limits bound occupancy — and occupancy is what actually exhausts pools. This is exactly why Stripe runs a concurrency limiter alongside its rate limiter (§9.1), and saying so is a strong senior signal.

The implementation is a semaphore, not a counter: acquire a permit on entry, release it on exit (in a finally block, always — a leaked permit is a permanent capacity loss that looks like a slow memory leak in your throughput). Distributed version: a Redis set or counter that is incremented on start and decremented on completion, with a TTL on each entry so that a client that crashes mid-request does not hold its permit forever. That TTL is mandatory: without it, one crash per hour silently shrinks your concurrency limit to zero over a day.

Use all three together. Rate limit for throughput, concurrency limit for occupancy, quota for billing. They are complements, not alternatives.

2.7Sub-Concept: Cost-Based (Weighted) Limiting#

The assumption baked into "100 requests per minute" is that all requests cost the same. §2.1 already noted they do not; cost-based limiting is the fix that takes that seriously.

The mechanism: instead of decrementing the counter by 1 per request, decrement it by that request's cost, computed from what the request actually consumes. A token bucket (§3.4) handles this natively — spend n tokens instead of 1 — which is one more reason it is the dominant algorithm.

Where cost is known in advance: a static weight per endpoint. GET /health costs 1, GET /users/:id costs 1, POST /search costs 10, GET /export costs 500. The client's budget is then denominated in "cost units per minute," and one export consumes what 500 health checks would. GitHub's GraphQL API does exactly this — it computes a query's point cost from the query itself (how many nodes it will traverse) before executing it, which is the only sane way to limit an API where a single request can ask for arbitrarily much.

Where cost is only known afterwards — and this is the modern case that matters — you must limit on consumption, not requests. LLM APIs are the canonical example: Anthropic's and OpenAI's APIs limit on tokens per minute alongside requests per minute, because one request can consume a hundred thousand times more compute than another. The pattern is: reserve an estimate up front, reconcile the actual afterwards. Deduct the estimated token count when the request starts (so concurrent requests cannot all sail through on a stale balance), then refund or additionally charge the difference when it completes. Databases do the analogous thing with I/O credits; AWS does it with burst-balance mechanics on EBS and older EC2 instance classes.

The trade-off: cost-based limiting is fair in the way request-counting is not — it prices the actual resource — but it requires you to know the cost, either by static assignment (which drifts as your code changes and someone forgets to update the weight) or by estimation (which is wrong, sometimes badly). The mitigation: measure real per-endpoint cost from production telemetry and revisit the weights, rather than assigning them once from intuition.

2.8Sub-Concept: Determining the Client's Identity Safely (the X-Forwarded-For trap)#

§2.1 said "key by IP" as though the IP were simply available. Behind a proxy it is not, and getting this wrong produces a limiter that is trivially bypassed — a security hole, not a bug.

Recall File 01: a full-proxy load balancer terminates the client's connection, so your application's socket shows the proxy's IP, not the client's. The real address is passed in a header — X-Forwarded-For (a comma-separated chain, appended to by each proxy), or Forwarded (the standardized version, RFC 7239), or the Proxy Protocol at L4. So the application reads the header.

And now the vulnerability: headers are client-supplied data. An attacker simply sends X-Forwarded-For: 1.2.3.4 with a random value on every request, and if your limiter trusts it, every request appears to come from a different client and your rate limiter does nothing at all while reporting healthy metrics. Worse, an attacker can forge the IP of a victim and get them blocked — turning your limiter into a denial-of-service tool aimed at your own users.

The correct rule: trust exactly as many entries as you have proxies you control, counting from the right. If you run one load balancer, the client IP is the last entry in the chain (the one your LB appended); everything to the left was supplied by the client and is untrustworthy. Frameworks express this as a "trusted proxy count" or a list of trusted proxy CIDRs — configure it explicitly. Cloud providers give you an unforgeable equivalent (CloudFront's CloudFront-Viewer-Address, Cloudflare's CF-Connecting-IP) precisely because these are set by their edge and stripped from client input.

Beyond IP: for abuse resistance you often need identity that survives IP rotation — a device fingerprint, a TLS fingerprint (JA3/JA4, which hashes the client's TLS handshake parameters and is far harder to vary than an IP), an account, or a payment instrument. Each step up that ladder is harder to forge and harder to obtain, and the honest interview answer is that you layer them rather than picking one.

One more subtlety worth naming: IPv6. Limiting a single IPv6 address is nearly meaningless, because a residential customer is typically handed a /64 — eighteen quintillion addresses — and can rotate freely inside it at zero cost. Limit IPv6 clients by prefix (/64 for a host, /56 or /48 for a site), not by address. Getting this wrong means your IPv6 limiter is decorative.

2.9Sub-Concept: Load Shedding and Priority#

Rate limiting asks "has this client had too much?" Load shedding asks a different question: "is the system in trouble right now, and if so, what should I drop?" The distinction matters because a system can be overloaded while every individual client is within its limit — a flash sale, a viral moment, or a partial capacity loss all produce this.

The mechanism: monitor a real saturation signal and, when it degrades, start rejecting a fraction of traffic. The signal choice is the whole design:

Priority is what makes shedding acceptable. Dropping traffic at random damages everything equally. Instead, classify traffic by criticality and shed from the bottom: prefetch and analytics beacons first, then background sync, then browsing, and never checkout, payment, or auth. Google's published approach uses a small number of criticality levels propagated through the whole call chain, so a downstream service knows whether the request it is serving ultimately belongs to a checkout or to a dashboard refresh. This propagation is the hard part — criticality must ride in the request context across every hop or the deepest service, the one that most needs to shed correctly, is flying blind.

The trade-off: shedding keeps the service alive for the traffic that matters, at the cost of visibly failing some requests and of the machinery to classify them. The failure mode to avoid: shedding based on a signal that the shedding itself improves, with no damping — you drop traffic, the signal recovers, you stop dropping, the flood returns, you drop again. That oscillation is worse than steady partial shedding; damp it with hysteresis (different thresholds for entering and leaving the shedding state).

2.10Sub-Concept: Backpressure#

Backpressure is the generalization of everything above: when a consumer cannot keep up, it propagates that fact upstream so producers slow down, rather than silently accumulating an unbounded queue.

You have already met it without the name. TCP has it built in: the receive window in every TCP header (File 01 §0.5) tells the sender exactly how much more the receiver is willing to accept — when the receiver's buffer fills, it advertises a zero window and the sender stops transmitting. That is backpressure implemented in the transport, and it is why TCP does not melt down when a fast server talks to a slow client.

The application-level equivalents: bounded queues that block or reject on put (never unbounded — an unbounded queue is a memory leak with extra steps and converts a fast failure into a slow, total one), reactive-streams demand signalling (request(n): the consumer states how many items it can take), gRPC and HTTP/2 flow control per stream, and consumer-driven pull in message systems (Kafka consumers pull at their own pace, which is exactly why Kafka absorbs bursts so well — File 07).

Why it beats rate limiting where it applies: a rate limit is a guess at the right rate, configured in advance and stale the moment your hardware or code changes. Backpressure is measured — the consumer's actual capacity, right now, communicated directly. Why you still need rate limiting: backpressure requires a cooperative producer inside your trust boundary. An anonymous attacker on the internet will not honour your demand signal, and a third-party client will not either. The rule: backpressure inside your system, rate limiting at its edges.

2.11Sub-Concept: Adaptive / Dynamic Limits#

Every limit discussed so far is a static number a human chose — and that number is wrong the moment you deploy new hardware, ship a performance regression, lose an availability zone, or add a caching layer. Adaptive limiting derives the limit from live measurement instead.

The mechanism, borrowed directly from TCP congestion control: AIMD — additive increase, multiplicative decrease. While the system is healthy (latency stable, errors low), raise the limit by a small increment. The moment a congestion signal appears (latency rising, errors, queueing delay past target), cut the limit by a multiplicative factor — typically halve it. The asymmetry is deliberate and is the reason TCP works: you probe for more capacity slowly and retreat from overload fast, because the cost of overshooting is far higher than the cost of under-using.

The concrete implementation most worth naming is **Netflix's concurrency-limits library, which applies Little's Law (§0.5) in reverse: it continuously measures the minimum observed latency (an estimate of the service time with no queueing) and the current latency, infers how much queueing exists, and adjusts the concurrency limit to keep queueing near zero. The elegance is that it needs no configuration at all** — no one has to guess "50 concurrent requests"; the system discovers its own capacity and re-discovers it after every deploy.

3The Algorithms — Exhaustive Breakdown#

This is the core of the file. There are five canonical algorithms. Know each one's mechanics, memory cost, burst behavior, and boundary accuracy.

3.1Fixed Window Counter#

Mechanism: Divide time into fixed windows (e.g., each calendar minute). Keep a counter per key per window. Increment on each request; if the counter exceeds the limit within the current window, reject. At the window boundary, reset the counter to 0.

limit = 100 / minute
key "user:42" -> counter for window [12:00:00 - 12:00:59]
  request -> counter++ ; if counter > 100 -> 429
at 12:01:00 -> counter resets to 0

3.2Sliding Window Log#

Mechanism: Store a timestamp for every request (a log) per key, in a sorted structure. On each new request, drop timestamps older than now - window, then count what remains; if count < limit, allow and append the new timestamp; else reject.

On request at time T:
  remove all timestamps < (T - window)
  if len(log) < limit: append T; ALLOW
  else: REJECT

3.3Sliding Window Counter (the pragmatic favorite)#

Mechanism: A hybrid that approximates the sliding log with fixed-window memory. Keep counters for the current and previous fixed windows, and compute a weighted estimate based on how far into the current window we are.

limit = 100/min. Previous minute count = 80, current minute count = 30.
We are 25% into the current minute (15s of 60s elapsed).
estimate = current + previous * (1 - elapsed_fraction)
         = 30 + 80 * (1 - 0.25) = 30 + 60 = 90  -> under 100, ALLOW

3.4Token Bucket (the burst-friendly workhorse)#

Mechanism: Imagine a bucket that holds up to B tokens (the burst capacity). Tokens are **refilled at a steady rate r tokens/sec** (the sustained rate), up to the cap B. Each request must remove one token to proceed. If the bucket has a token, allow and decrement; if empty, reject (or wait).

bucket capacity B = 500 (burst), refill r = 100 tokens/sec (sustained)
- Idle client accumulates up to 500 tokens.
- A burst of 500 requests drains the bucket instantly -> all allowed.
- After that, requests succeed only as fast as tokens refill (100/s).

3.5Leaky Bucket (the smoother / traffic shaper)#

Mechanism: Requests enter a queue (the bucket). The queue is drained (processed) at a fixed, constant rate — like water leaking from a hole at the bottom. If the queue is full, new requests overflow and are dropped.

Requests arrive bursty -> enter FIFO queue (size Q)
Processor pulls from queue at a CONSTANT rate r (e.g., 100/s)
Queue full -> drop new arrivals

The distinction that trips people up: leaky bucket has two forms. What §3.5 describes is the leaky bucket as a queue (a shaper) — requests are held and released at a constant rate, so nothing is dropped until the queue overflows, and latency is added deliberately. There is a second form, the leaky bucket as a meter (a policer), in which nothing is queued at all: you merely track a virtual water level that rises by one on each request and drains at rate r, and you reject any request that would overflow the bucket. The meter form is mathematically equivalent to the token bucket — one counts water rising toward a ceiling, the other counts tokens falling toward zero, and they admit exactly the same request sequences. Knowing that these are the same algorithm viewed from two ends, and that only the queue form actually shapes traffic, is a genuine senior distinction, and it is the bridge to GCRA below.

3.6GCRA — The Generic Cell Rate Algorithm (the elegant one nobody teaches)#

What it is. GCRA comes from ATM telecom networking, where it was the standard traffic policer, and it is a token bucket that stores a single timestamp instead of a counter. It is the algorithm behind Redis's redis-cell module and several production limiters, and it is worth knowing precisely because it eliminates the two operational annoyances of token bucket: storing two mutable fields, and having to reason about refill.

The insight. Rather than track "how many tokens do you have," track "what is the earliest time at which your next request would be conforming?" — a single value called the TAT (Theoretical Arrival Time). Everything else falls out of arithmetic.

The mechanism. Two parameters: the emission interval T = 1 / rate (the minimum spacing between requests at the sustained rate) and the burst tolerance τ = (burst − 1) × T (how far ahead of schedule a client is allowed to run). On a request at time t:

   if TAT is unset:  TAT = t
   if t < TAT − τ:     REJECT   (too far ahead of schedule)
   else:               ALLOW, and TAT = max(TAT, t) + T

Worked example. Rate = 1 request/second (T = 1 s), burst = 3 (τ = 2 s). Client is idle, then fires four requests at t = 10.0:

   t=10.0  TAT unset -> TAT=10.0.  10.0 < 10.0−2 ? no  -> ALLOW, TAT = 11.0
   t=10.0  10.0 < 11.0−2 = 9.0 ?   no  -> ALLOW, TAT = 12.0
   t=10.0  10.0 < 12.0−2 = 10.0 ?  no  -> ALLOW, TAT = 13.0
   t=10.0  10.0 < 13.0−2 = 11.0 ?  YES -> REJECT

Exactly three allowed in the burst, then rejection — matching the intended burst of 3 — and the client may proceed again at t = 11.0, one per second thereafter. Notice what you get for free: **TAT − τ − t is precisely how long the client must wait**, so Retry-After (§2.4) comes out of the algorithm exactly rather than as an estimate. That is a real advantage in practice; most limiters can only approximate that header.

3.7Concurrency Limiting (the semaphore) — the algorithm that is not about time#

Included here because §2.6 established that rate limits cannot bound occupancy, and occupancy is what exhausts pools. This is a limiting algorithm even though it has no time window at all.

Mechanism. Maintain a count of in-flight requests per key. On arrival, if in_flight < limit, increment and proceed; otherwise reject (or queue). On completion — success, error, timeout, or panic — decrement.

   acquire:  if in_flight >= limit -> REJECT
             in_flight += 1
   ...serve the request...
   release:  in_flight -= 1        <-- MUST be unconditional (finally / defer)

Distributed version. A Redis sorted set per key, where each in-flight request adds a member (a unique request ID) scored by its start time. On arrival: remove all members older than a timeout (that is your crash-recovery mechanism), count what remains with ZCARD, and add the new member if under the limit — all in one Lua script for atomicity (§4.2). On completion, ZREM the member.

3.8Adaptive Limiting (AIMD) — the algorithm with no configured limit#

The mechanised form of §2.11, included because "the limit itself is a variable" is a genuinely different algorithm, not a tuning detail.

Mechanism. Maintain a current limit L. Continuously sample a health signal — queueing delay, error rate, or latency versus the minimum observed latency. Then:

   every measurement window:
      if healthy:     L = L + 1                 (additive increase — probe carefully)
      if congested:   L = L × 0.5               (multiplicative decrease — retreat fast)
      clamp L to [L_min, L_max]

Why the asymmetry is correct, and why it is not arbitrary. Overshooting the limit costs you a queue that goes hyperbolic (§0.5); undershooting costs you only some unused capacity. The costs are wildly asymmetric, so the response must be too: creep upward, collapse downward. This is exactly TCP's congestion window, and it is one of the most-validated control laws in computing — it is what keeps the internet from congestion collapse.

The Netflix refinement (gradient-based). Rather than a binary healthy/congested signal, compute gradient = latency_minimum / latency_current. A gradient near 1 means no queueing (current latency equals the no-load latency), so grow; a gradient well below 1 means requests are queueing, so shrink proportionally to how bad it is. This converges faster and oscillates less than binary AIMD.

3.9Algorithm Comparison Table#

Fuller comparison across the dimensions that decide real choices:

3.10The Decision Rule#

Answer in this order; each question eliminates alternatives:

In one line: token bucket or GCRA for public APIs, sliding-window counter when you want cheap accuracy, leaky-bucket-queue when the downstream demands smoothness, sliding-window log when exactness is contractual, and a concurrency limit alongside all of them because none of them bound occupancy.

4Distributed Rate Limiting#

The single-server case is easy (a local counter). The hard, interview-worthy problem: you have 50 API gateway/LB instances behind a load balancer, and the limit is "1000 req/min per API key" globally. No single instance sees all the traffic. How do you enforce a global limit?

4.1The Core Problem#

If each of 50 instances independently enforces "1000/min," a client can do 50 × 1000 = 50,000/min — 50× the intended limit. You need shared state that all instances consult.

4.2Solution A: Centralized Counter in Redis (the standard answer)#

Keep the counters in a shared Redis (from File 02). Every instance does its increment/check against Redis, so all instances share one source of truth.

Naive (racy) version:

count = GET key
if count < limit: INCR key; allow
else: reject

This has a race condition: two instances both GET 999, both think "under 1000," both INCR → 1001. Over-limit.

Correct version — atomic Lua script: Run the read-check-increment as a single atomic operation on Redis (Redis executes Lua scripts atomically, single-threaded):

-- atomically: increment, set expiry on first hit, return new count
local current = redis.call("INCR", KEYS[1])
if current == 1 then redis.call("EXPIRE", KEYS[1], window) end
if current > limit then return 0 else return 1 end

Because Redis runs it atomically, no two instances can race. This is the canonical distributed fixed-window limiter. Token bucket and sliding window are likewise implementable as atomic Lua scripts (compute-refill-and-spend in one shot).

4.3Solution B: Local Token Buckets + Async Sync (the scalable approximation)#

To avoid a Redis call on every request, each instance keeps a local bucket and periodically syncs/reconciles with a central store (or gossips with peers). Each instance is allocated a share of the global budget and adjusts based on observed global usage.

4.4Solution C: Sticky Routing#

Route all requests for a given key to the same instance (consistent hashing by API key at the LB — File 06). Then each instance owns a disjoint set of keys and can limit locally with no shared state.

4.5The Fundamental Trade-off (CAP-flavored, foreshadowing File 08)#

Distributed rate limiting forces a choice: accuracy vs. latency/availability.

Most large systems (Stripe, Cloudflare) choose approximate + fast, accepting small overshoot. State this trade-off explicitly in interviews.

Fail-open vs fail-closed: if the Redis/limiter store is down, do you allow all requests (fail open — prioritize availability, risk overload) or reject all (fail closed — prioritize protection, risk outage)? For public APIs, usually fail open (don't let the limiter itself cause an outage). For abuse/security-critical limits (login), sometimes fail closed. A deliberate choice, not an accident.

4.6Solution D: Batched / Probabilistic Reservation (how you cut the Redis hop without losing much accuracy)#

Between "check Redis every request" (§4.2) and "sync occasionally" (§4.3) sits the approach most high-volume systems actually use: acquire permits in batches.

Mechanism. Instead of decrementing the shared counter by 1 per request, an instance atomically reserves a block of N permits from Redis (say 20), spends them locally with zero network cost, and returns for another block when it runs out. Redis traffic drops by a factor of N immediately.

The trade-off is precise and worth stating in exactly these terms: with M instances each holding up to N unspent permits, the worst-case overshoot is M × N requests beyond the limit — because an instance can hold permits it never spends while others are being refused. So batch size is a directly tunable accuracy-versus-load dial: N = 1 is §4.2 (exact, expensive), large N is §4.3 (cheap, sloppy). The refinement: make N adaptive — a client sending 10,000 req/s gets large batches (the relative error is negligible), while a client sending 2 req/s gets N = 1 (exact, and the Redis load is trivial anyway). This gives you accuracy exactly where it is cheap and approximation exactly where it is needed.

Unspent permits must expire, or an instance that goes idle (or is removed from rotation) permanently removes those permits from the global budget — a slow leak that shrinks your effective limit over time. Same failure shape as the leaked semaphore permit in §3.7.

4.7The Practical Concerns That Decide Whether Your Distributed Limiter Works#

Four operational realities that the three-solutions framing above glosses over.

**The limiter's Redis must be sized for every request, not for cache traffic. A cache absorbs reads; a limiter is consulted on 100% of requests including the ones it rejects. At 50,000 req/s your limiter Redis is doing 50,000 ops/s minimum — well within Redis's capability, but it means the limiter's store is now on the critical path of literally everything. Give it its own instance.** Sharing it with your cache means a cache incident (a big-key DEL, a KEYS scan — File 02 §2.7/§2.8) blocks your limiter, and a blocked limiter with a fail-closed policy is a total outage.

Hot keys apply here exactly as in File 02 §2.8. One enormous tenant means one key means one shard, and that shard receives that tenant's entire traffic. Mitigations, in order: a local pre-filter (the batching of §4.6 collapses a whale's traffic into occasional block reservations), splitting the whale's key into tenant:whale:shard0…shardN with each instance choosing one and each shard holding 1/N of the budget, or giving the largest tenants dedicated limiter capacity.

Latency budget. A limiter check that adds 0.5 ms to every request is usually fine; one that adds 5 ms because the Redis is cross-AZ or the connection pool is undersized is not. Two specifics: keep the limiter store in the same availability zone as the callers where possible (cross-AZ round trips are ~1 ms rather than ~0.2 ms), and always set an aggressive timeout on the limiter call itself — 10–50 ms — with fail-open on timeout. Without that timeout, a slow Redis converts into slow requests for everyone, which is the queueing spiral of §0.5 triggered by your own protective machinery.

Fail-open, done properly. "Fail open" does not mean "no limiting." It means fall back to a local limit, set generously (say 2–5× the per-instance share of the global limit), so that during a limiter-store outage you are still protected against the extreme case while not rejecting legitimate traffic. Pair it with an alarm, because a silently fail-open limiter can stay broken for weeks — the system looks perfectly healthy right up until someone abuses it. The interview line: "fail open to a degraded local limit, never fail open to unlimited."

5Where to Enforce & How to Respond#

5.1Placement (defense in depth)#

Layer them: coarse volumetric limits at the edge, per-key limits at the gateway, business limits in the app.

5.2Responding Well#

6Pros, Cons & Trade-offs#

6.1Benefits#

6.2Costs & Trade-offs#

7Interview Diagnostic Framework (Symptom → Solution)#

8Real Implementations & Product Landscape#

You will almost never write a rate limiter from scratch — you will configure one. This section is what exists, which algorithm each one actually implements (they differ, and the difference is visible in your traffic), and which to choose.

8.1Family 1 — Edge and CDN limiters#

Cloudflare Rate Limiting. Enforced at hundreds of PoPs before traffic reaches your network, which is the cheapest possible place to drop junk — you pay nothing in origin capacity for a request Cloudflare rejected. It implements a sliding window counter (§3.3) with local counting plus asynchronous cross-PoP reconciliation, which is the §4.3 approximation applied at planetary scale: a client hitting five PoPs is counted approximately, not exactly, because a synchronous global count would add cross-ocean latency to every request. Rules can key on IP, header, cookie, query parameter, or JA3/JA4 TLS fingerprint (§2.8), and can act with block, challenge (CAPTCHA/JS), or log-only — that last one being how you safely roll out a new limit (§2.2's soft limit). Limits: approximate global counts (deliberately); you are trusting a third party with your traffic. Reach for it when you face volumetric abuse, scrapers, or credential stuffing — anything you want stopped before your bill starts.

AWS WAF rate-based rules count requests per IP (or per header/cookie via custom aggregation keys) over a fixed 5-minute sliding evaluation, with a coarse evaluation granularity — it is designed for volumetric defence rather than precise per-second limits. Fastly exposes rate limiting through VCL/Compute with edge-local counters. Akamai offers similar controls. The universal trade at the edge: cheapest enforcement, coarsest accuracy, and no application context — the edge does not know that this user is on the enterprise plan.

8.2Family 2 — Reverse proxies and load balancers#

**NGINX limit_req. Important detail almost everyone gets wrong: limit_req implements a leaky bucket, not a token bucket.** Without the burst parameter it enforces a strictly smooth rate and rejects anything arriving early — which is why naïvely setting rate=10r/s and then seeing legitimate page loads rejected is such a common surprise (a browser firing 10 parallel asset requests in 50 ms is not 10 requests per second by NGINX's reckoning). Adding burst=20 gives a queue of 20 that is drained at the configured rate — the leaky-bucket-as-queue of §3.5, with real added latency. Adding nodelay serves the burst immediately while still consuming queue slots, which converts it into token-bucket-like behaviour. **limit_conn is the separate directive implementing a concurrency limit (§3.7). Counters live in a shared memory zone — per NGINX instance, so with N load balancers your effective limit is N × the configured value (§4.1). Reach for it when you already run NGINX and want a solid local limiter; not when** you need one global count across instances.

HAProxy stick tables. HAProxy's mechanism is unusually powerful: a stick table is an in-memory table keyed by anything you can extract from a request (source IP, header, URL parameter), storing counters, rates, and error counts, with built-in peer replication — HAProxy instances synchronize their stick tables with each other over a peers protocol. That means you get approximately global counting with no external datastore at all, which is the §4.3 local-plus-sync design shipped as a feature. It also tracks derived signals like HTTP error rate per key, so you can limit clients that generate errors rather than merely clients that are busy. Reach for it when you run HAProxy and want distributed-ish limiting without adding Redis.

Envoy offers both: a local rate limit filter (token bucket, per-instance, zero latency) and a global rate limit service — Envoy calls out over gRPC to an external service (the reference implementation, envoyproxy/ratelimit, is Redis-backed) on each request. The two are designed to be layered: local first to cheaply shed obvious excess, global second for accurate cross-fleet limits. Envoy also implements retry budgets and circuit breaking (§0.3, §2.5) in the same data plane, which is a genuine architectural advantage — the limiter and the retry policy are configured together rather than in two unrelated systems. This is the model to describe in an interview when asked how to do it properly in a microservice environment.

8.3Family 3 — API gateways#

Kong ships two plugins whose difference is the entire lesson: rate-limiting (fixed window, counters in a local store, Redis, or Postgres) and rate-limiting-advanced (sliding window, Redis-backed, with more key options). Choosing the basic one and then being surprised by the 2× boundary burst is a real, common outcome (§3.1). AWS API Gateway exposes a token bucket directly — rate is the refill rate and burst the bucket size (§9.3) — applied at account, stage, method, and per-API-key levels through usage plans, which is how you implement tiered pricing without writing code. Apigee, Tyk, and Azure API Management offer comparable quota-plus-spike-arrest pairs; note that Apigee's "Quota" and "Spike Arrest" policies are precisely the §2.6 quota-versus-rate distinction exposed as two separate policies, which is a well-designed API worth citing.

API gateways are where tiering lives, because they are the layer that already knows which API key maps to which plan. Doing this at the edge is impossible (no plan context) and doing it in the application is late (you have already paid for auth and routing).

8.4Family 4 — Datastore-backed limiters you build#

Redis + Lua is the canonical build-it-yourself answer (§4.2), and the reason is atomicity (§0.4). Notable ready-made pieces: **redis-cell, a Redis module implementing GCRA** (§3.6) as a single CL.THROTTLE command that returns allowed/denied, remaining quota, and the exact retry-after — the cleanest primitive available; and the widely-copied sorted-set sliding-window-log script. Redis Cluster caveat: a limiter key and its Lua script must resolve to one slot, so multi-key scripts need hash tags (File 02 §10.1).

Language libraries worth knowing by name, because interviewers ask what you would actually use: Bucket4j (Java, token bucket, pluggable backends including Redis/Hazelcast), **Guava RateLimiter (Java, token bucket, single-JVM only, with a warm-up mode that ramps the permitted rate after idleness), resilience4j (Java, rate limiter + bulkhead + circuit breaker in one library — the modern replacement for Hystrix), golang.org/x/time/rate (Go, token bucket, standard-library-adjacent and excellent), Netflix concurrency-limits (adaptive, §3.8), and in Python limits or Django/Flask middlewares. The universal caveat:** all of these are per-process unless explicitly backed by a shared store — a per-process limiter on a 50-instance fleet enforces 50× your intended limit (§4.1).

8.5Comparison table#

8.6Decision rules#

8.7Anti-recommendations#

9Real-World Engineering Scenarios#

9.1Stripe — Fair, Tiered API Rate Limiting#

Stripe (publicly documented) protects its API with multiple limiter types layered together:

9.2Cloudflare — Edge Rate Limiting at Global Scale#

Cloudflare enforces limits at its edge across hundreds of PoPs (points of presence):

9.3AWS API Gateway — Token Bucket as a Managed Service#

AWS API Gateway exposes rate limiting directly as token bucket parameters:

10Interview Gotchas & Failure Modes#

10.1Classic Questions#

10.2Failure Modes & Mitigations#

11Whiteboard Cheat Sheet#

Client ──► [Edge/WAF limit] ──► [API Gateway/LB limit] ──► [Service mesh limit] ──► App
              (volumetric)          (per-key, main)           (svc-to-svc)      (business rules)

ALGORITHMS:
  Fixed Window ......... counter/window; simple; 2x boundary burst BUG
  Sliding Log .......... store every timestamp; perfect; memory-heavy
  Sliding Window Ctr ... cur+prev weighted; O(1); BEST DEFAULT
  Token Bucket ......... capacity B(burst) + refill r(rate); allows bursts; MOST POPULAR
  Leaky Bucket ......... FIFO drained at constant r; smooth output; no bursts; adds latency
                         (two forms: QUEUE = shaper, adds latency | METER = policer ≡ token bucket)
  GCRA ................. one timestamp (TAT); token bucket w/ minimal state; EXACT Retry-After
  Concurrency (semaphore) in-flight cap; bounds OCCUPANCY not arrival; MUST release in finally
  Adaptive (AIMD) ...... limit itself is variable; +1 healthy / ×0.5 congested; zero config

LIMIT TYPES (do not conflate):
  Rate        = requests per second   -> protects throughput   -> algorithms above
  Quota       = total per month/day   -> billing; must be DURABLE, never in an evicting cache
  Concurrency = in-flight at once     -> protects POOLS; the one people forget

WHY IT COLLAPSES:  wait ≈ service × ρ/(1−ρ).  95%->99% util = 5× slower.  Run at 60-70%.
                   Little's Law: L = λ × W  (1000/s × 0.2s = 200 in flight = 200 threads)

DISTRIBUTED (N nodes, global limit):
  Redis + atomic Lua (INCR/EXPIRE)  -> accurate, +0.5ms/req, make Redis HA
  Local buckets + async sync        -> fast/approximate, small overshoot
  Consistent-hash sticky by key     -> local limit, per-key correct
  Trade-off: ACCURACY vs LATENCY. Fail-open (avail) vs fail-closed (protection).

RESPONSE: 429 + Retry-After + X-RateLimit-{Limit,Remaining,Reset}. Client: backoff+jitter.

One-sentence summary for an interviewer:

"Rate limiting protects finite backends from unbounded demand by capping requests per key; use token bucket when you need average-rate-plus-burst, leaky bucket to shape a smooth output, and sliding-window counter as the accurate O(1) default; enforce a global limit across many nodes with an atomic Redis counter (accepting a latency cost) or local buckets with async sync (accepting small overshoot), and decide fail-open vs fail-closed deliberately."

End of File 03. Next → File 04: Database Sharding & Partitioning (horizontal scaling, shard keys, resharding, hot spots).