【Flink】第十四篇：LSM-Tree一般性总结

往期看点：

【Flink】第五篇：checkpoint【1】

【Flink】第五篇：checkpoint【2】

【Flink】第六篇：记一次Flink状态（State Size）增大不收敛，最终引起OOM问题排查

【Flink】第八篇：Flink 内存管理

【Flink】第九篇：Flink SQL 性能优化实战

【Flink】第十篇：join 之 regular join

【Flink】第十二篇：记kudu-connector写CDC数据的-D数据时，报主键不存在的异常

【Flink】第十三篇：JVM思维导图

LevelDB的开源发起者：Jeff Dean和Sanjay Ghemawat，这两位是Google公司重量级的工程师。

Jeff Dean是Google大规模分布式平台Bigtable和MapReduce主要设计和实现者。

Sanjay Ghemawat是Google大规模分布式平台GFS，Bigtable和MapReduce主要设计和实现工程师。

如果了解Bigtable的话，应该知道在这个影响深远的分布式存储系统中有两个核心的部分：Master Server和Tablet Server。其中Master Server做一些管理数据的存储以及分布式调度工作，实际的分布式数据存储以及读写操作是由Tablet Server完成的，而LevelDB则可以理解为一个简化版的Tablet Server。

RocksDB是facebook开源的NOSQL存储系统，其设计是基于Google开源的LevelDB，优化了LevelDB中存在的一些问题，其性能要比LevelDB强，设计与LevelDB极其类似。

而HBase又是Bigtable的开源实现版。

总之，LevelDB、HBase、RocksDB都是LSM树存储引擎。

我们知道，大部分传统RDBMS是基于B+树的存储引擎。那LSM相对于B+的优点有哪些？

请先自行了解：二叉树，包括二叉树的各类衍生树，满二叉树、完全二叉树、堆、二叉查找树/排序树/搜索树(BST)、平衡二叉搜索树(AVL)、红黑树(RBT)

B+树本质上是一种多叉查找平衡树。

B树：

可以理解为平衡多叉查找树，每个结点有多个关键字，这些关键字有序，且子树是根据这些关键字分裂的。每个结点的子树数量是关键字数量 + 1。

同时，对每个结点的关键字数量做了一个最大最小的限制，所有的叶结点都在同一层上，并且不带信息。

B+树：

相对于B树，结点中不保存实际信息，只是一个稀疏的索引，叶子结点才是真正的储存信息的地方，并且叶子结点之间链接起来。这种改造更便于文件操作系统或者数据库索引，

(1) 顺序遍历效率高：叶子结点之间链接起来，顺序遍历效率很高。

(2) I/O少：结点很轻，直接加载至内存，减少磁盘I/O。

(3) 稳定：只有到叶子结点才会有有效的文件位置信息，所以，所有查询是一个从根到叶的过程，使得查询的消耗和效率很稳定，主要和树高度有关。

LSM树(Log Structured-Merge Tree)：

LSM树通过批量存储技术规避B+的磁盘随机写入问题。

LSM树结构的问题: 写入速度快，读取速度慢，写放大和读放大都较高。

LSM树的设计思想非常朴素, 它的原理是把一颗大树拆分成N棵小树， 它首先写入到内存中（内存没有寻道速度的问题，随机写的性能得到大幅提升），在内存中构建一颗有序小树，随着小树越来越大，内存的小树会flush到磁盘上。磁盘中的树定期可以做merge操作，合并成一棵大树，以优化读性能。

LSM vs B+

B+树最大的性能问题是会产生大量的随机IO，随着新数据的插入，叶子节点会慢慢分裂，逻辑上连续的叶子节点在物理上往往不连续，甚至分离的很远，但做范围查询时，会产生大量读随机IO。

对于大量的随机写也一样，举一个插入key跨度很大的例子，如7->1000->3->2000 … 新插入的数据存储在磁盘上相隔很远，会产生大量的随机写IO，低下的磁盘寻道速度严重影响性能。

本质上：

I/O亲大文件顺序读写，CPU亲多个小文件并行处理

按照我理解LSM，画出下图(可能存在HBase和RocksDB的影子)，

说明：

• 数据区：数据区主要是存储写入的命令，同时为了方便分段读取，是按照一定的数量大小分段的。
• 稀疏索引区：稀疏索引保存的是数据段每一段在文件中的位置索引，读取 SSTable 时候只会加载稀疏索引到内存，查询的时候根据稀疏索引加载对应数据段进行查询。
• 文件索引区：存储数据区域的位置。

writebuffer是一个写缓存，是内存级别的，所以速度肯定很快。而当writebuffer满了以后直接刷写到磁盘，因为它已经是内存维护的一个有序的数据结构了。当磁盘上的溢写SSTable越来越多，会进行合并，用归并进行文件合并就可以，速度同样快，并且这些过程都是异步的。当读时，由于存在读放大，需要读多个地方，但是SSTable的数据区是若干有序的数据段，所以，只需要将稀疏索引放入内存，进行磁盘的顺序IO即可。

所以，将其总结为，

I/O亲大文件顺序读写，CPU亲多个小文件并行处理