Skip to main content

hopr_transport/protocol/
surb_map.rs

1//! A bounded concurrent map of minted SURBs that evicts a random record when it is full.
2//!
3//! # Why random eviction
4//!
5//! A SURB is remembered from the moment it is minted until its reply comes home, and a FIFO replier
6//! spends its oldest SURB first, so the record whose reply is due next is always the *oldest* one.
7//! Any policy that evicts by age or recency (LRU, FIFO) therefore evicts exactly the records about to
8//! be needed: once the outstanding SURBs exceed the capacity, every record whose reply waits longer
9//! than `capacity / mint rate` is gone before its reply arrives, so a Session with a long wait
10//! matches none of its replies at all, and has no record left when a dead-relayer verdict needs to
11//! find its SURBs.
12//!
13//! Evicting a uniformly random record degrades gracefully instead. Each mint into a full map evicts
14//! a record chosen without regard to its age, so a record survives its wait with probability about
15//! `(1 - 1/capacity)` raised to the number of evicting mints during that wait: the longer the wait,
16//! the more it loses, smoothly (exponentially), and no Session drops to exactly zero, as one does
17//! under eviction by age. When every Session waits alike, with `ρ` the outstanding SURBs divided by
18//! the capacity, the share `h` of replies that still find their record solves `h = e^(-(1 - h) ρ)`:
19//! about 91 % at `ρ = 1.05` and about 20 % at `ρ = 2`. Sessions whose waits differ lose unequally: in
20//! the simulation of `under_overload_no_session_should_lose_all_its_replies`, a Session waiting three
21//! times as long as its busy neighbour matches 83 % of its replies against the neighbour's 94 % at
22//! `ρ = 1.05`, and 3 % against 32 % at `ρ = 2`. The newest record is always admitted: a full map
23//! never refuses it.
24//!
25//! # Layout
26//!
27//! The map is split into shards, each a `parking_lot::Mutex` over an `IndexMap` (a dense vector
28//! of records, so a random one is picked and removed in constant time) and the state of a small
29//! xorshift RNG. Nothing is ever called while a shard lock is held except the caller's closure of
30//! `for_each` and `update`, which must
31//! not call back into the same map. An evicted record is handed back to the caller of
32//! `insert`, who acts on it after the lock is released.
33
34use std::{
35    hash::{BuildHasherDefault, Hasher},
36    sync::atomic::{AtomicUsize, Ordering},
37    time::{Duration, Instant},
38};
39
40use hopr_api::types::internal::prelude::HoprSurbId;
41use indexmap::{IndexMap, map::Entry};
42use parking_lot::Mutex;
43
44/// Most records one shard is meant to hold before the map is split further: a record walk or an
45/// expiry sweep holds one shard lock at a time, so this bounds how long a lock is held.
46const RECORDS_PER_SHARD: usize = 4096;
47
48/// Most shards a map is split into.
49const MAX_SHARDS: usize = 64;
50
51/// The fraction of the shards one [`expire_step`](RandomEvictionMap::expire_step) sweeps, as a divisor:
52/// every shard is swept once per this many steps.
53const EXPIRY_SWEEP_STEPS: usize = 16;
54
55/// A shard's record storage grows by at least a `1 / GROWTH_DIVISOR` of its length at a time, so
56/// growing costs a bounded share of what is already held and never more than that is spare.
57const GROWTH_DIVISOR: usize = 16;
58
59/// The fewest records a shard's storage grows by at a time.
60const MIN_GROWTH_STEP: usize = 16;
61
62/// Bytes the index of one record costs, as a rule of thumb rather than a hard bound: the hash table
63/// of the [`IndexMap`] keeps one `usize` and one control byte per bucket, its bucket count is a power
64/// of two and it is never more than 7/8 full, which is up to about 2.3 buckets per record just after
65/// it doubled. Under churn, hashbrown resizes instead of rehashing in place when a table full of
66/// deleted-record tombstones holds more than half its capacity, which can double the index once more.
67/// That was not seen in the measured churn (a million records, evictions and removals), where the
68/// resident memory stayed within the accounted figure thanks to the other conservative terms of
69/// [`record_bytes`] (the growth spare, and the figure being the worst case at a full shard).
70const INDEX_BYTES_PER_RECORD: usize = (23 * (size_of::<usize>() + 1)).div_ceil(10);
71
72/// The multiplier that picks a record's shard from its id (a golden-ratio constant), so that ids that
73/// are not uniformly random (tests) still spread over the shards.
74const SHARD_MULTIPLIER: u64 = 0x9E37_79B9_7F4A_7C15;
75
76/// The multiplier of the id hash of a shard's table and of the RNG's output (Knuth's 64-bit LCG
77/// constant and the xorshift64* multiplier).
78const HASH_MULTIPLIER: u64 = 0x517C_C1B7_2722_0A95;
79const RNG_MULTIPLIER: u64 = 0x2545_F491_4F6C_DD1D;
80
81/// A stored record: the value and when it was last written (inserted or updated), for expiry.
82#[derive(Debug, Clone, Copy)]
83struct Slot<V> {
84    value: V,
85    written: Instant,
86}
87
88/// The layout of one entry of the [`IndexMap`] (hash, key, value), whose own type is private, so that
89/// its size can be read at compile time.
90#[allow(dead_code)]
91struct EntryLayout<V> {
92    hash: usize,
93    key: HoprSurbId,
94    slot: Slot<V>,
95}
96
97/// The memory one record of value type `V` costs, in bytes, in the worst case.
98///
99/// The entry itself, the spare of the storage that grows in steps (`1 / GROWTH_DIVISOR` of the
100/// entries), and the index that finds it. A map holds `budget / record_bytes::<V>()` records, so each
101/// map honours its byte budget from its own type instead of from a figure measured on another.
102/// Allocator overhead and fragmentation are not included.
103pub const fn record_bytes<V>() -> usize {
104    let entry = size_of::<EntryLayout<V>>();
105    entry + entry.div_ceil(GROWTH_DIVISOR) + INDEX_BYTES_PER_RECORD
106}
107
108/// A hasher for the 8 random bytes of a [`HoprSurbId`]: already uniform, so folding them in and
109/// spreading the high bits down is all the table needs. Much cheaper than SipHash, with no use for
110/// its resistance to chosen keys: the ids are minted here, not chosen by a peer.
111#[derive(Default)]
112struct IdHasher(u64);
113
114impl IdHasher {
115    fn fold(&mut self, word: u64) {
116        self.0 = (self.0.rotate_left(5) ^ word).wrapping_mul(HASH_MULTIPLIER);
117    }
118}
119
120impl Hasher for IdHasher {
121    fn write(&mut self, bytes: &[u8]) {
122        for chunk in bytes.chunks(size_of::<u64>()) {
123            let mut word = [0u8; size_of::<u64>()];
124            word[..chunk.len()].copy_from_slice(chunk);
125            self.fold(u64::from_le_bytes(word));
126        }
127    }
128
129    fn write_usize(&mut self, length: usize) {
130        self.fold(length as u64);
131    }
132
133    fn finish(&self) -> u64 {
134        // The table takes its bucket from the low bits and its tag from the high ones.
135        self.0 ^ (self.0 >> 32)
136    }
137}
138
139/// A shard: its records and the state of its eviction RNG.
140struct Shard<V> {
141    entries: IndexMap<HoprSurbId, Slot<V>, BuildHasherDefault<IdHasher>>,
142    rng: u64,
143}
144
145impl<V> Shard<V> {
146    /// xorshift64*: a few instructions under a lock already held, and no allocation or shared state.
147    fn next_random(&mut self) -> u64 {
148        let mut x = self.rng;
149        x ^= x >> 12;
150        x ^= x << 25;
151        x ^= x >> 27;
152        self.rng = x;
153        x.wrapping_mul(RNG_MULTIPLIER)
154    }
155
156    /// A uniform index below `len`, from the high bits of the RNG.
157    fn random_below(&mut self, len: usize) -> usize {
158        ((u128::from(self.next_random()) * len as u128) >> u64::BITS) as usize
159    }
160
161    /// Makes room for one more record without ever growing past `capacity`.
162    ///
163    /// The storage is grown in steps, not to `capacity` up front, because a map sized for the 4 GiB
164    /// ceiling would otherwise ask for gigabytes at startup for a node that never fills it; and with
165    /// `reserve_exact`, so that it never holds more than `capacity` either.
166    fn make_room(&mut self, capacity: usize) {
167        let len = self.entries.len();
168        if len >= self.entries.capacity() {
169            let step = (len / GROWTH_DIVISOR).max(MIN_GROWTH_STEP).min(capacity - len);
170            self.entries.reserve_exact(step);
171        }
172    }
173}
174
175/// splitmix64, to turn one seed into a distinct non-zero RNG state per shard.
176fn splitmix64(state: u64) -> u64 {
177    let mut z = state.wrapping_add(0x9E37_79B9_7F4A_7C15);
178    z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
179    z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
180    z ^ (z >> 31)
181}
182
183/// A concurrent map of at most a fixed number of records keyed by [`HoprSurbId`], evicting a random
184/// record to admit a new one when full. See the [module docs](self) for why.
185pub struct RandomEvictionMap<V> {
186    shards: Box<[Mutex<Shard<V>>]>,
187    /// log2 of the number of shards.
188    shard_bits: u32,
189    /// Records one shard holds; the map holds at most `shards.len()` times this.
190    shard_capacity: usize,
191    /// Where the next [`expire_step`](Self::expire_step) starts.
192    next_sweep: AtomicUsize,
193}
194
195impl<V> std::fmt::Debug for RandomEvictionMap<V> {
196    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
197        f.debug_struct("RandomEvictionMap")
198            .field("shards", &self.shards.len())
199            .field("shard_capacity", &self.shard_capacity)
200            .finish_non_exhaustive()
201    }
202}
203
204impl<V> RandomEvictionMap<V> {
205    /// A map holding as many records as fit in `budget_bytes`, at [`record_bytes`] each, seeded from
206    /// the system RNG. Always holds at least one.
207    pub fn new(budget_bytes: u64) -> Self {
208        let records = usize::try_from(budget_bytes / record_bytes::<V>() as u64).unwrap_or(usize::MAX);
209        Self::with_seed(records, rand::random::<u64>())
210    }
211
212    /// A map holding at most `records` records (at least one), with the eviction RNG seeded by `seed`:
213    /// the same inserts evict the same records, for deterministic tests.
214    ///
215    /// The map is split into a power of two of shards, about one per [`RECORDS_PER_SHARD`] records, so
216    /// that a map of a few thousand records is a single shard and evicts uniformly over all of it.
217    pub(crate) fn with_seed(records: usize, seed: u64) -> Self {
218        let records = records.max(1);
219        let shard_count = (1usize << (records / RECORDS_PER_SHARD).max(1).ilog2()).min(MAX_SHARDS);
220        let shard_capacity = (records / shard_count).max(1);
221        Self {
222            shards: (0..shard_count)
223                .map(|shard| {
224                    Mutex::new(Shard {
225                        entries: IndexMap::default(),
226                        rng: splitmix64(seed.wrapping_add(shard as u64)) | 1,
227                    })
228                })
229                .collect(),
230            shard_bits: shard_count.ilog2(),
231            shard_capacity,
232            next_sweep: AtomicUsize::new(0),
233        }
234    }
235
236    /// The most records the map holds.
237    #[cfg_attr(not(any(test, feature = "testing")), allow(dead_code))]
238    pub fn capacity(&self) -> usize {
239        self.shards.len() * self.shard_capacity
240    }
241
242    fn shard_of(&self, id: &HoprSurbId) -> &Mutex<Shard<V>> {
243        let index = if self.shard_bits == 0 {
244            0
245        } else {
246            (u64::from_le_bytes(*id).wrapping_mul(SHARD_MULTIPLIER) >> (u64::BITS - self.shard_bits)) as usize
247        };
248        &self.shards[index]
249    }
250
251    /// Stores `value` under `id` and returns the record it evicted to make room, if the map was full.
252    ///
253    /// The new record is always admitted. Replacing the record under `id` evicts nothing. The evicted
254    /// record is returned, not handled, so the caller acts on it after the lock is released.
255    pub fn insert(&self, id: HoprSurbId, value: V) -> Option<(HoprSurbId, V)> {
256        let slot = Slot {
257            value,
258            written: Instant::now(),
259        };
260        let mut shard = self.shard_of(&id).lock();
261        let full = shard.entries.len() >= self.shard_capacity;
262        match shard.entries.entry(id) {
263            Entry::Occupied(mut occupied) => {
264                occupied.insert(slot);
265                return None;
266            }
267            Entry::Vacant(_) if full => {}
268            Entry::Vacant(_) => {
269                shard.make_room(self.shard_capacity);
270                shard.entries.insert(id, slot);
271                return None;
272            }
273        }
274        let len = shard.entries.len();
275        let victim = shard.random_below(len);
276        let evicted = shard
277            .entries
278            .swap_remove_index(victim)
279            .map(|(evicted_id, evicted)| (evicted_id, evicted.value));
280        shard.entries.insert(id, slot);
281        evicted
282    }
283
284    /// Takes the record under `id` out of the map.
285    pub fn remove(&self, id: &HoprSurbId) -> Option<V> {
286        self.shard_of(id)
287            .lock()
288            .entries
289            .swap_remove(id)
290            .map(|removed| removed.value)
291    }
292
293    /// Changes the record under `id` in place and returns what `change` returns, or `None` if there is
294    /// no such record.
295    ///
296    /// The change happens under the shard's lock and never inserts, so a record that a concurrent
297    /// [`remove`](Self::remove) took is never brought back by it.
298    ///
299    /// An update counts as a write: the record's expiry runs from it, as it did when the update was a
300    /// re-insert. The registry opens every reply race through such an update, so after it the record
301    /// lives a further full horizon, far past the race's own lifetime, and expiry can never drop a
302    /// record while a race that only its reply can close is still open.
303    pub fn update<R>(&self, id: &HoprSurbId, change: impl FnOnce(&mut V) -> R) -> Option<R> {
304        self.shard_of(id).lock().entries.get_mut(id).map(|slot| {
305            slot.written = Instant::now();
306            change(&mut slot.value)
307        })
308    }
309
310    /// Whether there is a record under `id`.
311    pub fn contains_key(&self, id: &HoprSurbId) -> bool {
312        self.shard_of(id).lock().entries.contains_key(id)
313    }
314
315    /// The number of records, summed over the shards one after the other, so approximate while the map
316    /// is being changed.
317    #[cfg_attr(not(any(test, feature = "testing")), allow(dead_code))]
318    pub fn len(&self) -> usize {
319        self.shards.iter().map(|shard| shard.lock().entries.len()).sum()
320    }
321
322    /// Whether the map holds no record, to the same approximation as [`len`](Self::len).
323    #[cfg_attr(not(any(test, feature = "testing")), allow(dead_code))]
324    pub fn is_empty(&self) -> bool {
325        self.shards.iter().all(|shard| shard.lock().entries.is_empty())
326    }
327
328    /// Calls `visit` for every record, shard by shard, holding one shard's lock at a time.
329    ///
330    /// A record moved or removed while the walk is on another shard may be visited twice or not at all,
331    /// and `visit` must not call back into this map, which it would deadlock on: collect what it needs
332    /// and act after the walk.
333    pub fn for_each(&self, mut visit: impl FnMut(&HoprSurbId, &V)) {
334        for shard in &self.shards {
335            for (id, slot) in &shard.lock().entries {
336                visit(id, &slot.value);
337            }
338        }
339    }
340
341    /// Drops the records last written longer than `horizon` ago from the next `1 / EXPIRY_SWEEP_STEPS` of
342    /// the shards (at least one), so that every shard is swept once per that many calls, and returns
343    /// how many it dropped.
344    ///
345    /// Called once per flush tick, which at a horizon of minutes sweeps every shard far more often than
346    /// it must, and holds one shard lock at a time.
347    pub fn expire_step(&self, horizon: Duration) -> usize {
348        let per_step = self.shards.len().div_ceil(EXPIRY_SWEEP_STEPS);
349        let start = self.next_sweep.fetch_add(per_step, Ordering::Relaxed);
350        let mut expired = 0;
351        for offset in 0..per_step {
352            let mut shard = self.shards[(start + offset) % self.shards.len()].lock();
353            let before = shard.entries.len();
354            shard.entries.retain(|_, slot| slot.written.elapsed() <= horizon);
355            expired += before - shard.entries.len();
356        }
357        expired
358    }
359}
360
361#[cfg(test)]
362impl<V: Clone> RandomEvictionMap<V> {
363    /// A copy of the record under `id`.
364    pub(crate) fn get(&self, id: &HoprSurbId) -> Option<V> {
365        self.shard_of(id).lock().entries.get(id).map(|slot| slot.value.clone())
366    }
367}
368
369#[cfg(test)]
370mod tests {
371    use std::sync::{Arc, Barrier};
372
373    use anyhow::Context;
374
375    use super::*;
376
377    const SEED: u64 = 0x5EED;
378
379    fn id(n: u32) -> HoprSurbId {
380        let mut id = [0u8; 8];
381        id[..4].copy_from_slice(&n.to_le_bytes());
382        id
383    }
384
385    #[test]
386    fn a_map_should_never_hold_more_than_its_capacity() {
387        let map = RandomEvictionMap::<u32>::with_seed(100, SEED);
388        for n in 0..1_000 {
389            map.insert(id(n), n);
390            assert!(map.len() <= 100, "{} records after {} inserts", map.len(), n + 1);
391        }
392        assert_eq!(100, map.len(), "and it fills up to it");
393    }
394
395    #[test]
396    fn a_sharded_map_should_never_hold_more_than_its_capacity() {
397        let map = RandomEvictionMap::<u32>::with_seed(5 * RECORDS_PER_SHARD, SEED);
398        assert!(map.shards.len() > 1, "large enough to be split");
399        assert!(map.capacity() <= 5 * RECORDS_PER_SHARD);
400        for n in 0..4 * map.capacity() as u32 {
401            map.insert(id(n), n);
402        }
403        assert!(map.len() <= map.capacity());
404    }
405
406    #[test]
407    fn the_newest_record_should_always_be_present_after_it_is_inserted() {
408        let map = RandomEvictionMap::<u32>::with_seed(8, SEED);
409        for n in 0..200 {
410            map.insert(id(n), n);
411            assert_eq!(Some(n), map.get(&id(n)), "record {n} must not be refused");
412        }
413    }
414
415    #[test]
416    fn inserting_into_a_full_map_should_return_the_evicted_record() -> anyhow::Result<()> {
417        let map = RandomEvictionMap::<u32>::with_seed(4, SEED);
418        for n in 0..4 {
419            assert!(map.insert(id(n), n).is_none(), "nothing is evicted while there is room");
420        }
421        let (evicted_id, evicted) = map.insert(id(4), 4).context("a full map evicts")?;
422        assert_eq!(id(evicted), evicted_id);
423        assert!(!map.contains_key(&evicted_id), "and it is gone");
424        assert_eq!(4, map.len());
425        Ok(())
426    }
427
428    #[test]
429    fn replacing_a_record_should_evict_nothing() {
430        let map = RandomEvictionMap::<u32>::with_seed(4, SEED);
431        for n in 0..4 {
432            map.insert(id(n), n);
433        }
434        assert!(map.insert(id(2), 99).is_none());
435        assert_eq!(Some(99), map.get(&id(2)));
436        assert_eq!(4, map.len());
437    }
438
439    #[test]
440    fn updating_a_removed_record_should_find_nothing_and_not_bring_it_back() {
441        let map = RandomEvictionMap::<u32>::with_seed(4, SEED);
442        map.insert(id(1), 1);
443        assert_eq!(Some(1), map.remove(&id(1)));
444        assert!(map.update(&id(1), |value| *value += 1).is_none());
445        assert!(!map.contains_key(&id(1)), "an update never inserts");
446        assert!(map.is_empty());
447
448        map.insert(id(2), 5);
449        assert_eq!(
450            Some(6),
451            map.update(&id(2), |value| {
452                *value += 1;
453                *value
454            })
455        );
456        assert_eq!(Some(6), map.get(&id(2)));
457    }
458
459    /// The race this map exists to close: a record consumed by one thread while another updates it
460    /// must stay consumed, which a read-compute-insert update cannot promise.
461    #[test]
462    fn a_record_removed_while_it_is_updated_should_never_come_back() -> anyhow::Result<()> {
463        const ROUNDS: usize = 20_000;
464        let map = Arc::new(RandomEvictionMap::<u32>::with_seed(16, SEED));
465        let barrier = Arc::new(Barrier::new(3));
466        let key = id(7);
467
468        let remover = {
469            let (map, barrier) = (map.clone(), barrier.clone());
470            std::thread::spawn(move || {
471                for _ in 0..ROUNDS {
472                    barrier.wait();
473                    map.remove(&key);
474                    barrier.wait();
475                }
476            })
477        };
478        let updater = {
479            let (map, barrier) = (map.clone(), barrier.clone());
480            std::thread::spawn(move || {
481                for _ in 0..ROUNDS {
482                    barrier.wait();
483                    map.update(&key, |value| *value += 1);
484                    barrier.wait();
485                }
486            })
487        };
488        for round in 0..ROUNDS {
489            map.insert(key, 0);
490            barrier.wait();
491            barrier.wait();
492            assert!(!map.contains_key(&key), "round {round}: the removed record came back");
493        }
494        remover.join().map_err(|_| anyhow::anyhow!("remover thread panicked"))?;
495        updater.join().map_err(|_| anyhow::anyhow!("updater thread panicked"))?;
496        Ok(())
497    }
498
499    #[test]
500    fn expiring_should_drop_only_the_records_past_the_horizon() {
501        const HORIZON: Duration = Duration::from_millis(20);
502        let map = RandomEvictionMap::<u32>::with_seed(16, SEED);
503        map.insert(id(1), 1);
504        map.insert(id(2), 2);
505        std::thread::sleep(2 * HORIZON);
506        map.insert(id(3), 3);
507
508        assert_eq!(2, map.expire_step(HORIZON));
509        assert!(!map.contains_key(&id(1)) && !map.contains_key(&id(2)));
510        assert!(map.contains_key(&id(3)), "a younger record stays");
511        assert_eq!(0, map.expire_step(HORIZON));
512    }
513
514    /// An update restarts the record's expiry. The registry opens a reply race by updating the partner's
515    /// record, which may be nearly a horizon old: expiring it by its mint time would drop it while the
516    /// race it just opened is live, and its reply could then settle nothing. The registry's horizon is
517    /// the const `PENDING_SURB_HORIZON` of 15 minutes, too long for a test of its own, so this is the
518    /// test of that guarantee, with a short horizon.
519    #[test]
520    fn an_update_should_restart_the_expiry_of_the_record() {
521        // Long enough that each check has 400 ms of slack on either side, so a loaded machine that
522        // stalls the test between a sleep and a check does not fail it.
523        const HORIZON: Duration = Duration::from_secs(1);
524        let map = RandomEvictionMap::<u32>::with_seed(16, SEED);
525        map.insert(id(1), 1);
526        std::thread::sleep(HORIZON * 6 / 10);
527        assert_eq!(Some(()), map.update(&id(1), |value| *value += 1));
528        // The insert is now past the horizon, the update is not.
529        std::thread::sleep(HORIZON * 6 / 10);
530        assert_eq!(0, map.expire_step(HORIZON), "expiry counts from the update");
531        assert_eq!(Some(2), map.get(&id(1)));
532        std::thread::sleep(HORIZON * 6 / 10);
533        assert_eq!(1, map.expire_step(HORIZON), "and it expires a horizon after the update");
534    }
535
536    #[test]
537    fn expiring_should_reach_every_shard_within_a_cycle_of_steps() {
538        const HORIZON: Duration = Duration::from_millis(10);
539        let map = RandomEvictionMap::<u32>::with_seed(MAX_SHARDS * RECORDS_PER_SHARD, SEED);
540        assert_eq!(MAX_SHARDS, map.shards.len());
541        for n in 0..2_000 {
542            map.insert(id(n), n);
543        }
544        std::thread::sleep(2 * HORIZON);
545        let first = map.expire_step(HORIZON);
546        assert!(first < 2_000, "one step sweeps only part of the shards");
547        let rest: usize = (1..EXPIRY_SWEEP_STEPS).map(|_| map.expire_step(HORIZON)).sum();
548        assert_eq!(2_000, first + rest);
549        assert!(map.is_empty());
550    }
551
552    /// Past capacity a record survives a mint with probability `1 - 1/capacity` whatever its age:
553    /// after as many mints again, a record of the first batch is still there with probability
554    /// `(1 - 1/n)^n ≈ 1/e` — not 0, as for an eviction by age.
555    #[test]
556    fn eviction_should_not_favour_the_young_or_the_old() {
557        const N: u32 = 1_000;
558        let map = RandomEvictionMap::<u32>::with_seed(N as usize, SEED);
559        for n in 0..N {
560            map.insert(id(n), n);
561        }
562        for n in N..2 * N {
563            map.insert(id(n), n);
564        }
565        let old = (0..N).filter(|n| map.contains_key(&id(*n))).count();
566        let young = (N..2 * N).filter(|n| map.contains_key(&id(*n))).count();
567        assert_eq!(N as usize, old + young);
568        // 1/e of 1000 is 368.
569        assert!((300..440).contains(&old), "{old} of the old batch survived");
570    }
571
572    #[test]
573    fn a_walk_should_visit_every_record_once() {
574        let map = RandomEvictionMap::<u32>::with_seed(2 * RECORDS_PER_SHARD, SEED);
575        for n in 0..1_000 {
576            map.insert(id(n), n);
577        }
578        let mut seen = std::collections::HashSet::new();
579        map.for_each(|id, _| assert!(seen.insert(*id)));
580        assert_eq!(1_000, seen.len());
581    }
582
583    #[test]
584    fn storage_should_grow_in_steps_and_never_past_the_capacity() {
585        const CAPACITY: usize = 1_000;
586        let map = RandomEvictionMap::<u32>::with_seed(CAPACITY, SEED);
587        assert_eq!(
588            0,
589            map.shards[0].lock().entries.capacity(),
590            "nothing is reserved up front"
591        );
592        map.insert(id(0), 0);
593        assert!(map.shards[0].lock().entries.capacity() < CAPACITY / 4);
594        for n in 1..3 * CAPACITY as u32 {
595            map.insert(id(n), n);
596            assert!(map.shards[0].lock().entries.capacity() <= CAPACITY);
597        }
598        assert_eq!(CAPACITY, map.shards[0].lock().entries.capacity());
599    }
600
601    #[test]
602    fn the_shard_count_should_follow_the_capacity() {
603        let shards = |records| RandomEvictionMap::<u32>::with_seed(records, SEED).shards.len();
604        assert_eq!(1, shards(0));
605        assert_eq!(1, shards(1));
606        assert_eq!(1, shards(2 * RECORDS_PER_SHARD - 1));
607        assert_eq!(2, shards(2 * RECORDS_PER_SHARD));
608        assert_eq!(MAX_SHARDS, shards(usize::MAX / 2));
609    }
610
611    #[test]
612    fn a_budget_should_buy_records_at_the_cost_of_its_own_type() {
613        let budget = 1_000 * record_bytes::<u64>() as u64;
614        assert_eq!(1_000, RandomEvictionMap::<u64>::new(budget).capacity());
615        assert!(record_bytes::<[u8; 512]>() > record_bytes::<u64>());
616        assert_eq!(1, RandomEvictionMap::<u64>::new(0).capacity(), "never fewer than one");
617    }
618}