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

jaydenwen123

修改于 2021-07-20 13:34:21

2.8K1

导语：本篇是该系列下篇。主要介绍几种lsm派系的存储引擎的设计思想。为了方便大家回顾主题，上篇的导言内容再贴一遍。网上介绍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)存储模型概述(上篇)

3. lsm派系存储引擎

这部分内容主要回答我们在文章开头提到的第二个问题。第二个问题展开其实是一连串的问题。例如：lsm派系难道只有lsm tree这一类存储模型吗？如果答案是否定的，那么除了lsm tree存储模型外，还有哪些lsm 模型？这些模型之间又有哪些相同点和差异点？

所以这一部分的内容我们主要围绕上述问题展开，我们首先会介绍lsm派系除了lsm tree还有哪些模型？接着又会介绍每种模型的主要原理，最后会对上述几种模型做一个总结和对比。

这里我们先统一说明，在讨论的lsm派系的存储引擎里，这些存储引擎都是选择采用磁盘来组织数据；同时这些存储引擎对外暴露的都是针对kv操作的接口:set(k,v),get(k),del(k)等；只不过在底层内部实现时，内存和磁盘上对数据的组织方式不同而已。

3.1 bitcask存储模型(lsm hash)

首先介绍第一种lsm hash的模型，该模型的典型代表就是bitcask。官方文档中介绍说该模型主要采用的是(LSM+WAL)方式的磁盘布局。该模型的实现思想非常简单。下面给大家做一个简单介绍，更详细的内容大家可以参考其论文进行阅读学习。

此处奉上bitcask相关两份教程： bitcask原理分析视频教程 bitcask源码分析视频教程

3.1.1 bitcask整体架构

下图为bitcask的整体架构，我们划分为用户接口、内存结构、磁盘结构三层结构来介绍。

在用户接口中，bitcask主要暴露给用户的是Get(k)、Put(key,value)、Delete(key)、Scan(prefix)等。

在磁盘上，bitcask是采用追加写的方式记录用户的数据，所有涉及数据更新的记录，bitcask都会将其组织成统一的格式，然后追加到磁盘中。磁盘上的数据分小文件多段存储(当每个文件达到一定阈值后，关闭写入重新打开一个新文件处理写请求；另外关闭的文件通过mmap来打开，用来后续加速读请求查找数据)，它在磁盘上组织的数据时无序的，类似于很多分布式系统里记录WAL redo log的方式。我们先来考虑一个问题，当bitcask磁盘上这么组织数据后，磁盘上本身的数据就是乱序存储的。在用户访问时，它是怎么支持对数据排序的呢？下面我们就来通过内存结构来揭开这个谜题。

在内存中，bitcask采用了一种叫做ART 树来存储索引，它是一种前缀树的变形，此处我们不对ART树展开做介绍，感兴趣的读者可以自行查找资料学习。这种树主要有以下三个特点： 1. ART树能够比普通的前缀树更好的对数据进行压缩，因此在保存相同数据的情况下，所占用的空间更少。 2. ART树这种数据结构，其本身操作(增删改查)的时间复杂度近似于hash表。 3. ART树本身能支持前缀查找(可以看做前缀排序)的特性。

因为bitcask的索引是存储在内存的(每次关闭一个数据文件时，会将索引也更新一份到磁盘文件)，所以它正是看中了ART 树的上述几个特点，所以才选择该种数据结构来存储索引。

3.1.2 bitcask数据存储

在本节，我们重点看一下bitcask模型中，磁盘数据按照什么样的方式组织，内存中的索引又保存哪些信息。

如上图所示，bitcask的数据在磁盘上按照如上的格式进行存储，每一对kv会被扁平化(TLV方式)处理，然后追加到磁盘文件。接下来在内存的索引中，它主要记录了当前的一对kv写在哪个磁盘文件(fileId)的哪个位置(offset)，占了多大空间(size)，具体格式如下图所示。

3.1.3 bitcask查询、合并

在bitcask中，已经写满关闭的文件是通过mmap的方式打开的。在后续查询时，首先会从内存中找到索引。如果判断到当前查询的kv是存储在已经关闭的文件中，则直接通过mmap来读取对应的内容再做解析。如果查找的数据位于当前写入的文件，它会直接定位到该文件对应的位置offset，然后读取大小为size的数据解析。简单的查找过程如下图中左半部分描述。

另外由于bitcask是采用WAL的方式记录数据，所以必然会有无效数据存储在磁盘中，造成空间放大。这种情况下bitcask也是按照定时合并数据的方式来解决该问题的。具体的合并逻辑是：遍历内存中的全量索引，然后再依次获取有效的数据，写入到一个新的bitcask实例中，最后再通过新bitcak实例生成的数据文件替换掉老的bitcask实例所管理的数据文件。具体的合并过程可以参考下图右半部分描述。

bitcask的写入过程比较简单，首先查找一次如果数据已经存在，则执行更新操作。否则进行添加操作(先记录日志，然后更新索引)。

3.1.4 相关资料

3.2 moss存储模型(lsm array)

moss所采用的存储模型是lsm array。之所以称为lsm array，自然是因为它的内部在实现中采用了数组来组织数据，那具体怎么采用数组组织数据的，下面我们来重点介绍。

此处奉上moss相关两份教程： moss原理分析视频教程 moss源码分析视频教程

3.2.1 moss整体架构

关于moss的设计方案，官方有一个很详细的文档，大家可以点击该文档进行详细阅读，下图是根据官方文档和源码分析时候，笔者整理的一个moss的整体架构。

我们将moss的整体架构还是分为三层来介绍，首先是用户接口层，这一层主要暴露给用户的是Get(key)、NewBatch()、Set(key,value)、Delete(key)、Snapshot()等，总结起来无非也就是针对kv的增删改查这几个核心接口，只不过在moss中所有的key、value都是[]byte类型。

在内存中moss采用的是数组来组织用户传递进来的数据，其中数据和索引均采用数组结构来组织。在这儿大家可以想象一下，如果是自己来设计，会用数组怎么来管理这些数据。

在moss中内存里将数据按照分级的思想来划分，它总共划分为四层：top、mid、base、clean。这四层所采用的数据结构均是称为segmentStack的对象。segmentStack对象从字面意思也很容易理解，就是一个segment构成的栈。它的内部就是通过[]Segment来组织数据。在moss中，Segment是管理数据的基本单元。所有的kv数据都是通过用Segment在内存存储的。这儿关于上面四层的具体作用我们在3.2.4节介绍读写请求过程中详细介绍。

在磁盘层面，moss中的数据也是采用小文件分段存储的，文件按照固定的格式来命名。每个文件中都按照一定的格式保存了内存中存放的用户传递进来的kv数据。具体文件的大体格式我们在3.2.2节进行介绍。

3.2.2 moss数据存储

在前面一节中提到，moss在内存中的数据是按照Segment为基本单元组织的。其中每个segment中数据采用数组存储。具体的格式如下图所示。

我们将数据分两类来介绍：kv数据、索引数据。

kv数据： moss中kv数据也是采用扁平化存储的方式来组织，所有的kv数据全部紧凑的存放在kvbuf这个[]byte中。

那这么存储之后，将来通过key来读取的时候，怎么判定指定key对应的value存储在kvbuf中什么位置，占了多长呢？其实这就涉及到moss中索引是如何组织的了。

索引数据： moss中的索引数据也是采用数组来组织的，没错，你没听错，是用的数组，它没有采用任何高阶的数据结构，仅仅用了简简单单的数组来存储。kvs这个[]uint64就是用来存储它的索引的，在moss中一个kv对在kvs对应两个元素。

第一个元素(1个uint64 占8个字节，64bit)存储的是当前kv对的元信息：操作类型<更新、删除>(占8bit)、key的长度(占24bit)、中间4bit为分隔符、value的长度(占28bit)。

第二个元素存储是当前kv信息存储在kvbuf中的偏移量offset。

其中可以看到，在moss中数据也是存在空间放大的问题的。所以必然会涉及到数据的合并/压缩。那具体怎么处理呢？我们在3.2.3节详细介绍。

综述：上面就是moss在内存中组织kv的实现思路，巧妙的通过两个数组就实现了kv数据的灵活组织。

下面我们介绍moss在磁盘上数据的组织方式，在moss中，数据最终会存储到磁盘上，内部采用mossStore结构来做持久化。在磁盘上moss是将磁盘划分成以页(4k)的单位进行读写数据。内存中的一个segment对象，在最终写磁盘时，会首先写入header信息；然后再接着写入kvindex信息；然后再写入kvbuf信息。不过有以下两点需要注意：

一个segment持久化后，会生成一个segmentLoc对象来记录该segment在磁盘上的位置信息(kvbuf保存的位置、长度等信息)
在持久化一个segment时，内部为了提升性能，对kvindex和kvbuf会做页对齐等操作；同时在moss中，提供了嵌套的特性，所以它在下图的持久化中可以看到childSegments结构，此处不再展开，感兴趣的可以阅读参考资料部分做了解。

3.2.3 moss数据合并、持久化

这一节，我们重点介绍下moss中数据的一个扭转过程，前面提到，moss中数据分为四层：top、mid、base、clean，其中每个层都是一个segmentStack。下面我们一一介绍：

1. top:用户请求刚进来的kv数据会首先放入到topSegmentStack中。 2. mid:当topSegmentStack中元素达到一定阈值后，就会将其搬移到mid中，然后做合并压缩，存放到midSegmentStack。 3. base:当midSegmentStack数据合并压缩完后，会搬移到base中，base层中的数据主要用来持久化到文件。 4. clean:当base层中的数据持久化到文件后，内部会根据设置的属性判断，是否需要缓存数据，如果缓存则将base层中的数据再迁移到clean层，否则的话就直接清除了。

其中合并压缩、持久化这两部分功能在moss中是通过后台任务来执行的，merger goroutine主要负责合并压缩；persister goroutine主要负责持久化。下面我们重点说下合并的细节。

合并主要是对topSegmentStack中搬移到midSegmentStack中的数据进行处理。根据前面介绍我们都知道了，moss的每个SegmentStack中都有多个Segment对象，而每个对象内部是由kvs和kvbuf构成。那具体怎么合并呢？

其实合并无非就是对多个数据中的数据进行处理，最直接就通过一个map对象来辅助处理就好了，但这样的话，效率非常低。根据前面介绍，我们知道moss中的segment中的数据是无序组织的，对于无序的数据也只有这种遍历办法处理了。除非能让segment中的数据有序。

重点来了，重点来了，重点来了。

如何让segment中的数据有序呢？简而言之就是对segment中的kvbuf按照key进行排序。在moss中kvbuf已经写入无法修改，但可以考虑对kvs排序。最终moss中时采用了golang包自带的sort方法对kvs进行了O(nlogn)级别的排序。当排序后，索引有序了，自然访问数据的时候，也就是可以按照有序方式访问了。

所以在合并前，moss会对midSegmentStack当前的多个segment进行排序，排完序后采用堆的方式来进行数据合并。通过这样的方式来提升合并性能，不得不说作者这顿操作设计的还是非常巧妙。看完后不得不佩服。大写的服。(此处介绍了大体的实现思路，其中很多细节并未详细说明，感兴趣的可以看源码了解)

最后，关于合并和持久化的数据完整转移过程，大家可以参考下图进行理解，如果更有兴趣可以参考官方文档和项目源码进行深入探索。moss的代码整体实现还是很优雅的，写的非常不错，值得一读。

3.2.4 读写请求过程

写过程：

所有的kv都是通过Batch接口来写入(set、delete)的，当Batch数据调用ExecuteBatch后，内部会首先将其加入到topSegmentStack栈顶，当topSegmentStack元素个数达到一定阈值后，就会将其搬移到topSegmentStack中，midSegmentStack中对数据进行合并压缩，完了以后通知持久化协程，持久化协程将midSegmentStack数据搬移到baseSegmentStack中，做持久化处理。最后持久化后，如果需要缓存，则搬移到clean中，形成cleanSegmentStack。其中存储到文件中的数据也会通过mmap的方式再打开，以便后续加速读的效率。

读过程：

读取时有两种方式，一种是直接调用Get(key)，这种方式是以当前的数据作为一个快照，然后读取，读取时会按照倒序的方式读取。一旦读取到数据就停止读取逻辑。另一种方式是通过获取一个快照Snapshot()来读取。这种方式读取在指定点的快照上进行数据的读取逻辑。整体读时，也就是首先内存；再磁盘。内存中读取时，首先通过二分的方式定位到kvs索引。然后再根据索引去kvbuf中读取数据。如果在磁盘读取时，也是会首先通过mmap读到索引、再根据索引信息读取数据。最后返回给上层用户。

3.2.5 参考资料

3.3 leveldb存储模型(lsm tree)

leveldb是采用lsm tree来构建整套存储模型的。关于lsm tree的原理在第一节中我们重点做了介绍，这一节我们再简单介绍一下leveldb的实现原理。其实rocksdb、pebble、go-leveldb这几个项目都是在最原始的leveldb基础上做了一些改进和扩展，由此发展而来的，掌握了leveldb的实现原理以后，其他几个项目的大体实现也就掌握的差不多了。这也是本节以leveldb为例介绍的主要原因。

下图描述了rocksdb、pebble、go-leveldb、leveldb这四个项目之间的关系。

此处奉上leveldb原理分析的视频教程： leveldb原理分析视频教程

3.3.1 leveldb整体架构

leveldb整体的架构，如下图所示。

在上层暴露给用户的接口也主要是针对kv的操作(增删改查:get、set、del)。下面我们再介绍一下leveldb中几个重要的组件，这几个组件也是在介绍lsm tree原理中反复提到的。

1. MemTable: 所有的kv数据进来时，会记录到MemTable中，leveldb中采用跳表来实现。 2. Immutable Memtable:当MemTable达到一定大小后，就将该MemTable关闭，转变为只读的Immutable Memtable，后续会将该Immutable Memtable 持久化到磁盘变成sstable。然后重新打开一个新的MemTable负责新的写请求。 3. log:主要指通过WAL方式记录的redo log，用来保证数据的可靠性，当进程异常挂掉重新启动时恢复数据。 4. sstable:磁盘上存储kv数据和索引的文件。当Immutable Memtable写入磁盘后，会变成一个小的sstable。另外当跨层之间合并时，也会产生新的sstable文件。

此处只是简单的介绍一下leveldb中的几个重要组件，这几个组件也是lsm tree的核心组件。关于每个组件详细的介绍此处就不展开描述了。详细内容可以点击该链接学习，这个系列写的挺详细的。

3.3.2 leveldb读写过程

leveldb的读写过程，基本符合在第一节中介绍lsm tree原理中提到的读写过程。下面在结合下图进行简要回顾。

写过程：在leveldb中当写请求进来时主要分为两步，1.会首先记录redo log，以保证数据可靠性；2.其次在记录到MemTable(采用跳表)中。

读过程：在leveldb中发起读时，读取的核心逻辑是按照倒序读取数据。整个读取过程可以分为以下三大阶段： 1. 首先在MemTable中查找，如果查找则立即返回，否则会进入第2步查找； 2. 在Immutable Memtable中查找，如果Immutable Memtable中找到，则立即返回，否则进入第3步查找； 3. 在l0层和其他l层的sstable查找，不过此处需要注意，l0层的sstable之间是数据时有可能重叠的，所以需要仍旧按照倒序依次查找；其次除l0层外的其他层，层内数据不重叠，每层最多查找一个sstable文件，同时依然遵守按照数据数据新旧的规则查找(依次从上层往下层查找,一旦找到就结束)。

说明： 1. 在leveldb的sstable中查找时，每个sstable文件中都有bloomfilter来做拦截，以起到加速读的效率。 2. leveldb中也有做缓存，提升性能。

详细的读写过程参考该书深入学习

3.3.3 leveldb压缩合并

在leveldb中可以说压缩合并是最核心的一个功能了，一方面通过压缩来解决空间放大的问题(踢除无效、冗余的数据)。另一方面也通过压缩来提升读性能、降低读放大(例如通过合并控制l0层sstable个文件个数、跨层合并减少sstable的个数等)。但同时也因为压缩合并间接造成了写放大。

leveldb中压缩分为两种类型：minor压缩、major压缩。

minor压缩：minor压缩是指将Immutable Memtable写入到文件形成l0层sstable的过程，minor压缩如下图所示。

major压缩：major压缩主要是发生在跨层合并的过程中，例如当l1层的文件个数或者数据大小达到一定阈值后，就会触发l1层的压缩，而l1层会和它相邻的l2层发生跨层合并。简单的示意图如下图所示。合并中间涉及到寻找待合并的sstable列表的过程，这个逻辑比较复杂，我们就不展开介绍了，感兴趣的可以点击链接进行学习。

具体在合并时，因为每个sstable都是有序的，所以可以采用读多归并的方式进行合并。最终当l(i)层和l(i+1)层发生合并后，会生成l(i+1)层新的sstable。

上述只是简单介绍了下压缩合并的目的以及简单的过程。其中在工程实现中，合并细节居多，居繁杂，绝不少轻描淡写几句话就能说清楚的，本文的定位是告诉读者有什么、大概怎么做的，所以此处只是抛砖引玉的大概介绍下。更深入的内容还需读者自行探索学习。

3.3.4 参考资料

3.4 lsm派系存储引擎对比

以上我们介绍了lsm派系的几类存储引擎模型，有基于lsm hash模型实现的的bitcask、有基于lsm array模型实现的的moss、还有基于lsm tree模型实现的pebble/leveldb/rocksdb。最后我们将上述几类模型做一个总结，详细对如下表所示。

4. 总结

到此本文想介绍的核心内容终于完了，在最后的部分我想结合一段时间的学习理解，谈点个人的见解，观点不一定正确、也不一定准确。只是抛出来和读者做一点讨论交流。

个人认为虽然lsm tree目前最流行、最火的。但其实单拎出来lsm(log structured merge)而言，它本身表达了两层含义：日志结构、合并。从这两个核心点切入来看。其实lsm可以看做一类思想。甚至可以说日志结构是最核心的特性(数据最终要存储在磁盘文件上)、合并是附加特性。例如：在kafka、rocketMQ等消息队列的底层数据存储上，就有体现日志结构这个特性。但是因为本身消息队列是大量写、但数据不存在合并这么一说。所以他们的存储模型上就省去了合并这个附加特性。
综上所观lsm hash存储模型、lsm array存储模型、lsm tree存储模型甚至包括kafka、rocketMQ的存储模型，他们都是充分利用磁盘顺序写的特性来提升写性能，近而更好的处理写多读少的场景。在这个过程中就必然涉及到数据存储及索引存储这两个问题。
1. 针对数据存储，无非就两种：磁盘上无序存储(lsm hash)、磁盘上有序存储(其他几类)。数据有序存储则需要在写入前对其进行排序，所以在开始时可以选择本身就支持排序操作的数据结构来组织，例如lsm tree这个系列；也可以采用对其较容易排序的数据结构，后期要写入文件时再排序，例如lsm array，采用数组组织，最后通过对数组排序实现。kafka、rocketMQ这类数据也是有序的，因为每个消息在写入文件时都有一个单调增长的消息id。所有数据按照消息id升序。而无序存储时，那就最简单了，直接追加写文件即可。不过无序存储和有序存储想比较而言。有序存储可以自然支持对外的排序和范围查找这类操作；而无序存储想要支持排序、范围查找的操作，则必须要在索引上下功夫。
2. 索引存储时，最核心的理念就是：某一条数据写在哪个磁盘文件的什么位置、占了多长。然后不同的存储模型在具体存储时会有差异，当存储数据量很大时，索引本身的数据也很大很占空间，比如lsm hash采用ART树来节约存储空间。而kafka则采用稀疏索引的方式记录索引信息(每隔几条数据记录一个索引)、leveldb中也有采用稀疏索引的方式来存储。
关于数据合并压缩这个特性，上述几类需要压缩的模型除了lsm hash外，都基本上是采用保证待合并的多个文件有序，然后多路归并的方式来实现高效率的合并。
在写入时分为两种：数据立即写磁盘、数据异步写磁盘(需要采用redo log保证数据可靠性)，但二者本质上都是利用顺序写磁盘所以很快。在读取时，通常的优化的做法有两类：通过mmap加速读、通过内存中缓存数据加速读。