raft算法

raft 算法是一种简单易懂的共识算法,它依靠状态机和主从同步的方式,在各个节点之间实现数据的一致性

raft 的两个核心要点:

1.选取主节点

2.同步数据

raft 算法在选取主节点的过程,也是通过多个节点之间的投票竞争

raft 算法为节点定义了三种角色:

1.Leader(主节点)
2.Follower(从节点)
3.Candidate(参与投票竞争的节点/候选人)

选主的流程:

1.在最初的,还没有一个主节点的时候,所有节点的身份都是 follower;每一个节点都有自己的计时器,当计时器达到了超时时间(Election Timeout),该节点会转变为 Candidate

2.成为 Candidate 的节点,会首先给自己投票,然后向集群中其他所有的节点发起请求,要求大家都给自己投票

3.其他收到投票请求且还未投票的 Follower 节点会向发起者投票,发起者收到反馈通知后,票数增加

4.当得票数超过了集群节点的一半,该节点晋升为 Leader 节点;Leader 节点会立即向其他节点发出通知,告诉大家自己才是老大;收到通知的节点全部变为 Follower,同时将自己的计时器清零

这里需要注意,每个节点的超时时间都是不一样的;比如 A 节点的超时时间是 3 秒,B 节点的超时时间是 5 秒,C 节点的超时时间是 4 秒,这样一来 A 节点将会最先发起投票请求,而不是所有的节点同时发起

为什么这样设计呢,设想所有的节点同时发起投票,必然会导致大家的票数差不多,形成僵局,谁也当不成老大

那么,成为 leader 的节点是否就坐稳了老大的位置呢?并不是,Leader 节点需要每隔一段时间向集群其他节点发送心跳通知,表明它还活着;

一旦 Leader 节点挂掉,发不出通知,那么计时到达了超时时间的 Follower 节点会转变为 Candidate 节点,发起选主投票,周而复始.

数据同步的流程:

1.客户端提交数据到 Leader 节点

2.由 Leader 节点把数据复制到集群内的所有 Follower 节点,如果一次复制失败,会不断进行重试

3.Follower 节点们接收到数据,会反馈给 Leader 节点

4.如果 leader 节点接收到超过半数的 Follower 反馈,表明复制成功.于是提交自己的数据,并通知客户端数据提交成功

5.由 Leader 节点通知集群内所有的 Follower 节点提交数据,从而完成数据同步流程

共识算法的应用场景:

1.在用于共享配置和服务发现的 K-V 存储系统 etcd 中,使用的就是 Raft 算法来保证分布式一致性

除了 raft 之外,还有哪些算法解决了拜占庭将军问题:

1.Paxos 算法

早期的共识算法,由拜占庭将军问题的提出者 Leslie Lamport 所发明;谷歌的分布式锁服务 Chubby 就是以 Paxos 算法为基础

2.ZAB 算法

Zookeeper 所用的一致性算法,在流程上和 Raft 算法比较接近

3.PBFT 算法

区块链技术所用的共识算法之一,适用于私有链的共识