数据库系统内幕

当我们选择、使用并维护一个数据库系统时，理解它的原理至关重要。但是现今有太多的分布式数据库和工具可供使用，要想弄明白每一种工具的作用以及它们之间的区别往往并不容易。在这本实用指南中，作者讲解了现代数据库和存储引擎背后的概念。通过本书，你将领略到从众多书籍、论文、博客和多个开源数据库源代码中精心选取的相关材料，并且了解到众多现代数据库之间*重要的区别在于决定存储结构和数据分布的子系统。你将深入了解如下内容：?存储引擎：学习存储的种类、分类依据，理解基于B树和不可变日志存储结构的存储引擎。?存储构建块：理解数据库文件如何使用诸如页缓存、缓冲池等辅助数据结构来组织构建高效的存储。?分布式系统：逐步学习节点和进程间如何连接并构建复杂的通信模式。?数据库集群：深入探究现在数据库中常用的一致性模型，并了解分布式存储系统是如何实现一致性的。

这本书既不是关于关系型数据库的书，也不是关于NoSQL的书，而是关于在各种数据库系统中使用的算法和概念的书，重点是存储引擎和负责数据分布的组件。第壹部分讨论节点本地的进程，并着重于存储引擎这个数据库系统的核心组件以及*重要的一个特有元素。第二部分讨论负责数据分布的子系统和组件，介绍如何将多个节点组织到一个数据库集群中。

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

前言1部分 存储引擎章 简介与概述131.1 数据库架构141.2 内存数据库与磁盘数据库161.3 面向列与面向行的数据库171.3.1 面向行的数据布局181.3.2 面向列的数据布局191.3.3 区别与优化201.3.4 宽列式存储201.4 数据文件和索引文件211.4.1 数据文件221.4.2 索引文件231.4.3 间接的主索引241.5 缓冲、不可变性和有序性251.6 本章小结26第2章 B树基础知识282.1 二分搜索树282.1.1 树的平衡292.1.2 基于磁盘存储的树312.2 基于磁盘的结构322.2.1 机械硬盘322.2.2 固态硬盘322.2.3 磁盘存储结构342.3 无处不在的B树352.3.1 B树的层次结构362.3.2 分隔键382.3.3 B树查找复杂度392.3.4 B树查找算法392.3.5 键的数目402.3.6 B树的节点分裂402.3.7 B树的节点合并422.4 本章小结43第3章 文件格式453.1 动机453.2 二进制编码463.2.1 原始类型463.2.2 字符串和变长数据483.2.3 按位打包的数据：布尔值、枚举值和标志483.3 通用原理493.4 页的结构513.5 分槽页513.6 单元格布局533.7 将单元格放进分槽页543.8 管理变长数据553.9 版本563.10 校验和573.11 本章小结58第4章 B树的实现594.1 页头594.1.1 魔数594.1.2 同级指针604.1.3 最右指针604.1.4 节点的高键614.1.5 溢出页624.2 二分搜索644.3 传播分裂与合并654.4 再平衡674.5 仅在右侧追加684.6 压缩694.7 清扫与维护704.7.1 更新和删除导致的碎片704.7.2 页的碎片整理714.8 本章小结72第5章 事务处理与恢复745.1 缓冲区管理755.1.1 缓存语义775.1.2 缓存回收775.1.3 在缓存中锁定页785.1.4 页置换795.2 恢复825.2.1 日志语义835.2.2 操作日志与数据日志845.2.3 steal和force策略845.2.4 ARIES855.3 并发控制865.3.1 可串行化865.3.2 事务隔离875.3.3 读异常和写异常885.3.4 隔离级别885.3.5 乐观并发控制905.3.6 多版本并发控制915.3.7 悲观并发控制915.3.8 基于锁的并发控制915.4 本章小结98第6章 B树的变体1016.1 写时复制1016.2 抽象节点更新1036.3 惰性B树1036.3.1 WiredTiger1046.3.2 惰性自适应树1056.4 FD树1066.4.1 分段级联1066.4.2 对数级的有序段1086.5 Bw树1086.5.1 更新链1096.5.2 用CAS控制并发1096.5.3 结构修改操作1106.5.4 合并和垃圾收集1116.6 缓存无关B树1126.7 本章小结114第7章 日志结构存储1167.1 LSM树1177.1.1 LSM树的结构1187.1.2 更新与删除1227.1.3 LSM树的查找1237.1.4 合并迭代1247.1.5 协调1267.1.6 LSM树的维护1267.2 读写放大与空间放大1297.3 实现细节1307.3.1 有序字符串表1307.3.2 布隆过滤器1327.3.3 跳表1337.3.4 磁盘访问1357.3.5 压缩1367.4 无序LSM存储1367.4.1 Bitcask1377.4.2 WiscKey1387.5 LSM树中的并发1397.6 日志堆叠1407.6.1 闪存转换层1417.6.2 文件系统日志记录1427.7 LLAMA与精心堆叠1447.8 本章小结145部分总结147第二部分 分布式系统第8章 简介与概述1518.1 并发执行1518.2 分布式计算的误区1538.2.1 处理1548.2.2 时钟和时间1558.2.3 状态一致性1568.2.4 本地和远程执行1578.2.5 处理故障的需要1578.2.6 网络分区和部分故障1578.2.7 级联故障1588.3 分布式系统抽象1608.4 两将军问题1658.5 FLP不可能定理1668.6 系统同步性1678.7 故障模型1678.7.1 崩溃故障1688.7.2 遗漏故障1688.7.3 任意故障1698.7.4 故障处理1698.8 本章小结169第9章 故障检测1719.1 心跳和ping1729.1.1 无超时的故障检测器1739.1.2 外包心跳1749.2 phi增量故障检测器1759.3 Gossip和故障检测1759.4 反向故障检测1769.5 本章小结1770章 领导者选举17910.1 霸道选举算法18010.2 依次故障转移18110.3 候选节点/普通节点优化18210.4 邀请算法18310.5 环算法18410.6 本章小结1851章 复制和一致性18711.1 实现可用性18811.2 臭名昭著的CAP理论18811.2.1 小心使用CAP18911.2.2 收成与产量19011.3 共享内存19111.4 顺序19211.5 一致性模型19311.5.1 严格一致性19411.5.2 可线性化19411.5.3 顺序一致性19811.5.4 因果一致性19911.6 会话模型20211.7 最终一致性20411.8 可调一致性20411.9 见证者副本20611.10 强最终一致性和CRDT20711.11 本章小结2092章 反熵和传播21212.1 读修复21312.2 摘要读21412.3 提示移交21512.4 Merkle树21512.5 位图版本向量21612.6 Gossip传播21812.6.1 Gossip技术细节21912.6.2 覆盖网络21912.6.3 混合Gossip22012.6.4 局部视图22112.7 本章小结2223章 分布式事务22413.1 多个操作的原子性22513.2 两阶段提交22613.2.1 2PC中的参与者故障22713.2.2 2PC中的协调者故障22813.3 三阶段提交22913.4 Calvin分布式事务23113.5 Spanner分布式事务23313.6 数据库分区235