這是一部對分布式數據庫的核心原理、架構設計以及經典分布式數據庫的實現進行深入剖析的著作，融入了作者在騰訊、Oracle等企業20餘年的數據庫實踐經驗，以及數據庫領域前沿的研究成果，得到了中國人民大學杜小勇教授等多位業界知名專家的高口碑和鼎力推薦。
本書以前沿技術和工程實踐為抓手，沿著問題確認、原理闡述、架構剖析、實例分析的思路，從3個方面對分布式數據進行了講解。
分布式數據庫原理。首先提出了分布式繫統面臨的典型問題，尤其是一致性問題；然後結合CAP原理和分布式事務處理技術中的ACID技術對這些問題（重點是一致性問題）的本質進行深挖；接著基於時鐘、Paxos協議、Raft算法等給出可行的解決方案；後深度解讀事務處理技術中的MVCC、OCC、DTA等技術在近年的發展。
分布式數據庫架構。討論了影響架構的內在、外在技術因素，其中內在因素包括強一致性、高可靠性、高可用性等；外在因素包括雲計算、Serveless需求等。這部分終要解決的問題是：如何通過計算/存儲分離、智能化和新硬件技術實現繫統的高可擴展性、高可靠性以及高可用性？
分布式數據庫實現。從工程實踐的角度，以Spanner、CockroachDB等多個數據庫為對像，從問題、原理、前沿技術研究成果等角度對分布式數據庫的架構、事務處理技術的實現以及在實際繫統中的落地進行了詳細介紹。

Contents 目錄

序一

序二

序三

序四

前言

篇原理

第1章分布式數據庫繫統的

挑戰和原理  3

1.1分布式數據庫繫統的挑戰  3

1.1.1分布式繫統面臨的問題  4

1.1.2數據庫面臨的一致性問題  7

1.1.3分布式數據庫繫統面臨的問題  15

1.2分布式理論  20

1.2.1ACID、BASE與CAP簡析  21

1.2.2CAP分布式理論  23

1.2.3PACELC理論和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.1Paxos協議解決問題的背景  64

3.5.2 Paxos協議中的角色  64

3.5.3Basic Paxos協議  66

3.5.4 Paxos協議改進與擴展  67

3.6 Raft算法  74

3.6.1 Raft算法基礎  74

3.6.2 Raft算法詳解  75

3.6.3Paxos算法與Raft算法的比較  78

第4章分布式事務原理  81

4.1概述  82

4.1.1單機事務處理技術  82

4.1.2分布式事務處理技術  85

4.2基本的分布式事務並發訪問控制機制  89

4.2.1封鎖並發訪問控制算法  90

4.2.2TO相關算法  91

4.2.3CO算法  92

4.3OCC算法  95

4.3.1OCC算法的優勢與不足  95

4.3.2基本的OCC算法  97

4.3.3改進的OCC算法  103

4.3.4OCC算法與其他並發算法的融合  110

4.3.5分布式OCC算法  117

4.4MVCC技術  121

4.4.1MVCC技術解決了

什麼問題  122

4.4.2MVCC技術的核心思想  123

4.4.3可串行化的快照隔離  124

4.4.4寫快照隔離  128

4.4.5MVCC技術實現示例  132

4.4.6MVCC技術擴展  139

4.5前沿的並發控制技術  140

4.5.1動態調整時間戳算法  140

4.5.2Data-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.2MPP  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.3Serverless數據庫  217

6.4HTAP  218

6.4.1HTAP概念與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.2Spanner的架構  234

7.3Spanner的事務處理模型  236

7.3.1讀事務的分類和意義  237

7.3.2分布式一致性實現原理  237

7.3.3寫操作一致性的實現原理  239

7.3.4Truetime事務處理機制的缺點  241

7.3.5深入理解Spanner的悲觀策略  242

7.3.6Spanner與MVCC  243

7.3.7讀副本數據  244

7.3.8全局讀事務的一致性  244

7.3.9隻讀事務  245

7.4Spanner與CAP  246

第8章Percolator事務處理模型  247

8.1Percolator的架構  247

8.2Percolator的事務處理  248

8.2.1事務處理整體過程  248

8.2.2數據項上存儲的事務信息  249

8.2.3事務提交過程  249

8.2.4事務讀數據過程  252

8.2.5Percolator的事務處理示例  253

第9章CockroachDB深度探索  255

9.1CockroachDB的架構  255

9.2CockroachDB事務處理模型  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.1Hekaton的技術架構  267

10.1.2Hekaton的事務管理  271

10.1.3Hekaton的並發控制  275

10.2文檔型分布式數據庫MongoDB  276

10.2.1MongoDB的架構  277

10.2.2MongoDB的事務處理技術  277

10.3列存分布式數據庫HBase  278

10.3.1HBase的架構  278

10.3.2HBase的事務處理技術  279

10.4Greenplum  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

前言 Preface

為什麼寫這本書

現代的分布式技術在互聯網應用的驅動下，在CAP理論的引領下，已經有了很多新的內涵和外延。而分布式技術體繫下，分布式數據庫技術的發展方興未艾，其中有很多“新”問題正在被研究，例如：CAP理論中代表分布式一致性的C和事務ACID中的C之間是什麼關繫？是否存在可結合之處？當然，也有很多“新”技術正在發展中。但是，在分布式數據庫領域缺少體繫化的、深入剖析數據庫原理的書籍，使得這個領域的技術傳播偏弱，尤其是分布式數據庫領域的一致性等相關技術，存在概念混雜、理解不一的問題。筆者基於對該領域多年的科研和實踐，歷經數年，把對分布式數據庫領域一些重要技術的理解和在實踐中所得的經驗整理成冊，期待以圖書的形式幫到更多讀者。本書若是能促進分布式數據庫的進一步發展，筆者將不勝榮幸。

本書主要內容

本書主要討論如下3個話題。

分布式數據庫中存在的問題和原理。科學研究，始於問題。本書首先對分布式數據庫技術中一些典型問題進行分析，以明確本書所要研究和解決問題的技術方向。之後討論CAP原理與ACID技術結合後的一些問題（重點是一致性問題）及技術，以及業界在這方面的科研成果和工程實現思路。

分布式數據庫架構。從分布式數據庫架構的角度，討論影響架構的內在、外在技術因素，內在因素如強一致性、高可靠性、高可用性，外在因素如雲計算、Serverless需

求等。

分布式數據庫案例實踐。從工程實踐的角度，以案例的形式討論諸多分布式繫統的實現技術，涉及的數據庫包括Spanner、CockroachDB、HBase、Greenplum等。

本書主要特色

本書以前沿技術和工程實踐為抓手，通過問題確認、原理闡述、架構剖析、實例分析，有深度地進行了以下三項工作。

深入經典技術：對經典技術進行深度探索，如剖析CAP原理的發展過程，深度解讀事務處理技術（如MVCC、OCC、DTA等技術）的發展和相關研究。

前沿探索：按照本書的內容規劃，對前沿技術方向與內容從廣度層面進行剖析和介紹，以開闊讀者的思路和眼界。前沿內容散布於各個章節，與各章節主題互相映襯。

原理、案例相結合：立足原理，對分布式數據庫的架構進行深度剖析，並對業界多個產品從問題、原理、前沿技術研究成果、架構相關因素等角度進行深度分析。用多個案例多樣化地印證其他部分介紹的原理和前沿技術。

本書面向的主要讀者

分布式數據庫的設計者和開發者；

分布式數據庫前沿技術的研究者；

其他對分布式數據庫感興趣的讀者。

如何閱讀本書

本書沒有涉及編程實現的細節，而是從整體上對分布式數據庫一致性等重要問題逐步展開介紹。全書分為三篇——原理、架構和典型案例。其中原理篇對經典的分布式數據庫理論和技術進行剖析。

基於原理篇，架構篇從兩個角度對分布式數據庫架構進行剖析：一是影響數據庫內核設計的理念（第5章）；二是影響數據庫架構設計的外在環境（第6章）。這兩個方面的內容可幫助讀者深入理解數據庫內核的框架結構及設計思想。

典型案例篇則結合原理，對部分經典的分布式數據庫繫統展開討論，以幫助讀者把理論和實踐相結合。閱讀案例時，如能時時重溫原理篇的內容，則學習效果更佳。

本書不僅給出了大量的參考文獻及其概述，還將這些參考文獻和本書內容相結合，兩者相互印證，進而使本書內容更充實。限於篇幅，書中不可能對所有內容都充分展開，所以如果您期望更加深入地掌握和理解相關內容，可進一步閱讀相應參考文獻。

資源及勘誤

由於筆者的水平有限，書中難免存在錯誤，若您在閱讀時發現任何問題，都可發送電子郵件到database_XX@163.com，筆者不勝感謝。有了您的幫助和支持，本書定能更加完善。由於時間有限，也許筆者不能一一回復所有的電子郵件，但是一定會定期整理並彙總信息到華章網站（http://www.hzbook.com）本書的頁面下。

致謝

在多年的研究和實踐工作中，承蒙中國人民大學杜小勇教授的悉心指導，筆者獲益良多，本書能面世也與杜教授的指導息息相關，在此深表感謝。另外，要特別感謝杜教授在百忙之中抽出時間，專門為本書作序。

本書承蒙武漢大學彭智勇教授、易鯨捷信息技術有限公司CEO武新博士、CSDN創始人兼董事長蔣濤先生作序推薦，在此致以誠摯的感謝。

感謝筆者的父母、妻女。筆者傾注於寫作本書的時光，本應是陪伴親人們的歲月，筆者因此愧疚不已。

感謝華章公司編輯楊福川先生和孫海亮先生為本書付出的努力與耗費的心血，筆者出版了數本書，都得到他們無私、有價值的幫助。

感謝每一位讀者，讀者的口碑促使筆者不斷努力，每一位讀者都是筆者繼續進步的不竭動力。期待本書對讀者有所幫助。

李海翔

海翔對Spanner、Percolator、CockroachDB等多個分布式數據庫繫統進行了深入分析，對其中的一些核心技術有了較好的理解。在此基礎上，對分布式數據庫的一些原理進行了梳理，特別是對“一致性”的概念進行了繫統的研究，弄清楚了分布式計算中的一致性（CAP的C）和數據庫繫統中的事務一致性（ACID的C）的概念的區別和聯繫。他還深度研究和實踐了高可用分布式數據庫的架構設計、主流並發訪問控制算法等。這些都是很有價值的工作。
 ——杜小勇博士中國人民大學教授/中國計算機學會大數據專家委員會主任
 本書作者長期從事數據庫研究與開發工作，這是他繼《數據庫查詢優化器的藝術》和《數據庫事務處理的藝術》之後又一部集原理、架構與實踐於一體的分布式數據庫力作，非常值得數據庫學術界和產業界人士參考，也是高校學生學習分布式數據庫技術很好的教材。
 ——彭智勇博士武漢大學教授/中國計算機學會會士/數據庫專家委員會副主任
 本書的內容涵蓋了分布式技術領域和分布式OLTP數據庫領域的理論進展和技術實現原理，無論是對數據庫內核的資深開發者、還是進階者，對基於分布式數據庫的應用開發者，對學習數據庫課程的同學們，相信本書都可以帶來有價值的幫助和指導。這是一本分布式數據庫領域近幾年值得推薦的一本書。
 ——武新博士易鯨捷信息技術有限公司 CEO
 很高興看到國內有這樣的一線專家著書分享核心技術的原理，設計思想和架構。相信這本書的出版會激發更多的開發者深入研究基礎核心技術，未來幫助中國成為全球技術的領先者。
 ——蔣濤 CSDN創始人、董事長/ 極客幫創投創始合伙人