Katkat
Back

Scale a Cache or Rate Limiter Across Multiple Machines

MetaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSystem Design

Last updated

Tests your ability to design a horizontally scalable distributed rate limiter and caching layer, focusing on data partitioning, hot-key mitigation, failure modes, and consistency trade-offs.

Scenario

Design a distributed rate limiting and state-caching service capable of protecting core API infrastructure across multiple data centers. The service must evaluate whether incoming requests from millions of concurrent clients should be allowed, throttled, or rejected in real time based on configurable sliding-window rules (e.g., maximum 5,000 requests per minute per tenant, or 100 requests per second per IP).

Requirements

Functional Requirements

  • Rule Evaluation: Support configurable rate-limit policies based on various keys (user ID, tenant ID, IP address, API route).
  • Action Execution: Return whether a request is allowed along with standard rate-limit headers (X-RateLimit-Remaining, X-RateLimit-Reset).
  • Config Updates: Support dynamic rule updates without requiring a service restart.

Non-Functional Requirements & Scale

  • Throughput: Support 10 million queries per second (QPS) globally across multiple regions.
  • Low Latency: Limit evaluation overhead to less than 5ms (p99).
  • High Availability: Provide 99.999% availability. In the event of cluster failure, provide configurable degraded modes (fail open vs. fail closed).
  • Fault Tolerance: Tolerate individual node failures, network partitions, and traffic spikes targeting a single key (hot keys).

Key Architectural Considerations to Cover

  1. Data Model & Algorithms: Choose and justify an algorithm (e.g., Token Bucket, Leaky Bucket, Sliding Window Counter) considering memory footprint and accuracy.
  2. State Partitioning & Sharding: Explain how key state is partitioned across cluster nodes (e.g., consistent hashing) and how virtual nodes prevent imbalance.
  3. Hot-Key Mitigation: Detail how you handle extreme hot keys (e.g., sudden viral events or distributed denial-of-service attempts against a single entity) to avoid node saturation.
  4. Consistency vs. Latency: Discuss the trade-offs between local in-memory caching/batching and centralized state stores (e.g., Redis/Memcached cluster). Explain how cross-region latency is addressed.
  5. Failure & Degradation Strategy: Specify behavior during cache misses, partitioned storage shards, and node dropouts.

Hints

Hint 1

Consider how consistent hashing distributes keys, but note how a single tenant can still exhaust a single shard's resources unless hot keys are detected and handled separately.

Hint 2

Think about local in-memory token batching at the edge or application tier to reduce write pressure on the centralized distributed cache.

Hint 3

Evaluate the operational and performance trade-offs between strict atomic increments (centralized consensus) versus approximate counters with local aggregation.

Follow-up questions

  • How would you dynamically detect and split traffic for a suddenly hot key across multiple cache nodes without violating rate limits?
  • If a client splits traffic across two geographic regions simultaneously, how do you enforce a global limit without paying the latency cost of cross-region synchronous writes?
  • How does your architecture handle sudden network partitions between API gateways and the rate-limiting tier—when would you fail open versus fail closed?