分布式一致性算法 Raft
在学术理论界,分布式一致性算法的代表还是 Paxos,但是少数理解的人觉得很简单,尚未理解的觉得很难,大多数人还是一知半解。Paxos 的可理解性 & 工程落地性的门槛很高。斯坦福学者花了很多时间理解 Paxos,于是他们研究出来 Raft。本文主要是介绍 Raft 算法的基本原理。
共识算法就是保证一个集群的多台机器协同工作,在遇到请求时,数据能够保持一致。即使遇到机器宕机,整个系统仍然能够对外保持服务的可用性。
Raft 将共识问题分解三个子问题:
所以,Raft 算法核心流程可以归纳为:
这里先介绍一下日志同步的概念:服务器接收客户的数据更新/删除请求,这些请求会落地为命令日志。只要输入状态机的日志命令相同,状态机的执行结果就相同。所以 Raft 的核心就是 leader 发出日志同步请求,follower 接收并同步日志,最终保证整个集群的日志一致性。
集群中每个节点只能处于 Leader、Follower 和 Candidate 三种状态的一种:
具体的节点状态转换参考下图:
Raft 算法把时间轴划分为不同任期 Term。每个任期 Term 都有自己的编号 TermId,该编号全局唯一且单调递增。如下图,每个任务的开始都** Leader Election 领导选举**。如果选举成功,则进入维持任务 Term 阶段,此时 leader 负责接收客户端请求并,负责复制日志。Leader 和所有 follower 都保持通信,如果 follower 发现通信超时,TermId 递增并发起新的选举。如果选举成功,则进入新的任期。如果选举失败,TermId 递增,然后重新发起选举直到成功。
举个例子,参考下图,Term N 选举成功,Term N+1 和 Term N+2 选举失败,Term N+3 重新选举成功。
具体的说,Leader 在任期内会周期性向其他 follower 节点发送心跳来维持地位。follower 如果发现心跳超时,就认为 leader 节点宕机或不存在。随机等待一定时间后,follower 会发起选举,变成 candidate,然后去竞选 leader。选举结果有三种情况:
当 Candidate 获得超过半数的投票时,代表自己赢得了选举,且转化为 leader。此时,它会马上向其他节点发送请求,从而确认自己的 leader 地位,从而阻止新一轮的选举;
投票原则:当多个 Candidate 竞选 Leader 时:
简单的多,Leader Election 领导选举 通过若干的投票原则,保证一次选举有且仅可能最多选出一个 leader,从而解决了脑裂问题。
选举 leader 成功后,整个集群就可以正常对外提供服务了。Leader 接收所有客户端请求,然后转化为 log 复制命令,发送通知其他节点完成日志复制请求。每个日志复制请求包括状态机命令 & 任期号,同时还有前一个日志的任期号和日志索引。状态机命令表示客户端请求的数据操作指令,任期号表示 leader 的当前任期。
follower 收到日志复制请求的处理流程:
综上, Log Replication 日志复制有两个特点:
举个例子,最上面表示日志索引,这个是保证唯一性。每个方块代表指定任期内的数据操作,目前来看,LogIndex 1-4 的日志已经完成同步,LogIndex 5 的正在同步,LogIndex6 还未开始同步。Raft 日志提交的过程有点类似两阶段原子提交协议 2PC,不过和 2PC 的最大区别是,Raft 要求超过一般节点同意即可 commited,2PC 要求所有节点同意才能 commited。
日志不一致问题:在正常情况下,leader 和 follower 的日志复制能够保证整个集群的一致性,但是遇到 leader 崩溃的时候,leader 和 follower 日志可能出现了不一致的状态,此时 follower 相比 leader 缺少部分日志。
为了解决数据不一致性,Raft 算法规定 follower 强制复制 leader 节日的日志,即 follower 不一致日志都会被 leader 的日志覆盖,最终 follower 和 leader 保持一致。简单的说,从前向后寻找 follower 和 leader 第一个公共 LogIndex 的位置,然后从这个位置开始,follower 强制复制 leader 的日志。但是这么多还有其他的安全性问题,所以需要引入Safety 安全性规则 。
当前的 Leader election 领导选举 和 Log replication 日志复制并不能保证 Raft 算法的安全性,在一些特殊情况下,可能导致数据不一致,所以需要引入下面安全性规则。
选举安全性要求一个任期 Term 内只能有一个 leader,即不能出现脑裂现象,否者 raft 的日志复制原则很可能出现数据覆盖丢失的问题。Raft 算法通过规定若干投票原则来解决这个问题:
Raft 算法规定,所有的数据请求都要交给 leader 节点处理,要求:
这点主要是为了保证日志的唯一性,要求:
Raft 规定:只有拥有最新提交日志的 follower 节点才有资格成为 leader 节点。 具体做法:candidate 竞选投票时会携带最新提交日志,follower 会用自己的日志和 candidate 做比较。
因为日志提交需要超过半数的节点同意,所以针对日志同步落后的 follower(还未同步完全部日志,导致落后于其他节点)在竞选 leader 的时候,肯定拿不到超过半数的票,也只有那些完成同步的才有可能获取超过半数的票成为 leader。
日志更新判断方式是比较日志项的 term 和 index:
下面举个例子来解释为什么需要这个原则,如下图,假如集群中 follower4 在 LogIndex3 故障宕机,经过一段时间间,任期 Term3 的 leader 接收并提交了很多日志(LogIndex1-5 已经提交,LogIndex6 正在复制中)。然后 follower4 恢复正常,在没有和 leader 完成同步日志的情况下,如果 leader 突然宕机,此时开始领导选举。再假设在 Term4 follower4 当选 leader。根据日志复制的规则,其他 follower 强制复制 leader 的日志,那么已经提交却没完成同步的日志将会被强制覆盖掉,这回导致已提交日志被覆盖。
考虑到当前的日志复制规则
上述两条就可能出现已有任期日志被覆盖的情况,这意味着已复制超过半数的以前任期日志被强制覆盖了,和前面提到的日志安全性矛盾。
所以,Raft 对日志提交有额外安全机制:leader 只能提交当前任期 Term 的日志,旧任期 Term(以前的数据)只能通过当前任期 Term 的数据提交来间接完成提交。简单的说,日志提交有两个条件需要满足:
下面举个例子来解释为什么需要这个原则,如下图:
如何解决这个问题呢?Raft 在日志项提交上增加了限制:只有 当前任期 且 复制超过半数 的日志才可以提交。即只有 LogIndex4 提交后,LogIndex3 才会被提交。
Basic Paxos 算法没有 leader proposer 角色,是一个纯粹的去中心化的分布式算法,但是它存在若干不足(只能单值共识 & 活锁 & 网络开销大)。所以才有了以 leader proposer 为核心的 Multi Paxos 算法(由一个去中心化的算法变为 leader-based 的算法)。Raft 算法相当于 Multi Paxos 的进一步优化,主要通过增加两个限制:
下面是我个人的理解:
Raft 协议就是一种 leader-based 的共识算法,算法设计出发点就是可理解性以及工程的落地性。学习总结分布式一致性算法 Paxos 和 Raft 对我们理解、设计、实现、部署、测试分布式系统都大有益处,如果文章有啥不合适的地方,希望提出宝贵意见。
© 2019 - 2023 Liangliang Lee. Powered by gin and hexo-theme-book.