Skip to main content

Module surb_map

Module surb_map 

Source
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§

EntryLayout 🔒
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.
RandomEvictionMap
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_step sweeps, 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_DIVISOR of 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 one usize and 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 of record_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 V costs, in bytes, in the worst case.
splitmix64 🔒
splitmix64, to turn one seed into a distinct non-zero RNG state per shard.