前 言Preface
為什么寫這本書
現(xiàn)代的分布式技術在互聯(lián)網應用的驅動下，在CAP理論的引領下，已經有了很多新的內涵和外延。而分布式技術體系下，分布式數(shù)據庫技術的發(fā)展方興未艾，其中有很多新問題正在被研究，例如：CAP理論中代表分布式一致性的C和事務ACID中的C之間是什么關系？是否存在可結合之處？當然，也有很多新技術正在發(fā)展中。但是，在分布式數(shù)據庫領域缺少體系化的、深入剖析數(shù)據庫原理的書籍，使得這個領域的技術傳播偏弱，尤其是分布式數(shù)據庫領域的一致性等相關技術，存在概念混雜、理解不一的問題。筆者基于對該領域多年的科研和實踐，歷經數(shù)年，把對分布式數(shù)據庫領域一些重要技術的理解和在實踐中所得的經驗整理成冊，期待以圖書的形式幫到更多讀者。本書若是能促進分布式數(shù)據庫的進一步發(fā)展，筆者將不勝榮幸。
本書主要內容
本書主要討論如下3個話題。
分布式數(shù)據庫中存在的問題和原理�？茖W研究，始于問題。本書首先對分布式數(shù)據庫技術中一些典型問題進行分析，以明確本書所要研究和解決問題的技術方向。之后討論CAP原理與ACID技術結合后的一些問題（重點是一致性問題）及技術，以及業(yè)界在這方面的科研成果和工程實現(xiàn)思路。
分布式數(shù)據庫架構。從分布式數(shù)據庫架構的角度，討論影響架構的內在、外在技術因素，內在因素如強一致性、高可靠性、高可用性，外在因素如云計算、Serverless需
求等。
分布式數(shù)據庫案例實踐。從工程實踐的角度，以案例的形式討論諸多分布式系統(tǒng)的實現(xiàn)技術，涉及的數(shù)據庫包括Spanner、CockroachDB、HBase、Greenplum等。
本書主要特色
本書以前沿技術和工程實踐為抓手，通過問題確認、原理闡述、架構剖析、實例分析，有深度地進行了以下三項工作。
深入經典技術：對經典技術進行深度探索，如剖析CAP原理的發(fā)展過程，深度解讀事務處理技術（如MVCC、OCC、DTA等技術）的發(fā)展和相關研究。
前沿探索：按照本書的內容規(guī)劃，對前沿技術方向與內容從廣度層面進行剖析和介紹，以開闊讀者的思路和眼界。前沿內容散布于各個章節(jié)，與各章節(jié)主題互相映襯。
原理、案例相結合：立足原理，對分布式數(shù)據庫的架構進行深度剖析，并對業(yè)界多個產品從問題、原理、前沿技術研究成果、架構相關因素等角度進行深度分析。用多個案例多樣化地印證其他部分介紹的原理和前沿技術。
本書面向的主要讀者
分布式數(shù)據庫的設計者和開發(fā)者；
分布式數(shù)據庫前沿技術的研究者；
其他對分布式數(shù)據庫感興趣的讀者。
如何閱讀本書
本書沒有涉及編程實現(xiàn)的細節(jié)，而是從整體上對分布式數(shù)據庫一致性等重要問題逐步展開介紹。全書分為三篇原理、架構和典型案例。其中原理篇對經典的分布式數(shù)據庫理論和技術進行剖析。
基于原理篇，架構篇從兩個角度對分布式數(shù)據庫架構進行剖析：一是影響數(shù)據庫內核設計的理念（第5章）；二是影響數(shù)據庫架構設計的外在環(huán)境（第6章）。這兩個方面的內容可幫助讀者深入理解數(shù)據庫內核的框架結構及設計思想。
典型案例篇則結合原理，對部分經典的分布式數(shù)據庫系統(tǒng)展開討論，以幫助讀者把理論和實踐相結合。閱讀案例時，如能時時重溫原理篇的內容，則學習效果更佳。
本書不僅給出了大量的參考文獻及其概述，還將這些參考文獻和本書內容相結合，兩者相互印證，進而使本書內容更充實。限于篇幅，書中不可能對所有內容都充分展開，所以如果您期望更加深入地掌握和理解相關內容，可進一步閱讀相應參考文獻。
資源及勘誤
由于筆者的水平有限，書中難免存在錯誤，若您在閱讀時發(fā)現(xiàn)任何問題，都可發(fā)送電子郵件到database_XX@163.com，筆者不勝感謝。有了您的幫助和支持，本書定能更加完善。由于時間有限，也許筆者不能一一回復所有的電子郵件，但是一定會定期整理并匯總信息到華章網站（http://www.hzbook.com）本書的頁面下。
致謝
在多年的研究和實踐工作中，承蒙中國人民大學杜小勇教授的悉心指導，筆者獲益良多，本書能面世也與杜教授的指導息息相關，在此深表感謝。另外，要特別感謝杜教授在百忙之中抽出時間，專門為本書作序。
本書承蒙武漢大學彭智勇教授、易鯨捷信息技術有限公司CEO武新博士、CSDN創(chuàng)始人兼董事長蔣濤先生作序推薦，在此致以誠摯的感謝。
感謝筆者的父母、妻女。筆者傾注于寫作本書的時光，本應是陪伴親人們的歲月，筆者因此愧疚不已。
感謝華章公司編輯楊福川先生和孫海亮先生為本書付出的努力與耗費的心血，筆者出版了數(shù)本書，都得到他們無私、有價值的幫助。
感謝每一位讀者，讀者的口碑促使筆者不斷努力，每一位讀者都是筆者繼續(xù)進步的不竭動力。期待本書對讀者有所幫助。
李海翔
Contents目 錄
序一
序二
序三
序四
前言
篇 原理
第1章 分布式數(shù)據庫系統(tǒng)的
挑戰(zhàn)和原理 3
1.1 分布式數(shù)據庫系統(tǒng)的挑戰(zhàn) 3
1.1.1 分布式系統(tǒng)面臨的問題 4
1.1.2 數(shù)據庫面臨的一致性問題 7
1.1.3 分布式數(shù)據庫系統(tǒng)面臨的問題 15
1.2 分布式理論 20
1.2.1 ACID、BASE與CAP簡析 21
1.2.2 CAP分布式理論 23
1.2.3 PACELC理論和CAP新進展 29
1.3 分布式系統(tǒng)一致性的本質 30
1.3.1 偏序與全序 30
1.3.2 有序與并發(fā) 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 分布式系統(tǒng)主備一致性 54
2.5.2 去中心化的分布式系統(tǒng)一致性 55
第3章 一致性問題的解法 56
3.1依賴物理時間引發(fā)的問題 56
3.2邏輯時鐘 57
3.2.1 因果（happened-before）模型 57
3.2.2邏輯時鐘的實現(xiàn) 58
3.2.3邏輯時鐘的缺點 58
3.2.4物理時鐘與同步問題 59
3.3向量時鐘 59
3.4混合邏輯時鐘 61
3.5Paxos協(xié)議 64
3.5.1 Paxos協(xié)議解決問題的背景 64
3.5.2Paxos協(xié)議中的角色 64
3.5.3 Basic Paxos協(xié)議 66
3.5.4Paxos協(xié)議改進與擴展 67
3.6Raft算法 74
3.6.1Raft算法基礎 74
3.6.2Raft算法詳解 75
3.6.3 Paxos算法與Raft算法的比較 78
第4章 分布式事務原理 81
4.1 概述 82
4.1.1 單機事務處理技術 82
4.1.2 分布式事務處理技術 85
4.2 基本的分布式事務并發(fā)訪問控制機制 89
4.2.1 封鎖并發(fā)訪問控制算法 90
4.2.2 TO相關算法 91
4.2.3 CO算法 92
4.3 OCC算法 95
4.3.1 OCC算法的優(yōu)勢與不足 95
4.3.2 基本的OCC算法 97
4.3.3 改進的OCC算法 103
4.3.4 OCC算法與其他并發(fā)算法的融合 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技術實現(xiàn)示例 132
4.4.6 MVCC技術擴展 139
4.5 前沿的并發(fā)控制技術 140
4.5.1 動態(tài)調整時間戳算法 140
4.5.2 Data-driven算法 145
4.5.3 面向列的細粒度機制 148
4.5.4 基于硬件的改進 149
4.5.5 基于AI的改進 153
4.5.6 自適應并發(fā)訪問控制算法 155
4.6 分布式提交技術 159
4.6.1 兩階段提交 159
4.6.2 三階段提交 163
4.6.3 基于Paxos的提交 164
4.6.4 一階段提交 166
4.7 可串行化發(fā)展歷史 166
4.8 其他分布式處理技術 169
第二篇 架構
第5章 去中心化的分布式數(shù)據庫架構 175
5.1 分布式存儲架構 175
5.1.1 數(shù)據分布 176
5.1.2 數(shù)據管理 177
5.1.3 多副本與數(shù)據存儲 179
5.1.4 存算分離 180
5.1.5 多讀與多寫 184
5.2 分布式查詢優(yōu)化與并行執(zhí)行架構 187
5.2.1 查詢優(yōu)化 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 事務管理器在客戶端、中間件、服務器端中的實現(xiàn) 198
5.4.2 去中心化的并發(fā)事務框架 201
5.5 可擴展性架構 202
5.5.1 可擴展性是一種能力 202
5.5.2 事務處理的可擴展性 204
5.6 強一致性 206
5.7 解耦 206
第6章 新技術與分布式數(shù)據庫架構 210
6.1 新硬件 210
6.2 智能數(shù)據庫 211
6.3 云計算與數(shù)據庫 213
6.3.1 云原生 214
6.3.2 云數(shù)據庫 216
6.3.3 Serverless數(shù)據庫 217
6.4 HTAP 218
6.4.1 HTAP概念與HTAC架構 218
6.4.2 行列混存 220
6.5 下一代數(shù)據庫 221
6.5.1 數(shù)據庫技術簡史 221
6.5.2 下一代數(shù)據庫技術特征 228
第三篇 典型案例
第7章 Spanner深度探索 233
7.1 從Spanner的兩篇重點論文說起 233
7.2 Spanner的架構 234
7.3 Spanner的事務處理模型 236
7.3.1 讀事務的分類和意義 237
7.3.2 分布式一致性實現(xiàn)原理 237
7.3.3 寫操作一致性的實現(xiàn)原理 239
7.3.4 Truetime事務處理機制的缺點 241
7.3.5 深入理解Spanner的悲觀策略 242
7.3.6 Spanner與MVCC 243
7.3.7 讀副本數(shù)據 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 數(shù)據項上存儲的事務信息 249
8.2.3 事務提交過程 249
8.2.4 事務讀數(shù)據過程 252
8.2.5 Percolator的事務處理示例 253
第9章 CockroachDB深度探索 255
9.1 CockroachDB的架構 255
9.2 CockroachDB事務處理模型 257
9.2.1 事務處理相關的數(shù)據結構 258
9.2.2 事務處理的階段 259
9.2.3 事務處理的整體過程 260
9.2.4 事務的并發(fā)沖突 261
9.2.5 事務自動終止 264
9.2.6 隔離級別 265
9.3 分布式一致性實現(xiàn)原理 265
第10章 其他數(shù)據庫 267
10.1 內存型數(shù)據庫Hekaton的事務處理機制 267
10.1.1 Hekaton的技術架構 267
10.1.2 Hekaton的事務管理 271
10.1.3 Hekaton的并發(fā)控制 275
10.2 文檔型分布式數(shù)據庫MongoDB 276
10.2.1 MongoDB的架構 277
10.2.2 MongoDB的事務處理技術 277
10.3 列存分布式數(shù)據庫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 深入討論數(shù)據庫架構 285
10.6.1 數(shù)據庫的通用架構 285
10.6.2 事務型數(shù)據庫的架構 286
10.6.3 主流分布式數(shù)據庫的技術比較 290
參考文獻 292
書單推薦
