Rate Limiting (GCRA)

Every API you have ever called has a speed limit. Exceed it and you receive a 429 Too Many Requests error instead of a reply. The limit is not just about fairness: without it, a single misbehaving client can crowd out everyone else or melt a server.

The challenge is that "too fast" is surprisingly tricky to define. A client that sends ten requests in one second is certainly fast. But what about ten requests in one minute — is that ten little bursts of one, or one big burst of ten? And what if they are allowed to save up quiet time for an occasional burst?

The Generic Cell Rate Algorithm (GCRA) answers all three questions with a single number per client. First standardized in ATM networking by the ITU-T in 1992 and later popularized in web-API contexts, GCRA tracks a theoretical arrival time (TAT): the moment the next request would be due if arrivals were perfectly spaced. Each new request is accepted if it arrives early enough, and the TAT is pushed forward. The gap between a request's arrival and the TAT encodes both the average rate and the burst allowance in one compact computation.

This article unpacks how that single number does all the work, and why it is equivalent to both the token bucket and the leaky bucket — two algorithms that look completely different on the surface.

The panel below simulates a GCRA limiter set to 5 requests per second with a burst of 3 extra tokens. Click Send request to fire one request, or use Auto-fire to send a stream and watch the limiter decide.

<!-- {{c_html_intro}} -->
<div class="config-row">
  <label>{{lbl_rate}} <input id="rate" type="number" min="1" max="20" value="5"> {{lbl_rps}}</label>
  <label>{{lbl_burst}} <input id="burst" type="number" min="0" max="10" value="3"> {{lbl_tokens}}</label>
</div>
<div class="timeline" id="timeline" title="{{lbl_timeline_title}}"></div>
<div class="tat-bar">
  <span class="tat-label">{{lbl_tat}}</span>
  <span id="tat-display" class="tat-val">—</span>
  <span class="tat-label" id="tokens-label"></span>
</div>
<div class="btns">
  <button id="send" type="button">{{btn_send}}</button>
  <button id="auto" type="button">{{btn_auto}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="status" class="status"></div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.config-row { display: flex; gap: 1.2rem; flex-wrap: wrap; margin-bottom: .7rem; font-size: .9rem; }
label { display: flex; align-items: center; gap: .3rem; }
input[type=number] { width: 3.2rem; padding: .2rem .4rem; border: 1px solid #adb1b8; border-radius: 6px;
                     font-size: .9rem; text-align: center; }
.timeline { display: flex; gap: 4px; min-height: 44px; align-items: flex-end; margin: .5rem 0;
            background: #f3f5f7; border-radius: 8px; padding: 6px; flex-wrap: wrap; }
.dot { width: 24px; height: 24px; border-radius: 50%; flex-shrink: 0;
       display: flex; align-items: center; justify-content: center; font-size: 10px; font-weight: 700; }
.dot.ok  { background: #1d9e5c; color: #fff; }
.dot.deny { background: #e63946; color: #fff; }
.tat-bar { display: flex; align-items: center; gap: .6rem; margin: .3rem 0; font-size: .85rem; }
.tat-label { color: #555; }
.tat-val { font-weight: 700; font-variant-numeric: tabular-nums; min-width: 5rem; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin: .5rem 0; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button.active { background: #e63946; border-color: #c92f3c; }
.status { font-size: 1rem; font-weight: 600; min-height: 1.4em; margin-top: .2rem; }
.status.ok   { color: #0a7d33; }
.status.deny { color: #c92f3c; }

// Code not found

Notice that a short burst of requests after a quiet period is allowed — the quiet time replenished the burst budget. But keep firing without pause and the limiter starts denying requests. The Theoretical Arrival Time (TAT) is the key: if your request arrives before the TAT, it is accepted and the TAT advances by one slot; if the TAT has already slipped too far into the future, the request is denied.

Let $r$ be the sustained rate (requests per second) and $b$ be the burst size (extra tokens allowed on top of the average). Define the emission interval $T = 1/r$. The GCRA state for one client is a single timestamp: the Theoretical Arrival Time $\text{TAT}$.

On each incoming request at real time $t_{\text{now}}$:

$$\text{TAT}_{\text{new}} = \max(t_{\text{now}},\; \text{TAT}) + T$$

The request is allowed if:

$$\text{TAT}_{\text{new}} \leq t_{\text{now}} + b \cdot T$$

otherwise it is denied (and TAT stays unchanged).

That is the entire algorithm — one $\max$, one addition, one comparison. Time complexity: $O(1)$ per request. Space: $O(1)$ per client.

Why this equals a token bucket. The quantity $t_{\text{now}} + b \cdot T - \text{TAT}$ is exactly the number of tokens available at time $t_{\text{now}}$. When the client is idle, TAT drifts toward the past and available tokens accumulate — but never beyond $b$. When the client fires requests at full speed, TAT advances and tokens drain. Denying a request when TAT exceeds the deadline corresponds to "bucket empty."

Why this equals a leaky bucket. The TAT is the "water level": each request pours in one unit ($T$), and time drains at rate $r$. The burst window $b \cdot T$ is the bucket capacity above the normal waterline.

Both classical algorithms require either a counter plus a timestamp (token bucket) or a queue (leaky bucket). GCRA collapses both into one number, making it cache-friendly and trivially atomic — ideal for distributed systems where a single Redis GET/SET can implement the entire check.

GCRA's $O(1)$ overhead and single-number state make it the default rate-limiting algorithm in many production systems:

• Public REST APIs: GitHub, Stripe, and Twilio all expose X-RateLimit-* headers. Behind most of them sits a variant of GCRA or a token bucket, enforced in a Redis cluster with atomic Lua scripts.
• CDNs and reverse proxies: Nginx's limit_req module uses a leaky-bucket variant; Cloudflare's rate-limiting product uses sliding-window counters that approximate GCRA.
• Message queues: producers are throttled with GCRA so a slow consumer is never swamped.
• Database connection pools: new connections are rate-limited to prevent thundering-herd reconnects from cascading into a full outage.
• WebSocket and gRPC streams: per-stream message rates are enforced with the same virtual-clock logic, preventing one chatty client from starving others.

The pattern extends naturally to multi-tier limiting: global rate (e.g., 1000 req/s per tenant), per-endpoint rate, and per-user rate can each be a separate GCRA stored in Redis under a compound key. Because each check is $O(1)$, the layers compose without multiplicative cost.

Understanding GCRA also illuminates related algorithms: scheduling on network switches, max-flow shaping, and admission-control loops all rest on the same insight — track where time should be, not just where it is.

Rate limiting looks messy from the outside — token buckets, leaky buckets, sliding windows, fixed windows — but the Generic Cell Rate Algorithm reveals that all these strategies share a common skeleton: track when the next request is theoretically due, and reject anything that arrives too soon.

A single number per client. One $\max$ and one comparison per request. $O(1)$ time, $O(1)$ space, trivially atomic. Yet that tiny machine enforces any rate-plus-burst policy, is equivalent to both the token and leaky bucket, and scales to millions of clients in a Redis hash.

The next time a 429 bounces back at you, you now know exactly what clock just said no — and how much quiet time you need before it says yes again.