一致性问题

一致性是一个基本的分布式系统问题，在出现故障的情况下，需要多个步骤来达成一致[Pease et al., 1980]。该问题经常出现在如下场景中：通信是可靠的，但是由于系统崩溃或认为恶意破坏等原因（即未按照指定的协议或代码进行响应），站点可能会失效。一般而言，该问题可以使用一个单独的协调者，或称general，协调者给n-1个参与者发送一个二进制值，并满足下列条件：

一致：所有参与者都认同一个值。

正确：如果general是正确的，那么每一个参与者都认同general发送的值。

接下来介绍两个不可能出现的结果。在异步系统中，如果进程由于崩溃而失效，并且进程是通过消息传递来进行通信的，Fischer et al. [1983, 1985]证明一致性是不可能解决的。另一方面，在一个存在恶意故障的同步系统中，Dolev [1982] 证明了如果一个系统的进程数量小于3f+1，其中，f是故障（恶意）进程的最大值，那么该系统也无法解决一致性问题。

已经有多种协议可以用来解决同步系统和异步系统中的一致性问题。同步系统需要指定恶意故障站点的最大数量的上界，如三分之一。另一方面，异步系统可能无法确保系统能够终止。近来，Lamport [1998, 2001]为异步系统开发的Paxos协议广受欢迎。抽象地讲，Paxos是一个以领导者为基础的（leader-based）的协议，每一个进程都可以估计当前的领导者是谁。当一个进程希望在某个值上达成一致时，进程就把该值发送给领导者。领导者对操作进行排序并通过一致性算法来实现一致。通常情况下，该协议经历两个阶段。在每一个阶段，领导者会与大部分站点进行联系，往往会有多个并发的领导者。用投票来区分不同领导者提供的值。两个阶段的具体过程可以总结如下：第一阶段，又称为准备阶段，认为自己是领导者的节点可以选择一个新的唯一的投票号码，并把该号码发送给所有的站点，然后等待来自大部分站点的较小的投票号码的结果。第二阶段，又称接受阶段，领导者根据自己的投票号码建议一个值。如果领导者能够获得大多数支持，那么该值就会被接受，其他站点也会用对应的投票号码对该值进行判断。图2-7展示了基于Paxos协议的不同进程之间的通信模式。

图2-7　基于Paxos协议的通信