2. 目的
共识是容错系统中的一个基本问题：在面对故障时多个服务器如何就共享的状态/数据达成统一意见？这个问题出现在需要提供高可用性的各种系统中，并且不能影响一致性；因此，在几乎所有大规模存储系统中都使用了共识。第2.1节描述了共识通常用于创建复制状态机（Replicated State Machine），这是构建容错系统的基础；第2.2节讨论了大型系统中复制状态机的各种方式；第2.3节讨论了Paxos共识协议的问题，以及说明Raft致力于解决的问题。
2.1 通过复制状态机实现容错
在复制状态机的上下文中（场景中），共识算法常常被提起。在这种方法中，服务器集群中的每个服务器通过执行相同的状态操作来实现状态的一致，即使某些服务器已宕机/关闭，也可以继续运行。如第2.2节所述复制状态机用于解决分布式系统中的各种容错问题。复制状态机的示例包括Chubby和ZooKeeper，它们都为少量的配置数据提供了层次化的KV存储。除了get和put等基本操作外，它们还提供了CAS（Compare-and-Swap）同步原语，使并发客户端能够安全地进行协作。
复制状态机通常使用日志副本来实现，如图2.1所示。每个服务器都存储一个包含一系列命令的日志，其状态机会按顺序执行这些命令。每个日志都以相同的顺序包含相同的命令，因此每个状态机都会以相同的执行顺序来处理相同的命令。因为状态机是确定的，每个服务器计算相同的状态并产生相同的结果。
复制状态机的组成部分如下：
- **Client**，客户端，正常的产生相应命令交由复制状态机处理，这里的命令是对状态机中某个元素的值的修改；
- **Server**，状态机所在的服务器，其接收Client的命令，然后处理相关命令，并通过复制状态机的方法保证Client命令完成后的可靠性（即不容易丢失，因为有多个状态机副本，即使某个Server上的状态机丢失了，也能从其它服务器的状态机查询得到，或者通过log重新执行一遍命令后生成相应状态机内容），Server处理完Client的命令后会将处理结果回复给Client。
每个Server中含有三个关键的模块：共识模块、日志模块和状态机；
-**共识模块**，用于对Client发出的命令进行共识协商，来确定先执行那个Client的命令；
-**日志模块**，用于存储Client的命令的日志，将Client的每个命令都存在日志里面，这样的好处有：1）可以通过日志记录Client的所有命令；2）如果状态机模块失效了，可以从都到尾执行日志里面的命令重新构建一个状态机，并且这个状态机和其它Server里面的状态机内容一致。
-**状态机**，用于保存Server中数据/状态，是Server执行Client命令后的状态存储模块。
这里的日志记录的是**过程**，状态机则记录的是**结果**，结果可以由过程推导得出。
保持复制日志（Replicated Log）的一致性是共识算法的责任。服务器上的共识模块接收来自客户端的命令，并将其添加到其日志中。每个服务器它与其他服务器上的共识模块通信，以确保每个日志最终以相同的顺序包含相同的请求/命令，即使某些服务器失败。一旦正确地复制了客户端的请求/命令，就认为这个请求/命令是已提交。每个服务器的状态机都按日志顺序处理提交的命令，输出返回给客户端。因此，这些服务器似乎形成了一个单一的、高度可靠的状态机。
文中的“commited”指的是一种状态，这种状态就是某个Client的请求/命令被系统中大多数（多数派）Server的日志（Replicated Log）所记录，也就是说，大多数Server完成了Client请求/命令在日志中的记录操作后，系统中这个请求/命令就处于了已提交状态。需要注意的是：已提交的日志不一定被Server所执行。
实际系统的共识算法通常具有以下特性：
Safety，安全性，非拜占庭环境下的安全性保障（包括网络延迟、网络丢包、消息重复、消息乱序），绝不会返回错误的结果（给客户端），但是不保证拜占庭错误下的安全性；
Available，可用性，只要大多数的Server间以及与Client之间可以正常的通信，那么算法可保证其可用性。那么，典型的系统包含5个Server，就可以容忍2个Server的失效。Server默认的失效的关机，但是这些Server可能重启，并通过可靠存储中存储的状态机进行状态机的恢复，然后加入到集群中；
不依赖时间（物理时钟）来保证每个Server上日志的一致性，最坏情况下，错误的时钟和极端的消息延迟仅可引起可用性问题，而不会导致一致性问题。也就是说，Raft利用了异步的模型来保障算法的安全性，在这个算法中，消息和处理器可以是异步的（就是消息传输的速率、带宽、处理器处理消息的速度、消息处理的顺序等可以每个Server不一样）。
常见的情况，一个Client发出的请求/命令可很会得到回复，只要系统中大多数Server在一个回合的RPC调用中完成（Raft中的RPC调用在后续章节会详细介绍），小部分的Server的慢速处理不会影响系统性能。
2.2 复制状态机的常见用用例
复制状态机是用于实现系统容错的基础。它们可以以多种方式使用，本节还讨论了一些典型的使用模式。
大多数常见的共识算法部署在只有三到五台服务器上，构成一台复制状态机。其他服务器可以使用此状态机协调其活动，如图2.2(a)所示。这些系统通常使用复制状态机来提供组成员管理、配置管理或锁。作为一个更具体的示例，复制状态机可以提供容错工作队列，而其他服务器可以使用复制状态机协调将工作分配给自己。
此用法的常见简化如图2.2(b)所示。在此模式中，一台服务器充当领导者，管理其余的服务器。领导者将其关键数据存储在共识系统中。如果它失败了，其他备用服务器将竞争领导者的位置，如果它们成功了，它们将使用共识系统中的数据来继续操作。许多具有单一集群领导者的大型存储系统，如GFS、HDFS和RAMCloud，都使用这种方法。（这种场景中，将共识系统组成的复制状态机当做共享存储来用，并通过前端多个服务器提供高可用服务）。
共识有时也被用于复制大量的数据，如图2.3所示。大型存储系统，如s Megastore, Spanner, and Scatter，通过一组Server组成的集群提供海量数据的存储。数据被分成不同的分块，每个分块有多个副本在不同的复制状态机（一个复制状态机由多个Server组成），状态机的数据一致性由2PC来保障。
2.3 Paxos的问题
在过去的十年里，莱斯利·兰波特的Paxos协议几乎已经成为共识的同义词：它是课程中最常见的算法，而大多数共识算法的实现都将它作为起点。Paxos首先定义了一个能够就单个决策达成协议的协议，例如日志中单个条目的内容进行共识。这个方法被称为单Paxos（single-decree Paxos）。然后，Paxos结合了该协议的多个实例，以促进一系列的决策，如日志多个条目(多Paxos，Multi-Paxos)。图2.4总结了单Paxos，图A.5总结了多法令Paxos。Paxos确保了Safety和Liveness（最终可达到共识，假设可以避免活锁的话），其正确性已得到证明。多Paxos在正常情况下是有效的，而Paxos支持集群成员角色的改变。
Paxos算法的总结：https://www.jianshu.com/p/67dd80555ba2
不幸的是，Paxos有两个显著的缺点：1）Paxos算法很难理解，很多人试图对单Paxos进行深度解释，但是还是很难理解；2）Paxos算法没有提供工程化实现的良好指导。
我们假设Paxos的不易理解源于它选择了单Paxos作为其基础。单法令的Paxos是密集而微妙的：它分为两个阶段，没有简单的直观解释，各个阶段也不能独立理解。正因为如此，很难发展出为什么单一法令协议有效的直觉。多Paxos的组成规则增加了额外的复杂性。我们相信，就多个决策（即一个日志而不是单个条目）达成共识的整体问题可以以其他更直接和更明显的方式进行分解。
第二个问题的原因之一是针对多Paxos还没有达成深度的共识。莱斯利·兰波特在论文中的描述多是面向单Paxos的，只是给出了多Paxos的设计骨架，但是没有深入说明。虽然现在已经有很多关于多Paxos的工程实践，但是他们都是基于多Paxos的变种，不但没有采用莱斯利·兰波特多Paxos的设计骨架，而且每个变种之间的设计细节也各不相同。
此外，Paxos架构对于构建实际系统来说很差；这是单Paxos的另一个结果。例如，独立地选择一个日志条目集合，然后将它们合并成一个顺序的日志，几乎没有什么好处；这只是增加了复杂性。围绕一个日志设计一个系统更简单、更高效，在这种设计里，新的日志条目是按照一个有限制的顺序追加进日志里面的。
另一个问题是，Paxos的核心使用了对称的peer-to-peer方法（尽管它通过弱化Leader选举来提升算法性能，就是减少Leader选举产生的网络通讯消耗，单Paxos算法中Leader选举和共识融合在一起的）。这在一个简化的、只需做出一个决定的场景里是有意义的，但很少有实际的系统使用这种方法。如果必须做出一系列决定，首先选出领导人，然后让领导人协调决策就更简单、更快了。(第11章讨论了EPaxos，这是Paxos的最接近变体，不使用领导者，但在某些情况下可以比使用Leader的算法更有效；然而，这个算法比基于领导者的算法复杂得多。)
因此，实际的系统与Paxos几乎没有什么相似之处。每个实现都从Paxos开始，发现实现它的困难，然后开发一个显著不同的体系结构。这很耗时且容易出错，而理解Paxos的困难加剧了这个问题。Paxos的公式可能是证明其正确性的好公式，但实际的实现与Paxos是如此的不同，以至于证明几乎没有价值。以下是来自Chubby实现者的典型评论：
"在Paxos算法的描述和现实系统的需求之间存在着显著的差距。最终的系统将基于一个未经验证的算法。"
由于这些问题，我们得出结论，Paxos即不能为系统设计也不能为教学提供良好的帮助。考虑到共识在大规模软件系统中的重要性，我们决定看看是否可以设计一种比Paxos更好的替代共识算法。Raft就是这个实验的结果。
下一章：Raft算法基础 >>
