Raft分布式一致性算法整理 顶 原

CAP定理

1. Consistency:一致性
2. Availability:可用性
3. Partition-tolerance:分区容错性

CAP定理指出，在异步网络模型中，不存在一个系统可以同时满足上述3个属性。换句话说，分布式系统必须舍弃其中的一个属性。对于需要在分布式条件下运行的系统来说，如何在一致性、可用性和分区容错性中取舍，或者说要弱化哪一个属性，是首先要考虑的问题。

对于高可用性的系统来说，往往会保留强一致性。但对于强一致性的系统来说，有一类专门解决这种问题的算法——共识算法。"共识"的意思是保证所有的参与者都有相同的认知(可以理解为强一致性)。共识算法本身可以依据是否有恶意节点分为两类，大部分时候共识算法指的是没有恶意节点的那一类，即系统中的节点不会向其他节点发送恶意请求，比如欺骗请求。共识算法中最有名的是Paxos算法。其次是Raft和ZAB算法(Zookeeper中的实现)

• Raft核心算法

Raft算法的核心是选举和日志复制。

当多台服务器同时对外服务时，服务器如何同步变更成了一个问题。一般是采用主从模型，即一个主服务器(Leader)，多个从服务器(Follower),所有请求都通过Leader服务器处理，Follower服务器只负责备份数据。但假设Leader服务器宕机了，那么Follower服务器中哪个服务器成为新的Leader服务器呢？理论上所有的Follower服务器的副本数据应该是和Leader服务器一致的，但是由于数据延迟、发送顺序不一致等问题，导致某个时刻每个Follower服务器拥有的数据有可能不一样。由此产生的问题需要从以下两方面进行处理。

1. 使用日志写入，而不是直接修改，保证到Follower服务器的同步请求有序而且能够重新计算当前状态，也就是日志状态机模型。
2. 写入时，过半服务器写入成功才算整体成功，也就是Quorum机制。

• 日志状态机模型

在状态机模型中，日志从上往下不断追加，当前状态的任何时间点都可以从索引为1的日志开始计算。有了状态机模型后，分布式一致性的问题就转换成了如何保证所有参与的节点按照同一顺序写入的问题。

• 基于Quorum机制的写入

在一些master/slave模式中，有些master并不关心slave的复制进度。master只负责不断写入自己的日志，通过某些传输方式把变更同步给slave服务器。而在一些严格的全量复制中，当所有的slave服务器全部同步之后，master服务器才会继续写入。主从复制在master服务器宕机之后数据会丢失，而全量复制则性能非常差。相比之下，过半写入的Quorum机制既可以减少数据丢失的风险，性能也不会太差。

现在假设有3台服务器，节点A、B、C。此时正在向这三台服务器写入值，此时节点A的值是2(最新值)，而节点B和C的值都是旧值1.此时当客户端向这个集群取值的时候，如果读取任意两个节点的数据，客户端读取到的数据版本有以下可能。

1. 节点A和B:2与1
2. 节点A和C:2与1
3. 节点B和C:1与1

此时我们可以看到，当读取到B和C的时候，客户端没有读取到最新数据。

此时B节点也写入了新值2，此时我们称为过半写入完成。

当客户端向这个集群任意两个节点取值的时候。

1. 节点A和B:2与2
2. 节点A和C:2与1
3. 节点B和C:2与1

由以上结果我们可以看到，当过半写入的时候，无论哪一种情况，客户端都能读取到最新的值。对于master/slave或者leader/follower模型的分布式系统来说，客户端并不能直接访问所有节点，但是对于系统内的服务器节点来说，可以通过比较各自持有的日志来决定谁成为新的Leader节点，在此过程中，过半写入的数据往往是有效的数据。

• 基于日志比较的选举

假设Leader节点宕机，那么如何从剩下的服务器节点中选举新的Leader节点呢？一般情况下，肯定是希望选择拥有最新数据的节点。

理论上，这个拥有最新数据的节点应该有过半节点的支持，也就是说，集群中超过半数的节点(包括这个拥有最新数据的节点自身)的数据不会比这个节点更新。如果不满足这个条件，集群中可能出现"脑裂"现象，比如几个节点拥护一个Leader节点，而另外几个节点拥护另一个Leader节点。

对于如何判断谁的数据更新，可以通过比较来自其他节点的投票请求中的日志索引和自己本地的日志索引来确定。如果自己本地的日志索引比较大，则不支持对方，否则就支持。

根据这个规则，如果三个节点的日志索引都是2，则A会支持B和C以及自己，其他节点相同，每个节点都是三票。为了减少同时成为Leader节点的概率，要求节点不能重复投票，即每个节点只能投一票。

从以上结果可以看出，除了全部自荐，必会有一个节点被选举出来成为Leader。

对于N个节点的集群(N>0)，假设有M个节点成为Leader节点，那么这些节点都需要有过半的支持票，则总票数为

M * N过半

当节点数为奇数时，N过半为(N + 1) / 2

当节点数为偶数时，N过半为N / 2 + 1

而 M * N过半 <= N

要满足该式成立，M(Leader节点数)为1，N过半<= N成立，而M为2的时候

当节点数为奇数时，2 * (N + 1) / 2 = N + 1,而N + 1 <= N是不满足的

当节点数为偶数时，2 * (N / 2 + 1) = N + 2,而N + 2 <= N也是不满足的

以此类推，M >= 2的时候，M * N过半 <= N都是不满足的。

因此最多只能选出1个Leader节点。

• Raft算法中的选举

在Raft算法中，节点有3个角色

1. Leader
2. Candidate(Leader候选人)
3. Follower

在整个集群稳定状态下，Leader节点为一个，它会通过心跳消息与各个Follower节点保持联系。

包括心跳消息在内，Raft算法中使用的消息类型有以下两种。

1. RequestVote,即请求其他节点给自己投票，一般由Candidate节点发出。
2. AppendEntries，用于日志复制，增加条目，在增加日志条目数量为0时作为心跳信息，一般只由Leader节点发出。

• 逻辑时钟term

为了避免服务器时间不一致，系统也可以安全地推进逻辑时间，Raft算法中的选举有一个整形的term参数。这是一个逻辑时钟值，全局递增。它是Lamport Timestamp算法的一个变体。

当多个进程要维护一个全局时间，首先要让每个进程本地有一个全局时间的副本。Lamport Timestamp算法的流程如下

1. 每个进程在事件发生时递增自己本地的时间副本(加1)。
2. 当进程发送消息时，带上自己本地的时间副本。
3. 当进程收到消息时，比较消息中的时间值和自己本地的时间副本，选择比较大的时间值加1，并更新自己的时间副本。