Design a Rate Limiter

A rate limiter controls the rate of traffic sent by a client or service. In HTTP, it limits client requests allowed over a specified period; excess calls are blocked. Examples:

• Max 2 posts per second per user
• Max 10 accounts per day from same IP
• Max 5 reward claims per week from same device

Benefits:

1. Prevent resource starvation from DoS attacks (Twitter: 300 tweets/3h; Google Docs: 300 read reqs/60s per user)
2. Reduce cost: fewer servers, limit paid 3rd-party API calls
3. Prevent server overload from bots/user misbehavior

Step 1 of 4: Understand the problem and establish design scope #

Goal: pin down the requirements and constraints before designing.

Requirements #

Must have:

1. Server-side API rate limiter
2. Flexible throttle rules (by IP, user ID, etc.)
3. Handles large request volume
4. Works in a distributed environment
5. Informs users when throttled

System requirements:

1. Accurately limit excessive requests
2. Low latency (no HTTP slowdown)
3. Use as little memory as possible
4. Distributed rate limiting (across multiple servers/processes)
5. Return clear exceptions to throttled users
6. High fault tolerance (cache server offline shouldn't break the entire system)

Step 2 of 4: Propose high-level design and get buy-in #

Goal: agree on placement and pick the algorithm before diving deep.

Where to put the rate limiter? #

Client-side: unreliable: requests easily forged by malicious actors, no control over client implementation.

Server-side:

Middleware approach (API gateway):

Example: API allows 2 req/s. Client sends 3 requests in one second → first 2 routed to API servers, 3rd throttled with HTTP 429.

Decision factors:

1. Current technology stack (language, cache service)
2. Algorithm control (full control server-side vs limited with 3rd-party gateway)
3. Existing microservice architecture + API gateway → add rate limiter to gateway
4. Engineering resources → build vs buy commercial API gateway

Algorithms for rate limiting #

Token bucket algorithm #

Used by Amazon and Stripe.

How it works: bucket with predefined capacity. Tokens added at a preset rate periodically. Each request consumes one token. No tokens → request dropped.

Parameters: bucket size, refill rate.

Buckets needed: per API endpoint, per IP address, global bucket (10,000 req/s).

Pros: easy to implement, memory efficient, allows burst traffic. Cons: two parameters challenging to tune properly.

Leaking bucket algorithm #

Used by Shopify. Implemented with a FIFO queue.

How it works: request arrives → check if queue is full → if not, add to queue; otherwise drop. Requests pulled from queue at a fixed rate.

Parameters: bucket size (queue size), outflow rate.

Pros: memory efficient, fixed rate suitable for stable outflow use cases. Cons: burst traffic fills the queue with old requests, starving recent ones. Two parameters hard to tune.

Fixed window counter algorithm #

How it works: divide the timeline into fixed windows, each with a counter. Each request increments the counter. Counter reaches threshold → new requests dropped until the new window.

Critical flaw: traffic spikes at window edges let double the allowed requests through.

Example: 5 req/min allowed, but in a rolling window from 2:00:30 to 2:01:30, 10 requests pass: twice the limit.

Pros: memory efficient, easy to understand, quota reset fits certain use cases. Cons: spike at window edges allows excess requests.

Sliding window log algorithm #

How it works: track request timestamps (e.g. Redis sorted sets). On new request: remove outdated timestamps (older than window start), add new timestamp, check if log size ≤ allowed count.

Example: 2 req/min allowed. Requests at 1:00:01 ✓, 1:00:30 ✓, 1:00:50 ✗ (log=3 > 2). At 1:01:40, outdated 1:00:01 and 1:00:30 removed, log=2, request accepted.

Pros: very accurate: no request will exceed the rate limit in any rolling window. Cons: high memory usage (rejected request timestamps still stored).

Sliding window counter algorithm #

Hybrid of fixed window counter and sliding window log. Formula:

Requests in rolling window = current_window_count + previous_window_count × overlap_percentage

Example: max 7 req/min. Previous window: 5 requests, current window: 3 requests. New request at 30% into current window → 3 + 5 × 0.7 = 6.5 → rounded to 6. Request accepted.

Pros: smooths traffic spikes (average rate of previous window), memory efficient. Cons: approximation (assumes even distribution in previous window). Cloudflare experiment: only 0.003% of requests incorrectly allowed/blocked among 400M.

High-level architecture #

Store counters in an in-memory cache (Redis) using INCR (increment counter) and EXPIRE (set timeout for auto-deletion). Flow:

1. Client → rate limiting middleware
2. Middleware checks counter from Redis bucket
3. Limit reached → reject request
4. Not reached → forward to API servers, increment counter in Redis

Step 3 of 4: Design deep dive #

Goal: harden the design: rules, distributed behavior, performance, monitoring.

Rate limiting rules #

Configuration in files on disk (Lyft example):

domain: messaging
descriptors:
  - key: message_type
    value: marketing
    rate_limit:
      unit: day
      requests_per_unit: 5

Exceeding the rate limit #

Return HTTP 429 (too many requests). May enqueue rate-limited requests for later processing (e.g. orders during system overload).

Rate limiter HTTP headers:

1. X-Ratelimit-Remaining: remaining allowed requests in window
2. X-Ratelimit-Limit: max calls per time window
3. X-Ratelimit-Retry-After: seconds to wait before retry

Detailed design #

1. Rules stored on disk, workers pull into cache
2. Client request → rate limiter middleware → loads rules from cache → fetches counters/timestamps from Redis → decides: forward to API servers or return 429 (request dropped or queued)

Rate limiter in a distributed environment #

Race condition #

Counter value is 3. Two concurrent threads both read 3, both increment to 4, both write 4. Correct value should be 5.

Solutions: Lua scripts or Redis sorted sets (locks slow down the system).

Synchronization issue #

Multiple rate limiter servers: Client 1 → limiter 1, Client 2 → limiter 2. Without synchronization, limiter 1 has no data about client 2.

Bad solution: sticky sessions (not scalable/flexible). Good solution: centralized data store (Redis).

Performance optimization #

1. Multi-data center setup: route traffic to the closest edge server (Cloudflare: 194 edge locations as of 2020) to reduce latency
2. Eventual consistency model for data synchronization

Monitoring #

Verify:

1. Rate limiting algorithm is effective
2. Rate limiting rules are effective (not too strict, handle traffic surges)

Step 4 of 4: Wrap up #

Algorithms covered: token bucket, leaking bucket, fixed window, sliding window log, sliding window counter.

Additional talking points:

1. Hard vs soft rate limiting: hard never exceeds; soft can exceed briefly
2. OSI layers: application layer 7 HTTP shown; possible at layer 3 IP via Iptables
3. Client best practices: cache to avoid frequent calls, understand limits, catch exceptions gracefully, add backoff time to retry logic