《深入理解分散式共識算法》是2023年清華大學出版社出版的圖書，作者是釋慧利。
基本介紹
- 中文名：深入理解分散式共識算法
- 作者：釋慧利
- 出版時間：2023年4月1日
- 出版社：清華大學出版社
- 頁數：320 頁
- ISBN：9787302630036
- 類別：科技
- 定價：89.80 元
- 開本：16 開
- 裝幀：平裝
內容簡介,圖書目錄,
內容簡介
《深入理解分散式共識算法》結合理論知識、算法模擬和源碼解析，從多個維度詳細剖析分散式共識算法的基本原理和套用實踐，涵蓋分散式共識算法的方方面面。同時《深入理解分散式共識算法》對共識算法開發中的重點和難點問題進行了重點講解，並提供精心準備的練習題供讀者鞏固和提高所學的知識。另外，作者針對重點內容錄製了教學視頻，以幫助讀者高效、直觀地學習。
《深入理解分散式共識算法》共10章，分為4篇。第1篇分散式相關概念與定理，主要介紹集群、狀態機和共識等相關概念，以及BASE和CAP理論等相關知識；第2篇常見分散式共識算法原理與實戰，主要介紹二階段提交（2PC）協定、三階段提交（3PC）協定、Paxos、ZAB和Raft等相關知識；第3篇Paxos變種算法集合，主要介紹Paxos變種算法的發展歷程，以及Fast Paxos和EPaxos等變種算法的相關知識；第4篇番外——FLP 定理，簡要介紹FLP定理的相關知識。《深入理解分散式共識算法》按照“背景知識→運行過程→算法模擬→證明脈絡”的過程層層推進，介紹算法知識，並為每種算法提供經典類庫源碼解析。
《深入理解分散式共識算法》內容豐富，講解由淺入深，尤其適合剛開始接觸分散式開發的人員全面學習共識算法，也適合資深架構人員借鑑設計思路，還適合中間件開發人員、系統運維工程師、相關培訓學員和高校相關專業的學生閱讀。
圖書目錄
第1篇 分散式相關概念與定理
第1章 分散式共識算法概述 2
1.1 分散式架構的演進 2
1.2 集群與狀態機 3
1.2.1 分散式與集群 3
1.2.2 容錯能力 4
1.2.3 狀態機簡介 4
1.3 共識簡介 5
1.3.1 共識的概念 5
1.3.2 共識與集群 5
1.3.3 共識與副本 6
1.3.4 共識與一致性 7
1.3.5 共識算法的發展歷程 7
1.4 拜占庭故障 7
1.4.1 拜占庭的背景知識 7
1.4.2 拜占庭解決方案 8
1.5 本章小結 10
第2章 從ACID和BASE到CAP 11
2.1 ACID——追求一致性 11
2.2 BASE理論——追求可用性 11
2.2.1 BASE理論的三個方面 12
2.2.2 BASE理論的套用 12
2.3 CAP——分散式系統的PH試紙 13
2.3.1 CAP定理 14
2.3.2 為什麼C、A、P三者不可兼得 15
2.3.3 CAP的套用 16
2.4 本章小結 16
第2篇 常見分散式共識算法原理與實戰
第3章 2PC、3PC——分散式事務的解決方案 18
3.1 二階段提交協定 18
3.1.1 二階段提交協定簡述 18
3.1.2 故障恢復 20
3.1.3 二階段提交協定的優缺點 23
3.1.4 空回滾和防懸掛 23
3.2 三階段提交協定 25
3.2.1 三階段提交協定簡述 25
3.2.2 故障恢復 28
3.2.3 三階段提交協定的優缺點 29
3.3 二階段提交協定在Seata中的套用 29
3.3.1 AT模式 30
3.3.2 事務管理者 32
3.3.3 資源管理者 35
3.3.4 事務協調者 42
3.4 本章小結 46
第4章 Paxos——分散式共識算法 48
4.1 Paxos的誕生 48
4.2 初探Paxos 49
4.2.1 基本概念 49
4.2.2 角色 50
4.2.3 階段 51
4.3 Paxos詳解 54
4.3.1 Paxos模擬 54
4.3.2 Prepare階段 55
4.3.3 Accept階段 56
4.3.4 活鎖 58
4.3.5 提案編號選定 59
4.4 Paxos的推導過程 60
4.4.1 推導 60
4.4.2 多數派的本質 63
4.5 Multi Paxos詳解 64
4.5.1 Multi Paxos簡介 64
4.5.2 Leader選舉 66
4.6 工程實現 68
4.6.1 一些最佳化 68
4.6.2 對讀請求進行最佳化 70
4.6.3 並行協商 71
4.6.4 Instance的重確認 72
4.6.5 幽靈日誌 73
4.7 Paxos在PhxPaxos中的套用 74
4.7.1 PhxPaxos分析 75
4.7.2 PhxPaxos初始化 80
4.7.3 協商提案 82
4.7.4 數據同步 91
4.7.5 Master選舉 95
4.7.6 成員變更 98
4.8 本章小結 99
4.9 練習題 100
第5章 ZAB——ZooKeeper技術核心 101
5.1 Chubby簡介 101
5.1.1 Chubby是什麼 101
5.1.2 為什麼選擇鎖服務 102
5.1.3 需求分析 103
5.1.4 Chubby集群架構 104
5.2 ZooKeeper的簡單套用 107
5.2.1 ZooKeeper是什麼 107
5.2.2 數據節點 108
5.2.3 Watch機制 110
5.2.4 ACL許可權控制 111
5.2.5 會話 113
5.2.6 讀請求處理 113
5.3 ZAB設計 114
5.3.1 ZooKeeper背景分析 114
5.3.2 為什麼ZooKeeper不直接使用Paxos 116
5.3.3 ZAB簡介 118
5.3.4 事務標識符 120
5.3.5 多數派機制 121
5.3.6 Leader周期 121
5.4 ZAB描述 122
5.4.1 Leader選舉階段 122
5.4.2 成員發現階段 122
5.4.3 數據同步階段 123
5.4.4 訊息廣播階段 124
5.4.5 算法小結 124
5.5 ZooKeeper中的ZAB實現 125
5.5.1 選舉階段 126
5.5.2 成員發現階段 129
5.5.3 數據同步階段 130
5.5.4 訊息廣播階段 133
5.5.5 算法小結 134
5.5.6 算法模擬 135
5.5.7 提案的安全性 139
5.6 ZooKeeper成員變更 140
5.6.1 變更過程 141
5.6.2 並行變更 142
5.7 ZooKeeper源碼實戰 142
5.7.1 啟動 142
5.7.2 Leader選舉 144
5.7.3 Follower和Leader初始化 148
5.7.4 成員發現階段 151
5.7.5 數據同步階段 154
5.7.6 訊息廣播階段 157
5.8 本章小結 162
5.9 練習題 163
第6章 Raft——共識算法的寵兒 164
6.1 Raft簡介 164
6.1.1 Raft誕生的背景 164
6.1.2 可理解性 165
6.1.3 基本概念 165
6.2 Raft算法描述 167
6.2.1 Leader選舉 167
6.2.2 日誌複製 170
6.2.3 日誌對齊 173
6.2.4 幽靈日誌 174
6.2.5 安全性 175
6.2.6 Raft小結 176
6.3 算法模擬 177
6.3.1 Leader選舉 177
6.3.2 日誌複製 178
6.3.3 日誌對齊 180
6.4 成員變更 181
6.4.1 聯合共識 182
6.4.2 工程實踐 185
6.4.3 單個成員變更 188
6.5 日誌壓縮 191
6.6 網路分區 192
6.6.1 成員變更中的分區 192
6.6.2 對稱網路分區 193
6.6.3 非對稱網路分區 194
6.7 非事務請求 194
6.7.1 線性一致性 195
6.7.2 Leader Read方案 196
6.7.3 Raft Log Read方案 196
6.7.4 Read Index方案 196
6.7.5 Lease Read方案 197
6.8 Parallel Raft並行協商 198
6.8.1 亂序協商 199
6.8.2 Merge階段 200
6.9 Raft源碼實戰——SOFAJRaft 202
6.9.1 SOFAJRaft簡介 203
6.9.2 Leader選舉 205
6.9.3 日誌複製 212
6.9.4 非事務請求 219
6.9.5 成員變更 221
6.10 本章小結 223
6.10.1 Raft與Paxos的異同 223
6.10.2 Raft與ZAB的異同 224
6.11 練習題 225
第3篇 Paxos變種算法集合
第7章 Paxos變種算法的發展史 228
7.1 Disk Paxos簡介 228
7.1.1 算法描述 229
7.1.2 Disk Paxos小結 230
7.2 Cheap Paxos簡介 230
7.2.1 算法描述 231
7.2.2 Cheap Paxos小結 232
7.3 Generalized Paxos簡介 233
7.4 Stoppable Paxos簡介 234
7.5 Mencius簡介 235
7.6 Vertical Paxos簡介 237
7.6.1 算法描述 237
7.6.2 算法模擬 238
7.6.3 Vertical Paxos小結 240
7.7 本章小結 240
第8章 Fast Paxos——C/S架構的福音 242
8.1 Fast Paxos簡介 242
8.1.1 背景介紹 242
8.1.2 基本概念 243
8.2 算法詳述 244
8.2.1 算法設計 244
8.2.2 Fast Paxos模擬 245
8.2.3 Learn階段 246
8.3 Quorum推導 246
8.3.1 決策條件 247
8.3.2 計算Quorum 248
8.4 Classic Round簡介 249
8.4.1 提案衝突 249
8.4.2 選擇提案值的規則 250
8.4.3 證明 252
8.5 提案恢復 253
8.5.1 基於協調者的恢復 253
8.5.2 基於非協調者的恢復 254
8.6 本章小結 254
第9章 EPaxos——去中心化共識 255
9.1 EPaxos簡介 255
9.1.1 共識算法對比 255
9.1.2 認識EPaxos算法 256
9.1.3 基本概念 258
9.2 協商協定 260
9.2.1 Prepare階段 260
9.2.2 PreAccept階段 263
9.2.3 Paxos-Accept階段 264
9.2.4 Commit階段 265
9.2.5 特殊的Quorum 266
9.3 執行協定 268
9.3.1 互相依賴 268
9.3.2 執行過程 269
9.3.3 拓撲排序 270
9.3.4 尋找強連通分量 271
9.3.5 EPaxos排序 272
9.4 算法證明 272
9.4.1 執行的一致性 273
9.4.2 執行的順序性 274
9.5 Optimized-EPaxos簡介 274
9.5.1 Prepare階段 275
9.5.2 論證QuorumFast 278
9.6 算法模擬 279
9.6.1 協商協定 279
9.6.2 Prepare階段 282
9.7 成員變更 284
9.8 工程最佳化 285
9.8.1 巨大的訊息體 285
9.8.2 讀請求處理 285
9.9 本章小結 286
9.9.1 EPaxos與Paxos的異同 286
9.9.2 EPaxos與Raft、ZAB、Multi Paxos的異同 287
9.10 練習題 288
第4篇 番外——FLP定理
第10章 FLP——不可能定理 290
10.1 FLP定理概述 290
10.1.1 FLP簡介 290
10.1.2 FLP的環境模型 290
10.1.3 Paxos為什麼是正確的 291
10.2 FLP的證明 292
10.2.1 基礎定義 292
10.2.2 完全正確 292
10.2.3 引理1 293
10.2.4 引理2 293
10.2.5 引理3 294
10.2.6 證明 296
10.3 FLP的指導意義 296
練習題答案 298
參考文獻 303
