分佈式系統與一致性

一致性是非常重要的分佈式技術。眾所周知，分佈式系統有很多特性，如可用性、可靠性等，這些特性多多少少會與一致性產生關系，受到一致性的影響。要全面研究、掌握分佈式技術，一致性是繞不開的一個話題，也是最難解決的一個問題。本書主要介紹GFS、HDFS、BigTable、MongoDB、RabbitMQ、ZooKeeper、Spanner、CockroachDB系統與一致性有關的實現細節，以及非常重要的Paxos、Raft、Zab分佈式算法；本書還介紹了事務一致性與隔離級別、順序一致性、線性一致性與強一致性相關內容，以及架構設計中的權衡等。從分佈式技術的角度來說，本書講解了分佈式領域比較高階的內容，但是從分佈式一致性的角度來說，本書仍然是一致性的入門書。

陳東明: 餓了麼北京技術中心架構組負責人,負責餓了麼的產品線架構設計以及基礎架構研發工作,主導開發eleme key-value數據庫。
曾任百度架構師負責百度即時通訊產品的架構設計。
具有豐富的大規模系統構建和基礎架構的硏發經驗,善於復雜業務需求下的大並發、分佈式系統設計和持續優化。

第1部分開篇
第1章分佈式系統的核心特性：一致性 2
1.1 拆分是解決大規模應用的本質 2
1.2 分佈式技術是大規模應用的最後一個考驗 4
1.3 一致性是這個考驗的核心 6

第2部分系統案例
第2章Google的文件系統 8
2.1 GFS的外部接口和架構 8
2.1.1 GFS的外部接口 8
2.1.2 GFS的架構 9
2.2 GFS的寫流程細節11
2.2.1 名字空間管理和鎖保護11
2.2.2 租約11
2.2.3 變更及變更次序11
2.3 GFS的原子性13
2.3.1 write和record append的區別13
2.3.2 GFS中原子性的含義14
2.3.3 GFS中多副本之間不具有原子性15
2.4 GFS的鬆弛一致性15
2.4.1 元數據的一致性15
2.4.2 文件數據的一致性15
2.4.3 適應GFS的鬆弛一致性16
2.4.4 GFS的設計哲學17

第3章開源的文件系統HDFS 19
3.1 HDFS的外部接口和架構19
3.1.1 HDFS的外部接口19
3.1.2 HDFS的架構20
3.2 HDFS的寫流程細節21
3.2.1 打開文件22
3.2.2 pipeline寫入22
3.2.3 上報block狀態24
3.2.4 關閉文件24
3.2.5 DN定期上報信息24
3.3 HDFS的錯誤處理25
3.3.1 DN的錯誤25
3.3.2 NN的錯誤26
3.3.3 客戶端的錯誤26

第4章Google的BigTable系統30
4.1 BigTable的外部接口和架構30
4.1.1 表30
4.1.2 數據31
4.1.3 原子性32
4.1.4 時間戳32
4.1.5 BigTable的數據模型33
4.1.6 BigTable的架構34
4.2 BigTable的實現35
4.2.1 tablet location 35
4.2.2 tablet的指派36
4.2.3 加載tablet 36
4.2.4 tablet的讀/寫操作37
4.2.5 合併38

第5章文檔數據庫MongoDB 39
5.1 MongoDB的外部接口和架構39
5.1.1 MongoDB的基本概念39
5.1.2 MongoDB的架構39
5.2 MongoDB的standalone模式40
5.2.1 MongoDB的寫入過程40
5.2.2 無確認導致的丟失更新異常40
5.2.3 未持久化導致的丟失更新異常41
5.3 MongoDB的replica set模式42
5.3.1 MongoDB的複製過程43
5.3.2 無副本確認導致的丟失更新異常44
5.3.3 不正確選主導致的丟失更新異常45
5.3.4 腦裂導致的丟失更新異常47
5.3.5 缺失任期信息導致的丟失更新異常48
5.3.6 臟讀異常51
5.3.7 陳舊讀異常52

第6章消息系統RabbitMQ 54
6.1 RabbitMQ簡述54
6.1.1 關於broker 54
6.1.2 RabbitMQ的接口55
6.1.3 鏡像隊列55
6.2 RabbitMQ的基本實現55
6.2.1 鏡像複製55
6.2.2 鏡像加入隊列56
6.2.3 鏡像同步過程56
6.3 master切換及RabbitMQ的異常處理57
6.3.1 意外宕機後的master切換57
6.3.2 主動運維後的master切換57
6.3.3 意外宕機與主動運維的默認行為差異58
6.3.4 網絡分區後的master切換58
6.4 確認機制59

第7章協調服務ZooKeeper 60
7.1 協調服務的應用場景60
7.2 ZooKeeper簡述61
7.2.1 ZooKeeper的數據模型61
7.2.2 ZooKeeper的外部接口62
7.2.3 ZooKeeper的架構63
7.3 ZooKeeper的實現細節65
7.3.1 客戶端異步處理65
7.3.2 請求處理器65
7.3.3 原子廣播67

第8章Google的Spanner數據庫69
8.1 Spanner的數據模型69
8.2 Spanner的架構72
8.3 Spanner的實現73
8.4 TrueTime的作用81

第9章分佈式數據庫CockroachDB 86
9.1 CockroachDB的接口和數據模型86
9.2 CockroachDB的架構87
9.3 元數據存儲的實現88
9.4 多副本存儲的實現90
9.5 事務的實現92

第3部分分佈式算法
第10章共識算法Paxos 108
10.1 Paxos的歷史108
10.2 Consensus vs Paxos 110
10.3 Basic Paxos算法111
10.4 Multi Paxos 算法132
10.5 複製狀態機144
10.6 Paxos算法與復制狀態機146
10.7 原子廣播148
10.8 Paxos算法與原子廣播149

第11章複製日誌算法Raft 152
11.1 Raft是複制日誌的算法152
11.2 Raft算法的組成153
11.3 複製過程153
11.4 選舉過程154
11.5 異常處理157

第12章原子廣播算法Zab 163
12.1 Zab算法簡述163
12.2 各版本Zab算法的共有部分164
12.3 設計的Zab算法172
12.4 Zab Pre 1.0算法177
12.5 Zab 1.0算法179

第4部分一致性
第13章事務一致性與隔離級別184
13.1 ANSI的隔離級別185
13.2 SI和SSI隔離級別190

第14章順序一致性193
14.1 順序一致性的正式定義193
14.2 理解順序一致性202
14.3 順序一致性的其他描述204
14.4 順序一致性的作用206

第15章線性一致性與強一致性210
15.1 什麼是線性一致性210
15.2 判斷系統是否滿足線性一致性213
15.3 對線性一致性的理解與強一致性216
15.4 ZooKeeper的一致性分析219

第16章架構設計中的權衡225
16.1 什麼是CAP定理225
16.2 關於CAP定理的錯誤理解228
16.3 CAP中的權衡230
16.4 進一步權衡：HAT和PACELC 231