深入理解分布式共識(shí)算法

第1篇  分布式相關(guān)概念與定理
第1章  分布式共識(shí)算法概述 2
1.1  分布式架構(gòu)的演進(jìn) 2
1.2  集群與狀態(tài)機(jī) 3
1.2.1  分布式與集群 3
1.2.2  容錯(cuò)能力 4
1.2.3  狀態(tài)機(jī)簡(jiǎn)介 4
1.3  共識(shí)簡(jiǎn)介 5
1.3.1  共識(shí)的概念 5
1.3.2  共識(shí)與集群 5
1.3.3  共識(shí)與副本 6
1.3.4  共識(shí)與一致性 7
1.3.5  共識(shí)算法的發(fā)展歷程 7
1.4  拜占庭故障 7
1.4.1  拜占庭的背景知識(shí) 7
1.4.2  拜占庭解決方案 8
1.5  本章小結(jié) 10
第2章  從ACID和BASE到CAP 11
2.1  ACID——追求一致性 11
2.2  BASE理論——追求可用性 11
2.2.1  BASE理論的三個(gè)方面 12
2.2.2  BASE理論的應(yīng)用 12
2.3  CAP——分布式系統(tǒng)的PH試紙 13
2.3.1  CAP定理 14
2.3.2  為什么C、A、P三者不可兼得 15
2.3.3  CAP的應(yīng)用 16
2.4  本章小結(jié) 16
第2篇  常見(jiàn)分布式共識(shí)算法原理與實(shí)戰(zhàn)
第3章  2PC、3PC——分布式事務(wù)的解決方案 18
3.1  二階段提交協(xié)議 18
3.1.1  二階段提交協(xié)議簡(jiǎn)述 18
3.1.2  故障恢復(fù) 20
3.1.3  二階段提交協(xié)議的優(yōu)缺點(diǎn) 23
3.1.4  空回滾和防懸掛 23
3.2  三階段提交協(xié)議 25
3.2.1  三階段提交協(xié)議簡(jiǎn)述 25
3.2.2  故障恢復(fù) 28
3.2.3  三階段提交協(xié)議的優(yōu)缺點(diǎn) 29
3.3  二階段提交協(xié)議在Seata中的應(yīng)用 29
3.3.1  AT模式 30
3.3.2  事務(wù)管理者 32
3.3.3  資源管理者 35
3.3.4  事務(wù)協(xié)調(diào)者 42
3.4  本章小結(jié) 46
第4章  Paxos——分布式共識(shí)算法 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  提案編號(hào)選定 59
4.4  Paxos的推導(dǎo)過(guò)程 60
4.4.1  推導(dǎo) 60
4.4.2  多數(shù)派的本質(zhì) 63
4.5  Multi Paxos詳解 64
4.5.1  Multi Paxos簡(jiǎn)介 64
4.5.2  Leader選舉 66
4.6  工程實(shí)現(xiàn) 68
4.6.1  一些優(yōu)化 68
4.6.2  對(duì)讀請(qǐng)求進(jìn)行優(yōu)化 70
4.6.3  并行協(xié)商 71
4.6.4  Instance的重確認(rèn) 72
4.6.5  幽靈日志 73
4.7  Paxos在PhxPaxos中的應(yīng)用 74
4.7.1  PhxPaxos分析 75
4.7.2  PhxPaxos初始化 80
4.7.3  協(xié)商提案 82
4.7.4  數(shù)據(jù)同步 91
4.7.5  Master選舉 95
4.7.6  成員變更 98
4.8  本章小結(jié) 99
4.9  練習(xí)題 100
第5章  ZAB——ZooKeeper技術(shù)核心 101
5.1  Chubby簡(jiǎn)介 101
5.1.1  Chubby是什么 101
5.1.2  為什么選擇鎖服務(wù) 102
5.1.3  需求分析 103
5.1.4  Chubby集群架構(gòu) 104
5.2  ZooKeeper的簡(jiǎn)單應(yīng)用 107
5.2.1  ZooKeeper是什么 107
5.2.2  數(shù)據(jù)節(jié)點(diǎn) 108
5.2.3  Watch機(jī)制 110
5.2.4  ACL權(quán)限控制 111
5.2.5  會(huì)話 113
5.2.6  讀請(qǐng)求處理 113
5.3  ZAB設(shè)計(jì) 114
5.3.1  ZooKeeper背景分析 114
5.3.2  為什么ZooKeeper不直接使用Paxos 116
5.3.3  ZAB簡(jiǎn)介 118
5.3.4  事務(wù)標(biāo)識(shí)符 120
5.3.5  多數(shù)派機(jī)制 121
5.3.6  Leader周期 121
5.4  ZAB描述 122
5.4.1  Leader選舉階段 122
5.4.2  成員發(fā)現(xiàn)階段 122
5.4.3  數(shù)據(jù)同步階段 123
5.4.4  消息廣播階段 124
5.4.5  算法小結(jié) 124
5.5  ZooKeeper中的ZAB實(shí)現(xiàn) 125
5.5.1  選舉階段 126
5.5.2  成員發(fā)現(xiàn)階段 129
5.5.3  數(shù)據(jù)同步階段 130
5.5.4  消息廣播階段 133
5.5.5  算法小結(jié) 134
5.5.6  算法模擬 135
5.5.7  提案的安全性 139
5.6  ZooKeeper成員變更 140
5.6.1  變更過(guò)程 141
5.6.2  并行變更 142
5.7  ZooKeeper源碼實(shí)戰(zhàn) 142
5.7.1  啟動(dòng) 142
5.7.2  Leader選舉 144
5.7.3  Follower和Leader初始化 148
5.7.4  成員發(fā)現(xiàn)階段 151
5.7.5  數(shù)據(jù)同步階段 154
5.7.6  消息廣播階段 157
5.8  本章小結(jié) 162
5.9  練習(xí)題 163
第6章  Raft——共識(shí)算法的寵兒 164
6.1  Raft簡(jiǎn)介 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  日志復(fù)制 170
6.2.3  日志對(duì)齊 173
6.2.4  幽靈日志 174
6.2.5  安全性 175
6.2.6  Raft小結(jié) 176
6.3  算法模擬 177
6.3.1  Leader選舉 177
6.3.2  日志復(fù)制 178
6.3.3  日志對(duì)齊 180
6.4  成員變更 181
6.4.1  聯(lián)合共識(shí) 182
6.4.2  工程實(shí)踐 185
6.4.3  單個(gè)成員變更 188
6.5  日志壓縮 191
6.6  網(wǎng)絡(luò)分區(qū) 192
6.6.1  成員變更中的分區(qū) 192
6.6.2  對(duì)稱網(wǎng)絡(luò)分區(qū) 193
6.6.3  非對(duì)稱網(wǎng)絡(luò)分區(qū) 194
6.7  非事務(wù)請(qǐng)求 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并行協(xié)商 198
6.8.1  亂序協(xié)商 199
6.8.2  Merge階段 200
6.9  Raft源碼實(shí)戰(zhàn)——SOFAJRaft 202
6.9.1  SOFAJRaft簡(jiǎn)介 203
6.9.2  Leader選舉 205
6.9.3  日志復(fù)制 212
6.9.4  非事務(wù)請(qǐng)求 219
6.9.5  成員變更 221
6.10  本章小結(jié) 223
6.10.1  Raft與Paxos的異同 223
6.10.2  Raft與ZAB的異同 224
6.11  練習(xí)題 225
第3篇  Paxos變種算法集合
第7章  Paxos變種算法的發(fā)展史 228
7.1  Disk Paxos簡(jiǎn)介 228
7.1.1  算法描述 229
7.1.2  Disk Paxos小結(jié) 230
7.2  Cheap Paxos簡(jiǎn)介 230
7.2.1  算法描述 231
7.2.2  Cheap Paxos小結(jié) 232
7.3  Generalized Paxos簡(jiǎn)介 233
7.4  Stoppable Paxos簡(jiǎn)介 234
7.5  Mencius簡(jiǎn)介 235
7.6  Vertical Paxos簡(jiǎn)介 237
7.6.1  算法描述 237
7.6.2  算法模擬 238
7.6.3  Vertical Paxos小結(jié) 240
7.7  本章小結(jié) 240
第8章  Fast Paxos——C/S架構(gòu)的福音 242
8.1  Fast Paxos簡(jiǎn)介 242
8.1.1  背景介紹 242
8.1.2  基本概念 243
8.2  算法詳述 244
8.2.1  算法設(shè)計(jì) 244
8.2.2  Fast Paxos模擬 245
8.2.3  Learn階段 246
8.3  Quorum推導(dǎo) 246
8.3.1  決策條件 247
8.3.2  計(jì)算Quorum 248
8.4  Classic Round簡(jiǎn)介 249
8.4.1  提案沖突 249
8.4.2  選擇提案值的規(guī)則 250
8.4.3  證明 252
8.5  提案恢復(fù) 253
8.5.1  基于協(xié)調(diào)者的恢復(fù) 253
8.5.2  基于非協(xié)調(diào)者的恢復(fù) 254
8.6  本章小結(jié) 254
第9章  EPaxos——去中心化共識(shí) 255
9.1  EPaxos簡(jiǎn)介 255
9.1.1  共識(shí)算法對(duì)比 255
9.1.2  認(rèn)識(shí)EPaxos算法 256
9.1.3  基本概念 258
9.2  協(xié)商協(xié)議 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  執(zhí)行協(xié)議 268
9.3.1  互相依賴 268
9.3.2  執(zhí)行過(guò)程 269
9.3.3  拓?fù)渑判?270
9.3.4  尋找強(qiáng)連通分量 271
9.3.5  EPaxos排序 272
9.4  算法證明 272
9.4.1  執(zhí)行的一致性 273
9.4.2  執(zhí)行的順序性 274
9.5  Optimized-EPaxos簡(jiǎn)介 274
9.5.1  Prepare階段 275
9.5.2  論證QuorumFast 278
9.6  算法模擬 279
9.6.1  協(xié)商協(xié)議 279
9.6.2  Prepare階段 282
9.7  成員變更 284
9.8  工程優(yōu)化 285
9.8.1  巨大的消息體 285
9.8.2  讀請(qǐng)求處理 285
9.9  本章小結(jié) 286
9.9.1  EPaxos與Paxos的異同 286
9.9.2  EPaxos與Raft、ZAB、Multi Paxos的異同 287
9.10  練習(xí)題 288
第4篇  番外——FLP定理
第10章  FLP——不可能定理 290
10.1  FLP定理概述 290
10.1.1  FLP簡(jiǎn)介 290
10.1.2  FLP的環(huán)境模型 290
10.1.3  Paxos為什么是正確的 291
10.2  FLP的證明 292
10.2.1  基礎(chǔ)定義 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的指導(dǎo)意義 296
　　
練習(xí)題答案 298
參考文獻(xiàn) 303