数据库系统内幕

本书旨在指导开发者理解现代数据库和存储引擎背后的内部概念，包含从众多书籍、论文、博客和多个开源数据库源代码中精心选取的相关材料。本书深入介绍了数据存储、数据构建块、分布式系统和数据集群，并且指出了现代数据库之间最重要的区别在于决定存储结构和数据分布的子系统。本书分为两部分：第一部分讨论节点本地的进程，并关注数据库系统的核心组件——存储引擎，以及最重要的一个特有元素；第二部分探讨如何将多个节点组织到一个数据库集群中。本书主要面向数据库开发人员，以及使用数据库系统构建软件的人员，如软件开发人员、运维工程师、架构师和工程技术经理。

作者简介

Alex Petrov是一位数据基础架构工程师，数据库和存储系统的狂热爱好者，Apache Cassandra 提交者和PMC成员，精通存储、分布式系统和算法。

译者简介

黄鹏程 毕业于北京邮电大学，过去八年一直专注于数据库和大数据平台研发与架构工作。毕业后就职于中国民生银行，历任软件工程师及大数据基础架构团队负责人，目前为阿里云高级产品专家，负责阿里云数据库相关产品的设计与规划工作。你可以通过搜索“gnuhpc”在LinkedIn或者微信上找到他。

傅宇 毕业于南京大学计算机系，专注于数据库技术，现任阿里云技术专家，担任 PolarDB-X 分布式关系型数据库内核研发工作，在分布式事务、查询优化器、执行器等方向略有经验，对数据库和大数据领域充满热情。个人博客：https://ericfu.me，知乎账号 Eric Fu，欢迎与我交流！

张晨 毕业于上海交通大学。大数据、数据库、分布式系统和函数式编程爱好者。现于Indeed东京担任软件工程师一职。你可以通过 我的个人主页chasezhang.me了解更多信息。

适读人群 ：数据库系统工程师、开发工程师、运维工程师、存储工程师及其他相关从业人员

本书从数据库开发者角度，对现代数据库技术进行了全景式解读，完全不拘泥于任何一款数据库系统，也不偏袒任何一种数据库的类型或特性。这本书只会讨论现代数据库必不可少的那些东西，例如存储格式、索引数据结构、数据一致性等，以及相关的许多选项与权衡。第一部分从单机的角度，介绍磁盘存储格式、索引数据结构、事务处理等，第二部分则以分布式系统切入，讲解分布式数据库的多副本、分布式事务、一致性等问题。书中内容的选材紧跟业内前沿进展，不仅有提及各种新兴的数据库产品，还有涉及许多来自学术界前沿的研究成果。不论你是一名有志于从事云计算领域的开发者，深入的研究数据库系统的设计与实现，还是作为一名开发者，即将使用云数据库以及云原生数据库，阅读本书都会大有裨益。

分布式数据库系统是大多数企业和绝大多数应用程序不可或缺的一部分。这些应用程序提供业务逻辑和用户界面，而数据库系统则负责确保数据的完整性、一致性和冗余性。

回到2000年，那时如果你要选择一个数据库，则只有少数几个选项，而且其中大部分都属于关系型数据库，因此它们之间的差异相对较小。当然，这并不是说所有数据库都是完全相同的，只是它们的功能和使用场景都非常相似。

其中一些数据库专注于水平扩展（scale out），即通过运行多个数据库实例（表现得像是一个单一逻辑单元）来提高性能并增加容量，例如：Gamma数据库机器项目、Teradata、Greenplum、Parallel DB2等。如今，水平扩展仍然是客户期望的最重要的数据库特性之一，云服务的日益普及诠释了这一点。相较于将数据库迁移至更大型、功能更强大的计算机进行垂直扩展（scale up），启动一个新实例并将其添加到集群中通常要容易得多。因为迁移可能会耗时冗长且令人痛苦不堪，还可能会导致停机。

在2010年左右，一类新型的最终一致性数据库开始逐步涌现，并且一些诸如NoSQL、大数据等术语也日益流行。在过去的15年间，开源社区、大型互联网公司和数据库供应商构建了众多的数据库和工具，以至于当人们在试图理解它们的使用场景、细节和规范时很容易迷失方向。

Amazon团队于2007年发布的Dynamo论文[DECANDIA07]对数据库社区产生了相当巨大的影响，在短时间内它便激发出了许多变体和实现。其中最突出的是诞生于Facebook的Apache Cassandra、LinkedIn研发的Voldemort，以及由前Akamai工程师研发的Riak。

如今，该领域再次发生了变化：在键值存储、NoSQL和最终一致性数据库之后，我们开始看到一些可扩展性更强、性能更高的数据库，它们能够在保证具有更强一致性的同时执行复杂的查询。

本书的受众

在技术会议的交流中，我经常听到同样的问题：“如何更多地了解有关数据库内部的原理？我甚至不知道从哪里开始。”关于数据库系统的大多数书籍都没有详细介绍存储引擎的实现，并且只是在较高的层次上介绍了访问方法，例如B树。很少有书籍涵盖较新的概念，例如不同的B树变体和日志结构存储（log-structured storage），因此我通常建议直接阅读论文。

但是每个读过论文的人都知道这并不容易：时常缺乏上下文，措辞可能含糊不清，论文之间甚至几乎根本没有联系，论文本身也不容易找到。本书简要总结了重要的数据库系统概念，并可以为希望深入研究的人们提供指南，也可以为已经熟悉这些概念的人们提供备忘单。

并非每个人都希望成为数据库开发者，但是本书也将为使用数据库系统构建软件的人员提供帮助，如：软件开发者、运维工程师、架构师和工程技术经理。

如果你的公司依赖于任何基础架构组件，无论是数据库、消息队列、容器平台还是任务调度器，你都必须通过阅读项目变更日志（change-log）和邮件列表来与社区保持联系、同步项目的最新进展。理解术语并了解其中的工作原理将使你能够从这些信息来源中获取更多信息，并可以更高效地使用工具来进行故障诊断，识别和避免潜在的风险与瓶颈。如果系统出现了某些问题，那么对数据库系统的工作原理有一个全面和基本的了解将会对你有所帮助。利用这些知识，在面对问题时，你将有能力提出假设、进行验证、找到根本原因，并将其讲解给其他项目成员。

本书也适合那些具备好奇心的人：喜欢学习一些不急用的知识的人，将空闲时间花在捣鼓一些有趣事情上的人。他们有的自己编写编译器，有的编写自用的操作系统、文本编辑器、电脑游戏，有的学习编程语言—他们乐于获取新知识。

本书假设读者具有一些开发后端系统和以用户身份使用数据库系统的经验。同时，具备一些不同种类数据结构的知识将有助于更快地吸收书中的知识。

为什么应该阅读本书

我们经常听到人们用他们实现的概念和算法来描述数据库系统：“该数据库使用Gossip来进行成员资格的传播”（参见第12章）、“他们已经实现了Dynamo”或“这就像他们在Spanner论文中描述的一样”（参见第13章）。抑或，如果你正在讨论算法和数据结构，那么你会听到类似于“ZAB和Raft有很多共同点”（参见第14章）、“Bw树就像是在日志结构化存储上实现的B树一样”（参见第6章）或“它们使用的是类似于Blink树中的同级指针”（参见第5章）的描述。

我们需要使用抽象来讨论复杂的概念，但是我们不能在每次开启一场对话时都讨论抽象术语。以白话的形式来掌握这些抽象概念是一个捷径，这能帮助我们将注意力转移到其他更高层次的问题上。

学习基本概念、证明和算法的一个优点是它们永不过时。当然，总会有新的东西出现，但是新算法往往是在发现经典算法的缺陷或改进空间之后才被创造出来的。了解历史有助于更好地理解这些算法之间的差异和它们的发明动机。

学习这些内容是鼓舞人心的。你将看到各种各样的算法，了解我们的工业界是如何一个接一个地解决问题的，并开始欣赏数据系统。同时，学习这些是有回报的：你几乎可以感觉到多个拼图碎片在脑海中移动到一起，最终形成一幅完整的图画，并且你将总是能够与他人分享这幅图画。

本书的范畴

本书既不是关于关系型数据库的书，也不是关于NoSQL的书，而是关于在各种数据库系统中使用的算法和概念的书，且重点是存储引擎和负责数据分布的组件。

诸如查询计划、查询优化、调度、关系模型等概念，在一些优秀的数据库系统教科书中已均有涉及。这些概念中的一部分通常是从用户的角度进行描述的，而本书则着重于内部结构。你可以在第二部分的总结和每章的小结中找到一些有用文献的推荐。这些文献应该能回答很多与数据库相关的问题。

由于本书中提到的数据库系统之间没有一种通用的查询语言，所以本书将不讨论查询语言。

为了收集本书的材料，我研究了15本书、300多篇论文、无数的博客文章、源代码以及几个开源数据库的文档。对于是否要在书中包含某个特定概念的原则，我常常会问自己这样一个问题：“数据库工业界和学术界的人都在谈论这个概念吗？”如果答案是“是”，我便会将该概念添加到一个长长的讨论清单里。

本书的结构

市面上有一些支持可插拔组件的可扩展数据库的例子（例如[SCHWARZ86]），但它们较为少见。与此同时，数据库使用可插拔存储的例子却颇多。类似地，我们很少听到数据库供应商谈论查询的执行，但他们却非常热衷于讨论其数据库是如何保证一致性的。

数据库系统之间最显著的区别集中在两个方面：如何存储和分布数据（其他子系统有时也很重要，但这里不作介绍）。本书分为两部分，讨论了负责数据存储（第一部分）和数据分布（第二部分）的子系统和组件。

第一部分讨论节点本地的进程，并关注存储引擎，它是数据库系统的核心组件以及最重要的一个特有元素。首先，我们从数据库管理系统的架构开始介绍，并提出几种基于主存介质和布局来对数据库系统进行分类的方法。随后，我们将介绍存储结构，并学习基于磁盘的存储结构与基于内存的存储结构之间的区别。然后介绍B树以及在磁盘上高效维护B树结构的算法，包括序列化、页布局以及磁盘存储形式。再之后，我们会讨论B树的一些变体，以说明上述概念的作用以及受B树所影响和启发的数据结构的多样性。最后，我们将讨论日志结构存储的几种变体（它们通常用于实现文件和存储系统），并介绍日志结构存储的起源以及使用它们的原因。

第二部分介绍如何将多个节点组织到一个数据库集群中。我们从构建具备容错性的分布式系统理论开始，进而讨论分布式系统与单节点应用程序有何不同，以及我们在分布式环境中面临的问题、约束和复杂性。之后，我们将深入研究分布式算法。其中，我们从故障检测算法入手，这些算法通过检测和报告故障并排除故障节点的方式来提高系统整体的性能和稳定性。由于本书稍后讨论的许多算法都依赖于集群领导权这个概念，所以我们将介绍几种领导者选举算法，并讨论它们的使用范围。分布式系统中最困难的事情之一就是要保证数据一致性，因此我们将讨论复制的概念，紧接着讨论一致性模型、副本之间可能存在的差异以及最终一致性。由于最终一致性系统有时会依赖于反熵进行收敛，并依靠Gossip来进行数据分发，所以我们会讨论几种反熵和Gossip方法。最后，我们讨论数据库事务上下文中的逻辑一致性，并以共识算法结尾。

如果没有书中提到的这些研究和出版物，我是不可能完成本书的。在本书中，方括号代表参考文献的索引，例如[DECANDIA07]。你可以使用这些参考资料来更详细地了解有关概念。

在每章最后的小结中都包含与该章内容相关的进一步研究的材料。

本书约定

本书使用了下述约定。

楷体

表示新术语。

斜体（Italic）

表示URL、电子邮件地址、文件名和文件扩展名。

等宽字体（Constant width）

用于程序清单，以及段落中引用的程序元素，例如变量或函数名、数据库、数据类型、环境变量、语句和关键词。

这个图标表示提示或建议。

这个图标表示一般性说明。

这个图标表示警告或提醒。

示例代码

写作本书的目的是帮助你完成工作，而书中的示例代码则是为了帮助你更好地理解本书的内容。通常，可以在程序或文档中使用本书中的代码，而不需要联系O扲eilly获得许可，除非需要大段地复制代码。例如，使用本书中所提供的几个代码片段来编写一个程序不需要得到我们的许可，但销售或发布O扲eilly的配套CD-ROM则需要获得许可。引用本书的示例代码来回答一个问题也不需要许可，将本书中的示例代码的很大一部分放到自己的产品文档中则需要获得许可。

我们希望（但不强制）读者在使用本书代码时注明出处。出处的形式包含标题、作者、出版社和ISBN，例如：

Database Internals，作者Alex Petrov，由O扲eilly出版，书号978-1-492-04034-7

如果读者觉得对示例代码的使用超出了上面所给出的许可范围，欢迎通过[email protected]联系我们。

O'Reilly在线学习平台（O'Reilly Online Learning）

近40年来，O'Reilly Media致力于提供技术和商业培训、知识和卓越见解，来帮助众多公司取得成功。

我们拥有独一无二的专家和革新者组成的庞大网络，他们通过图书、文章、会议和我们的在线学习平台分享他们的知识和经验。O扲eilly的在线学习平台允许你按需访问现场培训课程、深入的学习路径、交互式编程环境，以及O扲eilly和200多家其他出版商提供的大量文本和视频资源。有关的更多信息，请访问http://oreilly.com。

联系方式

对于本书，如果有任何意见或疑问，请按照以下地址联系本书出版商。

美国：

O'Reilly Media，Inc.

1005 Gravenstein Highway North

Sebastopol，CA 95472

中国：

北京市西城区西直门南大街2号成铭大厦C座807室（100035）

奥莱利技术咨询（北京）有限公司

本书配套网站（http://bit.ly/database-internals）列出了勘误表、示例以及其他信息。

要询问技术问题或对本书提出建议，请发送电子邮件至[email protected]。

关于书籍、课程、会议和新闻的更多信息，请访问我们的网站：

http://www.oreilly.com

http://www.oreilly.com.cn

我们在Facebook上的地址：http://facebook.com/oreilly

我们在Twitter上的地址：http://twitter.com/oreillymedia

我们在YouTube上的地址：http://www.youtube.com/oreillymedia

致谢

如果没有数以百计的人辛勤撰写相关研究论文和书籍，本书就不可能出版。这些论文和书籍是分布式数据系统思想的源泉，亦是这些思想的参考物，更是本书的参考来源。

我想对所有审阅本书手稿并提供反馈的人表示谢意，是你们确保了书中内容与措辞的正确性：Dmitry Alimov、Peter Alvaro、Carlos Baquero、Jason Brown、Blake Eggleston、Marcus Eriksson、Francisco Fernández Casta、Joel Knighton、Eugene Lazin、Nate McCall、Christopher Meiklejohn、Tyler Neely、Maxim Neverov、Marina Petrova、Stefan Podkowinski、Edward Ribiero、Denis Rytsov、Kir Shatrov、Alex Sorokoumov、Massimiliano Tomassi及Ariel Weisberg。

当然，如果没有家人的支持，本书是不可能完成的，感谢我的妻子Marina和我的女儿Alexandra。这一路走来的每一步，她们都一直在支持我。

前言 1

第一部分 存储引擎

第1章 简介与概述 13

1.1 数据库架构 14

1.2 内存数据库与磁盘数据库 16

1.3 面向列与面向行的数据库 17

1.3.1 面向行的数据布局 18

1.3.2 面向列的数据布局 19

1.3.3 区别与优化 20

1.3.4 宽列式存储 20

1.4 数据文件和索引文件 21

1.4.1 数据文件 22

1.4.2 索引文件 23

1.4.3 间接的主索引 24

1.5 缓冲、不可变性和有序性 25

1.6 本章小结 26

第2章 B树基础知识 28

2.1 二分搜索树 28

2.1.1 树的平衡 29

2.1.2 基于磁盘存储的树 31

2.2 基于磁盘的结构 32

2.2.1 机械硬盘 32

2.2.2 固态硬盘 32

2.2.3 磁盘存储结构 34

2.3 无处不在的B树 35

2.3.1 B树的层次结构 36

2.3.2 分隔键 38

2.3.3 B树查找复杂度 39

2.3.4 B树查找算法 39

2.3.5 键的数目 40

2.3.6 B树的节点分裂 40

2.3.7 B树的节点合并 42

2.4 本章小结 43

第3章 文件格式 45

3.1 动机 45

3.2 二进制编码 46

3.2.1 原始类型 46

3.2.2 字符串和变长数据 48

3.2.3 按位打包的数据：布尔值、枚举值和标志 48

3.3 通用原理 49

3.4 页的结构 51

3.5 分槽页 51

3.6 单元格布局 53

3.7 将单元格放进分槽页 54

3.8 管理变长数据 55

3.9 版本 56

3.10 校验和 57

3.11 本章小结 58

第4章 B树的实现 59

4.1 页头 59

4.1.1 魔数 59

4.1.2 同级指针 60

4.1.3 最右指针 60

4.1.4 节点的高键 61

4.1.5 溢出页 62

4.2 二分搜索 64

4.3 传播分裂与合并 65

4.4 再平衡 67

4.5 仅在右侧追加 68

4.6 压缩 69

4.7 清扫与维护 70

4.7.1 更新和删除导致的碎片 70

4.7.2 页的碎片整理 71

4.8 本章小结 72

第5章 事务处理与恢复 74

5.1 缓冲区管理 75

5.1.1 缓存语义 77

5.1.2 缓存回收 77

5.1.3 在缓存中锁定页 78

5.1.4 页置换 79

5.2 恢复 82

5.2.1 日志语义 83

5.2.2 操作日志与数据日志 84

5.2.3 steal和force策略 84

5.2.4 ARIES 85

5.3 并发控制 86

5.3.1 可串行化 86

5.3.2 事务隔离 87

5.3.3 读异常和写异常 88

5.3.4 隔离级别 88

5.3.5 乐观并发控制 90

5.3.6 多版本并发控制 91

5.3.7 悲观并发控制 91

5.3.8 基于锁的并发控制 91

5.4 本章小结 98

第6章 B树的变体 101

6.1 写时复制 101

6.2 抽象节点更新 103

6.3 惰性B树 103

6.3.1 WiredTiger 104

6.3.2 惰性自适应树 105

6.4 FD树 106

6.4.1 分段级联 106

6.4.2 对数级的有序段 108

6.5 Bw树 108

6.5.1 更新链 109

6.5.2 用CAS控制并发 109

6.5.3 结构修改操作 110

6.5.4 合并和垃圾收集 111

6.6 缓存无关B树 112

6.7 本章小结 114

第7章 日志结构存储 116

7.1 LSM树 117

7.1.1 LSM树的结构 118

7.1.2 更新与删除 122

7.1.3 LSM树的查找 123

7.1.4 合并迭代 124

7.1.5 协调 126

7.1.6 LSM树的维护 126

7.2 读写放大与空间放大 129

7.3 实现细节 130

7.3.1 有序字符串表 130

7.3.2 布隆过滤器 132

7.3.3 跳表 133

7.3.4 磁盘访问 135

7.3.5 压缩 136

7.4 无序LSM存储 136

7.4.1 Bitcask 137

7.4.2 WiscKey 138

7.5 LSM树中的并发 139

7.6 日志堆叠 140

7.6.1 闪存转换层 141

7.6.2 文件系统日志记录 142

7.7 LLAMA与精心堆叠 144

7.8 本章小结 145

第一部分总结 147

第二部分 分布式系统

第8章 简介与概述 151

8.1 并发执行 151

8.2 分布式计算的误区 153

8.2.1 处理 154

8.2.2 时钟和时间 155

8.2.3 状态一致性 156

8.2.4 本地和远程执行 157

8.2.5 处理故障的需要 157

8.2.6 网络分区和部分故障 157

8.2.7 级联故障 158

8.3 分布式系统抽象 160

8.4 两将军问题 165

8.5 FLP不可能定理 166

8.6 系统同步性 167

8.7 故障模型 167

8.7.1 崩溃故障 168

8.7.2 遗漏故障 168

8.7.3 任意故障 169

8.7.4 故障处理 169

8.8 本章小结 169

第9章 故障检测 171

9.1 心跳和ping 172

9.1.1 无超时的故障检测器 173

9.1.2 外包心跳 174

9.2 phi增量故障检测器 175

9.3 Gossip和故障检测 175

9.4 反向故障检测 176

9.5 本章小结 177

第10章 领导者选举 179

10.1 霸道选举算法 180

10.2 依次故障转移 181

10.3 候选节点/普通节点优化 182

10.4 邀请算法 183

10.5 环算法 184

10.6 本章小结 185

第11章 复制和一致性 187

11.1 实现可用性 188

11.2 臭名昭著的CAP理论 188

11.2.1 小心使用CAP 189

11.2.2 收成与产量 190

11.3 共享内存 191

11.4 顺序 192

11.5 一致性模型 193

11.5.1 严格一致性 194

11.5.2 可线性化 194

11.5.3 顺序一致性 198

11.5.4 因果一致性 199

11.6 会话模型 202

11.7 最终一致性 204

11.8 可调一致性 204

11.9 见证者副本 206

11.10 强最终一致性和CRDT 207

11.11 本章小结 209

第12章 反熵和传播 212

12.1 读修复 213

12.2 摘要读 214

12.3 提示移交 215

12.4 Merkle树 215

12.5 位图版本向量 216

12.6 Gossip传播 218

12.6.1 Gossip技术细节 219

12.6.2 覆盖网络 219

12.6.3 混合Gossip 220

12.6.4 局部视图 221

12.7 本章小结 222

第13章 分布式事务 224

13.1 多个操作的原子性 225

13.2 两阶段提交 226

13.2.1 2PC中的参与者故障 227

13.2.2 2PC中的协调者故障 228

13.3 三阶段提交 229

13.4 Calvin分布式事务 231

13.5 Spanner分布式事务 233

13.6 数据库分区 235

13.7 Percolator分布式事务 236

13.8 协调避免 238

13.9 本章小结 240

第14章 共识 243

14.1 广播 244

14.2 原子广播 245

14.2.1 虚同步 245

14.2.2 Zookeeper原子广播 246

14.3 Paxos 248

14.3.1 Paxos算法 249

14.3.2 Paxos的Quorum 250

14.3.3 故障场景 251

14.3.4 Multi-Paxos 253

14.3.5 快速Paxos 254

14.3.6 平等Paxos 255

14.3.7 柔性Paxos 257

14.3.8 共识的推广解法 259

14.4 Raft 261

14.4.1 Raft中的领导者角色 263

14.4.2 故障场景 264

14.5 拜占庭共识 266

14.5.1 PBFT算法 266

14.5.2 恢复和检查点 268

14.6 本章小结 269

第二部分总结 272

参考文献 275