Katkat
Back

Design a Distributed Rate Limiter

AnthropicSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSystem Design

Last updated

Tests the candidate's ability to design a low-latency, highly available distributed rate-limiting service that coordinates shared state across geographically distributed API gateways while gracefully handling network partitions and datastore failures.

Scenario

You are tasked with designing a distributed rate-limiting service for a high-traffic AI platform API (e.g., an LLM inference service). The platform serves millions of developers globally and must enforce usage policies to protect backend infrastructure, prevent resource exhaustion, and enforce multi-tenant quotas.

Requirements

Functional Requirements

  • Support rate limiting based on various identifiers: API Key, User ID, and IP address.
  • Enforce configurable limits across different time granularities (e.g., requests per second, requests per minute).
  • Return standard HTTP response headers (X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset) and HTTP 429 (Too Many Requests) with a Retry-After header when limits are exceeded.
  • Support configurable policy actions: drop, delay (queue), or fail open/closed.

Non-Functional Requirements

  • Ultra-low latency: The rate limiter sits directly in the request path; overhead must be under 5ms (p99).
  • High availability: A failure in the rate-limiting infrastructure must not bring down the core API.
  • Scalability: Handle high concurrency across globally distributed edge gateways.
  • Accuracy & Consistency: Tolerate reasonable clock skew without drastically over- or under-counting requests.

Scale & Performance Assumptions

  • Peak traffic: 100,000 requests per second (RPS) globally.
  • 5,000,000 active rate-limit rules / API keys daily.
  • API gateways are distributed across 3 global regions (e.g., US-East, US-West, EU-Central).

What Your Design Should Cover

  1. Algorithm Selection: Compare Token Bucket, Leaky Bucket, Sliding Window Log, and Sliding Window Counter in terms of memory overhead and accuracy.
  2. Architecture & Storage: Choose the datastore (e.g., Redis cluster, local memory) and detail how state updates are made atomically (e.g., Lua scripts, Redis cell).
  3. Distributed Coordination & Multi-Region: Explain how limits are synchronized across regions without introducing cross-region round-trip latency on every request (e.g., local token pooling, batching).
  4. Failure Modes & Graceful Degradation: Explain what happens during Redis outages, network partitions, and heavy traffic spikes (fail open vs. fail closed strategies).

Hints

Hint 1

Consider combining local in-memory token allocation at the edge gateway with an asynchronous background sync to a central datastore to avoid cross-region latency on every request.

Hint 2

Evaluate atomic operations such as Redis Lua scripts or multi-key transactions to prevent race conditions during concurrent limit checks.

Hint 3

Decide on an explicit failure strategy (fail open vs. fail closed) depending on whether protecting platform availability or preventing user overage is the priority.

Follow-up questions

  • How would you extend this design to rate limit both Requests Per Minute (RPM) and Tokens Per Minute (TPM), given that token usage is only known after streaming completion?
  • If your rate-limiting cache cluster suffers a network partition, how do you prevent users from exceeding their allocated quota by hitting multiple isolated nodes?
  • How would you prevent 'thundering herd' issues when a high-traffic client's rate limit window resets?