Design a distributed rate limiter

Clarifying questions

• Are limits hard rejects or soft throttles with a retry-after hint?
• Do tenants need custom quota windows or a small fixed menu?
• Should internal service traffic share the same global budget?

Functional requirements

• Evaluate allow or deny decisions on every API request.
• Support tenant, user, endpoint, and global policy scopes.
• Return remaining quota and retry-after metadata to callers.

Nonfunctional requirements

• Keep limiter decision latency under 10 ms at the gateway.
• Fail closed for abuse-heavy tenants and fail open for trusted internal health checks.
• Sustain short bursts without losing the long-term quota guarantee.

Scale assumptions

• 50,000 peak requests per second across all tenants.
• Top 1 percent of tenants produce half of traffic.
• Most policies use one-minute and one-hour windows.

API sketch

• POST /v1/limit/check { tenantId, userId, route, requestId } -> { allowed, retryAfterMs, remaining }
• PUT /v1/limit/policies/{tenantId} for policy updates by administrators.

Data model

• Policy table keyed by tenantId and route pattern.
• Counter keys shaped as limit:{scope}:{id}:{windowStart}.
• Decision log keyed by requestId for idempotent gateway retries.

Architecture components

• API gateway calls a local limiter library before forwarding traffic.
• The library uses Redis scripts for atomic increment and expiry.
• Policy changes flow through a config service and local gateway cache.

Bottlenecks

• Hot tenants can concentrate all writes on a small set of counter keys.
• Policy cache misses can put the control-plane database on the request path.

Failure modes

• Redis timeout: apply tenant-specific fallback policy and emit a degraded-mode metric.
• Duplicate gateway retry: reuse the requestId decision record.
• Policy propagation delay: include policy version in decision logs.

Observability

• Limiter latency p50/p95/p99 by gateway and tenant tier.
• Allowed, denied, fallback, and Redis-timeout decision counts.
• Top hot keys and policy cache hit rate.

Security / privacy

• Keep user identifiers hashed in logs.
• Restrict policy mutation to tenant admins and platform operators.

Cost considerations

• Redis memory scales with active scope-window pairs, not with all registered tenants.
• High-cardinality metrics need tenant-tier labels rather than raw tenant ids.

Tradeoffs

• Token bucket handles bursts better than fixed windows but is harder to explain to tenants.
• Approximate local prechecks reduce Redis load but can produce short overages.

Rubric