CONCEPT Cited by 1 source

Reverse leaky bucket¶

Definition¶

A reverse leaky bucket is a rate-limiter topology in which each admitted unit of work accumulates debt in the bucket (rather than consuming credits), debt drains out of the bucket at a configured rate (rather than credits filling), and a bucket that would overflow with debt blocks the next admission. The bucket has two parameters: size (the burst limit — total debt allowed in a short time) and drain rate (the long-run steady-state admission share).

This is structurally identical to the classical leaky-bucket / token-bucket rate limiter with two semantic inversions:

	Classical leaky bucket	Reverse leaky bucket
Bucket starts	Full (max credits)	Empty (zero debt)
Accepting traffic	Consumes credits	Accumulates debt
Background process	Fills credits at rate `r`	Drains debt at rate `r`
Blocked when	Credits = 0	Debt would exceed size
Memory state when idle	Must hold max credits	Can be evicted (debt = 0)

Why the inversion matters¶

From sources/2026-04-21-planetscale-behind-the-scenes-how-database-traffic-control-works:

"Traditionally, leaky buckets work the other way: they start out full, they fill (but never overflow) with credits at a configured rate, traffic consumes credits, and if a bucket is ever empty, traffic gets blocked. We inverted the model for a simple reason: an empty bucket doesn't need to be stored. Over time, we may need to store many buckets for changing rules and changing query metadata. We can drop buckets with a zero debt level, meaning that we only need to store recently active buckets, instead of every possible bucket."

The inversion is motivated entirely by memory eviction. In classical leaky buckets, an idle entity's bucket is in its maximum (full-credit) state — its state is meaningful and can't be lost without giving the entity a burst advantage on next arrival. In a reverse leaky bucket, an idle entity's bucket is at zero debt, which is indistinguishable from "no bucket has ever been allocated for this entity," so the bucket is safely droppable. Re-allocating on next arrival re-initialises at zero debt, preserving the rate-limit semantics.

Operational parameters¶

In the PlanetScale Traffic Control instantiation:

Size = the burst limit — total resource (CPU-seconds, plan-cost-units, etc.) that queries under a budget may consume in a short burst.
Drain rate = the server share — the fraction of total server resources that queries under this budget may consume in the long run (expressed as drain-per-unit-time / total-capacity-per-unit-time).

Eviction policy¶

Reverse leaky buckets compose naturally with lazy update and lazy eviction: no dedicated thread drains or sweeps; both happen on bucket access. On new-bucket insertion, the data structure evicts any bucket at zero debt, or (if none) the bucket expected to hit zero soonest. The shared-memory footprint is thereby a configurable cap on simultaneously-active rate-limited entities, not on the total configured entity space.

Trade-offs vs. classical¶

Dimension	Classical	Reverse
Memory per configured entity	Full bucket always	Only active buckets
Cold-start burst advantage	Absent (bucket starts full but is pre-allocated)	Absent (newly-created bucket starts at zero debt)
Steady-state semantics	Identical	Identical
Easier to reason about?	Credit-style matches human intuition	Debt-style matches queue-depth intuition

Seen in¶

sources/2026-04-21-planetscale-behind-the-scenes-how-database-traffic-control-works — canonical wiki source. Patrick Reynolds (PlanetScale, 2026-03-23) canonicalises the reverse-leaky-bucket framing for per-workload-class resource budgets. The motivation is the scale of the configured rule space vs. the shared-memory budget available to the pginsights extension: potentially many <tag, budget> combinations, only a small active subset at any moment.