分布式高可用算法

本书从原理出发，系统性地介绍了分布式系统和算法，而非介绍如何使用某种分布式框架。本书首先介绍了分布式系统是如何被建模的，以及分布式算法是如何被描述的，然后从基础的链路抽象开始逐步增加复杂度，终将复杂的共识抽象以简单的方式呈现在读者面前。通过阅读本书，读者不仅可以掌握常用的分布式算法，还可以学到分布式算法的证明方法及适用条件，为自行设计分布式系统和算法打下坚实的基础。本书适合分布式领域的初学者及相关从业者阅读参考。

本书从原理出发，系统性地介绍了分布式系统和算法，而非介绍如何使用某种分布式框架。本书首先介绍了分布式系统是如何被建模的，以及分布式算法是如何被描述的，然后从基础的链路抽象开始逐步增加复杂度，最终将复杂的共识抽象以简单的方式呈现在读者面前。通过阅读本书，读者不仅可以掌握常用的分布式算法，还可以学到分布式算法的证明方法及适用条件，为自行设计分布式系统和算法打下坚实的基础。本书适合分布式领域的初学者及相关从业者阅读参考。

江峰，教授级高工，中国电信集团云计算专业首席专家，中国计算机学会信息存储专委会委员。长期在分布式存储领域从事理论研究和工程实践工作。

受内容分发网络(CDN)的启发，在业内首次提出和设计了“为写而生”的内容存储网络(CSN)——CTOOS。CTOOS实现了广域分布式海量数据存储服务的高可用、低时延和强一致，达到了单命名空间跨池数十个、实存容量过EB的规模，并长期稳定运行，为企业创造了可观的收益，技术水平达到了国内领先。

以作者在国际期刊会议上发表论文多篇，以发明人申请专利十多件，以完成人获得省部级、中国电信集团科技进步奖多次。

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

本书从原理出发，系统性地介绍了分布式系统和算法，而非介绍如何使用某种分布式框架。本书首先介绍了分布式系统是如何被建模的，以及分布式算法是如何被描述的，然后从基础的链路抽象开始逐步增加复杂度，终将复杂的共识抽象以简单的方式呈现在读者面前。通过阅读本书，读者不仅可以掌握常用的分布式算法，还可以学到分布式算法的证明方法及适用条件，为自行设计分布式系统和算法打下坚实的基础。本书适合分布式领域的初学者及相关从业者阅读参考。

江峰，教授级高工，中国电信集团云计算专业首席专家，中国计算机学会信息存储专委会委员。长期在分布式存储领域从事理论研究和工程实践工作。

受内容分发网络(CDN)的启发，在业内首次提出和设计了“为写而生”的内容存储网络(CSN)——CTOOS。CTOOS实现了广域分布式海量数据存储服务的高可用、低时延和强一致，达到了单命名空间跨池数十个、实存容量过EB的规模，并长期稳定运行，为企业创造了可观的收益，技术水平达到了国内领先。

以作者在国际期刊会议上发表论文多篇，以发明人申请专利十多件，以完成人获得省部级、中国电信集团科技进步奖多次。