前言 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
· · · · · · (收起)