Katkat
Back

Design a large-scale distributed rate limiter

GoogleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSystem Design

Last updated

This question tests the ability to design a high-throughput, distributed rate-limiting service that handles multi-tenancy, ensures low latency, and manages consistency trade-offs.

Problem Statement

Design a global, distributed rate-limiting service that protects Google’s microservices from traffic spikes and abuse. The system must support millions of requests per second across multiple data centers.

Requirements

  • Functional Requirements:
    • Support various rate-limiting rules (e.g., requests per second, requests per minute, per user, per API key, or per IP).
    • Provide a "deny," "allow," or "soft-limit" (allow but throttle/warn) decision.
    • Must support multi-tenancy, where different services define their own rate limits.
  • Non-Functional Requirements:
    • Latency: The rate-limiting decision must be made in under 5ms, as it sits in the hot path of incoming requests.
    • Scalability: Must handle massive traffic volume horizontally.
    • Accuracy: The system needs to be reasonably accurate. In high-contention scenarios, provide a clear trade-off between strictness (consistency) and throughput (availability).

Scope of Response

Your design should include:

  1. High-level Architecture: How do request-handling nodes interact with the rate-limiting service?
  2. Storage Strategy: Where is the state stored, and how do you handle cache-misses or local versus global state?
  3. Algorithms: Propose an algorithm (e.g., Token Bucket, Fixed Window, Sliding Window) and explain why it fits your chosen architecture.
  4. Fail-Open vs. Fail-Closed: How should the system behave if the rate-limiter service is unreachable?

Hints

Hint 1

Consider the trade-offs between centralized state (e.g., a shared Redis cluster) and decentralized/local state (e.g., in-memory counters on each application node).

Hint 2

Think about the impact of network latency if your rate-limiting logic requires a cross-DC coordination for every request.

Hint 3

Evaluate using a hierarchical approach, where local limits are enforced first, and a global sync happens asynchronously to reconcile the state.

Follow-up questions

  • How would you handle a 'thundering herd' problem if a rate-limit state is suddenly reset or a large user starts bursting?
  • How would you implement 'burstiness' control for users who have a high average rate limit but should not consume their entire quota in a single millisecond?
  • If you were to move the rate-limiter to the edge (CDN), how would that change your consistency model?