首页  

一致性算法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虚拟槽算法