Design a rate limiter in HLD - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Rate Limiter Algorithm Choice

You want to limit the number of requests a user can make to an API to 100 requests per minute. Which rate limiting algorithm is best suited to allow some bursts but still enforce the limit?

A Token bucket

B Sliding window log

C Fixed window counter

D Leaky bucket

💡 Hint

Think about which algorithm allows bursts but controls the average rate.

The token bucket algorithm allows bursts by accumulating tokens and enforces an average rate limit. Fixed window counters can cause spikes at window edges. Sliding window logs are accurate but expensive. Leaky bucket smooths out bursts but does not allow bursts.

❓ Architecture

intermediate

Distributed Rate Limiter Design

You need to design a rate limiter that works across multiple servers handling user requests. Which component is essential to ensure consistent rate limiting across all servers?

A Local in-memory counters on each server

B Separate rate limiters per server without coordination

C A centralized data store shared by all servers

D Client-side rate limiting only

💡 Hint

Think about how to keep counters consistent across servers.

A centralized data store ensures all servers share the same counters, preventing users from bypassing limits by switching servers. Local counters or uncoordinated limiters can cause inconsistent enforcement.

❓ scaling

advanced

Scaling Rate Limiter for High Traffic

Your API receives millions of requests per minute. Which approach best scales the rate limiter to handle this load without becoming a bottleneck?

A Shard counters across multiple Redis instances by user ID

B Use a single Redis instance to store all counters

C Store counters in a relational database with transactions

D Keep counters only in server memory without persistence

💡 Hint

Consider how to distribute load and avoid single points of failure.

Sharding counters across multiple Redis instances distributes load and avoids bottlenecks. A single Redis instance can become overwhelmed. Relational databases are too slow for this use case. In-memory counters lack persistence and consistency.

❓ tradeoff

advanced

Tradeoffs Between Accuracy and Performance

Which rate limiting approach trades off some accuracy for better performance and lower storage needs?

A Sliding window log storing every request timestamp

B Fixed window counter resetting every minute

C Token bucket with approximate counters

D Leaky bucket with exact queue of requests

💡 Hint

Think about which method uses less data but can cause bursts at window edges.

Fixed window counters are simple and fast but can cause bursts at window boundaries, reducing accuracy. Sliding window logs are accurate but expensive. Token bucket and leaky bucket offer different tradeoffs but usually require more state.

❓ estimation

expert

Capacity Estimation for Rate Limiter Storage

You expect 10 million users, each allowed 100 requests per minute. You want to store counters for each user in Redis with 8 bytes per counter. Estimate the minimum memory needed to store counters for all users for a 1-minute window.

A Approximately 80 GB

B Approximately 80 MB

C Approximately 8 GB

D Approximately 800 MB

💡 Hint

Calculate: 10 million users * 8 bytes per counter.

10,000,000 users * 8 bytes = 80,000,000 bytes = ~80 MB. But Redis stores overhead per key, so actual memory is higher. Considering overhead, estimate about 800 MB.

Practice

1. What is the primary purpose of a rate limiter in system design?

easy

A. To control the number of requests a user can make in a given time

B. To increase the speed of database queries

C. To store user data securely

D. To balance load between multiple servers

Solution

1. Step 1: Understand the role of rate limiter

   A rate limiter restricts how many requests a user or client can send in a certain time to prevent overload.

2. Step 2: Identify the correct purpose

   Among the options, only controlling request rate matches the rate limiter's function.

3. Final Answer:

   To control the number of requests a user can make in a given time -> Option A

4. Quick Check:

   Rate limiter = control request rate [OK]

Hint: Rate limiter limits requests per time window [OK]

Common Mistakes:

• Confusing rate limiter with load balancer
• Thinking it speeds up database queries
• Assuming it stores user data

2. Which data structure is most suitable to implement a sliding window rate limiter?

easy

A. Stack

B. Hash Map

C. Queue

D. Binary Tree

Solution

1. Step 1: Recall sliding window mechanism

   Sliding window rate limiter tracks timestamps of requests in a time window, removing old ones as time moves.

2. Step 2: Choose data structure for efficient insert and remove

   A queue allows adding new timestamps at the end and removing old timestamps from the front efficiently, matching sliding window needs.

3. Final Answer:

   Queue -> Option C

4. Quick Check:

   Sliding window = queue for timestamps [OK]

Hint: Sliding window needs FIFO structure like queue [OK]

Common Mistakes:

• Using stack which is LIFO, not suitable
• Choosing hash map without order
• Picking binary tree which is complex here

3. Consider a rate limiter allowing 3 requests per 10 seconds using sliding window. If requests come at seconds 1, 3, 7, and 9, which request will be rejected?

medium

A. Request at second 9

B. Request at second 3

C. Request at second 7

D. Request at second 1

Solution

1. Step 1: Track requests in 10-second window

   Requests at 1, 3, 7 are allowed as they are within limit 3 per 10 seconds.

2. Step 2: Check request at second 9

   At second 9, previous requests at 1, 3, 7 are still within 10 seconds window (from -1 to 9). So 3 requests already made, this 4th request exceeds limit and is rejected.

3. Final Answer:

   Request at second 9 -> Option A

4. Quick Check:

   4th request in 10s window = rejected [OK]

Hint: Count requests in last 10 seconds; 4th exceeds limit [OK]

Common Mistakes:

• Ignoring requests older than 10 seconds
• Allowing all requests without limit
• Counting requests incorrectly

4. A rate limiter uses a fixed window counter but sometimes allows bursts of requests at window edges. What is the likely cause?

medium

A. Sliding window algorithm is used

B. Queue data structure is not used

C. Rate limit is set too low

D. Fixed window resets counters abruptly causing bursts

Solution

1. Step 1: Understand fixed window behavior

   Fixed window counts requests in fixed intervals, resetting count at window end.

2. Step 2: Identify burst cause

   Requests near end of one window and start of next can both be allowed, causing bursts.

3. Final Answer:

   Fixed window resets counters abruptly causing bursts -> Option D

4. Quick Check:

   Fixed window reset causes bursts [OK]

Hint: Fixed window resets cause bursts at edges [OK]

Common Mistakes:

• Confusing sliding window with fixed window
• Blaming rate limit value instead of algorithm
• Ignoring window reset behavior

5. You need to design a distributed rate limiter for millions of users with low latency. Which approach best balances accuracy and scalability?

hard

A. Centralized fixed window counter on a single server

B. Distributed sliding window using local caches and periodic sync

C. Per-user token bucket stored only in client devices

D. No rate limiting, rely on server hardware scaling

Solution

1. Step 1: Consider scalability and accuracy needs

   Millions of users require distributed design to avoid bottlenecks and reduce latency.

2. Step 2: Evaluate options

   Centralized fixed window causes bottleneck; client-only token bucket is insecure; no rate limiting risks overload. Distributed sliding window with local caches and sync balances accuracy and scalability.

3. Final Answer:

   Distributed sliding window using local caches and periodic sync -> Option B

4. Quick Check:

   Distributed sliding window = scalable + accurate [OK]

Hint: Use distributed sliding window with local caches [OK]

Common Mistakes:

• Choosing centralized approach causing bottlenecks
• Relying on client-only enforcement
• Ignoring rate limiting and risking overload