LSM 原理

发表于 更新于 分类于

原文出自深度开源论坛，链接

LSM(Log Structured-Merge Tree) 出自 2006 年谷歌发表的论文 big table. LSM 被用在许多产品的文件结构策略: HBase, Cassandra, LevelDB, SQLite, 在 mangodb3.0 中也附带一个可选的 LSM 引擎.

背景

LSM 的设计目的来提供比传统的 B+ 树 或者 ISAM 更好的写操作吞吐量，通过消去随机的本地更新操作来达到目标。
根本原因在于硬盘随机读写操作慢，顺序操作快的问题。两种操作方式存在巨大的差距，无论是机械硬盘还是 SSD.

LSM_random_sequence_op

上图显式顺序读写磁盘快于随机读写内存，而且至少快三个数量级。

所以应用对写操作敏感，为了避免性能瓶颈，简单的办法是将数据追加到末尾。该策略常用于日志或者堆文件，因为该文件内容是完全顺序的，所以可以提供很好的写操作性能。
因为简单和高效，基于日志的策略在大数据之间越来越流行，同时也有一些缺点，从日志文件中读特定数据将比写操作需要更多的查找时间，需要倒序扫描，直到找到所需的内容。
这样的特性说明日志仅仅适用于一些简单的场景

  • 数据是被整体访问，如大部分数据库的 WAL
  • 知道明确的 offset, 比如 kafka

所以为了提供良好的读性能(比如按 key 或者 range), 有以下四种方法

  • 二分查找: 将数据有序保存，使用二分查找来完成特定 key 的查找
  • 哈希: 用哈希将数据分割成不同的 bucket
  • B+ 树: 使用 B+ 树或者 ISAM 等方法，可以减少外部文件的读取
  • 外部文件: 将数据保存为日志，并创建一个 hash 或者查找树映射相应的文件

以上的方法都提供了良好的读性能(最低为(log(n))), 但是丢失了日志文件超好的写性能。上面这些方法都强加了总体的结构信息在数据上，数据被按照特定的方式放置，所以可以很快的找到特定的数据，但是却对写操作不友善。

LSM 发明就是为了解决上述问题，保持了日志文件写性能，以及微小的读性能损失。本质上就是让所有的操作顺序化。

很多树结构可以不用 update-in-place, 最流行的就是 append-only-tree, 也称为 copy-on-write tree. 他们通过顺序的在文件末尾重复写对结构来实现写操作，之前的树结构的相关部分，包括最顶层节点都会变成孤节点。尽管这种办法避免了本地更新，但是因为每个写结构都要重写树结构，放大了写操作，降低了写性能。

Base LSM Algorithm

基本的 LSM 是将之前使用一个大的查找结构(造成随机读写，影响写性能), 变换为将写操作顺序的保存到一些相似的有序文件(也就是 sstable[sort-string-table])中。所有每个文件包含短时间内的一些改动。因为文件是有序的，所以之后查找也会很快，文件是不可修改的，永远不会更新，新的更新操作只会写到新的文件中。读操作检查现有的文件，通过周期性的合并这些文件来减少文件个数。

LSM_file

当一些更新操作到达时，他们会被写到内存缓存(memtable)中，memtable 使用树结构来保持 key 的有序，在大部分的实现中，memtable 会通过写 WAL 的方式备份到磁盘，用来恢复数据，防止数据丢失。当 memtable 达到一定规模时会被刷新到磁盘上的一个新文件，重要的是系统只做了顺序磁盘读写，因为没有文件被编辑，新的内容或者修改只用简单的生成新的文件。

因为比较旧的文件不会被更新，重复的记录只会通过创建新的记录来覆盖，也就产生了一些冗余的数据。所以系统会周期性的执行合并操作。合并操作选择一些文件，并把他们合并到一起，移除重复的更新或者删除记录，同时也会删除上述的冗余。更重要的是，通过减少文件个数的增长，保证读操作的性能。因为 sstable 文件都是有序结构的，所以合并操作也是非常高效的。

读操作

当一个读操作请求时，系统首先检查内存数据，如果没有找到一个 key, 就会逆向检查 sstable 文件，直到 key 被找到。因为每个 sstable 都是有序的，所以查找比较高效(O(logN)), 但是读操作会变的越来越慢随着 sstable 的个数的增加，因为每一个 sstable 都要被检查。

为了提高读操作的性能，最基本的方法就是页缓存(leveldb 的 TableCache, 将 sstable 按照 LRU 缓存在内存中)，减少二分查找的小号。LevelDB 和 BigTable 是将 block-index 保存在文件尾部，这样查找就只要一次 I/O 操作，如果 block-index 在内存中。

即使有每个文件的索引，随着文件个数的增多，读操作仍然很慢。通过周期的合并文件，来保持文件的个数。即使有了合并操作，读操作仍然会访问大量文件，大部分的实现通过布隆过滤器来避免大量的读文件操作，布隆过滤器一种高效的方法来判断一个 sstable 中是够包含一个特定的 key.(如果 bloom 判定一个 key 不存在，就一定不存在，而当 bloom 判定一个 key 存在，则有不存在的可能，只是通过概率保证)。

LSM_write_op

写操作

所有的写操作都被分批处理，只写到顺序块上。另外，周期性的合并操作会对 I/O 有影响，读操作有可能会访问大量的文件(散乱的读). 这就简化了算法工作的方法，LSM 交换了读和写的随机 I/O. 通过软件实现的技巧像布隆过滤器或者硬件(大文件 cache) 来优化读性能。

合并操作

当一定数量的 sstable 文件被创建，例如有 5 个 sstable, 每一个有 10 行，他们被合并为一个 50 行的文件(或者更少的行数). 这个过程一直持续着，当更多的有 10 行的 sstable 文件被创建，当产生 5 个文件，他们就会合并到 50 行的文件。最终会有 5 个 50 行的文件，这是会将这 5 个 50 行的文件合并成一个 250 行的文件。这个过程不停地创建更大的文件。

LSM_combine_op

上述的方案有一个问题，大量的文件被创建，最坏的情况下，所有的文件都要搜索

分层合并

levelDB 和 Cassandra 解决这个问题的方法是: 实现一个分层的，而不是根据文件大小执行合并操作。这个方法可以减少在最坏情况下需要检索的文件个数，同时也减少了一次合并操作的影响。

按层合并的策略相对于上述的按文件大小合并的策略有两个关键的不同：

  • 每一层可以维护指定的文件个数，同时保证不让 key 重叠。也就是将 key 分区到不同的文件。因此在一层查找一个 key, 只用查找一个文件。第一层是特殊情况，不满足上述条件，key 可以分布在多个文件中
  • 每次，文件只会合并到上一层的一个文件。当一层的文件满足特定个数时，一个文件会被选出并合并到上一层。这明显不同与另一种合并方式，一些相近大小的文件被合并为一个大文件

这些改变表明按层合并的策略减小了合并操作的影响，同时减少了空间需求。

总结

所以，LSM 是日志和传统的单文件索引(B+ tree, Hash Index) 的中立，他提供了一个机制来管理更小的独立的索引文件(sstable).

通过管理一组索引文件而不是单一的索引文件，LSM 将 B+ 树等结构昂贵的随机 I/O 变的更快，而代价就是读操作要处理大量的索引文件(sstable)而不是一个，另外还是一些 I/O 被合并操作消耗。