首先问各人一个小问题？区块链的账本数据存储名目主要是什么范例的？
相信智慧的你必然知道是Key-Value范例存储。
下一个问题，这些Key-Value数据在底层数据库如何高效组织？
谜底就是我们本期先容的内容：LSM[1]。
LSM是一种被遍及回收的耐久化Key-Value存储方案，如LevelDB, RocksDB, Cassandra等数据库均回收LSM作为其底层存储引擎。
据果真数据调研，LSM是当前市面上写麋集应用的最佳办理方案，也是区块链规模被应用最多的一种存储模式，本日我们将对LSM根基观念和机能举办先容和阐明。
LSM-Tree配景：追本溯源LSM-Tree的设计思想来自于一个计较机规模一个老生常谈的话题——对存储介质的顺序操纵效率远高于随机操纵。
如图1所示，对磁盘的顺序操纵甚至可以快过对内存的随机操纵，而对同一类磁盘，其顺序操纵的速度比随机操纵跨越三个数量级以上[2]，因此我们可以得出一个很是直观的结论：该当充实操作顺序读写而尽大概制止随机读写。
Figure 1 Random access vs. Sequential access
思量到这一点，假如我们想尽大概提高写操纵的吞吐量，那么最好的要领必然是不绝地将数据追加到文件末端，该要领可将写入吞吐量提高至磁盘的理论程度，然而也有显而易见的漏洞，即读效率极低（这也是许大都据库制止数据意外丢失的手段，因凡是不需要对其举办读取，称为Journaling或WAL），我们称这种数据更新长短原地的（Out-of-place），与之相对的是原地更新（In-place）。
为了提高读取效率，一种常用的要领是增加索引信息，如B+树, ISAM等，对这类数据布局举办数据（或索引）的更新是原地举办的，这将不行制止地引入随机IO。
LSM-Tree与传统多叉树的数据组织形式完全差异，可以认为LSM-Tree是完全以磁盘为中心（Disk-Centric）的一种数据布局，其只需要少量的内存来晋升效率，而可以尽大概地通过上文提到的Journaling方法来提高写入吞吐量。虽然，其读取效率会稍逊于B+树。
图2展示了LSM-Tree的理论模子(a)和一种实现方法(b)[3]。LSM-Tree是一种层级的数据布局，包括一层空间占用较小的内存布局以及多层磁盘布局，每一层磁盘布局的空间上限呈指数增长，如在LevelDB中该系数默认为10。
Figure 2 LSM与其LevelDB实现
对付LSM-Tree的数据插入或更新，首先会被缓存在内存中，这部门数据往往由一颗排序树举办组织。
当缓存到达预设上限，则会将内存中的数据以有序的方法写入磁盘（即L0层），我们称这样的有序列为一个Sorted Run，简称为Run。
跟着写入操纵的不绝举办，L0层会会萃越来越多的Run，且显然差异的Run之前大概存在重叠部门（如Run-1的数据范畴是a-c，Run-2的数据范畴是b-d），此时举办某一条数据的查询将无法精确判定该数据存在于哪个Run中，因此最坏环境下需要举办等同于L0层Run数量的I/O。
为了办理该问题，当某一层的Run数目或巨细达到某一阈值后，LSM-Tree会举办靠山的合并排序，并将排序功效输出至下一层，我们将一次合并排序称为Compaction。如同B+树的破裂一样，Compaction是LSM-Tree维持相对不变读写效率的焦点机制，我们将会在下文具体先容两种差异的Compaction计策。
别的值得一提的是，无论是从内存到磁盘的写入，照旧磁盘中不绝举办的Compaction，都是对磁盘的顺序I/O，这就是LSM拥有更高写入吞吐量的原因。
Leveling vs. Tiering：一读一写，不分伯仲
LSM-Tree的Compaction计策可以分为Leveling和Tiering两种，前者被LevelDB，RocksDB等回收，后者被Cassandra等回收，称回收Leveling计策的的LSM-Tree为Leveled LSM-Tree，回收Tiering的LSM-Tree为Tiered LSM-Tree，如图3所示[4]。
Figure 3 两种Compaction计策比拟
▲ Leveling简而言之，Tiering是写友好型的计策，而Leveling是读友好型的计策。在Leveling中，除了L0的每一层最多只能有一个Run（Run为一组有序且不重叠的序列，可以思量LevelDB中除了L0每一层中的SSTable都是有序且相互不重叠的，统称这些SSTable为一个Run），如图3右侧所示，当在L0插入13时，触发了L0层的Compaction，此时会对Run-L0与基层Run-L1举办一次合并排序，合并功效写入L1，此时又触发了L1的Compaction，此时会对Run-L1与基层Run-L2举办合并排序，合并功效写入L2。
▲ Tiering郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。
