2 Replicated state machines

集群中某些服务器不可用，整个集群还可以工作。

算法保证安全性；

复制日志保持顺序性；

        Consensus algorithms typically arise in the context of replicated state machines [37]. In this approach, state machines on a collection of servers compute identical copies of the same state and can continue operating even if some of the servers are down. Replicated state machines are used to solve a variety of fault tolerance problems in distributed systems. For example, large-scale systems that have a single cluster leader, such as GFS [8], HDFS [38],and RAMCloud [33], typically use a separate replicated state machine to manage leader election and store configuration information that must survive leader crashes. Examples of replicated state machines include Chubby [2] and ZooKeeper [11].

        共识算法通常出现在复制状态机的上下文中[37]。在这种方法中，服务器集合上的状态机计算相同状态的相同副本，即使某些服务器关闭，整个集群也可以继续运行。复制状态机用于解决分布式系统中的各种容错问题。例如，具有单个集群领导者的大型系统，如GFS[8]、HDFS[38]和RAMCloud[33]，通常使用单独的复制状态机来管理领导者选举并存储必须在领导者崩溃后生存的配置信息。复制状态机的示例包括Chubby[2]和ZooKeeper[11]。

        Replicated state machines are typically implemented using a replicated log, as shown in Figure 1. Each server stores a log containing a series of commands, which its state machine executes in order. Each log contains the same commands in the same order, so each state machine processes the same sequence of commands. Since the state machines are deterministic, each computes the same state and the same sequence of outputs.

        复制状态机通常使用复制log实现，如图1所示。每个服务器存储一个包含一系列命令的日志，其状态机按顺序执行这些命令。每个日志以相同的顺序包含相同的命令，因此每个状态机处理相同的命令序列。由于状态机是确定性的，因此每个状态机计算相同的状态和相同的输出序列。

Figure 1: Replicated state machine architecture. The consensus algorithm manages a replicated log containing state machine commands from clients. The state machines process identical sequences of commands from the logs, so they produce the same outputs.

图1 ：复制状态机架构。一致性算法管理包含来自client的状态机命令的复制日志。状态机处理来自日志的相同命令序列，因此它们产生相同的输出。

        Keeping the replicated log consistent is the job of the consensus algorithm. The consensus module on a server receives commands from clients and adds them to its log. It communicates with the consensus modules on other servers to ensure that every log eventually contains the same requests in the same order, even if some servers fail. Once commands are properly replicated, each server’s state machine processes them in log order, and the outputs are returned to clients. As a result, the servers appear to form a single, highly reliable state machine.

        保持replicate log的一致性是一致性算法的工作。服务器上的一致性模块从客户端接收命令并将其添加到日志中。它与其他服务器上的一致性模块通信，以确保每个日志最终以相同的顺序包含相同的请求，即使某些服务器出现故障。一旦命令被正确复制，每个服务器的状态机将按日志顺序处理它们，并将输出返回给客户端。因此，服务器似乎形成了一个单一的、高度可靠的状态机。

Consensus algorithms for practical systems typically have the following properties:

实际系统的一致性算法通常具有以下特性：

• They ensure safety (never returning an incorrect result) under all non-Byzantine conditions, including network delays, partitions, and packet loss, duplication, and reordering.
• 安全性：它们确保在所有非拜占庭条件下的安全性（从不返回错误结果），包括网络延迟、分区、数据包丢失、复制和重新排序。
• They are fully functional (available) as long as any majority of the servers are operational and can communicate with each other and with clients. Thus, a typical cluster of five servers can tolerate the failure of any two servers. Servers are assumed to fail by stopping; they may later recover from state on stable storage and rejoin the cluster.
• 大多数：只要大多数服务器都可以运行，并且可以相互通信和与客户机通信，它们就可以完全正常工作（可用）。因此，由五台服务器组成的典型集群可以容忍任何两台服务器的故障。假定服务器因停止而发生故障；它们可能稍后从稳定存储上的状态恢复并重新加入集群。
• They do not depend on timing to ensure the consis-tency of the logs: faulty clocks and extreme message delays can, at worst, cause availability problems.
• 它们不依赖于时间来确保日志的一致性：错误的时钟和极端的消息延迟在最坏的情况下会导致可用性问题。
• In the common case, a command can complete as soon as a majority of the cluster has responded to a single round of remote procedure calls; a minority of slow servers need not impact overall system performance.
• 在一般情况下，只要集群的大多数成员成功响应了一轮远程过程调用，命令就可以完成；少数速度较慢的服务器不需要影响总体系统性能。