API Gateway
Home › Technical Guides › Traffic Control
Traffic Control

Rate Limiting, Quotas, and Spike Arrest Algorithms at the API Gateway

Effective traffic shaping protects backend databases from noisy neighbors, credential stuffing, and flash traffic spikes while communicating clear retry signals to API clients.

Comparing Core Rate-Limiting Algorithms

Fixed-window counters use minimal memory but suffer from boundary burst doubling: a client can fire 100 requests at 12:00:59 and 100 more at 12:01:01. Sliding-window logs prevent boundary bursts by tracking exact timestamps, though memory scales linearly with traffic.

Token Bucket and Sliding Window Counter algorithms balance accuracy with O(1) memory. Token Bucket refills at a steady rate up to a burst limit for natural UI spikes, while Leaky Bucket (GCRA) enforces uniform spacing for spike arrest ahead of fragile upstreams.

  • Fixed Window: lowest memory, vulnerable to 2x boundary spikes
  • Sliding Window Counter: weighted interpolation across adjacent windows in O(1) memory
  • Token Bucket: steady average throughput with explicit burst headroom
  • Leaky Bucket / GCRA: strict pacing to flatten sudden traffic spikes

Local In-Memory vs. Distributed Counters

Multi-node gateways behind load balancers must decide how to share quota state. Querying Redis synchronously on every request adds network RTT and creates a runtime dependency.

Teams mitigate overhead using asynchronous counter batching (trading minor burst drift for local speed) or Redis Lua scripts on strict billing quotas—paired with a fast local spike-arrest fallback if Redis degrades.

  • Local memory counters deliver sub-100 microsecond spike protection
  • Atomic Redis Lua scripts prevent race conditions in shared quotas
  • Define explicit fail-open vs. fail-closed behavior per endpoint risk

Multi-Dimensional Keys and Standard RateLimit Headers

Avoid throttling authenticated APIs solely by IP, as corporate NAT gateways and mobile carriers share IPs across thousands of users. Key quotas by authenticated `sub`, API key, or tenant ID, reserving IP limits for anonymous routes like `/login`.

Return HTTP `429 Too Many Requests` with `Retry-After` and IETF `RateLimit-Limit`, `RateLimit-Remaining`, and `RateLimit-Reset` headers so client SDKs pause gracefully.

  • Key authenticated routes by tenant/API key; key anonymous endpoints by IP
  • Weight expensive search/export endpoints higher than lightweight reads
  • Emit `Retry-After` and IETF `RateLimit-*` headers on throttled responses

Combining Rate Limits with Concurrency Caps

Rate limits alone cannot protect thread pools when a slow database query stretches response time from 50 ms to 5 s, rapidly piling up concurrent connections.

Pairing request-rate limits with maximum in-flight concurrency caps per upstream service prevents socket and worker saturation during partial backend degradation.

API Gateway Rate Limiting Algorithm Matrix

AlgorithmMemory per KeyBurst HandlingDistributed ComplexityRecommended Role
Fixed Window CounterO(1) single integerUp to 2x at boundaryLow (atomic INCR + EXPIRE)Coarse daily/monthly API usage quotas
Sliding Window LogO(N) timestampsExact, zero boundary spikeHigh (sorted sets)Low-volume security-sensitive endpoints
Sliding Window CounterO(1) two integersSmooth approximationLow–ModerateGeneral per-minute per-tenant API limits
Token BucketO(1) tokens + timestampControlled burst capacityModerate (atomic Lua)Developer tiers allowing short UI bursts
Leaky Bucket / GCRAO(1) TAT timestampZero burst (strict pacing)Moderate (atomic Lua)Spike arrest in front of legacy backends

TAT denotes Theoretical Arrival Time in Generic Cell Rate Algorithm (GCRA) implementations.

Worked Illustration: Sizing a Token Bucket and Sliding Window Policy

This worked illustration calculates burst parameters for a B2B SaaS tier allowing 600 requests per minute with brief client batching.

  1. Step 1 (Refill Rate): Convert 600 requests per minute into a continuous refill rate of 10 tokens per second.
  2. Step 2 (Burst Capacity): Set bucket capacity to 50 tokens so loading a 30-widget dashboard succeeds while sustained floods drain the bucket rapidly.
  3. Step 3 (Fallback Ceiling): Across 5 nodes, configure a local emergency fallback of 4 tokens/s and 20 burst per node if Redis becomes unreachable.
  4. Step 4 (Response Headers): Return HTTP 429 with `Retry-After: 1` and `RateLimit-Remaining: 0` so client SDKs back off cleanly.

Engineering Illustration Summary: A 10 tokens/s refill with a 50-token burst accommodates legitimate UI spikes while bounding sustained load.

Traffic Control & Rate Limiting Verification Checklist

  • Select Token Bucket or Sliding Window Counter instead of unguarded Fixed Windows on critical routes.
  • Scope authenticated quotas by tenant or API key rather than shared corporate NAT IPs.
  • Assign stricter rate and cost weights to write endpoints, auth routes, and expensive queries.
  • Return HTTP 429 with `Retry-After` and `RateLimit-*` headers so client SDKs back off properly.
  • Pair time-window rate limits with maximum in-flight concurrency caps per upstream service.
  • Define explicit fail-open or fail-closed behavior if the distributed counter store is unavailable.

Frequently Asked Questions

What is the difference between rate limiting, quotas, and spike arrest?

Rate limiting caps short-term request frequency, quotas govern long-term billing usage, and spike arrest smooths micro-bursts so downstream servers are never flooded instantaneously.

Why does Fixed Window rate limiting allow twice the intended burst?

A client can send 100 requests at 00:59 and 100 more at 01:00 as the bucket resets, delivering 200 requests in two seconds.

Should health-check endpoints be excluded from rate limiting?

Yes. Exclude internal health probes or isolate them on an internal port so traffic spikes never trigger false-negative health failures.

How should clients handle HTTP 429 responses from the gateway?

Clients should honor `Retry-After` and apply exponential backoff with randomized jitter instead of retrying immediately.

Primary Standards & Specifications

  • RFC 9110 — HTTP Semantics (Status Code 429 / Retry-After Header, IETF)
  • IETF Draft — RateLimit Header Fields for HTTP (draft-ietf-httpapi-ratelimit-headers)
  • OWASP API Security Top 10 (2023) — API4:2023 Unrestricted Resource Consumption

Related Technical Guides