Rate-limiting algorithms and distributed correctness

Rate limiting is admission control. First define the subject (user, tenant, credential, IP or a hierarchy), protected resource, cost unit, burst policy, enforcement region and failure policy. Authentication and authorization remain separate checks.

Every distributed decision is a concurrency problem. A read followed by a write can over-admit under races. Refill, trim, count, increment and expiry changes must be one atomic state transition, for example a storage transaction or server-side script. Use a trusted time policy and test clock regressions and region skew.

Fixed window

One counter per key and time window is compact. Requests near the end of one window and start of the next can concentrate up to roughly two full window allowances in a very short interval. Correct implementations atomically create/increment the counter and expiry; separating those actions can leak a key without TTL after a crash.

Sliding-window log

Store the accepted request timestamps, trim entries older than the rolling interval, count, and append the current request atomically. This gives exact rolling-window semantics, but retained memory is proportional to events in the window and operations work over stored entries. It is not an O(1)-memory counter.

A sliding-window counter approximation combines adjacent buckets with weights. It uses bounded state but is approximate; do not describe it as the exact timestamp-log algorithm.

Token bucket

State is token balance plus last-refill time. On each decision:

new_tokens = min(capacity, old_tokens + refill_rate × elapsed_time)

Then atomically subtract the request cost if enough tokens exist. Capacity controls maximum burst; refill rate controls sustainable average. Weighted requests need bounded, validated costs so a caller cannot bypass the policy.

Leaky-bucket shaping

A bounded queue schedules output at a configured pace. It smooths bursts but adds queueing latency. Reject when queue capacity or the request deadline would be exceeded. A queue that grows without a bound merely moves overload into memory and latency.

HTTP response

RFC 6585 defines status 429 Too Many Requests and says a response may include Retry-After. RFC 9110 defines Retry-After as an HTTP date or delay in seconds. Use it when the server knows a meaningful retry point; clients still need capped backoff and jitter.

As of this research snapshot, the IETF RateLimit response fields are an active Internet-Draft, not a published RFC. Treat draft header syntax as versioned interoperability work, not a settled standard claim.

Scenarios

Compact counters with a boundary-burst trade-off.

Exact rolling timestamps with event-proportional storage.

Bounded burst capacity and sustainable refill rate.

Bounded queueing and paced emission.

Explicit fail-open/fail-closed policy when shared limiter state is unavailable.

Production controls

• Compose per-user, per-tenant and global overload limits without double-count surprises.
• Apply limits at every bypassable ingress, and sign or trust forwarded identity headers.
• Make policy rollout versioned so replicas do not silently enforce incompatible quotas.
• Keep a local hard concurrency ceiling to protect the service even if global state fails.
• Measure allowed/rejected QPS, decision latency, state errors, hot keys, fallback use and false-positive reports.
• Load-test the protected service; a quota copied from another system is not capacity evidence.

Primary sources

• RFC 6585, 429 Too Many Requests: https://www.rfc-editor.org/rfc/rfc6585.html
• RFC 9110, Retry-After semantics: https://www.rfc-editor.org/rfc/rfc9110.html
• Redis INCR documentation and rate-limiter transaction example: https://redis.io/docs/latest/commands/incr/
• IETF HTTPAPI RateLimit header fields draft status: https://datatracker.ietf.org/doc/draft-ietf-httpapi-ratelimit-headers/