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 不应该影响到整个系统性能。

results matching ""

    No results matching ""