Rate Limiting, Cells, and GCRA

Why Rate Limiting Matters

Rate limiting is a practical necessity for anyone running a service. The motivations fall into a few broad categories: protecting shared resources like server capacity or database load, securing endpoints against brute-force attacks such as repeated password or 2FA attempts, and enabling tiered service plans where usage is capped by subscription level. The algorithms behind these limits vary widely in sophistication, from simple expiry-based counters to the more elegant GCRA.

Time-Bucketed Counters

The most straightforward approach stores a remaining quota in a bucket that expires after a fixed interval. On the first request, the bucket is created with a decrementing counter. When the counter hits zero, further requests are rejected until the bucket resets. Redis’s SETEX command makes this trivial: set the key with the remaining count and an expiry, and let the store handle cleanup.

# 5000 allowed actions per hour
RATE_BURST  = 5000
RATE_PERIOD = 1.hour

def rate_limit?(bucket)
  if !bucket.exists?
    bucket.set_value(RATE_BURST)
    bucket.set_ttl(RATE_PERIOD)
  end

  if bucket.value > 0
    bucket.decrement
    true
  else
    false
  end
end

The Cost of Simplicity

This design punishes clients harshly. A misbehaving or buggy script can drain the entire hourly allowance in seconds, leaving the user locked out until the bucket expires. The server pays a price too. Consider an antisocial client that exhausts its limit in short bursts and resumes exactly when the window resets. The service must provision capacity for those periodic spikes even though most of the hour is quiet. A more evenly distributed algorithm would make such bursts impossible.

$ curl --silent --head -i -H "Authorization: token $GITHUB_TOKEN" \
    https://api.github.com/users/brandur | grep RateLimit
X-RateLimit-Limit: 5000
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1442423816

$ RESET=1442423816 ruby -e 'puts "%.0f minute(s) before reset" % \
    ((Time.at(ENV["RESET"].to_i) - Time.now) / 60)'
51 minute(s) before reset

Some APIs still run on this naive model. After depleting the 5,000-request allowance, the client is locked out for the rest of the hour, demonstrating the jagged, bursty behavior that comes with a fixed reset period.

Leaky Bucket Smoothing

The leaky bucket algorithm addresses the burst problem directly. Picture a real bucket with a fixed capacity (τ) and a small hole at the bottom. Water leaks out at a constant rate (T). Each action adds water proportional to its cost; the action is rejected when the bucket overflows. The leak drains the bucket continuously, so even after exhausting the full quota, a client regains access almost immediately as the leak reclaims space.

The effect is a smooth, even rate limit rather than an all-or-nothing window. Implementation typically relies on a background process that iterates over active buckets and drips each one by a fixed amount. In Redis, this might mean a hash grouped by limit type, decremented on a timer.

Drip Dependency

The weakness of this approach is its reliance on the dripping process. If the background job fails, is offline, or cannot keep up with a large number of buckets, incoming requests may be wrongly throttled or allowed. Various recovery strategies exist, but an algorithm that does not require a continuous background process would be fundamentally more robust.

The Generic Cell Rate Algorithm

GCRA, or the Generic Cell Rate Algorithm, is a variant of the leaky bucket that eliminates the drip process. Its roots are in ATM networking, where data traveled as fixed-size "cells." The ATM Forum recommended GCRA for scheduling—delaying or dropping cells that exceeded the negotiated rate. While ATM itself is obsolete, GCRA survives as a clean solution to rate limiting.

GCRA tracks a "theoretical arrival time" (TAT) for each limit. The first request seeds TAT by adding the cost (a multiple of the emission interval T, derived from the desired refill rate) to the current time. Each subsequent request compares the current time against the existing TAT minus a burst allowance (τ + T). If the allowed time is in the past, the request is accepted and TAT advances by T; if it is in the future, the request is denied.

Because GCRA relies entirely on time calculations, synchronized clocks matter when limits are enforced across multiple servers. Drift between machines can cause false lockouts. A simple safeguard is to use the central store’s time as the source of truth—for instance, calling the TIME command in Redis rather than relying on each application server’s local clock.

Throttled: A Go Reference Implementation

The open-source Go library Throttled recently moved from a naive rate limiter to one based on GCRA. The package is well documented and tested, making it a practical reference for those curious about the algorithm. The core logic lives in rate.go and is deliberately free of heavy abstraction. It already handles production traffic at Stripe and is slated for Heroku as well. For Go developers, it offers a convenient, battle-tested module out of the box.