pyrate_limiter.abstracts.algorithm module

Rate-limiting algorithm abstraction.

Separates the policy (which rates admit an item, how long a rejected one waits, how far back items may be leaked) from the storage that counts and persists them. Internal in v4; v5 promotes it to a public extension point.

Retry-after rides on Decision so one check under one lock yields both the verdict and the wait. Deriving it afterwards costs a second round trip and reads state that may have moved - and is impossible for algorithms whose state is not a log (token bucket, GCRA), which compute the wait in closed form.

pyrate_limiter.abstracts.algorithm.ADMITTED = Decision(failing_rate=None, retry_after_ms=None)

Reused on every admit; Decision is immutable, so the hot path allocates nothing.

class pyrate_limiter.abstracts.algorithm.Algorithm

Bases: ABC

A rate-limiting policy, independent of any storage backend.

Implementations must be stateless so one instance can be shared across buckets and threads. The two sub-interfaces differ in what they need remembered per key: LogAlgorithm an entry per consumed unit, StateAlgorithm a fixed handful of numbers.

max_weight(rate)

Largest weight this policy can ever admit under rate.

Return type:

int

class pyrate_limiter.abstracts.algorithm.Decision(failing_rate=None, retry_after_ms=None)

Bases: object

Outcome of an admit check.

retry_after_ms is measured from the checked item’s own timestamp. None means “unknown, ask AbstractBucket.waiting()” - either the weight can never fit, or the backend does not compute a wait. It does not mean “no wait”.

property allowed

failing_rate = None

retry_after_ms = None

class pyrate_limiter.abstracts.algorithm.FixedWindow

Bases: LogAlgorithm

Counts within a wall-clock-aligned window that resets every interval.

Cheaper and coarser than the rolling window: up to 2 * limit can pass across a window boundary. Use it to mirror an upstream API that genuinely resets on the hour rather than rolling.

admit(rates, counts, weight)

Whether weight more units fit, given counts aligned to rates.

Return type:

Decision

retry_after(rate, now, blocking_timestamp)

Milliseconds until room exists under rate.

blocking_timestamp is the entry named by blocking_offset(), or None when there is none - or when the policy never asks for one.

Return type:

int

window_start(rate, now)

Inclusive lower bound of rate’s counting window at now.

Return type:

int

class pyrate_limiter.abstracts.algorithm.GCRA

Bases: StateAlgorithm

Generic Cell Rate Algorithm - a leaky bucket kept as one timestamp.

Tracks a theoretical arrival time (TAT) per rate: the moment the bucket would next be empty. Admitting weight pushes the TAT forward by weight * emission_interval; the request is allowed while that stays within burst units of now.

Sustains limit per interval while tolerating a burst of rate.burst, using one number per rate instead of an entry per unit.

State is integer microseconds, not fractional milliseconds. An absolute TAT in epoch ms is ~1.7e12, and accumulating a fractional emission interval onto it loses the low bits - enough that the accumulated sum of burst emissions no longer equals burst * emission, and the last unit of a full burst gets rejected by a rounding error. Integers make it exact, and stay well inside the 2**53 a Lua double holds.

consumed(rates, state, now)

Units currently owed - the closest analogue to a log’s length.

Return type:

int

decode(values)

Parse persisted strings back into state.

Return type:

Tuple[float, ...]

initial(rates)

State for a key that has never been used.

Return type:

Tuple[float, ...]

max_weight(rate)

Largest weight this policy can ever admit under rate.

Return type:

int

redis_args(rates)

Arguments redis_script() needs, after the standard header.

The store passes these through without inspecting them, so a policy’s script and its arguments stay a matched pair that only the policy knows the shape of. The header the store supplies first is now, weight, ttl_ms, len(rates).

Return type:

List[int | float]

redis_script()

Lua implementing step() atomically, if this policy has one.

Return type:

str | None

step(rates, state, now, weight)

Apply an arrival of weight at now.

Returns the state to persist and the verdict. On denial it must return state unchanged: a rejected request spends nothing, under any rate.

Return type:

Tuple[Tuple[float, ...], Decision]

class pyrate_limiter.abstracts.algorithm.LogAlgorithm

Bases: Algorithm

Policy over storage holding one timestamped entry per consumed unit.

abstractmethod admit(rates, counts, weight)

Whether weight more units fit, given counts aligned to rates.

Return type:

Decision

blocking_offset(rate, weight)

Offset from the newest stored entry (0-based) whose expiry makes room for weight, or None if the wait does not depend on an entry.

Return type:

int | None

decide(rates, counts, weight, now, peek_timestamp)

admit(), resolving the retry-after in the same step on denial.

peek_timestamp(offset) is only called when the policy asks for an entry and the item was rejected, so backends pay for the lookup only when it is needed.

Return type:

Decision

leak_bound(rates, now)

Timestamp below which an entry is outside every rate’s window.

Return type:

int

abstractmethod retry_after(rate, now, blocking_timestamp)

Milliseconds until room exists under rate.

blocking_timestamp is the entry named by blocking_offset(), or None when there is none - or when the policy never asks for one.

Return type:

int

abstractmethod window_start(rate, now)

Inclusive lower bound of rate’s counting window at now.

Return type:

int

class pyrate_limiter.abstracts.algorithm.SlidingWindowLog

Bases: LogAlgorithm

Precise rolling window: admit while each rate’s last interval stays under its limit.

The default. Exact, at the cost of one stored entry per consumed unit.

admit(rates, counts, weight)

Whether weight more units fit, given counts aligned to rates.

Return type:

Decision

blocking_offset(rate, weight)

Offset from the newest stored entry (0-based) whose expiry makes room for weight, or None if the wait does not depend on an entry.

Return type:

int | None

retry_after(rate, now, blocking_timestamp)

Milliseconds until room exists under rate.

blocking_timestamp is the entry named by blocking_offset(), or None when there is none - or when the policy never asks for one.

Return type:

int

window_start(rate, now)

Inclusive lower bound of rate’s counting window at now.

Return type:

int

pyrate_limiter.abstracts.algorithm.State

Constant-state policies keep a small tuple of floats per key, opaque to the store that persists it. GCRA uses one theoretical-arrival-time per rate.

alias of Tuple[float, …]

class pyrate_limiter.abstracts.algorithm.StateAlgorithm

Bases: Algorithm

Policy whose state is a fixed-size tuple of numbers, not a log.

Storage keeps one small value per key however much traffic passes, and the wait comes out in closed form. In exchange the check is destructive - it spends what it admits - so step() must evaluate every rate before committing any of them.

consumed(rates, state, now)

Units currently owed - the closest analogue to a log’s length.

Return type:

int

decode(values)

Parse persisted strings back into state.

Return type:

Tuple[float, ...]

abstractmethod initial(rates)

State for a key that has never been used.

Return type:

Tuple[float, ...]

redis_args(rates)

Arguments redis_script() needs, after the standard header.

The store passes these through without inspecting them, so a policy’s script and its arguments stay a matched pair that only the policy knows the shape of. The header the store supplies first is now, weight, ttl_ms, len(rates).

Return type:

List[int | float]

redis_script()

Lua implementing step() atomically, if this policy has one.

Return type:

str | None

abstractmethod step(rates, state, now, weight)

Apply an arrival of weight at now.

Returns the state to persist and the verdict. On denial it must return state unchanged: a rejected request spends nothing, under any rate.

Return type:

Tuple[Tuple[float, ...], Decision]

class pyrate_limiter.abstracts.algorithm.TokenBucket

Bases: GCRA

Token bucket, which is GCRA under a more familiar name.

A bucket of rate.burst tokens refilling at rate.limit / rate.interval admits exactly what GCRA does with an emission interval of interval / limit. Same implementation, one float of state rather than a token count plus a refill timestamp.