ratelimit

A token bucket that holds at most burst tokens and refills continuously at rate tokens per period_ms (as golang.org/x/time/rate with a limit of rate / period and a burst). A request of cost n takes n tokens. Build it with token_bucket, which checks that the arithmetic is exact.

The generic cell rate algorithm (as redis-cell): limit requests per period_ms, at most burst of them at once. Its state is one number, the theoretical arrival time, kept in microseconds. It allows the same requests as a token bucket with the same numbers. Build it with gcra.

A window of window_ms milliseconds in which at most limit cost units are allowed, for the fixed and sliding window algorithms.

The algorithm a limiter runs. FixedWindow counts per calendar window (cheap, but allows up to twice the limit across a boundary), SlidingLog keeps every request in the window (exact, memory grows with the limit), SlidingCounter weighs the previous window's count by how much of it still overlaps (Cloudflare's approximation, two numbers of state; it assumes the previous window's requests were spread evenly, rounds the weighted count up, and can allow more than the limit in a sliding window only when they clustered at its end).

One allowed request in a sliding log.

The state a policy keeps per key. fresh makes the initial one; a state of another policy's shape counts as fresh, so changing a key's policy starts it over.

The answer for one request. limit is the quota (the burst of a bucket), remaining what is left of it after this request, reset_ms the time until the quota is whole again, retry_after_ms 0 when allowed, the wait before a request of the same cost can succeed when denied, or -1 when the cost is larger than the quota and can never succeed.

A token bucket after the x/time/rate convention: rate tokens per period_ms, burst at most.

A GCRA policy: limit requests per period_ms, burst at once. The emission interval must be at least a microsecond and the burst tolerance must fit in 2^62 microseconds.

limit per window_ms, for the window policies.

n requests per second, with a burst of n, as a token bucket.

n requests per minute, with a burst of n, as a token bucket.

n requests per hour, with a burst of n, as a token bucket.

The quota of a policy: the burst of a bucket or GCRA, the limit of a window.

The time in milliseconds over which the whole quota is granted: the window, or the time a bucket takes to refill from empty (rounded up).

The state of a key that has not been seen, at now_ms.

Decides a request of cost units for a key in state s (none for a new key) at now_ms, and returns the decision and the key's next state. A cost of 0 only reports the current status. A clock that goes backwards never grants more: the state's own time is used instead.

Decides a whole sequence of requests (now_ms, cost) for one key from a fresh state; handy in tests and simulations.

The absolute time in milliseconds after which s is the same as a fresh state, so a store may forget the key.

A reservation of cost tokens: ok when it was granted, and then the request may act delay_ms later, at act_at_ms.

The tokens in the bucket at now_ms (negative while reservations owe tokens), rounded down.

The wait in milliseconds until cost tokens are there, without taking them: 0 now, -1 if cost is more than the burst.

Reserves cost tokens, letting the bucket go into debt, when they will be there within max_wait_ms; the caller waits delay_ms and then acts. Otherwise nothing is reserved. As x/time/rate's ReserveN with a deadline.

Gives back the tokens of a granted reservation that has not acted yet (its time is after now_ms), up to a full bucket. Unlike x/time/rate it does not subtract tokens later reservations took, so a cancel may restore slightly more than a perfect ledger would.

A fixed-size, lock-free table for the policies memory_supported accepts, shared by the handlers of one process (they may share only atomics). Each slot is a pair of Atomic[Int]: the key's 64-bit fingerprint and its packed state, updated with compare-and-swap, so a decision is exact under any contention. A key is looked up in probes consecutive slots from the one its hash names, claiming an empty one or one whose state has fully recovered (an idle key, whose state equals a fresh one). When every probed slot is busy with other keys, the key shares its home slot with them: sharing only ever denies earlier, never allows more. Size it at about twice the number of keys active within one window; used shows the occupancy. It is opaque and has no Eq or Show, because it holds atomics.

A table of slots slots probing probes of them per key.

Whether the in-memory table can run p: token buckets and GCRA (as GCRA) and fixed windows, whose state fits in one 64-bit word. Sliding windows need the SQLite store.

The GCRA with the same numbers as a token bucket; both allow the same requests.

Decides a request of cost for key in the table at now_ms. Exact under concurrent calls: the update is a compare-and-swap loop on the key's slot.

The status of key without taking anything (a cost of 0).

Forgets key's state, as if it had never been seen: whether it was in the table.

How many slots hold a key.

A SQLite table of states, one row per key with its JSON state and the time it expires. Every decision is a transaction (BEGIN IMMEDIATE), so processes sharing the database file, and the handlers of one process sharing the Db, never lose an update. Works with every policy.

Whether s can name the store's table: a letter or underscore, then letters, digits and underscores, at most 63 characters.

Opens the store in c, creating the table table (and its expiry index) when missing.

Decides a request of cost for key at now_ms in one transaction, and stores the new state when the request is allowed.

The status of key without taking anything; reads only.

Forgets key: whether it had a row.

Deletes the rows of keys whose state has fully recovered by now_ms; the number deleted. Run it now and then (each decision only touches its own key).

How many keys have a row.

An IP address: IPv4 as a 32-bit number, IPv6 as two 64-bit halves.

A network: an address and a prefix length.

Parses an IPv4 address in dotted decimal (no leading zeros, which some parsers read as octal) or an IPv6 address in any RFC 4291 text form, including :: and a dotted IPv4 tail. Zone ids and brackets are not accepted.

An IPv4-mapped IPv6 address (::ffff:192.0.2.1) as the IPv4 address it maps; others unchanged.

The text of an address: dotted decimal, or the RFC 5952 form of IPv6 (lower case, no leading zeros, the longest run of zero groups as ::).

Parses addr/bits, or a bare address as a single-address network. Host bits may be set; they are ignored when matching.

Whether ip is in the network c. IPv4-mapped IPv6 addresses match IPv4 networks.

Parses a list of networks, skipping none: none if any entry is not a network.

Loopback, private (RFC 1918, RFC 4193), link-local and carrier-grade NAT networks: the usual addresses of proxies inside a deployment, to pass as trusted.

The client address from X-Forwarded-For by the rightmost-untrusted rule: the nearest address that isn't one of the trusted proxies. Only meaningful behind a proxy that appends to the header; sspur's server does not expose the peer address, so the nearest hop must be a proxy.

The client address hops entries from the right of X-Forwarded-For, for a fixed number of proxies (express's trust proxy = n); the leftmost entry when there are fewer.

The address in a single-valued header such as X-Real-IP, CF-Connecting-IP or Fly-Client-IP. Trust it only when the proxy in front always overwrites it.

One element of a Forwarded header (RFC 7239): the for, by, host and proto parameters, unquoted.

The elements of every Forwarded header of req, in order (nearest proxy last).

The client address from Forwarded for= values by the rightmost-untrusted rule. unknown and obfuscated identifiers (_hidden) are not addresses and stop the walk.

The key for one address: ip: and its canonical text (IPv4-mapped addresses as IPv4).

The key for the network of an address, so that one client can't escape the limit by rotating addresses within its allocation: the first v4_bits of IPv4, v6_bits of IPv6 (often 64).

The key of a route: the method and the path without the query.

One key from several parts (a user, a route, an address), unambiguously: each part is prefixed with its length, so ["a|b", "c"] and ["a", "b|c"] differ.

Whether s can name a policy in the RateLimit headers: 1 to 64 printable ASCII characters.

The RateLimit-Policy field of draft-ietf-httpapi-ratelimit-headers for one policy: its name, q the quota and w the window in seconds.

The RateLimit-Policy field listing several policies that apply to a request.

The RateLimit field for a decision under the policy name: r the remaining quota and t the seconds until it resets.

Adds the partition key parameter pk (an sf-binary of the key's bytes) to a RateLimit or RateLimit-Policy field, for clients that share a quota with others.

The legacy fields many clients read (GitHub, express-rate-limit): X-RateLimit-Limit, X-RateLimit-Remaining and X-RateLimit-Reset, the last as Unix seconds of the reset.

The seconds a denied client should wait, rounded up and at least 1; 0 when allowed or when the request can never succeed.

The Retry-After field (RFC 9110 10.2.3, delay-seconds) of a denied decision.

Which rate limit fields a response carries.

The fields for a decision in a style: the draft's RateLimit-Policy and RateLimit, the legacy X-RateLimit fields, both, or none; Retry-After is added by too_many.

A 429 Too Many Requests response (RFC 6585) with Retry-After, the rate limit fields of style, cache-control: no-store, and a text body, or with problem an RFC 9457 application/problem+json body.

How a wrapper limits requests: the policy and its name in the headers, the cost of a request, the header style, requests that are not limited (paths starting with one of skip_paths, methods in skip_methods, keys in allow_keys), whether 429s are problem+json, and whether a store failure lets the request through (fail_open) or answers 503.

A guard with the defaults: cost 1, draft headers, CORS preflights (OPTIONS) not limited, text 429s, and fail closed.

Whether g leaves the request with key key alone.

Applies a decision: an allowed request goes to next and its response gets the rate limit fields; a denied one gets too_many. This is the core the wrappers share, for limiters of your own.

Wraps next with a limit kept in the in-memory table t, per key that key gives for a request. Build it inside the handler (req => ratelimit.limit_memory(t, g, ratelimit.route_key, api)(req)): handlers may not share function values.

Wraps next with a limit kept in the SQLite store s. A database error answers 503, or with fail_open passes the request through unlimited.