2 复制状态机

一致性算法是在复制状态机（Replicated State Machine）的背景下提出来的。在这个方法中，一组 Server 的状态机计算相同状态的副本，并且即使有一部分 Server 宕机了它们仍然能够继续运行。在分布式系统中，复制状态机被用来解决各种容错问题。具有单个集群 Leader 的大规模系统，例如 GFS [8]、HDFS [38]、RAMCloud [33]，一般使用一个单独的复制状态机来管理 Leader 选举和存储配置信息，必须能够使 Leader 从失败中恢复。使用复制状态机的例子包括 Chubby [2] 和 ZooKeeper [11]。

图-1：复制状态机架构。一致性算法管理来自客户端的状态机命令的复制日志。状态机处理日志中相同顺序的命令序列，因此会输出相同的结果。

如 图-1 所示，一般通过使用复制日志来实现复制状态机。每个 Server 存储着一份包含命令序列的日志文件，状态机会按顺序执行这些命令。因为每个日志包含相同的命令，并且顺序也相同，所以每个状态机处理相同的命令序列。由于状态机是确定性的，所以处理相同的状态，得到相同的输出。

保证复制日志的一致性是一致性算法的任务。一个 Server 上的一致性模块会接收来自客户端的命令，并把命令添加到它的日志文件中。它同其它 Server 上的一致性模块进行通信，确保每一个日志最终包含相同的请求且顺序也相同，即使某些 Server 故障。一旦这些命令被正确复制，每个 Server 的状态机都会按照日志中的顺序去处理，将输出结果返回给客户端。最终，这些 Server 看起来就像一个单独的、高可靠的状态机。

对于实际系统，一致性算法一般具有如下特点：

• 安全。满足在所有非拜占庭条件下确保安全（从来不会返回错误结果），包括网络延迟、分区、丢包、重复和重排序。
• 高可用。只要集群中的大部分 Server 正常运行，并能够互相通信且可以同客户端通信，这个集群就完全可用。因此，拥有5个 Server 的集群可以容忍其中的2个 Server 失败。假使通过停掉某些 Server 使其失败，稍后它们会从持久化存储的状态进行恢复，并重新加入到集群中。
• 不依赖于时序。确保日志的一致性：时钟错误，以及极端情况下的消息延迟，在最坏的情况下都会造成可用性问题。
• 通常情况下，只要集群中大多数 Server 成功响应了某一轮 RPC 调用，一个命令就算完成。少部分较慢的 Server 不应该影响到整个系统性能。