Design a Distributed Rate-Limiting Service

Scenario

At a large-scale visual discovery platform, millions of clients interact with internal services through distributed API gateways. You need to design a distributed rate-limiting service that enforces multi-tiered policies across individual users, partner tenants, specific API routes (e.g., pin creation vs. feed browsing), and platform-wide global thresholds.

Because the rate limiter sits directly in the critical request path, it must execute checks with minimal latency overhead while surviving infrastructure failures gracefully.

Functional Requirements

• Multi-Level Policies: Evaluate limits hierarchically (e.g., IP/User -> Tenant/API Key -> Route -> Global limit).
• Response Metadata: Return standard headers indicating allowed status, remaining quota, and time until reset (X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset).
• Dynamic Configuration: Support runtime policy updates without gateway or cluster restarts.
• Configurable Enforcement: Support both blocking (hard throttle) and shadow/dry-run modes for new policies.

Non-Functional Requirements & Scale

• Traffic Scale: 500,000 queries per second (QPS) peak across 3 global regions.
• Latency: p99 evaluation latency under 2 ms.
• Availability: 99.999% uptime. System failures must not take down the core API.
• Accuracy vs. Performance: Bounded quota overshoot (e.g., within 5–10% of configured limits during transient network partitions).

Key Design Areas to Cover

1. Algorithm Selection: Compare Token Bucket, Leaky Bucket, and Sliding Window Counter. Analyze trade-offs in memory usage, burst handling, and computational overhead.
2. Architecture & Storage: Design the coordination mechanism between edge gateways and the rate-limiting tier (e.g., local in-memory caching with asynchronous lease renewal vs. centralized Redis clusters).
3. Hot Keys & Traffic Skew: Mitigate cache contention and hotspot bottlenecks caused by abusive bots or ultra-high-volume partner tenants.
4. Failure Modes & Partition Tolerance: Define behavior during regional partitions (bounded regional quotas vs. cross-region consensus) and criteria for choosing fail-open vs. fail-closed modes per route type.