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

Design: Rate Limiting System

Design the core rate limiting algorithms and their integration in a distributed API gateway or service. Out of scope: detailed user authentication, billing, or analytics.

Functional Requirements

FR1: Limit the number of requests a user or client can make in a given time window

FR2: Support burst traffic without dropping all requests immediately

FR3: Prevent system overload by smoothing request rates

FR4: Provide configurable limits per user or API key

FR5: Handle millions of requests per second across distributed servers

FR6: Ensure fairness and prevent abuse

Non-Functional Requirements

NFR1: Latency impact on request processing must be minimal (p99 < 10ms)

NFR2: System must be highly available (99.9% uptime)

NFR3: Rate limits must be consistent across distributed instances

NFR4: Support horizontal scaling to handle increasing traffic

NFR5: Memory usage per user/client must be efficient

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

Key Components

API Gateway or Load Balancer

Rate Limiter module implementing token bucket or leaky bucket

Distributed cache or in-memory store (e.g., Redis) for counters

Configuration service for rate limit policies

Monitoring and alerting system

Design Patterns

Token Bucket algorithm for burst handling

Leaky Bucket algorithm for smoothing traffic

Distributed counters with atomic increments

Sliding window rate limiting

Client-side vs server-side rate limiting

Reference Architecture

Client --> API Gateway --> Rate Limiter --> Backend Service
                    |              |
                    |              v
                    |          Distributed Cache
                    v
               Configuration Service

Components

API Gateway

Nginx or Envoy proxy

Entry point for client requests, routes traffic, and enforces rate limits

Rate Limiter

Custom module or middleware

Implements token bucket or leaky bucket algorithm to allow or reject requests

Distributed Cache

Redis with atomic commands

Stores counters and tokens per user/client for distributed consistency

Configuration Service

Central config store (e.g., Consul, etcd)

Manages rate limit policies and parameters

Request Flow

1. Client sends request to API Gateway

2. API Gateway forwards request to Rate Limiter module

3. Rate Limiter fetches current token count or leak state from Distributed Cache

4. Rate Limiter applies token bucket or leaky bucket logic:

5. - Token Bucket: refill tokens at fixed rate, consume token per request

6. - Leaky Bucket: requests enter queue, leak out at fixed rate

7. If tokens available or bucket not full, allow request and update cache

8. If limit exceeded, reject request with HTTP 429 Too Many Requests

9. Allowed requests proceed to Backend Service

10. Configuration Service updates rate limit parameters dynamically

Database Schema

Entities: - User or Client: id, rate_limit_policy_id - RateLimitPolicy: id, max_tokens, refill_rate, bucket_capacity, algorithm_type - TokenBucketState: user_id, tokens, last_refill_timestamp - LeakyBucketState: user_id, queue_size, last_leak_timestamp Relationships: - User references RateLimitPolicy - TokenBucketState and LeakyBucketState track per-user algorithm state

Scaling Discussion

Bottlenecks

Distributed cache becoming a single point of failure or bottleneck

High latency due to frequent cache reads/writes for counters

Inconsistent rate limiting state across distributed nodes

Memory overhead for storing state of millions of users

Handling sudden traffic spikes causing bursts beyond capacity

Solutions

Use Redis clusters with sharding and replication for high availability

Batch or approximate counter updates to reduce cache operations

Use consistent hashing to route requests of same user to same node

Evict or expire inactive user states to save memory

Implement hierarchical rate limiting with global and local limits

Interview Tips

Time: Spend 10 minutes understanding requirements and clarifying assumptions, 20 minutes designing the architecture and algorithms, 10 minutes discussing scaling and trade-offs, 5 minutes summarizing.

Explain difference between token bucket and leaky bucket algorithms

Discuss how burst traffic is handled gracefully

Describe how distributed state is managed for consistency

Highlight latency and availability considerations

Mention trade-offs between accuracy and performance

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