Bird
Raised Fist0

Distributed Rate Limiting - Redis-Based Centralized Counter Approach

HLDmediumInterview freq: common
Choose your preparation mode4 modes available
🏗️
Distributed Rate Limiting - Redis-Based Centralized Counter Approach
Centralized Redis counters for distributed rate limiting with TTL-based expiry
mediumRate LimitingFreq: common
Prerequisites:Caching BasicsKey-Value Stores
⚙️
Functional Requirements
  • Enforce per-user rate limits (e.g., 100 requests per minute) across distributed clients
  • Support multiple rate limiting policies (per API key, per IP, per user)
  • Provide real-time feedback on remaining quota in API responses
  • Allow dynamic updates to rate limit thresholds without downtime
  • Support burst traffic handling with smooth degradation
  • Expose APIs for querying current usage and resetting counters
📊
Non-Functional Requirements
  • Handle 2 billion daily active users generating ~40 requests per user per day
  • Achieve 99.99% availability with failover and minimal downtime
  • Ensure 100ms P99 latency for rate limit checks under peak load
  • Scale to 925K write QPS and 1.85M read QPS during peak hours
  • Data consistency within 1 second for counters to avoid over-limit errors
❓
Clarifying Questions to Ask
  • What is the exact rate limit policy granularity? Per user, IP, or API key?
  • Are rate limits fixed or do they vary dynamically per user or tier?
  • Is eventual consistency acceptable or is strong consistency required for counters?
  • What is the expected burst traffic pattern and tolerance for over-limit errors?
  • Should the system support distributed denial-of-service (DDoS) mitigation?
  • What is the retention period for rate limit counters and logs?
Out of Scope
✗ Designing client-side rate limiting or SDKs
✗ Handling authentication or authorization logic
✗ Long-term analytics or historical usage reporting
✗ Multi-region geo-distributed consistency guarantees
📌
Assumptions
  • 2 billion daily active users (DAU)
  • Each user generates 40 requests per day on average
  • Average request size is 100 bytes
  • Retention period for counters is 1 day
⚡
QPS Calculation
write qps2B × 40 / 86400 ≈ 925,926 writes/sec
peak write qpsAssuming 2× peak factor: 925,926 × 2 ≈ 1,851,852 writes/sec
read qpsEach request requires 2 reads (check + quota fetch): 925,926 × 2 ≈ 1,851,852 reads/sec
💾
Storage Estimate
daily storage bytes2B users × 40 req × 100 bytes = 8 TB/day
retention days1
total storage bytes8 TB × 1 = 8 TB
with replication8 TB × 2 (Redis master-slave) = 16 TB
🖥️
Server Estimate
redis cluster nodesAssuming 50K writes/sec per Redis node, need 1,851,852 / 50,000 ≈ 38 nodes
api serversAssuming each API server handles 5K QPS, need 1,851,852 / 5,000 ≈ 370 servers
🏗️
Architecture Diagram
Architecture Diagram
          +-------------+
          | API Servers |
          +------+------+
                 |
                 | Check Rate Limit Request
                 v
          +------+-------+
          |  Redis Cluster|
          +------+-------+
                 |
                 | Replication
                 v
          +------+-------+
          | Redis Replica|
          +--------------+
🧩
Components
API Servers
Receive client requests, query Redis for rate limit counters, enforce limits
Why thisStateless horizontally scalable servers allow easy scaling to handle 1.85M QPS reads/writes using technologies like NGINX or Envoy
Why notMonolithic servers would bottleneck and complicate scaling at 2B DAU, unlike microservices with container orchestration like Kubernetes
Redis Cluster
Centralized counters stored with TTL for rate limiting enforcement
Why thisRedis supports atomic INCR and EXPIRE commands with sub-millisecond latency and native TTL expiry, ideal for real-time counters
Why notCassandra has higher write latency and no native TTL expiry, complicating stale data cleanup and increasing complexity
Redis Replica
Serve read requests to reduce load on master nodes and improve read latency
Why thisRedis replicas provide eventual consistency with asynchronous replication, offloading read QPS and improving availability
Why notUsing only masters would create read bottlenecks and increase latency, reducing system responsiveness
Load Balancer
Distribute incoming API requests evenly across API servers
Why thisLayer 7 load balancers (e.g., Envoy, HAProxy) provide health checks and routing for high availability and fault tolerance
Why notDNS round-robin lacks health awareness and fine-grained routing, leading to uneven load and potential downtime
Monitoring & Alerting
Track Redis latency, error rates, and API server health to maintain 99.99% uptime
Why thisPrometheus + Grafana enable real-time metrics and alerting for operational excellence and proactive issue detection
Why notBasic logs lack real-time visibility and proactive alerting capabilities, delaying incident response
🔄
Data Flow
1
Client → API Server
Send request with user identifier and API key
API server extracts user ID and rate limit key
2
API Server → Redis Cluster
Atomic INCR command on user-specific counter key with TTL
TTL ensures counters reset after rate limit window
3
Redis Cluster → API Server
Return current counter value
API server compares counter to threshold
4
API Server → Client
Allow or reject request based on counter
Include remaining quota in response headers
5
Redis Cluster → Redis Replica
Asynchronous replication of counters
Replicas serve read-heavy queries and improve availability
🗄️
rate_limit_counters
PK: user_id
user_id STRINGtime_bucket STRINGcounter INTttl TIMESTAMP
Stores per-user counters bucketed by time window for rate limiting
🗄️
rate_limit_policies
PK: policy_id
policy_id STRINGuser_tier STRINGmax_requests INTwindow_seconds INT
Defines rate limit policies per user tier or API key
🔌
CheckRateLimit
Request
{
  "user_id": "string",
  "api_key": "string"
}
Response
{
  "allowed": "boolean",
  "remaining_quota": "int",
  "reset_time": "timestamp"
}
Checks if the user can make a request and returns remaining quota
🔌
ResetCounter
Request
{
  "user_id": "string",
  "api_key": "string"
}
Response
{
  "success": "boolean"
}
Resets the rate limit counter for a user or API key
🔌
GetUsage
Request
{
  "user_id": "string",
  "api_key": "string"
}
Response
{
  "current_count": "int",
  "window_start": "timestamp",
  "window_end": "timestamp"
}
Returns current usage stats for the user or API key

Practice

(1/5)
1. A SaaS platform must ensure strict data isolation between tenants while allowing shared infrastructure. Which component best enforces tenant data isolation at the storage layer?
easy
A. Use a single shared database schema with tenant_id column filtering in application code
B. Use separate database instances per tenant with network-level access controls
C. Use a multi-tenant database with row-level security policies enforced by the DBMS
D. Use a caching layer to segregate tenant data in memory for faster isolation

Solution

  1. Step 1: Understand tenant isolation requirements

    Strict isolation requires preventing any data leakage between tenants, which network-level controls and separate DB instances provide.
  2. Step 2: Evaluate options for isolation guarantees

    Use a single shared database schema with tenant_id column filtering in application code relies on application filtering, prone to bugs; Use a multi-tenant database with row-level security policies enforced by the DBMS depends on DBMS features that may be complex and less secure; Use a caching layer to segregate tenant data in memory for faster isolation only caches data and doesn't guarantee persistent isolation.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Separate DB instances + network controls -> strongest tenant isolation [check]
Hint: Separate DB instances isolate tenants physically [check]
Common Mistakes:
2. In the order matching flow, at step 5 the Matching Engine receives a new buy order for stock XYZ. What state does the Matching Engine hold immediately after processing this order if no matching sell orders exist?
easy
A. The order is marked as matched and removed from the order book
B. The order is added to the buy side of the order book and marked as open
C. The order is rejected due to lack of matching sell orders
D. The order is forwarded to the Market Data Feed before being stored

Solution

  1. Step 1: Trace Matching Engine behavior at step 5

    When no matching sell orders exist, the buy order is added to the order book's buy side and marked as open, waiting for future matches.
  2. Step 2: Eliminate other options

    The order is marked as matched and removed from the order book is wrong because no match occurred; The order is rejected due to lack of matching sell orders is wrong because orders are not rejected for no matches; The order is forwarded to the Market Data Feed before being stored is wrong because Market Data Feed only publishes after matching or order book update.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Unmatched order -> added to order book as open [check]
Hint: Unmatched orders stay open in order book [check]
Common Mistakes:
3. If the Layer 7 load balancer's HTTP header inspection module fails, what is the most likely failure mode for incoming requests?
medium
A. Requests are forwarded blindly to a default backend without routing based on URL
B. The load balancer drops all TCP connections silently without response
C. The load balancer falls back to Layer 4 forwarding, preserving source IP but ignoring HTTP routing
D. The load balancer encrypts requests incorrectly causing backend decryption errors

Solution

  1. Step 1: Understand failure impact on Layer 7 inspection

    If HTTP header inspection fails, the load balancer may fallback to Layer 4 forwarding to maintain availability.
  2. Step 2: Eliminate options inconsistent with graceful degradation

    Dropping all connections (B) is unlikely; forwarding blindly to default backend (A) loses load distribution; encryption errors (D) unrelated.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Layer 7 failure -> fallback to Layer 4 forwarding without HTTP routing [check]
Hint: Layer 7 fail -> fallback to Layer 4 forwarding [check]
Common Mistakes:
4. At 10x scale, which component in the multi-tenant SaaS platform is most likely to fail first, and why?
hard
A. Feature Flag Service cache, because stale flag data causes widespread inconsistent behavior
B. Billing database, due to write amplification from synchronous updates per tenant request
C. Tenant Metadata Service, as it becomes a centralized bottleneck for tenant context lookups
D. API Gateway, because it maintains stateful WebSocket connections that cannot be easily sharded

Solution

  1. Step 1: Analyze scaling bottlenecks

    Billing DB (A) can be scaled with sharding; Tenant Metadata (C) can be cached; API Gateway (D) handles stateless HTTP mostly.
  2. Step 2: Evaluate Feature Flag Service cache at scale

    Cache invalidation and stale data grow exponentially, causing inconsistent feature exposure and client errors.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Feature flag cache stale -> inconsistent behavior at scale [check]
Hint: Feature flag cache stale -> first scale failure [check]
Common Mistakes:
5. At 10x scale, which component in your design explanation is most likely to fail first due to stateful connection bottlenecks, and why?
hard
A. Stateful WebSocket servers because connections are bound to server memory and cannot be easily resharded
B. Stateless API servers because CPU usage spikes with more requests
C. Load balancers because they cannot handle increased DNS queries
D. Databases because they run out of disk space first

Solution

  1. Step 1: Identify stateful components at scale

    WebSocket servers maintain persistent connections bound to server memory, limiting horizontal scaling.
  2. Step 2: Compare with stateless components

    Stateless API servers and load balancers scale horizontally more easily; databases fail later due to storage.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Stateful WebSocket servers bottleneck first due to connection affinity [check]
Hint: Stateful WebSocket servers bottleneck first at scale [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard