Bird
Raised Fist0

Why Rate Limiting Exists and What Happens to Systems Without It

HLDmediumInterview freq: common
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🎯
Why Rate Limiting Exists and What Happens to Systems Without It
45 min · senior
senior

You are designing a rate limiting system for a 50 million daily active user (DAU) social media platform that experiences unpredictable traffic spikes. The system must protect backend services from overload, ensure fair usage, and maintain a P99 latency under 200ms. Data must be encrypted in transit and at rest. Offline delivery of notifications is required for users who are temporarily unreachable.

Constraints
  • Support 50M DAU with peak request rates up to 1 million requests per second
  • P99 request latency must be under 200ms including rate limiting checks
  • All data in transit and at rest must be encrypted using TLS and AES-256
  • Offline delivery of notifications with guaranteed eventual consistency
  • Rate limits must be configurable per user and per API endpoint
  • System must gracefully degrade under overload without cascading failures
📋
Guided Steps
1/5
Step 1
Define the core rate limiting strategy
What rate limiting algorithm and data store would you choose to enforce limits at 1M RPS with P99 < 200ms?
💡 Hint
Consider algorithms with O(1) complexity and stores optimized for high write throughput and low latency.
Key Decision
Use Redis with Lua scripts implementing a token bucket algorithm - Redis supports atomic increments with sub-millisecond latency and Lua scripts ensure atomicity under concurrency.
Interviewer Expectation
Mid: Names Redis and token bucket. Senior: Explains why token bucket fits bursty traffic and why Redis outperforms alternatives like Memcached for atomic counters.
⚠️Common Wrong Answer
Using Memcached for counters - lacks atomic increment and can cause race conditions leading to inaccurate rate limiting.
Step 2
Design for scalability and fault tolerance
How will you scale the rate limiting system horizontally and handle Redis failures without impacting client experience?
💡 Hint
Think about sharding keys and fallback mechanisms to avoid single points of failure.
Key Decision
Shard Redis keys by user_id using Redis Cluster to distribute load; implement a local in-memory fallback cache with leaky bucket approximation for degraded mode.
Interviewer Expectation
Mid: Mentions Redis Cluster for sharding. Senior: Details user_id as shard key to ensure even load and explains fallback cache trade-offs to maintain availability during Redis outages.
⚠️Common Wrong Answer
Single Redis instance - becomes a bottleneck and single point of failure causing system-wide outages.
Step 3
Handle encryption and security constraints
How do you ensure all rate limiting data and communication comply with encryption requirements without adding significant latency?
💡 Hint
Consider TLS termination points and encryption at rest mechanisms native to your data stores.
Key Decision
Terminate TLS at load balancers and use Redis with AES-256 encryption at rest enabled; use TLS 1.3 for all client-server and inter-service communication.
Interviewer Expectation
Mid: Mentions TLS for communication. Senior: Explains TLS termination at edge to reduce latency and Redis Enterprise or AWS ElastiCache encryption at rest to meet compliance.
⚠️Common Wrong Answer
Encrypting data at application layer only - adds CPU overhead and inconsistent encryption coverage.
Step 4
Design offline delivery and eventual consistency
How will the system handle offline users and ensure rate limits are eventually consistent when users reconnect?
💡 Hint
Think about durable queues and reconciliation mechanisms for delayed requests.
Key Decision
Use Apache Kafka as a durable event log to queue rate limit requests and updates; backend workers consume and reconcile usage asynchronously to maintain eventual consistency.
Interviewer Expectation
Mid: Names Kafka for durability. Senior: Explains Kafka partitioning by user_id to preserve ordering and how asynchronous reconciliation prevents blocking live traffic.
⚠️Common Wrong Answer
Synchronous blocking on offline users - causes increased latency and request timeouts.
Step 5
Define API endpoints for rate limiting
Sketch 3 core API endpoints for clients and backend services to interact with the rate limiting system.
💡 Hint
How does a client request permission to perform an action? How does the backend report usage or update limits? How does the client query current quota or rate limit status?
Key Decision
Expose REST endpoints: POST /rate_limit/check to request permission, POST /rate_limit/report to update usage, GET /rate_limit/status to query current quota; all endpoints secured with OAuth2 tokens.
Interviewer Expectation
Mid: Defines basic endpoints. Senior: Explains idempotency, rate limit headers in responses, and OAuth2 scopes for fine-grained access control.
⚠️Common Wrong Answer
Single endpoint for all operations - leads to complex client logic and harder scaling.
🔌
API Design Challenge
Sketch 3 core API endpoints for the rate limiting system that clients and backend services will use.
Hints
  • How does a client request permission to perform an action?
  • How does the backend service report usage or update limits?
  • How does the system expose current rate limit status or quota to clients?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Use of Redis with atomic Lua scripts for rate limiting counters
  • Sharding strategy for Redis to handle 1M RPS load
  • Encryption in transit and at rest with minimal latency impact
  • Offline delivery mechanism using durable queues like Kafka
  • Clear API design separating check, report, and status endpoints
Good to Have - 30%
  • Fallback cache for degraded mode during Redis failures
  • OAuth2 scopes for fine-grained API access control
  • Partitioning Kafka topics by user_id for ordering guarantees
Bonus - 10%
  • Explanation of token bucket advantages over fixed window counters
  • Discussion of graceful degradation strategies under overload
Anti-patterns to Avoid
Using Memcached for counters - causes race conditions due to lack of atomic increments, leading to inaccurate rate limiting and potential overload.
Single Redis instance without sharding - creates a bottleneck and single point of failure, risking system-wide outages under high load.
Encrypting data only at the application layer - adds CPU overhead and inconsistent encryption coverage, risking compliance violations.
Synchronous blocking on offline users - increases latency and causes request timeouts, degrading user experience.
Combining all rate limiting operations into a single endpoint - leads to complex client logic and harder scaling.
✅
Model Answer
▼ Reveal

This design uses Redis with Lua scripts to implement a token bucket algorithm for atomic, low-latency rate limiting at 1M RPS. Redis Cluster shards keys by user_id to distribute load and avoid hotspots. A local in-memory fallback cache with a leaky bucket approximation maintains availability during Redis outages. TLS 1.3 terminates at load balancers to reduce latency, and AES-256 encryption at rest in Redis meets security requirements. Apache Kafka serves as a durable event log for offline delivery and asynchronous reconciliation, ensuring eventual consistency. The system exposes three REST API endpoints secured with OAuth2 tokens for checking permission, reporting usage, and querying status, supporting configurable rate limits per user and API endpoint.

Key Decisions
  • Use Redis with Lua scripts implementing token bucket algorithm for O(1) latency atomic increments
  • Shard Redis keys by user_id using Redis Cluster to distribute load and avoid hotspots
  • Implement local in-memory fallback cache with leaky bucket approximation to maintain availability during Redis failures
  • Terminate TLS 1.3 at load balancers and enable AES-256 encryption at rest in Redis to meet security and latency constraints
  • Use Apache Kafka partitioned by user_id as a durable event log for offline delivery and asynchronous reconciliation
  • Design REST API with separate endpoints for check (/rate_limit/check), report (/rate_limit/report), and status (/rate_limit/status) operations secured with OAuth2 tokens
  • Redis with Lua scripts for atomic token bucket rate limiting - ensures O(1) latency at 1M RPS
  • Redis Cluster sharded by user_id - distributes load evenly and avoids hotspots
  • Local in-memory fallback cache with leaky bucket approximation - maintains availability during Redis outages
  • TLS 1.3 termination at load balancers and AES-256 encryption at rest in Redis - meets security and latency constraints
  • Apache Kafka as durable event log for offline delivery and asynchronous reconciliation - guarantees eventual consistency
  • REST API endpoints with OAuth2 authentication - clean separation of check, report, and status operations
  • Partition Kafka topics by user_id - preserves ordering and enables scalable consumption
  • Use of token bucket algorithm over fixed window counters - better handles bursty traffic without unfair throttling

Practice

(1/5)
1. A public API needs to support multiple client versions simultaneously without breaking existing integrations. Which versioning strategy best isolates client requests to avoid accidental breaking changes?
easy
A. Use content negotiation with Accept header media types to specify version
B. Use a custom HTTP header like X-API-Version to specify the version
C. Embed the version number in the URL path, e.g., /v1/resource
D. Rely on query parameters like ?version=1 to indicate API version

Solution

  1. Step 1: Identify version isolation requirements

    Embedding version in the URL path clearly separates client requests by version, preventing accidental routing to incompatible handlers.

  2. Step 2: Evaluate alternatives

    Custom headers and content negotiation can be ignored or mishandled by intermediaries or caches, risking breaking changes. Query parameters are less explicit and can cause caching issues.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    URL versioning cleanly isolates versions in routing paths [check]
Hint: URL path versioning isolates clients cleanly [check]
Common Mistakes:
2. A system requires sub-millisecond read latency for session data with frequent updates and ephemeral storage. Which key-value store is most appropriate?
easy
A. Use DynamoDB with on-demand capacity mode for automatic scaling
B. Use DynamoDB with global secondary indexes for fast queries
C. Use a relational database with caching layer for session data
D. Use Redis with in-memory storage and eviction policies

Solution

  1. Step 1: Identify latency and update frequency requirements

    Sub-millisecond latency and frequent updates favor in-memory stores over disk-based ones.

  2. Step 2: Evaluate Redis vs DynamoDB for ephemeral session data

    Redis provides in-memory storage with eviction policies ideal for ephemeral, fast-access data; DynamoDB has higher latency due to disk persistence.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Redis in-memory -> sub-ms latency for frequent updates [check]
Hint: In-memory Redis beats DynamoDB for low-latency ephemeral data [check]
Common Mistakes:
3. Without the Global Traffic Manager component in a multi-CDN setup, what is the most likely failure scenario when one CDN provider becomes unavailable?
medium
A. Origin server detects CDN failure and redirects traffic to healthy CDNs
B. Clients continue sending requests to the failed CDN, causing increased latency and errors
C. User requests automatically failover to the next CDN without delay
D. Edge caches replicate content from other CDNs to cover the outage

Solution

  1. Step 1: Understand role of Global Traffic Manager in failover

    It dynamically routes traffic away from failed CDNs. Without it, failover must be handled elsewhere.

  2. Step 2: Trace failure without Global Traffic Manager

    Origin server may attempt to redirect traffic, but this adds latency and is less dynamic than traffic manager.

  3. Step 3: Eliminate other options

    Automatic client failover (A) requires client intelligence not assumed here. Clients sending to failed CDN (B) is possible but less likely if origin redirects. Edge caches (D) do not replicate across CDNs automatically.

  4. Final Answer:

    Option A -> Option A

  5. Quick Check:

    Without traffic manager, origin server redirects traffic causing latency and partial failover [check]
Hint: No traffic manager -> origin server handles failover with latency penalty [OK]
Common Mistakes:
4. You must design a notification system that requires immediate user feedback on success or failure of each notification. Which communication approach is best suited for this requirement?
medium
A. Use synchronous HTTP calls with client-side timeouts and retries
B. Use fire-and-forget UDP packets for low latency
C. Use batch processing with delayed acknowledgment
D. Use an asynchronous message queue with eventual consistency

Solution

  1. Step 1: Identify requirement for immediate feedback

    Immediate success/failure feedback requires synchronous communication to confirm delivery.

  2. Step 2: Evaluate synchronous HTTP calls

    Synchronous HTTP with timeouts and retries provides immediate response and error handling.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Synchronous calls provide immediate feedback required by the system [check]
Hint: Immediate feedback needs synchronous calls with timeouts [check]
Common Mistakes:
5. At 10x scale, which component in a consistent hashing system with virtual nodes is most likely to fail first and why?
hard
A. The physical nodes, because they cannot handle increased key storage and request load
B. The token metadata service, due to increased complexity managing many virtual nodes and frequent updates
C. The network, because consistent hashing increases network chatter exponentially with scale
D. The client-side hash function, as hashing large key sets becomes computationally infeasible

Solution

  1. Step 1: Identify scaling bottlenecks

    Physical nodes scale horizontally; network and hash function scale well with optimizations.

  2. Step 2: Analyze token metadata service

    Managing many virtual nodes and frequent node changes increases metadata complexity and update frequency, causing bottlenecks.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Token metadata service complexity grows fastest, causing first failure [check]
Hint: Token metadata complexity grows fastest 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