Katkat
Back

Design a Distributed Rate Limiter

PinterestSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSystem Design

Last updated

This problem evaluates your ability to design a distributed rate-limiting service that maintains low latency while enforcing consistent request quotas across multiple global nodes.

Distributed Rate Limiter

Design a rate-limiting service that can be integrated into a distributed system to prevent abuse and manage API usage. The system must support various clients (e.g., mobile apps, web servers) and enforce different rate policies per user ID or API key.

Functional Requirements

  • Enforce a specific number of requests per unit of time (e.g., 100 requests per minute).
  • Support multiple rate-limiting algorithms (e.g., Fixed Window, Token Bucket, or Leaky Bucket).
  • Support different scopes: global limits, per-user limits, and per-API endpoint limits.

Non-Functional Requirements

  • Low Latency: The rate-limiting check should be extremely fast, ideally under 10ms, as it sits in the critical request path.
  • High Availability: The system should remain functional even if a node fails.
  • Scalability: It should handle thousands of requests per second across multiple data centers.
  • Accuracy: The system should handle concurrent requests correctly to avoid exceeding quotas due to race conditions.

Deliverables

  1. A high-level architecture diagram or description showing the interaction between the API gateway/application servers and the rate-limiting service.
  2. Choice of data store and explanation for why it fits the consistency/latency trade-offs.
  3. Handling of concurrency—how to ensure an atomic update to the request count or token bucket.
  4. Strategy for handling cache misses or service outages (e.g., fail-open vs. fail-close).

Hints

Hint 1

Consider using an in-memory store like Redis to provide sub-millisecond read/write access for tracking request counts.

Hint 2

Think about how the 'Distributed' part of the name affects your ability to ensure atomicity during race conditions between multiple application servers.

Hint 3

Evaluate whether your design should perform the check locally on the gateway node (using asynchronous sync) or rely on a centralized store for every request.

Follow-up questions

  • How would you handle a 'thundering herd' problem if the rate limiter itself becomes a bottleneck?
  • If the rate limiter is deployed globally, how do you handle clock skew between different servers when using time-window based algorithms?
  • How would you implement a 'graceful degradation' policy if the distributed cache is unreachable?