目录
1.什么是LSM树?
2.LSM树的落地实现
1.什么是LSM树?
LSM树(Log-Structured Merge Tree)是一种专门针对大量写操作做了优化的数据存储结构,尤其适用于现代大规模数据处理系统,如NoSQL数据库(如Cassandra、HBase、RocksDB等)和键值存储。尽管其名称中包含“树”,但它并不直接对应于传统的树状数据结构,而是指一种数据管理策略或体系架构。
LSM为什么会出现:
当数据量大了之后,读操作采用顺序遍历来进行查找肯能是不行的,性能太低了。所以需要维护一种数据结构用来帮助提升读的效率,在关系型数据库中用B+树(索引)来维护数据的关系,便于查找。
关系型数据库中对B+树的使用在读的时候性能不错,但是在写的时候存在明显的性能问题。不是说B+树这种数据结构在写的时候存在性能问题,而是关系型数据库中是将树结构存在磁盘上的,并且树的节点在磁盘上的存储是分散的,数据的存储也是分散的,这种落地方式在面对写操作的时候会有性能瓶颈。
原因如下:
首先是写操作。写操作是容易引起B+树的结构的调整的,要调整树的结构当然要去读写树的节点,树的整个结构都存在磁盘上的,所以要走磁盘IO,调整树当然就要去对磁盘上存的树的节点进行读写,B+树在磁盘中的存储是分散的,所以这里的IO是随机IO。写数据的时候,数据也不是顺序存放的,也是分散存放的,也会是随机IO。
其次是读操作,即使B+树尽力优化了树的层高,减少了磁盘IO次数,但是毕竟树的节点和数据不是顺序写入进行存储的,所以在访问的时候还是会进行随机IO,在关系型数据库的场景下倒是没什么问题,在大数据场景下要读的数据量是海量的,海量数据都是进行随机IO的读,性能上来说也是不佳的。
所以在海量数据的写入的时候B+树不是一个优质的选择。对着大数据场景的出现,LSM树出现,用于专门应对海量数据的写入。
总结一下B+树面对海量数据无力是因为:
-
树存在磁盘上,读写都是磁盘IO
-
树是分散存放的,读写都是随机IO
-
数据是分散存放的,读写都是随机IO
LSM树其实就是一套打法,核心目的就是为了规避上面的问题。
LSM树会将树结构放在内存中,从而规避磁盘IO,当然内存是有限的,到了一定条件后会将当前内存中这个版本的树存到磁盘中,存磁盘的时候开辟一块连续空间,将树的节点连续存储在一起,然后刷新内存再重新开始存新进来的内容。读的时候就会先去读内存,内存中没有再去读磁盘。由于磁盘中树的节点是连续写在一起的,会减少随机IO。
当在落磁盘的时候,磁盘上如果有历史版本的话,会和最新的历史版本进行合并。也就是说越新的历史版本,树越”茂盛“:
2.LSM树的落地实现
LSM树的落地实现通常包含内存中的MemTable(内存表)和磁盘上的SSTable(Sorted String Table,有序字符串表)两部分。
数据首先写入内存中的MemTable,数据在memtable中就会被组织成平衡二叉树:
当MemTable达到一定大小时,会被转换为不可变的SSTable并刷写到磁盘,写入磁盘的时候会开辟一段连续的存储空间,将树的内容连续存储在一起:
除了上面的内容外,还有一个核心内容——Compaction,合并。
由于肯定会落多次磁盘,生成多个版本的sstable,会浪费磁盘空间,所以还会存在合并操作,将多棵小树合成一棵大树。合并的时机一般有两个:
一个时机是在落磁盘生成新的sstable的时候会和之前最新的历史版本对应的sstable进行一次合并,两棵小树合并出一棵大树来。另一个时机是磁盘的存储达到一定阈值之后多个历史版本的sstable会进行合并合并出一棵大树来。
还有最后一个问题就是如何删除LSM树中的元素?
在memtable中删除了,但是sstable中还有,直接删除是没有用的,下次合并的时候还是会把已经删除的元素合并进来。所以LSM的做法是给要删除的元素打上一个墓碑标记,墓碑标记用来标记数据被删除了,下次合并的时候就能通过墓碑标记来判断哪些元素不用合并进来。