Bird
Raised Fist0

Design an API Rate Limiter - Algorithms, Distributed Counter, Edge Enforcement

HLDmediumInterview freq: high
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🎯
Design an API Rate Limiter - Algorithms, Distributed Counter, Edge Enforcement
45 min · senior
senior

You are designing an API rate limiter for a startup with 50 million daily active users (DAU). The system must enforce per-user and per-API key rate limits with P99 latency under 200ms. The rate limiter must support distributed counters across multiple data centers, ensure strong consistency for quota enforcement, and encrypt all data in transit and at rest. Edge enforcement is required to reduce backend load and prevent abuse closer to the client. The system should handle bursty traffic and provide real-time metrics for monitoring.

Constraints
  • P99 latency for rate limit checks must be under 200ms
  • All data must be encrypted in transit and at rest
  • Distributed counters must maintain strong consistency across multiple data centers
  • Edge enforcement required to reduce backend load and mitigate abuse
  • System must handle bursty traffic spikes gracefully
📋
Guided Steps
1/5
Step 1
Choose the Rate Limiting Algorithm
Which rate limiting algorithm will you use to enforce quotas accurately and efficiently at scale?
💡 Hint
Consider algorithms that support distributed counters and burst handling, such as token bucket or leaky bucket.
Key Decision
Use a distributed token bucket algorithm implemented with Redis Cluster's atomic Lua scripts to support burst handling and precise quota consumption.
Interviewer Expectation
Mid-level: Names token bucket algorithm. Senior: Explains why token bucket supports bursts better than fixed window counters and how Redis Lua scripts ensure atomicity under concurrency.
⚠️Common Wrong Answer
Using fixed window counters stored in a relational database, which causes inaccurate enforcement during bursts and high latency under load.
Step 2
Design Distributed Counters for Quota Tracking
How will you implement distributed counters that maintain strong consistency and low latency across multiple data centers?
💡 Hint
Think about data stores that support atomic increments and replication with strong consistency guarantees.
Key Decision
Use Redis Cluster with CRDT-based counters for eventual consistency or Redis Enterprise with active-active geo-replication for strong consistency and sub-200ms latency.
Interviewer Expectation
Mid-level: Suggests Redis for counters. Senior: Explains trade-offs between Redis CRDT eventual consistency and Redis Enterprise active-active replication for strong consistency and latency SLA.
⚠️Common Wrong Answer
Using Cassandra counters which have eventual consistency and can cause quota overshoot under concurrent increments.
Step 3
Implement Edge Enforcement
Where and how will you enforce rate limits at the edge to reduce backend load and latency?
💡 Hint
Consider CDN or API gateway integration with local caching and rate limiting capabilities.
Key Decision
Deploy Envoy proxy with local rate limiting filter at edge PoPs, backed by Redis for quota state caching and periodic sync with central counters.
Interviewer Expectation
Mid-level: Mentions API gateway rate limiting. Senior: Details Envoy local rate limiting filter, cache invalidation strategy, and fallback to central counters on cache miss.
⚠️Common Wrong Answer
Enforcing rate limits only at backend services, causing high backend load and increased latency.
Step 4
Design API Endpoints for Rate Limit Checks and Metrics
What are the core API endpoints your rate limiter exposes for clients and services?
💡 Hint
Think about endpoints for quota check & consume, quota sync, and metrics retrieval.
Key Decision
Expose three REST endpoints: POST /rate_limit/check_consume for atomic quota check and consume; GET /rate_limit/status for current quota state; GET /rate_limit/metrics for usage statistics, all secured with TLS 1.3 and JWT authentication.
Interviewer Expectation
Mid-level: Lists endpoints without security details. Senior: Explains atomic check-consume semantics, encryption in transit, and authentication mechanisms.
⚠️Common Wrong Answer
Using separate check and consume endpoints causing race conditions and quota overshoot.
Step 5
Ensure Data Encryption and Security
How will you ensure all data is encrypted in transit and at rest, and that only authorized clients can access the rate limiter APIs?
💡 Hint
Consider TLS, encryption at rest, and token-based authentication.
Key Decision
Use TLS 1.3 for all client-server and inter-service communication, AES-256 encryption for data at rest in Redis and logs, and JWT tokens with OAuth 2.0 for client authentication and authorization.
Interviewer Expectation
Mid-level: Mentions TLS and some auth. Senior: Details TLS version, encryption standards, key management, and OAuth scopes for fine-grained access control.
⚠️Common Wrong Answer
Omitting encryption at rest or using basic API keys without token expiration, risking data exposure and unauthorized access.
🔌
API Design Challenge
Sketch 3 core endpoints for the API Rate Limiter system that clients and services will use.
Hints
  • How does the client send a request to check and consume quota?
  • How does the client or service sync or refresh rate limit state?
  • How does the system expose metrics or allow clients to acknowledge quota usage?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Use of a rate limiting algorithm that supports burst handling and atomic quota consumption
  • Distributed counters with strong consistency and low latency across multiple data centers
  • Edge enforcement to reduce backend load and latency
  • Secure API endpoints with encryption and authentication
  • P99 latency under 200ms for rate limit checks
Good to Have - 30%
  • Periodic synchronization between edge caches and central counters
  • Sliding window implementation for smoother quota enforcement
  • Real-time monitoring and alerting integration
Bonus - 10%
  • Detailed trade-off analysis between eventual and strong consistency for counters
  • Use of Envoy local rate limiting filter specifics
  • Encryption key management strategy
Anti-patterns to Avoid
Using fixed window counters in a relational database causing inaccurate quota enforcement and high latency under load, leading to quota overshoot during bursts and system performance degradation.
Relying solely on eventual consistency counters like Cassandra causing quota overshoot under concurrency due to delayed counter synchronization.
Enforcing rate limits only at backend services leading to backend overload and increased latency, which reduces system scalability and user experience.
Separate check and consume endpoints causing race conditions and quota overshoot because atomicity is not guaranteed between the two calls.
✅
Model Answer
▼ Reveal

The system uses a distributed token bucket algorithm implemented with Redis Cluster Lua scripts to enforce rate limits with burst handling and atomic quota consumption. Distributed counters are managed using Redis Enterprise active-active geo-replication to ensure strong consistency and meet the sub-200ms P99 latency SLA. Edge enforcement is implemented via Envoy proxy local rate limiting filters deployed at edge PoPs, backed by Redis caches with periodic synchronization to central counters. The API exposes three secure REST endpoints for atomic quota check and consume, quota status retrieval, and metrics access, all protected with TLS 1.3 and JWT OAuth 2.0 authentication. Data encryption at rest uses AES-256. Monitoring integrates Prometheus and Grafana for real-time visibility.

Key Decisions
  • Use Redis Cluster Lua scripts to implement a distributed token bucket algorithm supporting burst handling and atomic quota consumption.
  • Choose Redis Enterprise active-active geo-replication to maintain strong consistency of counters across multiple data centers with sub-200ms P99 latency.
  • Deploy Envoy proxy local rate limiting filters at edge PoPs to enforce rate limits close to clients, reducing backend load and latency.
  • Expose three REST endpoints secured with TLS 1.3 and JWT OAuth 2.0: POST /rate_limit/check_consume for atomic quota check and consume, GET /rate_limit/status for quota state, and GET /rate_limit/metrics for usage statistics.
  • Encrypt all data in transit using TLS 1.3 and at rest using AES-256 encryption in Redis and logs.
  • Implement periodic synchronization between edge caches and central counters to maintain quota accuracy and handle cache misses gracefully.
  • Integrate monitoring and alerting with Prometheus and Grafana for real-time visibility into rate limiter performance and anomalies.
  • Distributed token bucket algorithm implemented with Redis Cluster Lua scripts for atomic quota updates and burst handling
  • Redis Enterprise active-active geo-replication for strong consistency of distributed counters across data centers with sub-200ms P99 latency
  • Envoy proxy local rate limiting filter deployed at edge PoPs to enforce limits close to clients and reduce backend load
  • REST API endpoints: POST /rate_limit/check_consume, GET /rate_limit/status, GET /rate_limit/metrics secured with TLS 1.3 and JWT OAuth 2.0
  • TLS 1.3 for all data in transit and AES-256 encryption for data at rest in Redis and logs to meet security constraints
  • Periodic sync between edge caches and central counters to maintain quota accuracy and handle cache misses gracefully
  • Use of Redis TTL and Lua scripts to implement sliding window rate limiting for smooth quota enforcement under bursty traffic
  • Monitoring and alerting integrated with Prometheus and Grafana for real-time visibility into rate limiter performance and anomalies

Practice

(1/5)
1. A system requires 99.99% availability for a critical service that must tolerate a single data center failure without downtime. Which component is most appropriate to achieve this?
easy
A. Deploy active-active multi-region clusters with automatic failover
B. Rely on local in-memory caches to serve requests during outages
C. Use a single-region relational database with synchronous replication
D. Use a single data center with redundant power and network equipment

Solution

  1. Step 1: Understand availability target and failure domain

    99.99% availability requires tolerating entire data center failure without downtime, which single-region setups cannot guarantee.

  2. Step 2: Evaluate options for multi-region failover

    Active-active multi-region clusters with automatic failover provide seamless continuity, unlike local caches or single-region redundancy.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Multi-region active-active clusters -> tolerate data center failure [check]
Hint: Multi-region active-active -> survive data center failure [check]
Common Mistakes:
2. In the newsfeed system, at Step 4 the Delivery Worker reads a fan-out event from Kafka and attempts to deliver it to followers. What happens if a follower's device is offline at this step?
easy
A. Delivery Worker marks the message as sent but not delivered, queues for retry later
B. Delivery Worker drops the message to avoid blocking other deliveries
C. Delivery Worker retries immediately until the follower is online
D. Delivery Worker pushes the message to the follower's device cache directly

Solution

  1. Step 1: Trace Delivery Worker behavior at Step 4

    The Delivery Worker reads fan-out events from Kafka and attempts delivery. If the follower is offline, immediate retry (A) would block and reduce throughput. Dropping messages (C) causes data loss. Pushing directly to device cache (D) is impossible if offline.

  2. Step 2: Understand retry mechanism

    The system marks the message as sent but not delivered, queues it for retry later when the follower reconnects, ensuring eventual delivery without blocking.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Offline followers cause queued retries, not immediate blocking [check]
Hint: Offline followers cause queued retries, not immediate blocking [check]
Common Mistakes:
3. In the request flow of a Redis-based centralized rate limiter, at Step 3 the API server performs an atomic INCR on the Redis key. What is the state of the counter immediately after this step if the limit is exceeded?
easy
A. The counter is reset to zero and the request is allowed
B. The counter value is incremented but the request is rejected
C. The counter value remains unchanged and the request is queued
D. The counter is decremented to rollback the increment and the request is allowed

Solution

  1. Step 1: Trace the atomic INCR operation

    At Step 3, the Redis INCR command increments the counter regardless of limit.

  2. Step 2: Check limit enforcement logic

    If the incremented counter exceeds the limit, the request is rejected but the counter remains incremented to reflect the attempt.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Counter increments atomically; request rejected if limit exceeded [check]
Hint: Counter increments first, then limit check rejects request [check]
Common Mistakes:
4. 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:
5. At 10x scale, which component in the Ticket Server pattern is most likely to become the bottleneck first, and why?
hard
A. Ticket Server, because it handles all block allocations and cannot be sharded easily
B. Clients, because local ID block exhaustion causes frequent server requests
C. Network, because increased traffic saturates bandwidth between clients and server
D. Database storing allocated blocks, because it cannot handle concurrent writes at scale

Solution

  1. Step 1: Identify centralization bottleneck

    The Ticket Server centrally allocates ID blocks and maintains allocation state, limiting horizontal scaling.

  2. Step 2: Compare other components

    Clients scale horizontally; network scales with infrastructure; database load is less critical if Ticket Server caches state.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Ticket Server centralization -> first bottleneck at 10x scale [check]
Hint: Central Ticket Server state limits horizontal scaling first [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