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
Design a scalable, distributed API rate limiter with edge enforcement using token bucket and Redis
mediumInfrastructure and Platform SystemsFreq: high
Prerequisites:Token Bucket AlgorithmRedisDistributed Systems BasicsCaching and TTL
⚙️
Functional Requirements
  • Limit API calls per user or API key using token bucket algorithm
  • Support multiple rate limiting policies (per user, per IP, per API key)
  • Enforce limits at edge nodes to reduce backend load
  • Provide real-time feedback on rate limit status (remaining tokens, reset time)
  • Allow dynamic configuration of rate limits without downtime
  • Support distributed counters with strong consistency or eventual consistency trade-offs
📊
Non-Functional Requirements
  • Handle 2 billion daily active users (DAU)
  • Support peak write QPS of approximately 925K (2B × 40 / 86400 ≈ 925,926)
  • Ensure 99.99% availability SLA for rate limiting service
  • Maintain 100ms P99 latency for rate limit checks at edge
  • Scale horizontally with minimal coordination overhead
❓
Clarifying Questions to Ask
  • What is the granularity of rate limiting? Per user, per API key, or per IP?
  • Are rate limits fixed or do they vary dynamically per user or plan?
  • Is strict consistency required for counters or is eventual consistency acceptable?
  • Where are the edge enforcement points located geographically?
  • What is the expected burst size and refill rate for token buckets?
  • Should the system support distributed denial-of-service (DDoS) mitigation?
Out of Scope
✗ Authentication and authorization mechanisms
✗ Detailed billing or quota charging systems
✗ API gateway or proxy implementation details
✗ Long-term analytics or reporting on rate limit usage
📌
Assumptions
  • 2 billion DAU
  • 40 API calls per user per day on average
  • 100 bytes per API call metadata for rate limiting
  • Retention period of 7 days for counters and logs
⚡
QPS Calculation
write qps2,000,000,000 × 40 / 86400 ≈ 925,926 writes/sec
peak write qpsAssuming 3× peak factor: 925,926 × 3 ≈ 2,777,778 writes/sec
read qpsEach API call requires 1 read + 1 write: 2 × 925,926 ≈ 1,851,852 reads/sec
💾
Storage Estimate
daily storage bytes2,000,000,000 × 40 × 100 bytes = 8,000,000,000,000 bytes ≈ 7.28 TB/day
retention storage bytes7.28 TB × 7 days = 50.96 TB
with replicationAssuming 3× replication: 50.96 TB × 3 = 152.88 TB total
🖥️
Server Estimate
redis clusterAssuming 100K ops/sec per Redis shard, need ~28 shards for peak writes (2,777,778 / 100,000 ≈ 28)
api edge nodesAssuming each edge node handles 10K QPS, need ~278 edge nodes globally (2,777,778 / 10,000 ≈ 278)
🏗️
Architecture Diagram
Architecture Diagram
          +----------------+
          |   API Clients  |
          +-------+--------+
                  |
          +-------v--------+
          |   Edge Nodes   |  <-- Enforce rate limits locally
          +-------+--------+
                  |
          +-------v--------+
          | Distributed    |  <-- Centralized Redis cluster for counters
          | Redis Cluster  |
          +-------+--------+
                  |
          +-------v--------+
          | Config Service |  <-- Dynamic rate limit configs
          +----------------+
🧩
Components
Edge Nodes
Enforce rate limits close to clients to reduce backend load and latency
Why thisEdge nodes cache token bucket state and perform local checks with Redis fallback to meet 100ms P99 latency using Redis atomic operations
Why notCentralized enforcement causes high latency and backend overload at 925K QPS peak; Redis Cluster enables distributed counters with low latency
Distributed Redis Cluster
Store distributed counters and token bucket states with TTL for automatic expiry
Why thisRedis supports atomic INCR and EXPIRE commands with sub-millisecond latency and native TTL for stale data cleanup, suitable for high QPS workloads
Why notPostgreSQL requires manual sharding and slower writes at 2.7M ops/sec; Cassandra eventual consistency unsuitable for strict limits requiring atomic counters
Config Service
Manage dynamic rate limit policies and propagate changes to edge nodes
Why thisCentralized config with push notifications using technologies like etcd or Consul ensures consistent policy updates without downtime
Why notHardcoding configs or manual updates cause downtime and inconsistent enforcement; dynamic config services enable zero-downtime updates
API Clients
Generate API requests subject to rate limiting
Why thisClients receive rate limit headers for feedback and adjust request rates accordingly improving user experience and reducing backend load
Why notNo client feedback leads to poor user experience and increased backend load due to uncontrolled retries
Metrics & Monitoring
Collect rate limiter performance and usage metrics for SLA and scaling decisions
Why thisPrometheus + Grafana provide real-time observability and alerting on latency and error rates enabling proactive SLA management
Why notLack of monitoring delays detection of bottlenecks and SLA violations, increasing risk of outages
🔄
Data Flow
1
API Client → Edge Node
Send API request with user/API key
Edge node intercepts request for rate limiting
2
Edge Node → Local Token Bucket Cache
Check token availability locally
Fast path to allow or reject request
3
Edge Node → Redis Cluster
If cache miss or token exhausted, atomically decrement token count
Ensures global consistency of counters
4
Redis Cluster → Edge Node
Return updated token count or rejection
Edge node updates local cache accordingly
5
Edge Node → API Client
Respond with success or rate limit error and headers
Client receives real-time feedback
6
Config Service → Edge Nodes
Push updated rate limit policies
Edge nodes refresh local configs dynamically
7
Metrics & Monitoring → Operations Team
Provide dashboards and alerts
Ensure SLA and detect anomalies

Practice

(1/5)
1. A web API must limit incoming requests to 100 per second with bursts allowed up to 200 requests. Which component best enforces this rate limiting with burst handling?
easy
A. A fixed window counter that resets every second
B. A simple request queue that drops requests when full
C. A leaky bucket algorithm that processes requests at a fixed rate without bursts
D. A token bucket algorithm that refills tokens at a steady rate with a maximum bucket size

Solution

  1. Step 1: Identify rate limiting with burst support

    The token bucket algorithm allows tokens to accumulate up to a max bucket size, enabling bursts beyond the steady refill rate.

  2. Step 2: Eliminate other options

    Fixed window counters cause spikes at window boundaries and don't handle bursts well. Leaky bucket smooths traffic but disallows bursts. Simple queues drop excess requests without rate control.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Token bucket allows bursts by token accumulation [check]
Hint: Token bucket = steady refill + burst capacity [OK]
Common Mistakes:
2. For storing user and item embeddings in a recommendation system, which storage choice best balances low-latency reads and frequent updates at scale?
medium
A. Use a document store like MongoDB with embedding documents
B. Use a distributed key-value store like Cassandra with tunable consistency
C. Use a file system with periodic batch loading into memory
D. Use a relational database with normalized tables for embeddings

Solution

  1. Step 1: Identify storage requirements

    Embedding storage requires low-latency reads and frequent writes at scale with high availability.

  2. Step 2: Evaluate storage options

    Relational DB (A) struggles with write throughput and scaling; Cassandra (B) offers tunable consistency but may add complexity; file system batch loading (D) introduces stale data and high latency. Document store (C) supports flexible schema and fast reads with embedded documents, balancing latency and update frequency.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Document store balances flexible schema and read/write latency [check]
Hint: Document store balances schema flexibility and latency [check]
Common Mistakes:
3. Without the shard-level cache in the faceted search system, what exactly breaks during high query load spikes?
medium
A. The Query Coordinator fails to merge results correctly causing incorrect counts
B. Shard nodes become overloaded, causing increased query latency and timeouts
C. Queries return stale facet counts due to delayed cache invalidation
D. The inverted index becomes inconsistent and returns wrong documents

Solution

  1. Step 1: Understand shard-level cache role

    The cache reduces load on shard nodes by serving frequent queries quickly, preventing overload during spikes.

  2. Step 2: Trace failure without cache

    Without cache, all queries hit shard nodes directly, causing CPU and I/O overload, increasing latency and timeouts.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Cache absence -> shard overload -> latency spikes [check]
Hint: No cache -> shard overload -> latency spikes [check]
Common Mistakes:
4. For a video streaming service with users worldwide, which architecture better reduces origin server load and latency under heavy traffic?
medium
A. A CDN with edge caching and origin fallback for cache misses
B. Client-side caching with no CDN or regional origin servers
C. Multiple origin servers deployed in each region without CDN
D. Origin servers with auto-scaling groups behind a global load balancer

Solution

  1. Step 1: Evaluate origin scaling and latency challenges

    Auto-scaling origin servers reduce load but cannot eliminate latency for distant users.

  2. Step 2: Assess CDN edge caching benefits

    CDN caches content near users, drastically reducing latency and origin load under heavy traffic.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    CDN edge caching best reduces latency and origin load globally [check]
Hint: CDN edge caching beats origin scaling for global latency [OK]
Common Mistakes:
5. At 10x scale, which component in a push-based metrics collection system is most likely to fail first, and why?
hard
A. The aggregation workers, because CPU-intensive aggregation cannot scale horizontally
B. The storage backend, because it cannot handle the increased write throughput
C. The Kafka cluster, because partition count limits throughput and causes broker overload
D. The metric agents, because they overwhelm network bandwidth with frequent pushes

Solution

  1. Step 1: Analyze storage backend scaling

    Storage can be scaled horizontally with sharding; unlikely first failure.

  2. Step 2: Analyze Kafka cluster scaling

    Kafka scales with partitions but requires careful tuning; not first failure at 10x.

  3. Step 3: Analyze aggregation workers

    Aggregation workers scale horizontally; CPU load manageable with more instances.

  4. Step 4: Analyze metric agents

    Agents push metrics frequently, increasing network usage exponentially; network bandwidth at agents is limited and saturates first.

  5. Final Answer:

    Option D -> Option D

  6. Quick Check:

    Agents saturate network bandwidth first at 10x scale [check]
Hint: Agents saturate network bandwidth before backend bottlenecks [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