TreePass: Lightweight Tree-Guided Cache Management for B+-tree Key-Value Stores

With the rise of NVMe SSDs, the performance gap between random and sequential I/O has narrowed, renewing interest in B+-tree-based key-value stores (KVSs) for modern data systems. In larger-than-memory B+-tree KVSs, performance critically depends on cache eviction decisions. However, existing page-cache eviction policies treat each page independently using only its own access history. As a result, they fail to exploit subtree-level hotness arising from key-range locality or preserve accumulated history across out-of-place updates, causing pages in hot subtrees to be misclassified and prematurely evicted. We observe that B+-tree operations naturally expose lightweight, address-independent signals for subtree hotness and future page invalidation. Based on these insights, we propose TreePass, a lightweight caching system that augments CLOCK eviction with per-pivot counters embedded in the B+-tree. With these counters, TreePass performs early eviction of cold-subtree pages and differentiated reference-counter initialization for newly created pages, suppressing unnecessary writebacks without additional metadata. We implement TreePass in SplinterDB and evaluate it across YCSB and real-world workloads. Across all evaluated workloads, TreePass achieves up to 101% higher throughput, 70% fewer page writes, and 15% lower P99 tail latency than state-of-the-art caching policies.