分布式系統(tǒng)與一致性

第1部分　開 篇
第1章 分布式系統(tǒng)的核心特性：一致性 2
1.1 拆分是解決大規(guī)模應(yīng)用的本質(zhì) 2
1.2 分布式技術(shù)是大規(guī)模應(yīng)用的最后一個考驗 4
1.3 一致性是這個考驗的核心 6
第2部分　系統(tǒng)案例
第2章 Google的文件系統(tǒng) 8
2.1 GFS的外部接口和架構(gòu) 8
2.1.1 GFS的外部接口 8
2.1.2 GFS的架構(gòu) 9
2.2 GFS的寫流程細節(jié) 11
2.2.1 名字空間管理和鎖保護 11
2.2.2 租約 11
2.2.3 變更及變更次序 11
2.3 GFS的原子性 13
2.3.1 write和record append的區(qū)別 13
2.3.2 GFS中原子性的含義 14
2.3.3 GFS中多副本之間不具有原子性 15
2.4 GFS的松弛一致性 15
2.4.1 元數(shù)據(jù)的一致性 15
2.4.2 文件數(shù)據(jù)的一致性 15
2.4.3 適應(yīng)GFS的松弛一致性 16
2.4.4 GFS的設(shè)計哲學(xué) 17

第3章 開源的文件系統(tǒng)HDFS 19
3.1 HDFS的外部接口和架構(gòu) 19
3.1.1 HDFS的外部接口 19
3.1.2 HDFS的架構(gòu) 20
3.2 HDFS的寫流程細節(jié) 21
3.2.1 打開文件 22
3.2.2 pipeline寫入 22
3.2.3 上報block狀態(tài) 24
3.2.4 關(guān)閉文件 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系統(tǒng) 30
4.1 BigTable的外部接口和架構(gòu) 30
4.1.1 表 30
4.1.2 數(shù)據(jù) 31
4.1.3 原子性 32
4.1.4 時間戳 32
4.1.5 BigTable的數(shù)據(jù)模型 33
4.1.6 BigTable的架構(gòu) 34
4.2 BigTable的實現(xiàn) 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章 文檔數(shù)據(jù)庫MongoDB 39
5.1 MongoDB的外部接口和架構(gòu) 39
5.1.1 MongoDB的基本概念 39
5.1.2 MongoDB的架構(gòu) 39
5.2 MongoDB的standalone模式 40
5.2.1 MongoDB的寫入過程 40
5.2.2 無確認導(dǎo)致的丟失更新異常 40
5.2.3 未持久化導(dǎo)致的丟失更新異常 41
5.3 MongoDB的replica set模式 42
5.3.1 MongoDB的復(fù)制過程 43
5.3.2 無副本確認導(dǎo)致的丟失更新異常 44
5.3.3 不正確選主導(dǎo)致的丟失更新異常 45
5.3.4 腦裂導(dǎo)致的丟失更新異常 47
5.3.5 缺失任期信息導(dǎo)致的丟失更新異常 48
5.3.6 臟讀異常 51
5.3.7 陳舊讀異常 52
第6章 消息系統(tǒng)RabbitMQ 54
6.1 RabbitMQ簡述 54
6.1.1 關(guān)于broker 54
6.1.2 RabbitMQ的接口 55
6.1.3 鏡像隊列 55
6.2 RabbitMQ的基本實現(xiàn) 55
6.2.1 鏡像復(fù)制 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 網(wǎng)絡(luò)分區(qū)后的master切換 58
6.4 確認機制 59
第7章 協(xié)調(diào)服務(wù)ZooKeeper 60
7.1 協(xié)調(diào)服務(wù)的應(yīng)用場景 60
7.2 ZooKeeper簡述 61
7.2.1 ZooKeeper的數(shù)據(jù)模型 61
7.2.2 ZooKeeper的外部接口 62
7.2.3 ZooKeeper的架構(gòu) 63
7.3 ZooKeeper的實現(xiàn)細節(jié) 65
7.3.1 客戶端異步處理 65
7.3.2 請求處理器 65
7.3.3 原子廣播 67

第8章 Google的Spanner數(shù)據(jù)庫 69
8.1 Spanner的數(shù)據(jù)模型 69
8.2 Spanner的架構(gòu) 72
8.3 Spanner的實現(xiàn) 73
8.4 TrueTime的作用 81

第9章 分布式數(shù)據(jù)庫CockroachDB 86
9.1 CockroachDB的接口和數(shù)據(jù)模型 86
9.2 CockroachDB的架構(gòu) 87
9.3 元數(shù)據(jù)存儲的實現(xiàn) 88
9.4 多副本存儲的實現(xiàn) 90
9.5 事務(wù)的實現(xiàn) 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 復(fù)制狀態(tài)機 144
10.6 Paxos算法與復(fù)制狀態(tài)機 146
10.7 原子廣播 148
10.8 Paxos算法與原子廣播 149

第11章 復(fù)制日志算法Raft 152
11.1 Raft是復(fù)制日志的算法 152
11.2 Raft算法的組成 153
11.3 復(fù)制過程 153
11.4 選舉過程 154
11.5 異常處理 157

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

第4部分　一 致 性
第13章 事務(wù)一致性與隔離級別 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 判斷系統(tǒng)是否滿足線性一致性 213
15.3 對線性一致性的理解與強一致性 216
15.4 ZooKeeper的一致性分析 219

第16章 架構(gòu)設(shè)計中的權(quán)衡 225
16.1 什么是CAP定理 225
16.2 關(guān)于CAP定理的錯誤理解 228
16.3 CAP中的權(quán)衡 230
16.4 進一步權(quán)衡：HAT和PACELC 231