數(shù)據(jù)庫系統(tǒng)內(nèi)幕

前言 1

第一部分 存儲(chǔ)引擎

第1章 簡(jiǎn)介與概述 13

1.1 數(shù)據(jù)庫架構(gòu) 14

1.2 內(nèi)存數(shù)據(jù)庫與磁盤數(shù)據(jù)庫 16

1.3 面向列與面向行的數(shù)據(jù)庫 17

1.3.1 面向行的數(shù)據(jù)布局 18

1.3.2 面向列的數(shù)據(jù)布局 19

1.3.3 區(qū)別與優(yōu)化 20

1.3.4 寬列式存儲(chǔ) 20

1.4 數(shù)據(jù)文件和索引文件 21

1.4.1 數(shù)據(jù)文件 22

1.4.2 索引文件 23

1.4.3 間接的主索引 24

1.5 緩沖、不可變性和有序性 25

1.6 本章小結(jié) 26

第2章 B樹基礎(chǔ)知識(shí) 28

2.1 二分搜索樹 28

2.1.1 樹的平衡 29

2.1.2 基于磁盤存儲(chǔ)的樹 31

2.2 基于磁盤的結(jié)構(gòu) 32

2.2.1 機(jī)械硬盤 32

2.2.2 固態(tài)硬盤 32

2.2.3 磁盤存儲(chǔ)結(jié)構(gòu) 34

2.3 無處不在的B樹 35

2.3.1 B樹的層次結(jié)構(gòu) 36

2.3.2 分隔鍵 38

2.3.3 B樹查找復(fù)雜度 39

2.3.4 B樹查找算法 39

2.3.5 鍵的數(shù)目 40

2.3.6 B樹的節(jié)點(diǎn)分裂 40

2.3.7 B樹的節(jié)點(diǎn)合并 42

2.4 本章小結(jié) 43

第3章 文件格式 45

3.1 動(dòng)機(jī) 45

3.2 二進(jìn)制編碼 46

3.2.1 原始類型 46

3.2.2 字符串和變長(zhǎng)數(shù)據(jù) 48

3.2.3 按位打包的數(shù)據(jù)：布爾值、枚舉值和標(biāo)志 48

3.3 通用原理 49

3.4 頁的結(jié)構(gòu) 51

3.5 分槽頁 51

3.6 單元格布局 53

3.7 將單元格放進(jìn)分槽頁 54

3.8 管理變長(zhǎng)數(shù)據(jù) 55

3.9 版本 56

3.10 校驗(yàn)和 57

3.11 本章小結(jié) 58

第4章 B樹的實(shí)現(xiàn) 59

4.1 頁頭 59

4.1.1 魔數(shù) 59

4.1.2 同級(jí)指針 60

4.1.3 最右指針 60

4.1.4 節(jié)點(diǎn)的高鍵 61

4.1.5 溢出頁 62

4.2 二分搜索 64

4.3 傳播分裂與合并 65

4.4 再平衡 67

4.5 僅在右側(cè)追加 68

4.6 壓縮 69

4.7 清掃與維護(hù) 70

4.7.1 更新和刪除導(dǎo)致的碎片 70

4.7.2 頁的碎片整理 71

4.8 本章小結(jié) 72

第5章 事務(wù)處理與恢復(fù) 74

5.1 緩沖區(qū)管理 75

5.1.1 緩存語義 77

5.1.2 緩存回收 77

5.1.3 在緩存中鎖定頁 78

5.1.4 頁置換 79

5.2 恢復(fù) 82

5.2.1 日志語義 83

5.2.2 操作日志與數(shù)據(jù)日志 84

5.2.3 steal和force策略 84

5.2.4 ARIES 85

5.3 并發(fā)控制 86

5.3.1 可串行化 86

5.3.2 事務(wù)隔離 87

5.3.3 讀異常和寫異常 88

5.3.4 隔離級(jí)別 88

5.3.5 樂觀并發(fā)控制 90

5.3.6 多版本并發(fā)控制 91

5.3.7 悲觀并發(fā)控制 91

5.3.8 基于鎖的并發(fā)控制 91

5.4 本章小結(jié) 98

第6章 B樹的變體 101

6.1 寫時(shí)復(fù)制 101

6.2 抽象節(jié)點(diǎn)更新 103

6.3 惰性B樹 103

6.3.1 WiredTiger 104

6.3.2 惰性自適應(yīng)樹 105

6.4 FD樹 106

6.4.1 分段級(jí)聯(lián) 106

6.4.2 對(duì)數(shù)級(jí)的有序段 108

6.5 Bw樹 108

6.5.1 更新鏈 109

6.5.2 用CAS控制并發(fā) 109

6.5.3 結(jié)構(gòu)修改操作 110

6.5.4 合并和垃圾收集 111

6.6 緩存無關(guān)B樹 112

6.7 本章小結(jié) 114

第7章 日志結(jié)構(gòu)存儲(chǔ) 116

7.1 LSM樹 117

7.1.1 LSM樹的結(jié)構(gòu) 118

7.1.2 更新與刪除 122

7.1.3 LSM樹的查找 123

7.1.4 合并迭代 124

7.1.5 協(xié)調(diào) 126

7.1.6 LSM樹的維護(hù) 126

7.2 讀寫放大與空間放大 129

7.3 實(shí)現(xiàn)細(xì)節(jié) 130

7.3.1 有序字符串表 130

7.3.2 布隆過濾器 132

7.3.3 跳表 133

7.3.4 磁盤訪問 135

7.3.5 壓縮 136

7.4 無序LSM存儲(chǔ) 136

7.4.1 Bitcask 137

7.4.2 WiscKey 138

7.5 LSM樹中的并發(fā) 139

7.6 日志堆疊 140

7.6.1 閃存轉(zhuǎn)換層 141

7.6.2 文件系統(tǒng)日志記錄 142

7.7 LLAMA與精心堆疊 144

7.8 本章小結(jié) 145

第一部分總結(jié) 147

第二部分 分布式系統(tǒng)

第8章 簡(jiǎn)介與概述 151

8.1 并發(fā)執(zhí)行 151

8.2 分布式計(jì)算的誤區(qū) 153

8.2.1 處理 154

8.2.2 時(shí)鐘和時(shí)間 155

8.2.3 狀態(tài)一致性 156

8.2.4 本地和遠(yuǎn)程執(zhí)行 157

8.2.5 處理故障的需要 157

8.2.6 網(wǎng)絡(luò)分區(qū)和部分故障 157

8.2.7 級(jí)聯(lián)故障 158

8.3 分布式系統(tǒng)抽象 160

8.4 兩將軍問題 165

8.5 FLP不可能定理 166

8.6 系統(tǒng)同步性 167

8.7 故障模型 167

8.7.1 崩潰故障 168

8.7.2 遺漏故障 168

8.7.3 任意故障 169

8.7.4 故障處理 169

8.8 本章小結(jié) 169

第9章 故障檢測(cè) 171

9.1 心跳和ping 172

9.1.1 無超時(shí)的故障檢測(cè)器 173

9.1.2 外包心跳 174

9.2 phi增量故障檢測(cè)器 175

9.3 Gossip和故障檢測(cè) 175

9.4 反向故障檢測(cè) 176

9.5 本章小結(jié) 177

第10章 領(lǐng)導(dǎo)者選舉 179

10.1 霸道選舉算法 180

10.2 依次故障轉(zhuǎn)移 181

10.3 候選節(jié)點(diǎn)/普通節(jié)點(diǎn)優(yōu)化 182

10.4 邀請(qǐng)算法 183

10.5 環(huán)算法 184

10.6 本章小結(jié) 185

第11章 復(fù)制和一致性 187

11.1 實(shí)現(xiàn)可用性 188

11.2 臭名昭著的CAP理論 188

11.2.1 小心使用CAP 189

11.2.2 收成與產(chǎn)量 190

11.3 共享內(nèi)存 191

11.4 順序 192

11.5 一致性模型 193

11.5.1 嚴(yán)格一致性 194

11.5.2 可線性化 194

11.5.3 順序一致性 198

11.5.4 因果一致性 199

11.6 會(huì)話模型 202

11.7 最終一致性 204

11.8 可調(diào)一致性 204

11.9 見證者副本 206

11.10 強(qiáng)最終一致性和CRDT 207

11.11 本章小結(jié) 209

第12章 反熵和傳播 212

12.1 讀修復(fù) 213

12.2 摘要讀 214

12.3 提示移交 215

12.4 Merkle樹 215

12.5 位圖版本向量 216

12.6 Gossip傳播 218

12.6.1 Gossip技術(shù)細(xì)節(jié) 219

12.6.2 覆蓋網(wǎng)絡(luò) 219

12.6.3 混合Gossip 220

12.6.4 局部視圖 221

12.7 本章小結(jié) 222

第13章 分布式事務(wù) 224

13.1 多個(gè)操作的原子性 225

13.2 兩階段提交 226

13.2.1 2PC中的參與者故障 227

13.2.2 2PC中的協(xié)調(diào)者故障 228

13.3 三階段提交 229

13.4 Calvin分布式事務(wù) 231

13.5 Spanner分布式事務(wù) 233

13.6 數(shù)據(jù)庫分區(qū) 235

13.7 Percolator分布式事務(wù) 236

13.8 協(xié)調(diào)避免 238

13.9 本章小結(jié) 240

第14章 共識(shí) 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 故障場(chǎng)景 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 共識(shí)的推廣解法 259

14.4 Raft 261

14.4.1 Raft中的領(lǐng)導(dǎo)者角色 263

14.4.2 故障場(chǎng)景 264

14.5 拜占庭共識(shí) 266

14.5.1 PBFT算法 266

14.5.2 恢復(fù)和檢查點(diǎn) 268

14.6 本章小結(jié) 269

第二部分總結(jié) 272

參考文獻(xiàn) 275