vlambda博客
学习文章列表

02

—

共识算法通常在replicated state machine（复制状态机）的内容里出现。使用复制状态机，server集群可以共同维护一份相同的状态机副本。哪怕集群中有一些server宕机了，整个系统一样可以正常运行。复制状态机通常用来解决分布式系统中的容错问题。比如说，像GFS、HDFS、RAMCloud这种大规模系统中的单leader集群（单leader集群是指，系统中leader是逻辑唯一的，但是物理上不一定只有一个服务器），通常会使用一个独立的复制状态机来管理leader选举、存储在leader崩溃后仍能正常运行的且必要的配置信息。复制状态机的例子还包括Chubby、Zookeeper。

状态机一般来说是由replicated log（备份日志）来实现的。如图1所示，每个server都保存一份log，用来记录一连串的命令，而且server的状态机是按一定顺序执行的。每份log所记录的命令都具有相同的顺序，所以每一个状态机都处理着相同的命令序列。因为状态机是确定性的，所以每一份状态机都对相同的状态进行计算且具有相同的一系列输出。

共识算法要做的就是保证replicated log（复制日志）的一致性。一个server上的共识模块会接收从client发送过来的命令，然后将这些命令追加到它的log里。每个server的共识模块会和其他server上的共识模块进行通信，确保即使在部分server宕机的情况下，每一份log最终仍然能以相同的顺序记录着相同的一连串请求。一旦命令被正确地备份，每个server的状态机会按log记录的顺序来处理这些命令，并且把输出返回给client。最终，整个server集群看上去就像是一个单节点、高可靠的状态机。

物理机上的共识算法具有如下性质：

• 安全性。在非拜占庭环境下，共识算法可以保证系统安全性，即绝不会返回错误的结果，哪怕是在网络延迟、分区、丢包、重复接收、乱序发送的情况下。

• 只要超过半数的server仍能工作并能够与其他server和client通信，系统就是可用（available）的。即，一个五台server的集群能够容忍两台server的崩溃。Server的崩溃通常被认为是停机了，也许不久后会从持久化存储中恢复运算状态，并且重新加入集群。

• 集群不依赖时钟来确保log的一致性。在极端情况下，易错的时钟和长延时会造成严重的系统不可用问题。

• 在绝大多数情况下，超过半数的server可以在一轮RPC的时间内就能完成client的命令，少数拖后腿的服务器就不会影响整体系统的性能了。