数据库系统内幕

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

.　　诸如查询计划、查询优化、调度、关系模型等概念，在一些优秀的数据库系统教科书中已均有涉及。这些概念中的一部分通常是从用户的角度进行描述的，而本书则着重于内部结构。你可以在第二部分的总结和每章的小结中找到一些有用文献的推荐。这些文献应该能回答很多与数据库相关的问题。
　　由于本书中提到的数据库系统之间没有一种通用的查询语言，所以本书将不讨论查询语言。
　　为了收集本书的材料，我研究了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
　　如果读者觉得对示例代码的使用超出了上面所给出的许可范围，欢迎通过permission@oreilly.com联系我们。
　　O'Reilly在线学习平台（O'Reilly Online Learning）
　　近40年来，O'Reilly Media致力于提供技术和商业培训、知识和卓越见解，来帮助众多公司取得成功。
　　我们拥有独一无二的专家和革新者组成的庞大网络，他们通过图书、文章、会议和我们的在线学习平台分享他们的知识和经验。O扲eilly的在线学习平台允许你按需访问现场培训课程、深入的学习路径、交互式编程环境，以及O扲eilly和200多家其他出版商提供的大量文本和视频资源。有关的更多信息，请访问http://oreilly.com。
　　致谢
　　如果没有数以百计的人辛勤撰写相关研究论文和书籍，本书就不可能出版。这些论文和书籍是分布式数据系统思想的源泉，亦是这些思想的参考物，更是本书的参考来源。
　　我想对所有审阅本书手稿并提供反馈的人表示谢意，是你们确保了书中内容与措辞的正确性：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。这一路走来的每一步，她们都一直在支持我。