Rate Limits
link-relay-limits keeps rate limits by key, in bounded memory: a
token bucket for each key (a visitor, a tunnel, a peer), so one key's
burst never spends another's. Every limit the relay and Link's services
keep is made of it.
A bucket
A bucket holds up to Rate::burst tokens and gains Rate::per_second
back each second; each thing limited takes one. Rate::one_every(burst, every) is burst at once, then one every every. Limits::new
refuses a rate no bucket can keep (BadRate): a per_second that isn't
a finite number above 0, or a burst that isn't a finite number of 1 or
more.
Its calls
What a caller asks of Limits, each given now: it keeps no clock, so
a caller with a clock of its own, a test's, uses it.
check and take
check says whether a key has a token now, or how long until it has
one, and takes none. take takes one token if the key has one, and says
what was taken: all of one, or none where the key went untracked.
spend and refund
spend takes one token whether the key has one or not, for a thing
done that was checked before: less than one when the bucket was near
empty, none when the key went untracked. refund gives back what take
or spend took, for a thing that turned out not to count.
tracks, forget_if_full, len and is_empty
tracks says whether a key is counted: it has a bucket, or one fits
now. A caller for whom an untracked key must not pass refuses it when
this is false. forget_if_full lets a key go once its bucket is full
again; len and is_empty say how many keys have a bucket now.
Bounded memory
A key with no bucket has a full one, so the map holds only keys that
spent something lately, and Limits::new's most of them at most.
When it's full
A full map is looked through for buckets full again (the same as
none), at most once a SWEEP_EVERY, a second. If none is, a new key
goes untracked, so a flood of new keys costs neither memory nor a scan
each, and is never refused for others' sake.
A second limit over all
Whatever a key's limit guards needs a second limit over all of them (a tunnel's over its visitors) where a flood must not get through untracked.