高效内功修炼必备，全景式解读现代数据库技术
新书速递
分布式数据库系统是大多数企业和绝大多数应用程序不可或缺的一部分。这些应用程序提供业务逻辑和用户界面，而数据库系统则负责确保数据的完整性、一致性和冗余性。
回到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和最终一致性数据库之后，我们开始看到一些可扩展性更强、性能更高的数据库，它们能够在保证具有更强一致性的同时执行复杂的查询。
《数据库系统内幕》从数据库开发者角度，对现代数据库技术进行了全景式解读，完全不拘泥于任何一款数据库系统，也不偏袒任何一种数据库的类型或特性。这本书只会讨论现代数据库必不可少的那些东西，例如存储格式、索引数据结构、数据一致性等，以及相关的许多选项与权衡。
第一部分从单机的角度，介绍磁盘存储格式、索引数据结构、事务处理等，第二部分则以分布式系统切入，讲解分布式数据库的多副本、分布式事务、一致性等问题。书中内容的选材紧跟业内前沿进展，不仅有提及各种新兴的数据库产品，还有涉及许多来自学术界前沿的研究成果。不论你是一名有志于从事云计算领域的开发者，深入的研究数据库系统的设计与实现，还是作为一名开发者，即将使用云数据库以及云原生数据库，阅读本书都会大有裨益。
●为什么应该阅读本书●
我们经常听到人们用他们实现的概念和算法来描述数据库系统：“该数据库使用Gossip来进行成员资格的传播”（参见第12章）、“他们已经实现了Dynamo”或“这就像他们在Spanner论文中描述的一样”（参见第13章）。抑或，如果你正在讨论算法和数据结构，那么你会听到类似于“ZAB和Raft有很多共同点”（参见第14章）、“Bw树就像是在日志结构化存储上实现的B树一样”（参见第6章）或“它们使用的是类似于Blink树中的同级指针”（参见第5章）的描述。
我们需要使用抽象来讨论复杂的概念，但是我们不能在每次开启一场对话时都讨论抽象术语。以白话的形式来掌握这些抽象概念是一个捷径，这能帮助我们将注意力转移到其他更高层次的问题上。
学习基本概念、证明和算法的一个优点是它们永不过时。当然，总会有新的东西出现，但是新算法往往是在发现经典算法的缺陷或改进空间之后才被创造出来的。了解历史有助于更好地理解这些算法之间的差异和它们的发明动机。
学习这些内容是鼓舞人心的。你将看到各种各样的算法，了解我们的工业界是如何一个接一个地解决问题的，并开始欣赏数据系统。同时，学习这些是有回报的：你几乎可以感觉到多个拼图碎片在脑海中移动到一起，最终形成一幅完整的图画，并且你将总是能够与他人分享这幅图画。
●本书的范畴●
本书既不是关于关系型数据库的书，也不是关于NoSQL的书，而是关于在各种数据库系统中使用的算法和概念的书，且重点是存储引擎和负责数据分布的组件。
诸如查询计划、查询优化、调度、关系模型等概念，在一些优秀的数据库系统教科书中已均有涉及。这些概念中的一部分通常是从用户的角度进行描述的，而本书则着重于内部结构。你可以在第二部分的总结和每章的小结中找到一些有用文献的推荐。这些文献应该能回答很多与数据库相关的问题。
由于本书中提到的数据库系统之间没有一种通用的查询语言，所以本书将不讨论查询语言。
● 目录●
前言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 ARIES85
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 WiredTiger104
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 Bitcask137
7.4.2 WiscKey138
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 心跳和ping172
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 小心使用CAP189
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 强最终一致性和CRDT207
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 混合Gossip220
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 Paxos248
14.3.1 Paxos算法249
14.3.2 Paxos的Quorum250
14.3.3 故障场景251
14.3.4 Multi-Paxos253
14.3.5 快速Paxos254
14.3.6 平等Paxos255
14.3.7 柔性Paxos257
14.3.8 共识的推广解法259
14.4 Raft261
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
上下滑动查看
●实拍●
点击链接了解详情并购买
更多精彩回顾
书讯 | 6月书讯 （上）| 初夏已至，书香有约，六月宜静心读书
书讯 | 6月书讯 （下）| 初夏已至，书香有约，六月宜静心读书
上新 | 周志华领衔撰写，历时4年，宝箱书问世！
书单 | 创建字节跳动之前，张一鸣读过哪些硬核技术书？
干货 | G1垃圾回收算法概述