Rate Limiting & Throttling

Distributed Systems & Scalability

Chapter 7 · Rate Limiting & Throttling

Chapter 1 measured what happens when load exceeds what a system can handle. Rate limiting is the deliberate decision to reject some requests before that happens, protecting whatever sits downstream. Three algorithms answer "how do I count requests fairly" in genuinely different ways — and one classic implementation has a real, verified bug most people don't expect.

Token Bucket: Allows a Burst, Then Throttles

class TokenBucket:
    def __init__(self, capacity, refill_rate_per_sec):
        self.capacity = capacity; self.tokens = capacity  # starts FULL
        self.refill_rate = refill_rate_per_sec; self.last_refill = time.time()
    def allow_request(self):
        now = time.time()
        self.tokens = min(self.capacity, self.tokens + (now - self.last_refill) * self.refill_rate)
        self.last_refill = now
        if self.tokens >= 1:
            self.tokens -= 1; return True
        return False
    

Verified directly — exactly the bucket's own capacity gets through immediately, then it stops

Against a bucket with capacity 10 (refilling at 2/sec): 11 requests fired instantly all return the exact expected pattern — the first 10 all succeed, and the 11th is correctly rejected, since the bucket started full and every request drains one token. Waiting 0.6s (refilling roughly 1.2 tokens) makes the next request correctly succeed again.

Leaky Bucket: Smooths a Burst Into a Steady Output Rate

class LeakyBucket:
    def __init__(self, capacity): self.capacity = capacity; self.queue = []
    def add_request(self, request_id):
        if len(self.queue) >= self.capacity: return False
        self.queue.append(request_id); return True
    def leak(self):  # releases exactly one, at whatever pace this is called
        return self.queue.pop(0) if self.queue else None
    

Verified directly — the burst gets queued and rate-limited on the way OUT, not rejected outright

Submitting 20 requests instantly to a leaky bucket with capacity 15: 15 are accepted (queued), 5 are rejected outright (the bucket was already full). Calling leak() fifteen times released every accepted request in the exact order it was originally submitted — ['req-0', 'req-1', ..., 'req-14'], confirmed matching the submission order exactly. Downstream code calling leak() only ever sees one request at a time, however bursty the input was.

The genuine difference between the two

Token bucket lets an entire allowed burst reach the downstream system immediately — verified: all 10 of the first requests succeeded in one instant. Leaky bucket accepts a burst but releases it downstream at a controlled, steady pace — verified: 15 requests queued instantly, released one call to leak() at a time. Choose token bucket when occasional bursts are genuinely fine; choose leaky bucket when downstream specifically needs a smooth, predictable rate — for instance, exactly the kind of steady processing rate a queue consumer (Chapter 6) or a database write path (Chapter 4) benefits from.

Fixed Window vs. Sliding Window: A Real Boundary Bug

A fixed window counts requests within calendar-aligned buckets (e.g., minute 0–60, 60–120) and resets the count at each boundary. What happens to traffic that straddles that boundary?

Verified directly — a fixed window lets exactly double the intended rate through, right at the boundary

With a limit of 10 requests per 60 seconds: sending 10 requests between t=55 and t=59.5 (the tail end of one window) correctly allows all 10. Sending 10 more requests between t=60.5 and t=65 — barely 5.5 to 10.5 seconds later, but now in the "next" window — also allows all 10. Total: 20 requests genuinely allowed within a single 10-second span, against a limit meant to cap traffic at 10 per full 60 seconds.

Verified directly — a sliding window, given the identical traffic, correctly closes the gap

Running the exact same request timing against a sliding window (which counts requests within the trailing 60 seconds from right now, not a fixed calendar bucket): the first batch of 10 is allowed identically. The second batch — arriving only 5.5–10.5 seconds later, well within the same rolling 60-second window as the first batch — is correctly rejected: 0 of 10 allowed. Total allowed across the identical 10-second span: 10, matching the intended limit exactly.

Why this bug is easy to miss

A fixed window limiter passes every simple, isolated test — send 10 requests, the 11th within the same window correctly fails. The bug only appears at exactly the boundary, and only when traffic is deliberately (or accidentally) clustered around it — which is exactly the shape of traffic a real abuser, or a genuinely bursty legitimate client, produces.

Where This Connects

This chapter's finding	What it connects to
A verified, doubled-rate fixed-window bug	Chapter 1's own O(n) bottleneck finding — both are bugs invisible in a simple test, only surfacing under a specific, real traffic shape
Leaky bucket's own steady, one-at-a-time release rate	Chapter 6's own message queue — `leak()` is structurally the same operation as a queue consumer processing one message at a time
Rate limiting protecting a downstream system before it's overwhelmed	Chapter 9's own Fault Tolerance & Resilience Patterns — rate limiting is a preventative resilience pattern, applied before a failure rather than reacting to one

Hands-On Exercises

Exercise 1

Using this chapter's own TokenBucket, verify what happens with a capacity of 5 and a much higher refill rate (10/sec) — send 5 immediate requests, then wait 0.3s and send 5 more. Report how many of the second batch succeed and explain why using this chapter's own refill formula.

📄 View solution

Exercise 2

Using this chapter's own LeakyBucket, submit 10 requests, leak out 3, then submit 8 more before leaking the rest. Verify the bucket correctly rejects any requests that would exceed its own capacity at the moment they're submitted, and verify the final leak order is still fully FIFO across both submission batches.

📄 View solution

Exercise 3

Using this chapter's own fixed-window and sliding-window results, construct a traffic pattern that does not straddle a window boundary (e.g., all 20 requests sent between t=10 and t=20, well inside one window). Verify both limiters now agree on how many requests are allowed, and explain why the boundary bug specifically requires boundary-straddling traffic to appear at all.

📄 View solution

Chapter 7 Quick Reference

Token bucket: allows a burst up to capacity, then throttles — verified: exactly 10 of 11 immediate requests succeeded against a 10-token bucket
Leaky bucket: queues a burst, releases it downstream at a steady rate — verified: 15 of 20 burst requests accepted, released one at a time in exact FIFO order
Fixed window, verified buggy: let 20 requests through in a 10-second span against a 10-per-60-second limit, purely from boundary timing
Sliding window, verified correct: capped the identical traffic at exactly 10 in the same 10-second span
Next chapter: API Gateways & Service Discovery — where rate limiting and routing typically get enforced in a real microservices system