Expand description
SharedLRUCache<K, V> - cross-process LRU cache.
Composite primitive demonstrating the layered-composition
thesis at full strength: combines
SharedHashMap<K, u32> for O(1) lookup
with SharedLinkedList<(K, V)> for
O(1) move-to-front and O(1) eviction.
§Files (3 per cache, all under a base path)
<base>.map.bin- the SharedHashMap<K, u32><base>.list.<region>- SharedLinkedList’s underlying region- (the linked list is single-file; uses one MMF for the region)
§Concurrency
get/contains_key/snapshot_*/len: lock-free read paths. Multi-reader safe at any concurrency. Does NOT promote MRU order.touch/get_and_touch/put/remove/evict_oldest: single-writer operations. Wrap in a SharedSemaphore(1) or the application’s own coordination for cross-process writer serialisation.
§Why split get vs touch
Many production caches (tokio::sync MokaCache, Java Caffeine)
separate the “look up the value” path from the “promote to MRU”
path. Read-heavy workloads where LRU ordering is approximate get
the cheap path; strict LRU workloads call get_and_touch. This
lets the cache be useful in both regimes.
§Eviction
put(k, v) always succeeds when the underlying map has room.
If the cache is at capacity AND k is not already present, the
LRU entry (back of list) is evicted first via pop_back +
map.remove.
§Long-running workload limit
The underlying SharedHashMap is sized
to 8x the cache capacity to absorb tombstone accumulation from
eviction. After roughly 7x capacity insert-then-evict cycles,
tombstones fill the map and put returns Map(Full). For
long-running workloads, either size the cache larger or wait for
the SharedHashMap.compact() reclamation primitive (separate
follow-on). For typical caches that hover near capacity, the
tombstone budget is far more than enough.