RURALPersistent map
How immutable AVL roots share nodes and values across snapshots without parent-chain reads.
Status: implemented in src/storage/persistent_map.zig, tested with Zig 0.16.0. This is the in-memory structural-sharing foundation for F01. Store-wide root publication, durable snapshots, branch catalogs, transaction isolation, retention policy and on-disk garbage collection remain separate work.
The map owns arbitrary byte-string keys and values. Keys use unsigned byte lexicographic ordering; empty keys, empty values and embedded zero bytes are valid. It does not interpret JSON, text normalization, schemas, document identifiers or graph relations.
API and ownership#
| Operation | Result and ownership |
|---|---|
Map.init(allocator) | Empty owning handle; no allocation. |
map.clone() | Another owning handle to the same immutable root; no allocation. |
map.get(key) | Optional borrowed value slice from this snapshot. |
map.put(key, value) | New owning map; input bytes are copied; source remains unchanged. |
map.remove(key) | New owning map; source remains unchanged. |
map.count() | Number of entries in this snapshot. |
map.iterator() | Owning iterator retaining the current root. |
iterator.next() | Next optional Map.Entry with borrowed key and value slices. |
map.deinit() / iterator.deinit() | Release that handle's ownership. |
Each successful put, remove or clone returns a separately owned map that must be released. A plain Zig assignment does not retain ownership. Transfer a handle only when the old variable will no longer be used as an owner; use clone() when both variables need independent lifetimes. The allocator and its backing state must outlive all maps and iterators using it.
A value returned by get stays valid while its source handle remains alive. Keep that handle rather than assuming another branch still contains the same allocation. An iterator retains its own snapshot, so its entries stay valid until the iterator is released, including across calls to next and after the original map has been released. An exhausted iterator still needs deinit.
deinit empties the handle. Calling it again on that same emptied variable is harmless; calling it on an unretained copy of an owning handle is invalid.
Putting the same bytes under an existing key and removing a missing key return allocation-free clones. Allocation failure returns error.OutOfMemory, releases temporary allocations and leaves the source snapshot unchanged. Excessively large combined key/value lengths are rejected with the same error before allocating.
Structure and costs#
Each root points directly into an immutable AVL tree. Nodes cache height and subtree entry count. An update creates nodes along the changed search path; rotations create new nodes and retain untouched subtrees. There is no parent-snapshot chain to search. A branch of a branch therefore has the same lookup structure as any other root.
Node references and key/value payload references have separate atomic counters. Path-copying an ancestor reuses its payload rather than copying its potentially large value. New payload bytes use one owned buffer containing the key followed by the value. Callers cannot change stored data by editing their input buffers afterward.
| Operation | Structural cost |
|---|---|
| Initialize, clone, count | Constant work; no data copy. Reference-count contention can still delay concurrent calls. |
| Lookup | O(log n) key comparisons. Byte comparison cost depends on key lengths. |
| Put/remove | O(log n) path work and node allocations; a changed put also copies the new key/value bytes. |
| Iterator creation | Retains one root and walks its leftmost path: O(log n), no allocation. |
| Complete iteration | O(n) traversal with a fixed bounded stack. |
| Release | Visits nodes whose last reference disappears; releasing the final complete tree can take O(n). |
The iterator's stack has twice the bit width of usize slots. An AVL tree with a node count representable in usize has a smaller height. Tree mutation and destruction recurse only through this balanced tree.
Snapshot depth does not add lookup work. Snapshot count and mutation volume still affect retained memory. This module has no admission quota, scheduler or background reclamation; higher layers must budget memory and the work involved in releasing large final snapshots. The allocator determines when freed memory is returned to the operating system.
Concurrency boundary#
Separately retained handles may be queried, cloned, updated into new maps and released concurrently when their shared allocator supports concurrent allocation/free. Node and payload fields remain immutable; only their atomic reference counts change. Releasing a last reference uses acquire/release ordering, and retaining a reference refuses counter overflow even in release builds.
A caller must hold a live source handle throughout get, clone, put, remove or iterator creation. Atomic node counts do not make racing deinit or assignment on that same handle safe. Sharing an immutable handle for concurrent reads is valid only when its lifetime is externally guaranteed. An iterator's mutable traversal state requires a single owner.
Publishing a new current root to other threads requires a separate synchronization protocol that protects acquisition of ownership. Loading a raw root pointer and incrementing its counter while another thread may free it is unsafe. This module does not provide that publication mechanism and does not substitute for the engine's transaction writer or retained-root catalog.
Verification#
Run the module directly with the pinned compiler:
zig test src/storage/persistent_map.zig
The inline tests cover:
Child and grandchild updates/deletes, empty and arbitrary byte keys, copied input ownership, and survival after source handles are released.
Ordered iteration retaining its own snapshot after maps are released.
Allocation-free forks/no-op mutations, shared subtree and payload identities, bounded path allocation, and complete release accounting.
AVL ordering/height/count invariants through 1,024 ascending inserts and alternating deletions while an older snapshot remains readable.
2,400 deterministic randomized operations across 12 independently evolving snapshots, compared with a separate reference model.
Every allocation-failure position in a mixed mutation workload, plus unchanged source contents and live-byte accounting at failed insertion/deletion path copies.
Four threads repeatedly reading, iterating, cloning, updating and releasing independent retained handles after the spawning handle is released. This uses the thread-safe page allocator; the sequential and failure-injection tests use the leak-checking testing allocator.
These tests establish the bounded module behavior. They do not establish disk durability, safe engine root publication, performance against another database, or complete UNIVERSE integration.