Bird
Raised Fist0

Fixed Window vs Sliding Window Counter - Trade-offs

HLDmediumInterview freq: common
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Fixed Window vs Sliding Window Counter - Trade-offs
Comparing fixed and sliding window counters for rate limiting at scale
mediumRate LimitingFreq: common
Prerequisites:Token BucketRedis
⚙️
Functional Requirements
  • Limit user requests to a maximum number per time window (e.g., 100 requests per minute)
  • Support both fixed window and sliding window rate limiting algorithms
  • Provide real-time enforcement with minimal latency (sub-100ms P99)
  • Allow per-user and per-API key rate limits
  • Expose APIs to query current usage and reset counters
  • Support distributed deployment with consistent rate limiting across nodes
📊
Non-Functional Requirements
  • Handle 2 billion daily active users (DAU)
  • Sustain peak write throughput of approximately 925K writes/sec
  • Ensure 99.99% availability for rate limiting decisions
  • Maintain 100ms P99 latency for rate limit checks
  • Data retention for counters up to 1 hour for sliding window calculations
❓
Clarifying Questions to Ask
  • What is the exact rate limit policy (e.g., requests per minute, hour)?
  • Are rate limits global or per user/API key or both?
  • Is eventual consistency acceptable or is strong consistency required for enforcement?
  • What is the acceptable latency for rate limit checks?
  • How long should counters be retained for sliding window calculations?
  • Are bursty traffic patterns expected, and how should they be handled?
Out of Scope
✗ Designing token bucket or leaky bucket algorithms in detail
✗ Authentication and authorization mechanisms
✗ Billing or quota management beyond rate limiting
✗ Long-term analytics or historical usage reporting
📌
Assumptions
  • 2 billion DAU
  • Each user sends 40 requests per day on average
  • Average request size is 100 bytes
  • Retention window for sliding window counters is 1 hour
⚡
QPS Calculation
write qps2B × 40 / 86400 ≈ 925,926 writes/sec
peak write qpsAssuming 3× peak factor: 925,926 × 3 ≈ 2.78M writes/sec
read qpsAssuming 1 read per write for enforcement: ~2.78M reads/sec
💾
Storage Estimate
daily storage bytes2B × 40 × 100 bytes = 8 TB/day
retention storage bytes8 TB × (1 hour / 24 hours) = 333 GB for 1 hour retention
with replication333 GB × 3 replicas = 1 TB total storage
🖥️
Server Estimate
redis clusterTo handle 2.78M writes/sec and 2.78M reads/sec with sub-ms latency, estimate 50 Redis shards with 10K ops/sec each
application serversAssuming 1000 requests/sec per server, need ~2800 app servers for peak load
🏗️
Architecture Diagram
Architecture Diagram
          +----------------------+
          |   Client Requests    |
          +----------+-----------+
                     |
                     v
          +----------------------+
          |  API Gateway / Proxy |
          +----------+-----------+
                     |
                     v
          +----------------------+
          | Rate Limiter Service |
          +----------+-----------+
                     |
         +-----------+------------+
         |                        |
         v                        v
 +---------------+        +---------------+
 | Redis Fixed   |        | Redis Sliding |
 | Window Store  |        | Window Store  |
 +---------------+        +---------------+
         |                        |
         +-----------+------------+
                     |
                     v
          +----------------------+
          |   Persistent Storage |
          | (e.g., Cassandra)    |
          +----------------------+
🧩
Components
API Gateway / Proxy
Receives client requests and routes them to the rate limiter service
Why thisNginx or Envoy provides high throughput, low latency routing with built-in rate limiting hooks
Why notCustom proxies add complexity and lack battle-tested performance and features
Rate Limiter Service
Implements fixed and sliding window algorithms, enforces rate limits per user/API key
Why thisStateless microservice allows horizontal scaling and easy deployment of different algorithms
Why notEmbedding logic in API Gateway limits flexibility and complicates updates
Redis Fixed Window Store
Stores counters with TTL for fixed window rate limiting
Why thisRedis TTL natively expires stale counters without cron jobs, supports atomic INCR operations with sub-ms latency
Why notMemcached lacks TTL granularity and atomic increment, leading to race conditions
Redis Sliding Window Store
Stores timestamped request counts in sorted sets for sliding window calculations
Why thisRedis Sorted Sets allow efficient range queries by timestamp, enabling accurate sliding window counts
Why notRelational DBs like PostgreSQL have high latency and poor write throughput for this use case
Persistent Storage (Cassandra)
Backs up counters and stores long-term usage data for analytics and recovery
Why thisCassandra scales linearly for high write throughput and offers tunable consistency for availability
Why notMongoDB's single primary node limits write scalability at 2.78M writes/sec
🔄
Data Flow
1
Client → API Gateway
Send request with user/API key metadata
Gateway handles initial routing and load balancing
2
API Gateway → Rate Limiter Service
Forward request metadata for rate limit check
Decouples rate limiting logic from gateway
3
Rate Limiter Service → Redis Fixed Window Store
Increment fixed window counter with TTL
Atomic INCR with TTL ensures accurate fixed window counting
4
Rate Limiter Service → Redis Sliding Window Store
Add timestamped entry to sorted set and remove old entries
Sliding window uses sorted sets for precise time-based counts
5
Redis Stores → Rate Limiter Service
Return current count for enforcement decision
Service compares count against limit to allow or reject request
6
Rate Limiter Service → Client
Respond with allow or reject status
Enforces rate limit with minimal latency
7
Rate Limiter Service → Persistent Storage
Periodically persist counters for analytics and recovery
Ensures durability and historical data availability

Practice

(1/5)
1. In the route leak mitigation system, at Step 4 the Route Validation Worker receives a BGP update. What does it do when the update contains a prefix not matching the configured filters?
easy
A. It immediately propagates the prefix to all peers to maintain connectivity
B. It marks the prefix as invalid and prevents it from being advertised further
C. It queues the prefix for manual review before any action is taken
D. It modifies the prefix to a default route to avoid blackholing traffic

Solution

  1. Step 1: Trace Route Validation Worker behavior at Step 4

    The worker checks prefixes against filters and, in some cases, queues suspicious prefixes for manual review, delaying propagation.

  2. Step 2: Eliminate other options

    Propagating invalid prefixes (A) causes leaks; marking invalid and blocking (B) is ideal but not always immediate; modifying prefixes (D) risks routing errors.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Suspicious prefixes queued for manual review, delaying propagation [check]
Hint: Suspicious prefixes queued before propagation [check]
Common Mistakes:
2. A search ranking system must store and serve feature vectors for millions of users with low latency. Which component is best suited to provide fast, consistent feature retrieval at scale?
easy
A. A relational database with complex joins to compute features on demand
B. A distributed in-memory feature store with precomputed feature vectors
C. A batch processing system that recomputes features daily and stores them in object storage
D. A key-value store without versioning or consistency guarantees

Solution

  1. Step 1: Identify feature retrieval requirements

    Low latency and consistency for millions of users require fast, precomputed feature access.

  2. Step 2: Evaluate component suitability

    A relational DB with joins (A) is too slow for real-time; batch recomputation (C) is stale; key-value store without consistency (D) risks stale or inconsistent features. Distributed in-memory feature store (B) provides fast, consistent retrieval.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    In-memory feature store -> low latency, consistent features [check]
Hint: Precompute features in-memory for fast, consistent retrieval [check]
Common Mistakes:
3. A system expects 1 million daily active users (DAU) with an average of 50 requests per user per day. Which component is best suited to handle the peak QPS estimation for capacity planning?
easy
A. Use a load balancer's metrics to estimate peak QPS from incoming traffic patterns
B. Use a relational database to directly measure QPS by counting requests in real-time
C. Use client-side logs aggregated asynchronously to estimate QPS after the fact
D. Use a CDN to estimate QPS by counting cache hits and misses

Solution

  1. Step 1: Identify component that reflects real-time incoming traffic

    Load balancer metrics provide immediate, accurate QPS data as they handle all incoming requests before backend processing.

  2. Step 2: Eliminate other options

    Relational DB counting is too slow and adds overhead; client logs are delayed and incomplete; CDN metrics reflect cached content, not all requests.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Load balancer metrics reflect real-time QPS accurately [check]
Hint: Load balancer metrics reflect real-time QPS [check]
Common Mistakes:
4. A distributed system requires generating unique IDs for millions of records per second across multiple data centers without coordination delays. Which ID generation strategy best fits this scenario?
easy
A. Use UUIDs generated independently by each data center
B. Use auto-increment IDs generated independently by each data center
C. Use custom IDs generated by a single global coordinator service
D. Use auto-increment IDs generated by a single centralized database node

Solution

  1. Step 1: Identify ID generation constraints

    Millions of IDs per second across multiple data centers require decentralized generation to avoid coordination delays.

  2. Step 2: Evaluate options for distributed uniqueness

    Auto-increment IDs from a single node (A) cause bottlenecks; custom IDs from a global coordinator (C) add latency; auto-increment per data center (D) risks collisions. UUIDs (B) are globally unique without coordination.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    UUIDs enable decentralized unique ID generation [check]
Hint: Decentralized unique IDs at scale -> UUIDs [check]
Common Mistakes:
5. If the Kafka cluster responsible for fan-out message delivery crashes, what is the exact failure observed in the News Feed system?
medium
A. New posts are lost permanently and never delivered to followers
B. The system blocks new post writes until Kafka recovers, causing user-facing delays
C. Followers receive duplicate feed updates due to Kafka replaying messages
D. Delivery Workers cannot fetch fan-out messages, so followers see stale feeds until recovery

Solution

  1. Step 1: Understand Kafka's role in fan-out delivery

    Kafka acts as a durable queue for fan-out messages. If it crashes, Delivery Workers cannot fetch new messages, causing stale feeds.

  2. Step 2: Evaluate failure modes

    Posts are not lost immediately (A) due to Kafka's durability; writes are asynchronous so no blocking (B); duplicates (D) occur only on replay, not crash.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Kafka crash stalls delivery, causing stale feeds [check]
Hint: Kafka crash stalls delivery, causing stale feeds [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