一、分布式一致性 (Consensus)

分布式一致性问题，简单的说，就是在一个或多个进程提议了一个值应当是什么后，使系统中所有进程对这个值达成一致意见。

这样的协定问题在分布式系统中很常用，比如：

• 领导者选举（leader election）：进程对leader达成一致；
• 互斥（mutual exclusion）：进程对进入临界区的进程达成一致；
• 原子广播（atomic broadcast）：进程对消息传递（delivery）顺序达成一致。

对于这些问题有一些特定的算法，但是，分布式一致性问题试图探讨这些问题的一个更一般的形式，如果能够解决分布式一致性问题，则以上的问题都可以解决。

分布式一致性问题的定义如下图所示：

分布式一致性问题

为了达成一致，每个进程都提出自己的提议（propose），最终通过分布式一致性算法，所有正确运行的进程决定（decide）相同的值。

分布式一致性实例

如果在一个不出现故障的系统中，很容易解决分布式一致性问题。但是实际分布式系统一般是基于消息传递的异步分布式系统，进程可能会慢、被杀死或者重启，消息可能会延迟、丢失、重复、乱序等。

在一个可能发生上述异常的分布式系统中如何就某个值达成一致，形成一致的决议，保证不论发生以上任何异常，都不会破坏决议的一致性，这些正是一致性算法要解决的问题。

二、分布式一致性算法典型应用场景

我们在分布式存储系统中经常使用多副本的方式实现容错，每一份数据都保存多个副本，这样部分副本的失效不会导致数据的丢失。每次更新操作都需要更新数据的所有副本，使多个副本的数据保持一致。那么问题来了，如何在一个可能出现各种故障的异步分布式系统中保证同一数据的多个副本的一致性 (Consistency) 呢？

以最简单的两副本为例，首先来看看传统的主从同步方式。

传统的主从同步

写请求首先发送给主副本，主副本同步更新到其它副本后返回。这种方式可以保证副本之间数据的强一致性，写成功返回之后从任意副本读到的数据都是一致的。但是可用性很差，只要任意一个副本写失败，写请求将执行失败。

主从同步的弱可用性

如果采用异步复制的方式，主副本写成功后立即返回，然后在后台异步的更新其它副本。

主从异步复制

写请求首先发送给主副本，主副本写成功后立即返回，然后异步的更新其它副本。这种方式可用性较好，只要主副本写成功，写请求就执行成功。但是不能保证副本之间数据的强一致性，写成功返回之后从各个副本读取到的数据不保证一致，只有主副本上是最新的数据，其它副本上的数据落后，只提供最终一致性。

异步复制失败

如果出现断网导致后台异步复制失败，则主副本和其它副本将长时间不一致，其它副本上的数据一直无法更新，直到网络重新连通。

主副本写成功后立即宕机

如果主副本在写请求成功返回之后和更新其它副本之前宕机失效，则会造成成功写入的数据丢失，一致性被破坏。

熟悉Oracle的朋友应该对上述同步方式非常熟悉，上述同步和异步复制方式分别对应Oracle Data Guard的一种数据保护模式。

同步复制为最高保护模式 (Maximum Protection)，异步复制为最高性能模式 (Maximum Performance)，还有一种最高可用性模式 (Maximum Availability) 介于两者之间，在正常情况下，它和最高保护模式一样，但一旦同步出现故障，立即切换成最高性能模式。

传统的主从同步无法同时保证数据的一致性和可用性，此问题是典型的分布式系统中一致性和可用性不可兼得的例子，分布式系统中著名的CAP理论从理论上证明了这个问题。

而Paxos、Raft等分布式一致性算法则可在一致性和可用性之间取得很好的平衡，在保证一定的可用性的同时，能够对外提供强一致性，因此Paxos、Raft等分布式一致性算法被广泛的用于管理副本的一致性，提供高可用性。

三、CAP理论

CAP理论是分布式系统、特别是分布式存储领域中被讨论的最多的理论。其中C代表一致性 (Consistency)，A代表可用性 (Availability)，P代表分区容错性 (Partition tolerance)。CAP理论告诉我们C、A、P三者不能同时满足，最多只能满足其中两个。

CAP理论

• 一致性 (Consistency)：一个写操作返回成功，那么之后的读请求都必须读到这个新数据；如果返回失败，那么所有读操作都不能读到这个数据。所有节点访问同一份最新的数据。
• 可用性 (Availability)：对数据更新具备高可用性，请求能够及时处理，不会一直等待，即使出现节点失效。
• 分区容错性 (Partition tolerance)：能容忍网络分区，在网络断开的情况下，被分隔的节点仍能正常对外提供服务。

理解CAP理论最简单的方式是想象两个副本处于分区两侧，即两个副本之间的网络断开，不能通信。

• 如果允许其中一个副本更新，则会导致数据不一致，即丧失了C性质。
• 如果为了保证一致性，将分区某一侧的副本设置为不可用，那么又丧失了A性质。
• 除非两个副本可以互相通信，才能既保证C又保证A，这又会导致丧失P性质。

一般来说使用网络通信的分布式系统，无法舍弃P性质，那么就只能在一致性和可用性上做一个艰难的选择。

CAP理论的表述很好地服务了它的目的，开阔了分布式系统设计者的思路，在多样化的取舍方案下设计出多样化的系统。在过去的十几年里确实涌现了不计其数的新系统，也随之在一致性和可用性的相对关系上产生了相当多的争论。

既然在分布式系统中一致性和可用性只能选一个。那Paxos、Raft等分布式一致性算法是如何做到在保证一定的可用性的同时，对外提供强一致性呢。

在CAP理论提出十二年之后，其作者又出来辟谣。“三选二”的公式一直存在着误导性，它会过分简单化各性质之间的相互关系：

• 首先，由于分区很少发生，那么在系统不存在分区的情况下没什么理由牺牲C或A。
• 其次，C与A之间的取舍可以在同一系统内以非常细小的粒度反复发生，而每一次的决策可能因为具体的操作，乃至因为牵涉到特定的数据或用户而有所不同。
• 最后，这三种性质都可以在程度上衡量，并不是非黑即白的有或无。可用性显然是在0%到100%之间连续变化的，一致性分很多级别，连分区也可以细分为不同含义，如系统内的不同部分对于是否存在分区可以有不一样的认知。

所以一致性和可用性并不是水火不容，非此即彼的。Paxos、Raft等分布式一致性算法就是在一致性和可用性之间做到了很好的平衡的见证。

四、多副本状态机

将多副本管理的模型抽象出来，可得到一个通用的模型：多副本状态机 (Replicated State Machine) 。

多副本状态机是指多台机器具有完全相同的状态，并且运行完全相同的确定性状态机。

通过使用这样的状态机，可以解决很多分布式系统中的容错问题。因为多副本状态机通常可以容忍半数节点故障，且所有正常运行的副本节点状态都完全一致，所以可以使用多副本状态机来实现需要避免单点故障的组件。

高可用"单点"的集中式架构

多副本状态机在分布式系统中被用于解决各种容错问题。如集中式的选主或是互斥算法中的协调者 (Coordinator)。集中式的领导者或互斥算法逻辑简单，但最大的问题是协调者的单点故障问题，通过采用多副本状态机来实现协调者实现了高可用的“单点”，回避了单点故障。

GFS，HDFS，RAMCloud等典型地使用一个独立的多副本状态机来管理领导者选举与保存集群配置信息，以备节点宕机后信息能够保持。

Chubby与ZooKeeper以及Boxwood等都是使用多副本状态机的例子。

多副本状态机的每个副本上都保存有完全相同的操作日志，保证所有状态机副本按照相同的顺序执行相同的操作，这样由于状态机是确定性的，则会得到相同的状态。

多副本状态机结构

每个服务器在日志中保存一系列命令，所有的状态机副本按照同样的顺序执行，分布式一致性算法管理着来自客户端的包含状态机命令的日志复制，每条日志以同样的顺序保存同样的命令，因此每个状态机执行同样的命令序列。因为状态机是确定的，每个都计算出同样的状态与同样的输出。

保证复制到各个服务器上的日志的一致性正是分布式一致性算法的工作。一致性算法保证所有状态机副本上的操作日志具有完全相同的顺序，如果状态机的任何一个副本在本地状态机上执行了一个操作，则绝对不会有别的副本在操作序列相同位置执行一个不同的操作。

服务器上的一致性模块，接收来自客户端的命令，并且添加到他们的日志中。它与其它服务器的一致性模块通讯，以确保每个日志最终以同样的顺序保存同样的请求，即使有些服务器失败。一旦命令被适当地复制，每台服务器的状态机以日志的顺序执行，将输出返回给客户端。结果多台服务器就像来自单个高度一致的高可用状态机。