分佈式高可用算法

1 初識分佈式1
1.1 什麼是分佈式系統1
1.2 分佈式算法的意義3
1.3 “兩將軍”問題3
1.4 設計分佈式算法的主要挑戰8
1.4.1 並發執行8
1.4.2 進程失敗9
1.4.3 鏈路失敗10

2 算法模型12
2.1 I/O 自動機12
2.1.1 基本模型13
2.1.2 組合模型15
2.1.3 隱藏操作16
2.1.4 與業務邏輯的關係18
2.1.5 小結19
2.2 編程模型20
2.2.1 調用關係. 21
2.2.2 事件和事件處理器. 23
2.2.3 抽象和實現. 25

3 系統模型30
3.1 進程30
3.2 消息31
3.3 進程啟動32
3.4 進程失敗33
3.4.1 崩潰式失敗. 33
3.4.2 遺漏式失敗. 34
3.4.3 恢復後崩潰失敗. 35
3.4.4 拜占庭失敗. 36
3.4.5 各種失敗的關係. 37
3.5 時鐘37
3.5.1 本地時鐘和全局時鐘. 37
3.5.2 因果順序不變. 38
3.5.3 邏輯時鐘. 41
3.5.4 時鐘偏移. 42
3.6 時間假設43
3.6.1 異步系統. 44
3.6.2 同步系統. 45
3.6.3 部分同步系統. 46
3.7 安全性和活性47
3.8 組合模型48
3.9 多數派50
3.10 性能度量51

4 鏈路52
4.1 公平丟包鏈路53
4.1.1 定義. 53
4.1.2 消息系統. 54
4.2 頑固鏈路57
4.2.1 定義. 57
4.2.2 靜音型失敗算法. 57
4.3 可靠鏈路60
4.3.1 定義. 61
4.3.2 靜音型失敗算法. 61
4.4 先進先出可靠鏈路63
4.4.1 定義. 63
4.4.2 靜音型失敗算法. 63
4.5 日誌可靠鏈路65
4.5.1 定義. 65
4.5.2 恢復型失敗算法. 66
4.6 其他說明69

5 失敗檢測和選主70
5.1 失敗檢測70
5.2 完美失敗檢測71
5.2.1 定義. 71
5.2.2 停止型失敗算法. 71
5.3 最終完美失敗檢測73
5.3.1 定義. 73
5.3.2 噪音型失敗算法. 74
5.4 選主76
5.4.1 定義. 76
5.4.2 停止型失敗算法. 77
5.5 最終選主78
5.5.1 定義. 79
5.5.2 噪音型失敗算法. 79
5.5.3 恢復失敗型算法. 81

6 可靠廣播85
6.1 盡力廣播85
6.1.1 定義. 86
6.1.2 靜音型失敗算法. 86
6.2 正則可靠廣播87
6.2.1 定義. 87
6.2.2 停止型失敗算法. 88
6.2.3 靜音型失敗算法. 90
6.3 統一可靠廣播91
6.3.1 定義. 92
6.3.2 停止型失敗算法. 92
6.3.3 靜音型失敗算法. 94
6.4 頑固廣播97
6.4.1 定義. 97
6.4.2 恢復型失敗算法. 97
6.5 概率廣播98
6.5.1 定義. 99
6.5.2 隨機化算法：盡力推送. 100
6.5.3 隨機化算法：推拉結合. 106
6.6 先進先出廣播112
6.6.1 定義. 113
6.6.2 靜音型失敗算法. 113
6.7 因果可靠廣播115
6.7.1 定義. 115
6.7.2 靜音型失敗算法. 116
6.7.3 停止型失敗算法. 118
?6.7.4 靜音型失敗算法：基於向量時間120

7 共享內存124
7.1 介紹124
7.1.1 前提假設. 125
7.1.2 操作順序. 126
7.1.3 操作失敗. 127
7.2 (1-N)正則註冊器. 128
7.2.1 定義. 128
7.2.2 停止型失敗算法. 130
7.2.3 靜音型失敗算法. 132
7.3 (1-N)原子註冊器. 135
7.3.1 定義. 136
7.3.2 停止型失敗算法. 137
7.3.3 靜音型失敗算法. 140
7.4 (NN)原子註冊器144
7.4.1 定義. 144
7.4.2 停止型失敗算法. 147
7.4.3 靜音型失敗算法. 149
7.5 (1-N)日誌正則註冊器. 152
7.5.1 操作順序. 153
7.5.2 定義. 153
7.5.3 恢復型失敗算法. 155
7.6 (NN)順序註冊器158
7.6.1 定義. 159
7.6.2 正則、順序與原子註冊器的比較160
7.6.3 疊加性. 163
7.6.4 靜音型失敗算法. 164
7.7 因果註冊器和先進先出註冊器169
7.8 CAP 理論. 170

8 共識173
8.1 正則共識174
8.1.1 定義. 174
8.1.2 停止型失敗算法：泛洪共識175
8.1.3 停止型失敗算法：等級共識178
8.2 統一共識180
8.2.1 定義. 180
8.2.2 停止型失敗算法：泛洪統一共識181
8.2.3 停止型失敗算法：等級統一共識184
8.3 適用於噪音型失敗模型的統一共識188
8.3.1 概述. 188
8.3.2 代次變更. 189
8.3.3 代次共識. 195
8.3.4 噪音型失敗算法. 200
8.3.5 Paxos 協議. 204
8.4 日誌統一共識206
8.4.1 定義. 206
8.4.2 日誌代次變更. 207
8.4.3 日誌代次共識. 209
8.4.4 恢復型失敗算法. 213
8.5 隨機共識215
8.5.1 定義. 216
8.5.2 共幣. 217
8.5.3 靜音型失敗算法：隨機二值正則共識222
8.5.4 靜音型失敗算法：隨機多值正則共識229
8.6 統一快速共識231
8.6.1 定義. 231
8.6.2 靜音型失敗算法. 232
8.7 統一序列共識236
8.7.1 概述. 236
8.7.2 定義. 237
8.7.3 基於單值共識的算法. 239
8.8 適用於噪音型失敗模型的統一序列共識240
8.8.1 概述. 241
8.8.2 代次序列共識. 241
8.8.3 噪音型失敗算法. 252
8.8.4 Multi-Paxos 和Raft 協議254

9 共識的應用256
9.1 全序廣播256
9.1.1 定義. 258
9.1.2 算法：基於共識的全序廣播259
9.2 複製狀態機263
9.2.1 定義. 263
9.2.2 算法：基於全序廣播的狀態復制264
9.3 信號量265
9.3.1 定義. 265
9.3.2 算法：基於全序廣播的信號量267
9.4 原子提交270
9.4.1 介紹. 271
9.4.2 定義. 272
9.4.3 停止型失敗算法：基於共識的非阻塞式原子提交273
9.5 組成員關係276
9.5.1 定義. 277
9.5.2 停止型失敗算法：基於共識的組成員關係278
9.6 可停止全序廣播280
9.6.1 定義. 281
9.6.2 停止型失敗算法：基於共識的可停止全序廣播283
9.7 可重配複製狀態機287
9.7.1 進程的加入和離開. 288
9.7.2 定義. 289
9.7.3 停止型失敗算法：基於可停止全序廣播291

10 基於時鐘的算法295
10.1 包含時鐘的時間假設295
10.2 基於時鐘同步的失敗檢測297
10.2.1 完美失敗檢測. 297
10.2.2 最終完美失敗檢測. 299
10.3 基於網絡同步的虛擬時鐘301
10.3.1 定義. 302
10.3.2 停止型失敗算法. 302
10.4 時鐘同步與網絡同步的等價性303
10.5 實時操作系統的意義305

11 結束語306
參考文獻307