我一直在学习有关分布式系统的知识，学习时间不算短了。老实说，只要你开始钻研分布式系统，知识点好像学不完似的，一个接一个。分布式系统领域的文献太多了，包括许多大学发表的论文，还有很多书籍可选。像我这样的绝对新手，很难决定应该阅读哪些论文或者购买哪些书籍。
同时，我还发现了几位博客作者在博客中推荐这篇或那篇论文，声称这是分布式系统工程师必须知道的（不要担心这个词的意思）。因此，我的阅读列表越来越长：FLP,Zab,时间,分布式系统中的时钟和事件顺序，Viewstamped Replication,Paxos,Chubby，等等。问题是，他们经常不解释为什么要读这篇或那篇论文。我非常喜欢这个想法，以满足好奇心，不分主次学习所有知识。然而，我们仍然应该确定不同内容的阅读优先级。毕竟，每天只有 24 小时呀。
除了大量的论文和研究材料外，分布式系统领域还有许多书籍。我买了很多书。当我读到这一章时，我发现有些书的标题很有吸引力。这似乎是我感兴趣的内容，但事实并非如此。换句话说，这些书的内容并不涉及我想解决的问题。
在写这篇博客的同时，我还在继续学习分布式系统的知识，所以请有点耐心，明白这篇文章不可避免地会有错误。我将尽我最大的努力来扩展我写的内容。
在这里，我想告诉你，我已经在几次会议上谈到了博客的内容和演讲：What We Talk About When We Talk About Distributed Systems
我在斯德哥尔摩 Erlang 用户大会上的演讲视频：What We Talk About When We Talk About Distributed Systems
主要概念
确定分布式系统算法的分类主要是基于理解算法的各种属性。例如，定时模型、过程间通信类型和故障模型等。
本文所涉及的主要概念包括：
- 时序模型（Timing Model）
- 进程间通信（Interprocess Communication）
- 失效模式（Failure Modes）
- 失效检测器（Failure Detectors）
- 领导人选举（Leader Election）
- 共识（Consensus）
- 法定人数（Quorums）
- 分布式系统中的时间
- 快速浏览 FLP
- 结束语
- 参考文献
时序模型
有三种时序模型：同步模型、异步模型和部分同步模型。
使用最简单。所有组件都在所谓的同步轮中（synchronous round）算法步骤同时执行。在同步模型中，已知消息传输的耗时，确定每个过程的速度，即确定每个过程执行算法步骤的耗时。同步模型的主要问题是它不能很好地反映现实世界，与分布式系统有更大的不同。在分布式系统中，我们向另外一个进程发送消息，肯定希望自己行大运，因为只有这样，才能保证消息一定发送到目标进程。幸运的是，我们可以利用同步模型获得理论结果，然后将结果转换为其他模型。例如，，如果一个问题不能在同步模型中解决，那么没有时间保证（例如，完美的故障检测器就是这样一个模型），就更不可能解决这个问题。
使用相对复杂。在异步模型中，算法步骤的执行顺序由每个组件决定，每个步骤的耗时性没有保证。虽然异步模型的描述非常简单，更接近现实世界，但它仍然不能正确地反映现实世界。例如，在异步模型中，过程响应请求的时间可能无限长，但在实际项目中，请求通常设置加班限制。如果在此期间没有响应，请求将被暂停并报告异常。异步模型带来的一个（liveness condition）。最著名的不可能结果之一是异步模型：只要有一个过程可能无效，就不可能达成共识。（Impossibility of Consensus with one Faulty Process），也就是说，不可能区分以下两种情况:(1)过程无效；(2)过程无效，但它需要无限长的时间来响应消息。
在在中间，每个组件都知道一些关于定时的信息。他们要么使用近似同步时钟，要么大致了解消息传输的耗时或每个过程执行算法步骤的耗时。
Nancy Lynch 书《分布式算法》是根据上述三种定时模型组织的。
进程间通信
本部分讨论了如何在分布式系统的不同过程之间交换信息，包括两类：
- ：相互发送信息的过程；
- ：不同的进程读写共享的变量，实现数据的共享。
记住，我们可以做到：。可读可写寄存器就是这样一种实现，在许多分布式系统书籍中都可以看到。一些作者还使用队列和堆栈来描述一致性，例如线性化（linearizabilty）。不要混淆共享内存的两个含义：一是读写不同过程中相同的共享变量，这是实现数据共享的一种方式；二是新闻传输上构建的共享内存抽象。
在理解基于信息传输模型的算法时，还必须找出过程之间的链接（可以理解为过程之间的信道）。不同类型的链接抽象为算法提供不同的保证。例如，完美的链接可以保证信息的可靠交付，而不会重复发送信息；它确保信息只交付一次。显然，现实世界并非如此。当算法设计师尽可能接近真实模型时，他们会使用其他类型的链接抽象。请记住，即使完美的链接不是那么真实，它仍然有用。例如，如果我们能证明，即使链接是完美的，我们也无法解决某个问题，那么所有相关的问题都将是不可解决的。在讨论链接时，研究者通常会假定消息顺序是“先入先出”的，Zab就是一个例子。
失效模式
我以前写过一篇关于分布式系统中的故障模式的文章，但它仍然值得在这里过程故障模式是分布式系统模型的属性，是对过程故障类型的假设。假设过程是正确的，直到它崩溃；崩溃后，过程不会恢复。，过程崩溃后会恢复。一些算法也将过程恢复到崩溃前的状态。要做到这一点，恢复过程要么从持久存储中读取以前的数据，要么与同一组的其他过程，以获取所需的数据。需要指出的是，在一些群组成员算法中，崩溃后恢复的过程并不等同于崩溃前的原始过程。两者是否相等取决于是动态组还是固定组。
另一种失效模式称为失效模式（omission failure mode），假设过程不能接收或发送消息。有两种忽略：过程无法收到消息，或过程无法发送消息。为什么要明白这一点？想想这种情景，实现分布式缓存的一组进程，如果其中一个进程无法应答其他进程的请求，只要它能收到其他进程的请求，那么这个进程的状态就是最新的，它仍然可以响应来自客户的读请求。
一种更复杂的失效模式称为（Byzantine or arbitrary failures mode）：这个过程可能会向同伴发送错误的信息；这个过程可能是假装的；响应其他过程的数据是正确的，但篡改了当地数据库的内容，等等。
在设计分布式系统时，必须考虑要处理的过程故障类别。Birman (见《可靠分布式系统指南》)认为，一般来说，我们不需要处理拜占庭失败。他引用了它 Yahoo! 完成的工作得出结论：崩溃比拜占庭更常见。
失效检测器
假设定期模型和过程故障模式，我们可以构建一个抽象的故障检测器，报告系统状态，即检测一个过程是否已经崩溃，或怀疑过程是否已经崩溃。完美的障检测器从不虚报过程故障。假设系统是崩溃-结束故障模式和同步定时模型，我们只需使用加班就可以实现一个完美的故障检测器：需要定期向检测器报告过程，报告信息肯定可以交付给故障检测器（同步模型可以确保此）；如果报告信息没有如期交付，我们可以得出结论，过程已经崩溃。
在实际系统中，不能假设消息传递的耗时，也不能保证每个步骤的耗时。在这个时候，我们可以建立一个故障检测器 _p_ ，如果进程 _q_ 在超时限制 _N_ 如果毫秒内没有答案，检测器将报告过程 _q_ 可能已经崩溃了。如果后来 _q_ 又开始回答，然后 _p_ 将把 _q_ 从怀疑已经崩溃的名单中删除。因为检测器不知道它和它和它 _q_ 实际网络之间的延迟，不想再推迟了 _q_ 添加到怀疑名单中(事实已经证明了) _q_ 没有崩溃)，所以会增加 _N_ 取值，保证 _q_ 有足够的时间报到。如果在某个时间点 _q_ 它真的崩溃了检测器首先将其列入怀疑名单，并将其保留在那里（因为 _q_ 永远不要再报告了)。要理解这个算法，请阅读《可靠安全的分布式程序设计指南》一书中的最终完美故障检测器部分。
故障检测器通常有两个属性：完整性和精度。最终完美的故障检测器有：
- 最后，每一次崩溃的过程都会被每一个正常运行的过程永久怀疑；
- 最后，其他正常过程会怀疑没有正常运行的过程。
在异步模型中，故障检测器是解决共识问题的关键。FLP本文提出了许多著名的不可能结果。本文指出，在异步分布式系统中，如果过程可能无效，则不可能达成共识。为了达成共识，系统必须引入一个可以避免上述问题的故障探测器。
领导人选举
与故障检测相反的一个问题是如何判断一个过程没有崩溃，因此它是正确的地工作。网络中其他进程会信赖这个进程，把它当作能够协调分布式行动的领导人。像 Raft 或者 Zab 这样的协议就依赖领导人进程来协调行动。
协议中有一个领导人，意味着不同节点的地位变得不对称，非领导人节点将成为跟随者。。选择什么协议，取决于我们要解决什么样的问题。有时，我们并不想使用需要领导人选举的协议。记住，大部分通过某种共识获得一致性的协议，都包含一个领导人进程和一组跟随者进程。这样的例子包括 Paxos 、 Zab 或者 Raft 。
共识
共识（consensus 或 agreement）问题是由 Pease ， Shostak 和 Lamport 在论文“在存在失效的情况下达成一致”首先提出来的。他们是这么描述的：
容错系统通常要求提供一种手段，使得独立的处理器或者进程能够达成某种精确的相互一致。例如，一个冗余系统的多个处理器可能需要定期同步它们的内部时钟。或者每个处理从某个时变的输入传感器读取的数值都有稍微不同，它们需要确定一个统一的值。
所以，共识是指独立的进程之间达成一致。针对某一个问题，这些进程提议了一些值，像它们的传感器的当前取值，然后根据这些值就共同的行动达成一致。例如，一辆轿车包含多个提供刹车温度水平信息的传感器。这些传感器的读数可能不同，因为它们的精度等不一样。但是汽车的防抱死制动系统需要它们达成一致，这样才能确定需要施加多少压力给刹车。这就是一个在我们日常生活中解决的共识问题。《容错的实时系统》这本书解释了在汽车行业的分布式系统中遇到的共识及其他问题。
实现某种形式共识的进程，。在共识的开始阶段，进程提议一个值，然后根据系统中提议的所有值，决定一个最终的值。共识算法必须满足下列属性：终止（Termination）、合法性（Validity）、诚实（Integrity）和一致性（Agreement）。例如，对于常规共识，
- 每一个正确的进程最终都会决定一个值；
- 如果某个进程最终决定取值是 _v_ ，那么这个 _v_ 必然是由某个进程提议的；
- 没有进程会决定两次；
- 两个正确的进程，它们的决定不会不同。
更多细节，请参考上面提到的原始论文。还有一些很棒的参考书：
- 《可靠且安全的分布式程序设计导论》第 5 章
- 《同步消息传递系统中的容错一致》
- 《容错、异步分布式系统中的通信与一致抽象》
法定人数
法定人数（Quorum）是设计容错分布式系统的工具，它是能表征系统特征的进程的交集，其中某些进程有可能失效。
举个例子，假设某个算法遵循崩溃失效模式，由 _N_ 个进程组成。只要大多数进程成功地应用了某个操作（例如，写入数据库），就可以说已经有了进程的法定人数。只要只有少数进程崩溃，即不超过 _N/2-1_ 个进程崩溃，那么大多数进程仍然知晓应用到系统的最后操作。例如，Raft在提交日志到系统时就用到了由大多数进程构成的法定人数。领导人向跟随者发出日志复制请求，只要有一半的服务器有应答，领导人立即把这一日志项应用到它的状态机。领导人加上一半服务器，已经构成了大多数。这样做的好处是， Raft 不必等待所有的服务器都应答日志复制的 RPC 请求之后才开始复制操作。
再举一个例子，限定每次只能有一个进程可以访问共享的资源。保卫资源的进程组成了集合 _S_ 。当进程 _p_ 要访问资源时，它首先要向 _S_ 中的大多数进程征求许可，大多数进程授权它可以访问资源。现在，系统中另外一个进程 _q_ 也要访问这个资源，但是它永远获得不了大多数保卫进程的许可和授权。只有当进程 _p_ 释放资源后，进程 _q_ 才有可能访问这个资源。更多细节，见论文“法定人数系统的负载、容量和可用性”。
法定人数并不总是指进程的大多数。有时，为了保证操作的成功，需要更多的进程形成法定人数，例如，由 _N_ 个可能出现拜占庭失效的进程构成的进程组。此时，如果 _f_ 表示可容忍的最多失效进程数，那么法定人数将是大于 _(N + f) / 2_ 。参见 《可靠且安全的分布式程序设计导论》。
如果你对这个话题感兴趣，有一本专门讲分布式系统法定人数的书：
《法定人数系统及其在存储和共识中的应用》
分布式系统中的时间
理解时间及其后果，是分布式系统最大的问题之一。在日常生活中，我们都习惯了事件一个接一个发生，按照完美定义的“在……之前发生”（happend before）的顺序。如果是一系列分布式进程，它们交换消息和访问资源都是并发的。我们该如何判断事件的先后发生顺序？要回答此类问题，不同的进程必须共享一个同步时钟，还要准确地知道通过网络交换信息的耗时、 CPU 调度任务的耗时等等。显然，在现实系统中不可能做到这一点。
有一篇讨论上述问题的影响深远的论文，标题是“时间，时钟和分布式系统中的事件顺序”。这篇论文引入了逻辑时钟的概念。逻辑时钟是为系统中每个事件分配一个数字的方法。这些数字与实际的时间无关，而是与分布式系统节点对事件的处理有关。
逻辑时钟算法有很多种，像向量时钟和区间树时钟。
我推荐一篇讨论分布式系统时间的文章， Justin Sheehy 写的“没有现在”，很有意思的讨论。
我认为，时间及其在分布式系统中引起的问题，是需要理解的关键概念。同时性的想法源自“绝对知识”的老观念，我们以前认为绝对知识是可以获得的。物理定律告诉我们，即使是光也需要时间才能从一个地方达到另外一个地方，这样，当光到达我们的眼睛时，我们的大脑会处理光传递的信息。这是一种旧的世界观。Umberto Eco 在《发明敌人》这本书的“绝对和相对”一章中讨论了上述想法。
快速浏览 FLP
最后，我们快速浏览这篇论文，把刚才学到的有关分布式系统的各种概念关联起来。
在摘要的开头，作者写道：
共识问题涉及的是由一组进程组成的异步系统，其中一些进程是不可靠的。
在异步系统中，对处理速度或者消息送达时间不做任何假设，其中有些进程可能会崩溃。
这种说法有一个问题。在通常的技术术语中，异步可能是指处理请求的方式。以 RPC 为例，进程 _p_ 向进程 _q_ 发送一个异步请求；在进程 _q_ 处理请求的同时， _p_ 会继续做别的事情——也就是说， _p_ 不会为了等待应答而阻塞自己的运行。你看，同样是叫异步，在这里的含义与在分布式系统文献中的含义完全不同。不了解这一点，你很难完全理解 FLP 论文的第一句话。
接下来，作者写道：
本文提出一个令人惊奇的结果：系统中哪怕是只有一个进程可能会失效，就完全不可能存在异步共识协议。我们假设系统中不存在拜占庭失效，消息系统也是可靠的——所有消息都会被正确地一次送达。
由此可见，这篇论文讨论的系统只存在崩溃-停止（或者说失效-停止）的失效模式，（除了不存在拜占庭模式），也不存在忽略失效模式，因为消息系统是可靠的。
最后，作者还添加下面一条约束：
不假定进程能够检测出另外一个进程是否死亡。也就是说，一个进程无法区分另外一个进程的两种状态：死亡（完全停止运行）或者运行得很慢。
这就是说，本文讨论的系统中不存在失效检测器。
总结一下， FLP 不可能性结果适用于具有下列特征的异步系统：崩溃-停止失效模式；可靠的消息系统；不存在失效检测器。不了解各种分布式系统模型的理论，我们就可能漏掉很多细节，我们的理解甚至与作者的原意相去甚远。
想要更详细地了解 FLP 不可能性，请看博客文章： FLP 简要梳理。
Marcos Aguilera 写了一篇有意思的论文“共识研究中的那些坑：误解与问题”，文中讨论了 FLP 作为分布式系统的一个不可能性结果，它的含义究竟是什么（剧透警告：这里说的不可能性与停机问题中的不可能性不是一回事儿）。
结束语
如你所知，分布式系统的学习需要时间投入。分布式系统是一个非常庞大的议题，每个子领域都已经有非常多的研究。与此同时，分布式系统的实现和验证又是非常复杂的，有很多容易犯错的细微之处，处理不好的话，我们实现的分布式系统就会在意想不到的情况下无法正常地工作。
如果不能正确地理解分布式系统的底层理论，下列问题甚至更多问题就会发生：选择错误的法定人数，结果导致新的复制算法丢失关键数据；选择非常保守的法定人数，导致应用程序运行变慢，从而满足不了向用户承诺的服务约定；我们要解决的问题本来根本没必要使用共识，用最终一致性就行，（但是我们却选择使用共识）；错误地假设系统的定时模型；使用了不符合底层系统属性的失效检测器；我们想优化像 Raft 这样的算法，于是去掉了貌似不相关的一个小步骤，结果却破坏了算法的安全性保证。
好，我明白了，我不想重新发明分布式系统轮子，但是面对如此众多的问题和文献，我该从哪里着手呢？在本文开头，我指出随机地阅读论文没有什么用处。就像上面提到的 FLP 论文，不了解各种定时模型，你就没办法理解论文的第一句话。因此，我推荐下列入门书籍：
《分布式算法》，Nancy Lynch 著。这本书就好像是分布式系统的圣经，内容涵盖上面提及的各种模型，包括每种模型涉及的算法。
《可靠且安全的分布式程序设计指南》，Christian Cachin 等人著。这本书不光导论写得非常棒，还涵盖了很多种共识算法。这本书还有个优点，到处可见解释算法的伪代码。
还有很多书。我觉得这两本非常适合入门使用。
参考文献
如果你还想深入研究，请看本文的参考文献列表：
- Marcos K. Aguilera. 2010. Stumbling over consensus research: misunderstandings and issues. In Replication, Bernadette Charron-Bost, Fernando Pedone, and André Schiper (Eds.). Springer-Verlag, Berlin, Heidelberg 59-72.
- Paulo Sérgio Almeida, Carlos Baquero, and Victor Fonte. 2008. Interval Tree Clocks. In Proceedings of the 12th International Conference on Principles of Distributed Systems (OPODIS ‘08), Theodore P. Baker, Alain Bui, and Sébastien Tixeuil (Eds.). Springer-Verlag, Berlin, Heidelberg, 259-274.
- Kenneth P. Birman. 2012. Guide to Reliable Distributed Systems: Building High-Assurance Applications and Cloud-Hosted Services. Springer Publishing Company, Incorporated.
- Mike Burrows. 2006. The Chubby lock service for loosely-coupled distributed systems. In Proceedings of the 7th symposium on Operating systems design and implementation (OSDI ‘06). USENIX Association, Berkeley, CA, USA, 335-350.
- Christian Cachin, Rachid Guerraoui, and Luis Rodrigues. 2014. Introduction to Reliable and Secure Distributed Programming (2nd ed.). Springer Publishing Company, Incorporated.
- Tushar Deepak Chandra and Sam Toueg. 1996. Unreliable failure detectors for reliable distributed systems. J. ACM 43, 2 (March 1996), 225-267.
- Umberto Eco. 2013. Inventing the Enemy: Essays. Mariner Books.
- Colin J. Fidge. 1988. Timestamps in message-passing systems that preserve the partial ordering. Proceedings of the 11th Australian Computer Science Conference 10 (1) , 56–66.
- Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. 1983. Impossibility of distributed consensus with one faulty process. In Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems (PODS ‘83). ACM, New York, NY, USA, 1-7.
- Maurice P. Herlihy and Jeannette M. Wing. 1990. Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12, 3 (July 1990), 463-492.
- Leslie Lamport. 1978. Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21, 7 (July 1978), 558-565.
- Leslie Lamport. 1998. The part-time parliament. ACM Trans. Comput. Syst. 16, 2 (May 1998), 133-169.
- Nancy A. Lynch. 1996. Distributed Algorithms. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.
- Moni Naor and Avishai Wool. 1998. The Load, Capacity, and Availability of Quorum Systems. SIAM J. Comput. 27, 2 (April 1998), 423-447.
- Brian M. Oki and Barbara H. Liskov. 1988. Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems. In Proceedings of the seventh annual ACM Symposium on Principles of distributed computing (PODC ‘88). ACM, New York, NY, USA, 8-17.
- Diego Ongaro and John Ousterhout. 2014. In search of an understandable consensus algorithm. In Proceedings of the 2014 USENIX conference on USENIX Annual Technical Conference (USENIX ATC’14), Garth Gibson and Nickolai Zeldovich (Eds.). USENIX Association, Berkeley, CA, USA, 305-320.
- M. Pease, R. Shostak, and L. Lamport. 1980. Reaching Agreement in the Presence of Faults. J. ACM 27, 2 (April 1980), 228-234.
- Stefan Poledna. 1996. Fault-Tolerant Real-Time Systems: The Problem of Replica Determinism. Kluwer Academic Publishers, Norwell, MA, USA.
- Michel Raynal. 2010. Communication and Agreement Abstractions for Fault-Tolerant Asynchronous Distributed Systems (1st ed.). Morgan and Claypool Publishers.
- Michel Raynal. 2010. Fault-tolerant Agreement in Synchronous Message-passing Systems (1st ed.). Morgan and Claypool Publishers.
- Benjamin Reed and Flavio P. Junqueira. 2008. A simple totally ordered broadcast protocol. In Proceedings of the 2nd Workshop on Large-Scale Distributed Systems and Middleware (LADIS ‘08). ACM, New York, NY, USA, , Article 2 , 6 pages.
- Justin Sheehy. 2015. There Is No Now. ACM Queue
- Marko Vukolic. 2012. Quorum Systems: With Applications to Storage and Consensus. Morgan and Claypool Publishers.