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

编写背景 分布式系统无处不在。一台计算机内部多个互联的处理器组成了一个分布式系统，它们通过“一致性缓存”算法使每个处理器核心看到相同的数据。近三十年来，随着互联网的发展，越来越多的互联网后台系统采用计算机集群的方式来应对海量请求和数据的需求，这个计算机集群也是分布式系统。 为了简化分布式系统的开发，出现了很多为开发者提供分布式框架的开源项目，例如Apache 基金会旗下的ZooKeeper 项目就是一个应用广泛的分布式框架。同时，国内也有很多关于如何使用这些分布式框架来搭建应用的书籍，它们极大地推动了分布式系统在国内的应用。我们不仅要知道如何使用这些现成的分布式框架来搭建应用，而且应该知道这些分布式框架背后的设计原理，做到“知其然，亦知其所以然”。这就是作者撰写本书的主要目的。 本书尝试以通俗易懂的方式从理论的角度系统性地介绍分布式系统和算法，使读者不仅从算法层面知道诸如共享内存、共识、信号量等分布式抽象背后的工作原理，还知道分布式系统是如何被建模的，进而知道这些算法是怎么来的、为什么是对的、适用场景是什么，为将来自行设计分布式算法打下基础。 本书对算法的描述与具体的编程语言无关，掌握任何一种编程语言、学习过《操作系统》和《计算机网络》两门课程的人，都能学懂本书绝大部分内容。 不过，学习算法从来都不是轻松简单的过程，再通俗的语言也无法降低算法本身的复杂度，否则本书就不是一本算法书，而“退化”成科普书了。尤其是本书第2 章中介绍的I/O 自动机，初次接触的读者学习起来可能会比较吃力。但作为分布式系统的理论基础， 作者不得不介绍它，否则读者难以理解后面的算法。 本书内容 第1 章介绍什么是分布式系统，分布式算法的用处，以及设计分布式算法面临的主要挑战，让读者对本书所介绍的分布式系统和算法的范围有初步认识。 第2 章介绍算法模型。分布式算法是一种并发执行算法，与顺序执行算法在模型上有很大的差异。本章首先介绍I/O 自动，这是描述分布式系统的理论模型；然后介绍基于I/O 自动机的编程模型，后续章节的所有算法都基于这套编程模型描述。通过本章的学习，读者将意识到设计分布式算法就是在定义自动机与外界的交互行为，并且能够阅读分布式算法。 第3 章介绍系统模型。分布式系统十分复杂，我们需要从复杂的现象中抽象出本质，这个过程就是系统建模。本章主要介绍进程、消息、链路和时钟等组成分布式系统的关键组件，并对它们的行为特性进行抽象。这些行为特征包括进程和链路会如何失败、网络时延和时钟快慢对系统有什么影响等。本章还会介绍一些重要的概念，包括同步系统、异步系统等时间假设，安全性和活性这两个既对立、又统一的特性，以及如何评价分布式算法的性能等。通过本章的学习，读者将掌握设计一个分布式系统主要的关注点。 第4 章介绍链路，从基础的公平丢包链路开始，依次定义和实现顽固链路、可靠链路、先进先出可靠链路、日志可靠链路等，为后续章节的学习打下基础。这部分算法看起来很简单，但深入理解却不容易，例如，为什么链路抽象中会存在这种看似性能低效的顽固链路，等等。通过本章的学习，读者不仅会更熟悉编程模型，而且将更深入地理解自动机和它的生命周期。 第5 章介绍失败检测和选主。之所以把失败检测和选主单独作为一章来介绍，是因为它们是分布式算法的基础，刻画了分布式系统的时间假设。通过本章的学习，读者将知道如何进行失败检测和选主，什么系统能够进行失败检测和选主，什么系统无法进行失败检测和选主。 第6 章介绍广播，从基础的尽力广播开始，依次介绍正则可靠广播、统一可靠广播、顽固广播、概率广播、先进先出广播和因果可靠广播。不同的广播有不同的特性，例如尽力广播是代价最低的广播，也是能力最有限的广播；统一可靠广播最大的特点是，所有进程要么都接收消息，要么都不接收消息，有很好的统一性；概率广播，即Gossip 协议，则适合于超大规模的分布式系统；而因果广播能确保接收进程看到的消息符合因果顺序。 通过本章的学习，读者将可以根据需要灵活地选择不同的广播。第7 章介绍共享内存，也叫注册器。本章主要介绍多种不同一致性要求的注册器，包括正则注册器、原子注册器、顺序注册器、因果注册器和先进先出注册器。同时，根据读写进程数量的不同，还介绍了单写多读、多写多读等不同的注册器。本章最后介绍和证明了CAP 理论，并揭示了它的独特之处。注册器在分布式系统中有着极为广泛的应用，例如分布式缓存、内存、存储、数据库等，都是注册器的应用。 第8 章介绍共识。共识是分布式系统得以实现高可用和一致性的关键技术。根据统一性的不同，本章主要介绍正则共识、统一共识这两种共识。同时，又根据不同的时间假设和进程失败假设，针对正则共识和统一共识介绍了多种实现算法，其中包括Paxos 协议、随机共识，以及统一快速共识等。最后介绍了序列共识，并对Multi-Paxos 和Raft 协议进行了对比。通过本章的学习，读者将对共识的本质有更深刻的认识。 第9 章介绍基于共识的应用，包括全序广播、复制状态机、信号量、原子提交（事务）、组成员关系等。最后还会介绍复制状态机的重配技术，实现进程动态地加入和离开系统。在ZooKeeper、etcd 等开源分布式框架中的Reconfiguration 功能的背后，其实就是复制状态机的重配技术。 第10 章介绍基于时钟的算法。本章介绍如何利用时钟同步系统构造网络同步系统，以及如何利用网络同步系统构造时钟同步系统，从而证明了时钟同步与网络同步的等价性。基于这一等价性，读者可以利用现代计算机的本地时钟、时钟同步协议以及原子钟等技术弥补网络的不足，即使在网络异步的情况下，也可以实现同步系统。 以上为本书内容。 致谢 对于工程师而言，写书并非易事，尤其是写一本通俗易懂而又不失严谨性的算法书。有时我在电脑前坐了一整天，竟写了不到一页纸的内容，曾经数百个夜晚、周末和节假日都献给了本书。 首先，我要感谢我的家人，没有他们的理解和支持，就没有这本书。其次，我要感谢我曾经和目前工作的两家公司。网易将我带入了专业领域的大门，我要感谢邓毅、吴迎晖、周枫等领导对我的指导；中国电信给了我长期耕耘、奋斗的机会和 平台，我要感谢余尔东、李桐、杨超、林叶、赵文韬、董昌坤、魏玮等同事对我的帮助，广小明、王峰、张成良、吴湘东、胡志强、黄礼莲、雷葆华等历任领导的支持，以及李正茂、韦乐平、高同庆等集团领导对我的关心（以上人名均按姓氏笔画数排序）。没有这两段宝贵的工作经历，也不会有这本书。 然后，我要感谢在撰写本书过程中给予我帮助和指导的各位专家。中国电信的张涛博士、秦伯卿博士、惠钊老师、程咏阳博士（按姓氏笔画数排序）参与了诸多讨论，并纠正了初稿中的诸多错误；龙芯中科的胡伟武老师指出了本书中的一些不足；福州大学的钱慧教授在百忙之中针对算法证明提供了帮助。还有很多为本书提供了宝贵建议的领导、同事和朋友，不一而足，在此一并感谢！ 最后，我要感谢为本书顺利出版而提供大力支持的电子工业出版社的编辑！

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