etcd学习笔记之理解Raft算法

背景

因为在开发网关时，etcd充当很重要的角色，需要系统性的学习。知识来源华为云容器团队的《云原生分布式存储基石-etcd深入解析》
Raft是一个共识算法，是常用的强一致性、去中心化、高可用的分布式协议

思维导图

复制状态机

Raft是基于复制状态机模型实现
基本思想是一个分布式复制状态机由多个复制单元组成，每个复制单元均是一个状态机，他的状态保存在一组状态变量中。
简单来说

相同的初识状态 + 相同的输入 = 相同的结束状态

一组状态变量（相同的输入）是基于操作日志来实现的

三个存储节点，初始保存变量x = 0;y = 0;
每个节点都收到 x<--3;y<-- 1;y<--9
最后三个节点的变量肯定是 x = 3;y = 9，保证了结果一致性

节点角色

分布式系统中节点存在两种关系模型

• 对称（所有节点平等），
• 非对称（选主模式，主节点拥有决策权）

raft 采用非对称节点关系模型，分为Leader(领导者)、Candidate(候选人)、Follower(群众)

Raft的逻辑时钟-- 任期（Term）

Term 任期：算法将时间划分成任意长度的任期，任期是单调递增
每一个任期开始都是一次选举，当候选人当选后，就会在剩余的时间当领导人

分布式环境时间同步是很大的难题，但是为了识别“过期信息”，时间信息又是必不可少的。所以Raft利用任期ID起到逻辑时钟的作用。
Raft本地维护当前任期值，期变更条件：

• 开始选举
• 和其他节点交换信息，节点之间通信时会对比任期号，更新自己的任期号为收到的最大任期号

领导人选举

选举定时器

每个Raft节点都有一个选举定时器，最开始都以Follower角色启动选举定时器（定时器长度不相等）

心跳

Leader 通过广播心跳包给其他Follower节点，Follower节点收到心跳包之后重置定时器，所以当Follower节点的定时器超时，他就可以认定Leader 已经不存在，开始发起选举。
这里要求广播周期一定要远小于选举定时器的时间

选举过程

1. Follower将本地任期号+1
2. 将自己的状态标记为候选人，经给自己投票
3. 向集群其他成员发送RPC（RequestVote）为自己拉票

投票采取的是先到先得的原则，所以其他节点会将票投给先拉选票的人，当发现自己胜出之后会向其他节点发送心跳包
当收到其他节点的宣称自己的Leader时，会对比其任期号，来选择接受还是拒绝，接受自己将降级成Follower
【问题】：假如大家同时发起选举，都投给了自己，就没有胜出，等待超时之后在进行选举，但是还有可能同时选举，出现上述问题，这里有个小算法是“随机重试”来解决这个问题，就是把超时时间设置成(150 ～ 300ms),所以不是避免这种问题的出现，只是降低选不出Leader的概率。

日志复制

复制流程：

1. 客户端向Leader写请求
2. Leader将指令写入本地日志文件
3. Leader向其他Follower发送RPC(AppendEntries),广播指令
4. Follower 进行一致性检验，选择位置追加Leaeder 的日志条目，并且应答RPC成功
5. 当Leader收到大多数的Follower追加成功后，则说明日志提交成功，则将日志对应到本地状态机中，并返回客户端
6. Leader将提交成功的日志告知大多数的Follower
7. Follower收到提交日志RPC，将日志应用到本地状态机中

提交过程有点类似两阶段提交(2PC)，Leader只需要大多数（majority）节点的回复即可，这样只要超过一半节点处于工作状态则系统就是可用的。

Follower的一致性检验

过程：Leader发送时，会发送当前槽位的上一个槽位信息，Follower收到Leaeder日志广播RPC时，会搜索自己文件当前槽位中是否存在这样的条目，如果不存在则返回失败，就意味着日志与Leader的日志不一致，此时Leaeder会将index-1发送，Follower在进行比较，直到找到相同的位置，并将该位置后所有的日志都用Leaeder的日志进行覆盖
Raft 算法的复制机制保证领导人的日志不会被删除和覆盖。且只要集群中大部分节点时正常的，Raft算法就能接受客户端复制请求。

安全性

选举限制

任何领导人都拥有之前Leader提交的全部日志
一个候选人要想赢得选举必须和集群中大多数节点进行通信，就意味着最少有一个节点上的日志保存了全部已提交的日志
如果某个节点比集群中大多数的节点都新，说明他包含全部已提交的日志。所以在投票时会比较请求方和自己的日志谁更加新，所以选举不仅仅比较任期号，还要比较日志索引号。

日志提交条件额外限制

要求Leader在当前任期至少有一条日志被提交，即被半数的节点写盘

• 只要一个日志条目被存在大多数的服务器上，领导人就知道当前任期可以提交该条目
• 如果领导人在提交日志之前就崩溃，之后的领导人会试着继续完成对日志的复制，但新领导人无法断定存储在大多数服务器上的日志条目一定在之前的任期中被提交。

异常情况

脑裂双Leader问题

网络分区环境下将原先的 Leader节点和Follower节点分隔开，Follower收不到Leader的心跳，发起选举产生新的Leader。这时就产生了双Leader，原先的 Leader 独自在一个区，向它提交数据不可能复制到多数节点所以永远提交不成功。向新的 Leader 提交数据可以提交成功，网络恢复后旧的 Leader 发现集群中有更新任期（Term）的新 Leader 则自动降级为 Follower 并从新 Leader 处同步数据达成集群数据一致。

其他情况

异常情况有很多种情况，其他情况可以参考。
https://www.cnblogs.com/mindwind/p/5231986.html

日志压缩和快照

Raft节点上的日志不可能无限制的增长下去，日志快照用来初始化新节点和重启回放，系统的全部状态都以快照的形式持久化存储，并删除那个时间节点之前的全部日志。
快照文件特点：

1. 每个节点独立创建，只包含已经提交的日志条目
2. 存储某一时刻的复制状态机的状态
3. 全量
4. 存储元数据，比如 被快照取代的最后一个日志条目的索引位置和对应的任期号。
5. 分块存储。

总结与思考

在学习etcd之前，学习过ES集群，mongo集群，kafka集群虽然细节不同，但是感觉多多少少都有很多相似之处，可能思想上都借鉴了Raft共识算法。
本文不是从论文中进行总结，是从书中按照自己的理解总结，算是拾人牙慧。

扩展阅读

https://www.cnblogs.com/xybaby/p/10124083.html
动态理解Raft(这个我感觉比较牛) ：http://thesecretlivesofdata.com/raft/