LSM (log-structured merge-tree or LSMT)

结构：

  1. memTable(memory table), 内存中维护一个有序平衡树AVL(eg: 红黑树)
  2. ssTable(sorted string table), 内存中数据量足够大时， 生成ssTable结构写入磁盘
  3. ssTable 自带布隆过滤器
  4. ssTable 自带offset索引
  5. 多个ssTable 在后台合并生成更大的ssTable， 合并时key相同的数据取最新的，老的直接丢弃
  6. 可以当sstable数据太多时合并， 也可以分层(每一层 ssTable 满后，合并到底下的一层)

写入：

  1. 直接写入内存的 memtable 即可

更新：

  1. 直接写入内存的 memtable， 不需要像MySQL一样找到数据node并更新数据

查询：

  1. 首先查找memtable
  2. 再按时间反着的顺序依次查找ssTable, 找到的就是最新的数据
  3. 查询时先用 bloom 判定当前 ssTable 中是否存在， 存在再执行查找
  4. 用offset索引， load 一部分 ssTable 数据到内存中进行查找

使用LSM的产品

  1. levelDB (google-单机单文件数据, c++)
  2. rocksDB (facebook-持久化的k-v数据库, fork from levelDB, c++)
  3. kvRocks (apache-分布式k-v数据库，兼容redis协议，基于rocksDB, c++)
  4. sqlite4 （sqlite3 目前还是btree结构，lsm作为可选模块. 只是在sqlite4 中做了尝试, 并没有发布. c）

    sqlite 是在边缘设备(手机、嵌入式)中大量使用， 内存和运行环境并不稳定， LSM 需要内存缓存并且还要后台merge， 和 sqlite的场景并不是很匹配。

视频： https://www.youtube.com/watch?v=I6jB0nM9SKU

来自：https://www.zhihu.com/question/19887265

问题的本质还是磁盘随机操作慢，顺序读写快的老问题。这二种操作存在巨大的差距，无论是磁盘还是SSD。

顺序读写磁盘（不管是SATA还是SSD）快于随机读写主存，而且快至少三个数量级。这说明我们要避免随机读写，最好设计成顺序读写。

从日志文件中读一些数据将会比写操作需要更多的时间，需要倒序扫描，直接找到所需的内容。

所有的方法都可以有效的提高了读操作的性能（最少提供了O(log(n)) )，但是，却丢失了日志文件超好的写性能

当我们需要更新hash或者B+树的结构时，需要同时更新文件系统中特定的部分，这就是上面说的比较慢的随机读写操作。这种随机的操作要尽量减少

文件是不可修改的，他们永远不会被更新，新的更新操作只会写到新的文件中

当一些更新操作到达时，他们会被写到内存缓存（也就是memtable）中，memtable使用树结构来保持key的有序，在大部分的实现中，memtable会通过写WAL的方式备份到磁盘，用来恢复数据，防止数据丢失。

系统会周期的执行合并操作（compaction)。 合并操作选择一些文件，并把他们合并到一起，移除重复的更新或者删除纪录，同时也会删除上述的冗余。更重要的是，通过减少文件个数的增长，保证读操作的性 能。因为ssTable文件都是有序结构的，所以合并操作也是非常高效的

因为每个ssTable都是有序的，所以查找比较高效(O(logN))，但是读操作会变的越来越慢随着ssTable的个数增加，因为每一个 ssTable都要被检查。（O(K log N), K为ssTable个数， N 为ssTable平均大小）。

LevelDB 和 BigTable 是将 block-index 保存在文件尾部，这样查找就只要一次IO操作，如果block-index在内存中。

通过周期的合并文件，来保持文件的个数，因些读操作的性能在可接收的范围内

大部分的实现通过布隆过滤器来避免大量的读文件操作，布隆过滤器是一种高效的方法来判断一个ssTable中是否包 含一个特定的key

更新的实现，像 LevelDB 和 Cassandra解决这个问题的方法是：实现了一个分层的，而不是根据文件大小来执行合并操作。

每一层可以维护指定的文件个数，同时保证不让key重叠。也就是说把key分区到不同的文件。因此在一层查找一个key，只用查找一个文件

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

ssTable文件是不可修改的，这让对他们的锁操作非常简单。

目前，在实践上，RocksDB 是 LSM 的典型代表乃至事实标准，围绕 RocksDB 的各种系统与应用，已经形成了一个巨大的生态

RocksDB 其实是有很多缺陷的，可改进的空间非常大，ToplingDB 就是一个脱胎换骨的 RocksDB：

BTree是第一个比较成功的索引结构。它把数据组织成Page，非叶子节点存放类似指针的值，指向自己的子节点，叶子节点存Value。它比较成功的一点是充分利用磁盘I/O的带宽。

它最本质的问题是系统设计者被传统思路束缚住了手脚：更新数据必须要同时覆盖旧的数据，也就是同一份数据只能存一份。要更新一个值，首先必须要通过查询找到这个值的Page

相比B/B+ Tree，LSM Tree的设计理念完全不同：更新数据不需要覆盖旧的数据，有多份也不用担心，反正只取最新的值。这一看就能知道肯定写效率会提升：想象一下，你有个纷繁复杂的账本，每次update都直接写在最新的一页而不是翻回前面找到那条记录改掉，多香呀！

方式大家都大差不差，无非就是什么时候做Compaction，Compaction是leveled还是tiered，按行组织的数据什么时候转为列存（或者不转，一般用于AP数据库）等等。LSM最大的问题是后台Compaction线程会和写入线程共同争抢磁盘的I/O资源。

LSM tree (log-structured merge-tree) 是一种对频繁写操作非常友好的数据结构，同时兼顾了查询效率

LSM tree 之所以有效是基于以下事实：磁盘或内存的连续读写性能远高于随机读写性能，有时候这种差距可以达到三个数量级之高

LSM tree 持久化到硬盘上之后的结构称为 Sorted Strings Table (ssTable)。

顾名思义，ssTable 保存了排序后的数据（实际上是按照 key 排序的 key-value 对）

LSM tree 会在内存中构造一个有序数据结构（称为 memtable），例如红黑树

当写入的数据量达到一定阈值时，将触发红黑树的 flush 操作，把所有排好序的数据一次性写入到硬盘中（该过程为连续写），生成一个新的 segment。

一个最简单直接的办法是扫描所有的 segment，直到找到所查询的 key 为止。通常应该从最新的 segment 扫描，依次到最老的 segment，这是因为越是最近的数据越可能被用户查询，把最近的数据优先扫描能够提高平均查询速度。

当扫描某个特定的 segment 时，由于该 segment 内部的数据是有序的，因此可以使用二分查找的方式，在 O(log⁡n)的时间内得到查询结果。但对于二分查找来说，要么一次性把数据全部读入内存，要么在每次二分时都消耗一次磁盘 IO，当 segment 非常大时（这种情况在大数据场景下司空见惯），这两种情况的代价都非常高。

稀疏索引极大地提高了查询性能，然而有一种极端情况却会造成查询性能骤降：当要查询的结果在 ssTable 中不存在时，我们将不得不依次扫描完所有的 segment，这是最差的一种情况。有一种称为布隆过滤器（bloom filter）的数据结构天然适合解决该问题

由于每个 segment 内部的数据都是有序的，合并过程类似于归并排序，效率很高，只需要 O(n) 的时间复杂度。

主流的关系型数据库均以 B/B+ tree 作为其构建索引的数据结构，这是因为 B tree 提供了理论上最高的查询效率 - O(log⁡n)

对查询性能的追求也造成了 B tree 的相应缺点，即每次插入或删除一条数据时，均需要更新索引，从而造成一次磁盘 IO

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

进行查询时，首先检查布隆过滤器。如果布隆过滤器报告数据不存在，则直接返回不存在。否则，按照从新到老的顺序依次查询每个 segment。