LSM-tree基本原理及应⽤
同学聚会感言
LSM-tree 在 NoSQL 系统⾥⾮常常见，基本已经成为必选⽅案了。今天介绍⼀下 LSM-tree 的主要思想，再举⼀个 LevelDB 的例⼦。
LSM-tree
LSM-tree起源于 1996 年的⼀篇论⽂《The Log-Structured Merge-Tree (LSM-Tree)》，今天的内容和图⽚主要来源于 FAST'16 的《WiscKey: Separating Keys from Values in SSD-conscious Storage》。
先看名字，log-structured，⽇志结构的，⽇志是软件系统打出来的，就跟⼈写⽇记⼀样，⼀页⼀页往下写，⽽且系统写⽇志不会写错，所以不需要更改，只需要在后边追加就好了。各种数据库的写前⽇志也是追加型的，因此⽇志结构的基本就指代追加。注意他还是个 “Merge-tree”，也就是“合并-树”，合并就是把多个合成⼀个。
好，不扯淡了，说正⽂了。
LSM-tree 是专门为 key-value 存储系统设计的，key-value 类型的存储系统最主要的就两个个功能，put（k，v）：写⼊⼀个
（k，v），get（k）：给定⼀个 k 查找 v。
璀璨造句LSM-tree 最⼤的特点就是写⼊速度快，主要利⽤了磁盘的顺序写，pk掉了需要随机写⼊的 B-tree。关于磁盘的顺序和随机写可以参考：《硬盘的各种概念》乐华彩电
下图是 LSM-tree 的组成部分，是⼀个多层结构，就更⼀个树⼀样，上⼩下⼤。⾸先是内存的 C0 层，保存了所有最近写⼊的 （k，v），这个内存结构是有序的，并且可以随时原地更新，同时⽀持随时查询。剩下的 C1 到 Ck 层都在磁盘上，每⼀层都是⼀个在 key 上有序的结构。
LSM-tree
写⼊流程：⼀个 put（k，v） 操作来了，⾸先追加到写前⽇志（Write Ahead Log，也就是真正写⼊之前记录的⽇志）中，接下来加到 C0
层。当 C0 层的数据达到⼀定⼤⼩，就把 C0 层 和 C1 层合并，类似归并排序，这个过程就是Compaction（合并）。合并出来的新的 new-C1会顺序写磁盘，替换掉原来的 old-C1。当 C1 层达到⼀定⼤⼩，会继续和下层合并。合并之后所有旧⽂件都可以删掉，留下新的。
注意数据的写⼊可能重复，新版本需要覆盖⽼版本。什么叫新版本，我先写（a=1），再写（a=233），233 就是新版本了。假如 a ⽼版本已经到 Ck 层了，这时候 C0 层来了个新版本，这个时候不会去管底下的⽂件有没有⽼版本，⽼版本的清理是在合并的时候做的。
写⼊过程基本只⽤到了内存结构，Compaction 可以后台异步完成，不阻塞写⼊。
查询流程：在写⼊流程中可以看到，最新的数据在 C0 层，最⽼的数据在 Ck 层，所以查询也是先查 C0 层，如果没有要查的 k，再查 C1，逐层查。
⼀次查询可能需要多次单点查询，稍微慢⼀些。所以 LSM-tree 主要针对的场景是写密集、少量查询的场景。
LSM-tree 被⽤在各种键值数据库中，如 LevelDB，RocksDB，还有分布式⾏式存储数据库 Cassandra 也⽤了 LSM-tree 的存储架构。LevelDB
敦煌的艺术
其实光看上边这个模型还有点问题，⽐如将 C0 跟 C1 合并之后，新的写⼊怎么办？另外，每次都要将 C0 跟 C1 合并，这个后台整理也很⿇烦啊。这⾥以 LevelDB 为例，看⼀下实际系统是怎么利⽤ LSM-tree 的思想的。
下边这个图是 LevelDB 的架构，⾸先，LSM-tree 被分成三种⽂件，第⼀种是内存中的两个 memtable，⼀个是正常的接收写⼊请求的memtable，⼀个是不可修改的immutable memtable。加拿大签证有效期
LevelDB
另外⼀部分是磁盘上的 SStable （Sorted String Table），有序字符串表，这个有序的字符串就是数据的 key。SStable ⼀共有七层（L0 到L6）。下⼀层的总⼤⼩限制是上⼀层的 10 倍。
青春赞歌写⼊流程：⾸先将写⼊操作加到写前⽇志中，接下来把数据写到 memtable中，当 memtable 满了，就将这个 memtable 切换为不可更改的immutable memtable，并新开⼀个 memtable 接收新的写⼊请求。⽽这个 immutable memtable 就可以刷磁盘了。这⾥刷磁盘是直接刷成L0 层的 SSTable ⽂件，并不直接跟 L0 层的⽂件合并。
每⼀层的所有⽂件总⼤⼩是有限制的，每下⼀层⼤⼗倍。⼀旦某⼀层的总⼤⼩超过阈值了，就选择⼀个⽂件和下⼀层的⽂件合并。就像玩 2048⼀样，每次能触发合并都会触发，这在 2048 ⾥是最爽的，但是在系统⾥是挺⿇烦的事，因为需要倒腾的数据多，但是也不是坏事，因为这样可以加速查询。
这⾥注意，所有下⼀层被影响到的⽂件都会参与 Compaction。合并之后，保证 L1 到 L6 层的每⼀层的数据都是在 key 上全局有序的。⽽ L0层是可以有重叠的。
Compaction
上图是个例⼦，⼀个 immutable memtable 刷到 L0 层后，触发 L0 和 L1 的合并，假如黄⾊的⽂件是
涉及本次合并的，合并后，L0 层的就被删掉了，L1 层的就更新了，L1 层还是全局有序的，三个⽂件的数据顺序是 abcdef。
虽然 L0 层的多个⽂件在同⼀层，但也是有先后关系的，后⾯的同个 key 的数据也会覆盖前⾯的。这⾥怎么区分呢？为每个key-value加个版本号。所以在 Compaction 时候应该只会留下最新的版本。
查询流程：先查memtable，再查 immutable memtable，然后查 L0 层的所有⽂件，最后⼀层⼀层往下查。
LSM-tree读写放⼤
读写放⼤（read and write amplification）是 LSM-tree 的主要问题，这么定义的：读写放⼤ = 磁盘上实际读写的数据量 / ⽤户需要的数据量。注意是和磁盘交互的数据量才算，这份数据在内存⾥计算了多少次是不关⼼的。⽐如⽤户本来要写 1KB 数据，结果你在内存⾥计算了1个⼩时，最后往磁盘写了 10KB 的数据，写放⼤就是 10，读也类似。
写放⼤：我们以 RocksDB 的 Level Style Compaction 机制为例，这种合并机制每次拿上⼀层的所有⽂件和下⼀层合并，下⼀层⼤⼩是上⼀层的 r 倍。这样单次合并的写放⼤就是 r 倍，这⾥是 r 倍还是 r+1 倍跟具体实现有关，我们举个例⼦。
假如现在有三层，⽂件⼤⼩分别是：9，90，900，r=10。⼜写了个 1，这时候就会不断合并，1+9=10，10+90=100，100+900=1000。总共写了 10+100+1000。按理来说写放⼤应该为 1110/1，但是各种论⽂⾥不是这么说的，论⽂⾥说的是等号右边的⽐上加号左边的和，也就是10/1 + 100/10 + 1000/100 = 30 = r * level。个⼈感觉写放⼤是⼀个过程，⽤⼀个数字衡量不太准确，⽽且这也只是最坏情况。
读放⼤：为了查询⼀个 1KB 的数据。最坏需要读 L0 层的 8 个⽂件，再读 L1 到 L6 的每⼀个⽂件，⼀共 14 个⽂件。⽽每⼀个⽂件内部需要读16KB 的索引，4KB的布隆过滤器，4KB的数据块（看不懂不重要，只要知道从⼀个SSTable⾥查⼀个key，需要读这么多东西就可以了）。⼀共24*14/1=336倍。key-value 越⼩读放⼤越⼤。
最长的电影简谱总结
什么的站立关于 LSM-tree 的内容和 LevelDB 的设计思想就介绍完了，主要包括写前⽇志 WAL，memtable，SStable 三个部分。逐层合并，逐层查找。LSM-tree 的主要劣势是读写放⼤，关于读写放⼤可以通过⼀些其他策略去降低。
