System Design Masterclass · Module 14 / Week 3

Rate Limiting & Load Shedding

Saying no is a feature. The algorithms and their burst semantics, distributed limiter design on Redis, and load shedding by priority — the art of dropping the right 10% to save the other 90%.

~2.5h study~1.5h exercise1 interactive simFast track ~70 min

Fast track — shipped a limiter before?

Compresses to ~70 min. Algorithm mechanics collapse to burst semantics; distributed design, keying strategy, and priority shedding stay mandatory.

  1. §01 takeaway + sim once · 10 min
  2. §02 distributed limiter design, in full · 15 min · MANDATORY
  3. §03 keying, in full · 10 min · MANDATORY
  4. §04 load shedding, in full · 20 min · MANDATORY
  5. Exercise step 2 · 15 min
STEP 01

Algorithms = burst policies

SKIM
Fast-track takeawayThe algorithms differ almost only in how they treat bursts: token bucket — rate r with burst capacity b: bursts up to b sail through, sustained rate capped (the right default; burst tolerance is usually what you want) · leaky bucket — smooths output to constant rate: shaping, not just limiting (pace outbound calls to a vendor with strict RPS) · fixed window — cheap, but 2× boundary leak (100 at 11:59:59 + 100 at 12:00:01) · sliding window counter — weighted two-window blend: boundary fixed, cheap, the practical accurate choice. Play one round below and move on.
Burst semantics · limit 10/s, burst of 15 arrives

Bucket / window state

10 / 10

Verdicts for the 15-burst

A client that was quiet sends 15 requests in one instant. Each algorithm answers differently — the answer IS the algorithm.
STEP 02

Distributed limiting on Redis

MANDATORY
STEP 03

What to key on

MANDATORY
STEP 04

Load shedding: dropping the right traffic

MANDATORY

Rate limiting enforces pre-agreed quotas; shedding is the emergency brake when the system is saturating regardless of quotas. The design questions are trigger, victim, and response:

Staff expectationOwning the priority taxonomy as a platform artifact — every endpoint classified, header propagated, shed order tested in game-days — and the overload math: at 130% of capacity, shedding 30% of background traffic keeps 100% of playback alive; shedding nothing gives every request a ~timeout. Being able to show that arithmetic is how the "we never drop requests" argument gets won.
STEP 05

Code: the atomic bucket

SKIM
Fast-track takeawayThe Lua below is the whole §02 argument in 12 lines: refill-check-consume atomically, O(1), returns remaining+retry-after. Skim it so "distributed rate limiter" is a script in your head, not a product to buy.
-- KEYS[1]=bucket key · ARGV: rate, burst, now_ms, cost
local tokens = tonumber(redis.call('HGET', KEYS[1], 't') or ARGV[2])
local ts     = tonumber(redis.call('HGET', KEYS[1], 'ts') or ARGV[3])
local refill = (ARGV[3] - ts) / 1000 * ARGV[1]
tokens = math.min(ARGV[2], tokens + refill)          -- refill, capped at burst
local ok = tokens >= tonumber(ARGV[4])
if ok then tokens = tokens - ARGV[4] end
redis.call('HSET', KEYS[1], 't', tokens, 'ts', ARGV[3])
redis.call('PEXPIRE', KEYS[1], 60000)               -- idle buckets evaporate
return {ok and 1 or 0, tokens}

Call via RedisTemplate.execute(RedisScript); wrap with the local pre-limiter and the fail-open fallback from §02.

STEP 06

Exercise

MANDATORY

Fast trackStep 2 (~30 min): the goodput-collapse demo. Once you've seen goodput hit zero without shedding, you'll never skip admission control again.

1
Build the limiter. The §05 Lua behind a Spring filter, keyed per-user + per-endpoint with weights. Prove atomicity: 10 concurrent pods (threads) hammering one key never exceed the budget; then race the naive get-then-incr version and count the overshoot.
2
Goodput collapse. Service with capacity ~200 RPS (sleep-calibrated), client timeout 1 s. Drive 400 RPS: graph throughput vs goodput (responses arriving under the client timeout) — watch goodput collapse. Add concurrency-based admission control (semaphore ≈ capacity × latency): goodput returns to ~200 while excess gets fast 429s. Two graphs, one lesson.
3
Priority shed. Tag requests critical/interactive/background; overload again and shed lowest-first at admission. Show critical goodput at 100% while background absorbs the loss.
4
Paper. The priority taxonomy for your real platform: every public endpoint classified into the four tiers, with the header-propagation design and the one contested classification (there's always one — usually search) argued in writing.

Self-check

Why does fixed-window allow 2× the limit, and when is that fine?
Counters reset at boundaries: a full budget spent in the last instant of window N plus a full budget in the first instant of N+1 = 2× in ~zero time. Fine when the limit is a coarse abuse guard with big margins; not fine when the number protects real capacity — then sliding-window or token bucket.
Your Redis limiter adds 8 ms p99 at the gateway. Diagnose paths?
Expected cost is ~0.3–1 ms, so: cross-AZ Redis placement (Module 02: +1–2 ms), non-pipelined multiple limiter checks per request (batch the keys in one script call), a hot key on one cluster shard (Module 05 — hash-tag or split), or connection-pool exhaustion on the Redis client (bulkhead it, Module 13).
Why must the limiter fail open when rate limiting exists to protect the backend?
The limiter's own dependency (Redis) failing is not evidence of traffic overload — failing closed makes the limiter a single point of failure that converts a Redis blip into 100% rejection. Fail open to a local approximate limiter: protection degrades from exact-global to approximate-local, which still catches gross abuse, while availability is preserved. Alert loudly; exact enforcement resumes with Redis.
Shedding by CPU vs by concurrency/queue depth — why does the latter win?
CPU is a lagging, workload-relative proxy: IO-bound saturation shows low CPU with exploding queues; a noisy neighbor shows high CPU with fine latency. Queue depth / in-flight count measures the thing users feel (waiting) directly and responds within one request-time. Adaptive concurrency limits formalize it: find the knee where more in-flight stops adding goodput, and admit only to there.