Bird
Raised Fist0

Why Rate Limiting Exists and What Happens to Systems Without It

HLDmediumInterview freq: common
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Why Rate Limiting Exists and What Happens to Systems Without It
Understanding the critical role of rate limiting in system stability and scalability
mediumRate LimitingFreq: common
Prerequisites:Token BucketRedis
⚙️
Functional Requirements
  • Limit the number of requests per user or client IP to prevent abuse and overload.
  • Support multiple rate limiting policies (e.g., per user, per API key, per IP).
  • Provide real-time feedback to clients when limits are exceeded (e.g., HTTP 429).
  • Allow dynamic configuration of rate limits without downtime.
  • Ensure rate limiting decisions are consistent and accurate across distributed servers.
  • Expose metrics and logs for monitoring rate limiting events and system health.
📊
Non-Functional Requirements
  • Handle up to 2 billion daily active users (DAU).
  • Support peak write QPS of approximately 925,000 requests per second.
  • Achieve 99.99% availability for rate limiting service.
  • Maintain sub-100ms P99 latency for rate limit checks to avoid user experience degradation.
  • Scale horizontally to handle traffic spikes and growth without service disruption.
❓
Clarifying Questions to Ask
  • What are the primary entities to rate limit on (user ID, API key, IP address)?
  • Are rate limits global or per region/data center?
  • What is the expected burst tolerance and refill rate for token buckets?
  • Should rate limiting state be shared globally or partitioned per region?
  • Is eventual consistency acceptable for rate limit counters or is strong consistency required?
  • What is the expected retention period for rate limiting logs and metrics?
Out of Scope
✗ Designing the entire authentication or authorization system.
✗ Handling billing or quota enforcement beyond rate limiting.
✗ Designing client-side retry or backoff strategies.
✗ Detailed security mechanisms unrelated to rate limiting (e.g., encryption).
📌
Assumptions
  • 2 billion DAU
  • Each user sends 40 requests per day on average
  • Average request size is 100 bytes
  • Retention period for logs and metrics is 7 days
⚡
QPS Calculation
write qps2,000,000,000 × 40 / 86,400 ≈ 925,926 requests/sec
peak write qpsAssuming 2× peak traffic multiplier: 925,926 × 2 = 1,851,852 requests/sec
read qpsReads for rate limit checks assumed equal to writes: 925,926 requests/sec
💾
Storage Estimate
daily storage bytes925,926 req/sec × 100 bytes × 86,400 sec ≈ 8 TB/day
retention storage bytes8 TB/day × 7 days = 56 TB
with replication56 TB × 3 replicas = 168 TB total storage
🖥️
Server Estimate
rate limit check serversAssuming 10,000 req/sec per server: 1,851,852 / 10,000 ≈ 186 servers
storage nodesAssuming 2 TB usable storage per node: 168 TB / 2 TB = 84 storage nodes
🏗️
Architecture Diagram
Architecture Diagram
      +-------------+
      |  Clients    |
      +------+------+
             |
             v
      +------+-------+
      | API Gateway  |
      +------+-------+
             |
             v
      +------+-------+
      | Rate Limiter |
      +------+-------+
             |
        +----+----+
        |         |
        v         v
  +-----+-----+ +-----+-----+
  | Redis     | | Metrics DB|
  | (Token    | | (Cassandra|
  | Bucket)   | |  or Scylla)|
  +-----------+ +-----------+
🧩
Components
API Gateway
Entry point for all client requests, performs initial routing and authentication
Why thisEnvoy proxy supports high throughput and integrates with rate limiting filters natively
Why notNginx lacks native distributed rate limiting support and scales poorly at 1M+ QPS
Rate Limiter
Enforces rate limiting policies using token bucket algorithm per user/IP
Why thisCustom stateless service using Redis for token bucket counters enables sub-100ms latency
Why notUsing only API Gateway rate limiting is insufficient for distributed consistency and scale
Redis Cluster
Stores token bucket counters with TTL for automatic expiry and fast atomic increments
Why thisRedis supports atomic INCR and EXPIRE commands with sub-millisecond latency and horizontal scaling
Why notMemcached lacks atomic increment with TTL, making token bucket implementation error-prone
Metrics Database
Stores aggregated rate limiting logs and metrics for monitoring and alerting
Why thisCassandra or ScyllaDB provides high write throughput and horizontal scalability for time-series data
Why notRelational DBs like PostgreSQL cannot handle 925K writes/sec without complex sharding
Clients
End users or services generating requests subject to rate limiting
Why thisClients must receive immediate feedback (HTTP 429) to implement backoff and avoid overload
Why notAllowing unlimited client requests leads to cascading failures and system instability
🔄
Data Flow
1
Client → API Gateway
Client sends request to API Gateway
API Gateway authenticates and routes request
2
API Gateway → Rate Limiter
API Gateway forwards request metadata for rate limit check
Includes user ID or IP for token bucket key
3
Rate Limiter → Redis Cluster
Rate Limiter performs atomic token bucket decrement in Redis
If tokens available, request allowed; else rejected
4
Rate Limiter → API Gateway
Rate Limiter returns allow or reject decision
API Gateway responds with 200 or 429 accordingly
5
Rate Limiter → Metrics Database
Rate Limiter logs rate limit events asynchronously
Used for monitoring, alerting, and capacity planning

Practice

(1/5)
1. A chat system must handle 1 million concurrent user requests, each requiring low-latency token streaming from a large language model. Which component is best suited to buffer and stream tokens efficiently to clients?
easy
A. A relational database with row-level locking to ensure token order
B. A batch processing system that aggregates tokens before sending
C. An in-memory message queue with backpressure support like Redis Streams
D. A distributed file system to store token chunks for streaming

Solution

  1. Step 1: Identify token streaming requirements

    Token streaming demands low latency and ordered delivery with backpressure to avoid overwhelming clients.

  2. Step 2: Evaluate component suitability

    Relational DBs (A) add latency and locking overhead; distributed file systems (C) are too slow for real-time streaming; batch processing (D) adds unacceptable delay. Redis Streams (B) supports in-memory buffering with backpressure and ordered delivery.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Redis Streams supports ordered, low-latency token streaming with backpressure [check]
Hint: In-memory queues handle streaming better than DBs or batch [check]
Common Mistakes:
2. For real-time analytics requiring low-latency dashboards and complex ad-hoc queries, which architecture is best suited?
medium
A. Use only Kafka Streams for both aggregation and serving queries
B. Use Flink to write directly to a NoSQL key-value store for dashboards
C. Use batch ETL jobs to load data into a relational database for dashboards
D. Use Flink for streaming aggregation and an OLAP store for dashboard queries

Solution

  1. Step 1: Evaluate streaming aggregation and query needs

    Flink excels at complex streaming aggregations; OLAP stores support fast ad-hoc queries and low-latency dashboards.

  2. Step 2: Eliminate other options

    Kafka Streams lacks complex query capabilities; batch ETL adds latency unsuitable for real-time; NoSQL key-value stores lack rich query support for dashboards.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Flink + OLAP store balances streaming and query complexity [check]
Hint: Flink streams, OLAP queries for real-time + ad-hoc [check]
Common Mistakes:
3. For a proximity service requiring low-latency queries and frequent updates of business locations, which spatial indexing approach is better and why?
medium
A. Use Geohash-based indexing because it supports efficient prefix queries and simpler updates
B. Use a full R-tree index because it guarantees minimal overlap and tight bounding rectangles
C. Use a grid-based fixed cell index because it provides exact bounding box queries without hierarchy
D. Use a Quadtree because it supports fast insertions and deletions with balanced trees

Solution

  1. Step 1: Compare update and query costs

    Quadtree (Use a Quadtree because it supports fast insertions and deletions with balanced trees) can become unbalanced and expensive to update frequently. R-tree (Use a full R-tree index because it guarantees minimal overlap and tight bounding rectangles) is complex and costly to maintain with frequent writes.

  2. Step 2: Evaluate Geohash benefits

    Geohash (Use Geohash-based indexing because it supports efficient prefix queries and simpler updates) encodes locations into fixed-length strings allowing efficient prefix queries and simpler incremental updates, ideal for low-latency and frequent writes.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Geohash supports efficient prefix queries and simpler updates [check]
Hint: Geohash enables fast prefix queries and simpler frequent updates [OK]
Common Mistakes:
4. Without explicitly defining system constraints during your 45-minute design answer, what failure mode is most likely to occur in your final design?
medium
A. The system will automatically scale without bottlenecks
B. Design decisions will conflict, causing unclear trade-offs and incomplete coverage
C. You will produce a perfect design that requires no iteration
D. The system will default to a microservices architecture regardless of needs

Solution

  1. Step 1: Trace impact of missing constraints

    Without constraints, design choices conflict and trade-offs are unclear, leading to incomplete or inconsistent design.

  2. Step 2: Exclude unrealistic outcomes

    Automatic scaling or perfect design without iteration is unrealistic; architecture does not default automatically.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Missing constraints -> conflicting design decisions [check]
Hint: Constraints prevent conflicting designs [check]
Common Mistakes:
5. At 10x traffic scale, which component of a global server load balancing system is most likely to fail first and why?
hard
A. The data center ingress routers, since network bandwidth scales linearly and saturates quickly
B. The health monitoring system, due to increased frequency of health checks overwhelming it
C. The GSLB control plane, as it struggles to process and update routing decisions for all data centers in real-time
D. The DNS servers, because they cannot handle the surge in query volume and caching limits failover speed

Solution

  1. Step 1: Analyze scaling challenges

    Health monitoring (The health monitoring system, due to increased frequency of health checks overwhelming it) scales with checks but can be optimized; control plane (The GSLB control plane, as it struggles to process and update routing decisions for all data centers in real-time) is distributed and designed for scale; ingress routers (The data center ingress routers, since network bandwidth scales linearly and saturates quickly) scale with network upgrades.

  2. Step 2: Identify DNS bottleneck

    DNS servers face query volume spikes and caching TTLs limit failover responsiveness, making them the first to fail under 10x load.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    DNS query volume and caching limits cause first failure at scale [check]
Hint: DNS query volume overloads servers first at scale [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