Limen.State.Gcra (limen v0.2.1)

Copy Markdown View Source

Lock-free GCRA (generic cell rate algorithm) rate limiting on ETS.

GCRA was specified for ATM networks, to police the rate of cells on each connection. It is equivalent to a leaky bucket, but needs a single timestamp per key instead of a level and the time it was last updated.

How it works

A limit of rate requests per period spaces requests T = period / rate apart, the emission interval. Each key stores its theoretical arrival time (TAT): when it would next be due, had it sent at exactly that pace. A request moves the TAT to max(TAT, now) + T, and is admitted if that is at most T * (burst + 1) ahead of now, the burst tolerance. A client sending faster than the rate pushes its TAT further ahead until it is refused; one that pauses finds its TAT in the past and starts afresh.

With 10 requests per second (T = 100 ms) and burst: 2 (a tolerance of 300 ms):

nownew TATaheadresult
0100100admitted
0200200admitted
0300300admitted
0400400refused, retry in 100 ms
150400250admitted
20002100100admitted, as a new key

Over any interval of length Δ, at most Δ / T + burst + 1 requests are admitted. For more, see Wikipedia, and Rate limiting, cells, and GCRA, which compares it with other rate limiting algorithms.

Implementation

Each key stores a single integer, its TAT in microseconds of monotonic time, and is updated with one :ets.update_counter/3 call that applies TAT' = max(TAT, now) + T atomically:

  1. {2, -1, now, now - 1} yields max(TAT, now) - 1: decrement, and if the result fell below now, reset it to now - 1;
  2. {2, T + 1} then yields max(TAT, now) + T.

A rejected request rolls its increment back, so rejected traffic does not push the key further into the future.

Keys whose TAT is in the past carry no information (a fresh key behaves the same), so sweep/1 removes them. New keys are refused once the table holds :gcra_max_keys entries; they are then not limited.

Summary

Types

result()

Functions

check(instance, key, rate, period, burst, now \\ System.monotonic_time(:microsecond))

Checks and records one request for key against a limit of rate requests per period milliseconds with burst extra requests allowed at once.

reset(instance, key)

Forgets key.

sweep(instance, now \\ System.monotonic_time(:microsecond))

Removes keys whose theoretical arrival time has passed and returns how many were removed.

Types

result()

@type result() :: :ok | {:error, retry_after_ms :: pos_integer()}

Functions

check(instance, key, rate, period, burst, now \\ System.monotonic_time(:microsecond))

@spec check(
  Limen.Instance.t(),
  term(),
  pos_integer(),
  pos_integer(),
  non_neg_integer(),
  integer()
) ::
  result()

Checks and records one request for key against a limit of rate requests per period milliseconds with burst extra requests allowed at once.

reset(instance, key)

@spec reset(Limen.Instance.t(), term()) :: :ok

Forgets key.

sweep(instance, now \\ System.monotonic_time(:microsecond))

@spec sweep(Limen.Instance.t(), integer()) :: non_neg_integer()

Removes keys whose theoretical arrival time has passed and returns how many were removed.