分布式数据库实战第三节 分布式数据库引擎、索引和事务_分布式索引

07 概要：什么是存储引擎，为什么需要了解它？

经过第一个模块的学习，相信你已经知道了什么是分布式数据库，对分布式数据库的核心知识有了比较全面和深入的了解了。

这一讲是第二模块存储引擎的概要，主要目的是为你解释什么是存储引擎，以及它在分布式数据库中起到什么样的作用。

数据库的一个首要目标是可靠并高效地管理数据，以供人们使用。进而不同的应用可以使用相同的数据库来共享它们的数据。数据库的出现使人们放弃了为每个独立的应用开发数据存储的想法，同时，随着数据库广泛的使用，其处理能力飞速发展，演进出如现代的分布式数据库这般惊人的能力。

那么，为了支撑抽象的多种场景。一般的数据库都会采用多模块或多子系统的架构来构建数据库，从而方便数据库项目团队依据现实的场景来组合不同的子模块，进而构造出一众丰富的数据库产品。

而存储引擎就是这一众模块中极为重要的一环，下面我们开始解释它在整个数据库架构中的定位和意义。

存储引擎的定位

这个世界上，没有针对数据库设计的一定之规。每个数据库都是根据它所要解决的问题，并结合其他因素慢慢发展成如今的模样的。所以数据库子模块的分化也没有一个广泛接受的标准，且有些模块之间的边界也是很模糊的。特别是需要优化数据库性能时，原有被设计为独立存在的模块很可能会融合以提高数据库整体性能。

这里，我总结出了一个比较典型的分布式数据库的架构和模块组合标准。虽然不能完全代表所有分布式数据库，但是可以帮助你理解模块的组成方式。这里需要注意，我给出的模型是基于客户端/服务器，也就是 C/S 模式的，因为这是大部分分布式数据库的架构模式。

1. 传输层：它是接受客户端请求的一层。用来处理网络协议。同时，在分布式数据库中，它还承担着节点间互相通信的职责。

2. 查询层：请求从传输层被发送到查询层。在查询层，协议被进行解析，如 SQL 解析；后进行验证与分析；最后结合访问控制来决定该请求是否要被执行。解析完成后，请求被发送到查询优化器，在这里根据预制的规则，数据分布并结合数据库内部的统计，会生成该请求的执行计划。执行计划一般是树状的，包含一系列相关的操作，用于从数据库中查询到请求希望获取的数据。

3. 执行层：执行计划被发送到执行层去运行。执行层一般包含本地运行单元与远程运行单元。根据执行计划，调用不同的单元，而后将结果合并返回到传输层。

细心的你可能会注意到，这里只有查询层，那么数据是怎么写入的？这对于不同的数据库，答案会非常不同。有的数据库会放在传输层，由于协议简单，就不需要额外处理，直接发送到执行层；而有些写入很复杂，会交给查询层进行处理。

以上就是数据库领域中比较常见的模块划分方式。你可能有这样的疑问：那么存储引擎在哪里呢？

执行层本地运行单元其实就是存储引擎。它一般包含如下一些功能：

1. 事务管理器：用来调度事务并保证数据库的内部一致性（这与模块一中讨论的分布式一致性是不同的）；

2. 锁管理：保证操作共享对象时候的一致性，包括事务、修改数据库参数都会使用到它；

3. 存储结构：包含各种物理存储层，描述了数据与索引是如何组织在磁盘上的；

4. 内存结构：主要包含缓存与缓冲管理，数据一般是批量输入磁盘的，写入之前会使用内存去缓存数据；

5. 提交日志：当数据库崩溃后，可以使用提交日志恢复系统的一致性状态。

以上就是存储引擎比较重要的几个功能，其核心就是提供数据读写功能，故一般设计存储引擎时，会提供对其写入路径与读取路径的描述。

好了，现在你清楚了存储引擎的定位和主要结构，那么存储引擎的种类也是很多的，下面我通过一些关键特性，来介绍几种典型的存储引擎。

内存与磁盘

存储引擎中最重要的部分就是磁盘与内存两个结构。而根据数据在它们之中挑选一种作为主要的存储，数据库可以被分为内存型数据库与磁盘型数据库。由此可见存储引擎的一个功能，就是可以被作为数据库类型划分的依据，可见引擎的重要性。

内存型存储是把数据主要存储在内存里，其目的很明显，就是加快数据读写性能。分布式数据库一个重要的门类就是内存型数据库，包括 Redis、NuoDB 和 MySQL Cluster 等。当然其缺点也很明显，那就是内存的成本较高，且容量有限。而分布式的架构能有效地扩充该类数据库的容量，这也是内存数据库主要是分布式数据库的原因。

磁盘存储相对传统，它存储主要数据，而内存主要作为缓冲来使写入批量化。磁盘存储的好处是，存储性价比较高，这主要得益于磁盘甚至是磁带的单位存储价格相比内存非常低廉。但是与内存型数据库相比，磁盘型数据库的性能比较低。不过，随着近年 SSD 磁盘的普及，这种趋势得到了有效的改善。

这两种存储引擎的差别还体现在功能实现的难度上。内存型数据库相对简单，因为写入和释放随机的内存空间是相对比较容易的；而磁盘型数据库需要处理诸如数据引用、文件序列化、碎片整理等复杂的操作，实现难度很高。

从目前的分布式数据库发展来看，磁盘型存储引擎还是占据绝对统治地位的。除了性价比因素外，内存型数据库要保证不丢失数据的代价是很高昂的，因为掉电往往就意味着数据的丢失。虽然可以使用不间断电源来保证，但是需要复杂的运维管理来保证数据库稳定运行。

然而近年来，随着 NVM（Non-Volatile Memory，非易失性内存）等技术的引入。这种情况开始出现了一些变化，此种存储具有 DRAM 内存的性能，同时能保证掉电后数据不丢失。且最重要的是读写模式类似于内存，方便应用去实现功能。有了它的加持，未来内存型数据库还将有比较大的发展。

除了硬件加持，内存型数据库也可以通过结构设计来保证数据不丢失。最常用的手段就是使用数据备份+提交日志的模式。数据库为了不影响写入读取性能，可以异步地备份数据。同时在每次写入数据之前要先写入提交日志，也就是说提交日志的写入成功才被认为是数据写入成功。

当数据库节点崩溃恢复后，将备份拿出来，计算出该备份与最新日志之间的差距，然后在该备份上重放这些操作。这样就保证数据库恢复出了最新的数据。

除了内存和磁盘的取舍，存储引擎还关心数据的组合模式，现在让我们看看两种常见的组合方式：行式与列式。

行式存储与列式存储

数据一般是以表格的形式存储在数据库中的，所以所有数据都有行与列的概念。但这只是一个逻辑概念，我们将要介绍的所谓“行式”和“列式”体现的其实是物理概念。

行式存储会把每行的所有列存储在一起，从而形成数据文件。当需要把整行数据读取出来时，这种数据组织形式是比较合理且高效的。但是如果要读取多行中的某个列，这种模式的代价就很昂贵了，因为一些不需要的数据也会被读取出来。

而列式存储与之相反，不同行的同一列数据会被就近存储在一个数据文件中。同时除了存储数据本身外，还需要存储该数据属于哪行。而行式存储由于列的顺序是固定的，不需要存储额外的信息来关联列与值之间的关系。

列式存储非常适合处理分析聚合类型的任务，如计算数据趋势、平均值，等等。因为这些数据一般需要加载一列的所有行，而不关心的列数据不会被读取，从而获得了更高的性能。

我们会发现 OLTP 数据库倾向于使用行式存储，而 OLAP 数据库更倾向于列式存储，正是这两种存储的物理特性导致了这种倾向性。而 HATP 数据库也是融合了两种存储模式的一种产物。

当然这里我们要区分 HBase 和 BigTable 所说的宽列存储与列存储在本质上是不同的。宽列存储放在其中的数据的列首先被聚合到了列簇上，列簇被放在不同的文件中；而列簇中的数据其实是按行进行组织的。

选择行模式与列模式除了以上的区分外，一些其他特性也需要考虑。在现代计算机的 CPU 中，向量指令集可以一次处理很多类型相同的数据，这正是列式存储的特点。同时，将相同类型数据就近存储，还可以使用压缩算法大大减少磁盘空间的占用。

当然，选择这两种存储模式最重要的因素还是访问模式。如果数据主要是按照行进行读取，比如交易场景、资料管理场景等，那么行式存储应是首选。如果需要经常查询所有数据做聚合，或者进行范围扫描，那么列式存储就很值得一试。

以上就是常见的数据的组合模式，那么组合好的数据如何存储在物理设备上呢？下面让我们探讨一下数据文件和索引文件两种常用的存放数据的物理原件。

数据文件与索引文件

上文介绍了内存与磁盘之间的取舍，从中可看到磁盘其实更为重要的，因为数据库是提供数据持久化存储的服务。故我们开始介绍磁盘上最为重要的两类文件：数据文件和索引文件。

数据文件和索引文件如名字所示，分别保存原始数据与检索数据用的索引数据。

但是随着时间的推移，两者的区分也不是那么泾渭分明了。其中以 IOT（索引组织表）模式为代表的数据文件在数据库，特别是分布式数据库中占据越来越重的位置。一种将两者进行融合的趋势已经变得势不可挡。

数据文件最传统的形式为堆组织表（Heap-Organized Table），数据的放置没有一个特别的顺序，一般是按照写入的先后顺序排布。这种数据文件需要一定额外的索引帮助来查找数据。

另外有两种数据表形式自带了一定的索引数据能力，即哈希组织表（Hash-Organized Table）和索引组织表（Index-Organized Table）。前者是将数据通过哈希函数分散到一组数据桶内，桶内的数据一般是按照一定规则进行排序，以提高查询效率；而后者一般采用索引文件的形式来存储数据，以 B+树为例，数据被存储在叶子节点上，这样做的目的是减少检索数据时读取磁盘的次数，同时对范围扫描支持友好。

索引文件的分类模式一般为主键索引与二级索引两类。前者是建立在主键上的，它可能是一个字段或多个字段组成。而其他类型的索引都被称为二级索引。主键索引与数据是一对一关系，而二级索引很有可能是一对多的关系，即多个索引条目指向一条数据。

这里按照索引与数据之间结合的程度，我们又可以把索引分为聚簇索引和非聚簇索引。前者如哈希组织表和索引组织表那样，数据的分布与索引分布是有关联的，它们被“聚”在一起，这样的查询效率很好。而后者最常见的例子就是针对这两种数据文件的二级索引，因为二级索引要索引的列不是主键，故索引与数据是分割的，查询时需要进行多次磁盘读取。但是对于写入，聚簇索引可能需要进行唯一判断，性能会比简单构建的非聚簇索引低效。

最后一点需要说明的是，二级索引需要保存指向最终数据的“引用”。从实现层面上，这个引用可以是数据的实际位置，也可以是数据的主键。前者的好处是查询效率高，而写入需要更新所有索引，故性能相对较低。而后者就恰好相反，查询需要通过主键索引进行映射，效率稍低，但写入性能很稳定，如 MySQL 就是选用后者作为其索引模式。

面向分布式的存储引擎特点

以上内容为存储引擎的一些核心内容。那分布式数据库相比传统单机数据库，在存储引擎的架构上有什么不同呢？我总结了以下几点。

内存型数据库会倾向于选择分布式模式来进行构建。原因也是显而易见的，由于单机内存容量相比磁盘来说是很小的，故需要构建分布式数据库来满足业务所需要的容量。

列式存储也与分布式数据库存在天然的联系。你可以去研究一下，很多列式相关的开源项目都与 Hadoop 等平台有关系的。原因是针对 OLAP 的分析数据库，一个非常大的应用场景就是要分析所有数据。

而列式存储可以被认为是这种模式的一种优化，实现该模式的必要条件是要有分布式系统，因为一台机器的处理能力是有瓶颈的。如果希望处理超大规模数据，那么将数据分散到多个节点就成为必要的方式。所以说，列模式是由分析性分布式的优化需求所流行起来的。

至于宽列存储更是分布式数据库场景下才会采用的模式。

数据文件的组织形式，分布式数据库几乎不会使用堆组织表。因为该形式过于随意，无法有效地分散数据。不知道学习过数据分片那一讲的时候你有没有注意到，另外两种组织表的名字与两种分片算法是有着天然联系的。

哈希组织表数据经过哈希函数散列到不同的桶，这些桶可以被分散到不同节点。而索引组织表一般叶子节点是按一定顺序排列的，这与范围分片又有着某种契合的关系。所以分布式数据库一般都会采用这两种模式作为其存储引擎，甚至一些分布式数据库直接将数据文件当作索引使用。

总结

好了，关于存储引擎我就介绍到这了。这一讲我们首先展示了数据库的整体架构，并点出了存储引擎所在的位置；而后分别讨论了存储引擎中几组概念的对比，并在最后说明了分布式数据库在引擎层面的选择及其原因。

当然，本讲只是一篇概述。存储引擎中其他重要的概念，我会在本模块随后的几讲中为你详细介绍。

教学相长

这里还是留给你一个思考题：目前有哪些独立的存储引擎，它们的基本特点是什么？请试着用本讲提到的知识点来回答。在本模块最后一讲中，我会告诉你我的答案。

下一讲，我们来聊聊分布式索引，让你知道如何在集群中快速定位数据。到时见。

---

08 分布式索引：如何在集群中快速定位数据？

索引是数据检错的关键技术，那么在分布式数据库这种体量的数据容量下，如单机数据那样进行数据表全量扫描是非常不现实的，故分布式存储引擎的关键就是要通过索引查找目标数据。

由于索引在不同的数据库概念里内涵是非常不同的，故本讲首先会定义我们要讨论的索引的内涵；接着会描述数据库的读取路径，从中可以观察到主要索引的使用模式；而后会重点介绍磁盘上与内存中的索引结构；最后会谈谈非主键索引，即二级索引的意义和主要实现形式。

那么，让我们从什么是分布式索引说起。

说到分布式索引时，我们在谈论什么？

首先，我要说明一下谈到分布式索引，需要了解什么样的内容。通过上一讲的学习，你已经知道存储引擎中包含数据文件和索引文件，同时索引文件中又有索引组织表这种主要的形式。目前世界上主要的分布式数据库的数据存储形式，就是围绕着索引而设计的。

为什么会这样呢？

由于分布式数据库的数据被分散在多个节点上，当查询请求到达服务端时，目标数据有极大的概率并不在该节点上，需要进行一次甚至多次远程调用才可查询到数据。由于以上的原因，在设计分布式数据库存储引擎时，我们更希望采用含有索引的数据表，从而减少查询的延迟。

这同时暗含了，大部分分布式数据库的场景是为查询服务的。数据库牺牲了部分写入的性能，在存入数据的时候同时生成索引结构。故分布式数据库的核心是以提供数据检索服务为主，数据写入要服务于数据查询。从这个意义上说，分布式索引就是数据存储的主要形式。

本讲会以 NewSQL 和 Cassandra 为代表，介绍典型的 NoSQL 的存储引擎中的主要技术，力图帮助你理解此类数据库中存储引擎检索数据的路径。

读取路径

掌握分布式数据库存储引擎，一般需要明确其写入路径与读取路径。但如上文讨论的那样，写入是严重依赖读取的，故明确读取路径我们就可以指明写入的规则。

因此这一部分，我们先来明确存储引擎是如何处理查询请求的。一般的规则如下：

1. 寻找分片和目标节点；

2. 检查数据是否在缓存与缓冲中；

3. 检查数据是否在磁盘文件中；

4. 合并结果。

第一步就是要查找数据在分布式系统的哪个目标节点上。严格说，这一步并不是存储引擎所囊括的部分，但为了表述清楚，我们也将它加入读取路径中来。由于分布式数据库采用分片技术来分散数据，那么查询条件中如果有分片键，就可以应用分片算法来计算出分片，也就是目标节点所在的位置；而如果不包含分片键，就需要“二级索引”来帮忙寻找分片键了，之后的逻辑与使用分片键查找就相似了。

第二步，既然确定了所在节点，那么剩下的就交给存储引擎了。首先需要在缓存（Cache）中进行查找。缓存包含数据缓存或行缓存，其中包含真实的数据，用于快速检索经常访问的数据，一般元数据和静态配置数据都会放在数据缓存里面。而后再缓冲查找数据，缓冲是为了批量写入数据而预留的一段内存空间，当写满缓冲后，数据会被刷入磁盘中，所以会有部分数据存在缓冲之中。

第三步，确定了数据并不在内存中，这时就需要检查磁盘了。我们需要在具有索引的数据文件内查找响应的数据。通过之前的学习我们可以知道，每个数据文件都有主键索引，可以直接在其中查找数据。但是，存储引擎为了写入性能，会把数据拆分在众多的数据文件内部。所以我们需要在一系列文件中去查找数据，即使有索引的加成，查找起来的速度也不是能够令人满意的。这个时候我们可以引入布隆过滤，来快速地定位目标文件，提高查询效率。

最后一步是对结果进行归并。根据执行层的不同需求，这里可以马上返回部分匹配结果，也可以一次性返回全部结果。

现在我们已经勾勒出存储引擎的一个完整的读取路径，可以看到路径上一些关键技术是保证数据查询与读取的关键点。下面我们就分别介绍其中所涉及的关键技术。

索引数据表

我在前文提到过，含有索引的数据表有索引组织表和哈希组织表。其实，我们在分布式数据库中最常见的是 Google 的 BigTable 论文所提到的 SSTable（排序字符串表）。

Google 论文中的原始描述为：SSTable 用于 BigTable 内部数据存储。SSTable 文件是一个排序的、不可变的、持久化的键值对结构，其中键值对可以是任意字节的字符串，支持使用指定键来查找值，或通过给定键范围遍历所有的键值对。每个 SSTable 文件包含一系列的块。SSTable 文件中的块索引（这些块索引通常保存在文件尾部区域）用于定位块，这些块索引在 SSTable 文件被打开时加载到内存。在查找时首先从内存中的索引二分查找找到块，然后一次磁盘寻道即可读取到相应的块。另一种方式是将 SSTable 文件完全加载到内存，从而在查找和扫描中就不需要读取磁盘。

从上面的描述看，我们会发现这些键值对是按照键进行排序的，而且一旦写入就不可变。数据引擎支持根据特定键查询，或进行范围扫描。同时，索引为稀疏索引，它只定位到数据块。查到块后，需要顺序扫描块内部，从而获取目标数据。

下面就是 RocksDB 的 SSTable 结构，可以看到数据是放在前面，后索引作为 metadata 放在文件尾部，甚至 meta 的索引也是放在整个 meta 结构的尾部。

<beginning_of_file>
[data block 1]
[data block 2]
...
[data block N]
[meta block 1: filter block]                  
[meta block 2: index block]
[meta block 3: compression dictionary block]  
[meta block 4: range deletion block]          
[meta block 5: stats block]               
...
[meta block K: future extended block]  
[metaindex block]
[Footer]                          
<end_of_file>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

当然 SSTable 的实现并不一定是通过一个文件，不同的存储引擎会采用不一样的策略去实现它。有的是使用一个文件，如 BigTable 论文中描述的那样，将数据放置在文件开始的部分，索引放在文件结尾。或者将数据和索引分开，放置在不同的文件中。

数据是按照键的顺序放置的，所以不论索引的实现形式如何，数据文件本身是支持范围扫描的。即使使用没有规律的哈希表，数据部分也可以正常支持范围扫描。

这里要注意，SSTable 是不可变的，也就是输入一旦写入是不可以更改的，而修改和删除操作一般也是以写入的形式进行的。这就需要进行合并（Compaction），将对同一个数据的操作合并为最终的结果。这个过程类似于上文中数据库面临故障崩溃后恢复的过程，其中日志回放与合并的基本思想是相同的。关于 SSTable 的详细操作，我们会在 LSM 树这种存储引擎的介绍中详细说明。

当然索引数据表的实现方式不仅仅有 SSTable 一种，对数据库索引有所了解的朋友应该都知道，B 树家族在索引领域扮演着举足轻重的角色。原因是 B 树的每个节点可以有多个数据，所以可以在高度与宽度上进行平衡，从而有效降低磁盘寻道次数。

但是对 B 树的更新代价是非常高的，故分布式数据库为了写入高效会采用一系列优化手段去提高更新 B 树的效率。这里我们以 MongoDB 的 WiredTiger 存储引擎为例，来介绍其中的一个优化手段。

这个优化方式就是缓存最近的对索引的操作，而后将操作固化到磁盘中。WiredTiger 使用 B 树来存储数据，在内存页中，B 树节点带有一个修改缓冲，这个缓冲保存的一个指向磁盘原始数据的引用。而后，在读取流程中，原始磁盘数据结合内存缓冲数据后，再返回给用户。这么做的好处是，数据的刷新和内存页更新都是由后台线程完成，不会去阻塞读写操作。

以上就是两种带有索引性质的数据表实现的逻辑，从中可以看到提高写入速度的关键点，不是采用顺序的形式写入，就是缓存随机写入，从而转变为顺序写入。

以上介绍的两种数据表都包含内存中的缓冲结构，用以应对内存与磁盘两种设备写入速度差的问题，我在这一讲的后面将会详细介绍其中使用的数据结构。

下面我们再来看看内存缓冲。

内存缓冲

目前有很多种不同的数据结构可以在内存中存储有序的数据。在分布式数据库的存储引擎中，有一种结构因其简单而被广泛地使用，那就是跳表（SkipList）。

跳表的优势在于其实现难度比简单的链表高不了多少，但是其时间复杂度可以接近负载平衡的搜索树结构。

跳表在插入和更新时避免对节点做旋转或替换，而是使用了随机平衡的概念来使整个表平衡。跳表由一系列节点组成，它们又由不同的高度组成。连续访问高度较高的节点可以跳过高度较低的节点，有点像蜘蛛侠利用高楼在城市内快速移动一样，这也就是跳表名称的来源。现在我们用一个例子来说明跳表的算法细节。请看下面的图片。

如果我们以寻找 15 为例来说明跳表的查找顺序。

1. 首先查找跳表中高度最高的节点，从图中可以看到是10。

2. 目标节点 15 比 10 大，从当前高度，也就是最高的高度，向后找没有任何节点，这个时候需要降低一个高度。

3. 高度降低后，找到了节点 22，它比 15 要大，这个时候我们又回到了 10 节点，且要继续降低高度。

4. 现在降低到了最低，而后顺利地找到了 15。

如果节点需要插入、删除和修改。就需要进行树的平衡，这个时候需要将节点在不同高度上移动，而且高度也会随着节点的数量而变化。要怎么决定变化的数量呢？答案其实很简单，使用随机数来决定这些变量。随机数虽然不是严格均分数据，但是可以做到相对均匀，且代价很小。这也是该算法被广泛使用的原因：用比较小的代价去实现较好的结果，简而言之，其通入产出比非常可观。

以上就是内存中常用的快速搜索数据结构，那么我们如何判断数据在哪个磁盘文件中呢？答案就是使用布隆过滤。

布隆过滤

以上介绍的内容包含了如何在数据文件以及在数据文件缓冲里查找数据。在查询路径中，我们介绍了，除了向所有数据文件请求查询（也被称作读放大）外，还可以利用布隆过滤快速定位目标数据文件。

布隆过滤的原理是，我们有一个非常大的位数组，首先初始化里面所有的值为 0；而后对数据中的键做哈希转换，将结果对应的二进制表示形式映射到这个位数组里面，这样有一部分 0 转为 1；然后将数据表中所有建都如此映射进去。

查找的时候，将查询条件传入的键也进行类似的哈希转换，而后比较其中的 1 是否与数组中的匹配，如果匹配，说明键有可能在这个数据表中。

可以看到，这个算法是一个近似算法，存在误判的可能。也就是所有位置都是 1，但是键也可能不在数据表内，而这些 1 是由于别的键计算产生的。

但是在查找数据文件的场景中，这个缺陷可以忽略。因为如果布隆过滤判断失败，也只是多浪费一些时间在数据表中查找，从而退化为读放大场景，并不会产生误读的情况。

布隆过滤的原理简单易懂，它对于 LSM 树存储引擎下所产生的大量 SSTable 的检索很有帮助，是重要的优化查询的手段。

二级索引

我以上谈到的所有查询方式都是基于主键索引，但是在真实的场景下，非主键经常需要作为查询条件。这个时候就引入了二级索引的概念。

二级索引一般都是稀疏索引，也就是索引与数据是分离的。索引的结果一般保存的是主键，而后根据主键去查找数据。这在分布式场景下有比较明显的性能问题，因为索引结果所在的节点很可能与数据不在一个节点上。

以上问题的一个可行解决方案是以二级索引的结果（也就是主键）来分散索引数据，也就是在数据表创建时，同时创建二级索引。Apache Cassandra 的 SASI 在这方面就是一个很好的例子。它绑定在 SSTable 的生命周期上，在内存缓存刷新或是在数据合并时，二级索引就伴随着创建了。这一定程度上让稀疏的索引有了一定亲和性。

如果要使用键值对实现二级索引，那么索引结果会有如下几种组合方式。

1. 急迫模式：将索引结果快速合并到一个 value 中，而后一次查询就可以查到所以结果。

2. 正常模式：使用多个键值对保留数据。

3. 键组合模式：把索引与结果全都放在 key 上，value 是空的。

总体来说，三种模式读取性能接近，但急迫模式的写入性能会低一些。但是对于不同的 key-value 底层实现，其性能会有差别，比如 wisckey（将在第 11 讲中介绍）实现的键值分离模式，使用组合模式就有意义。同时由于键组合模式比较简单，且适合键扫描算法的实现，故是一种比较常见二级索引形式。

总结

本讲内容就介绍到这里了。这一讲我们首先说明了分布式索引的概念，实际上它就是分布式数据库存储引擎中用来存储数据的所有技术的总称；而后我介绍了存储引擎的查询路径，帮你在心中建立起存储引擎处理查询的整体概念；最后我又分别介绍了影响查询路径的多个关键技术，并给出了实际的案例。

那么下一讲，我们来聊聊一个被许多分布式数据库使用的典型的存储引擎 LSM 树，欢迎你准时来学习，谢谢。

---

09 日志型存储：为什么选择它作为底层存储？

在上一讲中，我们学习了存储引擎的逻辑概念与架构。这些概念和架构都是总结了数个存储引擎的特点后，勾勒出的高度抽象的形象。目的是帮助你对数据库存储引擎，特别是分布式数据库存储引擎有一个总体认识，从而建立起一个知识体系。

但是，只有高度抽象的内容，而没有具体的案例，对于理解相关概念是远远不够的。这一讲，我将以经典日志合并树（LSM 树）——这个典型的日志型存储引擎为切入点，为你直观展示存储引擎的设计特点；同时我会解释为什么此类存储引擎特别适合于分布式数据库。

那么，我们首先开始介绍 LSM 树的结构特点。

LSM 树的结构

LSM 树存储引擎的结构暗含在它的名字内。LS 代表日志结构，说明它是以日志形式来存储数据的，那么日志有什么特点呢？如果你对财务记账有些了解的话，会知道会计在删除一笔记录时，是不会直接拿着橡皮擦去擦掉这个记录的，而是会写一笔与原金额相等的冲抵操作。这就是典型的日志型存储的模式。

日志型存储的特点是对写入非常友好，不像 B 树等结构需要进行随机写，日志存储可以进行顺序性写。因为我们常用的 HDD 磁盘是有旋转机构的，写入延迟主要发生在磁盘旋转与读写臂的移动上。如果数据可以顺序写入，可以大大加快这种磁盘机构的写入速度。

而 M 则暗含这个结构会存在合并操作，形成最终的可读取结构。这样读取操作就不用去查找对于该记录的所有更改了，从而加快了读取速度。同时将多个记录合并为一个最终结果，也节省了存储空间。虽然合并操作有诸多优点，但是它也不是没有代价的，那就是会消耗一定的计算量和存储空间。

现在让我们开始详细介绍 LSM 树的结构。

LSM 树包含内存驻留单元和磁盘驻留单元。首先数据会写入内存的一个缓冲中，而后再写到磁盘上的不可变文件中。

内存驻留单元一般被称为 MemTable（内存表），是一个可变结构。它被作为一个数据暂存的缓冲使用，同时对外提供读取服务。当其中的数据量到达一个阈值后，数据会被批量写入磁盘中的不可变文件内。

我们看到，它最主要的作用是将写入磁盘的数据进行排序，同时批量写入数据可以提高写入的效率。但是数据库一旦崩溃，内存中的数据会消失，这个时候就需要引入“07 | 概要：什么是存储引擎，为什么需要了解它”中提到的提交日志来进行日志回放，从而恢复内存中的数据了。但前提是，数据写入内存之前，要首先被记录在提交日志中。

磁盘驻留单元，也就是数据文件，是在内存缓冲刷盘时生成的。且这些数据文件是不可变的，只能提供读取服务。而相对的，内存表同时提供读写两个服务。

关于 LSM 树的结构，一般有双树结构和多树结构两种。前者一般是一个理论说明，目前没有一个实际的存储引擎是使用这种结构的。所以我简单说一下双树概念，它有助于你去理解多树结构。

双树中的两棵树分别指：内存驻留单元和磁盘驻留单元中分别有一棵树，你可以想象它们都是 B 树结构的。刷盘的时候，内存数据与磁盘上部分数据进行合并，而后写到磁盘这棵大树中的某个节点下面。成功后，合并前的内存数据与磁盘数据会被移除。

可以看到双树操作是比较简单明了的，而且可以作为一种 B 树类的索引结构而存在。但实际上几乎没有存储引擎去使用它，主要原因是它的合并操作是同步的，也就是刷盘的时候要同步进行合并。而刷盘本身是个相对频繁的操作，这样会造成写放大，也就是会影响写入效率且会占用非常大的磁盘空间。

多树结构是在双树的基础上提出的，内存数据刷盘时不进行合并操作，而是完全把内存数据写入到单独的文件中。那这个时候另外的问题就出现了：随着刷盘的持续进行，磁盘上的文件会快速增加。这时，读取操作就需要在很多文件中去寻找记录，这样读取数据的效率会直线下降。

为了解决这个问题，此种结构会引入合并操作（Compaction）。该操作是异步执行的，它从这众多文件中选择一部分出来，读取里面的内容而后进行合并，最后写入一个新文件中，而后老文件就被删除掉了。如下图所示，这就是典型的多树结构合并操作。而这种结构也是本讲介绍的主要结构。

最后，我再为你详细介绍一下刷盘的流程。

首先定义几种角色，如下表所示。

数据首先写入当前内存表，当数据量到达阈值后，当前数据表把自身状态转换为刷盘中，并停止接受写入请求。此时会新建另一个内存表来接受写请求。刷盘完成后，由于数据在磁盘上，除了废弃内存表的数据外，还对提交日志进行截取操作。而后将新数据表设置为可以读取状态。

在合并操作开始时，将被合并的表设置为合并中状态，此时它们还可以接受读取操作。完成合并后，原表作废，新表开始启用提供读取服务。

以上就是经典的 LSM 树的结构和一些操作细节。下面我们开始介绍如何对其进行查询、更新和删除等操作。

查询、更新与删除操作

查询操作本身并没有 LSM 树的特色操作。由于目标数据可能在内存表或多个数据表中，故需要对多个数据源的结果数据进行归并操作。其中使用了排序归并操作，原因也非常简单，因为不论是内存表还是数据表，其中的数据都已经完成了排序。排序归并算法广泛应用在多种数据库中，如 Oracle、MySQL，等等。另外数据库中间 Apache ShardingShpere 在处理多数据源 order by 时，也使用了这个方法。感兴趣的话你可以自行研究，这里我就不占用过多篇幅了。

而查询另外一个问题是处理同一份数据不同版本的情况，虽然合并操作可以解决部分问题，但合并前的数据还需要通过查询机制来解决。我刚介绍过 LSM 树中对数据的修改和删除本质上都是增加一条记录，因此数据表和内存表中，一份数据会有多条记录，这个时候查询就需要进行冲突处理。一般一份数据的概念是它们具有相同的 key，而往往不同的版本会有时间戳，根据这个时间戳可以建立写入顺序，这类似于向量时钟的概念。故查询中我们很容易判断哪条数据是最新数据。

更新和删除操作本质上是插入数据，然后根据上面提到的冲突处理机制和合并操作来获取最终数据。更新操作是比较简明的，插入新数据就好了。但是删除操作时插入的是什么呢？

一般插入的是特殊的值，被称作墓碑（Tombstone）。它是一个特殊的值，用来表示记录被删除。如果要产出一个范围内数据呢？Apache Cassandra 的处理方法是引入范围墓碑（Range Tombstone）。

比如有从 k0 到 k9 的 9 条数据，在 k3 处设置开始删除点（包含 k3），在 k7 处设置结束删除点（不包含 k7），那么 k3 到 k6 这四条数据就被删除了。此时查询就会查不到 k4 到 k6，即使它们上面没有设置墓碑。

以上我们介绍了 LSM 树中最基本的操作，下面我再为你介绍一种非常特殊的操作，那就是合并操作。

合并操作

合并操作是用来维护 LSM 树的结构的，以保证其可以正常运行。需要强调的一点是，我们这里说的合并操作针对的是 LSM 树的结构里面提到的多树结构。在多树结构中，磁盘中表的数量随着刷盘动作的持续进行，而变得越来越多。合并操作正是让它们减少的一种手段。

合并操作会根据一定规则，从磁盘的数据文件中选择若干文件进行合并，而后将新文件写入磁盘，成功后会删除老数据。在整个操作的过程中，对内存的消耗是完全可控的。这是由于每个数据文件都是经过排序的，如上一讲提到的查询规则一样，我们依然可以通过排序归并来合并多个文件中的数据。这种合并每次只会加载部分数据，也就是每个文件头部的数据，进入内存进行合并操作。从而很好地控制了合并操作对内存资源的消耗。

在整个合并的过程中，老的数据表依然可以对外提供读取服务，这说明老数据依然在磁盘中。这就要求磁盘要留有一定的额外空间来容纳生成中的新数据表。同时合并操作可以并行执行，但是一般情况下它们操作的数据不会重合，以免引发竞争问题。合并操作既可以将多个数据文件合并成一个，也可以将一个数据文件拆分成多个。

常见的合并策略有 Size-Tiered Compaction 和 Leveled Compaction。

Size-Tiered Compaction

下图就是这种策略的合并过程。

其中，数据表按照大小进行合并，较小的数据表逐步合并为较大的数据表。第一层保存的是系统内最小的数据表，它们是刚刚从内存表中刷新出来的。合并过程就是将低层较小的数据表合并为高层较大的数据表的过程。Apache Cassandra 使用过这种合并策略。

该策略的优点是比较简单，容易实现。但是它的空间放大性很差，合并时层级越高该问题越严重。比如有两个 5GB 的文件需要合并，那么磁盘至少要保留 10GB 的空间来完成这次操作，可想而知此种容量压力是巨大的，必然会造成系统不稳定。

那么有没有什么策略能缓解空间放大呢？答案就是 Leveled Compaction。

Leveled Compaction

如名称所示，该策略是将数据表进行分层，按照编号排成 L0 到 Ln 这样的多层结构。L0 层是从内存表刷盘产生的数据表，该层数据表中间的 key 是可以相交的；L1 层及以上的数据，将 Size-Tiered Compaction 中原本的大数据表拆开，成为多个 key 互不相交的小数据表，每层都有一个最大数据量阈值，当到达该值时，就出发合并操作。每层的阈值是按照指数排布的，例如 RocksDB 文档中介绍了一种排布：L1 是 300MB、L2 是 3GB、L3 是 30GB、L4 为 300GB。

该策略如下图所示。

上图概要性地展示了从 L1 层开始，每个小数据表的容量都是相同的，且数据量阈值是按 10 倍增长。即 L1 最多可以有 10 个数据表，L2 最多可以有 100 个，以此类推。

随着数据表不断写入，L1 的数据量会超过阈值。这时就会选择 L1 中的至少一个数据表，将其数据合并到 L2 层与其 key 有交集的那些文件中，并从 L1 中删除这些数据。

仍然以上图为例，一个 L1 层数据表的 key 区间大致能够对应到 10 个 L2 层的数据表，所以一次合并会影响 11 个文件。该次合并完成后，L2 的数据量又有可能超过阈值，进而触发 L2 到 L3 的合并，如此往复。

可见，Leveled Compaction 与 Size-Tiered Compaction 相比，每次合并时不必再选取一层内所有的数据，并且每层中数据表的 key 区间都是不相交的，重复 key 减少了，所以很大程度上缓解了空间放大的问题。

当然在实际应用中会组合两种策略，比如经典的 RocksDB 会在 L0 合并到 L1 时，使用 Size-Tiered Compaction；而从 L1 开始，则是采用经典的 Leveled Compaction。这其中原因是 L0 的数据表之间肯定会存在相同的 key。

以上介绍了 LSM 树中经典的合并问题，那么在合并过程中常常面临各种困境，比如上文提到的空间放大问题。下面我为你介绍 RUM 假说，来详细分析此类问题。

RUM 假说

开始介绍这个假说之前，你要先明确几个“放大”概念。

1. 读放大。它来源于在读取时需要在多个文件中获取数据并解决数据冲突问题，如查询操作中所示的，读取的目标越多，对读取操作的影响越大，而合并操作可以有效缓解读放大问题。

2. 写放大。对于 LSM 树来说，写放大来源于持续的合并操作，特别是 Leveled Compaction，可以造成多层连续进行合并操作，这样会让写放大问题呈几何倍增长。

3. 空间放大。这是我在说合并的时候提到过的概念，是指相同 key 的数据被放置了多份，这是在合并操作中所产生的。尤其是 Size-Tiered Compaction 会有严重的空间放大问题。

那么我们可以同时解决以上三种问题吗？根据 RUM 的假说，答案是不能。

该假说总结了数据库系统优化的三个关键参数：读取开销（Read）、更新开销（Update）和内存开销（Memory），也就是 RUM。对应到上面三种放大，可以理解为 R 对应读放大、U 对应写放大，而 M 对应空间放大（Memory 可以理解为广义的存储，而不仅仅指代内存）。

该假说表明，为了优化上述两项的开销必然带来第三项开销的上涨，可谓鱼与熊掌不可兼得。而 LSM 树是用牺牲读取性能来尽可能换取写入性能和空间利用率，上面我已经详细阐明其写入高效的原理，此处不做过多说明。

而有的同学会发现，合并操作会带来空间放大的问题，理论上应该会浪费空间。但是 LSM 树由于其不可变性，可以引入块压缩，来优化空间占用使用，且内存不需要做预留（B 树需要额外预留内存来进行树更新操作），从而使其可以很好地优化空间。

你应该知道，RUM 所描述的内容过于简单，一些重要指标如延迟、维护性等没有涵盖其中，但是它可以作为我们工具箱里面的一个短小精干的扳手，来快速分析和掌握一个存储引擎的特点。

总结

至此，我们学习了一个典型的面向分布式数据库所使用的存储引擎。从其特点可以看到，它高速写入的特性对分布式数据库而言是有非常大吸引力的，同时其KV 结构更是分片所喜欢的一种数据格式，非常适合基于此构建分布式数据库。所以诸如 Apache Cassandra、ClickHouse 和 TiDB 等分布式数据库都选用 LSM 树或类似结构的存储引擎来构建分布式数据库。

教学相长

最后给你留一个思考题，除了 LSM 树以外，还有哪些基于日志的存储引擎呢？我会在第 12 讲给出答案。

感谢学习，希望你能每天强大一点。

---

10 事务处理与恢复（上）：数据库崩溃后如何保证数据不丢失？

上一讲我们探讨了一个典型的面向分布式数据库所使用的存储引擎——LSM 树。那么这一讲，我将为你介绍存储引擎的精华部分，也就是事务管理。首先我将从使用者角度，介绍事务的特性，也就是 ACID；而后简要说明存储引擎是通过什么组件来支持这些特性的。

为了保持这些特性，事务管理器需要考虑各种可能的问题与故障，如数据库进程崩溃、磁盘故障等。在面临各种故障时，如何保证 ACID 特性，我会在“数据库恢复”部分为你介绍。

由于这部分内容较多，我分成了上下两讲来向你讲述。下一讲我会接着介绍数据库的隔离级别与并发控制，它们是数据库提供给应用开发人员的礼物，可以让其非常轻易地实现并发数据的一致性。

以上就是这部分内容的学习脉络，现在让我们从事务的概述说起。

事务概述

事务管理是数据库中存储引擎的一个相当独立并且重要的组件，它可以保证对数据库的一系列操作看起来就像只有一步操作一样。这大大简化了面向数据库的应用的开发，特别是在高并发场景下，其意义更为重要。

一个典型的案例就是转账操作：从甲处转 100 元给乙。现实生活中，这个操作是原子的，因为纸币是不可复制的。但是在计算机系统内，这个操作实际上是由两个操作组成：甲账户减 100、乙账户加 100。两个操作就会面临风险，比如在转账的同时，丁又从甲处转走 100（此时甲给乙的 100 未扣除），而如果此时账户内钱不够，这两笔操作中的一笔可能会失败；又比如，两个操作过程中数据库崩溃，重启后发现甲的账户已经没了 100，而乙账户还没有增加，或者相反。

为了解决上面类似的问题，人们在数据库特别是存储引擎层面提出了事务的概念。下面我来说说事务的经典特性 ACID。

ACID

A：原子性

原子性保证了事务内的所有操作是不可分割的，也就是它们要么全部成功，要么全部失败，不存在部分成功的情况。成功的标志是在事务的最后会有提交（Commit）操作，它成功后会被认为整个事务成功。而失败会分成两种情况，一种是执行回滚（Rollback）操作，另一种就是数据库进程崩溃退出。

原子性是数据库提供给使用者的保证，是为了模拟现实原子操作，如上文提到的转账。在现实生活中，一些看似不可分割的操作转换为计算机操作却并不是单一操作。而原子性就是对现实生活中原子操作的保证。

C：一致性

一致性其实是受用户与数据库共同控制的，而不只是数据库提供的一个服务。它首先是一个业务层面的约束，比如开篇中的例子，甲向乙转 100 元。业务应用首先要保证在甲账户扣款 100 元，而且在乙账户增加 100 元，这个操作所带来的一致性与数据库是无关的。而数据库是通过 AID 来保证这两个正确的动作可以得到最终正确的结果。

这里的一致性与模块一中的分布式一致性有本质区别，想了解详细对比的同学，请移步到“05 | 一致性与 CAP 模型：为什么需要分布式一致性”，这里就不进行赘述了。

I：隔离性

事务的一个伟大之处是能处理并发操作，也就是不同的事务在运行的时候可以互相不干扰，就像没有别的事务发生一样。做并发编程的同学会对此深有体会，处理并发操作需要的精力与经验与处理串行操作完全不在一个等级上。而隔离性恰好能将实际上并发的操作，转化为从使用者角度看却是串行的，从而大大降低使用难度。

当然在实际案例中，以上描述的强并发控制性能会偏低。一般数据库会定义多种的隔离级别来提供不同等级的并发处理能力，也就是一个事务在较低隔离级别下很可能被其他事务看见。详细内容我会在“隔离级别”部分进行说明。

D：持久性

持久性比较简单，就是事务一旦被提交，那么它对数据库的修改就可以保留下来。这里要注意这个“保存下来”不仅仅意味着别的事务能查询到，更重要的是在数据库面临系统故障、进程崩溃等问题时，提交的数据在数据库恢复后，依然可以完整地读取出来。

以上就是事务的四种重要的特性，那么事务在存储引擎内部有哪些组件来满足上面的特性呢？我接下来要为你介绍的就是一个典型的事务管理组件。

事务管理器

事务主要由事务管理器来控制，它负责协调、调度和跟踪事务状态和每个执行步骤。当然这与分布式事务两阶段提交（2PC）中的事务管理器是不同的，关于分布式事务的内容我将在下一个模块详细介绍。

页缓存

关于事务管理器，首先要提到的就是页缓存（Page Cache）或者缓冲池（Buffer Pool），它是磁盘和存储引擎其他组件的一个中间层。数据首先被写入到缓存里，而后同步到数据磁盘上。它一般对于其他组件，特别是对于写入来说是透明的，写入组件以为是将数据写入磁盘，实际上是写入了缓存中。这个时候如果系统出现故障，数据就会有丢失的风险，故需要本讲后面“如何恢复事务”要介绍的手段来解决这个问题。

缓存首先解决了内存与磁盘之间的速度差，同时可以在不改变算法的情况下优化数据库的性能。但是，内存毕竟有限，不可能将磁盘中的所有数据进行缓存。这时候就需要进行刷盘来释放缓存，刷盘操作一般是异步周期性执行的，这样做的好处是不会阻塞正常的写入和读取。

刷盘时需要注意，脏页（被修改的页缓存）如果被其他对象引用，那么刷盘后不能马上释放空间，需要等到它没有引用的时候再从缓存中释放。刷盘操作同时需要与提交日志检查点进行配合，从而保证 D，也就是持久性。

当缓存到达一定阈值后，就不得不将有些旧的值从缓存中移除。这个时候就需要缓存淘汰算法来帮忙释放空间。这里有 FIFO、LRU、表盘（Clock）和 LFU 等算法，感兴趣的话你可以根据这几个关键词自行学习。

最后存在部分数据我们希望它们一直在缓存中，且不受淘汰算法的影响，这时候我们可以把它们“锁”（Pinned）在缓存里。比如 B 树的高节点，它们一般数据量不大，且每次查询都需要访问。还有一些经常访问的元数据也会长期保存在缓存中。

日志管理器

其次是日志管理器，它保存了一组数据的历史操作记录。缓存内的数据没有刷入磁盘前，系统就崩溃了，通过回放日志，缓存中的数据可以恢复出来。另外，在回滚场景，这些日志可以将修改前的数据恢复出来。

锁管理器

最后要介绍的就是非常重要的锁管理器，它保证了事务访问共享资源时不会打破这些资源的完整性约束。同时，它也可以保证事务可以串行执行。关于锁的内容我会在后面详细说明。

以上就是事务管理的主要组件，下面我将从数据库恢复事务的角度介绍日志管理相关内容。

数据库如何恢复事务

数据库系统是由一系列硬件和软件组成的复杂生态系统，其中每个组件都有产生各种稳定性问题的可能，且将它们组合为数据库系统后，这种可能被进一步放大了。而数据库的设计者必须为这种潜在的稳定性问题给出自己的解决方案，并使数据库作出某种“承诺”。

提交日志，即 CommitLog 或 WAL（Write-Ahead Log）就是应对此种问题的有效手段。这种日志记录了数据库的所有操作，并使用追加（Append）模式记录在磁盘的日志文件中。

上文中我们知道数据库的写操作首先是写入了缓存，而后再刷入磁盘中。但是在刷盘之前，其实这些数据已经以日志的形式保存在了磁盘的提交日志里面。当数据没有刷入磁盘而仅仅驻留在缓存时，这些日志可以保证数据的持久性。也就是，一旦数据库遭遇故障，可以从日志中恢复出来数据。

那么提交日志具有哪些特性来保障这些功能呢？下面来看一下日志的特性。

提交日志的特性

首先，提交日志非常类似于上一讲介绍的 LSM 树的磁盘文件特性，都是顺序写入且不可变。其益处也是相同的，顺序写保障了写入的高性能，不可变保证了读取可以安全地从前到后读取里面的数据。

提交日志一般都会被分配一个序列号作为唯一键，这个序号不是一个自增数字，就是一个时间戳。此外，每条日志都非常小，有些数据库会将它们进行缓存而后批量写入磁盘。这就导致，默写情况下日志不能完全恢复数据库，这是对于性能的考虑，大部分数据库会给出不同的参数来描述日志缓存刷盘的行为，用户可在性能与恢复数据完整性上作出平衡。

而事务在提交的时候，一定要保证其日志已经写入提交日志中。也就是事务内容完全写入日志是事务完成的一个非常重要的标志。

日志在理论上可以无限增长，但实际上没有意义。因为一旦数据从缓存中被刷入磁盘，该操作之前的日志就没有意义了，此时日志就可以被截断（Trim），从而释放空间。而这个被截断的点，我们一般称为检查点。检查点之前的页缓存中的脏页需要被完全刷入磁盘中。

日志在实现的时候，一般是由一组文件组成。日志在文件中顺序循环写入，如果一个文件中的数据都是检查点之前的旧数据，那么新日志就可以覆盖它们，从而避免新建文件的问题。同时，将不同文件放入不同磁盘，以提高日志系统的可用性。

物理日志 Redo Log 与逻辑日志 Undo Log

事务对数据的修改其实是一种状态的改变，比如将 3 改为 5。这里我们将 3 称为前镜像（before-image），而 5 称为后镜像（after-image）。我们可以得到如下公式：

1. 前镜像+redo log=后镜像

2. 后镜像+undo log=前镜像

redo log 存储了页面和数据变化的所有历史记录，我们称它为物理日志。而 undo log 需要一个原始状态，同时包含相对这个状态的操作，所以又被称为逻辑日志。我们使用 redo 和 undo 就可以将数据向前或向后进行转换，这其实就是事务操作算法的基础。

Steal 与 Force 策略

redo 和 undo 有两种写入策略：steal 和 force。

steal 策略是说允许将事务中未提交的缓存数据写入数据库，而 no-steal 则是不能。可以看到如果是 steal 模式，说明数据从后镜像转变为前镜像了，这就需要 undo log 配合，将被覆盖的数据写入 undo log，以备事务回滚的时候恢复数据，从而可以恢复到前镜像状态。

force 策略是说事务提交的时候，需要将所有操作进行刷盘，而 no-force 则不需要。可以看到如果是 no-force，数据在磁盘上还是前镜像状态。这就需要 redo log 来配合，以备在系统出现故障后，从 redo log 里面恢复缓存中的数据，从而能转变为后镜像状态。

从上可知，当代数据库存储引擎大部分都有 undo log 和 redo log，那么它们就是 steal/no-force 策略的数据库。

下面再来说一个算法。

ARIES 数据恢复算法

这个算法全称为 Algorithm for Recovery and Isolation Exploiting Semantics。

该算法同时使用 undo log 和 redo log 来完成数据库故障崩溃后的恢复工作，其处理流程分为如下三个步骤。

1. 首先数据库重新启动后，进入分析模式。检查崩溃时数据库的脏页情况，用来识别需要从 redo 的什么位置开始恢复数据。同时搜集 undo 的信息去回滚未完成的事务。

2. 进入执行 redo 的阶段。该过程通过 redo log 的回放，将在页缓存中但是没有持久化到磁盘的数据恢复出来。这里注意，除了恢复了已提交的数据，一部分未提交的数据也恢复出来了。

3. 进入执行 undo 的阶段。这个阶段会回滚所有在上一阶段被恢复的未提交事务。为了防止该阶段执行时数据库再次崩溃，存储引擎会记录下已执行的 undo 操作，防止它们重复被执行。

ARIES 算法虽然被提出多年，但其概念和执行过程依然在现代存储引擎中扮演着重要作用。

以上我们讲解了数据库如何恢复数据，保持一致性状态。它对应着 AID（C 如前文所示，是一种约束，一般不认为是数据库提供的功能）中的 AD。同时我们也要知道以提交日志为代表的数据库恢复技术，在没有事务概念的数据库中也扮演着重要的作用，因为页缓存是无处不在的，解决主存掉电丢失数据的问题，是提交日志的主要功能。

总结

那么这一讲就介绍到这了。我们从 ACID 原理出发，介绍了管理事务的众多组件，而后重点介绍了如何保证数据的持久性，这主要通过提交日志来实现。其余有关隔离性的概念，我将会在下一讲接着介绍。

教学相长

依然留给你一道思考题：有没有不使用日志方式来恢复数据库的方案呢？

欢迎你在评论区留言，我们一起探讨，一起进步，下一讲再见。

---

11 事务处理与恢复（下）：如何控制并发事务？

上一讲，我们介绍了事务的基本概念和数据库恢复流程，其中涉及了事务持久性是如何保证的，那么这一讲，我们就重点介绍事务的隔离性。

数据库最强的隔离级别是序列化，它保证从事务的角度看自己是独占了所有资源的。但序列化性能较差，因此我们引入了多种隔离界别来提高性能。在本讲的最后我会介绍分布式数据库中常用的并发控制手段，它们是实现隔离级别的有效方案，其中以多版本方式实现快照隔离最为常见。

现在让我们开始今天的内容。

隔离级别

在谈隔离级别之前，我们先聊聊“序列化”（Serializability）的概念。

序列化的概念与事务调度（Schedule）密切相关。一个调度包含该事务的全部操作。我们可以用 CPU 调度理论来类比，当一个事务被调度后，它可以访问数据库系统的全部资源，同时会假设没有其他事务去影响数据库的状态。这就类似于一个进程被 CPU 调度，从而独占该 CPU 资源（这里的 CPU 指的是时分系统）。但是实际设计调度时，会允许调度事务内部的操作被重新排序，使它们可以并行执行。这些都是优化操作，但只要不违反 ACID 的原则和结果的正确性就可以了。

那什么是序列化呢？如果一个调度被说成是序列化的，指的是它与其他调度之间的关系：在该调度执行时没有其他被调度的事务并行执行。也就是说，调度是一个接着一个顺序执行的，前一个调度成功完成后，另一个调度再执行。这种方法的一个好处是执行结果比较好预测。但是，我们发现这种做法有明显的缺陷：性能太低。在实现时，一个序列化调度可能会并行执行多个事务操作，但是会保证这样与一个个顺序执行调度有相同的结果。

以上就是序列化的概念，它揭示了序列化也会存在并发执行的情况。这一点很重要，在隔离理论中，一个隔离概念只是描述了一种行为，而在实现层面可以有多种选择，只要保证这个行为的结果符合必要条件就没有问题了。

序列化是最强的事务隔离级别，它是非常完美的隔离状态，可以让并行运行的事务感知不到对方的存在，从而安心地进行自己的操作。但在实现数据库事务时，序列化存在实现难度大、性能差等问题。故数据库理论家提出了隔离级别的概念，用来进行不同程度的妥协。在详解隔离级别之前，来看看我们到底可以“妥协”什么。

这些“妥协”被称为读写异常（Anomalies）。读异常是大家比较熟悉的，有“脏读”“不可重读”和“幻读”。写异常不太为大家所知，分别是“丢失更新”“脏写”和“写偏序”。读异常和写异常是分别站在使用者和数据本身这两个角度去观察隔离性的，我们将成对介绍它们。传统上隔离级别是从读异常角度描述的，但是最近几年，一些论文也从写异常角度出发，希望你能明白两种表述方式之间是有联系的。下表就是经典隔离级别与读异常的关系。

从中可以看到序列化是不允许任何读写异常存在的。

可重读允许幻读的产生。幻读是事务里面读取一组数据后，再次读取这组数据会发现它们可能已经被修改了。幻读对应的写异常是写偏序。写偏序从写入角度发现，事务内读取一批数据进行修改，由于幻读的存在，造成最终修改的结果从整体上看违背了数据一致性约束。

读到已提交在可重读基础上放弃了不可重读。与幻读类似，但不可重读针对的是一条数据。也就是只读取一条数据，而后在同一个事务内，再读取它数据就变化了。

刚接触这个概念的同学可能会感觉匪夷所思，两者只相差一个数据量，就出现了两个隔离级别。这背后的原因是保证一条数据的难度要远远低于多条，也就是划分这两个级别，主要的考虑是背后的原理问题。而这个原理又牵扯出了性能与代价的问题。因此就像我在本专栏中反复阐述的一样，一些理论概念有其背后深刻的思考，你需要理解背后原理才能明白其中的奥义。不过不用担心，后面我会详细阐述它们之间实现的差别。

而不可重读对应的是丢失更新，与写偏序类似，丢失更新是多个事务操作一条数据造成的。

最低的隔离级别就是读到未提交，它允许脏读的产生。脏读比较简单，它描述了事务可以读到其他事务为提交的数据，我们可以理解为完全没有隔离性。而脏读本身也会造成写异常：脏写。脏写就是由于读到未提交的数据而造成的写异常。

以上，我们详细阐述了经典的隔离级别。但是这套理论是非常古早的，较新的 MVCC 多版本技术所带来的快照隔离又为传统隔离级别增添一个灵活选型。它可以被理解为可重读隔离级别，也就是不允许不可重读。但是在可重读隔离下，是可以保证读取不到数据被修改的。但快照隔离的行为是：一旦读到曾经读过的数据被修改，将立即终止当前事务，也就是进行回滚操作。在多并发事务下，也就是只有一个会成功。你可以细细品味两者的差异。

快照隔离可以解决丢失更新的问题，因为针对同一条数据可以做快照检测，从而发现数据被修改，但是不能防止写偏序的问题。

快照隔离是现代分布式数据库存储引擎最常使用的隔离级别，而解决写偏序问题，也是存储引擎在该隔离级别下需要解决的问题。SSI（Serializable Snaphost Isoltion）正是解决这个问题的方案，我会在“18 | 分布式事务：‘老大难’问题的最新研究与实践”中详细介绍该方案。

至此我们讨论了典型的隔离级别，隔离级别与分布式一致性的关系我在“05 | 一致性与 CAP 模型：为什么需要分布式一致性”中已经有过阐述，如果需要复习，请出门左转。现在让我们接着讨论如何实现这些隔离级别。

并发控制

目前存储引擎引入多种并发模型来实现上面提到的隔离级别，不同的模式对实现不同的级别是有偏好的，虽然理论上每种控制模型都可以实现所有级别。下面我就从乐观与悲观、多版本、基于锁的控制三个方面进行介绍。

乐观与悲观

乐观与悲观的概念类似于并发编程中的乐观锁与悲观锁。但是这里你要注意，实现它们并不一定要借助锁管理。

乐观控制使用的场景是并行事务不太多的情况，也就是只需要很少的时间来解决冲突。那么在这种情况下，就可以使用一些冲突解决手段来实现隔离级别。最常用的方案是进行提交前冲突检查。

冲突检查有多种实现模式，比如最常用的多版本模式。而另一种古老的模式需要检查并行事务直接操作的数据，也就是观察它们操作的数据是否有重合。由于其性能非常差，已经很少出现在现代存储引擎中了。这里需要你注意的是，乐观控制不一定就是多版本这一种实现，还有其他更多的选择。

同样的，悲观控制也不仅仅只有锁这一种方案。一种可能的无锁实现是首先设置两个全局时间戳，最大读取时间与最大写入时间。如果一个读取操作发生的时间小于最大写入时间，那么该操作所在的事务被认为应该终止，因为读到的很可能是旧数据。而一个写操作如果小于最大读取时间，也被认为是异常操作，因为刚刚已经有读取操作发生了，当前事务就不能去修改数据了。而这两个值是随着写入和读取操作而更新的。这个悲观控制被称为 Thomas Write Rule，对此有兴趣的话你可以自行搜索学习。

虽然乐观与悲观分别有多种实现方案，但乐观控制最为常见的实现是多版本控制，而悲观控制最常见的就是锁控制。下面我就详细介绍它们。

多版本

多版本并发控制（MVCC，Multiversion concurrency control）是一种实现乐观控制的经典模式。它将每行数据设置一个版本号，且使用一个单调递增的版本号生成器来产生这些版本号，从而保证每条记录的版本号是唯一的。同时给每个事物分为一个 ID 或时间戳，从而保证读取操作可以读到事务提交之前的旧值。

MVCC 需要区分提交版本与未提交版本。最近一次提交的版本被认为是当前版本，从而可以被所有事务读取出来。而根据隔离级别的不同，读取操作能或者不能读取到未提交的版本。

使用 MVCC 最经典的用法是实现快照隔离。事务开始的时候，记录当前时间，而后该事务内所有的读取操作只能读到当前提交版本小于事务开始时间的数据，而未提交的数据和提交版本大于事务开始时间点的数据是不能读取出来的。如果事务读取的数据已经被其他事务修改，那么该数据应该在上一讲提到的 undo log 中，当前事务还是能够读取到这份数据的。故 undo log 的数据不能在事务提交的时候就清除掉，因为很可能有另外的事务正在读取它。

而当事务提交的时候，数据其实已经写入完成。只需要将版本状态从未提交版本改为提交版本即可。所以 MVCC 中的提交操作是非常快的，这点会对分布式事务有很多启示。

而上文提到的 SSI 模式可以在 MVCC 的基础上引入冲突解决机制，从而解决写偏序问题。当提交发生的时候，事务会检测其修改和读取的数据在提交之前是否已经被其他已提交事务修改了，如果是，则会终止当前事务，并进行回滚。同时这个冲突检测时机会有两个：一个是在事务内进行读取操作时就进行检测，称为前向检测（forward）。而相对的，在提交时进行检测被称为后向检测（backward）。你会明显感觉到，前者会快速失败，但是性能较低；而后者对异常的反应较慢，但速度会有优势。

这就是经典的 MVCC 并发控制，现在让我接着介绍典型的悲观控制：锁控制。

基于锁的控制

基于锁的控制是典型的悲观控制。它会使用显示的锁来控制共享资源，而不是通过调度手段来实现。锁控制可以很容易实现“序列化操作”，但是它同时存在锁竞争和难扩展等问题。

一个比较知名的锁技术是两阶段锁（2PL），它将锁操作总结为两个阶段。

1. 锁膨胀阶段。在该过程中，事务逐步获得所有它需要的锁，同时不释放任何锁。这期间事务可以对加锁的数据进行操作。

2. 锁收缩阶段。该过程中，在上一过程中获得的锁全部被释放。这个事务是逐步的，这期间事务依然可以对还持有锁的数据进行操作。

以上过程简单明了，它是针对一次性加锁提出来的，一次性加锁的缺点是没有并发度，性能低；而两阶段锁可以保证一定的并发度，但其缺点是会有死锁的产生。

死锁是两个事务互相持有对方的锁，从而造成它们都无法继续运行。解决死锁需要引入超时机制，但超时机制又有明显的性能缺憾。此时，人们会引入死锁检测机制来尽早发现死锁。一般实现手段是将所有事务的锁依赖构建成一棵依赖图，而后使用图算法来发现其中的环形死锁结构，从而快速判断死锁的产生。

而与锁相对的一个概念就是“闩”（latch，读“shuān”）。一般资料说闩是轻量的，锁是重量的，这其实体现在两个方面。

一是说它们处理的对象。闩一般用在粒度很小的数据中，比如数据块、索引树的节点等。而锁一般作用在大颗粒操作，如锁定多行数据、事务和修改存储结构等。

二是它们本身的实现不同。闩一般使用 CAS 执行，是基于比较而后设置的无锁指令级别的操作。如果原始值发生变化就重新进行以上操作，这个过程叫自旋（spin）。而锁是使用独立的资源，且有锁管理器来控制。可想而知，调度锁也是一个比较耗时且复杂的过程。

这里就要解释上文中隔离级别“序列化”和“可重读”之间实现的差异了。“序列化”由于要保证一组数据重复读取的一致性，就需要引入重量级的锁，其代价是很高的；而“可重读”只需要保证一行数据重复读取是一致的，它可以使用轻量级的闩来实现。故隔离级别将它们分成两种是非常合理的，因为从原理看，它们是完全不同的。

以上就是关于基于锁的控制的相关内容。

总结

本讲内容就介绍到这里了。事务是我们课程到目前为止最长的内容，用了两讲的篇幅来详细介绍。事务的话题在数据库领域一直很热门，我从事务原理层面切入，解释了 ACID 和不同隔离级别所需要的技术手段。这些内容为分布式事务的学习打下坚实的基础，同时你可以将本专栏作为一份参考资料，随时进行查阅。

从本质出发，事务是一个面向使用者的概念，它向使用者提供一种契约，目的是使人们可以可靠地使用数据库保存和共享数据，这是数据库最核心的功能，且有众多的应用是基于该功能构建的，这也是分布式数据库为什么要实现分布式条件下的事务的根本原因。

好了，今天学习就到这里。下一讲，又是一节拓展课，我会为你解读当前流行的分布式存储引擎。到时候见。

---

12 引擎拓展：解读当前流行的分布式存储引擎

这一讲是存储引擎模块的最后一讲，通过这一个模块的学习，相信你已经对存储引擎的概念、使用方法与技术细节有了全方位的认识。本讲我们先总结一下模块二的主要内容，并回答大家提到的一些典型问题；而后我会介绍评估存储引擎的三个重要元素；最后为你介绍目前比较流行的面向分布式数据库的存储引擎。

让我们先进行本模块的内容回顾。

存储引擎回顾

存储引擎是数据库的核心组件，起到了物理模型与逻辑模型之间的沟通作用，是数据库重要功能，是数据写入、查询执行、高可用和事务等操作的主要承担者。可谓理解存储引擎也就掌握了数据库的主要功能。

在这个模块里，我首先向你介绍了存储引擎在整个数据库中的定位，点明了它其实是本地执行模块的组成部分；而后通过内存与磁盘、行式与列式等几组概念的对比，介绍了不同种类的存储引擎的实现差异；并最终说明了分布式数据库存储引擎的特点，即面向内存、列式和易于散列。

在第 8 讲中，我介绍了分布式数据库的索引。着重说明了存储引擎中大部分数据文件其实都是索引结构；而后带着你一起探讨了典型分布式数据库存储引擎的读取路径，并介绍了该路径上的一些典型技术，如索引数据表、内存跳表、布隆过滤和二级索引等。

接着我介绍了一个在分布式数据库领域内非常流行的存储引擎：LSM 树。介绍了其具体的结构、读写修改等操作流程；重点说明了合并操作，它是 LSM 树的核心操作，直接影响其性能；最后介绍了 RUM 假说，它是数据库优化的一个经典取舍定律。

最后，我们探讨了存储引擎最精华的概念，就是事务。我用了两讲的篇幅，详细为你阐述事务的方方面面。总结一下，事务其实是数据库给使用者的一个承诺，即 ACID。为了完成这个承诺，数据库动用了存储引擎中众多的功能模块。其中最重要的事务管理器，同时还需要页缓存、提交日志和锁管理器等组件来进行配合。故在实现层面上，事务的面貌是很模糊的，它同时具备故障恢复和并发控制等特性，这是由其概念是建立在最终使用侧而造成的。

事务部分我们主要抓住两点：故障恢复+隔离级别。前者保证了数据库存储数据不会丢失，后者保证并发读写数据时的完整性；同时我们要将事务与模块一中的分布式一致性做区别，详细内容请你回顾第 5 讲。

在事务部分，有同学提到了下面这个问题，现在我来为你解答。

当内存数据刷入磁盘后，同时需要对日志做“截取”操作，这个截取的值是什么？

这个“截取”是一个形象的说法，也就是可以理解为截取点之前的数据已经在输入磁盘中。当进行数据库恢复的时候，只要从截取点开始恢复数据库即可，这样大大加快了恢复速度，同时也释放了日志的空间。这个截取点，一般被称为检查点。相关细节，你可以自行学习。

以上我们简要回顾了本模块的基本知识。接下来，我将带你领略当代分布式数据库存储引擎的一些风采。但是开始介绍之前，我们需要使用一个模型来评估它们的特点。

评估存储引擎的黄金三角

存储引擎的特点千差万别，各具特色。但总体上我们可以通过三个变量来描述它们的行为：缓存的使用方式，数据是可变的还是不可变的，存储的数据是有顺序的还是没有顺序的。

缓存形式

缓存是说存储引擎在数据写入的时候，首先将它们写入到内存的一个片段，目的是进行数据汇聚，而后再写入磁盘中。这个小片段由一系列块组成，块是写入磁盘的最小单位。理想状态是写入磁盘的块是满块，这样的效率最高。

大部分存储引擎都会使用到缓存。但使用它的方式却很不相同，比如我将要介绍的 WiredTiger 缓存 B 树节点，用内存来抵消随机读写的性能问题。而我们介绍的 LSM 树是用缓存构建一个有顺序的不可变结构。故使用缓存的模式是衡量存储引擎的一个重要指标。

可变/不可变数据

存储的数据是可变的还是不可变的，这是判断存储引擎特点的另一个维度。不可变性一般都是以追加日志的形式存在的，其特点是写入高效；而可变数据，以经典 B 树为代表，强调的是读取性能。故一般认为可变性是区分 B 树与 LSM 树的重要指标。但 BW-Tree 这种 B 树的变种结构虽然结构上吸收了 B 树的特点，但数据文件是不可变的。

当然不可变数据并不是说数据一直是不变的，而是强调了是否在最影响性能的写入场景中是否可变。LSM 树的合并操作，就是在不阻塞读写的情况下，进行数据文件的合并与分割操作，在此过程中一些数据会被删除。

排序

最后一个变量就是数据存储的时候是否进行排序。排序的好处是对范围扫描非常友好，可以实现 between 类的数据操作。同时范围扫描也是实现二级索引、数据分类等特性的有效武器。如本模块介绍的 LSM 树和 B+ 树都是支持数据排序的。

而不排序一般是一种对于写入的优化。可以想到，如果数据是按照写入的顺序直接存储在磁盘上，不需要进行重排序，那么其写入性能会很好，下面我们要介绍的 WiscKey 和 Bitcask 的写入都是直接追加到文件末尾，而不进行排序的。

以上就是评估存储引擎特点的三个变量，我这里将它们称为黄金三角。因为它们是互相独立的，彼此并不重叠，故可以方便地评估存储引擎的特点。下面我们就试着使用这组黄金三角来评估目前流行的存储引擎的特点。

B 树类

上文我们提到过评估存储引擎的一个重要指标就是数据是否可以被修改，而 B 树就是可以修改类存储引擎比较典型的一个代表。它是目前的分布式数据库，乃至于一般数据库最常采用的数据结构。它是为了解决搜索树（BST）等结构在 HDD 磁盘上性能差而产生的，结构特点是高度很低，宽度很宽。检索的时候从上到下查找次数较少，甚至如 B+ 树那样，可以完全把非叶子节点加载到内存中，从而使查找最多只进行一次磁盘操作。

下面让我介绍几种典型的 B 树结构的存储引擎。

InnoDB

InnoDB 是目前 MySQL 的默认存储引擎，同时也是 MariaDB 10.2 之后的默认存储引擎。

根据上文的评估指标看，它的 B+ 树节点是可变的，且叶子节点保存的数据是经过排序的。同时由于数据的持续写入，在高度不变的情况下，这个 B+ 树一定会横向发展，从而使原有的一个节点分裂为多个节点。而 InnoDB 使用缓存的模式就是：为这种分裂预留一部分内存页面，用来容纳可能的节点分裂。

这种预留的空间其实就是一种浪费，是空间放大的一种表现。用 RUM 假设来解释，InnoDB 这种结构是牺牲了空间来获取对于读写的优化。

在事务层面，InnoDB 实现了完整的隔离级别，通过 MVCC 机制配合各种悲观锁机制来实现不同级别的隔离性。

WiredTiger

WiredTiger 是 MongoDB 默认的存储引擎。它解决了原有 MongoDB 必须将大部分数据放在内存中，当内存出现压力后，数据库性能急剧下降的问题。

它采用的是 B 树结构，而不是 InnoDB 的 B+ 树结构。这个原因主要是 MongoDB 是文档型数据库，采用内聚的形式存储数据（你可以理解为在关系型数据库上增加了扩展列）。故这种数据库很少进行 join 操作，不需要范围扫描且一次访问就可以获得全部数据。而 B 树每个层级上都有数据，虽然查询性能不稳定，但总体平均性能是要好于 B+ 树的。

故 WiredTiger 首先是可变数据结构，同时由于不进行顺序扫描操作，数据也不是排序的。那么它是如何运用缓存的呢？这个部分与 InnoDB 就有区别了。

在缓存中每个树节点上，都配合一个更新缓冲，是用跳表实现的。当进行插入和更新操作时，这些数据写入缓冲内，而不直接修改节点。这样做的好处是，跳表这种结构不需要预留额外的空间，且并发性能较好。在刷盘时，跳表内的数据和节点页面一起被合并到磁盘上。

由此可见，WiredTiger 牺牲了一定的查询性能来换取空间利用率和写入性能。因为查询的时候出来读取页面数据外，还要合并跳表内的数据后才能获取最新的数据。

BW-Tree

BW-Tree 是微软的 Azure Cosmos DB 背后的主要技术栈。它其实通过软件与硬件结合来实现高性能的类 B 树结构，硬件部分的优化使用 Llama 存储系统，有兴趣的话你可以自行搜索学习。我们重点关注数据结构方面的优化。

BW-Tree 为每个节点配置了一个页面 ID，而后该节点的所有操作被转换为如 LSM 树那样的顺序写过程，也就是写入和删除操作都是通过日志操作来完成的。采用这种结构很好地解决了 B 树的写放大和空间放大问题。同时由于存在多个小的日志，并发性也得到了改善。

刷盘时，从日志刷入磁盘，将随机写变为了顺序写，同样提高了刷盘效率。我们会发现，BW-Tree 也如 LSM 树一样存在读放大问题，即查询时需要将基础数据与日志数据进行合并。而且如果日志太长，会导致读取缓慢。而此时 Cosmos 采用了一种硬件的解决方案，它会感知同一个日志文件中需要进行合并的部分，将它们安排在同一个处理节点，从而加快日志的收敛过程。

以上就是典型的三种 B 树类的存储引擎，它们各具特色，对于同一个问题的优化方式也带给我们很多启发。

LSM 类

这个模块我专门用了一个完整篇章来阐述它的特点，它是典型的不可变数据结构，使用缓存也是通过将随机写转为顺序写来实现的。

我们在说 LSM 树时介绍了它存储的数据是有顺序的，其实目前有两种无顺序的结构也越来越受到重视。

经典存储

经典的 LSM 实现有 LeveledDB，和在其基础之上发展出来的 RocksDB。它们的特点我们之前有介绍过，也就是使用缓存来将随机写转换为顺序写，而后生成排序且不可变的数据。它对写入和空间友好，但是牺牲了读取性能。

Bitcask

Bitcask 是分布式键值数据库 Riak 的一种存储引擎，它也是一种典型的无顺序存储结构。与前面介绍的典型 LSM 树有本质上的不同，它没有内存表结构，也就是它根本不进行缓存而是直接将数据写到数据文件之中。

可以看到，其写入是非常高效的，内存占用也很小。但是如何查询这种“堆”结构的数据呢？答案是在内存中有一个叫作 Keydir 的结构保存了指向数据最新版本的引用，旧数据依然在数据文件中，但是没有被 Keydir 引用，最终就会被垃圾收集器删除掉。Keydir 实际上是一个哈希表，在数据库启动时，从数据文件中构建出来。

这种查询很明显改善了 LSM 树的读放大问题，因为每条数据只有一个磁盘文件引用，且没有缓存数据，故只需要查询一个位置就可以将数据查询出来。但其缺陷同样明显：不支持范围查找，且启动时，如果数据量很大，启动时间会比较长。

此种结构优化了写入、空间以及对单条数据的查找，但牺牲了范围查找的功能。

WiscKey

那么有没有一种结构，既能利用无顺序带来的高速写入和空间利用率上的优点，又可以支持非常有用的范围查询呢？WiscKey 结构正是尝试解决这个问题的一个手段。

它的特点是将 Key 和 Value 分别放在两个文件中。Key 还是按照 LSM 树的形式，这样就保证了 Key 是有顺序的，可以进行范围扫描。同时使用 LSM 树，即不需要将所有的 Key 放到内存里，这样也解决了 Bitcask 加载慢的问题。

而 Value 部分称为 vLogs（value Logs），其中的数据是没有顺序的。这种结构适合更新和删除比较少的场景，因为范围扫描会使用随机读，如果更新删除很多，那么其冲突合并的效率很低。同时在合并操作的时候，需要扫描 Key 而后确定合并方案，这个在普通的 LSM 树中也是不存在的。

WiscKey 非常适合在 SSD 进行运行，因为读取 Value 需要进行随机读取。目前 dgraph.io 的 Badger 是该模式比较成熟的实现。

总结

到这里，这一讲内容就说完了。我带你回顾了第二模块的主要内容，这是一个基础知识普及模块，将为接下来的分布式模块打下基础。同时相对于传统关系型数据库，分布式数据库的存储引擎也有其自身特点，如 LSM 树结构，你需要认真掌握这种结构。

从下一讲开始，我们将进入分布式数据库的核心内容：分布式系统。掌握分布式系统后，我们才可以说对分布式数据库有了比较完整的认识。

---