Please enable JavaScript.
Coggle requires JavaScript to display documents.
分布式算法 - Coggle Diagram
分布式算法
Paxos
MultiPaxos
- 每个节点有三种状态Fllower/candiate/leader
- Proposer定时轮询如发现没有主节点在心跳超时(心跳超时时间设置为随机150ms~300ms,保证没有活锁)结束后变成候选人向其他节点发起Basic Paxos 中定义的promise 和 Accept两个交互过程
- 希望其他接点选自己为主节点并达成一致
- 如果其他节点有票则会投给发送请求给他的候选人 并重置超时时间
- 一旦选举了主则主会发送定时心跳让其他follow它
- 如果超时会触发一次新任期选举
- 如果出现两个候选人同票,则重新设置超时再选举
- 选取了主节点后将不再选取主节点,保证只有一个Proposer
主节点提交proposer
- 类似两阶段提交,leader先预写值到log,再通过heartbeat 将值传给follower要求写入
- 如果半数以上follower写入,则提交
- 其中accept增加了主节点的任期,是一个全局递增Id
- 出现网络分区时必须以大的任期的主节点为准,小任期的主节点会回滚未提交的操作与新的leader同步,因为就算分区了总会有一方获取不到半数以上的投票,是所以选举或者提交都会收到限制
-
Gossip 协议
- 信息源选择一个周期如1s随机选择与他相连的K个节点来传播消息
- 接收到消息的节点再执行同上一样的步骤,要除去广播信息给他的节点
-
优缺点:
- 节点可以随意重启宕机最终会一致
- 随机传播导致无法预测节点准确接收时间
- 消息冗余
- 反熵 会同步节点的全部数据,以消除各节点之间的差异,目标是整个网络各节点完全的一致,网络中消息的数量非常庞大
- 传谣 以传播消息为目标,仅仅发送新到达节点的数据,即只对外发送变更信息,这样消息数据量将显著缩减,网络开销也相对较小。
Proposer
- 预先获取超过一半以上的Acceptor 访问权
- 如果更改了一半以上的Acceptor则算更改成功
- 如果大epoch的Proposer发现Acceptor已经接收了值则维护值
Acceptor
- 抢占式获取锁
- 只接受大epoch的Proposer
- 若值被设定则不会被更改
两个阶段:
- Promise 阶段 只接受比当前epoch大的Proposer
- Accept 如果值被设置则返回值,并广播,如果没有则设置 并广播
-