2021-11-05-基于LSM的KV存储写放大优化.md

基于LSM的KV存储写放大优化 - tiering

• 时间：2021.11.05
• 分享人：任勇闯
• 关键字：LSM, Leveling, Tiering, Partition
• 分享PPT：2021-11-05-基于LSM的KV存储写放大优化

分享内容

问题描述

基于 LSM 的 KV 引擎典型问题就是写放大，写放大的根本原因时 LSM 的 Compaction 过程导致数据反复提取到内存再写入磁盘，不仅浪费了资源，还减少了系统的吞吐量、降低 SSD 寿命。

内容

背景

1. LSM 基本合并策略分为 leveling 和 tiering 两种 [pdf](LSM-based storage techniques: a survey | SpringerLink)。
2. LSM partition 降低每次 Compaction 数据量，降低冷 sstable 参与 compaction 的频率
3. 问题：当前商业数据库基本采用 leveling 策略，而很少采用 tiering 的原因。
   1. tiering 降低读效率。但 tiering 将写放大降低一个数量级，且可以通过其他方法提高读效率，不应该成为完全抛弃的原因。
   2. tiering 难以分区。tiering sstable 不再以大小来分区，而是根据范围分区，范围的划分并没有公认合理的方法。

LSM-trie [pdf](LSM-trie: An LSM-tree-based Ultra-Large Key-Value Store for Small Data Items | USENIX)

1. 前缀树 + hash
2. 无索引
3. 负载均衡

PebblesDB [pdf](PebblesDB | Proceedings of the 26th Symposium on Operating Systems Principles (acm.org))

1. 借用跳表思想引入 guard
2. guard 的选择
3. guard 的变更

WipDB [pdf](WipDB: A Write-in-place Key-value Store that Mimics Bucket Sort | IEEE Conference Publication | IEEE Xplore)

1. 引用 buffer sort 思想
2. buffer 分区依据
3. buffer 变更

FAQ

无