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

2022-03-31 11:08:08 浏览数 (1)

往期看点:

【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亲多个小文件并行处理

0 人点赞