用机器学习优化LSM树查询,降低延迟和内存占用。
Learned LSM-trees: Two Approaches Using Learned Bloom Filters
- 用分类器判断是否跳过无关层级的布隆过滤器检查。
- 查询延迟最高降低2.28倍,跳过30%过滤器检查。
- 替换布隆过滤器后内存减少70%-80%,零误判。
现代键值存储依赖日志结构合并(LSM)树实现写入优化,但带来显著读放大问题。辅助结构如布隆过滤器虽有帮助,但内存开销随树深度和数据集大小增长。近期学习型数据结构的发展表明,机器学习模型可增强或替代这些组件,以数据自适应行为取代手工规则。本文探索两种将学习预测融入LSM树查找路径的方法:第一种使用分类器选择性跳过无关层级的布隆过滤器探测,以降低平均查询延迟;第二种用紧凑的学习模型和小型备份过滤器替代传统布隆过滤器,目标是在不牺牲正确性的前提下减少内存占用。我们在基于Monkey风格的LSM树上实现两种方法,采用分层压缩、每层布隆过滤器及真实工作负载。实验显示,分类器通过高精度跳过30%布隆过滤器检查,使GET查询延迟最高降低2.28倍,尽管存在轻微漏报率;学习型布隆过滤器设计实现零误报,保持基线延迟的同时,每层内存使用量减少70%-80%。两者展示了延迟、内存与正确性间的互补权衡,凸显了学习型索引组件在写优化存储系统中的潜力。
原文摘要 · Abstract (English)
Modern key-value stores rely heavily on Log-Structured Merge (LSM) trees for write optimization, but this design introduces significant read amplification. Auxiliary structures like Bloom filters help, but impose memory costs that scale with tree depth and dataset size. Recent advances in learned data structures suggest that machine learning models can augment or replace these components, trading handcrafted heuristics for data-adaptive behavior. In this work, we explore two approaches for integrating learned predictions into the LSM-tree lookup path. The first uses a classifier to selectively bypass Bloom filter probes for irrelevant levels, aiming to reduce average-case query latency. The second replaces traditional Bloom filters with compact learned models and small backup filters, targeting memory footprint reduction without compromising correctness. We implement both methods atop a Monkey-style LSM-tree with leveled compaction, per-level Bloom filters, and realistic workloads. Our experiments show that the classifier reduces GET latency by up to 2.28x by skipping over 30% of Bloom filter checks with high precision, though it incurs a modest false-negative rate. The learned Bloom filter design achieves zero false negatives and retains baseline latency while cutting memory usage per level by 70-80%. Together, these designs illustrate complementary trade-offs between latency, memory, and correctness, and highlight the potential of learned index components in write-optimized storage systems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。