分布式高可用算法

1 初識(shí)分布式 1
1．1 什么是分布式系統(tǒng)1
1．2 分布式算法的意義 3
1．3 “兩將軍”問題3
1．4 設(shè)計(jì)分布式算法的主要挑戰(zhàn)8
1．4．1 并發(fā)執(zhí)行 8
1．4．2 進(jìn)程失敗 9
1．4．3 鏈路失敗 10
2 算法模型 12
2．1 I/O 自動(dòng)機(jī) 12
2．1．1 基本模型 13
2．1．2 組合模型15
2．1．3 隱藏操作 16
2．1．4 與業(yè)務(wù)邏輯的關(guān)系18
2．1．5 小結(jié) 19
2．2 編程模型 20
2．2．1 調(diào)用關(guān)系 ． 21
2．2．2 事件和事件處理器 ． 23
2．2．3 抽象和實(shí)現(xiàn) ． 25
3 系統(tǒng)模型 30
3．1 進(jìn)程 30
3．2 消息 31
3．3 進(jìn)程啟動(dòng) 32
3．4 進(jìn)程失敗 33
3．4．1 崩潰式失敗 ． 33
3．4．2 遺漏式失敗 ． 34
3．4．3 恢復(fù)后崩潰失敗 ． 35
3．4．4 拜占庭失敗 ． 36
3．4．5 各種失敗的關(guān)系 ． 37
3．5 時(shí)鐘 37
3．5．1 本地時(shí)鐘和全局時(shí)鐘 ． 37
3．5．2 因果順序不變 ． 38
3．5．3 邏輯時(shí)鐘 ． 41
3．5．4 時(shí)鐘偏移 ． 42
3．6 時(shí)間假設(shè) 43
3．6．1 異步系統(tǒng) ． 44
3．6．2 同步系統(tǒng) ． 45
3．6．3 部分同步系統(tǒng) ． 46
3．7 安全性和活性 47
3．8 組合模型 48
3．9 多數(shù)派 50
3．10 性能度量 51
4 鏈路 52
4．1 公平丟包鏈路 53
4．1．1 定義 ． 53
4．1．2 消息系統(tǒng) ． 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 先進(jìn)先出可靠鏈路 63
4．4．1 定義 ． 63
4．4．2 靜音型失敗算法 ． 63
4．5 日志可靠鏈路 65
4．5．1 定義 ． 65
4．5．2 恢復(fù)型失敗算法 ． 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 恢復(fù)失敗型算法 ． 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 統(tǒng)一可靠廣播 91
6．3．1 定義 ． 92
6．3．2 停止型失敗算法 ． 92
6．3．3 靜音型失敗算法 ． 94
6．4 頑固廣播 97
6．4．1 定義 ． 97
6．4．2 恢復(fù)型失敗算法 ． 97
6．5 概率廣播 98
6．5．1 定義 ． 99
6．5．2 隨機(jī)化算法：盡力推送 ． 100
6．5．3 隨機(jī)化算法：推拉結(jié)合 ． 106
6．6 先進(jìn)先出廣播 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 靜音型失敗算法：基于向量時(shí)間 120
7 共享內(nèi)存 124
7．1 介紹 124
7．1．1 前提假設(shè) ． 125
7．1．2 操作順序 ． 126
7．1．3 操作失敗 ． 127
7．2 (1-N)正則注冊(cè)器 ． 128
7．2．1 定義 ． 128
7．2．2 停止型失敗算法 ． 130
7．2．3 靜音型失敗算法 ． 132
7．3 (1-N)原子注冊(cè)器 ． 135
7．3．1 定義 ． 136
7．3．2 停止型失敗算法 ． 137
7．3．3 靜音型失敗算法 ． 140
7．4 (N-N)原子注冊(cè)器 144
7．4．1 定義 ． 144
7．4．2 停止型失敗算法 ． 147
7．4．3 靜音型失敗算法 ． 149
7．5 (1-N)日志正則注冊(cè)器 ． 152
7．5．1 操作順序 ． 153
7．5．2 定義 ． 153
7．5．3 恢復(fù)型失敗算法 ． 155
7．6 (N-N)順序注冊(cè)器 158
7．6．1 定義 ． 159
7．6．2 正則、順序與原子注冊(cè)器的比較 160
7．6．3 疊加性 ． 163
7．6．4 靜音型失敗算法 ． 164
7．7 因果注冊(cè)器和先進(jìn)先出注冊(cè)器 169
7．8 CAP 理論 ． 170
8 共識(shí) 173
8．1 正則共識(shí) 174
8．1．1 定義 ． 174
8．1．2 停止型失敗算法：泛洪共識(shí) 175
8．1．3 停止型失敗算法：等級(jí)共識(shí) 178
8．2 統(tǒng)一共識(shí) 180
8．2．1 定義 ． 180
8．2．2 停止型失敗算法：泛洪統(tǒng)一共識(shí) 181
8．2．3 停止型失敗算法：等級(jí)統(tǒng)一共識(shí) 184
8．3 適用于噪音型失敗模型的統(tǒng)一共識(shí) 188
8．3．1 概述 ． 188
8．3．2 代次變更 ． 189
8．3．3 代次共識(shí) ． 195
8．3．4 噪音型失敗算法 ． 200
8．3．5 Paxos 協(xié)議 ． 204
8．4 日志統(tǒng)一共識(shí) 206
8．4．1 定義 ． 206
8．4．2 日志代次變更 ． 207
8．4．3 日志代次共識(shí) ． 209
8．4．4 恢復(fù)型失敗算法 ． 213
8．5 隨機(jī)共識(shí) 215
8．5．1 定義 ． 216
8．5．2 共幣 ． 217
8．5．3 靜音型失敗算法：隨機(jī)二值正則共識(shí) 222
8．5．4 靜音型失敗算法：隨機(jī)多值正則共識(shí) 229
8．6 統(tǒng)一快速共識(shí) 231
8．6．1 定義 ． 231
8．6．2 靜音型失敗算法 ． 232
8．7 統(tǒng)一序列共識(shí) 236
8．7．1 概述 ． 236
8．7．2 定義 ． 237
8．7．3 基于單值共識(shí)的算法 ． 239
8．8 適用于噪音型失敗模型的統(tǒng)一序列共識(shí) 240
8．8．1 概述 ． 241
8．8．2 代次序列共識(shí) ． 241
8．8．3 噪音型失敗算法 ． 252
8．8．4 Multi-Paxos 和Raft 協(xié)議 254
9 共識(shí)的應(yīng)用 256
9．1 全序廣播 256
9．1．1 定義 ． 258
9．1．2 算法：基于共識(shí)的全序廣播 259
9．2 復(fù)制狀態(tài)機(jī) 263
9．2．1 定義 ． 263
9．2．2 算法：基于全序廣播的狀態(tài)復(fù)制 264
9．3 信號(hào)量 265
9．3．1 定義 ． 265
9．3．2 算法：基于全序廣播的信號(hào)量 267
9．4 原子提交 270
9．4．1 介紹 ． 271
9．4．2 定義 ． 272
9．4．3 停止型失敗算法：基于共識(shí)的非阻塞式原子提交 273
9．5 組成員關(guān)系 276
9．5．1 定義 ． 277
9．5．2 停止型失敗算法：基于共識(shí)的組成員關(guān)系 278
9．6 可停止全序廣播 280
9．6．1 定義 ． 281
9．6．2 停止型失敗算法：基于共識(shí)的可停止全序廣播 283
9．7 可重配復(fù)制狀態(tài)機(jī) 287
9．7．1 進(jìn)程的加入和離開 ． 288
9．7．2 定義 ． 289
9．7．3 停止型失敗算法：基于可停止全序廣播 291
10 基于時(shí)鐘的算法 295
10．1 包含時(shí)鐘的時(shí)間假設(shè) 295
10．2 基于時(shí)鐘同步的失敗檢測 297
10．2．1 完美失敗檢測 ． 297
10．2．2 最終完美失敗檢測 ． 299
10．3 基于網(wǎng)絡(luò)同步的虛擬時(shí)鐘 301
10．3．1 定義 ． 302
10．3．2 停止型失敗算法 ． 302
10．4 時(shí)鐘同步與網(wǎng)絡(luò)同步的等價(jià)性 303
10．5 實(shí)時(shí)操作系統(tǒng)的意義 305
11 結(jié)束語 306
參考文獻(xiàn) 307