Chapter 17: Rate Limiting — Protecting Systems From Themselves and Others

Curriculum: Distributed Systems from First Principles Chapter: 17 of 24 Part: 7 — Edge Infrastructure Prerequisites: Chapter 1 (latency numbers), Chapter 9 (Redis, atomic operations), Chapter 16 (load balancers, where rate limiting lives) Estimated reading time: 75–85 minutes

Opening

Every system has a throughput ceiling — a maximum number of requests per second it can handle before latency spikes, errors accumulate, and the system degrades or crashes. You've spent the last several chapters building systems that scale horizontally: more database replicas, more shards, more application servers, more load balancer capacity. Horizontal scaling raises the ceiling. But no ceiling is infinite. And more importantly, a single badly-behaved client — one sending 10,000 requests per second in a retry storm, or one tenant in a multi-tenant SaaS monopolising shared database connections — can push the entire system past its ceiling, affecting every other user.

Rate limiting is the mechanism that enforces a ceiling per client, per user, per API key, or per tenant. It is simultaneously a protection mechanism (defend your system from overload), a fairness mechanism (ensure no single client monopolises shared resources), and a business mechanism (charge for API usage, enforce plan limits). The algorithms behind rate limiting are elegant and appear everywhere: token buckets govern TCP congestion control, leaky buckets control packet transmission rates in network switches, and sliding windows power GitHub's API throttling, Stripe's payment API limits, and AWS's service quotas. This chapter builds each algorithm from the physical operations it performs — what variables it stores, what arithmetic it computes, what the failure cases are — and then puts them together in a distributed rate limiting system that works across multiple servers.

Part 1: Why Rate Limiting — The Concrete Failure Modes It Prevents

Before the algorithms, the specific problems rate limiting solves:

Retry storms: A client receives a 503 Service Unavailable response. Its retry logic immediately retries. Fails again. Retries. If thousands of clients do this simultaneously, a brief overload (say, a database GC pause lasting 3 seconds) becomes a permanent overload — as the service starts recovering, it's hit with an amplified wave of retries. Rate limiting with backoff signals to clients to slow down, allowing the service to recover instead of being overwhelmed by its own clients.

Runaway jobs: A misconfigured batch job processes 10 million records and sends one API request per record. At 10,000 requests/second, it saturates the API within minutes. Every other client gets timeouts. Rate limiting caps the batch job's throughput and keeps the API usable for interactive clients.

Multi-tenant resource starvation: In a SaaS platform with 1,000 tenants sharing a database cluster, one tenant runs an expensive analytics query every minute, consuming 40% of database capacity. The other 999 tenants experience elevated latency. Per-tenant rate limiting on expensive operations protects shared resources.

DDoS amplification: An attacker sends requests to your search API with carefully crafted queries that each trigger expensive database full-table scans. Each attacker request costs your system 100× the cost of a normal request. Rate limiting by IP caps the damage any single source can do.

Cost control in multi-cloud environments: Every outbound API call to a third-party service (Stripe, Twilio, SendGrid) has a monetary cost. Rate limiting internal callers of these expensive operations prevents runaway bills.

Rate limiting doesn't solve all of these problems completely — a sophisticated DDoS from millions of IPs bypasses per-IP limits — but it eliminates the simple, common cases and degrades gracefully under the hard ones.

Part 2: Fixed Window Counter — The Simplest Algorithm and Its Critical Flaw

The fixed window counter is the most intuitive rate limiting algorithm. Divide time into fixed-size windows (e.g., 1-minute intervals). Count how many requests arrive in each window. If the count exceeds the limit, reject the request.

Limit: 100 requests per minute
Windows: [10:00–10:01], [10:01–10:02], ...

At 10:00:00: request arrives. Window count: 1.  Accept.
At 10:00:30: request arrives. Window count: 2.  Accept.
...
At 10:00:59: 100th request. Window count: 100. Accept.
At 10:00:59: 101st request. Window count: 101. Reject (429).

At 10:01:00: window resets. Window count: 0.
At 10:01:00: request arrives. Window count: 1. Accept.

Implementation in Redis — the entire state for one client is a single Redis key:

-- For client "user:42", window "10:00"
INCR rate_limit:user:42:10:00          -- returns new count
EXPIRE rate_limit:user:42:10:00 60     -- key expires after 60s
-- if count > 100: reject with 429

Simple, fast, low memory (one integer per client per window). But it has a critical flaw: the boundary burst problem.

Consider a client that sends 100 requests at 10:00:59 (the last second of the first window) and 100 requests at 10:01:00 (the first second of the second window). Both are within their respective window limits. But within the 2-second span from 10:00:59 to 10:01:01, the client sent 200 requests — double the intended limit of 100/minute.

BOUNDARY BURST:

10:00:59: [request 1 ... request 100] → all accepted (window 1 count: 100)
10:01:00: [request 101 ... request 200] → all accepted (window 2 count: 100)

In 1 second: 200 requests. 2× the intended rate. System sees a traffic spike.

For many systems, this burst is acceptable — the average rate is within limits. For systems with tight resource constraints (database connection pools, external API limits), this burst causes exactly the overload rate limiting was supposed to prevent.

Part 3: Sliding Window Log — Accurate but Memory-Hungry

The sliding window log eliminates the boundary burst by tracking the exact timestamp of every request in a sorted list.

Algorithm: maintain a log of request timestamps for each client. When a new request arrives, remove all timestamps older than the window size (1 minute ago), then count the remaining timestamps. If the count < limit, add the new timestamp and accept. If count ≥ limit, reject.

Limit: 5 requests per minute
Current time: 10:02:30

Timestamp log for user:42:
  [10:01:31, 10:01:45, 10:02:00, 10:02:15, 10:02:25]

New request arrives at 10:02:30:
  1. Remove timestamps older than 10:01:30 (60s ago): none removed
  2. Count remaining: 5
  3. 5 >= limit (5): REJECT

New request arrives at 10:02:32:
  1. Remove timestamps older than 10:01:32: removes 10:01:31
  2. Count remaining: 4
  3. 4 < limit (5): ACCEPT. Add 10:02:32 to log.
  Log: [10:01:45, 10:02:00, 10:02:15, 10:02:25, 10:02:32]

This is perfectly accurate — no boundary bursts, the rate is truly 5 per minute regardless of when in the minute the requests arrive. Redis Sorted Sets implement this naturally: ZADD adds a timestamp with the timestamp as the score, ZREMRANGEBYSCORE removes old entries, ZCARD counts remaining.

The problem: memory usage. For each client, the log stores one entry per allowed request per window. With 100,000 API clients each allowed 1,000 requests/minute, the log holds up to 100,000 × 1,000 = 100 million entries. At ~50 bytes per entry (timestamp + overhead), that's 5 GB just for rate limit state. At high request rates, the log grows large, and the sorted set operations (ZREMRANGEBYSCORE, ZCARD) become O(N) where N is the log size.

Sliding window log is appropriate for: low-volume, high-precision rate limiting where accuracy matters more than memory (e.g., limiting expensive operations to 10/hour per user, where the log is at most 10 entries). Inappropriate for: high-volume APIs with large per-user limits.

Part 4: Sliding Window Counter — The Practical Hybrid

The sliding window counter approximates the sliding window log's accuracy using only two integers per client — the count in the current window and the count in the previous window.

The intuition: if we're currently 30% through the current window, then 70% of the previous window's requests are "still within the last minute." We approximate the current rate as: rate = previous_window_count × (1 - elapsed_fraction) + current_window_count.

Limit: 100 requests per minute
Window size: 60 seconds

State:
  previous_window_count = 84  (requests in 10:00–10:01)
  current_window_count  = 36  (requests in 10:01 so far)
  current_time = 10:01:45     (45s into current window = 75% elapsed)

Approximate count in sliding window:
  = previous_window_count × (1 - 0.75) + current_window_count
  = 84 × 0.25 + 36
  = 21 + 36
  = 57

57 < 100 → ACCEPT

This approximation has at most ~0.003% error compared to the perfect sliding window log (proven mathematically), which is negligible for practical rate limiting. And it uses only two integers per client, regardless of the request rate.

Redis implementation — three operations, all O(1):

-- At time T, for a 60-second window:
current_window  = floor(T / 60)
elapsed_seconds = T mod 60
elapsed_fraction = elapsed_seconds / 60.0

prev_count = GET rate:user:42:{current_window - 1}  -- previous window count
curr_count = INCR rate:user:42:{current_window}      -- increment current window

approx_count = prev_count × (1 - elapsed_fraction) + curr_count

IF approx_count > limit:
    DECR rate:user:42:{current_window}  -- undo the increment
    REJECT 429
ELSE:
    EXPIRE rate:user:42:{current_window} 120  -- retain for 2 windows
    ACCEPT

The sliding window counter is the practical choice for most production API rate limiting: near-perfect accuracy, O(1) time and O(1) space per client. Cloudflare uses a variant of this algorithm at global scale.

Part 5: Token Bucket — Allowing Bursts Within Limits

The algorithms so far enforce a strict rate — exactly N requests per window. Many real systems need to allow bursting: a client that was quiet for the past 5 minutes should be able to send a brief burst of requests, as long as its sustained average rate stays within limits.

The token bucket algorithm models this precisely. Imagine a bucket that holds tokens. Tokens refill at a constant rate R (tokens per second). Each request consumes one token. If there are tokens available, the request is accepted. If the bucket is empty, the request is rejected (or queued).

Token bucket state:
  capacity = 100 tokens     (max burst size)
  refill_rate = 10/second   (sustained allowed rate)
  tokens = 100              (current tokens available)
  last_refill = T₀          (timestamp of last refill calculation)

Request arrives at T₁ (5 seconds after T₀):
  1. Refill: tokens += (T₁ - T₀) × rate = 5 × 10 = 50 tokens
             tokens = min(tokens, capacity) = min(150, 100) = 100 (capped at capacity)
  2. Request consumes 1 token: tokens = 99
  3. tokens > 0: ACCEPT

Burst scenario:
  100 requests arrive simultaneously:
    tokens = 100
    100 requests each consume 1 token: tokens = 0
    All 100 accepted (the burst is within bucket capacity)

  101st request immediately after:
    tokens = 0: REJECT
    Wait 0.1 seconds: tokens refill to 1 → next request accepted

The token bucket captures the real-world intuition of "you have credit from being quiet." A client that was idle for 10 seconds accumulates 100 tokens (at 10/second), allowing a burst of 100 requests. A client constantly sending at 10/second never accumulates tokens and gets exactly 10 requests/second — the sustained rate limit.

Two parameters control the bucket's behaviour independently:

• Bucket capacity (burst size): the maximum instantaneous request rate. Set based on what your system can handle in a short burst.
• Refill rate (sustained rate): the long-term average rate. Set based on your business/cost limits.

This separation is powerful. Stripe's API uses token buckets: each API key has a sustained rate (e.g., 100 requests/second) and a burst capacity (e.g., 200 tokens), allowing clients to handle bursty workloads without always hitting rate limits, while ensuring no client can sustain more than 100 requests/second indefinitely.

Implementation in Redis

Token bucket state is two values: current tokens and last refill timestamp. These must be updated atomically — a non-atomic read-modify-write would allow two concurrent requests to both see tokens = 1, both accept, and drain to -1 (over-limit).

The correct implementation uses Redis Lua scripts (executed atomically on the Redis server) or Redis's SET with conditional logic:

-- Lua script (runs atomically in Redis)
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])  -- tokens per second
local now = tonumber(ARGV[3])          -- current timestamp (seconds)
local requested = tonumber(ARGV[4])    -- tokens needed (usually 1)

local data = redis.call('HMGET', key, 'tokens', 'last_refill')
local tokens = tonumber(data[1]) or capacity
local last_refill = tonumber(data[2]) or now

-- Refill tokens based on elapsed time
local elapsed = now - last_refill
local new_tokens = math.min(capacity, tokens + elapsed * refill_rate)

if new_tokens >= requested then
    -- Accept: consume tokens
    redis.call('HMSET', key, 
        'tokens', new_tokens - requested,
        'last_refill', now)
    redis.call('EXPIRE', key, math.ceil(capacity / refill_rate) + 1)
    return 1  -- accepted
else
    -- Reject: update refill timestamp but don't consume
    redis.call('HMSET', key, 'tokens', new_tokens, 'last_refill', now)
    return 0  -- rejected
end

The Lua script runs atomically — Redis executes the entire script without interruption. No race conditions. No over-counting.

One production detail: now is passed in by the application server. With many app servers, their clocks disagree by milliseconds to seconds, and a server whose clock runs behind computes a negative elapsed, which removes tokens. Either clamp it (elapsed = math.max(0, now - last_refill)) or read the time inside the script from Redis itself (redis.call('TIME')), so every server uses the same clock. The reject branch should also set the EXPIRE, so an idle, rejected client's key doesn't linger forever. (HMSET still works but is deprecated; modern Redis uses HSET with multiple fields.)

You've now seen three algorithms on paper. Feed them the same traffic and watch where they disagree. Predict first, then run each tab.

Part 6: Leaky Bucket — Smoothing Traffic to a Constant Rate

The leaky bucket algorithm is the inverse of token bucket: instead of clients accumulating credit, requests accumulate in a queue that drains at a constant rate.

The leaky bucket enforces a perfectly smooth output rate regardless of input burstiness. Even if 100 requests arrive simultaneously, they're processed at 10/second — the 100th request is processed 10 seconds after the first. This smoothing is valuable when: your downstream system (a database, an external API) cannot handle bursts — it needs a constant, predictable rate.

The token bucket allows instantaneous bursts (all 100 tokens consumed in one millisecond). The leaky bucket spreads those 100 requests over 10 seconds, smoothing them into a steady stream. For protecting systems that are sensitive to instantaneous load spikes (like a rate-limited third-party payment API), leaky bucket is superior.

Comparison:

100 requests arrive at t=0:
  Token bucket: all 100 processed at t=0 (burst), next request at t=0.1
  Leaky bucket: request #1 at t=0, #2 at t=0.1, ..., #100 at t=9.9

At t=5:
  Token bucket: 50 new tokens have refilled
  Leaky bucket: queue drained to ~50 requests processed, 50 still waiting

The practical difference: token bucket is better for clients (they get fast responses during bursts). Leaky bucket is better for downstream systems (they see smooth, predictable load). Many production systems use token bucket at the API gateway (client-facing) and leaky bucket internally (protecting downstream dependencies).

Part 7: Distributed Rate Limiting — The Hard Problem

A single-server rate limiter is straightforward — one process, one counter, no coordination. The hard problem is distributed rate limiting: your API gateway runs on 10 load balancer instances, each independently receiving requests. A client's requests are distributed across all 10 instances. How do you enforce a global limit?

Problem: local counters don't coordinate

If each load balancer instance maintains its own local counter, a client allowed 100 requests/minute can send 100 requests to each of the 10 instances — 1,000 total. The global limit is violated 10×.

Total accepted: 1,000 requests. Limit: 100. Violation: 10×.

Solution 1: Centralised Redis counter

All instances share one Redis cluster. Every request atomically increments a shared counter. The atomic Redis INCR command returns the new count; if it exceeds the limit, reject.

Every rate limit check (any instance):
  count = REDIS INCR rate:user:42:current_window
  REDIS EXPIRE rate:user:42:current_window 60  (if first increment)
  if count > 100: reject
  else: accept

This works correctly — one global counter, no over-counting. The cost: every request requires one Redis round trip (0.5–1ms). At 1 million requests/second, that's 1 million Redis operations/second — achievable with a Redis cluster but not free.

Atomic INCR is one operation — no race conditions on the count. The EXPIRE is the weak spot: it is a separate command, and if it is sent only "if first increment," a crash or network error between INCR and EXPIRE leaves a key with no TTL at all. That key never resets, and the user stays rate-limited forever. Two correct ways to close the gap:

• Run INCR and EXPIRE together in one Lua script (or a MULTI/EXEC transaction), so they succeed or fail as a unit.
• Create the key with its TTL first, then increment: SET key 0 EX 60 NX (does nothing if the key already exists), then INCR key. INCR keeps the existing TTL, so the counter can never exist without an expiry.

Solution 2: Lua script for token bucket

Token bucket requires read-modify-write (read current tokens, compute refill, write new tokens). This must be atomic. Lua scripts on Redis execute atomically — the script from Part 5 is the correct implementation.

Solution 3: Local approximation with periodic sync

For very high throughput where even Redis round-trips are too slow: each instance maintains a local counter and periodically (every 100ms) syncs with Redis.

Each instance:
  local_count = 0
  global_count_estimate (synced every 100ms from Redis)

On request:
  if local_count + global_count_estimate > limit: reject
  else: local_count++

Every 100ms:
  INCRBY redis_counter local_count  -- add local count to Redis
  global_count_estimate = GET redis_counter  -- read new global total
  local_count = 0  -- reset local counter

This approach allows up to limit × 100ms / 1000ms over-counting per instance during the sync window. For a limit of 1,000/second with 10 instances syncing every 100ms, each instance might over-count by 100 × (100ms/1000ms) = 10 requests. The global over-count is at most 100 requests — 10% above limit. Acceptable for many use cases, with the benefit of requiring only one Redis round trip per 100ms per instance instead of one per request.

Solution 4: Consistent hash routing to dedicated rate limiter

Use consistent hashing (Chapter 8) to route all requests for a given client to the same rate limiter instance. That instance maintains local state for its assigned clients — no cross-instance coordination needed.

Each instance manages its assigned clients locally. No Redis coordination for the common case.

The downside: if Rate Limiter Instance 2 goes down, Client A's requests need to be re-routed. During the failover window, Client A either gets no rate limiting (unsafe) or is rate-limited to 0 (unavailable). This is the same trade-off as any stateful system failover. A warm standby per instance or consistent hashing with virtual nodes (Chapter 8) mitigates this.

Part 8: Rate Limiting Granularity — What to Limit

The identifier used for rate limiting determines what kind of fairness and protection you achieve.

Per IP address: The most common for unauthenticated endpoints and DDoS protection. Simple — no authentication required. Flawed: shared IPs (NAT, IPv6 prefixes) limit an entire office or ISP. Easy to bypass with multiple IPs.

Per user / account ID: Correct for authenticated APIs. Fair across users regardless of IP. Requires authentication before rate limiting check — adds latency to the check. All of a user's API keys share the same limit.

Per API key: Allows different limits for different keys owned by the same user. Enables: free tier (100 req/day), paid tier (10,000 req/day), enterprise (unlimited). Easy to revoke: invalidating an API key stops all requests with that key.

Per tenant (multi-tenant SaaS): All users within a tenant share a limit. Prevents one tenant's usage from affecting others. The limit is configurable per tenant — enterprise customers get higher limits. This is the correct granularity for protecting shared infrastructure.

Per endpoint: Different endpoints have different costs. A GET /users/{id} (fast, cached) can be allowed at 10,000/minute. A POST /reports/generate (expensive, triggers ML model) can be limited to 10/minute. Per-endpoint limits prevent expensive operations from monopolising the system.

Compound limits: Production systems often combine multiple granularities: an API key is limited to 1,000 requests/minute (sustained), with a burst capacity of 2,000 tokens. The tenant owning that key is limited to 10,000 requests/minute total across all their API keys. The endpoint /reports/generate is additionally limited to 50/hour per API key. Multiple token buckets, each enforcing a different constraint.

Part 9: Responding to Rate Limited Clients — The Protocol

When a request is rejected, the response must give the client enough information to behave correctly. The standard is HTTP 429 Too Many Requests, with specific headers.

HTTP/1.1 429 Too Many Requests
Content-Type: application/json
Retry-After: 30
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1700000060

{
  "error": "rate_limit_exceeded",
  "message": "You have exceeded the rate limit of 100 requests/minute.",
  "retry_after_seconds": 30
}

Retry-After: How many seconds the client should wait before retrying. Without this, clients retry immediately — recreating the retry storm. Setting Retry-After to the time until the next window reset (or until enough tokens refill) gives clients precise guidance.

X-RateLimit-Remaining: How many requests the client can still send in the current window. Include this on every successful response, not just 429s — clients use it to slow down proactively before hitting the limit. GitHub includes these headers on every API response.

X-RateLimit-Reset: The Unix timestamp when the rate limit resets. Clients can compute exactly when to retry.

X-RateLimit-Limit: The total limit for the current period. Helps clients understand their quota.

Clients that receive 429 should implement exponential backoff with jitter: wait min(cap, base × 2^attempt) + random_jitter. The jitter prevents a synchronized retry storm (all clients waking up at the same time after Retry-After expires). Without jitter, every rate-limited client retries at the same second — creating the same spike they were trying to avoid.

Exponential backoff with jitter:
  attempt 1: wait = min(60, 1 × 2¹) + random(0, 1) = 2 + 0.7 = 2.7s
  attempt 2: wait = min(60, 1 × 2²) + random(0, 1) = 4 + 0.3 = 4.3s
  attempt 3: wait = min(60, 1 × 2³) + random(0, 1) = 8 + 0.9 = 8.9s
  attempt 4: wait = min(60, 1 × 2⁴) + random(0, 1) = 16 + 0.2 = 16.2s
  attempt 5: wait = min(60, 1 × 2⁵) + random(0, 1) = 32 + 0.5 = 32.5s
  attempt 6: wait = min(60, 1 × 2⁶) + random(0, 1) = 60 + 0.8 = 60.8s (capped)

Part 10: Where Rate Limiting Lives in the Architecture

Rate limiting can be implemented at multiple layers. The correct layer depends on what's being protected and at what granularity.

API Gateway / Load Balancer (Chapter 16): Coarse-grained rate limiting before requests reach application servers. Protects the entire backend from overload. Operates on IP or API key. Fast (Redis check adds ~1ms). AWS API Gateway, Kong, Nginx Plus, and Envoy all support rate limiting at this layer. This is the first line of defence against DDoS and retry storms.

Application layer: Fine-grained rate limiting inside the application. Can access authenticated user identity, tenant ID, endpoint cost. Checks business-level limits: "this tenant has a paid plan allowing 10,000 API calls/day." Slower (must run after authentication) but more expressive.

Service layer: Rate limiting outbound calls from your application to third-party services. Your application is the "client" — you rate-limit yourself. When calling Stripe's API (100 requests/second limit), your service maintains a token bucket for outgoing Stripe calls and queues or rejects internal requests that would exceed Stripe's limit. This prevents your application from accidentally overloading Stripe and having its API key suspended.

Database connection pool: A form of implicit rate limiting — the connection pool has a maximum size (say, 100 connections). The 101st concurrent database operation waits in the pool queue until a connection is available. Pool timeouts reject requests that wait too long. This is less a rate limit than a concurrency limit, but it protects the database from connection exhaustion.

Cell-level rate limiting (per-datacenter): In a multi-datacenter system, rate limits are applied per cell (datacenter). A client's 1,000 requests/minute limit applies within each cell independently. This avoids cross-datacenter coordination for rate limit checks — each cell manages its own Redis cluster and its own rate limit state. The downside: a client can exceed the global limit by sending requests to multiple cells. Acceptable for most systems; global rate limiting would require cross-datacenter coordination, adding 50–200ms of latency.

Part 11: Real-World Rate Limiting in Production Systems

Stripe

Stripe's API uses token bucket per API key. Rate limits are documented per API endpoint (the create payment intent endpoint has a different limit than the list customers endpoint). Stripe returns X-RateLimit-Limit, X-RateLimit-Remaining, and Retry-After headers. Critically, Stripe applies rate limits at the account level, not per API key — all keys for an account share the bucket. This prevents a single account from bypassing limits by creating many API keys.

GitHub API

GitHub uses a sliding window counter (5,000 requests/hour for authenticated users, 60/hour for unauthenticated). GitHub includes rate limit headers on every response — even successful ones — so clients can track their remaining quota. The search API has a stricter separate limit (30 requests/minute) because search is computationally expensive. GitHub also uses a "secondary rate limit" (formerly "abuse rate limit") for concurrent requests — if a single client opens too many concurrent connections, it's temporarily blocked.

AWS API Throttling

AWS services use token bucket at the service level. Each AWS account has per-service, per-region token buckets. For example, EC2 DescribeInstances might allow 100 requests/second burst and 20 requests/second sustained. When throttled, AWS returns HTTP 400 with error code ThrottlingException (not 429 — AWS precedes the HTTP 429 standard). AWS SDKs implement exponential backoff automatically for throttling responses.

Cloudflare Rate Limiting

Cloudflare's rate limiting operates at the edge — at their anycast points of presence globally. Rate limit rules are evaluated before the request reaches the origin server. Cloudflare uses a sliding window counter synced across their global network using their distributed KV store. Because Cloudflare has dozens of PoPs, their distributed rate limiting is a production example of Solution 3 (local approximation with periodic sync) at internet scale.

Part 12: Graceful Degradation vs Hard Rejection

Not all rate limiting must result in hard rejection (429). Depending on the use case, a better response might be to degrade gracefully.

Queue and delay: Instead of rejecting the request, enqueue it. The client blocks (or gets an async job ID) and the request is processed when capacity is available. Appropriate for expensive background operations (report generation, bulk exports) where the client can wait. Inappropriate for interactive APIs where clients expect sub-second responses.

Serve cached/stale data: If the expensive operation is a read, return the last known good response from cache when rate limited. The client gets slightly stale data rather than an error. Appropriate for dashboards, analytics reads, recommendation systems where approximate data is acceptable.

Serve degraded response: Return a simplified response instead of a full one. Instead of "here are 50 personalised recommendations," return "here are 10 generic trending items." The client gets a response (not an error), and the expensive ML model isn't invoked.

Shadow limit: Log rate limit violations without actually rejecting requests. Use this to calibrate limits before enforcing them — observe what limits would reject how many requests, then enforce only when you're confident the limits are correct. Prevents accidentally blocking legitimate traffic when first deploying rate limiting.

The choice between hard rejection and graceful degradation is a product decision: does your SLA promise best-effort or guaranteed service? For paid API customers, hard rejection (with clear error messages and retry guidance) is often more honest and actionable than silently serving stale data. For internal services or non-critical endpoints, graceful degradation provides better user experience.

Vocabulary Map

Practice Problems

Problem 1 — Failure Analysis

A fixed window counter allows 1,000 requests/minute per API key. An attacker knows the window boundaries and sends exactly 1,000 requests at 11:59:59 and exactly 1,000 requests at 12:00:00.

Calculate: how many total requests are accepted in the 2-second span from 11:59:59 to 12:00:01? What is the effective requests-per-second rate during this window? If your API server can handle 100 requests/second before latency degrades, what is the impact?

Now redesign using a sliding window counter with 60-second windows. At 12:00:30 (30 seconds into the new window), the attacker has sent 500 requests in the current window. The previous window had 1,000 requests. What approximate count does the sliding window counter report? Is the next request accepted or rejected? Show the arithmetic.

Problem 2 — Design from Scratch

Design a complete rate limiting system for a public REST API serving 10,000 API customers. Plans: Free (100 requests/day), Pro (10,000 requests/day, 100/minute burst), Enterprise (1,000,000 requests/day, 1,000/minute burst, dedicated rate limit namespace). The API runs on 20 load balancer instances. Requests arrive at 500,000/minute peak.

Specify: which algorithm for each plan tier and why, what Redis data structures store the state, how you handle the distributed rate limiting across 20 instances (which solution from Part 7 and why), how you handle Redis downtime (fail open vs fail closed and the implications of each), what headers you return on successful requests, what your 429 response body contains, and how Enterprise customers get isolated rate limit state that doesn't share counters with other tenants.

Problem 3 — Synthesis

Connect rate limiting to Chapter 9's Redis and Chapter 16's load balancing.

Your API gateway (10 instances) implements token bucket rate limiting using a shared Redis cluster for state. Bucket capacity: 100 tokens. Refill rate: 10 tokens/second. A Lua script atomically reads and updates token state for each request.

At peak traffic (500,000 requests/second across all clients), each rate limit check is one Redis Lua script execution. Calculate: how many Redis operations per second does this require? A Redis cluster with 6 shards (using consistent hashing — Chapter 8) distributes rate limit keys across shards. How many operations per shard? From Chapter 1's latency numbers, how much latency does each Redis round trip add to request processing?

Now Redis Cluster experiences a network partition (Chapter 6): 3 shards are unreachable. The 3 unreachable shards contain rate limit state for ~50% of your API keys. Two approaches: (a) fail open (skip rate limiting for keys on unreachable shards), (b) fail closed (reject all requests for keys on unreachable shards). For each approach: what is the business impact, what is the security impact, and which would you choose for a payment API vs a weather data API? Connect this to Chapter 6's safety vs liveness trade-off.

Problem 4 — Go Deeper

The token bucket algorithm refills tokens based on elapsed time since the last request. This means the refill calculation happens at request time — "lazy refill." An alternative is "eager refill" — a background process that increments tokens on a schedule.

From first principles: what are the computational trade-offs between lazy and eager refill? For a system with 1 million active API keys, what is the Redis write throughput required for eager refill at 1-second granularity? For lazy refill?

Now consider clock skew: your 20 API gateway instances each have slightly different system clocks (±10ms drift). In lazy refill, the elapsed time calculation now - last_refill depends on now, which differs across instances. Trace a specific scenario: Instance A processes a request at T=1000ms (real time), sets last_refill=1000. Instance B processes the next request at T=1005ms (real time) but its clock reads T=998ms (2ms behind). What token count does Instance B calculate? Is this a correctness issue or just imprecision? How large must the clock skew be before it causes a measurable rate limit accuracy problem? What is Redis's role in providing a consistent time reference?

Problem 5 — Connect to Previous Chapters

Connect rate limiting to Chapter 13's distributed transactions and Chapter 14's message queue patterns.

Part A: Your e-commerce checkout service calls the Stripe payment API, which has a rate limit of 100 requests/second per API key. Your checkout service runs on 50 instances, each capable of processing 10 checkouts/second = 500 checkouts/second total. Without outbound rate limiting, all 50 instances together can send 500 Stripe API calls/second — 5× Stripe's limit.

Design an outbound token bucket rate limiter (your service rate-limiting itself) using the distributed approaches from Part 7. Which approach minimises latency impact? What happens to checkout requests when the Stripe rate limit is reached — reject (checkout fails) or queue (checkout waits)? Connect to Chapter 14's leaky bucket: why is a leaky bucket more appropriate than a token bucket for smoothing outbound calls to Stripe, even though token bucket is more appropriate for inbound client-facing API limiting?

Part B: A Chapter 14 message queue consumer processes messages at a maximum rate of 1,000/second (limited by a downstream database write capacity). The queue receives bursts of 10,000 messages/second during peak hours. The queue itself buffers the burst (Chapter 14's backpressure). The consumer's processing loop is effectively a leaky bucket: it drains the queue at 1,000/second regardless of how fast messages arrive.

Trace the queue depth over 60 seconds: messages arrive at 10,000/second for the first 30 seconds, then drop to 500/second. What is the maximum queue depth? When does the queue fully drain? What is the maximum end-to-end message latency (time from message produced to message processed) at the peak of the burst? How is this mathematically equivalent to a leaky bucket with capacity=queue_size and drain_rate=1,000/second?

What's Coming Next

Rate limiting and load balancing together form the protective edge of your system: load balancers distribute traffic fairly across available capacity, rate limiters enforce per-client ceilings on how much of that capacity any one client can consume. Chapter 18 turns inward — to observability. You've built a complex distributed system with dozens of components, each making thousands of decisions per second. When something goes wrong — and it will — you need to know what happened, where, and why. Observability is the practice of making the internal state of a distributed system externally knowable: through metrics (what is the system doing right now?), tracing (how did this specific request flow through the system?), and logging (what exactly happened and when?). After Chapter 18, you'll know what to instrument, how to interpret what you see, and — critically — how to reason about system health before an incident, not just during one.

Chapter 17 complete. Problem 1 (boundary burst arithmetic) is the fastest way to internalise why fixed windows fail — do the math in 5 minutes and you'll never recommend fixed window counters for production again. Problem 2 (design a multi-tier rate limiting system) is the complete system design exercise — it requires choosing algorithms per plan tier, selecting Redis data structures, handling distributed state, and designing the API contract. This appears in API gateway design interviews at every major tech company. Problem 5A (outbound leaky bucket to Stripe) is the most practically important for SaaS engineers — accidentally exceeding a payment provider's rate limit during a traffic spike is a real, painful production incident.