分布式高可用算法

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 (N-N)原子注册器 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 (N-N)顺序注册器 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