数据库系统内幕

图书标准信息

• 作者 [美]亚历克斯·彼得罗夫（Alex Petrov） 著
• 出版社 机械工业出版社
• 出版时间 2020-06
• 版次 1
• ISBN 9787111655169
• 定价 119.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 300页
• 字数 100千字

【内容简介】

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

 

【作者简介】

作者简介

 

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

 

译者简介

 

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

 

 

 

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

 

 

 

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

 

【目录】

前言 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