..

LSM Tree

介绍

  • 写操作友好，同时兼顾查询效率

  • 多用于 key-value 型 or 日志型数据库

  • LSM Tree 性能高的原因：采用顺序读写，避免随机读写

    不管是 Disk 还是 Memory，顺序读写都能比随机读写有较大的性能提好（甚至是几个数量级）

结构

维护 SSTable 持久化到磁盘

  • 每个 SSTable 包含多个 Segment
  • 每个 Segment 中有序存储 key-value 对（按 key 排序）
  • 但是不同 Segment 之间不存在顺序关系
  • Segment 中的数据不可以修改 (immutable)

写入

为了避免随机写，同时保证每个 Segment 中的数据是有序的，LSM Tree 会在内存中维护一个有序结构 memtable（可以是红黑树），每次写入操作需要先写入 memtable 中，当内存中的数据达到某个阈值之后，会将 memtable 中的数据有序写入到 Segment 中（生成新的 Segment）。

查询

  • 为了提高查询效率，写入操作除了将数据写入到 memtable 中，还会在内存中维护 Bloom Filter & Sparse Index ：Bloom Filter 是为了避免无用的查询，Sparse Index 是为了减少查询的数据量与 IO 次数
  • 依次扫描所有的 Segment：首先从最新的 Segment 中查询，如果当前 Segment 中不存在，则查询下一个
  • 在某个特定的 Segment 中查询 key 时，首先利用维护的 Bloom Filter 判断该 key 是否存在当前 Segment 中，如果存在，则再利用 Sparse Index 找到 key 在 Segment 中所处的数据块，之后再将这段数据块加入到内存中进行二分查找

压缩

每次查询时需要依次遍历所有的 Segment，如果 Segment 的数量很多的话，就会降低查询效率。因此，需要定期对所有的 Segment 进行合并，减小 Segment 的数量。

合并是一个归并排序的过程，在合并过程中，对于相同的 key，只需要保存最新的即可。

删除

Segment 中的数据不能被修改，为了实现删除，需要写入一条 value = {墓碑标志} 的数据。

如果在查询时遇到该标志，则返回 null；同时，墓碑标志会在压缩过程中回收掉。

删除的本质是覆盖写，而不是清除数据

LSM tree VS B-tree

主流的关系型数据库均以 B/B+ tree 作为其构建索引的数据结构，这是因为 B tree 提供了理论上最高的查询效率 - O(log⁡n)。但对查询性能的追求也造成了 B tree 的相应缺点，即每次插入或删除一条数据时，均需要更新索引，从而造成一次磁盘 IO。这种特性决定了 B tree 只适用于频繁读、较少写的场景。如果在频繁写的场景下，将造成大量的磁盘 IO，从而导致性能骤降。这种应用场景在传统的关系型数据库中比较常见。

而 LSM tree 则避免了频繁写场景下的磁盘 IO 开销，尽管其查询效率无法达到理想的 O(log⁡n)，但依然非常快，可以接受。所以从本质上来说，LSM tree 相当于牺牲了一部分查询性能，换取了可观的写入性能。这对于 key-value 型或日志型数据库是非常重要的。