Rate Limiter

Problem

Design a rate limiter that restricts the number of requests a user/service can make in a given time window.

---

Functional Requirements

• Allow N requests per user per time window (e.g., 100 req/min)
• Return HTTP 429 (Too Many Requests) when limit exceeded
• Support different limits per API endpoint / user tier

Non-Functional Requirements

• Low latency — rate check must not slow the request path
• Highly available — limiter failure ≠ service failure
• Distributed — works across multiple servers

---

Algorithms for Rate Limiting

1. Token Bucket — used by Amazon, Stripe

• A container with predefined capacity. A set of tokens is added periodically.
• Each request takes 1 token. If the bucket is empty → reject (429).

flowchart LR
    Req[Request] --> Check{Enough<br/>tokens?}
    Refill[Refill tokens<br/>periodically] --> Check
    Check -- Yes: forward --> Server[Server]
    Check -- No --> Drop[Drop request<br/>Return 429]

• Two parameters: bucket size, refill rate.
• How many buckets needed?
  • Each endpoint can have its own bucket.
  • Throttle by IP / user → one bucket per IP / user.
  • If system allows a flat global limit (e.g. 10k req/s) → a global bucket is enough.
• Pros: simple to implement, handles bursts, memory efficient.
• Cons: requires parameter tuning.

2. Leaking Bucket — used by Shopify

• Similar to token bucket, but requests are processed at a fixed rate via a FIFO queue.

flowchart LR
    Req[Request] --> Full{Bucket<br/>full?}
    Full -- Yes --> Drop[Drop]
    Full -- No: append --> Queue[FIFO Queue]
    Queue -- process at<br/>fixed rate --> Server[Server]

• Parameters: bucket size (queue size), outflow rate.
• Pros: memory efficient, stable outflow rate.
• Cons: cannot handle bursts (smooths them away), parameter tuning.

3. Fixed Window Counter

• A simple counter per window that resets at the next window.
• If request counter is within threshold → process, else reject.
• Pros: memory efficient, simple.
• Cons: a spike at the edge of a window can allow up to 2× the limit (e.g. burst at 1:00.5 and 1:01.0 both pass, overlapping a real ~1s span).

4. Sliding Window Log

• Tracks each request's timestamp. Stores data in cache — e.g. Redis sorted sets.
• On a new request → remove outdated timestamps, add the new request's timestamp to the log.
• If log size is ≤ threshold → accept.
• Pros: accurate — in any window the limit is never exceeded.
• Cons: consumes a lot of memory (even rejected requests are stored).

5. Sliding Window Counter

• Hybrid of fixed window + sliding window log, using a rolling window.
• Count ≈ requests in current window + requests in previous window × overlap percentage.

count = req_current_window + req_prev_window * overlap_%

• Pros: smooths out traffic spikes (uses the average rate of the previous window), memory efficient.
• Cons: only works for a not-too-strict look-back window; it's an approximation — assumes requests in the previous window are evenly distributed (but "not as bad as it seems").

Algorithm comparison

---

High-Level Architecture

Counters are stored in Redis (in-memory). Two key commands:

• INCR — increases the stored counter by 1.
• EXPIRE — sets a timeout on the counter; when it expires the counter is auto-deleted (gives the sliding/fixed window).

flowchart LR
    Client[Client] --> MW{Rate Limiter<br/>Middleware}
    Rules[(Rules on disk)] -.workers pull.-> Cache[Cache<br/>cached rules]
    Cache --> MW
    Redis[(Redis<br/>counters)] --> MW
    MW -- success --> Server[Servers]
    MW -- rate limited: option 1 --> Dropped[Request dropped<br/>429]
    MW -- rate limited: option 2 --> MQ[Message Queue<br/>process later]

• Rules are stored on disk. Workers frequently pull rules from disk and store them in the cache.
• On limit breach, two options: drop the request (429) or enqueue it to a message queue for later processing.

Rate Limiting Rules — Lyft open-source (Envoy) style

Rules expressed as a domain + descriptors:

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

domain: auth
descriptors:
  - key: auth_type
    value: login
    rate_limit:
      unit: minute
      requests_per_unit: 5

Rate Limit Response Headers

• X-RateLimit-Remaining — remaining number of allowed requests within the window.
• X-RateLimit-Limit — how many calls the client can make per time window.
• X-RateLimit-Retry-After — seconds to wait before making a request again without being throttled.

---

In a Distributed Environment

Two challenges: race condition and synchronization.

Race Condition

Classic read-modify-write lost update:

req 1: read_counter = 3  →  increment → 4
req 2: read_counter = 3  →  increment → 4     (value should be 5!)

• Naive fix: locks — but they slow the system down.
• Better in Redis: (1) Lua script (atomic read-modify-write) or (2) sorted-set data structure.

Synchronization Issue

Multiple rate-limiter service instances a client can connect to → counters diverge.

• Sticky session — route a client's traffic to the same rate limiter. (Works, but uneven load / poor failover.)
• Better: a centralized data store (Redis) shared by all limiter instances.

---

Performance Optimization

1. Multi-datacenter setup for the rate limiter (keep it close to users).
2. Eventual consistency for cross-region synchronization (avoid strong-consistency latency).

Monitoring

Make sure:

• The rate-limiting algorithm is effective.
• The rate-limiting rules are effective.

---

Extra Considerations

• Hard rate limiting: number of requests cannot exceed the threshold.
• Soft rate limiting: requests can exceed the threshold for a short period.
• Rate limiting at different levels:
  • We discussed the application level (HTTP, Layer 7).
  • Can also apply at IP level using iptables (Layer 3).
• OSI model (7 layers): 1. Physical · 2. Data Link · 3. Network · 4. Transport · 5. Session · 6. Presentation · 7. Application.

---

Key Trade-offs

---

Interview Talking Points

• Token bucket vs sliding window: Stripe/Amazon use token bucket; sorted-set log when exactness matters.
• Race condition on counter → Redis Lua script (atomic) instead of locks.
• Distributed limiting → centralized store beats sticky sessions.
• Headers: X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Retry-After.
• Fixed-window edge burst (2×) → why sliding window counter is the pragmatic default.
• Levels: L7 (app/HTTP) vs L3 (IP/iptables).

Related

• [[System Design/Databases/Redis]] — INCR/EXPIRE, sorted sets, single-thread atomicity
• [[Message Queues & Kafka]] — the "enqueue over-limit" option
• [[synthesis/Job Switch Hub]] · [[API Gateway]]