Bird
Raised Fist0

Distributed Rate Limiting - Redis-Based Centralized Counter Approach

HLDmediumInterview freq: common
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🎯
Distributed Rate Limiting - Redis-Based Centralized Counter Approach
45 min · senior
senior

You are designing a distributed rate limiting system for a startup with 50 million daily active users (DAU). The system must enforce API usage limits per user and per API key to prevent abuse and ensure fair usage. The system should support bursty traffic patterns and maintain a P99 latency under 200ms for rate limit checks. All counters must be encrypted at rest and in transit due to regulatory compliance. The system must handle up to 1 million requests per second globally and provide near real-time feedback to clients on their remaining quota.

Constraints
  • P99 latency for rate limit checks must be under 200ms
  • Counters must be encrypted at rest and in transit
  • Support burst traffic with accurate rate limiting
  • Handle 1 million requests per second globally
  • Centralized counter approach using Redis
  • Provide near real-time feedback on quota usage
📋
Guided Steps
1/5
Step 1
Choosing the Data Store for Counters
Which data store will you use to maintain distributed counters for rate limiting, and why?
💡 Hint
Consider a store with atomic increment operations, low latency, and support for TTL for burst handling.
Key Decision
Use Redis with the INCR and Lua scripting capabilities for atomic counter increments and TTL management to handle burst traffic efficiently.
Interviewer Expectation
Mid-level: Names Redis for counters. Senior: Explains Redis atomic INCR, Lua scripts for atomic multi-step operations, and TTL for automatic counter resets.
⚠️Common Wrong Answer
Using a relational database like MySQL for counters - leads to high latency and poor write scalability at 1M RPS.
Step 2
Ensuring Data Encryption and Security
How will you ensure counters are encrypted both at rest and in transit in Redis?
💡 Hint
Think about Redis encryption features and network security layers.
Key Decision
Enable Redis TLS for encryption in transit and use Redis Enterprise or Redis modules supporting encryption at rest, combined with application-level encryption for sensitive data.
Interviewer Expectation
Mid-level: Mentions TLS for in-transit encryption. Senior: Details Redis Enterprise encryption at rest, key management, and application-level encryption to meet compliance.
⚠️Common Wrong Answer
Relying only on network-level encryption without encrypting data at rest - violates compliance and risks data exposure.
Step 3
Handling High Throughput and Low Latency
How will you architect the system to handle 1 million requests per second with P99 latency under 200ms?
💡 Hint
Consider Redis clustering, sharding, and client-side load balancing.
Key Decision
Deploy Redis Cluster with sharded counters across multiple nodes, use client-side consistent hashing to route requests, and employ pipelining and Lua scripts to minimize round trips.
Interviewer Expectation
Mid-level: Describes Redis Cluster for sharding. Senior: Explains consistent hashing to avoid hot keys, Lua scripts to reduce latency, and monitoring for cluster health.
⚠️Common Wrong Answer
Using a single Redis instance - causes bottlenecks and latency spikes under high load.
Step 4
API Design for Rate Limiting Service
Design 3 core API endpoints for clients to interact with the rate limiting system.
💡 Hint
Think about endpoints for consuming quota, querying usage, and acknowledging resets or errors.
Key Decision
Define endpoints: POST /consumeQuota to atomically check and decrement counters; GET /quotaStatus to fetch current usage and remaining quota; POST /ackReset to acknowledge quota resets or error states.
Interviewer Expectation
Mid-level: Lists endpoints with basic functionality. Senior: Explains atomicity in /consumeQuota, caching strategies for /quotaStatus, and error handling in /ackReset.
⚠️Common Wrong Answer
Designing only a single endpoint without separation of concerns - leads to complex client logic and harder scaling.
Step 5
Dealing with Counter Consistency and Race Conditions
How will you ensure counters remain consistent and avoid race conditions under concurrent requests?
💡 Hint
Consider atomic operations and scripting capabilities in Redis.
Key Decision
Use Redis Lua scripts to perform atomic read-modify-write operations for counters, ensuring no race conditions during concurrent increments and TTL resets.
Interviewer Expectation
Mid-level: Mentions atomic INCR commands. Senior: Details Lua scripting for multi-step atomicity and fallback strategies on script failures.
⚠️Common Wrong Answer
Using separate GET and SET commands for counters - causes race conditions and inaccurate rate limiting.
🔌
API Design Challenge
Sketch 3 core endpoints for the rate limiting service that clients will use.
Hints
  • How does the client send a request to check and consume quota?
  • How does the client query their current usage and remaining quota?
  • How does the client report or acknowledge quota resets or errors?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Use Redis Cluster for scalable distributed counters
  • Implement atomic counter increments with Redis Lua scripts
  • Encrypt data in transit with TLS and at rest with Redis Enterprise or equivalent
  • Design API endpoints for quota consumption, status, and reset acknowledgment
Good to Have - 30%
  • Client-side consistent hashing to avoid hot keys
  • Application-level encryption for sensitive data
  • Use Redis pipelining to optimize latency
  • Monitoring Redis cluster health and latency
Bonus - 10%
  • Explain fallback mechanisms for Redis script failures
  • Discuss burst traffic handling with TTL and token bucket algorithms
Anti-patterns to Avoid
Using a single Redis instance causes bottlenecks and latency spikes under high load, leading to degraded performance and request failures.
Relying on separate GET and SET commands for counters leads to race conditions and inaccurate rate limiting due to non-atomic updates.
Ignoring encryption at rest violates compliance requirements and risks sensitive data exposure in case of breaches.
Designing monolithic API endpoints increases client complexity and reduces scalability by mixing concerns and making maintenance harder.
Using relational databases for counters causes high latency and poor write scalability, unable to handle 1 million RPS efficiently.
Neglecting monitoring leads to undetected performance degradation and potential system outages due to lack of visibility.
✅
Model Answer
▼ Reveal

A Redis Cluster-based distributed rate limiting system using atomic Lua scripts for counters, TLS and Redis Enterprise encryption for security, and well-designed APIs to handle 1M RPS with P99 latency under 200ms.

Key Decisions
  • Use Redis Cluster to shard counters across multiple nodes to scale to 1 million RPS with low latency.
  • Implement atomic counter increments and TTL management using Redis Lua scripts to avoid race conditions.
  • Enable TLS encryption for all Redis client-server communication to secure data in transit.
  • Use Redis Enterprise or equivalent to encrypt data at rest, meeting regulatory compliance.
  • Design three separate API endpoints: POST /consumeQuota for atomic quota consumption, GET /quotaStatus for usage querying, and POST /ackReset for acknowledging resets or errors.
  • Apply client-side consistent hashing to route requests to appropriate Redis shards and avoid hot keys.
  • Use application-level encryption for sensitive counter metadata beyond Redis native encryption.
  • Employ Redis pipelining to reduce network round trips and improve throughput.
  • Set up monitoring and alerting on Redis cluster health and latency metrics to detect and mitigate bottlenecks.
  • Redis Cluster for sharded, scalable counter storage with sub-200ms P99 latency
  • Redis Lua scripting for atomic multi-step counter increments and TTL management
  • Redis TLS and Redis Enterprise encryption at rest for compliance with data security
  • Client-side consistent hashing to route requests to correct Redis shards and avoid hot keys
  • API endpoints designed for atomic quota consumption, usage querying, and reset acknowledgments
  • Application-level encryption for sensitive counter metadata beyond Redis native encryption
  • Pipelining Redis commands to reduce network round trips and improve throughput
  • Monitoring and alerting on Redis cluster health and latency metrics to detect bottlenecks

Practice

(1/5)
1. In the message delivery trace, at Step 4 the Delivery Worker checks the consumer offset stored in ZooKeeper before sending messages. What happens if the offset is missing at this step?
easy
A. The Delivery Worker resets the offset to the earliest available message in the partition
B. The Delivery Worker blocks indefinitely waiting for the offset to appear
C. The Delivery Worker skips the message and moves to the next offset
D. The Delivery Worker deletes the partition and requests a new one

Solution

  1. Step 1: Understand consumer offset role

    The offset tracks the last consumed message; if missing, the consumer has no progress marker.

  2. Step 2: Delivery Worker behavior on missing offset

    Kafka semantics dictate resetting to earliest offset to avoid message loss; skipping (A) would lose messages; blocking (C) causes deadlock; deleting partition (D) is invalid.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Missing offset -> reset to earliest offset to ensure delivery [check]
Hint: Missing offset resets to earliest message, never skips or blocks [check]
Common Mistakes:
2. A stock exchange system must handle millions of incoming orders per second and ensure strict ordering per stock symbol for matching. Which component is best suited to guarantee ordering and durability of these orders before matching?
easy
A. Use a partitioned Kafka topic keyed by stock symbol to persist and order incoming orders
B. Use a relational database with a global sequence number to store all orders
C. Use a distributed in-memory cache like Redis to store incoming orders temporarily
D. Use a simple message queue like RabbitMQ without partitioning to enqueue orders

Solution

  1. Step 1: Identify Kafka's role in ordering and durability

    Kafka partitions keyed by stock symbol ensure strict ordering per symbol and durable storage of orders before matching.

  2. Step 2: Eliminate other options

    Redis lacks durability guarantees; relational DB with global sequence is a bottleneck at scale; RabbitMQ without partitioning cannot guarantee ordering per symbol.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Kafka partition keyed by symbol -> ordering + durability guaranteed [check]
Hint: Partition by key for ordering and durability [check]
Common Mistakes:
3. In the request flow for a nearby search, at step 4 the Quadtree component receives a query bounding box. What does the Quadtree do at this step?
easy
A. It returns all businesses within the bounding box without further filtering
B. It converts the bounding box into Geohash prefixes and queries a key-value store
C. It recursively traverses nodes intersecting the bounding box to collect candidate locations
D. It sends the bounding box to a full-text search engine for keyword filtering

Solution

  1. Step 1: Understand Quadtree traversal

    At step 4, the Quadtree recursively visits nodes overlapping the bounding box to efficiently narrow down candidate locations.

  2. Step 2: Eliminate other options

    It returns all businesses within the bounding box without further filtering is incorrect because Quadtree does filtering, not a full scan. It converts the bounding box into Geohash prefixes and queries a key-value store describes Geohash usage, not Quadtree. It sends the bounding box to a full-text search engine for keyword filtering is unrelated to spatial indexing.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Quadtree recursively traverses nodes intersecting query box [check]
Hint: Quadtree recursively visits nodes overlapping query bounding box [OK]
Common Mistakes:
4. In a token bucket rate limiter, at step 4 the Request Handler checks the token count before processing a request. What happens if the bucket is empty at this step?
easy
A. The token count is reset to maximum and the request proceeds
B. The request is immediately processed and the token count goes negative
C. The request is rejected or delayed until tokens are refilled
D. The request is queued indefinitely without token consumption

Solution

  1. Step 1: Trace Request Handler token check at Step 4

    If the token bucket is empty, no tokens are available to allow immediate processing.

  2. Step 2: Determine request fate

    The request must be rejected or delayed until tokens refill; processing without tokens violates rate limits.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Empty bucket -> reject or delay request [check]
Hint: No tokens? Delay or reject request [OK]
Common Mistakes:
5. For a video streaming service with users worldwide, which architecture better reduces origin server load and latency under heavy traffic?
medium
A. A CDN with edge caching and origin fallback for cache misses
B. Client-side caching with no CDN or regional origin servers
C. Multiple origin servers deployed in each region without CDN
D. Origin servers with auto-scaling groups behind a global load balancer

Solution

  1. Step 1: Evaluate origin scaling and latency challenges

    Auto-scaling origin servers reduce load but cannot eliminate latency for distant users.

  2. Step 2: Assess CDN edge caching benefits

    CDN caches content near users, drastically reducing latency and origin load under heavy traffic.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    CDN edge caching best reduces latency and origin load globally [check]
Hint: CDN edge caching beats origin scaling for global latency [OK]
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