本文转载自: 分布式一致性算法
用于自己学习的记录
CAP理论
一般来说,对于一个分布式系统,不能同时满足以下三点:
- Consistency (一致性)
- Availability (可用性)
- Partition Tolerance (分区容错性)
BASE理论
BASE解释:即使分布式系统无法做到强一致性,但可以采用适当的间接性手段,实现弱一致性,最终达到全局的一致性。
- Basically Available (基本可用)
- Soft state (软状态)
- Eventually consistent (最终一致性)
一致性模型
- 强一致性(原子一致性、线性一致性)
- 在任意时刻,所有节点中的数据是一样的
- 任何一次读都能读到某个数据的最近一次写的数据
- 和全局时钟下的顺序一致
- 顺序一致性
- 任何一次读都能读到某个数据的最近一次写的数据
- 所有进程的顺序一致,不需要和全局时钟下的顺序一致
- 弱一致性
- 最终一致性,随着时间推荐,会最终达到全局一致性
Basic-Paxos
-
角色分类
- Proposer 提案者:可以有多个,用于发起一个议案(由client向Proposer发出),议案包括议案编号、议案内容
- Acceptor 接收者、批准者:用于接收Proposer提出的议案,并决定采纳哪一个议案
- Learner 学习者、记录者:在最终决定采纳某个议案后,进行记录,不做其他事
-
约束条件
- Acceptor必须接受它收到的第一个议案
- Acceptor只认可接收到的最新的议案(即议案编号最新)
- 当某个议案被一半以上Acceptor认可后,那么该议案成功
-
运作流程
basic-paxos运作流程.png
Multi-Paxos
-
说明
- Basic-Paxos每次都要重新选举一个可信任的Proposer,但实际上Proposer不会随时都挂掉
- 因此,应该先只选举一次可信任的Proposer,后续的议案都由它来发起
- 当该Proposer挂了(没有心跳包),再次进行选举即可
- 该Proposer叫做Leader,Leader只有一个
-
运作流程
multi-paxos运作流程.png
Raft
- 说明:
- Raft是Multi-Paxos的简化模型
- 区别:
- Raft中追加日志的操作必须是连续的(Multi-Paxos中是并发)
- 只有拥有最新、最全日志的节点才能够当选Leader(Multi-Paxos中任意节点都可以写日志,无限制)
- 运作流程:
- 同Multi-Paxos
- Leader对应Leader
- Acceptor对应Follower
- 参考的动态图:
ZAB
- 代表: ZooKeeper
- 基本与Raft相同
- 不同点
- Raft每一次leader的任期叫做term,ZAB中叫做epoch
- Raft有leader向follower发送心跳,ZAB相反
- 选主投票方式不同
- 事务操作方式不同
ZooKeeper-ZAB
- Leader选举:Leader挂了,其他节点将进行重新选举。各节点优先投自己一票(myId, zxid),再广播至其他节点。每个节点对比收到的票,zxid大的优先,zxid相等再按myId大的优先。选中某个投票后,会再向集群其他节点广播选中的票。当某个票被集群中超过一半的节点选中后,该票对应的Follower升为Leader(也就是说,一个节点A会查看收到的票,如果其中的某个节点的得票数超过集群节点数的一半,这个节点A就认为该票对应的Follower是Leader,其他节点依此类推)。
- 集群消息广播:当Client一次写请求发送至ZooKeeper集群时,无论连接的是什么节点,写操作都会转发至Leader,由Leader来控制写(保证一致性)。每一次写操作都会更新zxid。Leader会先向Follower发送一次请求(Propose),如果超过一半的节点回复Ack,那么Leader会认为没问题,执行commit(向所有节点发送),完成本次写操作。
网友评论