Katkat
Back

Design a rate limiter

RobloxSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSystem Design

Last updated

This problem tests your ability to design a distributed rate-limiting service that maintains request counts across multiple application nodes while balancing system performance and accuracy.

Design a Distributed Rate Limiter

Design a rate-limiting service for a high-traffic gaming platform. The platform receives millions of requests per second, and we must ensure that no single user (identified by user_id) exceeds a pre-defined quota (e.g., 100 requests per minute).

Functional Requirements

  1. Enforce a per-user request limit within a rolling time window.
  2. Return an HTTP 429 (Too Many Requests) status code when the limit is reached.

Non-Functional Requirements

  1. Low latency: The rate limiter must add minimal overhead to the request path.
  2. Scalability: The system must handle increasing traffic without significant performance degradation.
  3. Accuracy: While high precision is desired, the system should favor availability and performance under extreme load.

Expectations

Your design should cover:

  • Choice of rate-limiting algorithm (e.g., Fixed Window, Sliding Window, Token Bucket, or Leaky Bucket).
  • Data storage strategy: Where and how to store the request counts for high-concurrency access.
  • Distributed coordination: How multiple application servers synchronize state.
  • Handling failure: What happens if the rate-limiting service or the data store goes down?

Hints

Hint 1

Consider the trade-offs between centralized state (e.g., Redis) versus local, in-memory counters on each application server.

Hint 2

If you use a centralized store, think about how to minimize network round-trips for every incoming request.

Hint 3

Evaluate whether your chosen algorithm requires exact historical data or if an approximate count suffices for performance reasons.

Follow-up questions

  • How would you handle the 'thundering herd' problem if the rate limiter storage becomes a bottleneck?
  • If you need to support different tiers of users (e.g., premium vs. free), how would your schema or algorithm adapt?
  • How could you modify your design to handle a 'burst' of traffic while still maintaining a long-term average rate limit?