LSM Tree，即日志结构合并树(Log-StructuredMerge-Tree)。LSM tree 之所以有效是基于以下事实：磁盘或内存的连续读写性能远高于随机读写性能，有时候这种差距可以达到三个数量级之高。这种现象不仅对传统的机械硬盘成立，对 SSD 硬盘也同样成立。如下图：
连续访问vs随机访问
LSM tree 是许多 key-value 型或日志型数据库所依赖的核心数据结构，例如 BigTable、HBase、Cassandra、LevelDB、SQLite、Scylla、RocksDB 等。
LSM tree 在工作过程中尽可能避免随机读写，充分发挥了磁盘连续读写的性能优势。
1、LSM树的核心思想
组成部分
如上图所示，LSM树有以下三个重要组成部分：
1) MemTable
MemTable是在内存中的数据结构，用于保存最近更新的数据，会按照Key有序地组织这些数据，LSM树对于具体如何组织有序地组织数据并没有明确的数据结构定义，例如Hbase使跳跃表来保证内存中key的有序。
因为数据暂时保存在内存中，内存并不是可靠存储，如果断电会丢失数据，因此通常会通过WAL(Write-ahead logging，预写式日志)的方式来保证数据的可靠性。
2) Immutable MemTable
当 MemTable达到一定大小后，会转化成Immutable MemTable。Immutable MemTable是将转MemTable变为SSTable的一种中间状态。写操作由新的MemTable处理，在转存过程中不阻塞数据更新操作。
3) SSTable(Sorted String Table)
有序键值对集合，是LSM树组在磁盘中的数据结构。为了加快SSTable的读取，可以通过建立key的索引以及布隆过滤器来加快key的查找。
sstable索引
lsm工作流程
2、写入数据
LSM tree 的所有写操作均为连续写，因此效率非常高。但由于外部数据是无序到来的，如果无脑连续写入到 segment，显然是不能保证顺序的。对此，LSM tree 会在内存中构造一个有序数据结构（就是 memtable）。每条新到达的数据都插入到该红黑树中，从而始终保持数据有序。当写入的数据量达到一定阈值时，将触发红黑树的 flush 操作，把所有排好序的数据一次性写入到硬盘中（该过程为连续写），生成一个新的 segment。而之后红黑树便从零开始下一轮积攒数据的过程。
写入数据
3、删除数据
如果是在内存中，删除某块数据通常是将它的引用指向 NULL，那么这块内存就会被回收。但现在的情况是，数据已经存储在硬盘中，要从一个 segment 文件中间抹除一段数据必须要覆写其之后的所有内容，这个成本非常高。LSM tree 所采用的做法是设计一个特殊的标志位，称为 tombstone（墓碑），删除一条数据就是把它的 value 置为墓碑，如下图所示：
删除数据
这个例子展示了删除 segment 2 中的 dog 之后的效果。注意，此时 segment 1 中仍然保留着 dog 的旧数据，如果我们查询 dog，那么应该返回空，而不是 52。因此，删除操作的本质是覆盖写，而不是清除一条数据，这一点初看起来不太符合常识。墓碑会在 compact 操作中被清理掉，于是置为墓碑的数据在新的 segment 中将不复存在。
4、读取/查询数据
如何从 SSTable 中查询一条特定的数据呢？一个最简单直接的办法是扫描所有的 segment，直到找到所查询的 key 为止。通常应该从最新的 segment 扫描，依次到最老的 segment，这是因为越是最近的数据越可能被用户查询，把最近的数据优先扫描能够提高平均查询速度。
当扫描某个特定的 segment 时，由于该 segment 内部的数据是有序的，因此可以使用二分查找的方式，在
的时间内得到查询结果。但对于二分查找来说，要么一次性把数据全部读入内存，要么在每次二分时都消耗一次磁盘 IO，当 segment 非常大时（这种情况在大数据场景下司空见惯），这两种情况的代价都非常高。一个简单的优化策略是，在内存中维护一个稀疏索引（sparse index），其结构如下图：
image.png
稀疏索引是指将有序数据切分成（固定大小的）块，仅对各个块开头的一条数据做索引。与之相对的是全量索引（dense index），即对全部数据编制索引，其中的任意一条数据发生增删均需要更新索引。两者相比，全量索引的查询效率更高，达到了理论极限值
，但写入和删除效率更低，因为每次数据增删时均需要因为更新索引而消耗一次 IO 操作。通常的关系型数据库，例如 MySQL 等，其内部采用 B tree 作为索引结构，这便是一种全量索引。
有了稀疏索引之后，可以先在索引表中使用二分查找快速定位某个 key 位于哪一小块数据中，然后仅从磁盘中读取这一块数据即可获得最终查询结果，此时加载的数据量仅仅是整个 segment 的一小部分，因此 IO 代价较小。以上图为例，假设我们要查询 dollar 所对应的 value。首先在稀疏索引表中进行二分查找，定位到 dollar 应该位于 dog 和 downgrade 之间，对应的 offset 为 17208~19504。之后去磁盘中读取该范围内的全部数据，然后再次进行二分查找即可找到结果，或确定结果不存在。
稀疏索引极大地提高了查询性能，然而有一种极端情况却会造成查询性能骤降：当要查询的结果在 SSTable 中不存在时，我们将不得不依次扫描完所有的 segment，这是最差的一种情况。有一种称为布隆过滤器（bloom filter）的数据结构天然适合解决该问题。布隆过滤器是一种空间效率极高的算法，能够快速地检测一条数据是否在数据集中存在。我们只需要在写入每条数据之前先在布隆过滤器中登记一下，在查询时即可断定某条数据是否缺失。
布隆过滤器的内部依赖于哈希算法，当检测某一条数据是否见过时，有一定概率出现假阳性（False Positive），但一定不会出现假阴性（False Negative）。也就是说，当布隆过滤器认为一条数据出现过，那么该条数据很可能出现过；但如果布隆过滤器认为一条数据没出现过，那么该条数据一定没出现过。这种特性刚好与此处的需求相契合，即检验某条数据是否缺失。
这里需要关注一个重点，LSM树(Log-Structured-Merge-Tree)正如它的名字一样，LSM树会将所有的数据插入、修改、删除等操作记录(注意是操作记录)保存在内存之中，当此类操作达到一定的数据量后，再批量地顺序写入到磁盘当中。这与B+树不同，B+树数据的更新会直接在原数据所在处修改对应的值，但是LSM数的数据更新是日志式的，当一条数据更新是直接append一条更新记录完成的。这样设计的目的就是为了顺序写，不断地将Immutable MemTable flush到持久化存储即可，而不用去修改之前的SSTable中的key，保证了顺序写。
因此当MemTable达到一定大小flush到持久化存储变成SSTable后，在不同的SSTable中，可能存在相同Key的记录，当然最新的那条记录才是准确的。这样设计的虽然大大提高了写性能，但同时也会带来一些问题：
1）冗余存储，对于某个key，实际上除了最新的那条记录外，其他的记录都是冗余无用的，但是仍然占用了存储空间。因此需要进行Compact操作(合并多个SSTable)来清除冗余的记录。
2）读取时需要从最新的倒着查询，直到找到某个key的记录。最坏情况需要查询完所有的SSTable，这里可以通过前面提到的索引/布隆过滤器来优化查找速度。
5、文件合并（Compaction）
随着数据的不断积累，SSTable 将会产生越来越多的 segment，导致查询时扫描文件的 IO 次数增多，效率降低，因此需要有一种机制来控制 segment 的数量。对此，LSM tree 会定期执行文件合并（compaction）操作，将多个 segment 合并成一个较大的 segment，随后将旧的 segment 清理掉。由于每个 segment 内部的数据都是有序的，合并过程类似于归并排序，效率很高，只需要
的时间复杂度。
compaction
在上图的示例中，segment 1 和 2 中都存在 key 为 dog 的数据，这时应该以最新的 segment 为准，因此合并后的值取 84 而不是 52，这实现了类似于字典/HashMap 中“覆盖写”的语义。
go-leveldb
go-leveldb是一个对leveldb的golang实现。
db, err := leveldb.OpenFile("path/to/db", nil)
// get
data, err := db.Get([]byte("key"), nil)
// 新增/修改
err = db.Put([]byte("key"), []byte("value"), nil)
// 删除
err = db.Delete([]byte("key"), nil)
// 批量操作
batch := new(leveldb.Batch)
batch.Put([]byte("foo"), []byte("value"))
batch.Put([]byte("bar"), []byte("another value"))
batch.Delete([]byte("baz"))
err = db.Write(batch, nil)
// 使用布隆过滤器
o := &opt.Options{
Filter: filter.NewBloomFilter(10),
}
db, err := leveldb.OpenFile("path/to/db", o)
defer db.Close()
参考：https://zhuanlan.zhihu.com/p/181498475、 https://www.qtmuniao.com/2022/04/16/ddia-reading-chapter3-part1/
网友评论