谈谈Raft
阅读原文时间:2022年01月09日阅读:4

本文主要参考

极客时间-etcd 实战课

GitChat-分布式锁的最佳实践之:基于 Etcd 的分布式锁

谈到分布式协调组件,我们第一个想到的应该是大名鼎鼎的Zookeeper,像我们常用的Kafka(最新版本的Kafka已经抛弃了Zookeeper),Hadoop都用到了Zookeeper,而另外一个分布式协调组件etcd随着k8s的出现,也映入了我们的眼帘。谈到etcd,不得不说说etcd的基石—Raft。

在远古时代,我们数据都只存在于一个节点,不管是读数据也好,写数据也罢,都在一个节点上进行,不存在数据一致性问题,非常简单。

但是慢慢的,单点的问题就显现了——无法高可用,因为我们的数据是单点的,只要这个节点出现问题,我们的系统就不可用了,我们就得提桶跑路了:

作为有追求的软件开发者,肯定不允许这样的情况,所以就引入了“多副本”的概念,也就是说一份数据,同时在N个节点保存,这样做的好处也显而易见:

  1. 高可用,避免单点故障,哪怕有个别节点挂了,其他节点还可以继续提供服务。

  2. 高性能:

    2.1 原本读写数据都在一个节点,节点压力比较大,现在把读写请求分散在不同的节点,节点压力就下降了,性能也就获得了提升。

    2.2 原本读写数据都在一个节点,比如说数据节点部署在了广东机房,应用部署在了内蒙古机房,位于内蒙古的应用操作位于广东的数据节点,想想就不怎么“高性能”,现在由于“多副本”,可以把数据节点同时部署在内蒙古机房、广东机房,如果是位于内蒙古的应用来操作数据节点,就可以访问内蒙古的数据节点,如果是位于广东的应用来操作数据节点,就可以访问广东的数据节点,大幅度减少访问延迟,性能也就获得了提升。

引入了“多副本”后,带来的第一个问题就是多节点数据如何复制,有两个大方向:

  1. 主从复制,一个节点是主节点,其他节点都是从节点,当主节点收到写请求后,再把数据分发给从节点。
  2. 去中心化复制,任意节点都可以接收写请求,再把数据分发给其他节点,这种方案听起来就比较头疼——如何处理各种冲突。

大部分系统都是采用的主从复制,主从复制也有不同的实现方案:

  1. 同步复制,主节点收到写请求后,把数据分发给所有的从节点,从节点接收到数据后,给主节点一个响应,直到所有的从节点都响应了主节点,主节点才能响应客户端。这种方案确保了数据的一致性,但是可用性却降低了,只要有一个节点出现故障,整个系统就会不可用。
  2. 异步复制,主节点收到写请求后,立刻响应客户端,同时后台异步的将数据分发给从节点,如果从节点还没有收到数据,主节点或者从节点或者主节点和从节点间的网络出现故障了,那数据就不一致了,但是可用性却是最高的。
  3. 半同步复制,介于同步复制和异步复制之间,主节点收到写请求后,把数据分发给所有的从节点,从节点接收到数据后,给主节点一个响应,直到主节点收到了N个从节点的响应,主节点才能响应客户端。在一致性,可用性上进行了平衡和取舍。

注意,同步复制是主节点收到了所有从节点的响应,才能响应客户端,而半同步复制是主节点收到了N个从节点的响应,就能响应客户端,N可以是如下的情况:

  • 可以是1,也可以是2。
  • 可以是所有从节点的数量,这样就接近于同步复制了。
  • 可以是0,这样就接近于异步复制了。
  • 比较好的方案,N=所有从节点的数量/2+1。

上面我们了解了单点系统的问题——无法高可用,引入“多副本”的意义,介绍了多副本数据复制的方案,其中主从复制是用的比较广泛的,又分析了三种主从复制方案的优缺点。

既然是主从复制,那么问题就来了,who is master?who is follower?谁是主节点,谁是从节点?数据复制细节是怎样的?异常情况如何处理?Paxos便出现了,Paxos是解决这类问题的“祖师爷”,它是一种共识算法,非常复杂,实现起来难度也非常高,所以一般来说,实现的时候都会进行一定的简化,像我们比较熟悉的Zookeeper采用的ZAB就是基于Paxos实现的,还有今天要分享的Raft也是基于Paxos实现的。

好了,餐前小面包吃完了,现在进入正餐环节。

Raft定义了三种角色:Leader、 Follower 、Candidate,一个运行良好的Raft集群,只会存在Leader、 Follower两种角色。下面,我们来看看这三种角色的职责。

  1. Leader:领导者,一个Raft集群,只会有一个Leader

    1.1 处理来自客户端的读写请求;

    1.2 接收到写请求后,会把数据分发给Follower;

    1.3 与Follower保持心跳,稳固自己Leader的地位。

  2. Follower:追随者

    2.1 处理来自客户端的读写请求,如果是写请求,会转发给Leader;

    2.2 接收来自Leader分发的数据;

  3. Candidate:候选者,负责投票选举Leader,选举胜出后,Candidate转为Leader。

一个应用Raft的集群只会有一个Leader,其他节点都是Follower:

  • Follower只是被动的接收来自Leader、客户端的请求,并且响应,不会主动发起请求,如果接收到了来自客户端的写请求,会把请求转发给Leader。
  • Leader会处理来自客户端的读写请求,如果接收到了写请求,还会将数据分发给Follower,让Follower的数据和自己保持同步。

为了简化逻辑,Raft将一致性问题拆分成了三个子问题:

  • 选举:集群刚启动,或者Leader宕机,就需要选举出新的Leader。
  • 日志复制:Leader处理来自客户端的写请求,然后把日志(数据)分发给Follower强制Follower的数据和自己保持一致。
  • 安全性:由Leader只附加原则、Leader完全特性、日志匹配三个特性保证。

下面我们将围绕这三个子问题,进行较为详细的介绍,不过在这之前,需要再介绍几个专业名词:

  • Term:届数、任期,集群刚启动Term为0,有新的Leader产生,Term就会+1(自增),在ZAB协议中,用Epoch表示,概念是类似的。
  • Index:索引,每个日志(数据)都对应了一个索引。
  • 日志:数据,这里的日志并不是指的我们在开发中,打印出来,帮助我们分析、排查问题的日志,也不是用户的操作日志,而是数据的概念。

了解了这三个专业名词之后,我们就要开始介绍选举、日志复制、安全性三个子问题了:

Raft集群启动——没有Leader,或者Leader宕机——没有Leader,Follwer就接收不到来自Leader的心跳,持续一段时间后,Follwer就会转为Candidate,进入投票流程,如果Candidate收到大多数Candidate同意自己成为Leader的投票,就会升级为Leader,此时Term就会+1。

Leader宕机,又会进入新一轮的选举。

从这里看出,Follwer和Candidate是可以相互转换的,Follwer是无法直接转为Leader的,但是Leader可以直接转为Follwer(Leader转为Follower的时机,后面会说到):

下面我们就来看看一个应用Raft的集群启动,选举过程中的细节:

第一阶段:所有节点都是Follower

一个应用Raft的集群刚启动,所有节点都是Follower,此时Term为0,由于接收不到来自Leader的心跳(Leader还没有产生,肯定接收不到来自Leader的心跳),并持续一段时间,Follower转为Candidate,Term自增。

第二阶段:所有节点都是Candidate

第一阶段后,所有节点都从Follower转为了Candidate,这个时候,有一个新的概念:选举定时器。每个节点都有一个选举定时器,选举定时器的时间是随机的,且很大概率上,每个节点的选举定时器的时间都不同。节点的选举定时器达到一定时间后,此节点会向所有其他节点发起“毛遂自荐”式的投票。

第三阶段:Candidate判定

节点(假设是B)收到其他节点(假设是A)的“毛遂自荐”式的投票后,会有两种可能:

  1. A的日志完整度至少和自己一样高,且B节点没有同意其他节点成为Leader,B节点才会同意A节点成为Leader(当B节点同意A节点成为Leader后,就没办法同意其他节点成为Leader了,每个Candidate只有一张选票)。
  2. A的日志完整度没有自己高,且A节点没有同意其他节点成为Leader,B节点就会拒绝A成为Leader,并且将票投给自己。

第四阶段:Candidate转为Leader

正常情况下,经过一轮的选举,会有一个Candidate可以获得半数以上节点的投票,此节点就成为了Leader,Leader会告知其他节点,其他节点就会从Candidate转为Follower。

如果一轮的选举后,没有Candidate获得半数以上节点的投票,就会再次进行选举。

选举定时器的作用

让我们想想这个选举定时器有什么作用,假设现在有3个节点:Follwer A、Follwer B、Leader C,由于某些原因,Leader C宕机了,A、B就会从Follwer转为Candidate,进入投票流程,选出新的Leader。Candidate A、Candidate B两个节点同时发起“毛遂自荐”式的投票,极有可能出现以下的情况:

  • A节点收到了B“毛遂自荐”式的投票后,发现自己已经投了自己,就会拒绝B成为Leader
  • B节点收到了A“毛遂自荐”式的投票后,发现自己已经投了自己,就会拒绝A成为Leader

然后就尴尬了:一个集群中有三个节点,Candidate要成为Leader,至少要获得两个节点的同意,现在并不满足这个条件,就需要重新进行选举,正是引入了选举定时器,所以一般不会发生这种情况。

Follower认为Leader挂了的时机

在前面,我们说到Follwer就接收不到来自Leader的心跳,持续一段时间后,Follwer就会转为Candidate。那么就产生了两个问题,Leader与Follower心跳间隔的时间是多少,到多长时间还接收不到Leader的心跳 ,Follower才认为Leader挂了。

在etcd中,这两个参数是可以配置的,etcd的Leader与Follower默认心跳间隔是100ms,默认最大容忍时间是1000ms,这个默认最大容忍时间实在是太小了,需要进行适当的增大,否则很容易触发选举,影响集群的稳定性,当然也不能增加的很大,不然Leader真的挂了,需要过好久,才能触发选举,也影响集群的稳定性。

Leader转为Folllower、无效选举、etcd如何避免

为了方便大家阅读,避免往上翻,我把Raft角色转换的图片再复制下:

可以看到Follower无法直接转为Leader,但是Leader可以直接转为Follower,那么在什么情况下,Leader可以直接转为Follower呢?

假设,现在有3个节点:Follwer A、Follwer B、Leader C,Leader C宕机了,A、B就会从Follwer转为Candidate,进入投票流程,选出新的Leader,新的Leader会从A、B中诞生。Leader C复活后,发现现在已经有新的Term了,现在的天下已经不是自己的了,就会发出这样的感叹:

曾经的Leader C就会默默的转为Follower,假设网络原因,C突然无法与A、B进行联通,它就会不断的自增Term,发起投票,但是这是无效的,因为无法与A、B进行联通。

网络问题修复后,新的Leader收到了大于自己的Term,Leader就会陷入自我怀疑,也会发出这样的感叹:

Leader就会默默的转为Follower。

由于此时集群中没有Leader,就会进入选举。节点C的数据是很旧的,所以C肯定在选举中落败,这个选举是毫无意义的,且会影响集群的稳定性。

为了避免问题,3.4版本的etcd新增了一个参数:PreVote。开启PreVote后,Follower在转为Candidate前,会进入PreCandidate,不自增Term,发起预投票,如果多数节点认为此节点有成为Leader的资格,才能转为Candidate,进入选举。

不过,PreVote默认是关闭的,如果有需要,可以打开。

看到预投票、投票,不知道大家有没有想到2PC,这应该就是2PC的一个应用吧。

在一个Raft集群中,只有Leader才能真正处理来自客户端的写请求,Leader接收到写请求后,需要把数据再分发给Follower,当半数以上的Follower响应Leader,Leader才会响应客户端。如果有部分Follower运行缓慢,或者网络丢包,Leader会不断尝试,直到所有Follower都响应了客户端,保证数据的最终一致性。

从这里可以看出,Raft是最终一致性,那么应用Raft的etcd也应该是最终一致性(从存储数据的角度来说),但是etcd很巧妙的解决了这个问题,实现了强一致性(从读取数据的角度来说)。Zookeeper处理写请求,从宏观上来讲,和Raft是比较类似的,所以Zookeeper本身并不是强一致性的(更准确的来说,从Zookeeper服务端的角度来说,Zookeeper并不是强一致性的,但是客户端提供了API,可以实现强一致性),很多地方都说Zookeeper是强一致性的,其实这是错误的,最起码,我们调用普通API的时候,Zookeeper并不是强一致性的。

让我们来看看日志复制过程中的细节。

第一阶段:客户端提交写请求到Leader

如果客户端把写请求提交给了Follower,Follower会把请求转给Leader,由Leader真正处理写请求。

第二阶段:Leader预写日志

Leader收到写请求后,会预写日志,日志为不可读,这就是传说中的WAL。

第三阶段:Leader将日志发送给Follower

Leader与Follower保持心跳联系,会把日志分发给Follower,这里的日志可能会存在多个,因为在一个心跳时间间隔内,Leader可能收到了来自客户端的多个写请求。Leader同步给Follower的日志,并不是仅仅只有当前的日志,还会包含上一个日志的index,term,因为Follower要进行一致性检查。

第四阶段:Follower收到Leader的日志,进行一致性检查

Follower收到Leader的日志,会进行一致性检查,如果Follower的日志情况和Leader给的日志情况不同,就会拒绝接收日志。

一般来说,Follower的日志是和Leader的日志保持一致的,但是由于某些情况,可能导致Follower的日志中有Leader没有的日志,或者Follower的日志中没有Leader有的日志,或者两种情况都有。这个时候,Leader的权限就会凸显,它会强制Follower的日志,与自己保持一致。具体是怎么做的,我们后面再说,先看整体流程。

第五阶段:Follower预写日志

一致性检查通过,Follower也会预写日志,日志为不可读。

第六阶段:Leader收到大多数Follower响应,提交日志

Leader收到大多数Follower的响应后,会提交日志,并把日志应用到它的状态机中,此时日志是可读的。

第七阶段:Leader响应客户端

Leader响应客户端,经过这几个阶段,Leader才能响应客户端。

第八阶段:Leader通知Follower提交日志

Leader与Follower保持心跳联系,会通知Follower:你们可以提交日志了。可千万别忘了,在第五阶段,Follower也只是进行了日志预写。

第九阶段:Follower提交日志

Follower接收到Leader的提交日志通知后,会进行日志提交,并把日志应用到它的状态机中,此时日志是可读的。

第十阶段:收尾

可以来到第十阶段,说明至少大多数Follower和Leader是保持一致的,可能还会有部分Follower因为性能、故障等原因,没有和Leader保持一致,Leader会不断的尝试,直到所有的Follower都和Leader保持一致。

一致性检查失败,怎么办?

在第四阶段,说到Follower收到了Leader的日志后,会进行一致性检查,如果成功还好说,如果失败,怎么办呢?

Leader针对每个Follower都维护了一个nextIndex。当Leader获得权力的时候,会初始化每个Follower的nextIndex为自己的最后一条日志的index+1,如果Follower的日志和Leader的日志不一样,那么一致性检查就会失败,就会拒绝Leader。Leader会逐步减小此Follower对应的nextIndex,并进行重试,说白了,就是回溯,找到两者最近的一致点。找到两者最近的一致点后,Follower会删除冲突的日志,并且应用Leader的日志,此时,Follower便和Leader保持一致了。

Raft集群的安全性是由三个特性来保障的:Leader只附加原则、Leader完全特性、日志匹配特性。

Leader只附加原则

让我们设想一种场景:Leader响应客户端后,宕机了,发生这样的事情意味着什么?既然Leader已经响应客户端了,说明Leader已经提交日志了,并且大多数Follower已经进行了预写日志,只是目前还没有提交日志,那这个日志会被删除吗?

不会,因为Leader只能追加日志,而不能删除日志。发生这种情况,说明大多数Follower已经进行了预写日志,这个写请求是成功的,那新的Leader也一定会包含这条日志(如果不包含这条日志,说明日志完整度不高,会在选举中落败),新的Leader会完成前任Leader的“遗嘱”,完成这个日志的完全提交(所有Follower都提交)。

Leader完全特性

Leader完全特性指的是某个日志在某个Term中已经提交了,那么这个日志必定会出现在更大的Term日志中。

日志匹配特性

日志匹配特性在上文已经说过了,就是Follower在接收到Leader的日志后,会进行一致性检查,如果一致性检查失败,会进行回溯,找到两者日志最近的一致点,Follower会删除冲突的日志,与Leader保持一致。

博客到这里就结束了,在写博客的时候,翻阅了很多文章,很多文章写的挺细致,挺优秀,但是真正读起来,并不是那么好理解,所以本篇博客的目标就是坐上马桶上也能看懂。

由于本人水平有限,并没有阅读过etcd的源码,也没有读过Raft的论文,所以博客中可能会有不少错误,还希望大家指出。