Skip to main content

Module shared_hash_map

subetha_cxc

Module shared_hash_map 

Source
Expand description

SharedHashMap<K, V> - cross-process open-addressed hash map backed by a single MMF file.

§Why open addressing?

All storage is inline. No allocator, no pointer indirection. Each slot lives in its own cache line; the entire table is a flat array in the MMF. Robin Hood, linear, and quadratic probing all work; we use linear probing because it’s the most cache- friendly on modern CPUs (sequential access dominates probe- variance on speculative-prefetch architectures).

§Stable hashing

std::hash::BuildHasher uses a per-process random seed for DoS resistance, which would make keys irreproducible across processes. We use FNV-1a over the key bytes - fast, deps-free, and deterministic across processes / runs / OSes.

§Layout

+---------------------------+
| MapHeader (64B)           |
|   magic, capacity, count  |
|   key_size, value_size    |
+---------------------------+
| Slot[0]  (64B cache line) |
|   state (EMPTY/OCC/TS)    |
|   version (SeqLock)       |
|   hash (cached)           |
|   payload [u8; 48]: K + V |
| Slot[1] ...               |
+---------------------------+

§Protocol

§Insert

  1. Hash key (FNV-1a).
  2. Probe from hash % capacity, linearly.
  3. At each slot:
    • Empty: CAS state Empty → Occupied. On success, SeqLock- write (K, V) and store hash; bump count. Return Inserted.
    • Occupied & hash matches & key matches: SeqLock-update V (state unchanged). Return Updated.
    • Occupied & no match: probe next slot.
    • Tombstone: skip (linear probe continues; tombstones do NOT terminate insert because we want to overwrite them preferentially - track first tombstone and use it if no Empty is found earlier than a definitive “not present” conclusion).

Actually the simpler insert: probe until first Empty (insert there) OR find key (update). The tombstone-reuse optimisation costs an extra bookkeeping pass; we skip it and reclaim tombstones via the compact() method (single-writer in-place rebuild) instead.

§Get

  1. Hash key, probe linearly.
  2. Empty: key absent (probe always terminates at Empty).
  3. Occupied & hash matches: SeqLock-read; if K matches, return V.
  4. Tombstone or hash mismatch: continue probing.

§Remove

  1. Find key (same probe).
  2. CAS state Occupied → Tombstone. count.fetch_sub(1).

§Concurrency

All slot writes are SeqLock-protected so readers never observe torn key+value. The state byte’s CAS is the serialisation point for who “owns” a slot for write. Two writers racing on the same key both reach the same slot; one wins the Empty→Occupied CAS and writes; the loser falls through to “Occupied + key matches” and updates instead.

§Capacity and load factor

Fixed at create time. Recommend capacity = 2 * expected_max to keep load factor below 0.5; linear probing degrades sharply above 0.7. insert returns MapError::Full when the probe chain saturates.

§If you need dynamic sizing, use SharedUniversal

SharedHashMap deliberately does NOT implement resize-on-grow. Cross-process resize requires the same reader-coordination machinery as MMF-backed migration (atomic file rename, reader re-open signaling). Rather than reinvent that machinery inside SharedHashMap, callers who need a dynamically-resizing hash map should use crate::shared_universal::SharedUniversal<T> configured with hash-map-only backings. The migration mechanism handles cross-process resize correctly, with the reader-side generation-bump protocol that makes wrap-around safe.

Structs§

MapHeader
MapSlot
SharedHashMap

Enums§

InsertOutcome
MapError

Constants§

MAP_MAGIC
MAP_PAYLOAD_BYTES
SLOT_EMPTY
SLOT_OCCUPIED
SLOT_TOMBSTONE

Functions§

fnv1a_64
FNV-1a 64-bit over a byte slice. Deterministic across processes (unlike std::hash::BuildHasher which uses per-process random seeds for DoS resistance).
map_file_size