Analysis of the Effects of Two-Level Caching and Sparse Indexes on Read Latency in LSM Data Stores
DOI:
https://doi.org/10.63356/stes.ing.2026.003Keywords:
LSM tree, key-value store, block cache, LRU cache, read latencyAbstract
Introduction: Log-Structured Merge-Tree (LSM) stores provide high write throughput, but multi-level searches and read amplification can increase read latency.
Aim: To experimentally evaluate the effects of two-level caching, an application LRU cache and a disk block cache, and Summary/Index sparsity on point GET performance in a custom LSM key-value system.
Material and Methods: A key-value system with two-level caching and configurable Summary/Index structures was implemented. We evaluated 10⁶ reads with Zipfian and uniform distributions over existing and non-existing keys, using 4, 8, and 16 KB blocks and Summary/Index sampling ratios from 1:4 to 1:64.
Results: Best overall performance was achieved with 4 KB blocks, a 1:16 Summary sampling ratio, and both L1 and L2 caches. Compared with no caching, L2 reduced mean latency from 1,048.2 to 214.7 µs (79.5%), while L1+L2 reduced it to 178.4 µs (83.0%). Under 10⁶ mixed requests, L1+L2 reduced mean GET latency from 220.30 to 182.36 µs (17.2%) and increased throughput from 4,539 to 5,484 GET/s (20.8%) versus L2 alone. L1 achieved a 37.5% hit rate and reduced L2 accesses by 16.5%.
Conclusion: Two-level caching substantially improves read performance, while block size and index sparsity balance latency, throughput, and memory use. The best configuration used 4 KB blocks, a 1:16 sampling ratio, and both L1 and L2 caches.