Design a rate limiter in HLD - System Design Exercise

Design: Rate Limiter

Design focuses on the rate limiting component integrated with an API gateway or service. Authentication and API business logic are out of scope.

Functional Requirements

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

FR2: Support different rate limits for different users or API keys

FR3: Provide real-time feedback when limits are exceeded

FR4: Ensure minimal latency impact on request processing

FR5: Allow configuration of limits per API endpoint

FR6: Support distributed deployment for scalability

Non-Functional Requirements

NFR1: Handle up to 100,000 requests per second

NFR2: Latency for rate limit check should be under 10ms (p99)

NFR3: Availability target of 99.9% uptime

NFR4: Rate limits must be enforced accurately across multiple servers

NFR5: System should be resilient to clock skew between servers

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

❓ Question 6

Key Components

API Gateway or Proxy to intercept requests

In-memory cache or datastore for counters (e.g., Redis)

Distributed synchronization mechanism

Configuration service for rate limit rules

Monitoring and alerting system

Design Patterns

Fixed Window Counter

Sliding Window Log

Sliding Window Counter

Token Bucket

Leaky Bucket

Distributed Cache with Atomic Operations

Reference Architecture

Client
  |
  v
API Gateway / Proxy
  |
  v
Rate Limiter Service <--> Configuration Store
  |
  v
Distributed Cache (Redis Cluster)
  |
  v
Backend Services

Monitoring & Alerting System (observes Rate Limiter metrics)

Components

API Gateway / Proxy

Nginx, Envoy, or custom proxy

Intercept incoming requests and forward them to rate limiter before backend

Rate Limiter Service

Stateless microservice in Go/Java/Python

Check and enforce rate limits using counters in distributed cache

Distributed Cache

Redis Cluster with atomic INCR and EXPIRE commands

Store counters for requests per user/key with TTL for time windows

Configuration Store

Relational DB or NoSQL (PostgreSQL, DynamoDB)

Store rate limit rules per user, API key, or endpoint

Monitoring & Alerting

Prometheus + Grafana or Datadog

Track rate limiter performance, errors, and usage patterns

Request Flow

1. Client sends request to API Gateway

2. API Gateway forwards request to Rate Limiter Service

3. Rate Limiter Service fetches applicable rate limit rules from Configuration Store or cache

4. Rate Limiter Service increments request counter in Distributed Cache atomically

5. If counter exceeds limit, Rate Limiter Service rejects request with 429 Too Many Requests

6. If under limit, Rate Limiter Service allows request to proceed to backend

7. Rate Limiter Service returns response to API Gateway

8. API Gateway forwards response to client

9. Monitoring system collects metrics from Rate Limiter Service

Database Schema

Entities: - User (user_id, user_type, etc.) - APIKey (key_id, user_id, permissions) - RateLimitRule (rule_id, target_type [user/api_key/endpoint], target_id, limit_count, window_seconds) Relationships: - User 1:N APIKey - RateLimitRule applies to User or APIKey or Endpoint Counters stored in Redis as keys: "rate_limit:{target_id}:{window_start_timestamp}" with integer count and TTL equal to window_seconds

Scaling Discussion

Bottlenecks

Distributed cache becoming a single point of failure or bottleneck under high QPS

Synchronization issues causing inaccurate counters due to race conditions

Latency increase due to network calls to cache for every request

Configuration store latency or stale rules causing incorrect enforcement

Handling sudden traffic spikes causing burst limit breaches

Solutions

Use Redis Cluster with sharding and replication for high availability and throughput

Use atomic increment operations and Lua scripts in Redis to ensure consistency

Implement local caching of rate limit rules to reduce configuration store calls

Use approximate algorithms (e.g., sliding window counters) to reduce strict locking

Implement burst handling with token bucket allowing short bursts without penalty

Deploy rate limiter service close to API gateway to reduce network latency

Interview Tips

Time: Spend 10 minutes clarifying requirements and constraints, 20 minutes designing architecture and data flow, 10 minutes discussing scaling and trade-offs, 5 minutes summarizing.

Clarify types of rate limiting and use cases

Explain choice of data store and atomic operations for counters

Discuss trade-offs between accuracy and performance

Highlight distributed consistency challenges and solutions

Mention monitoring importance for operational health

Show awareness of scaling bottlenecks and mitigation strategies

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