Rate limiter: one limit for a fleet of gateways

"Design a rate limiter that caps how many requests a client may make, in front of an API served by many servers."

functional

Allow or refuse each call. Tell the client when to retry. Change rules without a deploy.

latency

Under 1 ms added at p50: one Redis round trip at most.

availability

A limiter failure must not take the API down.

accuracy

Exact for login and paid calls; approximate is fine for reads.

I assume 5 billion API calls a day, 10 million clients, 2 rules per request, and under 1 ms added at p50.

5 billion calls, 10 million keys, 2 rules, a 3× peak and 50 gateways are assumptions. 25,000 script decisions a second per Redis is the B3 lab number. Memory per key is Redis MEMORY USAGE, measured here on Redis 8.10.2.

At peak the limiter makes about 347,222 decisions a second. Memory is small; throughput needs a Redis Cluster or fewer Redis calls.

• 429 is defined in RFC 6585 and Retry-After in RFC 9110. An IETF draft adds RateLimit and RateLimit-Policy header fields; until it is final, many APIs send X-RateLimit-* headers.
• Key the limit by the authenticated client, not the IP. Many users share one NAT address.
• A request with a cost, such as a batch of 50, takes 50 from the count.

The limiter has no public endpoint of its own. Clients see 429 with Retry-After; operators change rules through an admin call that bumps a version.

-- One row per limit. '*' matches any tier or any route.
CREATE TABLE rate_rules (
  tier        text    NOT NULL,
  route       text    NOT NULL,
  limit_count int     NOT NULL CHECK (limit_count > 0)2,
  window_ms   int     NOT NULL CHECK (window_ms >= 1000),
  fail_open   boolean3 NOT NULL DEFAULT true,
  PRIMARY KEY (tier, route)1
);

-- One version for the whole rule set. Every change to rate_rules bumps it.
CREATE TABLE rule_version (
  id      int    PRIMARY KEY CHECK (id = 1),
  version bigint NOT NULL
);
INSERT INTO rule_version VALUES (1, 1);

CREATE FUNCTION bump_rule_version() RETURNS trigger LANGUAGE plpgsql AS $$
BEGIN
  UPDATE rule_version SET version = version + 1 WHERE id = 1;
  RETURN NULL;
END $$;

CREATE TRIGGER rate_rules_changed
AFTER INSERT OR UPDATE OR DELETE ON rate_rules
FOR EACH STATEMENT4 EXECUTE FUNCTION bump_rule_version();

Rules are a small versioned table in Postgres. Counters are small expiring keys in Redis, one per client and window, under a hash tag.

The gateway decides; Redis counts; Postgres holds the rules. The API servers see only the calls the limiter admitted.

Redis gives me atomic scripts, counters with expiry and hash tags. Postgres gives me a durable, versioned rule set. The gateway gives me one place to enforce both.

on request(client, route):
  rule = rules.for(client.tier, route)      // memory, no I/O1
  d = redis_script(key(client, rule), now)   // ONE atomic step2
  IF d.allowed:
    forward; add RateLimit-Remaining3: d.remaining
  ELSE:
    RETURN 429, Retry-After: ceil(d.retry_after)4

-- Fixed window: count requests in the current window; refuse once the count passes the limit.
-- KEYS[1] the counter for this window: rl:{user:42}:fw:<window start, ms>
-- ARGV[1] now, ms    ARGV[2] window, ms    ARGV[3] limit
-- Returns {allowed, retry after ms, remaining, delay ms}.
local now = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local limit = tonumber(ARGV[3])
local count = redis.call('INCR', KEYS[1])
if count == 1 then
  redis.call('PEXPIRE', KEYS[1], window)
end
if count <= limit then
  return {1, 0, limit - count, 0}
end
local window_end = now - now % window + window
return {0, window_end - now, 0, 0}

if !dec.Allowed {
  secs := (dec.RetryAfter + time.Second - 1) / time.Second
  w.Header().Set("Retry-After", strconv.FormatInt(int64(secs), 10))
  http.Error(w, "too many requests", http.StatusTooManyRequests)
  return
}

I put the limiter in the gateway, in process, with the counts in Redis. In a service mesh, a sidecar does the same job per service.

allow(client, now):                        // memory only1
  w = window of now
  IF known[client, w] + pending[client, w]2 >= limit:
    RETURN refuse
  pending[client, w] += 1
  RETURN allow

every interval:                              // one round trip3
  FOR EACH (client, w) seen in this window:
    known[client, w] = INCRBY global(client, w), pending4
    pending[client, w] = 0
  IF Redis fails: keep pending for the next sync5

// Allow implements Gate. It never calls Redis.
func (g *SyncGate) Allow(_ context.Context, client string, now time.Time) (bool, error) {
  k := winKey{client, windowStart(now, g.Window)}
  g.mu.Lock()
  defer g.mu.Unlock()
  if g.known[k]+g.pending[k] >= g.Limit {
    return false, nil
  }
  g.pending[k]++
  return true, nil
}

// Sync adds this instance's pending admits to the global counts and reads them back. It returns
// the number of Redis commands it sent.
func (g *SyncGate) Sync(ctx context.Context, now time.Time) (int, error) {
  cur := windowStart(now, g.Window)
  g.mu.Lock()
  batch := map[winKey]int64{}
  for k := range g.known {
    if k.start < cur {
      delete(g.known, k) // a past window can no longer admit anything
    } else {
      batch[k] = 0 // read the global count even if this instance admitted nothing
    }
  }
  for k, n := range g.pending {
    batch[k] = n
  }
  g.pending = map[winKey]int64{}
  g.mu.Unlock()
  if len(batch) == 0 {
    return 0, nil
  }

  keys := make([]winKey, 0, len(batch))
  cmds := make([]*redis.IntCmd, 0, len(batch))
  _, err := g.RDB.Pipelined(ctx, func(p redis.Pipeliner) error {
    for k, n := range batch {
      keys = append(keys, k)
      cmds = append(cmds, p.IncrBy(ctx, SyncKey(k.client, k.start), n))
      if n > 0 {
        p.PExpire(ctx, SyncKey(k.client, k.start), 2*g.Window)
      }
    }
    return nil
  })
  if err != nil {
    g.mu.Lock()
    for k, n := range batch {
      g.pending[k] += n // keep the admits; the next sync pushes them
    }
    g.mu.Unlock()
    return 0, fmt.Errorf("sync %d counters: %w", len(batch), err)
  }

  g.mu.Lock()
  sent := 0
  for i, k := range keys {
    g.known[k] = cmds[i].Val()
    sent++
    if batch[k] > 0 {
      sent++ // the PEXPIRE
    }
  }
  g.mu.Unlock()
  return sent, nil
}

A shared Redis count is exact and costs one call per request. For the heaviest keys, I count locally and sync every second; that over-admits by about one second of traffic.

With memory-only limits, more gateways means more admits. The shared count stays exact at any fleet size; the synced design stays close, with far fewer Redis calls.

d = limiter(client, now)    // with a short timeout1
IF the limiter fails:
  IF rule.fail_open2: log it; serve the request
  ELSE: RETURN 5033, Retry-After: 1
IF NOT d.allowed:
  RETURN 429, Retry-After: whole seconds, rounded up

if err != nil {
  if mode == FailOpen {
    log.Warn("rate limiter unavailable; failing open", "client", c, "err", err)
    next.ServeHTTP(w, r)
    return
  }
  log.Error("rate limiter unavailable; failing closed", "client", c, "err", err)
  w.Header().Set("Retry-After", "1")
  http.Error(w, "rate limiter unavailable", http.StatusServiceUnavailable)
  return
}

if !dec.Allowed {
  secs := (dec.RetryAfter + time.Second - 1) / time.Second
  w.Header().Set("Retry-After", strconv.FormatInt(int64(secs), 10))
  http.Error(w, "too many requests", http.StatusTooManyRequests)
  return
}

Each rule carries its failure mode. A hot tenant gets a local tier, so it stops costing one Redis call per request.

rule_for(tier, route):                     // most specific wins1
  try (tier, route), (tier, *), (*, route), (*, *)

every 10 s, on each gateway:
  v = SELECT version                         // one tiny read2
  IF v == current.version: done
  set = SELECT every rule                    // one snapshot3
  IF set has no (*, *) default:
    keep the old set; alert4
  current = set                              // one atomic swap5

// For returns the most specific rule: tier and route, then tier only, then route only, then the
// default.
func (rs *RuleSet) For(tier, route string) Rule {
  for _, k := range [][2]string{{tier, route}, {tier, "*"}, {"*", route}, {"*", "*"}} {
    if r, ok := rs.rules[k]; ok {
      return r
    }
  }
  panic("rule set without a default rule") // Reload refuses such a set
}

// Reload reads the version, and only when it changed, every rule. It checks the new set before
// it swaps it in with one atomic store; a bad set leaves the old one in use.
func (r *Rules) Reload(ctx context.Context) (bool, error) {
  var v int64
  if err := r.db.QueryRow(ctx, sqls["version"]).Scan(&v); err != nil {
    return false, fmt.Errorf("read rule version: %w", err)
  }
  if old := r.cur.Load(); old != nil && old.Version == v {
    return false, nil
  }
  rows, err := r.db.Query(ctx, sqls["load"])
  if err != nil {
    return false, fmt.Errorf("load rules: %w", err)
  }
  defer rows.Close()
  set := &RuleSet{rules: map[[2]string]Rule{}}
  for rows.Next() {
    var rl Rule
    var ms int
    if err := rows.Scan(&set.Version, &rl.Tier, &rl.Route, &rl.Limit, &ms, &rl.FailOpen); err != nil {
      return false, fmt.Errorf("scan rule: %w", err)
    }
    rl.Window = time.Duration(ms) * time.Millisecond
    set.rules[[2]string{rl.Tier, rl.Route}] = rl
  }
  if err := rows.Err(); err != nil {
    return false, fmt.Errorf("read rules: %w", err)
  }
  if _, ok := set.rules[[2]string{"*", "*"}]; !ok {
    return false, fmt.Errorf("version %d: %w", v, ErrNoDefault)
  }
  r.cur.Store(set)
  return true, nil
}

A round trip across an ocean is about 150 ms (R2). Shared regional counts are the sync design at a larger scale: the error grows with the share interval.

Rules reload on a version change with one atomic swap. Across regions, each region counts locally and shares its counts in the background, so the global limit is approximate.

Demand as in panel B. Capacity bars are the B3 lab numbers from one loaded laptop; read them as orders of magnitude.

I start with one Redis and one script per request. I add a cluster when decisions outgrow one node, and local counts for heavy keys when Redis load is the cost.