分布式一致性算法----Raft
博客专区 > AlexT 的博客 > 博客详情
分布式一致性算法----Raft
AlexT 发表于6个月前
分布式一致性算法----Raft
  • 发表于 6个月前
  • 阅读 12
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

Raft 是解决分布式一致性的协议。Raft将分布式系统中的结点分成三种状态:Leader,Follower,Candidate。大致分为如下几步:

一、 Leader Election

(1)所有的结点初始都为 follower状态。

(2)如果followers 不能从Leader听见任何消息就会变成Candidate。

(3)Candidate会从其他结点那请求vote,其他结点会返回自己的vote。

(4)如果这个Candidate从大部分结点那得到vote,则此Candidate变成Leader。

 

二、Log Replication

(1)所有对系统的set等改变都会途径这个Leader。

(2)每一个对系统set的改变都会作为一个Entry添加到结点的log中。下面场景是说向分布式系统中提交set 5。

(3)若Log没有提交,则Node a的值不会改变,并且向Node b与 Node c 同步修改日志

(4)之后leader等待,知道大部分结点将这个Entry写入等待提交。

(5)leaderNode提交,并且node的State变为5,同时告知所有followers ,Entry已经被提交了。

(6) 集群系统状态被同步了。

 

三、TimeOut

在集群中有两个地方可能timeout,第一个是Election timeout。

(1)ElectionTimeout 选举超时是一个Follower等到变成一个Candidate的时间,election timeout 在150ms和300ms之间取随机值。

(2) 在 ElectionTimeout 超时之后,follower 变成了一个candidate 并且开始一个新的election term---即发起vote请求给其他结点。

(3) 如果结点没有为这个vote,则vote并重置自己的ElectionTimeout的时间。若一个候选人拥有大多数的vote,则变成leader。

(4) Leader开始发出Append Entries 消息给所有的folllowers。

(5) 在发消息内部有个timeOut 叫做 heartbeat timeout,所有的消息都是以heartBeat的方式传输的。

(6) Followers 回复每一个Append Entires消息。

(7) 这个election term会继续 直到一个follower停止接受心跳并且变成一个candidate。

(8)若node A挂了,重新选举。node B变成新的leader。

四、 split-brain脑裂处理

split-brain(脑裂) ,若node是偶数个,如下图:Node A和Node C同时发起选举:

    之后 node A与 node C 都有了两个votes,并且不会接受更多的vote。

之后Node A与 Node C会等待等到有新的Candidate 发出 requests vote。

 

五、分区容错

若有5个节点,Node B是leader,假设在A,B与 C D E之间做了分隔,那这时会出现两个leader在不同的terms里。

如果有两个客户端,一个客户端向Node B发送了一个SET 3的请求,然后Node B得到大多数的结点的回复,所有一直不会提交。

另一个客户端,发送set 8到Node C,这时Node C提交。

Node B 需要更高的election term 并且 step down。

Node A和B都会回滚未提交的日志,并且同步新Leader的log。 这时,集群又重新同步了。

 

后续有时间解读一下 Redis的集群方案。

参考资料:

http://thesecretlivesofdata.com/raft/

共有 人打赏支持
粉丝 2
博文 13
码字总数 28763
×
AlexT
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: