Rate limiting algorithms (token bucket, leaky bucket) in HLD - Scalability & System Analysis

Scalability Analysis - Rate limiting algorithms (token bucket, leaky bucket)

Growth Table: Rate Limiting Algorithms

Users/Traffic	Token Bucket	Leaky Bucket	System Impact
100 users	Simple in-memory counters, low memory	Simple queue with fixed leak rate	Works well on single server
10K users	Needs distributed counters or shared cache	Queue size grows, needs distributed state	Single server may struggle with concurrency
1M users	Distributed token buckets with sharding or Redis cluster	Distributed leaky bucket queues with partitioning	State synchronization and latency increase
100M users	Highly scalable distributed caches, approximate counters (e.g. Bloom filters)	Approximate leak rate enforcement, multi-region coordination	Network and storage bottlenecks appear

First Bottleneck

The first bottleneck is the state storage for counters or queues that track tokens or leaks.

At low scale, in-memory counters suffice. As users grow, the system must maintain distributed state with low latency.

This state storage (e.g., Redis or distributed cache) can become overwhelmed by high QPS and concurrent updates.

Scaling Solutions

• Horizontal scaling: Add more rate limiter instances behind a load balancer.
• Distributed caching: Use Redis clusters or similar to store counters with sharding.
• Approximate algorithms: Use probabilistic data structures to reduce storage and update costs.
• Local token buckets: Use local counters with periodic sync to reduce latency.
• Rate limit partitioning: Partition users by key (e.g., user ID hash) to spread load.
• Backpressure and queuing: For leaky bucket, use queues with controlled leak rates and backpressure to smooth bursts.

Back-of-Envelope Cost Analysis

Assuming 1M users, each making 1 request per second:

• Requests per second: 1 million QPS total.
• Each request updates a token bucket counter or leaky bucket queue.
• Redis can handle ~100K ops/sec per instance; need ~10 Redis instances for counters.
• Network bandwidth: 1M QPS * ~200 bytes/request = ~200 MB/s (1.6 Gbps), requires multiple network links.
• Memory: Each token bucket counter ~100 bytes; for 1M users = ~100 MB RAM, feasible in distributed cache.

Interview Tip

Start by explaining the rate limiting goal: controlling request rate per user or client.

Describe token bucket and leaky bucket simply, focusing on how they handle bursts and steady rates.

Discuss state storage challenges and how scaling affects latency and consistency.

Outline scaling strategies: horizontal scaling, distributed caches, sharding, and approximate methods.

Use real numbers to show understanding of system limits and trade-offs.

Self Check

Question: Your database handles 1000 QPS for rate limiting counters. Traffic grows 10x to 10,000 QPS. What do you do first?

Answer: Introduce a distributed cache like Redis with sharding to offload counters from the database, reducing latency and increasing throughput.

Key Result

Rate limiting algorithms scale well initially with in-memory counters but face bottlenecks in distributed state storage as traffic grows; scaling requires distributed caches, sharding, and approximate methods to maintain low latency and high throughput.

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