Bird
Raised Fist0

Token Bucket Algorithm - Design, Implementation, and Burst Handling

HLDmediumInterview freq: high
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Token Bucket Algorithm - Design, Implementation, and Burst Handling
Design a scalable token bucket rate limiter supporting burst handling for 2B DAU
mediumRate LimitingFreq: high
Prerequisites:Token Bucket AlgorithmRedis
⚙️
Functional Requirements
  • Enforce per-user rate limits using token bucket algorithm with configurable refill rate and burst size
  • Support burst traffic by allowing token accumulation up to a maximum bucket size
  • Provide APIs to check and consume tokens atomically with low latency (<100ms P99)
  • Support distributed deployment to handle 2 billion DAU with consistent rate limiting
  • Expose metrics for monitoring token consumption and rate limit violations
  • Allow dynamic configuration updates for rate limits without downtime
📊
Non-Functional Requirements
  • System must handle 2 billion DAU generating 40 requests per user per day
  • End-to-end token check and consume latency must be under 100ms P99
  • Availability SLA of 99.99% to avoid user experience degradation
  • System must scale to peak write QPS of ~1 million and read QPS of ~2 million
  • Data consistency must be eventual but token consumption must be atomic per user
❓
Clarifying Questions to Ask
  • What is the maximum burst size relative to the refill rate per user?
  • Are rate limits uniform across all users or do they vary by user or tier?
  • Is strict consistency required or is eventual consistency acceptable for token counts?
  • What is the expected peak QPS and traffic pattern (steady vs spiky)?
  • Should the system support global rate limits in addition to per-user limits?
  • What is the retention period for token bucket state and logs?
Out of Scope
✗ Authentication and user identity management
✗ Complex multi-tenant quota sharing or hierarchical rate limits
✗ Long-term analytics or historical usage reporting beyond 30 days
✗ Integration with billing or payment systems
📌
Assumptions
  • 2 billion DAU
  • 40 requests per user per day
  • 100 bytes per request metadata stored for token bucket state
  • Retention period of 30 days for token bucket state
⚡
QPS Calculation
write qps2B × 40 / 86400 ≈ 925,926 writes/sec
peak write qpsAssuming 2x peak factor → 1,851,852 writes/sec
read qpsToken check API called twice per request → 2 × 925,926 = 1,851,852 reads/sec
💾
Storage Estimate
daily storage gb(2B × 40 × 100 bytes) / (1024^3) ≈ 7.45 GB/day
retention storage gb7.45 GB/day × 30 days = 223.5 GB
with replication223.5 GB × 3 replicas = 670.5 GB total
🖥️
Server Estimate
redis clusterAssuming 50K writes/sec per Redis shard → 1,851,852 / 50,000 ≈ 38 shards
api serversAssuming each API server handles 5,000 QPS → 1,851,852 / 5,000 ≈ 370 servers
🏗️
Architecture Diagram
Architecture Diagram
                +----------------------+
                |      Client Apps      |
                +----------+-----------+
                           |
                           v
                +----------------------+
                |   API Gateway Layer   |
                +----------+-----------+
                           |
                           v
                +----------------------+
                |  Rate Limiter Service |
                +----------+-----------+
                           |
                           v
                +----------------------+
                |     Redis Cluster     |
                | (Token Bucket State)  |
                +----------+-----------+
                           |
                           v
                +----------------------+
                |  Metrics & Monitoring |
                +----------+-----------+
                           |
                           v
                +----------------------+
                | Configuration Service |
                +----------------------+
🧩
Components
API Gateway Layer
Receives client requests and routes them to Rate Limiter Service
Why thisNginx or Envoy provides high throughput, low latency routing with TLS termination
Why notCustom HTTP servers add complexity and lack battle-tested performance at 1.8M QPS
Rate Limiter Service
Implements token bucket logic, atomically checks and consumes tokens per user
Why thisStateless microservice horizontally scalable to handle 1.8M QPS with Redis backend
Why notEmbedding logic in API Gateway reduces flexibility and complicates deployment
Redis Cluster
Stores token bucket state with TTL, supports atomic Lua scripts for token operations
Why thisRedis supports sub-millisecond lookups, atomic Lua scripts, and TTL for stale data cleanup
Why notCassandra has higher write latency and no native atomic decrement with TTL
Metrics & Monitoring
Collects token consumption, rate limit violations, and system health metrics
Why thisPrometheus + Grafana provide scalable, real-time monitoring with alerting
Why notCustom monitoring lacks ecosystem and scalability for 2B DAU scale
Configuration Service
Manages dynamic rate limit configurations and propagates updates to Rate Limiter Service
Why thisConsul or etcd provides consistent distributed configuration with watch APIs
Why notStatic config files require redeployment and do not support dynamic updates
🔄
Data Flow
1
Client Apps → API Gateway Layer
Send request with user ID and action metadata
Requests arrive at API Gateway for routing
2
API Gateway Layer → Rate Limiter Service
Forward request for token bucket check and consume
Rate Limiter Service is stateless and horizontally scalable
3
Rate Limiter Service → Redis Cluster
Execute atomic Lua script to check tokens and decrement if allowed
Atomicity ensures no race conditions in token consumption
4
Redis Cluster → Rate Limiter Service
Return success or rate limit exceeded response
TTL auto-expires stale token buckets without manual cleanup
5
Rate Limiter Service → Client Apps
Return allow or reject response with remaining tokens
Client receives immediate feedback on rate limit status
6
Rate Limiter Service → Metrics & Monitoring
Emit metrics on token consumption and violations
Enables real-time monitoring and alerting
7
Configuration Service → Rate Limiter Service
Push dynamic rate limit config updates
Supports live updates without downtime

Practice

(1/5)
1. You must design a high-throughput OLTP system that requires strong consistency but can tolerate some delay in durability guarantees. Which approach is best suited?
medium
A. Use asynchronous replication with strict serializable isolation but delayed durability
B. Use synchronous replication with immediate durability on commit
C. Use eventual consistency with snapshot isolation and immediate durability
D. Use read uncommitted isolation with synchronous durability

Solution

  1. Step 1: Analyze consistency and durability trade-offs

    Strong consistency requires strict serializable isolation; durability can be delayed to improve throughput.

  2. Step 2: Evaluate replication and isolation options

    Asynchronous replication with strict serializable isolation fits the requirement, allowing durability delay without sacrificing consistency.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Async replication + strict serializable -> strong consistency, delayed durability [check]
Hint: Strong consistency needs strict isolation, durability can lag [check]
Common Mistakes:
2. If the Kafka cluster is unavailable, what exact failure occurs in the notification system's delivery path?
medium
A. Notifications are lost silently because the delivery workers cannot fetch messages
B. Notification producers block synchronously, causing upstream request latency spikes and potential timeouts
C. Delivery workers switch to a backup queue automatically with no message loss
D. The system falls back to synchronous HTTP calls to devices, causing slow delivery

Solution

  1. Step 1: Trace failure impact of Kafka unavailability

    Kafka unavailability blocks producers or causes retries; delivery workers cannot fetch messages from Kafka.

  2. Step 2: Evaluate fallback mechanisms

    In a robust design, a backup queue or dead-letter queue is used to avoid message loss; synchronous HTTP fallback (D) is not automatic; silent loss (A) is unacceptable.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Backup queue prevents message loss during Kafka downtime [check]
Hint: Backup queue prevents loss when Kafka is down [check]
Common Mistakes:
3. Without the consistent hashing ring metadata, what exactly breaks in a distributed cache system when a client requests a key?
medium
A. The cache nodes lose synchronization and data becomes corrupted
B. The cache node receiving the request cannot determine the correct node, causing request failure or indefinite retry
C. The client receives stale data from an outdated cache node
D. The system falls back to a centralized database for all requests, increasing latency

Solution

  1. Step 1: Role of consistent hashing ring metadata

    The ring metadata maps keys to nodes; without it, nodes cannot route requests correctly, leading to inconsistent data placement.

  2. Step 2: Consequence of missing ring metadata

    Without this metadata, nodes lose synchronization on key ownership, causing data corruption as writes go to wrong nodes; request failure (The cache node receiving the request cannot determine the correct node, causing request failure or indefinite retry) is secondary, and fallback (The system falls back to a centralized database for all requests, increasing latency) is not automatic.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Missing ring metadata causes data corruption due to lost key-node mapping [check]
Hint: No ring metadata -> lost key-node mapping -> data corruption [check]
Common Mistakes:
4. At 10x traffic scale during a flash sale, which component is most likely to fail first and why?
hard
A. The relational database because it cannot handle 10x write throughput without sharding
B. The API Gateway because it maintains stateful user sessions and cannot horizontally scale easily
C. The cache layer because TTL expiration floods the database with cache misses
D. The inventory service because distributed locking causes contention and latency spikes

Solution

  1. Step 1: Identify stateful components under load

    API Gateway maintains user session state (e.g., WebSocket connections), which are sticky and stateful, limiting horizontal scaling.

  2. Step 2: Compare other components

    Relational DB (A) can be sharded; cache (C) TTL floods are mitigated by pre-warming; inventory locking (D) is optimized with partitioning. API Gateway statefulness causes connection limits and bottlenecks first.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    API Gateway stateful sessions limit horizontal scaling [check]
Hint: Stateful API Gateway limits scaling under 10x load [check]
Common Mistakes:
5. At 10x scale, which component in the News Feed system is most likely to fail first and why?
hard
A. The database, because it cannot handle the increased write volume for posts
B. The Delivery Workers, because they cannot process the exponentially larger fan-out queues fast enough
C. The cache layer, because cache invalidation traffic grows superlinearly with user count
D. The fan-out message queue (Kafka), because partition count limits prevent scaling beyond a threshold

Solution

  1. Step 1: Analyze bottlenecks at 10x scale

    Database (A) can be sharded; cache (C) scales horizontally; Kafka (D) can add partitions but has limits.

  2. Step 2: Delivery Workers face exponential fan-out growth

    Fan-out queues grow with followers; Delivery Workers must push updates to millions more followers, causing processing lag and backlog.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Delivery Workers bottleneck due to fan-out processing load [check]
Hint: Delivery Workers bottleneck on fan-out processing 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