Design a Distributed Rate Limiter

3. Clarify non functional requirements

• Traffic: High scale. Assume 100 Million Daily Active Users (DAU) and 1 Billion requests per day.

• Latency: Critical. The limiter sits on the "hot path". It must add less than 10ms latency.

• Availability: Very High (99.99%).

• Reliability: Fail-Open. If the rate limiter service goes down or times out, we must allow the traffic to prevent a total system outage.

• Consistency: Eventual consistency is acceptable, but synchronization must be fast enough (sub-second) to prevent massive abuse.

• Data Retention: Ephemeral. Counters are only needed for the duration of the window (e.g., 1 minute).

4. Back of the envelope estimates

• Throughput (QPS):

  • 1 Billion requests / day.

  • Seconds in a day\approx 86,400 (use 100,000 for simple math).

  • Average QPS = 1,000,000,000 / 100,000 = 10,000 QPS.

  • Peak QPS (assume 5x burst) = 50,000 QPS.

• Storage (Memory):

  • We need to store counters for active users in RAM (Redis).

  • Assume 10% of users are active in a specific window (10M users).

  • Per User: Key (User ID \approx 8 bytes) + Value (2 Integers \approx 8 bytes) + Redis Overhead \approx 50 bytes. Total \approx 66 bytes.

  • Total Memory = 10,000,000 * 66 bytes \approx660 MB.

  • Conclusion: The entire dataset fits easily into the RAM of a single Redis node, though we will shard it for CPU throughput.

5. API design

The rate limiter is internal middleware, but we can define the communication interface.

1. Internal Check Method (RPC/Local Call)

• check_limit(key, limit, window_size)
  • key: String (e.g., "user_123:login")
  • limit: Integer (e.g., 5)
  • window_size: Integer (e.g., 60 seconds)
• Returns:
  • is_allowed: Boolean
  • remaining: Integer
  • retry_after: Integer (seconds)

2. Client Response (HTTP Headers)

When the Gateway responds to the client:

• X-Ratelimit-Limit: 100
• X-Ratelimit-Remaining: 0
• X-Ratelimit-Retry-After: 30 (Only if blocked)

3. Admin Configuration API

• POST /rules
  • Body: { "endpoint": "/api/v1/payment", "limit": 10, "window": "60s" }

6. High-level architecture

We will place the Rate Limiter logic inside the API Gateway. This ensures traffic is rejected at the edge of our infrastructure, saving resources for backend services.

1. Client: Sends an HTTP request.

2. Load Balancer: Distributes traffic to API Gateway instances.

3. API Gateway:

   • Serves as the entry point.
   • Runs the Rate Limiter Middleware.
   • The middleware calculates the user's key and asks Redis: "Can this user proceed?"
   • If Yes: Forwards request to Backend Service.
   • If No: Returns HTTP 429.

4. Redis Cluster: Stores the request counters in memory. We use Redis for its speed and atomic operations (Lua scripts).

5. Backend Services: The actual application servers (e.g., Order Service).

7. Data model

We will use Redis (Key-Value Store) because we need extremely fast writes and atomic counters.

Algorithm: Sliding Window Counter (Weighted Average)

We choose this over "Fixed Window" (which has edge-case spikes) and "Sliding Log" (which consumes too much memory).

• Logic: We track the count for the Current Window (e.g., current minute) and the Previous Window.
• Formula: Estimated = (Previous_Count * Overlap_Percentage) + Current_Count

Redis Schema:

We use a Redis Hash to store both counters for a user.

• Key: limiter:{user_id}:{endpoint} (e.g., limiter:user_55:login)
• Value (Hash):
  • current_ts: timestamp (e.g., 10:01)
  • current_count: integer (e.g., 15)
  • previous_count: integer (e.g., 40)

8. Core flows end to end

We will focus on the most critical path: The Request Evaluation Flow. This flow determines whether a user’s API request is accepted or rejected.

Since this is a distributed system, we must ensure the check is atomic (happens all at once) to prevent race conditions where two users read the same counter simultaneously.

Flow 1: The "Check-and-Act" Cycle (Happy Path)

This process happens for every single incoming request. It must complete in under 10 milliseconds.

1. Request Interception

• Action: A client sends a GET /api/orders request.
• Gateway: The API Gateway (middleware) intercepts the request before it reaches the backend Order Service.
• Identification: The middleware extracts the User_ID (e.g., user_55) from the JWT token or API Key.

2. Constructing the Keys

• The middleware identifies the current time window and the previous window.
• Example:
  • Current Time: 10:01:15 (15 seconds into the minute).
  • Current Key: limiter:user_55:10:01
  • Previous Key: limiter:user_55:10:00

3. Atomic Check (The Lua Script)

• The Gateway sends a single Lua script to the Redis Cluster.
• Why Lua? Redis executes Lua scripts atomically. No other request can interrupt the script while it runs. This performs a "Get, Calculate, and Set" operation in one go, preventing race conditions.
• The Script Logic:
  • Fetch: It retrieves the values for Current Key and Previous Key.
  • Calculate: It runs the "Weighted Average" formula (detailed below).
  • Decision:
    • If result \le Limit: It increments the Current Key and returns ALLOW.
    • If result > Limit: It returns BLOCK without incrementing.

4. Forwarding the Request

• Gateway: Since Redis returned ALLOW, the Gateway forwards the HTTP request to the backend Order Service.
• Response: The Order Service processes the data and returns it to the client. The user perceives no delay.

9. Caching and read performance

Redis is fast, but 50k QPS is a lot of network calls. We can optimize.

• Redis as Primary Store: It holds the definitive "truth" for counters.
• Local Memory "Short Circuit":
  • If a user is blocked by Redis, the API Gateway instance caches that "BLOCKED" decision in its own local RAM for a short time (e.g., 1 second).
  • Benefit: If a bot scripts 1,000 requests/sec, the first one hits Redis. The next 999 are rejected instantly by the Gateway's local memory. This saves network bandwidth and protects Redis.
• Rule Caching:
  • Limit rules (e.g., "login = 5 req/min") are stored in a database but cached in the Gateway's memory. We update this cache every few minutes.

10. Storage, indexing and media

• Storage: Redis Cluster.
• Data Retention (TTL):
  • We set a TTL (Time To Live) on the Redis keys equal to Window_Size * 2.
  • If a user stops sending requests, their counters expire and are deleted automatically. This keeps memory usage low.
• Persistence:
  • We can disable Redis disk persistence (RDB/AOF) or make it very infrequent.
  • Trade-off: If Redis crashes, we lose the counters. Users get a "limit reset." This is an acceptable risk for a rate limiter in exchange for maximum write performance.

11. Scaling strategies

• Sharding (Partitioning):
  • A single Redis node can handle ~50k-80k ops/sec. We need to handle peaks and future growth.
  • Strategy: Shard by User ID.
  • Shard = Hash(User_ID) % Number_Of_Nodes.
  • This distributes the counters evenly across the cluster. If we need more throughput, we simply add more Redis nodes.
• Stateless Gateways:
  • The API Gateway layer is stateless. We can auto-scale the number of Gateway instances based on CPU load to handle increased traffic volume.

12. Reliability, failure handling and backpressure

• Fail-Open Strategy:
  • If Redis is down, unreachable, or times out (> 10ms), the Gateway must allow the request.
  • Reason: The rate limiter is a helper tool. It should never be the cause of a total system outage. We prefer to let a few spammers through than to block all legitimate revenue-generating traffic.
• Circuit Breakers:
  • If Redis errors spike, the Gateway opens a circuit breaker and bypasses the rate check entirely for 30 seconds, defaulting to "Allow" to let Redis recover.
• Jitter:
  • When many users are blocked, they might retry at the exact same second. We add random "jitter" to the Retry-After header (e.g., 30s, 31s, 29s) to smooth out the retry traffic.

13. Security, privacy and abuse

• Identity:
  • Prefer User ID (Authenticated) over IP. IPs are unreliable (NAT, shared WiFi).
  • Use IP limiting only as a fallback for unauthenticated endpoints (like Sign Up or Login).
• Security of Headers:
  • For public-facing or sensitive endpoints, consider hiding the X-Ratelimit-Remaining header so attackers cannot easily reverse-engineer the exact detection thresholds.
• Key Exhaustion:
  • Attackers might try to create millions of random keys. The TTL on Redis keys prevents memory from filling up with garbage data.

14. Bottlenecks and next steps

• Bottleneck: Network Latency.
  • Calling Redis for every request adds latency.
  • Next Step: Implement Synchronization Batching. Gateways count requests locally for 5 seconds and then send a single INCRBY command to Redis. This drastically reduces Redis load but makes the limiter "eventually consistent" (less precise).
• Bottleneck: Hot Keys.
  • A celebrity user or major integration might overwhelm a single Redis shard.
  • Next Step: specific "Hot User" logic where their limits are cached and enforced entirely in the Gateway's local memory, bypassing Redis.

The complete picture

Every diagram above shows one part of the system. This one shows all of them at once, with the caches, the queues, the datastores and the scaling strategy for each path marked on it. If you remember one image from this lesson, make it this one.

Summary

Say this first. A rate limiter sits on the hot path of every request in the system, so it has two jobs that pull against each other: be accurate, and be almost free. The design resolves that by doing the real check once in Redis and then remembering the answer locally, and by choosing to let traffic through when it is unsure.

The decisions that mattered

The numbers that forced them

What breaks first

1. Network latency to Redis. One round trip per request is fine at this volume and becomes the bottleneck well before Redis itself does. Batching counts locally and syncing periodically trades accuracy for throughput.
2. A hot key. One very large customer concentrates on a single shard. Enforce their limit entirely in gateway memory instead.
3. Key exhaustion. An attacker generating random keys fills memory. The TTL is what prevents this, which is why it is not optional.

If the interviewer pushes

• "Why not a token bucket?" You can, and it handles bursts more gracefully. The sliding window counter was chosen for accuracy near the limit with only two integers of state. Either is defensible if you say why.
• "Fail open or fail closed?" Open for a public API, because availability is the product. Closed for something like a login endpoint, where the abuse you are stopping is worse than the outage.
• "How do you keep the check atomic?" A Lua script runs to completion inside Redis with nothing interleaved, so get, calculate and set become one operation.
• "Where does this design leak?" During the local block cache window and during any Redis outage, the limit is approximate. That is a deliberate trade, not an oversight.