Rate limiting algorithms (token bucket, leaky bucket) in HLD - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding Token Bucket Algorithm Behavior

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

A 2 requests allowed immediately, 5 requests rejected

B 7 requests allowed immediately

C 0 requests allowed immediately, all queued

D 5 requests allowed immediately, 2 requests rejected

💡 Hint

Think about how many tokens are available at the start and how many requests consume tokens.

The bucket starts full with 5 tokens. Each request consumes one token. So, 5 requests can be served immediately. The remaining 2 requests have no tokens and are rejected or delayed.

❓ Architecture

intermediate

Choosing Between Token Bucket and Leaky Bucket

You are designing an API gateway that needs to limit request bursts but also smooth out traffic spikes over time. Which rate limiting algorithm is more suitable?

A Token Bucket, because it allows bursts up to bucket capacity

B Leaky Bucket, because it allows bursts up to bucket capacity

C Leaky Bucket, because it allows unlimited bursts

D Token Bucket, because it enforces a fixed output rate regardless of bursts

💡 Hint

Consider which algorithm allows bursts and which smooths traffic strictly.

Token Bucket allows bursts up to the bucket capacity by accumulating tokens. Leaky Bucket enforces a fixed output rate, smoothing traffic but not allowing bursts.

❓ scaling

advanced

Scaling Rate Limiter for Distributed Systems

You need to implement a distributed rate limiter using the token bucket algorithm across multiple servers. What is the main challenge and best approach?

A Challenge: High memory usage; Approach: Store tokens locally on each server without synchronization

B Challenge: Synchronizing token counts; Approach: Use a centralized token store with atomic operations

C Challenge: Network latency; Approach: Use local caches and ignore synchronization

D Challenge: Token overflow; Approach: Increase bucket size infinitely

💡 Hint

Think about consistency of token counts across servers.

Distributed token bucket requires synchronizing token counts to avoid allowing more requests than the limit. A centralized store with atomic operations ensures consistency.

❓ tradeoff

advanced

Tradeoffs Between Token Bucket and Leaky Bucket

Which statement correctly describes a tradeoff between token bucket and leaky bucket algorithms?

A Token bucket allows bursty traffic but can cause uneven output; leaky bucket smooths output but rejects bursts

B Leaky bucket allows bursty traffic but can cause uneven output; token bucket smooths output but rejects bursts

C Both algorithms allow unlimited bursts but differ in refill rates

D Token bucket rejects all bursts; leaky bucket allows bursts up to bucket size

💡 Hint

Recall how each algorithm handles bursts and output rate.

Token bucket allows bursts by accumulating tokens, which can cause uneven output. Leaky bucket enforces a steady output rate, smoothing traffic but rejecting bursts.

❓ estimation

expert

Estimating Capacity for Rate Limiter with Token Bucket

You have a token bucket rate limiter with a bucket size of 100 tokens and a refill rate of 10 tokens per second. What is the maximum number of requests that can be served in a 15-second window assuming the bucket starts full and requests arrive uniformly?

A 100 requests

B 150 requests

C 250 requests

D 50 requests

💡 Hint

Calculate total tokens available: initial tokens plus tokens refilled over time.

Total tokens = initial bucket size (100) + refill rate (10 tokens/sec) * 15 seconds = 100 + 150 = 250 tokens, so 250 requests can be served.

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