System Design Patterns

English

日本語

English

日本語

Appearance

Rate Limiting: Admission Policy and Distributed Budgets ​

TL;DR ​

Rate limiting decides whether new work may enter a protected scope. A complete design names the subject, resource, cost unit, sustained rate, burst allowance, decision scope, and failure behavior. “100 requests per second” is incomplete if one request costs a thousand times another, ten gateway replicas each enforce their own 100, or an unavailable counter silently changes the policy.

Token buckets are the common admission primitive because they express both rate and burst. The distributed challenge is accounting: a linearizable global decision is accurate but adds a dependency to every request; local decisions are available and fast but overshoot unless they spend bounded leases allocated by a global authority. Put cheap local protection in front of shared policy, expose honest retry guidance, and treat policy rollout and counter recovery as production migrations.

Rate limiting governs admission and quota accounting. Circuit Breakers own dependency health and in-flight concurrency, Backpressure owns bounded queues and producer signaling, and Retries, Timeouts, and Hedging owns later attempts.

1. Admission Contract ​

Define the decision before choosing an algorithm:

FieldRequired answer
SubjectUser, tenant, credential, IP prefix, device, workload, or a hierarchy of them.
ResourceRoute, operation, model, bytes, database partition, global service, or daily entitlement.
Cost unitRequest, byte, row, CPU estimate, token, recipient, or another stable weighted unit.
PolicySustained rate, burst, quota period, priority, and whether unused entitlement carries forward.
ScopeProcess, host, zone, region, or global; exact or bounded-error enforcement.
DecisionReject, degrade, redirect, or shape. Queueing belongs to backpressure, not an implicit limiter buffer.
ResponseMachine-readable reason, policy identity, retry guidance, and remaining budget if safe to expose.
Failure behaviorFail open, fail closed, spend a cached lease, or enter a restricted emergency policy.
Change semanticsWhen a new policy becomes effective and how already leased capacity is handled.

Invariants ​

  1. Every admitted unit is charged to all mandatory policy dimensions exactly once at the declared accounting boundary.
  2. Distributed overshoot is bounded and derived from lease or replica configuration.
  3. A client cannot select another gateway, identity form, or region to multiply entitlement.
  4. Clock rollback cannot mint credit or extend a quota window.
  5. Policy and counter state are versioned so a stale data plane cannot enforce an incompatible rule indefinitely.
  6. Cardinality and stored state remain bounded under attacker-controlled identifiers.
  7. A rejection is cheaper than the work it protects.

Rate limits are policy, not capacity discovery. Derive them from downstream safe goodput, fairness, commercial entitlement, and recovery headroom; do not use a limiter to guess where saturation begins.

2. Data Plane and Control Plane ​

The data plane must continue with a deliberate degraded policy when the control plane is impaired. If every request synchronously fetches policy, a policy-store incident becomes a full application outage. If cached policy never expires or carries no version, revocation and emergency reduction may not take effect.

3. Rate, Burst, Quota, and Concurrency Are Different ​

  • Rate bounds admitted work per unit time.
  • Burst permits temporary accumulation of unused rate credit.
  • Quota bounds total entitlement over a longer business interval.
  • Concurrency bounds simultaneous in-flight work and adapts to service time; Circuit Breakers governs it.
  • Backpressure slows producers or bounds queued work; Backpressure covers its end-to-end propagation.

A service may need all four. A rate limiter alone can overload a slow dependency: under Little’s Law, admitted concurrency is approximately arrival rate × service time. If service time grows tenfold while rate stays fixed, in-flight work grows tenfold. Pair an entitlement limiter with a concurrency guard at the dependency boundary.

Multi-dimensional policy ​

A request may consume:

  • one global service budget;
  • one tenant budget;
  • one route budget;
  • a weighted compute budget;
  • a security/abuse budget.

Define whether all dimensions must succeed atomically. Sequentially consuming global credit and then discovering the tenant is empty leaks global credit unless the first reservation can be rolled back safely. Options are:

  • one atomic script/transaction for co-located counters;
  • reserve all dimensions under one decision ID and commit/expire them;
  • order checks from cheapest/coarsest to most specific and accept documented conservative under-utilization;
  • use independent hierarchical leases whose parent already bounds their sum.

Do not reveal another tenant’s remaining capacity through response headers or timing.

4. Canonical Algorithms ​

Token bucket ​

Let:

  • r be credit added per second;
  • B be maximum stored credit;
  • x be the request’s weighted cost;
  • t_last and b_last be the prior update.

At monotonic time t:

b_now = min(B, b_last + r × max(0, t − t_last))

Admit if b_now ≥ x, then store b_now − x. The state update and decision must be atomic.

The bucket permits at most B + rT units over any interval of length T, subject to initialization policy. A full bucket’s burst duration at rate r is B/r; choose B from downstream queue/concurrency headroom, not convenience.

Use weighted tokens when work varies, but validate estimates against actual resource consumption. If clients declare their own cost, the server must constrain or recompute it.

Leaky-bucket shaping and GCRA ​

A shaper schedules admitted units at a controlled departure rate rather than rejecting them immediately. This is appropriate only when a bounded delay still meets the caller deadline. Its queued bytes and wait time are backpressure state and must be capped.

The Generic Cell Rate Algorithm represents a conforming schedule with a theoretical arrival time. Each unit advances that time by an emission interval; burst tolerance allows arrivals a bounded distance before it. It stores compact state and avoids a log of timestamps, but weighted work and distributed updates still require atomic accounting.

Fixed and sliding windows ​

A fixed-window counter is simple but permits a boundary burst: nearly a full allowance just before reset and another just after. A rolling log is exact for recorded events but costs memory and deletion work proportional to activity. A sliding-window counter interpolates adjacent buckets, reducing boundary error without storing every arrival.

Use window counters for contractual calendar quotas, reporting, or when their error is explicitly acceptable. Do not present one algorithm as universally “best”; state the maximum burst and approximation error the product accepts.

Avoid client-clock authority ​

Use a monotonic server clock for replenishment. For distributed durable state, server-side store time or logical expiries are safer than a caller timestamp. Civil-time quota boundaries require explicit timezone and repeated/missing-hour behavior; a daily entitlement is not the same mechanism as a per-second traffic shaper.

5. Distributed Accounting ​

Linearizable central decision ​

Every request atomically updates one authoritative counter. This gives the clearest global bound and easy revocation, but adds network latency, store throughput, and a new availability dependency. Hot tenants create hot keys even if the counter store is horizontally scalable.

Use it when the entitlement is financially or operationally strict and the decision rate fits the authority. Partition by policy key while preserving atomicity across mandatory dimensions.

Independent local buckets ​

Each of N replicas enforces a local rate r_local. If every replica uses the full global rate, total admission can reach N × r_global, and autoscaling silently raises the limit. Dividing by an expected replica count fails during rollout, skew, and partial outage.

Independent buckets are appropriate for per-instance self-protection, not an exact tenant-global entitlement.

Leased credit ​

A global allocator grants each enforcement point a bounded amount of spend:

  1. Data plane requests a lease containing policy version, subject/resource, credit, epoch, and expiry.
  2. Allocator atomically subtracts that credit from the parent budget.
  3. Data plane admits locally until credit or lease time is exhausted.
  4. It reports usage and requests more before depletion.
  5. Expired or revoked leases cannot be reused; unused credit is reclaimed only by a protocol that prevents double spend.

If at most q_i unreported credit exists at enforcer i, crash/failover overshoot or stranded-credit error is bounded by:

distributed error bound ≤ sum of outstanding lease credit + in-flight decision race

Smaller leases improve accuracy and revocation speed but increase allocator QPS and sensitivity to latency. Larger leases improve availability and locality but reserve more unused capacity and enlarge the error bound.

Regional hierarchy ​

For global traffic, allocate global → region → cell/process. Enforce cheap local safety before spending regional/global entitlement. Rebalance using measured demand, but keep emergency reserve rather than allocating the entire parent budget.

During a partition choose explicitly:

  • fail closed: preserve strict quota, sacrifice availability;
  • cached lease: preserve bounded service until credit expires;
  • fail open: preserve availability with unbounded entitlement risk;
  • restricted policy: allow critical operations, deny optional or expensive work.

This is a product and security choice, not an implementation default.

6. Fairness, Identity, and Abuse ​

Rate-limit keys must follow authenticated identity. IP-only limits combine many users behind NAT, allow address rotation, and can let an attacker exhaust a victim’s shared prefix. Use IP/network reputation as one abuse signal, not the commercial tenant identity.

Hierarchical fairness prevents one subject from taking every resource:

  • reserve a minimum or weighted share per class;
  • permit borrowing from unused shared capacity;
  • revoke borrowed credit when owners become active;
  • cap expensive routes with weighted cost;
  • isolate administrative and recovery traffic from public traffic.

High-cardinality keys are a denial-of-service vector against the limiter itself. Validate key length, canonicalize identity, bound inactive-state retention, aggregate unauthenticated traffic, and cap dynamic policy descriptors.

Quota enforcement is not authorization. A valid token balance never grants access to the underlying resource.

7. Response and Client Contract ​

For HTTP, 429 means the client exceeded a rate policy. A temporarily overloaded service may instead use a service-unavailable response according to its API contract. Include:

  • a stable reason/policy code;
  • whether retry is permitted;
  • Retry-After when the server can provide meaningful guidance;
  • standardized RateLimit fields where deployed and safe;
  • correlation and decision IDs for support.

Remaining-credit values are observations, not reservations. Concurrent requests can spend them before the next call.

Clients must obey the attempt policy in Retries, Timeouts, and Hedging. A retry at exactly the reset instant can synchronize a herd; retry guidance should still be combined with client jitter and deadline checks.

8. Concrete Failure Trace: Scaling Multiplies the Limit ​

  1. A gateway process has a local bucket allowing R requests/s for tenant T.
  2. The fleet runs four replicas, so T can reach roughly 4R by spreading connections.
  3. A burst increases CPU and Auto-Scaling adds eight replicas.
  4. Aggregate entitlement becomes roughly 12R exactly while the downstream is stressed.
  5. Requests slow; in-flight work rises; retries add more attempts.
  6. The downstream fails despite every gateway reporting that its limiter is healthy.

The bug is a mismatch between declared global scope and process-local state. Fix it with a global authority or bounded regional/process leases. Keep a separate local self-protection bucket so a global-accounting outage cannot flood one instance.

9. Capacity and Cost Model ​

Let:

  • lambda: offered requests/s;
  • r: admitted weighted units/s;
  • B: burst units;
  • S: mean admitted service time;
  • K: active subject/resource counter cardinality;
  • u: atomic store operations per exact decision;
  • q: average lease size;
  • N: enforcement points.

Expected admitted concurrency is approximately r × S for stable traffic. A burst can add up to B near-simultaneous units, so downstream concurrency or queue headroom must absorb the chosen burst.

An exact central limiter needs approximately r × u store operations/s plus rejected-decision traffic if denials also read/update state. With leases, allocator request rate is approximately:

allocator QPS ≈ admitted weighted units/s ÷ average lease size

but hot-key skew, unused leases, refresh-before-empty, and failover increase it.

State memory is roughly K × bytes per counter plus indexes, expiry structures, policy cache, and replicas. Estimate attacker-created inactive keys and cleanup cost, not only paying tenants.

Cost includes decision latency, counter storage/replication, cross-region traffic, audit retention, unused reserved credit, rejected-request CPU/TLS, and engineering for reconciliation. If the limiter call costs more than the request it rejects, add an earlier local guard.

10. Operations and Migration ​

Safe policy rollout ​

  1. Publish a versioned policy with effective time and compatibility metadata.
  2. Evaluate in shadow mode and record would-allow/would-deny decisions.
  3. Compare impact by tenant, route, cost, and region.
  4. Enforce for a controlled cohort while retaining a kill switch.
  5. Reconcile leased credit across old/new versions.
  6. Expand only when rejection and downstream-goodput effects match the model.

Changing a key, cost unit, or quota window is a state migration. Dual-account old and new keys before cutover; otherwise subjects can reset usage simply by crossing the version boundary.

Recovery ​

  • Counter-store loss: restore durable entitlement state, then reconcile audit/usage; do not invent remaining paid quota.
  • Allocator partition: use only valid cached leases and explicit emergency behavior.
  • Clock anomaly: clamp negative elapsed time and alert; never refill from rollback.
  • Policy-store outage: serve last verified snapshot until its safety expiry.
  • Hot subject: isolate shard/key and reduce lease size or move to a dedicated authority.

11. Security and Governance ​

  • Authenticate before charging a privileged identity; apply a cheap unauthenticated guard before expensive authentication.
  • Sign or mutually authenticate lease and policy distribution.
  • Prevent tenants from choosing policy descriptors or weighted cost.
  • Encrypt counter, lease, policy, and audit traffic; usage reveals customer behavior.
  • Separate policy authorship, emergency override, and audit permissions.
  • Audit policy changes, manual credit grants, fail-open activation, key rewrites, and counter resets.
  • Retain decision evidence according to billing, fraud, privacy, and dispute requirements.

Never expose a global limiter service directly to untrusted callers.

12. Observability ​

Measure:

  • offered, admitted, rejected, degraded, and shaped weighted units;
  • rejection by policy version, subject class, resource, region, and reason;
  • bucket/lease utilization and outstanding credit;
  • overshoot, stranded credit, reconciliation difference, and stale-policy age;
  • decision latency and error by local/global path;
  • counter-store QPS, hot keys, conflicts, expiry backlog, and cardinality;
  • downstream goodput, latency, concurrency, and saturation alongside admission.

Avoid unbounded subject IDs in metrics labels. Put high-cardinality detail in sampled logs or an audit store.

A rising rejection rate may mean policy is working. The alert condition is a contract violation: unexpected protected-traffic rejection, error bound exceeded, stale policy, allocator exhaustion, or downstream saturation despite admission.

13. Verification ​

  • prove the token-bucket interval bound with deterministic and randomized arrival sequences;
  • race concurrent spends on the same key;
  • test monotonic-clock rollback and civil-time quota transitions;
  • distribute one subject across every replica and region;
  • add/remove replicas during a burst and verify entitlement is unchanged;
  • partition enforcers from the allocator and measure the declared error bound;
  • crash an enforcer with unused and just-spent lease credit;
  • roll policy/key/cost versions while traffic continues;
  • generate attacker-controlled unique identities and verify bounded limiter state;
  • overload the counter store and exercise fail-open/closed/restricted behavior;
  • compare audit usage with authoritative billing/resource totals;
  • verify rejected work is materially cheaper than admitted work.

Test the full composition with retry budgets and downstream concurrency limits. A mathematically correct bucket can still participate in an overload loop if clients ignore rejection guidance.

14. Decision Framework ​

RequirementPreferred mechanism
Per-process self-protectionLocal token bucket
Strict global commercial quotaLinearizable authoritative counter
High-rate global entitlement with bounded errorHierarchical leased credit
Smooth egress into a batchable dependencyBounded shaper plus backpressure
Calendar usage entitlementVersioned window/quota ledger
Variable request costWeighted units validated by server
Limit must follow changing service latencyConcurrency control, not a fixed rate
Control plane may be unavailableCached policy and bounded leases with declared emergency behavior

Select the weakest coordination that still satisfies the entitlement and error contract. Add an exact global decision only where its precision is worth the latency and availability dependency.

Primary References ​

A practical reference for distributed system design. Released under the MIT License.

Copyright 2024-present Babushkai