一致性算法raft要点
所属分类 raft
浏览量 1397
raft paxos
Raft 可理解性 ,《In Search of an Understandable Consensus Algorithm》
Raft 集群三类角色
Leader(领袖)
Follower(群众)
Candidate(候选人)
任期 Term
a b c
a 投给自己 , b 和 c 投给 a ,a 成为leader
b 投给自己 , a 和 c 投给 a ,a 成为leader
a b c 都投给自己 ,选举失败
投票无效(Split Votes)
随机休息后(Election Timeout)重新发起投票
随机 timeout,最先从 timeout 中恢复发起投票的一方向还在 timeout 中的另外两方请求投票,这时它们就只能投给对方了,很快达成一致。
选出 Leader 后,Leader 通过定期向所有 Follower 发送心跳信息维持其统治。
若 Follower 一段时间未收到 Leader 的心跳则认为 Leader 可能已经挂了,再次发起选主过程。
Raft 协议强依赖 Leader 节点的可用性来确保集群数据的一致性。
数据的流向只能从 Leader 节点向 Follower 节点转移。
当 Client 向集群 Leader 节点提交数据后,Leader 节点接收到的数据处于未提交状态(Uncommitted),
接着 Leader 节点会并发向所有 Follower 节点复制数据并等待接收响应,
确保至少集群中超过半数节点已接收到数据后再向 Client 确认数据已接收。
一旦向 Client 发出数据接收 Ack 响应后,表明此时数据状态进入已提交(Committed),
Leader 节点再向 Follower 节点发通知告知该数据状态已提交。
Leader挂掉对数据一致性的影响
1.数据到达 Leader 节点前
无影响
2 数据到达 Leader 节点,但未复制到 Follower 节点
3 数据到达 Leader 节点,成功复制到 Follower 所有节点,但还未向 Leader 响应接收
4 数据到达 Leader 节点,成功复制到 Follower 部分节点,但还未向 Leader 响应接收
数据在 Follower 节点处于未提交状态(Uncommitted)且不一致,Raft 协议要求投票只能投给拥有最新数据的节点。
所以拥有最新数据的节点会被选为 Leader 再强制同步数据到 Follower
5 数据到达 Leader 节点,成功复制到 Follower 所有或多数节点,数据在 Leader 处于已提交状态,但在 Follower 处于未提交状态
6 数据到达 Leader 节点,成功复制到 Follower 所有或多数节点,数据在所有节点都处于已提交状态,但还未响应 Client
7 网络分区导致的脑裂情况,出现双 Leader
客户端 重试 幂等
参考
[1]. LESLIE LAMPORT, ROBERT SHOSTAK, MARSHALL PEASE. The Byzantine General Problem. 1982
https://www.microsoft.com/en-us/research/publication/byzantine-generals-problem/
[2]. Leslie Lamport. The Part-Time Parliament. 1998
https://www.microsoft.com/en-us/research/publication/part-time-parliament/
[3]. Leslie Lamport. Paxos Made Simple. 2001
http://microsoft.com/en-us/research/publication/paxos-made-simple/
[4]. Diego Ongaro and John Ousterhout. Raft Paper. 2013
[5]. Raft Website. The Raft Consensus Algorithm
[6]. Raft Demo. Raft Animate Demo
http://thesecretlivesofdata.com/raft/
上一篇
下一篇
jvm相关知识点
ConcurrentHashMap读操作为什么不需要加锁
java里的协程
消息队列知识点
铁娘子董明珠
Redis虚拟槽算法