分佈式數據庫原理、架構與實踐

李海翔（網名：那海藍藍）

 騰訊金融雲數據庫首席研究員，騰訊T14級專家，騰訊TDSQL分佈式數據庫首席架構師。
 中國人民大學、北京林業大學特聘碩士導師，CCF數據庫專委會委員，
DTCC（中國數據庫技術大會）專家委員會委員，北京市科技進步一等獎得主。
申請和獲得授權的專利多達70餘項，在VLDB等數據庫大會上發表論文若干篇，
參與了多個國家863重大專項、核高基、工信部、科技部等的項目。
 出版《數據庫查詢優化器的藝術：原理解析與SQL性能優化》
《數據庫事務處理的藝術：事務管理與並發控制》等數據庫領域著作4本。

目錄
序一
序二
序三
序四
前言
篇　原理
第1章　分佈式數據庫系統的
挑戰和原理 3
1.1　分佈式數據庫系統的挑戰 3
1.1.1　分佈式系統面臨的問題 4
1.1.2　數據庫面臨的一致性問題 7
1.1.3　分佈式數據庫系統面臨的問題 15
1.2　分佈式理論 20
1.2.1　ACID、BASE與CAP簡析 21
1.2.2　CAP分佈式理論 23
1.2.3　PACELC理論和CAP新進展 29
1.3　分佈式系統一致性的本質 30
1.3.1　偏序與全序 30
1.3.2　有序與並發 31

第2章　深入研究一致性 33
2.1　概述 34
2.1.1　常見的分佈式一致性 35
2.1.2　科研情況一覽 38
2.2　結果一致性 41
2.2.1　共識問題形象化描述：拜占庭將軍問題 42
2.2.2　結果一致性的應用 42
2.3　次序一致性 43
2.3.1　線性一致性 43
2.3.2　順序一致性 47
2.3.3　因果一致性 47
2.3.4　會話一致性 48
2.4　分佈式事務一致性 49
2.4.1　單機事務的一致性 49
2.4.2　分佈式事務的一致性 52
2.4.3　分佈式一致性與分佈式事務一致性的關係 52
2.5　架構一致性 54
2.5.1　分佈式系統主備一致性 54
2.5.2　去中心化的分佈式系統一致性 55

第3章　一致性問題的解法 56
3.1?依賴物理時間引發的問題 56
3.2?邏輯時鐘 57
3.2.1　因果（happened-before）模型 57
3.2.2?邏輯時鐘的實現 58
3.2.3?邏輯時鐘的缺點 58
3.2.4?物理時鐘與同步問題 59
3.3?向量時鐘 59
3.4?混合邏輯時鐘 61
3.5?Paxos協議 64
3.5.1　Paxos協議解決問題的背景 64
3.5.2?Paxos協議中的角色 64
3.5.3　Basic Paxos協議 66
3.5.4?Paxos協議改進與擴展 67
3.6?Raft算法 74
3.6.1?Raft算法基礎 74
3.6.2?Raft算法詳解 75
3.6.3　Paxos算法與Raft算法的比較 78

第4章　分佈式事務原理 81
4.1　概述 82
4.1.1　單機事務處理技術 82
4.1.2　分佈式事務處理技術 85
4.2　基本的分佈式事務並發訪問控制機制 89
4.2.1　封鎖並發訪問控制算法 90
4.2.2　TO相關算法 91
4.2.3　CO算法 92
4.3　OCC算法 95
4.3.1　OCC算法的優勢與不足 95
4.3.2　基本的OCC算法 97
4.3.3　改進的OCC算法 103
4.3.4　OCC算法與其他並發算法的融合 110
4.3.5　分佈式OCC算法 117
4.4　MVCC技術 121
4.4.1　MVCC技術解決了
什麼問題 122
4.4.2　MVCC技術的核心思想 123
4.4.3　可串行化的快照隔離 124
4.4.4　寫快照隔離 128
4.4.5　MVCC技術實現示例 132
4.4.6　MVCC技術擴展 139
4.5　前沿的並發控制技術 140
4.5.1　動態調整時間戳算法 140
4.5.2　Data-driven算法 145
4.5.3　面向列的細粒度機制 148
4.5.4　基於硬件的改進 149
4.5.5　基於AI的改進 153
4.5.6　自適應並發訪問控制算法 155
4.6　分佈式提交技術 159
4.6.1　兩階段提交 159
4.6.2　三階段提交 163
4.6.3　基於Paxos的提交 164
4.6.4　一階段提交 166
4.7　可串行化發展歷史 166
4.8　其他分佈式處理技術 169

第二篇　架構
第5章　去中心化的分佈式數據庫架構 175
5.1　分佈式存儲架構 175
5.1.1　數據分佈 176
5.1.2　數據管理 177
5.1.3　多副本與數據存儲 179
5.1.4　存算分離 180
5.1.5　多讀與多寫 184
5.2　分佈式查詢優化與並行執行架構 187
5.2.1　查詢優化 187
5.2.2　MPP 188
5.2.3　計算下推/外推 189
5.3　高可用性架構 190
5.3.1　高可用衡量指標 191
5.3.2　高可用性分類 194
5.3.3　高可用事務 195
5.3.4　高可用架構 197
5.4　分佈式事務架構 198
5.4.1　事務管理器在客戶端、中間件、服務器端中的實現 198
5.4.2　去中心化的並發事務框架 201
5.5　可擴展性架構 202
5.5.1　可擴展性是一種能力 202
5.5.2　事務處理的可擴展性 204
5.6　強一致性 206
5.7　解耦 206

第6章　新技術與分佈式數據庫架構 210
6.1　新硬件 210
6.2　智能數據庫 211
6.3　雲計算與數據庫 213
6.3.1　雲原生 214
6.3.2　雲數據庫 216
6.3.3　Serverless數據庫 217
6.4　HTAP 218
6.4.1　HTAP概念與HTAC架構 218
6.4.2　行列混存 220
6.5　下一代數據庫 221
6.5.1　數據庫技術簡史 221
6.5.2　下一代數據庫技術特徵 228

第三篇　典型案例
第7章　Spanner深度探索 233
7.1　從Spanner的兩篇重點論文說起 233
7.2　Spanner的架構 234
7.3　Spanner的事務處理模型 236
7.3.1　讀事務的分類和意義 237
7.3.2　分佈式一致性實現原理 237
7.3.3　寫操作一致性的實現原理 239
7.3.4　Truetime事務處理機制的缺點 241
7.3.5　深入理解Spanner的悲觀策略 242
7.3.6　Spanner與MVCC 243
7.3.7　讀副本數據 244
7.3.8　全局讀事務的一致性 244
7.3.9　只讀事務 245
7.4　Spanner與CAP 246

第8章　Percolator事務處理模型 247
8.1　Percolator的架構 247
8.2　Percolator的事務處理 248
8.2.1　事務處理整體過程 248
8.2.2　數據項上存儲的事務信息 249
8.2.3　事務提交過程 249
8.2.4　事務讀數據過程 252
8.2.5　Percolator的事務處理示例 253

第9章　CockroachDB深度探索 255
9.1　CockroachDB的架構 255
9.2　CockroachDB事務處理模型 257
9.2.1　事務處理相關的數據結構 258
9.2.2　事務處理的階段 259
9.2.3　事務處理的整體過程 260
9.2.4　事務的並發衝突 261
9.2.5　事務自動終止 264
9.2.6　隔離級別 265
9.3　分佈式一致性實現原理 265

第10章　其他數據庫 267
10.1　內存型數據庫Hekaton的事務處理機制 267
10.1.1　Hekaton的技術架構 267
10.1.2　Hekaton的事務管理 271
10.1.3　Hekaton的並發控制 275
10.2　文檔型分佈式數據庫MongoDB 276
10.2.1　MongoDB的架構 277
10.2.2　MongoDB的事務處理技術 277
10.3　列存分佈式數據庫HBase 278
10.3.1　HBase的架構 278
10.3.2　HBase的事務處理技術 279
10.4　Greenplum 280
10.5　圖、鍵值、文檔事務處理技術 282
10.5.1　圖模型事務處理技術 283
10.5.2　鍵值、文檔模型事務處理技術 284
10.6　深入討論數據庫架構 285
10.6.1　數據庫的通用架構 285
10.6.2　事務型數據庫的架構 286
10.6.3　主流分佈式數據庫的技術比較 290
參考文獻 292