首页  

分布式一致性算法 Paxos Raft ZAB     所属分类 architecture 浏览量 70
CAP理论
Consistency (一致性)
Availability (可用性)
Partition Tolerance (分区容错性)

BASE理论
Basically Available (基本可用)
Soft state (软状态)
Eventually consistent (最终一致性)

Cassandra 采用 Gossip协议,弱一致性


一致性模型
强一致性(原子一致性、线性一致性)
在任意时刻,所有节点中的数据是一样的
任何一次读都能读到某个数据的最近一次写的数据
和全局时钟下的顺序一致


顺序一致性

任何一次读都能读到某个数据的最近一次写的数据
所有进程的顺序一致,不需要和全局时钟下的顺序一致

弱一致性
最终一致性,随着时间推荐,会最终达到全局一致性

Basic-Paxos
角色分类
Proposer 提案者 , 可以有多个,用于发起一个议案,议案包括议案编号、议案内容
Acceptor 接收者、批准者 ,用于接收Proposer提出的议案,并决定采纳哪一个议案
Learner 学习者、记录者 ,在最终决定采纳某个议案后,进行记录,不做其他事

约束条件
Acceptor 必须接受它收到的第一个议案
Acceptor 只认可接收到的最新的议案(即议案编号最新)
当某个议案被一半以上Acceptor认可后,那么该议案成功

流程
Proposer 广播 ---Prepare(n)---> 所有的 Acceptor

Proposer <---接受--- Acceptor 1
Proposer <---接受--- Acceptor 2
Proposer <---否认--- Acceptor 3

// 如果有一半以上Acceptor接受,那么该议案成功
// 否则隔一个随机时间,更新自己的议案编号,重提
Proposer 广播 ---Accpet(n, value)---> 所有的 Acceptor

// 议案通过
Proposer <---认可--- 所有的 Acceptor ---认可---> Learner [进行记录]

Multi-Paxos
Basic-Paxos每次都要重新选举一个可信任的Proposer,但实际上Proposer不会随时都挂掉
因此,应该先只选举一次可信任的Proposer,后续的议案都由它来发起
当该Proposer挂了 ,再次进行选举即可
该Proposer叫做Leader,Leader只有一个
运作流程
// 第一次,需要选举一个 Leader
Leader 广播 ---Prepare(n)---> 所有的 Acceptor
Leader <---接受--- Acceptor 1
Leader <---接受--- Acceptor 2
Leader <---否认--- Acceptor 3
// 如果有一半以上Acceptor接受,那么选举成功

// 后续一直重复该流程 1
Leader 广播 ---Accpet(n, value)---> 所有的 Acceptor
Leader <---认可--- 所有的 Acceptor ---认可---> Learner [进行记录]

// 后续一直重复该流程 2
Leader 广播 ---Accpet(n, value)---> 所有的 Acceptor
Leader <---认可--- 所有的 Acceptor ---认可---> Learner [进行记录]

// 后续一直重复该流程 3
Leader 广播 ---Accpet(n, value)---> 所有的 Acceptor
Leader <---认可--- 所有的 Acceptor ---认可---> Learner [进行记录]

 
Raft
Raft是Multi-Paxos的简化模型

区别
Raft中追加日志的操作必须是连续的(Multi-Paxos中是并发)
只有拥有最新、最全日志的节点才能够当选Leader(Multi-Paxos中任意节点都可以写日志,无限制)

流程同Multi-Paxos
Leader对应Leader
Acceptor对应Follower

可参考的动态图
https://raft.github.io/
http://thesecretlivesofdata.com/raft/


ZAB
ZooKeeper
基本与Raft相同

不同点
Raft每一次leader的任期叫做term,ZAB中叫做epoch
Raft有leader向follower发送心跳,ZAB相反
选主投票方式不同
事务操作方式不同


ZooKeeper-ZAB
Zookeeper Atomic Broadcast 
Leader选举
Leader挂了,重新选举。
各节点优先投自己一票(myId, zxid),再广播至其他节点。
每个节点对比收到的票,zxid大的优先,zxid相等再按myId大的优先。
选中某个投票后,会再向集群其他节点广播选中的票。
当某个票被集群中超过一半的节点选中后,该票对应的Follower升为Leader


集群消息广播
写操作转发至Leader,由Leader来控制写(保证一致性)。每一次写操作都会更新zxid。
Leader会先向Follower发送一次请求(Propose),如果超过一半的节点回复Ack,执行commit(向所有节点发送),完成本次写操作。



一致性算法raft简介 一致性算法raft要点 CAP和一致性协议 zab协议 zookeeper内部原理 zookeeper知识点整理 zookeeper如何保证数据一致性

上一篇     下一篇
tcpdump使用简介

kafka各版本特性

ThreadLocal原理及最佳实践

springcloud sleuth zipkin 实例

Spring Cloud Sleuth Zipkin原理

《人性的弱点》53条经典总结