Leaky Bucket vs Token Bucket vs Sliding Window Log

If you have ever been asked "how would you design a rate limiter" in a system design interview, you already know the panic that follows. There are at least three algorithms that come up almost every time, and interviewers expect you to know the trade-offs, not just the definitions.

This article solves exactly one problem: helping you understand the differences between Leaky Bucket, Token Bucket, and Sliding Window Log rate limiting algorithms so you can pick the right one, explain the trade-offs, and answer interview or certification questions confidently.

This guide is for backend engineers, SRE and platform engineering candidates, and anyone preparing for a system design interview at a company that expects API throttling knowledge (which is most of them today).

Quick Answer (30 Second Read)

• Token Bucket: allows short bursts of traffic while enforcing an average rate. Most widely used in production (AWS API Gateway, Stripe API).
• Leaky Bucket: smooths traffic into a constant outflow rate, no bursts allowed. Common in network traffic shaping.
• Sliding Window Log: tracks exact request timestamps for precise rate limiting, but is memory-heavy at scale.
• Common mistake: assuming all three algorithms behave identically under burst traffic. They do not.
• Interview tip: interviewers care more about your trade-off reasoning (memory vs accuracy vs burst tolerance) than the algorithm name.

Core Concepts

Rate limiting exists to protect a system from being overwhelmed by too many requests in a given time window, whether from abusive clients, bugs in a retry loop, or legitimate traffic spikes. Every rate limiting algorithm answers the same question differently: should this request be allowed right now?

```

The three algorithms differ in how they track "how much capacity is left" and how they treat bursts of traffic versus sustained load.

Deep Explanation

What is Leaky Bucket?

Leaky Bucket models requests like water poured into a bucket with a small hole at the bottom. Requests enter a fixed-size queue and are processed ("leaked") at a constant rate. If the bucket is full, new requests are dropped.

• Output rate is always constant, regardless of input bursts.
• Implemented using a FIFO queue plus a fixed-rate worker.
• Used heavily in network traffic shaping and legacy API gateways.

What is Token Bucket?

Token Bucket keeps a bucket of tokens that refills at a fixed rate. Every incoming request must consume one token to proceed. If tokens are available, even a burst of requests is allowed immediately, up to the bucket size.

• Allows controlled bursts (bucket capacity) while enforcing a long-term average rate.
• Requires only a counter and a timestamp, so it is cheap to implement and scale.
• This is why most cloud providers default to it: AWS API Gateway, Google Cloud Endpoints, and Stripe all use variations of Token Bucket.

What is Sliding Window Log?

Sliding Window Log stores the exact timestamp of every request in a sorted structure (often a sorted set in Redis). To check if a new request is allowed, the system removes timestamps older than the window and counts what remains.

• Extremely accurate, no boundary edge cases like fixed window counters.
• Memory cost scales with request volume, which becomes expensive under high traffic.
• Common in fraud detection and strict compliance-driven rate limiting, where exact accuracy matters more than memory efficiency.

Advantages and Limitations

Algorithm	Burst Handling	Memory Usage	Accuracy	Implementation Complexity
Leaky Bucket	No bursts, constant output	Low	Medium	Medium (needs queue + worker)
Token Bucket	Allows configurable bursts	Very low	Medium-High	Low
Sliding Window Log	Allows bursts within window	High (grows with traffic)	Very High	Medium-High

Best Practices

• Use Token Bucket for public APIs where short bursts are normal user behavior (page load triggering multiple calls).
• Use Leaky Bucket when downstream systems cannot tolerate any burst, such as legacy databases or third-party APIs with strict per-second limits.
• Use Sliding Window Log only when precision matters more than cost, and pair it with Redis sorted sets plus a TTL to bound memory growth.
• Always rate limit per client identifier (API key, user ID, or IP), never globally, unless you are protecting shared infrastructure.

Real Industry Example

Stripe publishes documented rate limits per API key and uses a token-bucket-style algorithm so that a burst of legitimate checkout requests does not get rejected, while sustained abuse is throttled. Cloudflare, on the other hand, uses sliding window approaches at the edge for DDoS and bot mitigation, where precise request counting across a rolling window matters more than allowing bursts. Netflix applies leaky-bucket-style smoothing internally between microservices to protect downstream services from thundering herd problems after a cache miss storm.

Common Mistakes

• Using Sliding Window Log for high-volume public APIs: leads to unnecessary memory pressure. Reserve it for lower-volume, accuracy-critical endpoints.
• Setting Token Bucket capacity too low: causes legitimate burst traffic (like page loads) to be rejected. Test with real client traffic patterns before deploying.
• Rate limiting globally instead of per client: one noisy client can starve every other user. Always key limits by user ID or API key.
• Forgetting to add Retry-After headers: clients cannot back off intelligently without knowing when to retry, which increases retry storms.

Best Practices

• Default to Token Bucket unless you have a specific reason not to, it is the most balanced choice for cost, accuracy, and burst tolerance.
• Centralize rate limiter state in Redis or a similar low-latency store for distributed systems.
• Always return clear 429 responses with a Retry-After header.
• Load test your rate limiter configuration against real traffic shapes, not synthetic uniform traffic.

Key Takeaways

• Token Bucket = burst-friendly, low memory, most widely used in production.
• Leaky Bucket = constant output rate, no bursts, good for protecting strict downstream systems.
• Sliding Window Log = most accurate, but memory-expensive at scale.
• Interviewers care about trade-off reasoning, not memorized definitions.
• Always rate limit per client identity, not globally.

Frequently Asked Questions

Q: Is Token Bucket faster than Leaky Bucket? Both are O(1) per request; the difference is behavior, not raw speed. Token Bucket allows bursts, Leaky Bucket does not.

Q: Which algorithm do most cloud API gateways use? Most major providers, including AWS and Google Cloud, use Token Bucket or a close variant because of its low overhead and burst tolerance.

Q: Can beginners implement Sliding Window Log easily? Yes, using Redis sorted sets it is a straightforward implementation, though understanding the memory trade-off is important before using it in production.

Q: What is the difference between Sliding Window Log and Sliding Window Counter? Sliding Window Log stores every timestamp for exact accuracy; Sliding Window Counter approximates using weighted counts from adjacent fixed windows, trading some accuracy for lower memory use.

Q: Do these algorithms apply outside of APIs? Yes, they are used in network traffic shaping, database connection throttling, and message queue consumers as well.

Q: Is rate limiting a common system design interview topic? Yes, it is one of the most frequently asked system design and backend interview topics across companies of all sizes.

Conclusion

Rate limiting is one of those topics that looks simple until an interviewer asks "why not just use a counter?" Understanding the trade-offs between Leaky Bucket, Token Bucket, and Sliding Window Log, burst tolerance versus memory cost versus accuracy, is what separates a memorized answer from a confident, production-ready explanation. This topic shows up constantly in backend, SRE, and system design interviews, and understanding it well pays off far beyond just passing an interview.