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
45 min · senior
senior

You are designing a rate limiting system for a 50M DAU social media startup. The system must enforce per-user API call limits with P99 latency under 200ms. The system must support encrypted counters due to compliance requirements and handle offline delivery scenarios where clients may retry requests after network disruptions.

Constraints
  • Must support encryption of counters at rest and in transit
  • P99 latency for rate limit checks must be under 200ms
  • System must handle offline delivery and retries without violating limits
  • Counters must scale to 50M DAU with peak QPS of 1M requests/sec
  • Trade-offs between accuracy and resource usage must be explicit
📋
Guided Steps
1/5
Step 1
Choosing the Counter Type
Should you use a Fixed Window or Sliding Window counter for rate limiting? What are the trade-offs in accuracy and complexity?
💡 Hint
Consider how each approach handles boundary conditions and burstiness in traffic.
Key Decision
Use Sliding Window counters implemented with Redis Sorted Sets to achieve near real-time accuracy and smooth rate limiting, rejecting Fixed Window counters due to their burstiness at window boundaries.
Interviewer Expectation
Mid: Names Fixed and Sliding Window counters and basic pros/cons. Senior: Explains how Fixed Window causes burstiness at window edges and how Sliding Window with Redis Sorted Sets provides smoother rate limiting with acceptable latency.
⚠️Common Wrong Answer
Choosing Fixed Window counters without acknowledging burstiness leads to poor user experience during window boundaries.
Step 2
Data Storage and Encryption
Where and how do you store counters securely to meet encryption requirements while maintaining low latency?
💡 Hint
Think about in-memory stores with encryption support and how to minimize encryption overhead on hot paths.
Key Decision
Use Redis Enterprise with built-in TLS encryption in transit and AES-256 encryption at rest, combined with client-side encryption for sensitive metadata to meet compliance and maintain sub-200ms P99 latency.
Interviewer Expectation
Mid: Suggests Redis or Memcached for counters. Senior: Explains Redis Enterprise encryption features, client-side encryption trade-offs, and how encryption impacts latency and throughput.
⚠️Common Wrong Answer
Using unencrypted Redis or a traditional RDBMS leads to compliance violations or unacceptable latency.
Step 3
Handling Offline Delivery and Retries
How does the system handle offline clients that retry requests later without violating rate limits?
💡 Hint
Consider idempotency keys and how counters can be synchronized or reconciled after offline periods.
Key Decision
Implement idempotency tokens stored in Cassandra with TTL to deduplicate retries, combined with counter reconciliation logic in Redis to prevent double counting during offline retries.
Interviewer Expectation
Mid: Mentions idempotency keys. Senior: Details Cassandra TTL for idempotency storage, how reconciliation avoids double counting, and trade-offs in consistency and latency.
⚠️Common Wrong Answer
Ignoring retries leads to inflated counters and incorrect rate limiting.
Step 4
API Design for Rate Limiting
Design 3 core API endpoints: request submission with rate limit check, counter synchronization after offline periods, and acknowledgment of processed requests.
💡 Hint
Think about request flow, client-server state synchronization, and how acknowledgments update counters atomically.
Key Decision
Design endpoints: POST /request with rate limit check returning allowed/denied; POST /sync to reconcile counters after offline; POST /ack to confirm processed requests updating Redis counters atomically.
Interviewer Expectation
Mid: Names endpoints and basic functionality. Senior: Explains atomic counter updates in Redis, synchronization challenges, and how APIs minimize race conditions and maintain P99 latency.
⚠️Common Wrong Answer
Designing only a single endpoint without sync or ack leads to stale counters and inconsistent rate limiting.
Step 5
Scaling to 50M DAU and 1M QPS
How do you scale the counter system to handle 1 million QPS with 50 million daily active users while maintaining latency and encryption constraints?
💡 Hint
Consider sharding, partitioning, and caching strategies in Redis and Cassandra clusters.
Key Decision
Shard Redis counters by user_id hash to distribute load evenly; use Redis Cluster with TLS; Cassandra for idempotency keys partitioned by user_id; employ client-side caching with Redis TTL to reduce hot reads.
Interviewer Expectation
Mid: Mentions sharding and caching. Senior: Explains Redis Cluster partitioning, TLS overhead mitigation, Cassandra partition keys for idempotency, and cache TTL tuning to meet latency and throughput.
⚠️Common Wrong Answer
Single Redis instance or unsharded Cassandra leads to hotspots and latency spikes.
🔌
API Design Challenge
Sketch 3 core endpoints for the rate limiting system: how clients send requests, how clients sync counters after offline periods, and how clients acknowledge processed requests.
Hints
  • How does the client send a request and get rate limit feedback?
  • How does the client synchronize counters after offline or retry scenarios?
  • How does the client acknowledge successful request processing to update counters?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Clear explanation of Fixed vs Sliding Window counters with trade-offs
  • Use of Redis Sorted Sets for Sliding Window implementation
  • Encryption strategy with Redis Enterprise TLS and AES-256 at rest
  • Handling offline retries with idempotency tokens in Cassandra
  • API design covering request, sync, and acknowledgment endpoints
Good to Have - 30%
  • Sharding and partitioning strategy for Redis and Cassandra
  • Client-side caching to reduce latency and load
  • Atomic counter updates using Redis Lua scripts
  • Discussion of latency impact due to encryption and mitigation
Bonus - 10%
  • Detailed failure mode analysis for race conditions in counters
  • Trade-offs in consistency models for counter synchronization
  • Use of metrics and monitoring to detect counter anomalies
Anti-patterns to Avoid
Using Fixed Window counters without smoothing causes burstiness and poor user experience at window boundaries, leading to sudden spikes in request rejections.
Storing counters in unencrypted Redis or relational DB violates compliance and increases latency due to lack of optimized encryption support.
Ignoring idempotency leads to double counting and incorrect rate limiting during retries, causing unfair throttling or abuse.
Single Redis instance without sharding causes hotspots and latency spikes, resulting in degraded system performance under high load.
✅
Model Answer
▼ Reveal

This design uses Sliding Window counters implemented with Redis Sorted Sets to provide accurate and smooth rate limiting, avoiding burstiness seen in Fixed Window counters. Counters are stored securely using Redis Enterprise with TLS encryption in transit and AES-256 at rest, meeting compliance and latency requirements. Offline retries are handled with idempotency tokens stored in Cassandra with TTL, preventing double counting. The API exposes three endpoints: POST /request for rate limit checks, POST /sync for counter reconciliation after offline periods, and POST /ack for atomic counter updates. The system scales to 50M DAU and 1M QPS by sharding Redis counters by user_id hash using Redis Cluster with TLS, partitioning Cassandra by user_id for idempotency keys, and employing client-side caching with Redis TTL to reduce load and maintain P99 latency under 200ms.

Key Decisions
  • Use Sliding Window counters with Redis Sorted Sets to avoid burstiness and provide smooth rate limiting
  • Store counters in Redis Enterprise with TLS and AES-256 encryption to meet compliance and latency goals
  • Use Cassandra with user_id partition key and TTL for idempotency tokens to handle offline retries safely
  • Design API with three endpoints to handle request submission, counter synchronization, and acknowledgment atomically
  • Shard Redis counters by user_id hash using Redis Cluster to distribute load evenly and scale to 1M QPS
  • Implement client-side caching with Redis TTL to reduce hot reads and maintain P99 latency under 200ms
  • Use Redis Lua scripts for atomic counter updates to prevent race conditions during concurrent requests
  • Employ idempotency tokens to deduplicate retries and prevent counter inflation
  • Sliding Window counters implemented with Redis Sorted Sets for smooth rate limiting and boundary accuracy
  • Redis Enterprise with TLS and AES-256 encryption at rest to meet compliance and latency requirements
  • Cassandra with user_id partition key for storing idempotency tokens with TTL to handle offline retries
  • API endpoints: POST /request for rate limit check, POST /sync for counter reconciliation, POST /ack for atomic counter updates
  • Redis Cluster sharded by user_id hash to scale to 1M QPS with even load distribution
  • Client-side caching with Redis TTL to reduce read load and maintain P99 latency under 200ms
  • Atomic Lua scripts in Redis to update counters and prevent race conditions during concurrent requests
  • Use of idempotency tokens to deduplicate retries and prevent counter inflation

Practice

(1/5)
1. In an Active-Passive failover system, at step 3 the passive node receives a heartbeat timeout from the active node. What is the passive node's immediate state transition?
easy
A. Passive node continues waiting for active node recovery
B. Passive node promotes itself to active and starts accepting traffic
C. Passive node sends a failback request to active node
D. Passive node shuts down to avoid split-brain

Solution

  1. Step 1: Understand heartbeat role

    Heartbeat timeout signals active node failure, triggering failover.

  2. Step 2: Passive node failover action

    Passive node must promote itself to active to maintain availability and accept traffic.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Heartbeat timeout -> passive promotes to active [check]
Hint: Heartbeat lost -> passive promotes active [check]
Common Mistakes:
2. In the newsfeed system, at Step 4 the Delivery Worker reads a fan-out event from Kafka and attempts to deliver it to followers. What happens if a follower's device is offline at this step?
easy
A. Delivery Worker marks the message as sent but not delivered, queues for retry later
B. Delivery Worker drops the message to avoid blocking other deliveries
C. Delivery Worker retries immediately until the follower is online
D. Delivery Worker pushes the message to the follower's device cache directly

Solution

  1. Step 1: Trace Delivery Worker behavior at Step 4

    The Delivery Worker reads fan-out events from Kafka and attempts delivery. If the follower is offline, immediate retry (A) would block and reduce throughput. Dropping messages (C) causes data loss. Pushing directly to device cache (D) is impossible if offline.

  2. Step 2: Understand retry mechanism

    The system marks the message as sent but not delivered, queues it for retry later when the follower reconnects, ensuring eventual delivery without blocking.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Offline followers cause queued retries, not immediate blocking [check]
Hint: Offline followers cause queued retries, not immediate blocking [check]
Common Mistakes:
3. If the API Gateway's authentication service crashes, what is the immediate failure mode observed by clients attempting to access protected endpoints?
medium
A. Clients receive a 500 Internal Server Error due to gateway crash
B. Clients receive a 401 Unauthorized response because authentication cannot be verified
C. Requests bypass authentication and reach backend services unverified
D. Requests queue indefinitely at the gateway until authentication service recovers

Solution

  1. Step 1: Trace failure impact of authentication service crash

    Without the authentication service, the gateway cannot verify credentials and may default to allowing requests through if no fail-closed mechanism is implemented.

  2. Step 2: Evaluate other options

    Clients receive a 500 Internal Server Error due to gateway crash is unlikely as gateway remains up. Clients receive a 401 Unauthorized response because authentication cannot be verified requires fail-closed design, which is not always implemented. Requests queue indefinitely at the gateway until authentication service recovers causes indefinite blocking, which is rare.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Auth service down -> requests pass unverified if no fail-closed [check]
Hint: Auth crash -> requests may bypass if no fail-closed design [check]
Common Mistakes:
4. At 10x scale, which component in the CDN architecture for adaptive bitrate HLS streaming is most likely to fail first, and why?
hard
A. Origin servers, because they cannot handle the increased number of segment requests
B. Edge cache nodes, because their limited storage causes frequent cache evictions and increased origin fetches
C. Load balancers, because they become bottlenecks distributing requests to edge nodes
D. Client players, because they cannot handle rapid bitrate switching at scale

Solution

  1. Step 1: Identify bottleneck at 10x scale

    Edge cache nodes have limited storage and memory; increased users cause cache thrashing and more origin fetches, increasing latency and load.

  2. Step 2: Evaluate other components

    Origin servers scale with CDN design; load balancers are horizontally scalable; client players are distributed and not a system bottleneck.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Edge cache storage limits cause cache thrashing first at scale [check]
Hint: Edge cache storage limits cause thrashing before origin overload [check]
Common Mistakes:
5. At 10x scale, which component in the ML data infrastructure is most likely to become the bottleneck first, and why?
hard
A. The feature store's online serving layer, because in-memory caches cannot scale linearly with data volume
B. The training pipeline's batch processing cluster, because compute resources scale easily with more nodes
C. The feature metadata registry, because relational databases handle metadata efficiently at scale
D. The ingestion Kafka cluster, because partition count limits throughput and rebalancing causes downtime

Solution

  1. Step 1: Analyze scaling challenges per component

    Feature store caches can be sharded; batch clusters scale horizontally; metadata registries are smaller and less frequently accessed.

  2. Step 2: Identify Kafka bottleneck

    Kafka throughput depends on partition count, which is hard to increase dynamically. Rebalancing partitions at scale causes downtime and latency spikes, making Kafka ingestion the first bottleneck.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Kafka partition limits and rebalancing cause ingestion bottlenecks [check]
Hint: Kafka partitions limit throughput; rebalancing causes downtime [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