Rate limiting algorithms (token bucket, leaky bucket) in HLD - System Design Guide

Problem Statement

When a service receives too many requests in a short time, it can become overwhelmed, leading to slow responses or crashes. Without controlling the request rate, users or clients can unintentionally or maliciously flood the system, causing denial of service or degraded experience for others.

Solution

Rate limiting algorithms control how many requests a client can make in a given time. The token bucket algorithm allows bursts by accumulating tokens that represent permission to proceed, while the leaky bucket algorithm processes requests at a steady rate, smoothing out bursts. Both prevent overload by rejecting or delaying excess requests.

Architecture

Client

→Rate Limiter

↓

Token Bucket

Token Bucket

This diagram shows a client sending requests to a rate limiter that uses either a token bucket or leaky bucket algorithm to control request flow before forwarding allowed requests to the service.

Trade-offs

✓ Pros

→

Token bucket allows short bursts of traffic, improving user experience during sudden spikes.

→

Leaky bucket enforces a smooth, constant request rate, preventing sudden overloads.

→

Both algorithms protect backend services from being overwhelmed by excessive requests.

✗ Cons

→

Token bucket complexity increases with distributed systems needing synchronized token counts.

→

Leaky bucket can introduce latency by queuing requests to maintain steady output.

→

Implementing accurate rate limiting requires careful handling of time and concurrency.

Use token bucket when burst tolerance is needed and occasional spikes are acceptable. Use leaky bucket when a steady, predictable request rate is critical. Apply rate limiting when request rates exceed hundreds or thousands per second to protect system stability.

Avoid complex rate limiting algorithms for very low traffic systems under 100 requests per second where overhead outweighs benefits. Do not use leaky bucket if burst traffic is common and must be served quickly.

Real World Examples

Amazon

Amazon uses token bucket rate limiting in AWS API Gateway to allow clients to burst requests while protecting backend APIs from overload.

Twitter

Twitter applies leaky bucket algorithms to smooth out tweet posting rates, preventing sudden spikes from overwhelming their servers.

Google

Google Cloud services implement token bucket rate limiting to balance user request bursts with backend capacity.

Alternatives

Fixed Window Counter

Counts requests in fixed time windows without smoothing bursts, leading to potential spikes at window boundaries.

Use when: Use when simplicity is more important than smooth rate control and traffic is relatively uniform.

Sliding Window Log

Tracks timestamps of each request for precise rate limiting but requires more memory and processing.

Use when: Choose when accurate per-request rate limiting is needed and system resources allow.

Summary

Rate limiting algorithms prevent system overload by controlling request rates.

Token bucket allows bursts by accumulating tokens, while leaky bucket smooths traffic at a fixed rate.

Choosing the right algorithm depends on whether burst tolerance or steady output is more important.

Practice

1. Which rate limiting algorithm allows short bursts of traffic by accumulating tokens over time?

easy

A. Token Bucket

B. Leaky Bucket

C. Fixed Window Counter

D. Sliding Log

Solution

1. Step 1: Understand token bucket behavior

   The token bucket algorithm accumulates tokens at a fixed rate, allowing bursts when tokens are available.

2. Step 2: Compare with leaky bucket

   The leaky bucket processes requests at a steady rate, smoothing bursts rather than allowing them.

3. Final Answer:

   Token Bucket -> Option A

4. Quick Check:

   Token Bucket = allows bursts [OK]

Hint: Token bucket = bursts allowed, leaky bucket = steady flow [OK]

Common Mistakes:

• Confusing leaky bucket with token bucket
• Thinking fixed window allows bursts
• Mixing sliding log with token bucket

2. Which of the following is the correct description of the leaky bucket algorithm?

easy

A. Requests are counted in fixed time windows

B. Tokens accumulate and requests consume tokens

C. Requests are processed at a fixed rate regardless of burst

D. Requests are logged with timestamps for sliding window

Solution

1. Step 1: Recall leaky bucket mechanism

   Leaky bucket processes requests at a constant rate, smoothing out bursts by queuing excess requests.

2. Step 2: Eliminate other options

   Tokens accumulate and requests consume tokens describes token bucket, C and D describe other rate limiting methods.

3. Final Answer:

   Requests are processed at a fixed rate regardless of burst -> Option C

4. Quick Check:

   Leaky bucket = fixed rate processing [OK]

Hint: Leaky bucket = steady output rate, no bursts allowed [OK]

Common Mistakes:

• Confusing token accumulation with leaky bucket
• Mixing fixed window counting with leaky bucket
• Assuming leaky bucket allows bursts

3. Consider a token bucket with a capacity of 5 tokens and a refill rate of 1 token per second. Initially, the bucket is full. If 7 requests arrive instantly, how many requests will be allowed immediately?

medium

A. 5

B. 7

C. 1

D. 0

Solution

1. Step 1: Understand token bucket capacity and refill

   The bucket starts full with 5 tokens, each request consumes one token.

2. Step 2: Calculate allowed requests

   Since 7 requests arrive instantly but only 5 tokens are available, only 5 requests are allowed immediately.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Tokens available = 5, requests = 7, allowed = 5 [OK]

Hint: Max allowed = tokens in bucket at request time [OK]

Common Mistakes:

• Assuming all 7 requests allowed instantly
• Ignoring token bucket capacity
• Confusing refill rate with immediate tokens

4. A developer implemented a leaky bucket rate limiter but notices that bursts are still allowed. What is the most likely cause?

medium

A. The bucket capacity is set too low

B. Requests are dequeued faster than the leak rate

C. Tokens are refilled too quickly

D. The leak rate is set to zero

Solution

1. Step 1: Analyze leaky bucket behavior

   Leaky bucket allows steady output by leaking requests at a fixed rate.

2. Step 2: Identify cause of bursts

   If requests are dequeued faster than the leak rate, bursts can pass through, breaking the smoothing effect.

3. Final Answer:

   Requests are dequeued faster than the leak rate -> Option B

4. Quick Check:

   Dequeue rate > leak rate = bursts allowed [OK]

Hint: Leaky bucket bursts mean dequeue faster than leak rate [OK]

Common Mistakes:

• Confusing token refill with leaky bucket
• Assuming bucket capacity controls bursts
• Ignoring dequeue speed vs leak rate

5. You need to design a rate limiter for an API that allows short bursts but enforces an average rate limit over time. Which algorithm should you choose and why?

hard

A. Leaky Bucket, because it smooths out bursts by processing requests steadily

B. Fixed Window Counter, because it counts requests in fixed intervals

C. Sliding Log, because it logs every request timestamp

D. Token Bucket, because it allows bursts by accumulating tokens and enforces average rate

Solution

1. Step 1: Understand requirement for bursts and average rate

   The system must allow short bursts but keep average rate limited over time.

2. Step 2: Match algorithm to requirement

   Token bucket allows bursts by using tokens that refill over time, enforcing average rate while permitting bursts.

3. Final Answer:

   Token Bucket, because it allows bursts by accumulating tokens and enforces average rate -> Option D

4. Quick Check:

   Bursts + average rate = Token Bucket [OK]

Hint: Token bucket = bursts + average rate control [OK]

Common Mistakes:

• Choosing leaky bucket which smooths bursts
• Confusing fixed window with burst allowance
• Ignoring average rate enforcement