分布式共识系列文章:
前面几篇文章介绍了Paxos算法,一直是分布式协议的标准,但Paxos算法难于理解,更难以实现。即使google的分布式锁系统Chubby以Paxos算法实现,也遇到了很多坑。为了简化分布一致性算法,斯坦福大学提出了一种Raft算法。
Raft 算法在2013年发表,就是建立在希望得到一个更易于理解的 Paxos 算法的替代品。论文题目《In Search of an Understandable Consensus Algorithm》就可以看出来,可理解性是Raft算法的主要目标之一。到现在已经有了十多种语言的Raft算法的实现框架,最为出名的就是Etcd。
Etcd是CoreOS团队于2013年6月发起的开源项目,它的目标是构建一个高可用的分布式键值(key-value)数据库。
在一个由 Raft 协议组织的集群中有三类角色:Leader(领袖)、Follower(群众)、Candidate(候选人)。
Raft三类角色的状态转换
一个最小的 Raft集群需要三个参与者,这样才可能投出多数票。如下图所示,初始状态下 ABC三个节点开始选举Leader。
Raft协议Leader选举
Leader选举过程中有三种可能的情形发生:
以上前二种情况都能选出 Leader,第三种情况本轮投票无效,出现了平票(Split Votes)。因为没有任何一方获得多数票,所以要发起新的一轮投票。
Raft协议为了不让选举机制反复出现平票,定义了一个随机超时机制(randomized election timeouts)。一旦发生平票,平票的节点会各自再来一次随机timeout倒数,然后重新拉票。先发起拉票的节点就可以优先获得了多数节点的投票。
Raft 协议强依赖 Leader 节点的可用性来确保集群数据的一致性。数据的流向只能从 Leader节点向 Follower 节点转移。
数据从Leader向Follower转移过程
接下来我们看一下,如果在数据转移过程中,Leader挂掉,对数据一致性会造成什么影响。
1. 在数据到达 Leader 节点前,这个阶段 Leader 挂掉。显然不影响一致性。
数据到达Leader前,Leader挂掉
2. 当数据到达 Leader 节点,但未复制给 Follower 节点。这个阶段 Leader 挂掉,数据属于未提交状态。Client 没有收到 Ack确认会认为超时失败,于是发起重试。
Follower 节点重新选主,新的Leader上没有该数据。Client 重新提交数据到新Leader可以成功。原来的 Leader 节点恢复后作为 Follower 加入集群,从当前任期的新 Leader 同步数据,保持和 Leader 数据一致。
数据到达Leader,处于未提交状态
3 当数据到达 Leader 节点,并成功复制给所有Follower节点,但Follower节点尚未向 Leader 响应接收。此时 Leader 挂掉。
虽然数据在 Follower 节点处于未提交状态(Uncommitted),但已经保持一致。重新选出 Leader 后可完成数据提交。此时 Client 由于不知到底提交成功没有,会重试提交。针对这种情况 Raft 要求 RPC 请求实现幂等性,也就是要实现内部去重机制。
当数据到达 Leader 节点,并成功复制给所有Follower节点,但尚未提交
4. 数据到达 Leader 节点,并成功复制给 Follower 部分节点,但还未向 Leader 响应接收。在这个阶段 Leader 挂掉,数据在 Follower 节点处于未提交状态(Uncommitted)且数据不一致。
Raft 协议要求投票只能投给拥有最新数据的节点。这样拥有最新数据的节点会被选为 Leader,再同步数据到 Follower,数据不会丢失并实现最终一致。
5 数据到达 Leader 节点,并成功复制给 Follower 所有或多数节点,数据在 Leader 处于已提交状态,但在 Follower 处于未提交状态。这个阶段 Leader 挂掉,重新选出新 Leader 后的处理流程和上面第3种情况一样。
数据在Leader 节点处于已提交,在Follower处于未提交状态
6 数据到达 Leader 节点,成功复制到 Follower 所有或多数节点,数据在所有节点都处于已提交状态,但由于某种原因,Client未收到Ack响应。这个阶段 Leader 挂掉,集群内部数据其实已经是一致的,Client 重新提交数据,基于幂等策略对一致性无影响。
集群内数据已达成一致
从上面的讨论可知,在Leader向Follower进行数据同步的不同阶段,Leader挂掉也不会影响数据的最终一致性。那么如果由于网络分区,导致双Leader出现,即所谓脑裂的情况,那么对数据一致性会有影响吗?
所谓脑裂,就是集群中出现了双 Leader,这种情况通常是由于网络分区导致。一山不容二虎,一个集群也不能有二主。我们来看一下这种情况下,Raft协议如何将集群恢复到正常。
脑裂最终达成一致
设计Raft算法的目的是实现一种可理解性较好的Multi Paxos算法。看了上面的讲解,大家是否也觉得Raft算法理解起来非常容易呢?
我会持续更新关于物联网、云原生以及数字科技方面的文章,用简单的语言描述复杂的技术,也会偶尔发表一下对IT产业的看法,请大家多多关注,欢迎留言和转发,希望与大家互动交流,谢谢。