lsm派系(不仅lsm tree)存储模型概述(上篇)

jaydenwen123

修改于 2021-07-20 13:20:56

1.8K0

修改于 2021-07-20 13:20:56

导语：本篇是该系列上篇。网上介绍lsm tree相关的文章很多。那为什么还要写这篇文章呢？原因主要有以下两点： 1.首先，大部分的文章仅仅是介绍lsm tree是什么？包括哪些模块(MemTable、SSTable、WAL log等)？但极少有文章介绍为什么包含这些模块？ 2.其次，在介绍lsm tree的文章中，绝大部分文章都是侧重于告诉读者lsm tree的原理。其实从个人观点来看，lsm是一种思想，一种解决特定工程问题的通用思想。那除了lsm tree这种经典存储模型外，lsm派系还有其他存储模型吗？这一类存储模型之间又有哪些相同点、差异点？通过个人一段时间的探索和学习，决定以lsm tree作为切入点，先介绍lsm tree原理(因为只要深刻理解了lsm tree，然后再来看其他类lsm的存储模型，很容易掌握),然后在介绍其他lsm派系的存储模型思想。最终尝试写下此文，来回答上述问题。本系列总共包含三部分内容，分上下篇来介绍： 上篇： 1.用最直观的方式理解lsm tree 2.学术界提出的lsm tree 下篇： 3.lsm派系存储引擎 4.总结第一部分主要通过个人理解来阐述lsm tree原理，在介绍lsm tree是什么的同时，重点回答为什么会有各个模块，阅读完第一部分猜想大部分人都能顺利的理解lsm tree的精髓了。这一部分主要回答第一个问题(为什么包含这些模块？)。第二部分中，会简单介绍一下学术界对lsm tree的描述，同时介绍一些lsm tree相关论文和综述。这一部分的内容主要有两个作用：一方面是对第一部分内容的补充(毕竟第一部分的内容主要是从个人观点来介绍(有点事后诸葛亮的感觉)，目的是帮助大家串起来各个模块，细抠细节的话可能有些逻辑不太严谨)；另一方面主要是作为扩展材料，对lsm tree感兴趣的读者可以进行扩展阅读和学习。第三部分重点介绍几种lsm派系的存储引擎的设计思想，并比较它们之间的差异点，希望能对读者起到扩展视野的目的。这一部分主要回答第二个问题(lsm派系除了lsm tree还有哪些存储模型？他们的相同点、差异点？)

虽然分为上下篇介绍，但两篇文章的内容之间比较独立，完全可以单独阅读。 下篇链接如下： lsm派系(不仅lsm tree)存储模型概述(下篇)

1. 用最直观的方式理解lsm tree

这一部分主要介绍三块内容。首先回答一个问题：为什么会有lsm tree。回答完这个问题后，接下来会重点介绍lsm tree的原理及它所包含的各个模块之间的关系。最后会介绍下lsm tree在工程上的一些应用。从工程角度来论证我们回答的第一个问题。

此处先奉上lsm tree原理分析的视频教程 lsm tree原理分析视频教程

1.1 为什么会有lsm tree

在早期我们使用的大部分系统主要处理的是读多写少的场景，几乎所有的数据主要存储在mysql、oracle等关系型数据库中。随着互联网的快速发展，尤其是云计算、大数据这些领域近些年的兴起，又带来了新的问题。除了需要面对原先的读多写少的场景，我们还要面对一些写多读少的场景。我们下面举两个经典的例子。 1. 日志系统：目前的大部分互联网公司提供的软件服务，线上每天都有大量的前台和后台应用程序在不间断的提供服务。这些服务每天会产生大量的日志，这些信息需要存储下来，以便做服务监控、数据分析、排查定位问题、链路追踪等。这些数据的写入量会远远大于读取量。 2. 推荐系统：近些年推荐系统的兴起，导致现在每个app基本上内部都会一项推荐栏目。每天线上的推荐服务中，每时每刻都会记录用户的行为信息，这些信息都需要实时的存储，用来训练线上运行的推荐模型。另一方面用户和内容的一些动态特征信息每天也会频繁写入更新。方便对用户提供更优质的推荐效果。上述推荐场景中涉及的数据写入量也远大于读取量。

类似的例子还有很多，此处我们就不再展开过多讨论了。介绍完这个背景后，我们再来总结下。

上述的这些场景中，不但数据的写入量远大于读取量，而且存储的数据量更大。解决读多写少的关系型数据库不太适合解决上述问题。所以需要一种新的方案来解决该类问题，最经典的一类解决方案也就是我们今天的主角--lsm tree。下面我们用一句话来总结性的回答这个问题。

lsm tree是为了解决写多读少的场景而采用的一种解决方案，通常lsm tree被用来构建写多读少的存储引擎。

下面我们来重点看看lsm tree存储引擎是具体怎么解决写多读少这个问题的。

1.2 一步一步看清lsm tree

我们来想一下，用lsm tree构建的存储引擎主要适用于写多读少场景，既然这样自然就得搞明白数据存哪里、数据怎么存这两个大的问题。换言之，我们回答清楚下面三个问题即可：

lsm tree 管理的数据选择何种存储介质存储？
lsm tree 怎么写数据？
lsm tree 怎么读数据？

1.2.1 数据选择何种存储介质？

在介绍选择何种存储介质前，首先得知道有哪些介质可以存储数据。整体上存储数据的介质可以分为两大类：易失性存储、非易失性存储。易失性存储典型代表就是内存，当机器断电后数据就会丢失，但数据访问速度较快；非易失性存储典型的代表就是磁盘，它的特点是断电不丢数据，但数据访问相对慢一些。关于二者更详细的对比如下表所示。

通过上表几个维度，我们可以得知，对于存储海量数据、保证数据可靠性的系统而言，成本是考虑的一方面，另外容量也是考虑另一方面。自然就选择硬盘存储数据了。而硬盘尤其是机械硬盘，由于它本身的结构受限。不同访问方式访问速度也差异很大(顺序访问>>随机访问)。关于机械硬盘的更多介绍此处就不展开了，感兴趣的可以参考之前写过的这篇文章1.4节内容详细了解。

至此我们先明确了我们的第一个问题的答案：选择硬盘存储数据。

接下来我们看，一次普通的用户请求流程大体如下图所示，同时在这个过程中，我们得保证尽可能高效的处理写多读少场景下的数据读写操作。

1.2.2 数据如何写(大量写)？

在通常的过程中涉及数据写的操作有：增加、修改、删除这三种，为了尽可能顺序写磁盘，我们先按照最简单的方式来处理，我们想要是能将上述这些写操作全部追加到一个文件中，类似于写日志的方式记录下来，那么不同的操作需要通过操作类型来区分(op_type:add[添加]、update[更新]、del[删除])，假设用户写入进来的数据已经全部组织成(k,v,op_type)对的形式，每来一条数据就写一次磁盘，采用追加的方式进行。基本的过程如下图所示。

在上图的例子中，我们执行的操作依次是(k1,v1,add)->(k2,v2,add)->(k1,v1',update)->(k1,v1'',update)->(k1,,del)。在这个例子中，我们可以看出最后我们剩余的数据只有(k2,v2)这条了。其中k1最后删除了，但是和k1相关的四条记录依然占据着磁盘空间。这对于磁盘而言，很多无效的数据占据了空间，显然空间利用率不高。我们将该情景称为空间放大(一条(有效or无效)记录占据了多份磁盘空间)。这种情况如果不解决，时间长了明显会影响我们的系统，必须要进行优化处理。

Q1:怎么解决无效数据占据空间的问题？

A1:自然能想到的一种做法是：每隔一段时间将该数据文件进行清理一次，对数据做一次整理，清理掉无用的数据，该过程我们称为压缩或者合并吧

接下来我们就朝着压缩这条路开始进行，因为只要通过压缩解决了无效数据造成的空间放大问题，我们前面介绍的这种方案就是可行的。但是怎么压缩呢？

Q2:如何进行对数据压缩？

A2:将磁盘中的数据从头开始读取，然后在内存中借助于hashmap类型的数据结构进行做判断更新or删除，当经过一遍整理后，再将内存中剩余的数据写入到磁盘中即可。

这样做可行，但是呢又引入了新的问题，在这样压缩的过程中，一方面会阻塞住我们新的写入和读取操作；另一方面每次的压缩，都需要读取整个文件内容遍历，最后再将数据写入到磁盘。这个过程中时间复杂度为O(n)。当数据量较大时，压缩会比较耗时。

造成上面第一个问题的根本原因在于我们最初设定的存储数据的文件只有一个，如果我们能将数据分段存储，这样的话每次当一个文件写入的数据达到一定条件后就关闭，不再修改，然后重新打开一个新文件进行写入数据不就好了。然后合并的时候对前面关闭的一些文件进行定期压缩。这样我们的第一个问题就得到解决了。压缩过程不会阻塞读写过程。具体过程如下图所示

核心改进点：将原先单个文件存储转为采用多个小文件分段存储数据

Q3:如何对文件进行分段?

A3:文件分段规则最简单的一种方式是：可以设定每个文件有一个大小阈值，当当前文件达到或超过阈值后就关闭，重新打开一个新文件即可

这么改进后，之前提到的压缩过程还是不变，只不过压缩对象是之前关闭后的多个小文件。具体的压缩逻辑大致如下： 1. 依次按照文件关闭先后顺序倒序读取多个文件内容到内存 2. 内存中保留最新的数据(越后写入的数据越新)即可 3. 最后合并的数据写入到新文件中

这个压缩过程依旧存在上面单个文件压缩时提到的第二个问题：压缩比较慢。

Q4:那我们来看针对压缩很慢的这个问题，是否有一些思路可以进行优化呢？

A4:上述的压缩过程，其实也可以称为合并，本意就是对多个文件内容进行按照一定规则合并。这个过程和算法里面听过的多路归并排序有点类似耶。是否可以从这儿找到一个头绪呢？细想一下，二者之间主要差别在于多路归并的过程中，要求归并的每一项都是有序的，而目前我们遇到的数据都是无序的。如果我们能让归并的每个文件内容都有序，就可以借鉴归并的思想了，这样的话，压缩过程效率就能大大提高

Q5:如何保证我们的每个文件中的数据有序呢？

A5:方法1：数据写入文件的时候就已排好序，数据有序的存储在文件中；方法2：数据无序存储在文件中，在压缩前对每个文件的数据再进行排序

那到底采用哪种方法呢？答案是采用方法1：数据写入文件的时候就已排好序。因为写入文件数据有序一方面能支持对外范围查找；另一方面数据有序能提升读取的效率，这点后面再介绍如何读时介绍。

Q6:但目前我们的数据是来一条写一条，这种方式就没法保证写入有序，怎么办呢？

A6:写入文件时数据已经排好序，那就在内存中找一种支持排序的数据结构进行组织，然后缓存一段时间再写磁盘呗。

这样是可行，但是同时又引出来了下面两个子问题。 1. 内存中选择何种数据结构呢？ 2. 数据在内存中缓存一段时间，如果缓存期间还未来得及刷盘，就断电了数据就丢了，这种情况怎么处理？

只要上面两个问题解决了，那自然我们就可以采用这种方式了，接下来我们就一一看看如何解决上述问题。

Q7:内存中选择何种数据结构呢？

A7:此处选择的数据结构一定是可以支持排序的数据结构。可选的类型还是挺多的，详细参见下表

兼顾排序及时间复杂度，我们可选的数据结构有：avl树、红黑树、b树、b+树、跳表等。 关于这些数据结构的区别可以参考之前的一篇介绍

Q8:数据在内存中缓存一段时间，如果缓存期间还未来得及刷盘，就程序异常挂掉后数据就丢了，这种情况怎么处理？

A8:针对这个问题，可以选择在数据缓存到内存之前，先记录到日志中。当程序异常挂掉后重新启动时，就可以根据日志文件中记录来恢复数据。保证数据的可靠性。通常此类日志也被称为WAL(write ahead log)日志

综上，上面的两个子问题我们也就得到解决了。到这儿我们的数据模型发生了一些变化，既引入了内存模型、又引入了WAL日志，还将原先数据文件中存储的无序数据转变为有序数据。下面我们对这几个模块进行简单介绍：

1. 内存数据(MemTable): 内存数据主要缓存我们写入进来的数据，因为是内存数据所以称为MemTable。一般选择跳表或者红黑树等有序数据结构实现。 2. 磁盘数据文件(SSTable):磁盘数据文件，保存我们所有的用户数据，数据有序存储，所以又称为SSTable(Sorted String Table) 。 3. 磁盘日志文件(WAL log):预写日志文件，主要用来程序异常退出重启时恢复数据，保证数据可靠性，WAL全程write ahead log。

到此我们还有两个问题还需要解决。

Q9:数据以什么样的策略进行压缩？

A9:一种方式就是大小分级压缩；还有一种就是分层压缩。二者区别下面进行介绍；

大小分级压缩：较新的和较小的SSTable文件被连续合并到较旧的、较大的文件SSTable中。 分层压缩：分层压缩中，按照key的范围分裂成多个小文件SSTable，旧数据被移动到单独的层级。

Q10:何时进行数据压缩？

A10:压缩时机可以有很多，例如1.当文件个数达到一定数目时压缩；2.给每一层设定一个阈值，达到一定阈值后触发压缩等。

前面我们通过一些列的问题+答案的方式展开了介绍，可能不少读者看到此处后会有一些云里雾里的感觉，听着是这么回事，自己要再想一遍，感觉串不起来。下面将前面介绍的从小文件合并开始的一些列问题用一张图来描述。

最后的最后，我们将前面介绍的写过程再总结一下，一次写操作完整过程如下：

首先记录到WAL log文件中；
接着记录到MemTable中；
当MemTable达到一定阈值后关闭该MemTable,变成ImmuMemTable(只读，等待持久化到文件)；然后打开新的MemTable处理写操作，将ImmuMemTable写入到磁盘中，形成一个SSTable；

整体过程如下图所示。

1.2.3 数据如何读？

前面介绍完了写操作，我们知道了一个数据新旧的规律：

MemTable数据最新、ImmuMemTable数据次新、SSTable数据更旧(如果是分层压缩话，SSTable数据又可以按照层级来划分，层级越大，表明数据越旧)

而读取的过程，始终遵循一个核心原则：

数据是追加写入，所以按照倒序的方式读取，最先读取的数据最新，一旦读取到数据，则停止读取逻辑

既然如此，那我们一次读操作的过程如下图所示

整体过程如下： 1. 首先从MemTable中尝试读取，如果读取到数据，则停止读取过程，立即返回给用户。 2. 如果MemTable中数据未读到，则尝试从ImmuMemTable读取数据，如果读取到，则停止读取，返回给用户。 3. 如果ImmuMemTable中数据未读到，则尝试从SSTables中读取数据(此处省去繁琐的具体SSTable中读取数据的逻辑，因为涉及到数据是按照大小分级组织还是按照分层关系组织。还记得前面提到的关于数据排序时提到的两种策略吗？当初选择了写入文件时数据就已经有序。其主要是在这块读取SSTable时来加速读取的效率)，最后将读取的数据返回给用户。

接下来我们考虑这样一个极端情况，如果我们要搜索的数据根本就不存在。那这种情况下，我们需要读取完所有的数据才能返回给上层用户，搜索的数据不存在。

当数据量较大时，这种查找过程效率极低。往往在工程上实现时，会采用布隆过滤器来加速读取，查找每个SSTable时，首先会根据布隆过滤器来拦截一次，如果布隆过滤器检测当前查找的数据不存在，那么查找的数据就一定不存在当前的SSTable中，加快读取效率。不过布隆过滤器存在误判情况(判断存在的数据可能不存在)，所以在实际使用时，需要合理的设置布隆过滤器的几个关键参数。

其实在搞定了写的逻辑后，读取就是相对简单的一个过程了。无非就是写操作的逆过程，数据怎么写的就怎么来读而已。

1.2.4 总结

我们最后对这一部分通过一张图来进行以下总结，下面这张图中，SSTable采用的是分层压缩的方式组织。其中左右两侧分别展示了读写过程。相信到此，通过前面的介绍大家应该对lsm tree的整个原理有个大概的认识了，包括其中每个组件存在的价值、发挥的作用。另外也推荐一个关于这部分内容的视频教程分享给大家：lsm tree原理详解

1.3 lsm tree在工程上的应用

在前面介绍完lsm tree的思想后，我们来看一下，平常工作中接触到的哪些组件都用到了lsm tree呢？其实lsm tree在工程上应用相当广泛，除了大名鼎鼎的leveldb、rocksdb外，还有很多组件也是以lsm tree的思想进行实现。下面我们罗列一些大家比较熟悉的组件。

1. leveldb

leveldb是google开源的一款由c++编写的k-v存储引擎。它主要采用lsm tree来实现，并且底层SSTable在管理时是采用分层的方式进行组织，所以命名为leveldb。

2. rocksdb

rocksdb是facebook主力研发维护的一个k-v存储引擎，它是在早期的leveldb基础上进行扩展的。对leveldb做了大量细节的改进和优化。详细信息可以参考官方文档介绍。

3. go-leveldb

go-leveldb是用go语言实现的leveldb版本，目前归于golang组织下面。但目前的实现还不完善，无法在生产环境使用。

4. pebble

pebble是cockroachDB团队受leveldb/rocksdb启发采用go语言研发的一个k-v存储引擎。它继承了rocksdb的文件格式和一些特性。它主要的目标是为cockroachDB数据库提供数据存储服务。并不是替代rocksdb。

5. hbase

hbase是apache旗下的hadoop生态内的一个基于列式存储的分布式数据库。hbase内部数据按照一定策略进行分区，每个分区称为region，每个region通过lsm tree来组织管理数据。

6. Cassandra

Cassandra是apache旗下的继亚马逊Dynamo和谷歌BigTable之后开源的一款分布式数据存储系统，Cassandra采用去中心化架构实现，以此来避免单点故障问题。在Cassandra中每个数据分区采用lsm tree来组织数据。

7. Badger

Badger是一个用go语言开发的基于lsm tree的k-v存储引擎，它主要为分布式图数据Dgraph提供底层数据存储服务。官方说badger是一个可以替代非go编写的存储引擎(例如rocksdb等)的高性能替代选择。

除了上述列举的这些组件，内部采用lsm tree实现外，还有很多未被罗列出来的组件。此处不再对其一一进行介绍，感兴趣的读者可以自行搜索资料进行了解。

1.4 总结

在这一部分中，主要介绍了lsm tree的思想，回答了两个问题：1.为什么会有lsm tree？2.lsm tree内部各模块之间的相互关系？整个过程通过层层提问->回答的方式进行介绍。最终通过10问10答解释了在最初前言里提出的第一个问题。最后第三节简要介绍了一些基于lsm tree工程上实现的组件。主要的目的在于扩展视野。每个组件只是简单提了提点到为止。每一个组件的内容单独展开都可以用很长的篇幅来阐述。感兴趣的读者想更详细深入的研究可以自行查找资料学习。

2. 学术界提出的lsm tree

前面介绍的第一部分内容，以层层递进的方式介绍了lsm tree的原理。这部分内容完全是笔者根据自己的学习、思考、理解最终汇总而成。历史上的lsm tree到底怎么被推演发明的不得而知。但是可以找到其lsm tree最早提出来的论文。所以为了严谨起见，这一节我们花一小部分的内容来简单介绍一下lsm tree相关的几篇比较重要的论文和综述。我们不会过多展开来介绍这部分内容，感兴趣的读者可以直接阅读其论文内容来自行学习。

2.1 lsm tree 论文和综述

上面两篇是比较重要的论文，其中第一篇是 O'Neil, Elizabeth 等人在1996年提出了lsm tree，并撰写了一篇lsm tree论文。这篇论文内容比较丰富，作者首先详细介绍了为什么会设计出lsm tree的缘由，接着提出了5min rule，接着又介绍了lsm tree算法的大致结构，包括如何查找、如何删除、如何更新、并发、如何恢复等等内容。该论文不仅仅从理论部分介绍了lsm tree，而且还对lsm tree和b+ tree这两种磁盘模型进行了定性的计算分析并给出了结论，lsm tree和b+ tree相比到底有哪些优势，其中涉及的数学计算比较复杂，感兴趣的可以直接看原论文的介绍。最后作者还给出了和其他几种磁盘访问方式的对比分析。

第二篇论文，主要介绍的是关于lsm存储引擎相关的文献综述。这篇综述是Chen Luo · Michael J. Carey在2018年发表的，文中提到了这些年随着NoSql的大力发展，很多NoSql都基于lsm tree这种架构来设计实现，文中作者介绍了lsm tree发展的一个历史过程，并引出了今天主要适用的lsm tree架构。综述里不但提到了两种压缩方式：分层压缩、分级压缩；而且还介绍了一些针对lsm tree的改进例如采用布隆过滤器加速读、数据分区等。更重要的是，作者在该综述里提供了一些关于lsm tree的优化思路，大体的内容如下图所示，下图摘自于这篇翻译的文献