Expand description
A bounded concurrent map of minted SURBs that evicts a random record when it is full.
§Why random eviction
A SURB is remembered from the moment it is minted until its reply comes home, and a FIFO replier
spends its oldest SURB first, so the record whose reply is due next is always the oldest one.
Any policy that evicts by age or recency (LRU, FIFO) therefore evicts exactly the records about to
be needed: once the outstanding SURBs exceed the capacity, every record whose reply waits longer
than capacity / mint rate is gone before its reply arrives, so a Session with a long wait
matches none of its replies at all, and has no record left when a dead-relayer verdict needs to
find its SURBs.
Evicting a uniformly random record degrades gracefully instead. Each mint into a full map evicts
a record chosen without regard to its age, so a record survives its wait with probability about
(1 - 1/capacity) raised to the number of evicting mints during that wait: the longer the wait,
the more it loses, smoothly (exponentially), and no Session drops to exactly zero, as one does
under eviction by age. When every Session waits alike, with ρ the outstanding SURBs divided by
the capacity, the share h of replies that still find their record solves h = e^(-(1 - h) ρ):
about 91 % at ρ = 1.05 and about 20 % at ρ = 2. Sessions whose waits differ lose unequally: in
the simulation of under_overload_no_session_should_lose_all_its_replies, a Session waiting three
times as long as its busy neighbour matches 83 % of its replies against the neighbour’s 94 % at
ρ = 1.05, and 3 % against 32 % at ρ = 2. The newest record is always admitted: a full map
never refuses it.
§Layout
The map is split into shards, each a parking_lot::Mutex over an IndexMap (a dense vector
of records, so a random one is picked and removed in constant time) and the state of a small
xorshift RNG. Nothing is ever called while a shard lock is held except the caller’s closure of
for_each and update, which must
not call back into the same map. An evicted record is handed back to the caller of
insert, who acts on it after the lock is released.
Structs§
- Entry
Layout 🔒 - The layout of one entry of the [
IndexMap] (hash, key, value), whose own type is private, so that its size can be read at compile time. - IdHasher 🔒
- A hasher for the 8 random bytes of a [
HoprSurbId]: already uniform, so folding them in and spreading the high bits down is all the table needs. Much cheaper than SipHash, with no use for its resistance to chosen keys: the ids are minted here, not chosen by a peer. - Random
Eviction Map - A concurrent map of at most a fixed number of records keyed by [
HoprSurbId], evicting a random record to admit a new one when full. See the module docs for why. - Shard 🔒
- A shard: its records and the state of its eviction RNG.
- Slot 🔒
- A stored record: the value and when it was last written (inserted or updated), for expiry.
Constants§
- EXPIRY_
SWEEP_ 🔒STEPS - The fraction of the shards one
expire_stepsweeps, as a divisor: every shard is swept once per this many steps. - GROWTH_
DIVISOR 🔒 - A shard’s record storage grows by at least a
1 / GROWTH_DIVISORof its length at a time, so growing costs a bounded share of what is already held and never more than that is spare. - HASH_
MULTIPLIER 🔒 - The multiplier of the id hash of a shard’s table and of the RNG’s output (Knuth’s 64-bit LCG constant and the xorshift64* multiplier).
- INDEX_
BYTES_ 🔒PER_ RECORD - Bytes the index of one record costs, as a rule of thumb rather than a hard bound: the hash table
of the [
IndexMap] keeps oneusizeand one control byte per bucket, its bucket count is a power of two and it is never more than 7/8 full, which is up to about 2.3 buckets per record just after it doubled. Under churn, hashbrown resizes instead of rehashing in place when a table full of deleted-record tombstones holds more than half its capacity, which can double the index once more. That was not seen in the measured churn (a million records, evictions and removals), where the resident memory stayed within the accounted figure thanks to the other conservative terms ofrecord_bytes(the growth spare, and the figure being the worst case at a full shard). - MAX_
SHARDS 🔒 - Most shards a map is split into.
- MIN_
GROWTH_ 🔒STEP - The fewest records a shard’s storage grows by at a time.
- RECORDS_
PER_ 🔒SHARD - Most records one shard is meant to hold before the map is split further: a record walk or an expiry sweep holds one shard lock at a time, so this bounds how long a lock is held.
- RNG_
MULTIPLIER 🔒 - SHARD_
MULTIPLIER 🔒 - The multiplier that picks a record’s shard from its id (a golden-ratio constant), so that ids that are not uniformly random (tests) still spread over the shards.
Functions§
- record_
bytes - The memory one record of value type
Vcosts, in bytes, in the worst case. - splitmix64 🔒
- splitmix64, to turn one seed into a distinct non-zero RNG state per shard.