Bird
Raised Fist0

Leaky Bucket Algorithm - Smoothing Traffic Bursts to Steady Rate

HLDmediumInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Leaky Bucket Algorithm - Smoothing Traffic Bursts to Steady Rate
Implementing Leaky Bucket to smooth traffic bursts into steady request rates
mediumRate LimitingFreq: medium
Prerequisites:Token BucketRedis
⚙️
Functional Requirements
  • Accept incoming requests from clients and enqueue them for processing
  • Apply Leaky Bucket algorithm to smooth bursts into a steady output rate
  • Reject or delay requests exceeding the configured leak rate per user or API key
  • Provide real-time feedback on rate limit status (e.g., remaining capacity)
  • Support configurable leak rates per user or service tier
  • Expose metrics and logs for monitoring rate limiting behavior
📊
Non-Functional Requirements
  • Support 2 billion daily active users generating up to 40 requests per user per day
  • Ensure 99.99% availability with failover and redundancy
  • Maintain request processing latency under 100ms P99 including rate limiting
  • Handle peak write QPS of approximately 925K requests per second
  • Scale horizontally to handle traffic spikes without degradation
❓
Clarifying Questions to Ask
  • Is rate limiting applied per user, per API key, or globally?
  • What is the maximum allowed leak rate per user or service tier?
  • Should the system support burst capacity beyond the steady leak rate?
  • Is the system expected to persist state across restarts or failures?
  • What is the expected maximum request size and payload?
  • Are there SLAs for rate limit feedback latency or accuracy?
Out of Scope
✗ Authentication and authorization of users
✗ Detailed billing or quota enforcement beyond rate limiting
✗ Long-term analytics or historical usage reporting
✗ Design of client-side retry or backoff mechanisms
📌
Assumptions
  • 2 billion daily active users (DAU)
  • Each user sends 40 requests per day on average
  • Average request size is 100 bytes
  • Retention period for rate limiting state is 1 day
⚡
QPS Calculation
write qps2,000,000,000 x 40 / 86,400 ≈ 925,926 requests/sec
peak write qpsAssuming 3x peak factor: 925,926 x 3 ≈ 2,777,778 requests/sec
read qpsReads for rate limit checks assumed equal to writes: 925,926 requests/sec
💾
Storage Estimate
daily storage bytes2,000,000,000 x 40 x 100 bytes = 8,000,000,000,000 bytes ≈ 7.28 TB/day
retention days1
total storage with replication7.28 TB x 3 (replication factor) = 21.84 TB
🖥️
Server Estimate
api gateway serversAssuming each server handles 10,000 QPS, need 278 servers for peak load
redis cluster nodesEach Redis node supports 50,000 ops/sec, need 56 nodes for 2.8M ops/sec peak
🏗️
Architecture Diagram
Architecture Diagram
Client
  |
  v
API Gateway (Nginx + Envoy)
  |
  v
Rate Limiter Service (Leaky Bucket Logic)
  |
  v
Redis Cluster (Leaky Bucket State Storage)
  |
  v
Downstream Services (Business Logic)
  |
  v
Monitoring & Metrics (Prometheus + Grafana)
🧩
Components
API Gateway
Entry point for client requests, performs initial routing and authentication
Why thisNginx + Envoy provide high throughput, low latency, and native support for rate limiting hooks
Why notCustom proxies lack mature ecosystem and scalability at 2.8M QPS peak
Rate Limiter Service
Implements Leaky Bucket algorithm per user/API key to smooth traffic bursts
Why thisStateless service with Redis backend allows horizontal scaling and fast state access
Why notIn-memory local caches (e.g., Guava) cannot share state across distributed instances
Redis Cluster
Stores per-user leaky bucket state with TTL for automatic expiration
Why thisRedis supports sub-millisecond lookups, atomic INCR and EXPIRE commands, and clustering for scale
Why notCassandra has higher write latency and complexity for atomic counters at 2.8M ops/sec
Downstream Services
Business logic services that consume rate-limited requests
Why thisDecoupling rate limiting from business logic improves modularity and fault isolation
Why notEmbedding rate limiting inside business services complicates scaling and maintenance
Monitoring & Metrics
Collects metrics on rate limiting hits, rejections, latencies for alerting and capacity planning
Why thisPrometheus + Grafana provide real-time observability with alerting and dashboarding
Why notCustom monitoring lacks community support and integration with alerting tools
🔄
Data Flow
1
Client → API Gateway
Send request with user/API key metadata
API Gateway authenticates and forwards request
2
API Gateway → Rate Limiter Service
Forward request metadata for rate limiting check
Rate Limiter is stateless, relies on Redis for state
3
Rate Limiter Service → Redis Cluster
Read and update leaky bucket counters atomically
Use Redis INCR and TTL to track bucket fill and leak
4
Rate Limiter Service → API Gateway
Return allow or reject decision with remaining capacity
Reject if bucket overflow, else allow request
5
API Gateway → Downstream Services
Forward allowed requests for business processing
Downstream services receive smoothed traffic
6
Rate Limiter Service → Monitoring & Metrics
Emit metrics on rate limiting decisions and latencies
Supports alerting on overload or failures

Practice

(1/5)
1. In a primary-replica replication system, at step 4 the replica receives a batch of write-ahead log entries from the primary. What is the replica's exact state after applying these entries?
easy
A. Replica marks entries as committed and acknowledges primary before applying
B. Replica applies entries to its data store and then acknowledges primary
C. Replica applies entries and immediately serves reads from them before acknowledgment
D. Replica buffers entries without applying until primary confirms commit

Solution

  1. Step 1: Trace replica behavior at step 4

    Replica applies WAL entries to its local store to catch up with primary.

  2. Step 2: Understand acknowledgment timing

    Replica acknowledges primary only after applying entries to ensure durability and consistency.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Replica applies then acknowledges -> ensures data durability [check]
Hint: Apply WAL entries before ack -> durability ensured [check]
Common Mistakes:
2. A distributed API rate limiter must enforce limits with minimal latency at the network edge. Which component is best suited to perform this enforcement?
easy
A. Centralized database that aggregates all request counts for global enforcement
B. Edge cache with local counters and periodic sync to central store
C. Batch job that processes logs every minute to update usage stats
D. Client-side SDK that tracks usage and blocks requests locally

Solution

  1. Step 1: Identify edge enforcement needs

    Enforcement must be low-latency and close to the client to avoid network round trips.

  2. Step 2: Evaluate options for latency and consistency

    Centralized DB (A) adds latency; batch jobs (C) are too delayed; client SDK (D) is untrustworthy. Edge cache with local counters (B) balances latency and eventual consistency.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Edge cache enforces limits locally with periodic sync [check]
Hint: Enforce limits close to client with local counters [check]
Common Mistakes:
3. A full-text search system must handle millions of document updates per second and ensure near real-time search availability. Which component is best suited to buffer and decouple the high write throughput from the indexing process?
easy
A. Use a relational database with batch update triggers to update the index
B. Use a distributed log system like Kafka to buffer document update events
C. Use a distributed cache like Redis to store the entire inverted index in memory
D. Use a message queue with at-least-once delivery but no ordering guarantees

Solution

  1. Step 1: Identify buffering component for high write throughput

    Relational DBs with triggers (A) are not designed for millions of writes per second and cause blocking. Redis (C) is fast but storing entire inverted index in memory is not durable or scalable. Message queues without ordering (D) risk out-of-order updates causing index inconsistency.

  2. Step 2: Evaluate Kafka's suitability

    Kafka provides durable, ordered, partitioned logs that can buffer high write rates and decouple ingestion from indexing, enabling near real-time processing.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Kafka buffers high write throughput with ordering and durability [check]
Hint: Kafka buffers writes with ordering and durability [check]
Common Mistakes:
4. If the commit metadata database becomes unavailable, what is the immediate failure observed when a user tries to create a new branch?
medium
A. The system creates the branch but marks it as unverified until metadata is restored
B. The branch creation request fails immediately with an error indicating metadata service unavailability
C. The system queues the branch creation request and retries later without user notification
D. The branch is created locally on the client but not persisted to the server

Solution

  1. Step 1: Understand role of commit metadata DB

    Commit metadata DB stores branch pointers; without it, server cannot persist new branches.

  2. Step 2: Trace branch creation failure

    Client may create branch locally, but server cannot persist it, so branch is effectively lost or inconsistent.

  3. Step 3: Eliminate other options

    Queuing without notification hides failure; immediate error is possible but not typical if client allows local ops; marking unverified branches requires metadata DB access.

  4. Final Answer:

    Option D -> Option D

  5. Quick Check:

    Metadata DB down -> branch created locally but not persisted [check]
Hint: Metadata DB down -> local branch only, no server persistence [check]
Common Mistakes:
5. If the centralized session store is unavailable, what exactly breaks in a system where stateless frontends rely on it for user session data?
medium
A. Frontend servers crash due to missing session data causing system-wide outage
B. User requests block waiting for session data, causing increased latency and possible timeouts
C. User sessions silently expire but requests continue processing without authentication
D. Load balancer reroutes all traffic to a backup session store automatically

Solution

  1. Step 1: Identify session store role

    Centralized session store provides authentication and session state to stateless frontends.

  2. Step 2: Trace failure impact

    If unavailable, frontends cannot validate sessions, leading to silent session expiry and unauthenticated request processing.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Session store down -> sessions expire silently, requests proceed unauthenticated [check]
Hint: Session store down -> silent expiry, unauthenticated requests proceed [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