分布式一致性算法:Raft

2019-05-23 20:05:18

阅读次数 - 381

架构 分布式 一致性

前面介绍了《分布式一致性算法:Paxos》。可以看出,Paxos算法的的原理其实是比较晦涩难懂的。因为 Paxos 难懂,也难以实现,所以斯坦福大学的教授在2014年发表了新的分布式协议 Raft。与 Paxos 相比,Raft 有着基本相同运行效率,但是更容易理解,也更容易被用在系统开发上。

etcd项目就是使用的Raft算法,etcd被广泛应用于分布式系统中,比如k8s就是使用etcd来作为信息存储的。

Raft算法是怎样实现分布式一致性的呢?它主要有两个过程:

  • 选主过程
  • 基于日志复制的数据同步过程

下面来介绍一下Raft具体是怎么做的。

三种状态

Raft中,一共有三种状态。每个节点都处于某个状态,每个节点都可以在三种状态中间转换。这三种状态分别是:

  • Follower状态,从结点,我们用无边的圆来表示
  • Candidate状态,有资格参与竞选的结点,我们用虚线边的圆来表示
  • Leader状态,主结点,用实线边的圆来表示。

三种状态

选举过程

正常状态的选举

先来看一下如果系统中各结点和网络都正常,它是怎么实线主结点的选举和数据同步的。

每个节点上都有一个倒计时器,时间随机在150ms到300ms之间。节点在以下两种情况下回重置倒计时器:

  • 收到选举请求
  • 收到Leader结点的心跳(Heartbeat)

然后看一下选举过程:

  1. 一开始,三个结点都是Follower状态,每个节点开始自己的随机倒计时。
  2. 最先倒计时结束的那一个,就变成Candidate状态,开始给其它结点发送选举请求。
  3. 其它结点如果收到这个请求,就重置自己的倒计时器并返回“同意”的响应。
  4. Condidate结点如果收到了超过半数(包括它自己)的结点同意,就变成Leader结点,然后会不断向其它结点发送心跳(Heartbeat)来维持这个状态。

正常选举

如果Leader结点不可用

这个时候如果Leader结点宕机了或由于其它原因不可用,那Follower结点收不到心跳,倒计时结束后就会产生另一个选举过程,产生另一个Leader结点。

Leader结点不可用

那这个时候Leader结点C醒来了怎么办呢?它会收到来自新Leader结点A的心跳,通过对比Term,发现它的Term更高,于是自动降级为Follower状态。

如果两个结点同时计时器结束

如果两个结点同时timeout,或者由于网络的原因,存在Leader确认之前多个Follower结点变成Candidate的情况。这个时候会发生什么呢?

我们其实可以设想一下。假如有4个结点。其中两个结点同时计时器结束。这个时候两个结点都会广播选主请求。这可能导致有些结点投票给C,有些结点投票给D:

候选结点

这个时候,所有结点都会重新开始计时。直到进入正常状态(只有一个节点最先计时结束)。

同时结束

这里有一个小细节:Follower结点只接受最先收到的选主请求,会丢弃后来的所有选主请求

日志复制过程

正常状态的复制

日志复制过程是基于“心跳”来做的。过程如下:

  1. 首先,客户端会给Leader结点发送一个写请求;
  2. Leader结点会将这个写操作先放到日志里。这里我们用红色来表示它;
  3. 然后,Leader会再下次心跳的时候发送这个“写请求”;

发送写请求

  1. 然后从节点响应,并在本地也创建这个日志;
  2. 一旦Leader结点收到过半数(包括它自己)结点的确认,就持久化这个修改(我们这里用黑色来表示)。

收到确认

  1. Leader结点返回响应给用户,修改成功;
  2. 与此同时,发送心跳给从节点,告诉他们可以持久化这个修改了;
  3. 从节点收到消息后,持久化这个修改;

网络分区如何处理?

网络分区是一种分布式网络故障的现象。通俗的说,就是原本在一个网络的结点,由于网络故障,变成了两个区域,结点只能与部分结点进行通信。这样就可能会导致两个Leader结点。如图:

网络分区

假设最开始网络是好的,B结点选举为Leader结点。后来出现了暂时的网络分区,B结点仍然是Leader结点,而另一个分区里面重新进行了选举,C结点成功成为新的Leader结点。

这个时候,一个客户端给B结点发送了一个写请求,设置某个变量为3:

给B结点写请求

然后B结点按照正常流程走。但是因为收不到“过半数”从节点的确认,所以一直不能持久化,只是记录日志

这个时候另一个结点给C结点发送了一个请求,设置同样一个变量为8。C结点按照正常流程处理,所有同一网络分区的结点都能够持久化,把这个变量设置成了8。

C结点写请求

然后网络恢复了。

B结点收到来自C结点的心跳,并且发现它的Term比自己大,于是降级成为Follower结点,并丢弃本地的日志,并根据C结点心跳发来的信息,持久化设置变量为8。

恢复分区

这里其实笔者有一个疑问:如果恢复分区故障前,C结点还处理了其它客户端的请求,那再恢复分区故障后,会在心跳里带上这段时间所有的修改吗?它是如何判断哪些修改属于故障期间的呢?还是把本地的日志全部发出去,那这样会不会数据量太大?

我人为这个可能要看具体的实现。笔者的猜想是,C结点应该是能够知道什么时候故障发生的(即收不到来自B结点的心跳的时候),把这个时间点存下来。继而它是可以知道哪些是属于故障期间的修改的。在故障期间,它会把这些所有的修改都发送出去。直到恢复正常网络为止。


本文所有截图和动画均来自这个动画示例,非常生动明了,推荐可以看一遍。

感谢阅读


觉得文章还不错?点击下方按钮分享吧!

评论

快来占个沙发吧~


TO: