hesela.devPACTree
PACTree is a persistent range index that decouples a trie search layer from linked data nodes and updates routing asynchronously.
The data layer persists a structural modification before background work updates the search layer. A lookup can follow sibling links from an outdated routing result. Recovery still repairs unfinished structural modifications. [1]
The inspected StringKey uses C-string comparison, so an explicit-length setter does not make embedded NUL bytes distinguishable. This is a key-domain constraint, not evidence of a crash-recovery failure. [3]
Relations
- related
- B+ tree, Persistent memory, Crash consistency
Limitations
- In the later equal-core-budget study, background lag increased insert latency at 20 threads; asynchronous work does not remove its CPU cost. [2]
- PiBench's variable-length-key comparison excluded PACTree because generated keys can contain NUL bytes; omission is not a measured performance loss. [2]
Citations
- Kim et al. PACTree: A High Performance Persistent Range Index Using PAC Guidelines. SOSP 2021, sections 5.2-5.9. DOI: 10.1145/3477132.3483589.
- He et al. Evaluating Persistent Memory Range Indexes: Part Two. PVLDB 15(11), 2477-2490, 2022, sections 6.1-6.7 and footnote 10. DOI: 10.14778/3551793.3551808.
- PACTree artifact, revision f173a0f: StringKey constructors, set and comparisons in include/common.h.
Further reading
Sources & caveats
- Primary-source synthesis and a native replay of the exact pinned StringKey class fragment under -O0 and -O2 -DNDEBUG; not a full index, PMDK, hardware or recovery experiment.