Bird
Raised Fist0

Token Bucket Algorithm - Design, Implementation, and Burst Handling

HLDmediumInterview freq: high
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
▶
Request Trace
Step 1/6
API Gateway Layer

Receives client request

Accepts incoming HTTP request and forwards to Rate Limiter Service

Protocol:HTTP
BeforeClient request arrives at API Gateway
AfterRequest forwarded to Rate Limiter Service
Rate Limiter Service

Fetches token bucket state

Reads current token count and last refill timestamp from Redis

Protocol:Redis GET
BeforeRate Limiter has no token bucket data for client
AfterToken count and timestamp retrieved from Redis
Rate Limiter Service

Calculates tokens to add and checks allowance

Refills tokens based on elapsed time, decrements if allowed

Protocol:In-memory calculation
BeforeToken bucket state loaded with last known values
AfterToken count updated, request allowed or rejected
Rate Limiter Service

Updates token bucket state in Redis

Writes updated token count and timestamp back to Redis

Protocol:Redis SET
BeforeToken bucket state updated in memory
AfterRedis reflects new token bucket state
Metrics & Monitoring

Records rate limit decision

Logs allowed or rejected request for monitoring dashboards

Protocol:Internal API call
BeforeRate Limiter decision made
AfterMetrics updated with request outcome
Configuration Service

Provides rate limit parameters

Supplies token bucket capacity and refill rate to Rate Limiter

Protocol:gRPC or REST
BeforeRate Limiter needs config for token bucket
AfterRate Limiter has current rate limit parameters
🏗️
Architecture Diagram
Architecture Diagram
┌───────────────────────┐
│   API Gateway Layer    │
│  (entry point for req) │
└────────────┬──────────┘
             │ HTTP Request
             ▼
┌───────────────────────┐
│  Rate Limiter Service  │
│ (executes token bucket)│
└───────┬───────────────┘
        │ Redis GET/INCR/SET
        ▼
┌───────────────────────┐
│     Redis Cluster      │
│ (stores token buckets) │
└───────┬───────────────┘
        │ Metrics data
        ▼
┌───────────────────────┐
│  Metrics & Monitoring  │
│ (collects usage stats) │
└───────┬───────────────┘
        │ Config fetch
        ▼
┌───────────────────────┐
│ Configuration Service  │
│ (provides rate limits) │
└───────────────────────┘
Design Rationale

This architecture implements the Token Bucket algorithm for rate limiting. Incoming requests first hit the API Gateway Layer, which forwards them to the Rate Limiter Service. The Rate Limiter queries the Redis Cluster to fetch the current token bucket state, including token count and last refill timestamp. It then calculates token refills based on elapsed time and decides whether to allow or reject the request. Updated token bucket state is written back to Redis to maintain consistency. Metrics & Monitoring collects data on rate limiting decisions for observability. The Configuration Service supplies dynamic rate limit parameters, enabling flexible burst handling and capacity adjustments. This design ensures efficient, consistent rate limiting with durable state and real-time metrics.

Primary Focus

✓

Practice

(1/5)
1. In the event sourcing system trace, at Step 4 the Delivery Worker reads an event from Kafka and attempts to update the read model. What happens if the read model update fails due to a transient database error?
easy
A. The Delivery Worker sends the event back to Kafka for reprocessing
B. The Delivery Worker discards the event and moves to the next one
C. The Delivery Worker commits the offset immediately and logs the failure
D. The Delivery Worker retries the update until success before committing the offset

Solution

  1. Step 1: Trace Delivery Worker decision at Step 4 -- read model update

    The Delivery Worker must ensure the read model is updated before committing the Kafka offset to avoid data loss.

  2. Step 2: Understand failure handling

    On transient DB errors, the worker retries to guarantee eventual consistency; discarding or committing offset prematurely risks data loss.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Retry read model update before offset commit -> ensures consistency [check]
Hint: Commit Kafka offset only after successful read model update [check]
Common Mistakes:
2. At 10x scale, which component in a real-time chat system implementing CAP theorem fails first and why?
hard
A. The database fails first due to increased write amplification
B. The message queue fails first due to partition key hotspots causing uneven load
C. Chat servers fail first because WebSocket connections are stateful and cannot be resharded easily
D. The load balancer fails first due to inability to handle increased connection churn

Solution

  1. Step 1: Identify stateful bottleneck

    Chat servers maintain WebSocket connections statefully, limiting horizontal scaling.

  2. Step 2: Understand scaling impact

    At 10x scale, existing WebSocket connections cannot be moved, causing chat servers to saturate first.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Stateful WebSocket servers bottleneck scaling before DB or load balancer [check]
Hint: Stateful WebSocket servers bottleneck scaling first [check]
Common Mistakes:
3. At 10x traffic scale, which CDN component is most likely to become the bottleneck first and why?
hard
A. Origin server, because it must handle all cache misses and cannot be scaled horizontally easily
B. Edge nodes, because their cache storage and network bandwidth scale linearly with traffic
C. DNS servers, because increased queries cause lookup latency and resolution failures
D. Load balancers, because they maintain stateful connections that cannot be sharded

Solution

  1. Step 1: Analyze scaling characteristics of CDN components

    Origin servers can be scaled horizontally; DNS is stateless and highly distributed; load balancers can be scaled or replaced.

  2. Step 2: Identify edge node bottleneck

    Edge nodes have fixed cache storage and network bandwidth per PoP; scaling traffic 10x stresses these resources first.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Edge nodes limited by cache and bandwidth -> bottleneck at 10x scale [check]
Hint: Edge nodes limited by cache and bandwidth first [check]
Common Mistakes:
4. At 10x current scale, which component is most likely to fail first in Instagram's real-time feed delivery, and why?
hard
A. The relational database storing user profiles, due to increased read/write contention
B. The feed cache layer, because cache invalidation traffic grows exponentially with user base
C. The WebSocket servers handling live feed updates, due to stateful connections limiting horizontal scaling
D. The photo storage service, because object storage bandwidth saturates under heavy upload load

Solution

  1. Step 1: Identify stateful components limiting scale

    WebSocket servers maintain persistent connections per user, which are stateful and bound to server memory.

  2. Step 2: Analyze scaling challenges

    At 10x scale, adding servers doesn't migrate existing WebSocket connections, causing uneven load and resource exhaustion. Relational DB (A) can be sharded, cache (B) can be scaled with TTL tuning, storage (D) scales with cloud object storage.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Stateful WebSocket connections limit horizontal scaling [check]
Hint: Stateful WebSocket servers bottleneck horizontal scaling [check]
Common Mistakes:
5. At 10x scale, which component in a message queue system is most likely to fail first and why?
hard
A. The database storing consumer offsets, because it cannot handle the increased write volume
B. The message broker's partition leader nodes, due to increased network I/O and disk throughput limits
C. The chat servers maintaining WebSocket connections, because stateful connections cannot be resharded easily
D. The producers, because they cannot generate messages fast enough to keep up with demand

Solution

  1. Step 1: Analyze stateful components at scale

    Chat servers maintain stateful WebSocket connections bound to server memory; scaling requires connection migration which is complex.

  2. Step 2: Compare other components

    Database (A) and brokers (B) can be scaled horizontally with sharding and replication; producers (D) can be scaled out by adding more instances.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Stateful WebSocket servers bottleneck scaling due to connection affinity [check]
Hint: Stateful WebSocket servers bottleneck 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