Skip to content

[BUG] Rate limiters allow small bounded overshoot under simultaneous cross-node bursts (SELECT-then-UPDATE not atomic) #1334

Description

@jsbattig

Problem

The PostgreSQL-backed token-bucket rate limiters perform their decrement as a
non-atomic SELECT tokens ... ; UPDATE tokens = tokens - cost ... guarded only by
a per-process lock. Under simultaneous cross-node bursts for the same key, two nodes
can both read tokens >= cost and both decrement, allowing a small bounded
overshoot
beyond the configured rate.

This affects both PG-backed token buckets:

This is an accepted limitation today (the overshoot is bounded by concurrency, and it
is a massive improvement over the pre-#1332 configured x workers x nodes behavior).
The #1332 docstrings were made honest about it ("bounded ... small transient overshoot
possible under simultaneous cross-node bursts"). Filing so strict bounding can be done
deliberately if ever required.

Proposed fix

Replace the SELECT-then-UPDATE in TokenBucketManager._pg_consume with a single
atomic conditional decrement, e.g.:

UPDATE <table> SET tokens = tokens - %s, last_access = %s
WHERE <key_column> = %s AND tokens >= %s
RETURNING tokens
  • Row present + sufficient tokens -> one row returned, decremented atomically.
  • Insufficient tokens -> zero rows -> deny.
  • Combine with the existing refill computation (may need a refill-then-decrement in one
    statement or a short transaction with SELECT ... FOR UPDATE).

Applies to BOTH limiters (shared TokenBucketManager), so it is a single change with
broad blast radius -> requires the full auth + admission test suites, and a real-PG
concurrency test proving no overshoot under simultaneous cross-node consumption.

Acceptance criteria

  • _pg_consume decrement is atomic (single conditional UPDATE ... RETURNING or
    SELECT FOR UPDATE transaction); no SELECT-then-UPDATE race window.
  • Refill semantics preserved (bucket refills correctly across the atomic path).
  • Real-PG concurrency test: N concurrent consumers on one key across simulated
    nodes never exceed the configured capacity (zero overshoot).
  • Auth login limiter behavior unchanged functionally (regression suite green).
  • Docstrings updated to state strict bounding once achieved.

Severity

priority-4. Bounded, non-corrupting, accepted today; strict bounding is a hardening.
Source: code review of #1332 (non-blocking note #2).

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Fields

    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions