NAME Data::HashMap::Shared - Multiprocess shared-memory hash maps with LRU eviction and per-key TTL SYNOPSIS use Data::HashMap::Shared::II; # Create or open a shared map (file-backed mmap) my $map = Data::HashMap::Shared::II->new('/tmp/mymap.shm', 100000); # Keyword API (fastest) shm_ii_put $map, 42, 100; my $val = shm_ii_get $map, 42; # Method API $map->put(42, 100); my $v = $map->get(42); # Atomic counters (under the read lock, without LRU or TTL) shm_ii_incr $map, 1; # 1 shm_ii_incr_by $map, 1, 10; # 11 shm_ii_max $map, 1, 50; # monotonic: store max(current, 50) -> 50 # Compare-and-swap (all variants; byte-compare for string values) shm_ii_cas $map, 1, 50, 42; # swap to 42 only if current == 50 # LRU cache (evicts least-recently-used when full) my $cache = Data::HashMap::Shared::II->new('/tmp/cache.shm', 100000, 1000); shm_ii_put $cache, 42, 100; # auto-evicts LRU entry if size > 1000 # TTL (entries expire after N seconds) my $ttl_map = Data::HashMap::Shared::II->new('/tmp/ttl.shm', 100000, 0, 60); shm_ii_put $ttl_map, 1, 10; # expires in 60s shm_ii_put_ttl $ttl_map, 2, 20, 5; # per-key: expires in 5s # Multiprocess if (fork() == 0) { my $child = Data::HashMap::Shared::II->new('/tmp/mymap.shm', 100000); shm_ii_incr $child, 1; # atomic increment visible to parent exit; } wait; DESCRIPTION Data::HashMap::Shared provides type-specialized hash maps stored in file-backed shared memory (mmap(MAP_SHARED)) for multiprocess data sharing on Linux. With opt-in LRU eviction and per-key TTL it doubles as a fast cross-process cache; lookups take a lock-free seqlock path. Linux-only. Requires 64-bit Perl on a little-endian architecture. Features * File-backed mmap for cross-process sharing * Futex-based read-write lock (fast userspace path) * Atomic counters (incr/decr under the read lock on maps without LRU or TTL) * Elastic capacity (starts small, grows/shrinks automatically) * Arena allocator for string storage in shared memory * Keyword API via XS::Parse::Keyword for maximum speed * Opt-in LRU eviction -- clock/second-chance algorithm; reads stay lock-free * Opt-in per-key TTL expiry -- lazy removal on access; monotonic clock * Stale lock recovery for both writers and readers (dead PIDs detected and drained automatically) Variants Data::HashMap::Shared::I16 - int16 to int16 Data::HashMap::Shared::I32 - int32 to int32 Data::HashMap::Shared::II - int64 to int64 Data::HashMap::Shared::I16S - int16 to string Data::HashMap::Shared::I32S - int32 to string Data::HashMap::Shared::IS - int64 to string Data::HashMap::Shared::SI16 - string to int16 Data::HashMap::Shared::SI32 - string to int32 Data::HashMap::Shared::SI - string to int64 Data::HashMap::Shared::SS - string to string Integer Range and Wrapping Integer keys and values are fixed-width two's complement: 16-bit for "I16"/"SI16"/"I16S", 32-bit for "I32"/"SI32"/"I32S", 64-bit for "II"/"IS"/"SI". A number outside the variant's range is silently truncated to its low bits: on an "I16" map 70000 is key 4464. Numbers beyond 64 bits saturate first (1e20 becomes -1, NaN 0). "incr" and "decr" wrap the same way. Pick a variant wide enough for your data. Constructor my $map = Data::HashMap::Shared::II->new($path, $max_entries); my $map = Data::HashMap::Shared::II->new(undef, $max_entries); # anonymous my $map = Data::HashMap::Shared::II->new($path, $max_entries, $max_size); my $map = Data::HashMap::Shared::II->new($path, $max_entries, $max_size, $ttl); my $map = Data::HashMap::Shared::II->new($path, $max_entries, $max_size, $ttl, $lru_skip); my $map = Data::HashMap::Shared::SS->new($path, $max_entries, 0, 0, 0, $arena_cap); # explicit arena bytes my $map = Data::HashMap::Shared::II->new($path, $max_entries, $max_size, $ttl, $lru_skip, $arena_cap, $file_mode); my $map = Data::HashMap::Shared::II->new_sharded($prefix, $shards, $max_entries, $max_size, $ttl, $lru_skip, $arena_cap, $file_mode); my $map = Data::HashMap::Shared::II->new_memfd($name, $max_entries, ...); # memfd-backed my $map = Data::HashMap::Shared::II->new_from_fd($fd); # reopen memfd my $fd = $map->memfd; # -1 if not memfd Creates or opens a map backed by file $path; "undef" creates an anonymous mapping shared only with "fork"ed children. Any number of processes may open the same file. The sizing arguments apply only when the file is created: an existing file's header wins, though the arguments are still range-checked. Opening a file of another variant, or a corrupt one, croaks. A handle cannot cross into a new ithread or be copied: open the map again instead (in a thread, for a memfd map, with "new_from_fd" on a "$map->memfd" taken before the thread starts). "Storable" croaks on a handle; "Clone" makes a second object that frees the map under the first. "new_memfd" creates an unlinked memfd-backed map whose descriptor can be inherited across "fork" or sent with "SCM_RIGHTS"; $name is only a label and may be "undef". The descriptor is close-on-exec: pass POSIX::dup($map->memfd) across "exec". "new_from_fd" reopens such a descriptor from a duplicate, so the one you pass stays yours to close. "$map->memfd" returns the handle's own descriptor; do not close it. $max_size enables LRU eviction: an insert at $max_size entries evicts the least recently used (clock/second-chance; an eviction spares at most 64 recently read entries). 0 disables it. A $max_size at or above the table's slot count (2048 for $max_entries 1000) can never be reached, and the constructor warns (category "misc"). $ttl sets the default time-to-live in seconds (0 disables it). An expired entry is invisible to reads but keeps its slot, and counts in "size", until the next write to that key, a flush ("flush_expired", "flush_expired_partial"), or an insert that needs room: an insert flushes every expired entry at once when the table or arena is full or the table passes its design load. TTLs are whole seconds, truncated, so a TTL of "n" expires between "n-1" and "n" seconds later: refresh a heartbeat at least two seconds before its TTL. Every store resets an entry's TTL to the map default (a permanent entry stays permanent); "put_ttl", "update_ttl" and "set_ttl" set a per-key one. Expiry follows "CLOCK_MONOTONIC_COARSE", which restarts on reboot: TTLs do not survive a reboot or a move to another host. $lru_skip (0-99) reduces LRU promotion on updates to a power-of-two rate: below 50 every update promotes, 50 one in two, 90 one in sixteen, 99 one in 128. Reads never promote; they set the clock bit eviction consults. It pays off only on Zipfian write workloads; leave it at 0 otherwise. $arena_cap sizes the string arena in bytes (default about 128 per entry, clamped to 4096 .. 0xFFFFFFFF; per shard; ignored by integer-only variants). Keys and values of 7 bytes or fewer are stored inline and need no arena; one must stay under 1 GB. Arena blocks are powers of two from 16 bytes, recycled only within their size, and the arena reserves its first 16 bytes: size it from the rounded lengths, with room for a block of every size you store. When the arena is full, an insert on an LRU map evicts an entry and retries, and a TTL map flushes its expired entries; if that makes no room the store fails, so check what it returns. An overwrite stores the new value before freeing the old one and can fail the same way. Space freed in the wrong sizes is gathered by compaction, which the next store of the handle that was refused runs; "$map->compact" runs it on demand and returns the bytes reclaimed. "arena_used" is a high-water mark: only compaction, "clear" and refilling an emptied map lower it. $file_mode (default 0600) sets the permissions of a newly created file exactly, regardless of umask; above 07777 it croaks, except for a regular file's type bits, so "(stat $f)[2]" passes. Use 0660 to share across users. "get" and "exists" are lock-free (under write contention that keeps invalidating them they fall back to the read lock). On a map with neither LRU nor TTL, "incr", "decr", "incr_by", "max", "min" and an integer-value "cas" update an existing key under the read lock; every other write takes the write lock. String Keys/Values and UTF-8 String keys compare as raw bytes. The UTF-8 flag round-trips but is not part of the key: ASCII keys match whatever their flag, while a non-ASCII key in two encodings ("caf\xe9" and "caf\xc3\xa9") is two keys, which also collide in "to_hash". Normalize with "Encode::encode_utf8" when input encodings are mixed. A stored key keeps the flag it was first inserted with. String values round-trip their flag; "cas" compares bytes only. Sharding my $map = Data::HashMap::Shared::II->new_sharded($path_prefix, $shards, $max_entries, ...); Creates $shards maps (files "$path_prefix.0", "$path_prefix.1", ...) behind one handle, each sized as a map of its own. Keys route by hash, and writes to different shards run in parallel. $shards is rounded up to a power of two (0 is 1, more than 4096 croaks); a path prefix is required. All operations work on sharded maps; size and capacity figures are totals, and "reserve $n" grows each shard to $n. Use the smallest shard count that relieves lock contention. Batches and whole-map operations lock shard by shard, so they are not atomic across shards; "keys", "values", "items" and "to_hash" hold every shard's read lock until their copy is done. Cursors chain across shards. Every shard must come from the same configuration and shard count; a mismatch croaks. Treat the files as one unit: a shard file that goes missing is recreated empty, losing its keys. API Replace "xx" with variant prefix: "i16", "i32", "ii", "i16s", "i32s", "is", "si16", "si32", "si", "ss". my $ok = shm_xx_put $map, $key, $value; # insert or overwrite my $ok = shm_xx_add $map, $key, $value; # insert only if key absent my $ok = shm_xx_update $map, $key, $value; # overwrite only if key exists my $old = shm_xx_swap $map, $key, $value; # put + return old value (undef if new) my $ok = shm_xx_cas $map, $key, $expected, $desired; # compare-and-swap my $v = shm_xx_cas_take $map, $key, $expected; # compare-and-remove; returns value on match, undef otherwise my $n = $map->set_multi($k, $v, ...); # batch put under single lock, returns count my $n = $map->remove_multi(@keys); # batch remove under single lock, returns count my @v = $map->get_multi($k1, $k2, ...); # batch get under single lock with prefetch pipeline my ($v, $ttl) = $map->get_with_ttl($key); # atomic snapshot; () if missing, $ttl is undef on non-TTL map, 0 = permanent; sets LRU clock bit my $v = shm_xx_get $map, $key; # returns undef if not found my $ok = shm_xx_remove $map, $key; # returns false if not found my $ok = shm_xx_exists $map, $key; # returns boolean my $s = shm_xx_size $map; my $m = shm_xx_max_entries $map; my @k = shm_xx_keys $map; my @v = shm_xx_values $map; my @items = shm_xx_items $map; # flat (k, v, k, v, ...) while (my ($k, $v) = shm_xx_each $map) { ... } # auto-resets at end shm_xx_iter_reset $map; shm_xx_clear $map; my $href = shm_xx_to_hash $map; my $v = shm_xx_get_or_set $map, $key, $default; # returns value A store fails when there is no room: every table slot is taken or, for string data, the arena is full. Then "get_or_set" returns "undef", "add" and "cas" return false (as they do when the key exists or the value differs), and "swap" returns "undef" (as for a new key) and leaves an existing key alone; check "exists" when you need to tell these apart. "cas" compares strings byte-wise. "get_multi" returns one element per key, "undef" for a miss. The counters and integer "cas" on a map without LRU or TTL run under the read lock, so a bulk read ("get_multi", "values", "items", "to_hash") can combine values that never existed together; quiesce those updates for a consistent snapshot. Integer-value variants also have: my $n = shm_xx_incr $map, $key; # returns new value my $n = shm_xx_decr $map, $key; # returns new value my $n = shm_xx_incr_by $map, $key, $delta; my $n = shm_xx_max $map, $key, $desired; # store max(current, desired), return it my $n = shm_xx_min $map, $key, $desired; # store min(current, desired), return it A missing key starts from zero ("incr" returns 1), and "max"/"min" insert $desired. They die only when a new key finds no room, and wrap at the variant's width. "max" never lowers and "min" never raises a value, whatever runs concurrently. LRU/TTL operations ("put_ttl", "add_ttl", and "update_ttl" require a TTL-enabled map): my $ok = shm_xx_put_ttl $map, $key, $value, $ttl_sec; # per-key TTL (0 = permanent); requires TTL-enabled map my $ok = shm_xx_add_ttl $map, $key, $value, $ttl_sec; # insert-if-absent with per-key TTL (0 = permanent) my $ok = shm_xx_update_ttl $map, $key, $value, $ttl_sec; # overwrite-only with per-key TTL (0 = permanent) my $ms = shm_xx_max_size $map; # LRU capacity (0 = disabled) my $t = shm_xx_ttl $map; # default TTL in seconds my $r = shm_xx_ttl_remaining $map, $key; # whole seconds left, rounded up (0 = permanent, undef if missing/expired/no TTL) my $ok = shm_xx_touch $map, $key; # refresh TTL to default (permanent entries stay permanent); promotes in LRU; false if no TTL/LRU my $ok = shm_xx_persist $map, $key; # remove TTL, make key permanent; false on non-TTL maps my $ok = shm_xx_set_ttl $map, $key, $sec; # change TTL without changing value (0 = permanent); false on non-TTL maps my $n = shm_xx_flush_expired $map; # proactively expire all stale entries, returns count my ($n, $done) = shm_xx_flush_expired_partial $map, $limit; # scan $limit slots (per shard); $done at the end of a cycle Call "flush_expired_partial" on a timer with a $limit that cycles the whole table (the slots "max_entries" allows, divided by the ticks in a TTL window). Atomic remove-and-return: my $v = shm_xx_take $map, $key; # remove key and return value (undef if missing) my ($k, $v) = shm_xx_pop $map; # remove+return from LRU tail / scan forward my ($k, $v) = shm_xx_shift $map; # remove+return from LRU head / scan backward my @kv = shm_xx_drain $map, $n; # remove+return up to N entries as flat (k,v,...) list On an LRU map "pop" takes the least and "shift" the most recently used entry; otherwise they sweep the table from where their last call stopped. "drain" removes in "pop" order. All three return an empty list on an empty map. Cursors (independent iterators, allow nesting and removal during iteration): my $cur = shm_xx_cursor $map; # create cursor while (my ($k, $v) = shm_xx_cursor_next $cur) { ... } shm_xx_cursor_reset $cur; # restart from beginning my $ok = shm_xx_cursor_seek $cur, $key; # position at key (best-effort across resize); true if found, false if missing/expired # cursor auto-destroyed when out of scope $cur->next; $cur->reset; $cur->seek($key); # method forms "each" and cursors tolerate "remove" during iteration. A table resize restarts an iteration, which may then return keys again; under heavy churn from other processes a pass may never finish, while "keys", "values", "items" and "to_hash" always do. Leaving an "each" loop early keeps the iterator open and defers tombstone compaction on that handle: call "iter_reset" ("keys" does not reset it). Diagnostics: my $cap = shm_xx_capacity $map; # current table capacity (slots) my $tb = shm_xx_tombstones $map; # tombstone count my $au = shm_xx_arena_used $map; # arena high-water mark my $ac = shm_xx_arena_cap $map; # arena total capacity (0 for int-only) my $sz = shm_xx_mmap_size $map; # backing file size in bytes my $ok = shm_xx_reserve $map, $n; # pre-grow (false if exceeds max) my $ev = shm_xx_stat_evictions $map; # cumulative LRU eviction count my $ex = shm_xx_stat_expired $map; # cumulative TTL expiration count my $rc = shm_xx_stat_recoveries $map; # cumulative stale lock recovery count my $n = $map->compact; # reclaim the arena, returns bytes (method only) my $p = $map->path; # backing file path (method only; undef if none) my $s = $map->stats; # hashref with all diagnostics in one call (not an atomic snapshot) # stats keys: size, capacity, max_entries, tombstones, mmap_size, # arena_used, arena_cap, evictions, expired, recoveries, max_size, ttl, # frozen, readonly "max_entries" reports the entry count at the table's 75% design load (a map created with 1000 reports 1536, over 2048 slots). Inserts succeed beyond it until every slot is taken, but probes grow long near full: run at "max_entries", not above it. The table shrinks as entries go, so "reserve" again before refilling a drained map. "set_multi", "get_multi", "remove_multi", "get_with_ttl", "stats", "compact", "path", "sync", "unlink", "freeze", "frozen", "readonly" and "memfd" are method-only (no keyword form). Keywords take their arguments as a list without parentheses: shm_ii_put $map, $key, $value; # correct shm_ii_put($map, $key, $value); # wrong An argument that opens with a parenthesis ends at its close, so write "$t + 60", not "($t) + 60", in the last position. List-returning calls -- "keys", "values", "items", "each", "get_multi", "get_with_ttl", "pop", "shift", "drain", "flush_expired_partial", a cursor's "next" -- yield their last element in scalar context; use "size" for a count. "no Data::HashMap::Shared::II;" disables that variant's keywords in the enclosing scope. File management: $map->sync; # flush the mmap to the backing file (msync MS_SYNC) $map->unlink; # remove backing file (mmap stays valid) Data::HashMap::Shared::II->unlink($path); # class method form (single file) "sync" matters only for durability on disk; other processes see changes without it. "unlink" returns false instead of dying when nothing was removed; "$map->unlink" removes only the file the map was opened on, even after a "chdir" or a rename over its path. Frozen (Read-Only) Mode $map->freeze; # seal the file immutable (durable) my $ro = Data::HashMap::Shared::II->new_readonly($path); my $v = $ro->get($key); # lock-free query; writes nothing my $is_frozen = $map->frozen; # true once sealed my $is_readonly = $ro->readonly; # true for a read-only handle "freeze" seals a map for good, durably: every mutator croaks afterwards. Stop your writers first -- a write already under way when "freeze" runs, or the rest of a batch on a sharded map, still lands. "new_readonly" maps a frozen file read-only. Its queries take no lock and write nothing, so it works from a read-only filesystem and any number of processes can share the file; every query and iterator is supported. A frozen file cannot be opened read-write, and "new_readonly" refuses one that is not frozen. There is no read-only sharded constructor, so freeze single-file maps. A frozen file is a memory image: read it on the same architecture, and ship it by copying, not over a network filesystem. Crash Safety A writer that dies holding the lock (SIGKILL, OOM kill) is detected within 2 seconds, and the next process to take a lock recovers the map: an interrupted resize or "clear" is finished, the LRU list repaired, and an interrupted compaction leaves every entry intact. The entry being written at the time may be left stale or partial and some arena space may leak; call "clear" after a recovery ("stat_recoveries") where that matters. Upgrade every process sharing a map together. Each handle records its read locks in one of 1024 slots, so a killed reader is cleared by the next writer; a handle beyond 1024 runs without one, and its crash inside a read lock cannot be recovered. Every write scans the slots in use, so writes cost more as handles multiply. Liveness is tested with "kill($pid, 0)", so all processes must share one PID namespace, and a lock left by a process that died before a reboot or container restart can name a reused PID and block the map for good. Carry a map across a restart only if every process using it exited cleanly, and copy one only while nothing uses it. Keep a map on tmpfs ("/run", "/dev/shm"): on a disk filesystem under memory pressure, writeback can stall the lock holder, and everyone behind it, for hundreds of milliseconds. Perl croaks a call once 120 signals are pending. Long writes under the write lock block signals once one arrives, so the croak cannot land inside them, but it can still hit a write waiting for readers or reading a paged-out map back from disk: that write keeps the lock until its process exits. A read croaked inside its read lock keeps it until the handle next locks. This assumes Perl's deferred signals (not "PERL_SIGNALS=unsafe"); drive periodic work from an event loop rather than a fast signal timer. Map files are sparse, and a full filesystem raises SIGBUS in a writer touching a new page. Leave "mmap_size" bytes of headroom, or set "DATA_HASHMAP_SHARED_SPARSE=0" to reserve the space at creation (the constructor then croaks instead; on tmpfs and memfd this commits the memory, and "new_sharded" needs a free descriptor per shard while it creates the set). A creator killed mid-create leaves an all-zero file, which the next "new" initializes when the file has the expected size and owner; one killed later leaves "incomplete map file left by an interrupted create; remove it and retry". BENCHMARKS "Benchmark" rates over 25,000 entries, single process, Linux x86_64, in whole passes per second (multiply by 25,000 for operations per second); the cross-process table is in operations per second. Reproduce with "perl -Mblib bench/vs.pl 25000". Integer key -> integer value (Shared::II): BerkeleyDB LMDB Shared::II INSERT 30 44 280 LOOKUP 38 38 353 INCREMENT 16 17 247 String key -> string value, short (inline <= 7B, Shared::SS): FastMmap BerkeleyDB LMDB SharedMem Shared::SS INSERT 17 30 43 64 189 LOOKUP 15 35 36 154 220 DELETE -- 15 19 34 101 String key -> string value, long (~50-100B, Shared::SS), measured separately on a slower machine, so compare it only within itself: BerkeleyDB LMDB SharedMem Shared::SS INSERT 17 28 46 111 LOOKUP 23 25 92 139 LRU cache lookup (25K entries, lock-free clock eviction): plain LRU II 342 327 (lock-free; within run-to-run noise of plain) SS 165 164 Cross-process (25K SS entries, 2 processes, ops/s): Shared::SS SharedMem LMDB READS 3,798,000 3,085,000 854,000 WRITES 2,424,000 984,000 130,000 MIXED 50/50 5,738,000 2,470,000 275,000 LMDB benchmarked with MDB_WRITEMAP|MDB_NOSYNC|MDB_NOMETASYNC|MDB_NORDAHEAD. BerkeleyDB with DB_PRIVATE|128MB cache. SEE ALSO Data::HashMap::Shared::Cookbook - recipes for counters, caches, rate limits, liveness, dedup and atomic state Data::Buffer::Shared - typed shared array Data::Queue::Shared - FIFO queue Data::PubSub::Shared - publish-subscribe ring Data::ReqRep::Shared - request-reply Data::Sync::Shared - synchronization primitives Data::Pool::Shared - fixed-size object pool Data::Stack::Shared - LIFO stack Data::Deque::Shared - double-ended queue Data::Log::Shared - append-only log (WAL) Data::Heap::Shared - priority queue Data::Graph::Shared - directed weighted graph Data::BitSet::Shared - shared bitset (lock-free per-bit ops) Data::RingBuffer::Shared - fixed-size overwriting ring buffer SECURITY Files are created with mode 0600, "O_EXCL" and "O_NOFOLLOW", and their header is validated on attach. A constructor attaches to any valid map already at the path, whoever made it, so keep maps in a directory only the processes sharing them can write to -- not /tmp. Every process with write access to a map, and every map file you open, is trusted: corruption is outside the threat model, and only string bounds are checked against it. Keys are hashed with unseeded XXH3, so whoever chooses the keys can pile them into one probe run and slow every operation on it (4000 such keys made them ten to thirty times slower). Hash keys from an untrusted party with a keyed hash (an HMAC under a secret, kept as a string key) first. Under taint mode "new" and "new_sharded" with a path, "new_from_fd" and "unlink" refuse tainted arguments, and a handle opened from tainted input is itself tainted. Files from before 0.16 are refused; recreate them. AUTHOR vividsnow LICENSE This is free software; you can redistribute it and/or modify it under the same terms as Perl itself. It bundles xxHash by Yann Collet, used under the BSD 2-Clause licence; see LICENSE.xxhash in the distribution.