谈谈燃气灶谈谈Raft

本文主要参考
极客时间-etcd 实战课
GitChat-分布式锁的最佳实践之：基于 Etcd 的分布式锁
谈到分布式协调组件，我们第一个想到的应该是大名鼎鼎的Zookeeper ，像我们常用的Kafka（最新版本的Kafka已经抛弃了Zookeeper）， Hadoop都用到了Zookeeper ，而另外一个分布式协调组件etcd随着k8s的出现，也映入了我们的眼帘。谈到etcd ，不得不说说etcd的基石—Raft 。
远古时代-单点系统在远古时代，我们数据都只存在于一个节点，不管是读数据也好，写数据也罢，都在一个节点上进行，不存在数据一致性问题，非常简单。
但是慢慢的，单点的问题就显现了——无法高可用，因为我们的数据是单点的，只要这个节点出现问题，我们的系统就不可用了，我们就得提桶跑路了：

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

高可用，避免单点故障，哪怕有个别节点挂了，其他节点还可以继续提供服务。
高性能：
2.1 原本读写数据都在一个节点，节点压力比较大，现在把读写请求分散在不同的节点，节点压力就下降了，性能也就获得了提升。
2.2 原本读写数据都在一个节点，比如说数据节点部署在了广东机房，应用部署在了内蒙古机房，位于内蒙古的应用操作位于广东的数据节点，想想就不怎么“高性能” ，现在由于“多副本” ，可以把数据节点同时部署在内蒙古机房、广东机房，如果是位于内蒙古的应用来操作数据节点，就可以访问内蒙古的数据节点，如果是位于广东的应用来操作数据节点，就可以访问广东的数据节点，大幅度减少访问延迟，性能也就获得了提升。

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

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

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

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

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

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

Raft的由来上面我们了解了单点系统的问题——无法高可用，引入“多副本”的意义，介绍了多副本数据复制的方案，其中主从复制是用的比较广泛的，又分析了三种主从复制方案的优缺点。
既然是主从复制，那么问题就来了， who is master？who is follower？谁是主节点，谁是从节点？数据复制细节是怎样的？异常情况如何处理？Paxos便出现了， Paxos是解决这类问题的“祖师爷” ，它是一种共识算法，非常复杂，实现起来难度也非常高，所以一般来说，实现的时候都会进行一定的简化，像我们比较熟悉的Zookeeper采用的ZAB就是基于Paxos实现的，还有今天要分享的Raft也是基于Paxos实现的。
好了，餐前小面包吃完了，现在进入正餐环节。
Raft角色Raft定义了三种角色：Leader、 Follower 、Candidate ，一个运行良好的Raft集群，只会存在Leader、 Follower两种角色。下面，我们来看看这三种角色的职责。

Leader：领导者，一个Raft集群，只会有一个Leader
1.1 处理来自客户端的读写请求；
1.2 接收到写请求后，会把数据分发给Follower；
1.3 与Follower保持心跳，稳固自己Leader的地位。
Follower：追随者
2.1 处理来自客户端的读写请求，如果是写请求，会转发给Leader；
2.2 接收来自Leader分发的数据；
Candidate：候选者，负责投票选举Leader ，选举胜出后， Candidate转为Leader 。

Raft概述一个应用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】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）的“毛遂自荐”式的投票后，会有两种可能：

A的日志完整度至少和自己一样高，且B节点没有同意其他节点成为Leader ， B节点才会同意A节点成为Leader（当B节点同意A节点成为Leader后，就没办法同意其他节点成为Leader了，每个Candidate只有一张选票）。
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将日志发送给FollowerLeader与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的论文，所以博客中可能会有不少错误，还希望大家指出。

谈谈燃气灶 谈谈Raft

谈谈燃气灶谈谈Raft