etcd 的高可靠性源于 Raft 共识算法,这类似于 Zookeeper 的 Paxos 强一致性算法, 但是 Paxos 却非常的晦涩难懂,想要彻底理解,估计头发要掉不少. Raft 也是用于保证分布式环境下多节点数据的一致性, 但相较于 Paxos 更加易懂.
Raft 的原理可以理解为 Leader Selection 过程的算法.在一个集群中,必然会存在三种可能的角色:
- Leader :集群中仅有一个,是内部数据同步的发起者与外部数据的入口
- Follower : 在集群存在 Leader 的情况下,其余皆是 Follower,它们处理来自 Leader 和 Candidate 的请求
- Candidate :用于继承 Leader 的临时角色,如果赢得了集群中大多数服务器的投票,则将成为 Leader,否则退化为 Follower
Leader 的推举过程
在集群的初始化阶段,所有成员都是先成为 Follower,而后经过一系列艰难的斗争,才会推举出 Leader.
每个 Follower 一开始在内部就会生成一个随机的timer,timer到时间后若还没有其他成员联系自己,则它就自我升级成 Candidate,于此同时向其他成员发起投票请求 RequestVote RPC,开启 Term 环节.
但由于网络延时等原因,此时可能会存在两个情况:
- 当前仅存在一个 Candidate.
- 当前存在多个 Candidate.
如果是只有一个 Candidate 则就会直接当选,但如果有多个 Candidate 时,则会根据先来先得的原则投票,并且每个 Follower 仅给一个Candidate投票,若是获得 Follower 的投票票数最多,则就会成为 Leader,不然就继续当回跟班小弟 Follower .
一旦成为 Leadeer 后,就会向 Follower 发送心跳,来维持 Leader 的身份, Follower 通过心跳感知到 Leader的存在后就会老老实实的继续当小弟.
如果在 timer 超时后未能收到来自 Leader 的心跳,则 Follower 就会认为 Leader 猝,于是就会开启新一轮的 Term.
此时,该集群中的各个 Follower 保存的数据可能会不太一致,因此 Candidate 在发送 Vote 时会带上:
- Term : 自身的选举周期
- LastLogIndex : 最新log的索引值
- LastLogTerm : 最新log是在哪个 Term中记录的
其他的 Follower 在接到该 Vote 后,便会开始与自己记录的信息比较:
- 如果发现 Vote中的 Term 小于 自身的 CurrentTerm,则直接返回 false
- 如果已经给其他 Candidate 投票,则直接返回 false
- 如果 Log 不匹配(log index 太小),则直接返回 false
Log 的 匹配规则时:
- 如果在不同日志中的两个条目有着相同的索引和任期号,则它们所存储的命令是相同的.
- 如果在不同日志中的两个条目有着相同的索引和任期号,则它们之间的所有条目都是完全一样的.
因此如果因Log不匹配而被拒绝后,就会有其他的 Candidate 产生,重复这个步骤,直到有最新的log匹配成功,才能成为 Leader.
数据的同步过程
当 Leader 选举出来后,可能会存在与 Follower 数据不一致的情况,则 Leader 发送的心跳包中包含的term,prevLogIndex,pervLogTerm,commitIndex就会被 Follower 收到后拿去比较,如果 log 不匹配,则会返回 false,然后 Leader 会将prevLogIndex往前拨,直到匹配上prevLogIndex后,返回 true 告诉 Leader 当前记录的最新log, Leader 将会将数据放入 entries字段发送给该 Follower,让其添加或覆盖数据以追平 Leader.
数据的持久化过程
当 Leader 在接收到外部数据后,会先生成一份 log,然后将 log 广播给所有的 Follower.此时 Follower 存在两种可能的回应,
- Follower 听从 Leader 的指令,写入 log 并回应 success
- Follower 认为当前不满足某些条件,并不写入 log,因此会回应 false
这时 Leader 也会存在两种可能:
- Leader 收到的超过半数的 Follower 都返回 success, 则 Leader 就会正式写入持久化数据,然后同样广播给所有 Follower,Follower也会根据之前的情况选择写入或不写入,并将结果返回给 Leader
- Leader 若是收到了超半数的 false 或返回超时,则该次数据写入失败,可能会被后来的过程覆盖掉