分布式系统如何保证一致性

分布式一致性算法概要

随着各种高并发访问、海量数据处理等应用场景越来越多，为了应对这些使用场景，分布式系统应运而生。分布式系统得以发展，得益于诸多优点，比如：可以避免 单点故障 ，容易 横向扩展 等。所谓单点故障指的是：单个组件发生故障会导致整个系统的瘫痪，而容易横向扩展的意思是我们可以通过增加机器来提高整个系统的性能。分布式系统在带来诸多优点的同时，也带来了一些挑战，我们下面来重点描述清楚其中的一个核心挑战： 在分布式系统中如何保证数据的一致性 。关于分布式系统的基本概念，可以参考相关的理论书籍。

在众多分布式一致性协议中， paxos 算法经过了严格的数学证明。然而由于该算法非常难以理解，尤其是在各种系统的实现时，一般采用 paxos 的简化版本或者 paxos 的一些变种协议，比如 Raft 和 Zab 等。为此，本文选取 Raft 算法来进行介绍。我们可以通过构造一个如下的应用场景来帮助我们理解一个算法。

 

以一个数据存储系统为例，如果 client 想要在 server 上设置一个值，假如一开始有一个 server 和 一个 client，此时只要一个server 完成值的设置即可。可是如果有多个 server 存在的话，要如何保证所有的 server 节点上存储的值是一致的呢？如果各节点的初始状态一致，每个节点执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。

Raft 算法介绍

在一个由 Raft 协议组织的集群中有三类角色：

• Leader（领袖）
• Follower（群众）
• Candidate（候选人）

每个节点都会处于以上三种角色中的一种。

算法的主体大致可分为2个过程：

• 选举(Leader Election)
• 日志同步(Log Replication)

下面我们分别介绍 Raft 算法中的选举流程和日志同步流程，随后会介绍 Raft 算法对一些异常情况的处理。

选举

选举和现实社会中的民主选举制度很像，刚开始没有 Leader，所有集群中的参与者都是 Follower, 当 Follower 超过选举超时时间 ( election timeout ) 没收到来自 Leader 的心跳报文，则成为 Candidate，增加任期 ( Term ) 并向其他节点发起新的选举请求。接收到请求的节点如果还没投票，则投票给该节点，并重置自己的超时时间。如果某个 Candidate 节点接收到的选票的个数占大多数（超过 1/2）， 它就会成为 Leader 节点，这就是所谓的 Leader election 的过程。每隔一定时间向 Follower 发送心跳报文来维持自己的 『统治』地位。

集群中的每个节点都处于以上三种角色中的一种，其状态转换图可以总结如下：

 

 

 

下面通过几个例子来帮助我们理解这个选举过程：

1. 可以正常选举出 Leader 的例子 ：

 

 

 

在此例子中，一共有三个节点，复现流程如下：

• 节点 B 首先出现心跳超时，然后变成 Candidate 角色。
• 节点 B 首先把自己宝贵的一票投给自己，然后请求其他节点也将赞同票投给自己。
• 节点 A 和 C 此时还未出现超时，仍然处于 Follower 角色，接收到请求后，投票给了 节点 B。
• 节点 B 接收到的赞同票超过半数，成为 Leader 节点。

2. 平分选票的情况

由于 Raft 协议并不要求集群中的节点个数为奇数，于是在四个节点的集群中，可能出现如下的情况：

 

 

 

复现流程如下：

• 节点 B 和 C 几乎同时心跳超时，成为 Candidate 角色。
• 节点 B 和 C 均将自己的赞同票投给自己。
• 节点 A 投给了节点 B，而 节点 D 则投给了节点 C。
• 出现两个 Candidate 的选票相同的情况。

当出现这种情况的时候，没有任何一个节点接收到的赞同票超过半数，于是此选举过程不会有 Leader 角色出现。大家各自等待超时，然后开启下一轮的选举流程。

疑问：那有没有可能在下一轮的选举过程依然出现平分选票的情况？答案是有的，可是 Raft 有一个机制可以避免此种情况持续发生： 每个节点的超时时间都是随机的 ，这样就可以尽量避免多次出现以上的情况。

 

3. 选举流程要点总结

「1」Leader 角色通过发送心跳报文来维护自己的统治地位。「2」Follower 角色接收不到心跳报文，则超时开始下一轮的选举。「3」每个节点的超时时间都是随机的。「4」成为 Leader 节点需要赞同票超过半数。「5」选举结束，所有除 Leader 的候选人又变回 Follower 服从 Leader。

日志同步

当选举完成后，客户端进行的操作都要通过 Leader 来进行。Leader 接受到客户端发来的操作请求后，首先记录到日志中，此时为 uncommitted 状态。然后在下一个心跳报文中通知所有 Follower，当大多数 Follower 响应 ACK 后，Leader 响应客户端，进入 committed 阶段，并向 Follower 发送 commit 通知应用( Apply )操作。

日志同步流程如下：

 

 

 

上图中的序号对应一个存储的步骤， 日志同步 流程总结如下：「1」client 给 Leader 发送一个操作请求，假设为 SET X=8。「2」Leader 会把 SET X=8 这个操作记录到本地 log，此时为 uncommited 状态，同时将这个操作发送给所有的 Follower。「3」Follower 接收到操作请求后，也将 SET X=8 这个操作记录到本地 log（uncommited 状态），然后给 Leader 回复 ACK 信息。「4」Leader 节点当接收到的 ACK 超过半数后，给 client 回复 ACK 信息，进入 commited 阶段。「5」Leader 节点首先应用自己的 log，然后将 commit 消息发送给 Follower, 让 Follower 也 应用自己存储的日志信息。

 

Raft 中的异常处理

我们已经介绍了 Raft 算法的正常处理流程，然而现实总是很骨感，会出现各种异常的情况。client 和 Leader 之间的通信异常，不会影响到集群内部状态的一致性，不再赘述；如果在一个任期内，Follower 角色宕机，处理流程比较简单。其呈现出来的现象就是 步骤「3」异常，然而只要 Leader 能够接收到超过半数的 ACK，就不会影响到正常的存储流程。但是 Leader 角色会针对该 Follower 节点，持续进行步骤 「2」 的动作，直到接收到步骤 「3」的回应信息或者我们把该 Follower 节点从集群中拿掉；Raft 协议强依赖 Leader 节点的可用性来确保集群数据的一致性。下面重点介绍在各种情况下 Leader 节点出现故障时，Raft 协议是如何保障数据一致性的。

1. 写操作 到达 Leader 节点，但尚未同步到 Follower 节点

此刻集群的状态如下，用方框中的灰色表示当前处于 uncommited 状态。

 

 

 

如果集群在此状态，Leader 节点宕机，则 Raft 的处理流程如下：「1」Follower 节点超时，然后选举出新一任期的 Leader，然后它并没有处于 uncommited 状态的日志。「2」Client 节点由于 Ack 超时，可安全发起重试。「3」原来的 Leader 节点恢复后以 Follower 角色重新加入集群。并从当前任期的新 Leader 处同步数据，可能会覆盖原来处于 uncommited 状态的日志。

2. 写操作 到达 Leader 节点，且将写操作同步到 Follower 节点，但还未向 Leader 回复 ACK 信息。

此刻集群的状态如下，用方框中的灰色表示当前处于 uncommited 状态。

 

如果集群在此状态，Leader 节点宕机，则 Raft 的处理流程如下：「1」Follower 节点超时，然后选举出新一任期的 Leader，并且它存在处于 uncommited 状态的日志。「2」新的 Leader 节点假装没有刚才的选举过程，继续从步骤（2）开始执行，以完成数据的提交。「3」Client 节点由于 ACK 超时，可安全发起重试。「4」原来的 Leader 节点恢复后以 Follower 角色重新加入集群。并从当前任期的新 Leader 处同步数据。

此时，在上面步骤「1」中选举新的 Leader 节点时，需要满足一个限制条件，即新的 Leader 节点需要具有最新的日志信息，所谓的最新是通过任期和日志的偏移量两个参数来判定的，这个限制是为了解决只有部分 Follower 节点接收到写操作请求的情况。

3. Leader 节点接收到写操作的 ACK 信息，处于 commited 状态，然而 Follower 处于 uncommited 状态。

此种情况是由于，在步骤（5）执行过程中，Leader 宕机导致的，此刻集群的状态如下，用方框中的灰色表示当前处于 uncommited 状态，用方框中的黑色表示当前处于 commited 状态，同时圆圈中的值表示操作已经生效。

 

 

 

对于此种情况，Raft 协议的处理流程和上面情况2的处理流程是一样的。

4. 脑裂

由于网络故障，产生分区将原先的 Leader 节点和 Follower 节点分隔开，Follower 收不到 Leader 的心跳将发起选举，产生新的 Leader，这时就产生了双 Leader，这就是所谓的脑裂。这种情况下某些 Leader 由于获取不到大多数的投票，所以数据永远不会提交成功。当网络故障恢复后，旧的 Leader 发现有 Term 更新的 Leader 存在，则自动降级为 Follower 并从最新的 Leader 同步数据达成集群一致。

总结

本文以 Raft 协议为契机来介绍分布式环境中的一致性。首先介绍了 Leader 选举和日志同步的过程，然后介绍了 Raft 协议是如何处理各种异常情况的。通过 Raft 协议的学习，不仅可以对分布式一致性有一个概括性的了解，同时也会有助于对其他一致性协议（比如 paxox）的学习。在此基础上，可以尝试阅读一些 Raft 开源的实现, 以加深进一步的理解。