本書從原理出發(fā)，系統(tǒng)性地介紹了分布式系統(tǒng)和算法，而非介紹如何使用某種分布式框架。本書首先介紹了分布式系統(tǒng)是如何被建模的，以及分布式算法是如何被描述的，然后從基礎(chǔ)的鏈路抽象開(kāi)始逐步增加復(fù)雜度，最終將復(fù)雜的共識(shí)抽象以簡(jiǎn)單的方式呈現(xiàn)在讀者面前。通過(guò)閱讀本書，讀者不僅可以掌握常用的分布式算法，還可以學(xué)到分布式算法的證明方法及適用條件，為自行設(shè)計(jì)分布式系統(tǒng)和算法打下堅(jiān)實(shí)的基礎(chǔ)。本書適合分布式領(lǐng)域的初學(xué)者及相關(guān)從業(yè)者閱讀參考。
1 初識(shí)分布式 1
1.1 什么是分布式系統(tǒng)1
1.2 分布式算法的意義 3
1.3 “兩將軍”問(wèn)題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 其他說(shuō)明 69
5 失敗檢測(cè)和選主 70
5.1 失敗檢測(cè) 70
5.2 完美失敗檢測(cè) 71
5.2.1 定義 . 71
5.2.2 停止型失敗算法 . 71
5.3 最終完美失敗檢測(cè) 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)程的加入和離開(kāi) . 288
9.7.2 定義 . 289
9.7.3 停止型失敗算法：基于可停止全序廣播 291
10 基于時(shí)鐘的算法 295
10.1 包含時(shí)鐘的時(shí)間假設(shè) 295
10.2 基于時(shí)鐘同步的失敗檢測(cè) 297
10.2.1 完美失敗檢測(cè) . 297
10.2.2 最終完美失敗檢測(cè) . 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é)束語(yǔ) 306
參考文獻(xiàn) 307
書單推薦
