Wise Hustlers — Digital Product & App Development Studio Logo
Get Consultation
By Wise Hustler Admin•11/22/2026•32 min read

Distributed Rate Limiting at Scale: GCRA vs Sliding Window Counter vs Token Bucket in Redis and Envoy

Distributed Rate Limiting at Scale: GCRA vs Sliding Window Counter vs Token Bucket in Redis and Envoy

# Distributed Rate Limiting GCRA vs Sliding Window: Redis and Envoy Architecture at Scale

Summary: Distributed rate limiting at scale requires balancing memory footprint, computational overhead, and boundary precision. The Generic Cell Rate Algorithm (GCRA) provides the optimal production standard, reducing memory to a single 64-byte Redis key per client via Theoretical Arrival Time (TAT) arithmetic, eliminating sliding window log memory bloat. For multi-region ingress, Envoy's global Rate Limit Service (RLS) decouples rate checking via asynchronous gRPC, coordinating distributed quotas under high-throughput traffic with sub-millisecond overhead.

---

The Mathematics of Distributed Rate Limiting: Algorithmic Foundations

Managing traffic throughput across horizontally scaled API gateways introduces fundamental distributed state challenges. When stateless application instances or reverse proxies enforce quotas independently, local counters fail to reflect aggregate cluster traffic, permitting abusive spikes. Centralizing quota states in an external memory store like Redis resolves visibility, but introduces network round-trips and memory overhead. Choosing the right algorithm determines whether your storage layer survives traffic surges or collapses under memory exhaustion.

The Distributed Synchronization Dilemma

In a distributed topology where fifty API gateway workers process incoming traffic across multiple availability zones, synchronizing an active counter for an API key in real time requires atomic operations. A naive read-then-write pattern (GET key followed by SET key (val + 1)) creates severe race conditions under concurrent execution.

Distributed architectures counter this either by routing tenant requests deterministically to specific nodes (consistent hashing), which causes hot-spot vulnerabilities during traffic spikes, or by relying on atomic primitives executed within an in-memory data store like Redis. The choice of algorithm dictates the number of Redis instructions required per request, the memory consumed per active identity, and the mathematical accuracy of the quota envelope.

+--------------------------------------------------------------------------------+
|                      Rate Limiting Algorithmic Trade-Offs                      |
+--------------------------+-----------------------+-----------------------------+
| Algorithm                | Memory Complexity     | Boundary Accuracy           |
+--------------------------+-----------------------+-----------------------------+
| Fixed Window Counter     | O(1) - ~54 bytes      | Poor (200% boundary burst)  |
| Sliding Window Log       | O(N) - ~16 KB (N=100) | Exact (0% error)            |
| Sliding Window Counter   | O(1) - ~160 bytes     | Approximation (~0.003% err) |
| Token Bucket             | O(1) - ~148 bytes     | Smooth burst support        |
| GCRA (Leaky Bucket Dual) | O(1) - ~58 to 96 bytes| Exact (0% error)            |
+--------------------------+-----------------------+-----------------------------+

Fixed Window Counters: The Boundary Burst Vulnerability

The simplest rate limiter uses a fixed window counter. For a quota of 100 requests per minute, a key formatted as ratelimit:{client_id}:{minute_timestamp} increments on each request via Redis INCR, setting a 60-second time-to-live (EXPIRE).

The flaw in fixed windows is the boundary burst effect. If an automated client remains idle for 59 seconds, dispatches 100 requests during second 59, and then fires another 100 requests at second 61 (which falls into the subsequent window), the limiter permits 200 requests within a two-second interval. For downstream databases and microservices dimensioned for a peak load of 100 requests per minute, this instantaneous 200% surge can trigger database connection exhaustion, elevated thread pool queueing, and cascading outages.

Leaky Bucket vs. Token Bucket: Traffic Shaping vs. Burst Absorption

To prevent boundary surges, classical telecommunication algorithms separate burst tolerance from continuous egress rates:

  • Leaky Bucket: Models an open bucket with a small hole in the bottom. Inflow can arrive in bursts, but requests leave (leak) at a constant, fixed rate. In network traffic shaping, excess requests overflow and get dropped immediately. Leaky bucket algorithms smooth traffic into a deterministic flow, but they penalize legitimate user interactions that demand brief bursts of speed (such as loading a single-page dashboard executing parallel REST calls).
  • Token Bucket: Accumulates tokens at a steady fill rate up to a predefined burst capacity $C$. Each request consumes one or more tokens. If tokens are available, the request executes immediately without artificial queueing delay; if empty, the request is throttled.

Implementing a distributed Token Bucket in Redis typically requires storing two fields per client: last_updated_timestamp and available_tokens. Because replenishing tokens on a timer for millions of keys is computationally prohibitive, implementations calculate lazy replenishment during incoming requests:

$$\text{new\_tokens} = \min(C, \text{stored\_tokens} + (\text{current\_time} - \text{last\_updated}) \times \text{refill\_rate})$$

While conceptually clean, maintaining two distinct state variables requires Redis Hashes or custom serialized JSON strings, increasing serialization overhead and memory footprint.

Sliding Window Log: Exact Precision at an Extreme Memory Penalty

The Sliding Window Log resolves boundary bursts completely by logging the Unix timestamp of every request in a Redis Sorted Set (ZSET). When a request arrives at timestamp $t$ for a window duration $W$ with limit $L$:

1. Remove all elements older than the current window: ZREMRANGEBYSCORE key -inf (t - W)

2. Query the current set cardinality: ZCARD key

3. If cardinality is less than $L$, append the current request: ZADD key t uuid

4. Set expiration: EXPIRE key W

This delivers 100% boundary accuracy. However, memory complexity is $O(N)$, where $N$ is the number of requests processed within the active window. For an API tier servicing 100 requests per minute across 1,000,000 active API keys, Redis must store 100,000,000 sorted set nodes. As analyzed in the memory section below, this consumes approximately 16 GB of RAM and forces Redis through expensive skiplist deletions that degrade CPU cache efficiency.

Sliding Window Counter: Approximating Windows with Linear Interpolation

To eliminate $O(N)$ memory bloat while avoiding fixed window boundary spikes, Cloudflare popularized the Sliding Window Counter pattern. This technique tracks request counts across two fixed windows: the current window and the previous window.

When a request arrives at an offset within the current window, the algorithm calculates an estimated rate by weighting the previous window's counter inversely proportional to elapsed time:

$$\text{Estimated Count} = \text{Count}_{\text{current}} + \text{Count}_{\text{previous}} \times \left(1 - \frac{t - t_{\text{window\_start}}}{W}\right)$$

If $\text{Estimated Count} < L$, the request increments $\text{Count}_{\text{current}}$ and passes.

This reduces storage to two integers per client. The trade-off is an approximation: the algorithm assumes that traffic across the previous window was evenly distributed. In Cloudflare's landmark production analysis evaluating 400 million requests across 270,000 unique sources, linear interpolation exhibited an observed error rate of only 0.003%, demonstrating strong practical accuracy. While synthetic edge cases with extreme step-function surges concentrated in the final seconds of a window can theoretically understate short-term rates, the algorithm reliably dampens the 200% burst vulnerabilities of fixed windows.

Generic Cell Rate Algorithm (GCRA): Virtual Scheduling via Theoretical Arrival Time

The Generic Cell Rate Algorithm (GCRA) originates from Asynchronous Transfer Mode (ATM) network specifications (ITU-T Recommendation I.371 / ATM Forum Traffic Management 4.0). GCRA achieves the exact burst tolerance and traffic shaping of a Token Bucket, yet requires tracking only a single scalar value per entity: the Theoretical Arrival Time (TAT).

Instead of counting tokens or logging timestamps, GCRA models time as an arrival schedule.

Given:

  • Rate Limit: $L$ requests per Period $P$
  • Emission Interval ($T$): The nominal duration between consecutive requests:

$$T = \frac{P}{L}$$

  • Burst Tolerance ($\tau$ or Tau): The maximum duration a client can arrive ahead of its scheduled arrival time without being throttled:

$$\tau = T \times \text{burst\_capacity}$$

When a client makes its first request at time $t$, its initial $TAT$ is established:

$$TAT = t + T$$

For every subsequent request arriving at time $t$:

1. Determine the base theoretical arrival time:

$$\text{base\_TAT} = \max(t, TAT)$$

2. Compute the projected theoretical arrival time:

$$\text{projected\_TAT} = \text{base\_TAT} + T$$

3. Conformance Check:

$$\text{projected\_TAT} \le t + \tau$$

If the condition holds, the request conforms to the traffic contract. Redis updates $TAT = \text{projected\_TAT}$ and allows the request. If $\text{projected\_TAT} > t + \tau$, the arrival time is too far in the future; the request violates the burst envelope, is denied (HTTP 429), and $TAT$ remains untouched.

GCRA provides zero boundary approximation error, $O(1)$ constant time execution, and $O(1)$ constant memory overhead consisting of a single 64-bit integer timestamp.

---

Redis Memory Internals: Jemalloc Allocation and Key Footprints

In high-concurrency systems servicing millions of active entities, memory consumption is not merely an infrastructure cost; it directly impacts tail latency. Redis relies on jemalloc as its default memory allocator. Jemalloc allocates memory in discrete size classes (bins) such as 32, 48, 64, 80, 96, 112, 128, 160, 192, and 256 bytes. Any allocation request is rounded up to the nearest bin boundary, introducing internal fragmentation.

Redis Memory Overhead: dictEntry, robj, and SDS Headers

Every Redis key-value pair incurs fundamental data structure overhead before accounting for user data:

1. `dictEntry`: Redis stores keys and values in a global hash table. Each entry consumes:

- Key pointer: 8 bytes

- Value pointer: 8 bytes

- Next pointer (for hash collision chaining): 8 bytes

- Total dictEntry overhead: 24 bytes (rounded to 32 bytes in jemalloc).

2. Redis Object (`robj`): Every value is wrapped in a redisObject struct:

- Type (4 bits) + Encoding (4 bits) + LRU/LFU clock (24 bits) = 4 bytes

- Reference count (refcount): 4 bytes

- Pointer to actual value (ptr): 8 bytes

- Total robj overhead: 16 bytes.

3. Simple Dynamic String (SDS): Redis strings utilize SDS headers. For short strings (under 44 bytes), Redis combines the robj and SDS buffer into a single contiguous allocation (OBJ_ENCODING_EMBSTR), avoiding a second jemalloc call.

Memory Breakdown: 1 Million Active Keys Across Algorithms

Let us calculate the exact memory footprint of maintaining 1,000,000 active rate-limited clients (keys formatted as rl:usr:1000000, 14 bytes) configured for a quota of 100 requests per minute:

1. Sliding Window Log (Sorted Set):

Each client requires a ZSET. In Redis, once a ZSET exceeds zset-max-listpack-entries (default 128 entries) or elements exceed 64 bytes, Redis converts the internal representation from a compact listpack into a dual structure: an internal dictionary (dict) for $O(1)$ element lookup and a skiplist (zskiplist) for range queries.

  • Per Sorted Set Member:

- Timestamp score (double): 8 bytes

- Member value (UUID string, ~36 bytes): robj (16 bytes) + SDS (39 bytes) = 55 bytes $\rightarrow$ jemalloc 64-byte bin

- zskiplistNode: Pointer (8 bytes) + backward pointer (8 bytes) + score (8 bytes) + obj pointer (8 bytes) + average 1.33 level pointers ($1.33 \times 16$ bytes $\approx 21$ bytes) = ~53 bytes $\rightarrow$ jemalloc 64-byte bin

- dictEntry in ZSET dictionary: 24 bytes $\rightarrow$ jemalloc 32-byte bin

- Total per logged request: $\approx 160\text{ bytes}$

  • At 100 requests logged in the window per key:

$$100 \times 160\text{ bytes} = 16,000\text{ bytes per client}$$

  • For 1,000,000 active clients:

$$\text{Total RAM} \approx 16\text{ GB to } 18\text{ GB (including base dictEntry and memory fragmentation)}$$

2. Sliding Window Counter (Dual String Keys or Hash):

Maintaining current and previous window integers requires two Redis keys per client, or a single Redis Hash with two fields (prev and curr):

  • Hash overhead: dictEntry (32 bytes) + robj (16 bytes) + compact listpack structure (~48 bytes) + fields/values (~40 bytes) = ~136 bytes $\rightarrow$ jemalloc 160-byte bin.
  • For 1,000,000 active clients:

$$\text{Total RAM} \approx 160\text{ MB}$$

3. Generic Cell Rate Algorithm (GCRA Single Key):

GCRA requires storing only the $TAT$ millisecond timestamp as a string or 64-bit integer:

  • Redis key: rl:usr:1000000 (14 bytes)
  • Stored value: 1700000000000 (13-character timestamp string)
  • Redis encodes short strings using OBJ_ENCODING_EMBSTR:

- dictEntry: 24 bytes (jemalloc 32-byte bin)

- Key SDS (sdshdr8 + 14 chars + null): 18 bytes (jemalloc 32-byte bin)

- robj + Value SDS (sdshdr8 + 13 chars + null): $16 + 16 = 32\text{ bytes}$

- Base allocation per key: $32 + 32 + 32 = 96\text{ bytes}$ (or as low as 58 bytes when key names are tightly optimized or integers are stored).

  • For 1,000,000 active clients:

$$\text{Total RAM} \approx 58\text{ MB to } 96\text{ MB}$$

+-------------------------------------------------------------------------------+
|             Redis RAM Footprint Comparison (1 Million Active Keys)            |
+-------------------------------------------------------------------------------+
| Sliding Window Log (ZSET)  | [████████████████████████████████████] ~16.0 GB  |
| Sliding Window Counter     | [█] ~160 MB                                      |
| Token Bucket (Hash)        | [█] ~148 MB                                      |
| GCRA (Single Scalar TAT)   | [░] ~58 MB - 96 MB                               |
+-------------------------------------------------------------------------------+

Based on Redis data structure overhead and jemalloc bin allocations, maintaining a 100-request Sliding Window Log consumes approximately 16 KB per client (~16 GB for 1,000,000 keys), whereas GCRA stores a single scalar timestamp consuming 58 to 96 bytes per client (~58 MB to 96 MB for 1,000,000 keys). This architectural difference yields a 160x to 270x reduction in memory consumption for a 100-request window, with memory savings scaling linearly higher as quota limits ($N$) expand.

CPU Cache Line Utilization and Single-Threaded Event Loop Pressure

Redis executes commands within a single-threaded event loop. Latency spikes occur when operations traverse pointers across non-contiguous heap memory, triggering CPU L1/L2/L3 cache misses.

In a Sliding Window Log, executing ZREMRANGEBYSCORE requires Redis to traverse skiplist pointers and deallocate jemalloc nodes. During an ingress surge of 50,000 requests per second, sweeping millions of expired ZSET nodes causes high CPU cache invalidation rates and stalls the event loop. In contrast, GCRA executes in $O(1)$ time: fetching a single string, executing pure register arithmetic, and performing a single write. The Redis CPU core spends its execution cycles serving network I/O rather than traversing heap pointers.

---

Production Redis Lua Script: Atomic GCRA Implementation

Executing GCRA across distributed API gateway nodes requires atomic execution inside Redis. If two requests for the same client execute concurrently across different application servers, a race condition could overwrite the $TAT$. By encapsulating GCRA inside a Redis Lua script, operations execute atomically within Redis's event loop without external distributed locks.

Server-Side Monotonic Time via `redis.call('TIME')`

A common failure mode in distributed rate limiting is relying on application server system clocks. If Node.js Server A has a clock drift of +400ms relative to Node.js Server B, clients routed through Server A will encounter premature rate limit denials.

To eliminate clock skew, our Lua script calls redis.call('TIME'). Redis retrieves its own operating system time directly via gettimeofday(), returning a two-element array: [seconds, microseconds]. This guarantees that every distributed client is evaluated against a single, monotonic reference clock.

Executable Lua Script with Theoretical Arrival Time (TAT)

Save the following script as gcra.lua:

-- ============================================================================
-- Production Generic Cell Rate Algorithm (GCRA) Rate Limiter
-- ============================================================================
-- Description:
--   Enforces exact rate limits and burst tolerances using Theoretical
--   Arrival Time (TAT). Employs atomic server-side time from redis.call('TIME').
--
-- KEYS[1]: Rate limit identifier (e.g., "{tenant:tenant_9823}:ratelimit")
-- ARGV[1]: Max capacity / rate limit (e.g., 100 requests)
-- ARGV[2]: Time window period in milliseconds (e.g., 60000 for 1 minute)
-- ARGV[3]: Cost / cell quantity to consume (default: 1)
-- ARGV[4]: Burst tolerance multiplier (default: equals ARGV[1])
--
-- Returns array of 4 integers:
--   [1] Allowed: 1 if conforming, 0 if throttled
--   [2] Remaining: Estimated remaining quota before throttling
--   [3] Reset After (ms): Milliseconds until quota completely refills
--   [4] Retry After (ms): Milliseconds until next request can be admitted
-- ============================================================================

local rate_limit_key   = KEYS[1]
local max_rate         = tonumber(ARGV[1])
local period_ms        = tonumber(ARGV[2])
local cost             = tonumber(ARGV[3]) or 1
local burst_capacity   = tonumber(ARGV[4]) or max_rate

-- Step 1: Calculate Emission Interval (T) and Burst Tolerance (Tau)
-- T: Time increment added to TAT per single unit of cost
local emission_interval_ms = period_ms / max_rate
-- Tau: Maximum time allowance ahead of the current arrival window
local tau_ms = emission_interval_ms * burst_capacity

-- Step 2: Retrieve atomic server time from Redis (eliminates clock drift)
local server_time = redis.call('TIME')
local now_ms = (tonumber(server_time[1]) * 1000) + math.floor(tonumber(server_time[2]) / 1000)

-- Step 3: Fetch existing Theoretical Arrival Time (TAT)
local current_tat = redis.call('GET', rate_limit_key)
local tat_ms

if current_tat then
    tat_ms = tonumber(current_tat)
else
    -- If key does not exist or has expired, initialize TAT to now
    tat_ms = now_ms
end

-- Step 4: Virtual Scheduling calculation
-- If client was idle and TAT is in the past, baseline TAT resets to now
local new_tat_base = math.max(now_ms, tat_ms)
local projected_tat = new_tat_base + (cost * emission_interval_ms)

-- Step 5: Conformance Check
local allowed = 0
local remaining = 0
local reset_after_ms = 0
local retry_after_ms = 0

if projected_tat <= (now_ms + tau_ms) then
    -- Request conforms to rate envelope: ALLOW
    allowed = 1
    tat_ms = projected_tat

    -- Calculate remaining units permissible under the burst ceiling
    local remaining_time_window = (now_ms + tau_ms) - tat_ms
    remaining = math.floor(remaining_time_window / emission_interval_ms)

    -- Milliseconds until the bucket fully drains to idle
    reset_after_ms = math.max(0, tat_ms - now_ms)

    -- Dynamic TTL: Persist key only until TAT drains back to 'now'
    -- Adding a small 1000ms safety buffer prevents boundary thrashing
    local ttl_ms = math.ceil(reset_after_ms + 1000)
    redis.call('PSETEX', rate_limit_key, ttl_ms, tostring(tat_ms))
else
    -- Request exceeds rate envelope: THROTTLE (HTTP 429)
    allowed = 0
    remaining = 0
    reset_after_ms = math.max(0, tat_ms - now_ms)

    -- Calculate exact delay required before a cell with 'cost' can conform
    retry_after_ms = math.ceil(projected_tat - (now_ms + tau_ms))
end

return { allowed, remaining, reset_after_ms, retry_after_ms }

Script Execution Logic and Mathematical Conformance Walkthrough

Let us trace how this script handles three distinct execution phases:

1. Cold Start (Initial Request): A client arrives at $t = 1000\text{ ms}$. With no existing key, tat_ms initializes to $1000\text{ ms}$. For a rate of 10 requests per 10,000ms ($T = 1000\text{ ms}$, $\tau = 10000\text{ ms}$):

- $\text{projected\_TAT} = 1000 + 1000 = 2000\text{ ms}$

- Check: $2000 \le (1000 + 10000) = 11000$ (Passes)

- Stored $TAT = 2000\text{ ms}$. PSETEX sets key expiration to 2000ms.

2. Instantaneous Burst: The client immediately fires 9 more requests at $t = 1000\text{ ms}$. For each request, new_tat_base remains at the incrementing $TAT$:

- Req 2: $TAT = 3000\text{ ms}$

- Req 10: $TAT = 11000\text{ ms}$. $\text{Remaining} = 0$.

- Req 11 arrives at $t = 1000\text{ ms}$: $\text{projected\_TAT} = 11000 + 1000 = 12000\text{ ms}$.

- Check: $12000 \le 11000$ evaluates to False.

- Request throttled. retry_after_ms returned: $12000 - 11000 = 1000\text{ ms}$.

3. Continuous Flow: If the client waits exactly 1000ms and fires at $t = 2000\text{ ms}$, the ceiling increases: $t + \tau = 2000 + 10000 = 12000\text{ ms}$. Now $\text{projected\_TAT} = 12000 \le 12000$ evaluates to True. The request passes without any artificial interval delays.

---

High-Throughput Client Integration: TypeScript and RFC 6585 Headers

To run this in production without adding latency to every HTTP request, clients must avoid resending the entire Lua script text over the network. Using Redis SCRIPT LOAD on process initialization stores the script in Redis memory and returns a 40-character SHA-1 digest. Subsequent evaluations call EVALSHA.

Cluster-Aware Hash Tagging and SHA-1 Preloading

In a multi-node Redis Cluster, keys are partitioned across 16,384 hash slots computed via CRC16. Lua scripts executing multi-key commands or single-key modifications must ensure the key maps to the target cluster node.

By enclosing the entity identifier in curly braces—e.g., {tenant:cust_9823}:ratelimit—Redis computes the CRC16 hash slot strictly on the characters inside the braces (tenant:cust_9823). This guarantees slot stability across distributed cluster shards.

Production TypeScript Client Implementation

Below is a complete, production-grade TypeScript driver using ioredis designed for high-concurrency API gateways:

import Redis from 'ioredis';
import { Request, Response, NextFunction } from 'express';

export interface RateLimitConfig {
  maxRate: number;        // Maximum requests permitted in window
  periodMs: number;       // Window size in milliseconds
  cost?: number;          // Quota cost for this route (default: 1)
  burstCapacity?: number; // Burst capacity (defaults to maxRate)
}

export interface RateLimitResult {
  allowed: boolean;
  remaining: number;
  resetAfterMs: number;
  retryAfterMs: number;
}

export class GcraRateLimiter {
  private redis: Redis;
  private scriptSha: string | null = null;
  private readonly luaScript = `
    local rate_limit_key   = KEYS[1]
    local max_rate         = tonumber(ARGV[1])
    local period_ms        = tonumber(ARGV[2])
    local cost             = tonumber(ARGV[3]) or 1
    local burst_capacity   = tonumber(ARGV[4]) or max_rate

    local emission_interval_ms = period_ms / max_rate
    local tau_ms = emission_interval_ms * burst_capacity

    local server_time = redis.call('TIME')
    local now_ms = (tonumber(server_time[1]) * 1000) + math.floor(tonumber(server_time[2]) / 1000)

    local current_tat = redis.call('GET', rate_limit_key)
    local tat_ms = current_tat and tonumber(current_tat) or now_ms

    local new_tat_base = math.max(now_ms, tat_ms)
    local projected_tat = new_tat_base + (cost * emission_interval_ms)

    if projected_tat <= (now_ms + tau_ms) then
        tat_ms = projected_tat
        local remaining_time = (now_ms + tau_ms) - tat_ms
        local remaining = math.floor(remaining_time / emission_interval_ms)
        local reset_after_ms = math.max(0, tat_ms - now_ms)
        local ttl_ms = math.ceil(reset_after_ms + 1000)
        redis.call('PSETEX', rate_limit_key, ttl_ms, tostring(tat_ms))
        return { 1, remaining, reset_after_ms, 0 }
    else
        local reset_after_ms = math.max(0, tat_ms - now_ms)
        local retry_after_ms = math.ceil(projected_tat - (now_ms + tau_ms))
        return { 0, 0, reset_after_ms, retry_after_ms }
    end
  `;

  constructor(redisClient: Redis) {
    this.redis = redisClient;
  }

  /**
   * Preload SHA into Redis script cache to eliminate script network payload
   */
  public async init(): Promise<void> {
    this.scriptSha = await this.redis.script('LOAD', this.luaScript) as string;
  }

  /**
   * Execute atomic GCRA evaluation
   */
  public async evaluate(
    entityId: string,
    config: RateLimitConfig
  ): Promise<RateLimitResult> {
    // Hash-tag wrapper ensures compatibility with Redis Cluster sharding
    const key = `{ratelimit:${entityId}}`;
    const cost = config.cost ?? 1;
    const burst = config.burstCapacity ?? config.maxRate;

    try {
      let rawResult: [number, number, number, number];

      if (this.scriptSha) {
        try {
          rawResult = (await this.redis.evalsha(
            this.scriptSha,
            1,
            key,
            config.maxRate,
            config.periodMs,
            cost,
            burst
          )) as [number, number, number, number];
        } catch (err: any) {
          // Fall back to EVAL if Redis restarted and lost its script cache (NOSCRIPT)
          if (err?.message?.includes('NOSCRIPT')) {
            await this.init();
            rawResult = (await this.redis.eval(
              this.luaScript,
              1,
              key,
              config.maxRate,
              config.periodMs,
              cost,
              burst
            )) as [number, number, number, number];
          } else {
            throw err;
          }
        }
      } else {
        await this.init();
        rawResult = (await this.redis.evalsha(
          this.scriptSha!,
          1,
          key,
          config.maxRate,
          config.periodMs,
          cost,
          burst
        )) as [number, number, number, number];
      }

      return {
        allowed: rawResult[0] === 1,
        remaining: rawResult[1],
        resetAfterMs: rawResult[2],
        retryAfterMs: rawResult[3],
      };
    } catch (error) {
      // Fail-open strategy: log Redis failure and permit request to protect availability
      console.error('Redis Rate Limiting Error, failing open:', error);
      return {
        allowed: true,
        remaining: 1,
        resetAfterMs: 0,
        retryAfterMs: 0,
      };
    }
  }

  /**
   * Express Middleware implementing IETF RFC 6585 and RateLimit standard headers
   */
  public middleware(config: RateLimitConfig) {
    return async (req: Request, res: Response, next: NextFunction) => {
      // Identify client by authenticated API key, JWT sub, or remote IP
      const identifier = (req.headers['x-api-key'] as string) || req.ip || 'anonymous';
      const result = await this.evaluate(identifier, config);

      const resetSeconds = Math.ceil(result.resetAfterMs / 1000);
      const retrySeconds = Math.ceil(result.retryAfterMs / 1000);

      // Set standard and legacy headers
      res.setHeader('RateLimit-Limit', config.maxRate);
      res.setHeader('RateLimit-Remaining', result.remaining);
      res.setHeader('RateLimit-Reset', resetSeconds);
      res.setHeader('X-RateLimit-Limit', config.maxRate);
      res.setHeader('X-RateLimit-Remaining', result.remaining);
      res.setHeader('X-RateLimit-Reset', resetSeconds);

      if (!result.allowed) {
        res.setHeader('Retry-After', retrySeconds);
        res.status(429).json({
          error: 'Too Many Requests',
          message: `API rate limit of ${config.maxRate} requests per ${config.periodMs / 1000}s exceeded.`,
          retryAfterMs: result.retryAfterMs,
        });
        return;
      }

      next();
    };
  }
}

When building high-throughput API gateways and enterprise platforms, engineering organizations often partner with specialized engineering practices like Wise Hustlers Custom Software to architect distributed caching layers, custom gateway filters, and fault-tolerant microservice meshes.

Standard HTTP 429 and RateLimit Response Headers

Adhering to standard headers prevents client integration friction and ensures automated SDK retries obey backoff envelopes. Our implementation sets:

  • RateLimit-Limit: Maximum quota for the configured period (IETF Draft RFC).
  • RateLimit-Remaining: Calculated units remaining before throttling occurs.
  • RateLimit-Reset: Seconds remaining until the quota fully replenishes.
  • Retry-After: Required by RFC 6585 on HTTP 429 responses, specifying the integer seconds the client must sleep before re-attempting.

---

Architectural Benchmarks: Latency, Memory, and Throughput Under Concurrency

To establish objective comparisons across rate-limiting algorithms, architectural evaluations analyze computational complexity, single-threaded Redis event loop impact, and memory allocation dynamics under sustained concurrency.

Controlled Benchmark Methodology

In high-throughput architectures scaling from 10,000 to 100,000 operations per second (RPS) across 1,000,000 active client identities, rate limiters exhibit distinct performance profiles depending on their underlying data structures:

1. Fixed Window Counter: Single INCR pipelined with EXPIRE on a Redis string key.

2. Sliding Window Log: Redis Sorted Set (ZSET) executing ZREMRANGEBYSCORE, ZCARD, ZADD, and EXPIRE.

3. Sliding Window Counter: Redis Lua script executing linear interpolation across dual integer counters.

4. Generic Cell Rate Algorithm (GCRA): Atomic Redis Lua script evaluating Theoretical Arrival Time (TAT) against a single scalar key.

Performance Benchmark Comparison Matrix

Evaluation MetricFixed Window CounterSliding Window Log (ZSET)Sliding Window CounterToken Bucket (Redis Hash)GCRA (Atomic Lua TAT)
Underlying Redis Data StructureString (INCR)Sorted Set (ZSET)Hash / 2x StringHash (HMSET)Single String (PSETEX)
Memory per 1M Active Keys (N=100)~54 MB~16.0 GB~160 MB~148 MB~58 MB to 96 MB
Redis Commands per Evaluation2 (pipelined)4 (ZSET ops)2 (in Lua)2 (in Lua)1 (`PSETEX` in Lua)
Time Complexity$O(1)$$O(\log N + M)$$O(1)$$O(1)$$O(1)$
Space Complexity$O(1)$$O(N)$$O(1)$$O(1)$$O(1)$
Single-Threaded Event Loop ImpactMinimalSevere (Skiplist sweeps block main thread)LowLowMinimal (In-place scalar update)
Tail Latency Sensitivity at ScaleFlat ($O(1)$ register op)High degradation under burst evictionsFlatFlatFlat ($O(1)$ register arithmetic)
Boundary Spike VulnerabilityCritical (200% burst)None (0% error)Negligible (~0.003% empirical error)None (Controlled burst)None (0% error)
Clock Skew SensitivityN/AHigh (Client-timestamp dependent)LowLowZero (Atomic server TIME)

Tail Latency Analysis: P99 and P99.9 Under 100k RPS

Under sustained high-concurrency workloads, tail latency (P99 and P99.9) across distributed rate limiters is governed by Redis's single-threaded event loop architecture and memory deallocation dynamics.

While the Sliding Window Log maintains mathematical accuracy, its tail latency deteriorates significantly under sustained query volume. This latency inflation is driven by Redis skiplist maintenance: when executing ZREMRANGEBYSCORE, Redis must traverse internal skiplist pointers and iteratively deallocate jemalloc heap chunks for expired member nodes while holding the main thread lock. Because Redis processes commands sequentially on a single core, CPU cycles spent freeing sorted set nodes directly stall subsequent commands, causing network packets to accumulate in the Redis TCP receive buffer and inflating tail latency across the entire client fleet.

GCRA, conversely, avoids event loop stalls by executing in constant $O(1)$ time. Because GCRA tracks only a single scalar Theoretical Arrival Time stored as an embedded string (OBJ_ENCODING_EMBSTR), updates occur in place without pointer traversal or dynamic memory reallocation. The Redis CPU core spends its execution cycles servicing network socket I/O rather than walking heap data structures, preserving low, predictable tail latencies even under severe ingress spikes.

---

Envoy Global Rate Limit Service (RLS) Architecture

In large-scale microservice deployments, executing rate limiting inside application code introduces significant architectural liabilities:

  • Every microservice must implement and maintain rate limit client logic.
  • Misconfigured connection pools to Redis across hundreds of container pods can overwhelm Redis through connection churn.
  • Network bandwidth is wasted routing unauthorized requests through API gateways, ingress controllers, and service meshes before application middleware rejects them.

The cloud-native solution is offloading rate limiting to the edge data plane using the Envoy Proxy Global Rate Limit Service (RLS).

In-Process vs. Decentralized vs. Global Edge Rate Limiting

Rate limiting strategies operate at three distinct architectural tiers:

1. In-Process Token Buckets: Implemented locally within Envoy workers using the envoy.filters.http.local_ratelimit filter. Token buckets execute in memory with zero network overhead. However, quotas are partitioned per proxy process: if you have 20 Envoy pods and set a limit of 100 RPS, aggregate throughput can reach 2,000 RPS.

2. Decentralized Application Middleware: Running Node.js/Go middleware talking directly to Redis. This suffers from the operational overhead detailed above.

3. Envoy Global Rate Limit Service (RLS): Envoy proxies intercept inbound HTTP requests and issue non-blocking, asynchronous gRPC requests (CheckRequest) to an external RLS daemon cluster (such as the reference Go RLS implementation maintained by Envoy/Lyft). The RLS daemon communicates with Redis, aggregates keys via pipelining, and replies with a gRPC CheckResponse indicating OK or OVER_LIMIT.

Envoy RLS gRPC Architecture and Network Topology

flowchart TD
    subgraph Clients["Edge Traffic Ingress"]
        C1["Public Mobile Clients"]
        C2["Third-Party API Integrations"]
    end

    subgraph DataPlane["Envoy Data Plane (Edge Fleet)"]
        E1["Envoy Proxy Pod 1"]
        E2["Envoy Proxy Pod 2"]
        E3["Envoy Proxy Pod N"]
    end

    subgraph RlsTier["Global Rate Limit Service (RLS) Fleet"]
        RLS1["RLS Daemon Worker 1"]
        RLS2["RLS Daemon Worker 2"]
    end

    subgraph StorageTier["Distributed Storage Tier"]
        RC1[("Redis Primary (Cluster)")]
        RC2[("Redis Replica")]
    end

    subgraph CoreServices["Upstream Microservices"]
        S1["Authentication Service"]
        S2["Order Processing Engine"]
        S3["Payment Settlement Core"]
    end

    C1 -->|HTTPS| E1
    C2 -->|HTTPS| E2
    
    E1 -.->|1. Async gRPC CheckRequest| RLS1
    E2 -.->|1. Async gRPC CheckRequest| RLS2
    
    RLS1 <-->|2. Atomic Pipelined GCRA / Counters| RC1
    RLS2 <-->|2. Atomic Pipelined GCRA / Counters| RC1
    RC1 -.->|Replication| RC2

    RLS1 -.->|3. gRPC CheckResponse: OK| E1
    RLS2 -.->|3. gRPC CheckResponse: OVER_LIMIT| E2

    E1 ==>|4. Forward Allowed Traffic| S2
    E2 -->|4. Immediate 429 Too Many Requests| C2

Envoy Data Plane Configuration (`envoy.yaml`)

To activate global rate limiting, configure the envoy.filters.http.ratelimit HTTP filter within the Envoy filter chain:

static_resources:
  listeners:
    - name: ingress_listener
      address:
        socket_address:
          address: 0.0.0.0
          port_value: 443
      filter_chains:
        - filters:
            - name: envoy.filters.network.http_connection_manager
              typed_config:
                "@type": type.googleapis.com/envoy.extensions.filters.network.http_connection_manager.v3.HttpConnectionManager
                stat_prefix: ingress_http
                route_config:
                  name: primary_routes
                  virtual_hosts:
                    - name: api_v1
                      domains: ["api.domain.com"]
                      routes:
                        - match:
                            prefix: "/v1/transactions"
                          route:
                            cluster: upstream_transaction_service
                            rate_limits:
                              - actions:
                                  - generic_key:
                                      descriptor_value: "transactions"
                                  - request_headers:
                                      header_name: "X-Tenant-ID"
                                      descriptor_key: "tenant_id"
                http_filters:
                  - name: envoy.filters.http.ratelimit
                    typed_config:
                      "@type": type.googleapis.com/envoy.extensions.filters.http.ratelimit.v3.RateLimit
                      domain: api_gateway_limits
                      failure_mode_deny: false # Fail-open during RLS outage
                      timeout: 0.050s          # Strict 50ms gRPC budget
                      enable_x_ratelimit_headers: DRAFT_VERSION_03
                      rate_limit_service:
                        transport_api_version: V3
                        grpc_service:
                          envoy_grpc:
                            cluster_name: rate_limit_cluster

  clusters:
    - name: rate_limit_cluster
      type: STRICT_DNS
      connect_timeout: 0.020s
      lb_policy: ROUND_ROBIN
      http2_protocol_options: {} # Required for gRPC transport
      load_assignment:
        cluster_name: rate_limit_cluster
        endpoints:
          - lb_endpoints:
              - endpoint:
                  address:
                    socket_address:
                      address: rls-daemon.internal.net
                      port_value: 8081

    - name: upstream_transaction_service
      type: STRICT_DNS
      connect_timeout: 0.250s
      lb_policy: ROUND_ROBIN
      load_assignment:
        cluster_name: upstream_transaction_service
        endpoints:
          - lb_endpoints:
              - endpoint:
                  address:
                    socket_address:
                      address: transaction-service.internal.net
                      port_value: 8080

Envoy RLS Service Descriptor Configuration (`config.yaml`)

The external Rate Limit Service reads YAML descriptor rules that define hierarchical rate limits based on descriptors dispatched by Envoy:

domain: api_gateway_limits
descriptors:
  - key: generic_key
    value: transactions
    descriptors:
      - key: tenant_id
        rate_limit:
          unit: minute
          requests_per_unit: 1000
      - key: tenant_id
        value: enterprise_tier_unlimited
        rate_limit:
          unit: minute
          requests_per_unit: 50000

When an HTTP request strikes Envoy with X-Tenant-ID: tenant_9823 on /v1/transactions, Envoy extracts the descriptors:

("generic_key", "transactions"), ("tenant_id", "tenant_9823")

It sends this tuple to RLS over gRPC. RLS computes the key, executes the rate-limit verification against Redis, and returns OK or OVER_LIMIT.

High-Availability Patterns: Fail-Open, Shadowing, and Local Cache Absorption

Operating global rate limiting at scale introduces edge-case failure modes that must be engineered defensively:

1. Fail-Open Policy (`failure_mode_deny: false`): If the RLS daemon crashes or the Redis cluster experiences a network partition, setting failure_mode_deny: false instructs Envoy to bypass rate limit verification and forward traffic directly to upstream services. In mission-critical environments, degrading rate enforcement is vastly preferable to dropping all incoming API traffic across the entire enterprise.

2. Strict gRPC Timeouts (`timeout: 0.050s`): Rate limiting sits in the critical path of every inbound HTTP call. Setting a 50ms gRPC timeout budget prevents Redis latency spikes from saturating Envoy connection pools.

3. Shadow / Dry-Run Mode: Envoy supports rate_limited_as_resource_exhausted: false and shadowing headers. This allows architects to deploy new rate limit descriptors into production, observing via Prometheus metrics which clients would be throttled without actually returning HTTP 429 errors.

4. Local Cache Absorption: The Envoy RLS daemon features an internal LRU cache. When a client significantly exceeds its limit, RLS caches the negative decision in memory for a short duration (e.g., 5 seconds), rejecting subsequent calls without generating network I/O to Redis.

---

Architectural Decision Matrix and Implementation Trade-Offs

When architecting a production rate-limiting tier, evaluate the operational parameters against this decision framework:

+-------------------------------------------------------------------------------+
|                       Rate Limiting Decision Framework                        |
+-------------------------------------------------------------------------------+
| Criteria                          | Recommended Architecture                  |
+-----------------------------------+-------------------------------------------+
| Multi-region cloud API gateway    | Envoy Global RLS + Redis Cluster (GCRA)   |
| High active tenant count (>5M)    | GCRA (Lua in Redis)                       |
| Simple microservice, low volume   | Sliding Window Counter (Redis Hash)       |
| Strict anti-scraping burst filter | Token Bucket / GCRA with low Tau          |
| Zero network latency tolerance    | Local Envoy Token Bucket (in-process)     |
+-------------------------------------------------------------------------------+

When to Choose GCRA

GCRA is the architectural standard when:

  • The system must track millions of concurrent identities (API keys, IP addresses, tenant UUIDs) with minimal RAM.
  • Strict protection against boundary bursts is non-negotiable.
  • Redis CPU overhead must be minimized under heavy traffic (>50k requests/sec).
  • Clients require exact, predictable Retry-After backoff metrics calculated via mathematical scheduling rather than rough window approximations.

When to Choose Sliding Window Counter

Sliding Window Counters are suitable when:

  • Rate limiting is implemented directly inside application runtimes (e.g., Node.js or Go) without Lua scripting capabilities.
  • Storage memory is plentiful, and an approximation variance (empirically observed by Cloudflare at ~0.003%, with localized variance during sudden step-function spikes) is acceptable for the workload.
  • Quotas span very long durations (e.g., 30-day billing cycle quotas) where sub-second burst calculation is unnecessary.

When to Choose Local Envoy Token Bucket Filters

Local filters (envoy.filters.http.local_ratelimit) are recommended as a defensive perimeter:

  • Deploy local filters alongside global RLS to protect against catastrophic DDoS attacks.
  • If edge ingress spikes from 50,000 to 1,000,000 RPS, local Envoy token buckets shed excess volume at zero network cost, shielding the external RLS daemon and Redis storage cluster from saturation.

---

Technical FAQ: Edge Cases in Distributed Rate Limiting

How does GCRA prevent the "double-limit burst" inherent to fixed-window counters without paying the memory tax of sliding window logs?

Fixed-window counters evaluate quotas in discrete, isolated time buckets. A client with a 100 req/min limit can fire 100 requests at 00:00:59 and another 100 requests at 00:01:01, yielding 200 requests within two seconds. The Sliding Window Log eliminates this by storing every individual timestamp in a Redis sorted set, consuming $O(N)$ memory. GCRA eliminates boundary bursts using continuous virtual scheduling: every request pushes the Theoretical Arrival Time ($TAT$) forward by the emission interval $T$. Because $TAT$ accumulates across arbitrary time boundaries, requests fired at 00:00:59 push $TAT$ into the future, leaving insufficient burst tolerance ($\tau$) to admit another batch at 00:01:01. This mathematical continuity prevents double-limit bursts while requiring only a single scalar timestamp key.

What happens to GCRA when Redis node clocks experience drift or NTP step updates?

If application nodes query their local system clocks, NTP drift creates divergent rate evaluations across servers. Our production Lua script eliminates this by executing redis.call('TIME'), deriving all timestamps from the Redis primary instance's system clock. If the Redis host's operating system executes a backwards NTP step adjustment, GCRA's new_tat_base = math.max(now_ms, tat_ms) logic provides intrinsic protection: because tat_ms was calculated against the prior forward time, new_tat_base remains anchored to the higher value, preventing negative time anomalies. In environments with frequent clock adjustments, configuring the host NTP daemon to slew time smoothly (slewing via chrony or ntpd -x) rather than stepping ensures zero sub-millisecond calculation artifacts.

How can an engineering team enforce multi-tier rate limits (e.g., 100 req/min AND 50,000 req/day) using GCRA?

Multi-tier rate limits are enforced by evaluating multiple GCRA keys within a single atomic Lua script call. For example, pass two keys to the script: KEYS[1] = {user:123}:min and KEYS[2] = {user:123}:day. The script calculates conformance for both the short-term burst interval ($T_1 = 60000/100$) and the long-term volume quota ($T_2 = 86400000/50000$). If either conformance check fails, the script returns allowed = 0, updates neither $TAT$, and returns the maximum retry_after_ms of the two limits. Enclosing both keys in matching hash tags ({user:123}) ensures both keys hash to the identical Redis Cluster slot, preserving single-transaction atomicity.

Under what conditions should an architect choose Sliding Window Counter over GCRA?

Sliding Window Counters are preferable when client engineering teams lack Lua scripting permissions on managed Redis clusters (such as multi-tenant AWS ElastiCache instances with restricted commands) or when building application middleware using basic Redis INCR and EXPIRE primitives. They are also appropriate for macroscopic time windows—such as daily or weekly billing limits—where microscopic burst smoothing is unnecessary and developers prefer reading simple, human-readable integer counts directly from Redis CLI tools.

How does Envoy's Global Rate Limit Service prevent Redis connection saturation when incoming ingress spikes to 200,000 RPS?

Envoy's external RLS daemon (written in Go) decouples client connections from the Redis data layer. When 200,000 HTTP requests hit fifty Envoy proxies, Envoy dispatches gRPC requests over persistent HTTP/2 multiplexed connections to the RLS fleet. The RLS workers do not issue individual Redis calls per gRPC request; instead, they aggregate inbound descriptors within an event-loop batching pipeline, issuing pipelined Redis multi-key operations. Furthermore, RLS integrates an in-memory LRU cache that stores negative rate-limit verdicts (OVER_LIMIT). Once an abusive client is throttled, subsequent requests from that identity are rejected directly by RLS memory for the duration of the cooldown window, absorbing massive surges without touching Redis.

---

Sources

Related articles