分布式高可用算法

"《分布式高可用算法》是市面上少有的系统性阐述分布式系统底层架构原理的著作。
长期以来，在996的工作压力下，工程师们更重视实践中的技巧，力求快速解决眼前的问题，而鲜有时间关注问题背后的底层原理。表面看来，这种做法提高了工作效率，但实际上，这样容易形成“头疼医头，脚疼医脚”的思维和工作方式，难以工程中的问题，也难以形成长效的机制，无法透彻地剖析系统工程，从而埋下了众多隐患。
本书作者洞悉了这一本质难题。《分布式高可用算法》结合作者在本领域十余年的丰富实践，不仅剖析了经典算法背后的逻辑，而且深入浅出地分析了每个经典算法在实践中的应用思路，让人知其然并知其所以然，举一反三。
《分布式高可用算法》在表达上通俗易懂，即便是刚入门的新手，读完本书也能有“哦，原来是这样！”的体会；对于已在本领域工作多年的工程师，相信在读完本书之后，也会有豁然开朗的感觉，领悟到算法的精妙之处，从而更好地指导工作。"

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

"江峰，教授级高工，中国电信集团云计算专业首席专家，中国计算机学会信息存储专委会委员。长期在分布式存储领域从事理论研究和工程实践工作。
受内容分发网络(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

"本书从算法与系统模型开始，详细论述了分布式系统涉及的链路、失败检测和选主、可靠广播、共享内存、共识、基于时钟的算法等核心内容，这些知识是构建大型分布式系统的底层架构时需要使用的，也是比较有难度和复杂性的内容。本书以算法为主线组织内容，提供了各个算法的原理解释和伪码，具有较高的实用性和方便性。
CAP理论是我的导师、美国国家工程院院士Eric？Brewer教授提出来的，也是分布式系统领域的定理之一。本书作者从分布式系统模型的角度指出CAP定理与其他分布式抽象的不同之处，令我耳目一新，这说明作者对分布式系统已经有了独到的见解。
该书既适合分布式领域的初学者阅读，也能引起分布式领域专家的诸多思考，是的高质量分布式系统书籍。现阶段，国内关于分布式框架背后算法和原理的书籍很少，希望该书的出版能够促进国内更多的研究者关注分布式框架的创新，促进我国分布式计算领域的发展。
周枫
网易集团高级副总裁，网易有道首席执行官、首席架构师

本书是分布式系统的理论体系类书籍，在第一次阅读时也许会觉得略为抽象，但一旦进入实际场景，就会发现遇到的各类问题其实都和理论的不同层面相关。此时再来拜读，就会发现先贤们其实已经整理好了各类解法——因此，只要熟练掌握体系框架，就一定能找到最符合业务实际需要的很优解——这就是本书的重要价值。
根据我自己这十几年在互联网行业解决各类实际问题的经历，大部分技术问题的解决，归根结底，都是一个依托于分布式系统理论范式、根据实际业务需求做取舍的过程。本书洞悉了这一本质，它从整个分布式系统的理论根基出发，阐述分布式系统中会面临的各类问题及其解法，非常有助于工程师在实践中找到问题症结并迅速解决之。相信每一位有志于在分布式领域内有所建树的读者都会从中获益。
沈询
阿里巴巴资深技术专家，阿里分布式数据层、分布式消息服务负责人

很荣幸，提前拜读了江峰老师这本《分布式高可用算法》前三章的内容，本以为分布式系统会非常复杂，算法会非常枯燥，没想到读完第1章后，这个刻板的印象就接近被颠覆了，一个通俗易懂的“两将军”就让我感受到了分布式共识算法的巨大威力！本书兼顾深度和广度，由浅入深地介绍了分布式系统的方方面面，非常值得一读！
沉默王二
《Java程序员进阶之路》作者，CSDN两届博客之星"