LSM 详解

2019-08-01 algorithm

简介

从 Google 发表了 BigTable 的论文之后，基于 LSM-Tree 的存储系统越来越常见，尤其是对于写多读少的时序数据库，通过 LSM-Tree 可以将离散的随机写转换成批量的顺序写请求 (WAL + Compaction)，以此来提高写性能。

读写放大

当然，天下没有免费的午餐，同时也带来了一些问题：

  • 读放大 (Read Amplification)，查询需要读取磁盘的次数。读取数据需要从新到旧一层一层查找，直到找到所需数据，会导致这一过程可能需要不止一次 IO 操作，尤其是范围查询。
  • 空间放大 (Space Amplification)，实际使用磁盘大小与存储数据大小比例。所有写入都是添加 (Append-Only) 的，而不是替换 (In-place Update)，这意味着相同数据可能存在多个版本，过期数据不会马上清理；在 Compaction 过程中，也需要临时存储空间。

为此，由于 LSM-Tree 的机制，需要定期通过后台的 Compaction 线程来减少读放大 (减少 SST 文件数量)和空间放大 (清理过期数据)，不过也因此带来了写放大 (Write Amplification) 问题。

  • 写放大，写入磁盘的数据量与写数据库的数据量比例，一般是以写入速率比较。其中涉及到了一直写入的 WAL 以及周期性的 Compaction 操作，所以，实际观察写入速率可能会出现周期性的波动。

磁盘主要分成了两类：A) Hard Disk Drive, HDD 传统的机械磁盘，包含了磁头、马达、磁盘等主要元器件，读写速度慢、容易损坏等；B) Solid State Drive, SSD 固态硬盘，包含了控制和存储单元，没有了机械结构也更可高，速度也更高。当然，也有两者的结合 Hybrid Hard Drive, HHD 混合硬盘，其实就是在性能和成本之间的平衡，随着 SSD 发展，慢慢会被取代。

写放大对于 SSD 来说，尤其严重，因为 SSD 不支持覆盖写，必须先擦除再写入，而擦除的次数是有限的。在 PebblesDB: Building Key-Value Stores using Fragmented Log-Structured Merge Trees 中有关于写入放大的评估。

原始的论文可以查看 The Log-Structured Merge-Tree (LSM-Tree) 中的详细介绍。

压缩

Compaction 是 LSM 树中很重要的步骤，决定了树的形状，期间会合并数据，例如将已经删除的数据删除、合并多次操作的数据等，在 RocksDB 中，同时还会根据 Key 做排序。

Level0 在内存中，其中的 Key 可能会重叠，而 Level1~LevelN 是保存在磁盘上的，已经排好序，而且不会重叠。

MiniLSM

MiniLSM 不错的基于 Rust 实现 LSM 教程，其中的一个实现可以参考 Solution 实现，相同作者实现。如下介绍一些常见的依赖库：

  • Moka 类似 Java Caffeine 的缓存库，支持并发、多种淘汰策略。

Memtable

通过 crossbeam 中的 skiplist 实现，其作为有序的 KV 内存存储，支持并发读写，其提供了类似 BTreeMap 的接口，区别是，即使是 put 操作也不需要 mut 对象，这样就意味着即使是修改，也只需要读锁就行。

另外，Memtable 的 delete 操作是通过将 Value 设置为空实现，而没有提供独立的删除接口。

冻结

超过某个指定的限制之后需要对其进行冻结，因为涉及到并发，可能存在两个请求进入临界区，此时就需要获取锁之后再检查一次是否超过限制。

因为冻结之后会有多个版本，那么读取时就需要获取到最新的数据。

Iterator

实现时尽量避免动态分派，也就是不使用 Box<dyn StorageIterator> 类型，更倾向于使用泛型进行静态分派，

MergeIterator

对多个底层数据进行合并，并将每个键的最新版本返回，例如有如下

参考