江苏龙网

  1. 主页 > 生活百科 > >

算法专家教你一致性算法：Paxos+Zab+Raft+NWR+Gossip+一致性Hash

一致性算法

一致性算法PaxosPaxos 算法解决的问题是一个分布式系统如何就某个值（决议）达成一致 。一个典型的场景是 ， 在一个分布式数据库系统中 ， 如果各节点的初始状态一致 ， 每个节点执行相同的操作序列 ， 那么他们最后能得到一个一致的状态 。为保证每个节点执行相同的命令序列 ， 需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致 。zookeeper 使用的 zab 算法是该算法的一个实现 。在 Paxos 算法中 ， 有三种角色：Proposer ， Acceptor ， Learners 。
Paxos 三种角色：Proposer ， Acceptor ， Learners
Proposer：
只要 Proposer 发的提案被半数以上 Acceptor 接受 ， Proposer 就认为该提案里的 value 被选定了 。
Acceptor：
只要 Acceptor 接受了某个提案 ， Acceptor 就认为该提案里的 value 被选定了 。
Learner：
Acceptor 告诉 Learner 哪个 value 被选定 ， Learner 就认为那个 value 被选定 。
Paxos 算法分为两个阶段 。具体如下：
阶段一（准 leader 确定 ）：
【算法专家教你一致性算法：Paxos+Zab+Raft+NWR+Gossip+一致性Hash】(a) Proposer 选择一个提案编号 N ， 然后向半数以上的 Acceptor 发送编号为 N 的 Prepare 请求 。
(b) 如果一个 Acceptor 收到一个编号为 N 的 Prepare 请求 ， 且 N 大于该 Acceptor 已经响应过的所有 Prepare 请求的编号 ， 那么它就会将它已经接受过的编号最大的提案（如果有的话）作为响应反馈给 Proposer ， 同时该 Acceptor 承诺不再接受任何编号小于 N 的提案 。
阶段二（leader 确认）：
(a) 如果 Proposer 收到半数以上 Acceptor 对其发出的编号为 N 的 Prepare 请求的响应 ， 那么它就会发送一个针对[N,V]提案的 Accept 请求给半数以上的 Acceptor 。注意：V 就是收到的响应中编号最大的提案的 value ， 如果响应中不包含任何提案 ， 那么 V 就由 Proposer 自己决定 。
(b) 如果 Acceptor 收到一个针对编号为 N 的提案的 Accept 请求 ， 只要该 Acceptor 没有对编号大于 N 的 Prepare 请求做出过响应 ， 它就接受该提案 。
ZabZAB( ZooKeeper Atomic Broadcast , ZooKeeper 原子消息广播协议）协议包括两种基本的模式：崩溃恢复和消息广播
1. 当整个服务框架在启动过程中 ， 或是当 Leader 服务器出现网络中断崩溃退出与重启等异常情况时 ， ZAB 就会进入恢复模式并选举产生新的 Leader 服务器 。
2. 当选举产生了新的 Leader 服务器 ， 同时集群中已经有过半的机器与该 Leader 服务器完成了状态同步之后 ， ZAB 协议就会退出崩溃恢复模式 ， 进入消息广播模式 。
3. 当有新的服务器加入到集群中去 ， 如果此时集群中已经存在一个 Leader 服务器在负责进行消息广播 ， 那么新加入的服务器会自动进入数据恢复模式 ， 找到 Leader 服务器 ， 并与其进行数据同步 ， 然后一起参与到消息广播流程中去 。
以上其实大致经历了三个步骤：
1.崩溃恢复：主要就是 Leader 选举过程
2.数据同步：Leader 服务器与其他服务器进行数据同步
3.消息广播：Leader 服务器将数据发送给其他服务器
说明：zookeeper 章节对该协议有详细描述 。
Raft与 Paxos 不同 Raft 强调的是易懂（Understandability） ， Raft 和 Paxos 一样只要保证 n/2+1 节点正常就能够提供服务；raft 把算法流程分为三个子问题：选举（Leader election）、日志复制（Log replication）、安全性（Safety）三个子问题 。
角色
Raft 把集群中的节点分为三种状态：Leader、 Follower 、Candidate ， 理所当然每种状态负责的任务也是不一样的 ， Raft 运行时提供服务的时候只存在 Leader 与 Follower 两种状态；
Leader（领导者-日志管理）
负责日志的同步管理 ， 处理来自客户端的请求 ， 与 Follower 保持这 heartBeat 的联系；
Follower（追随者-日志同步）
刚启动时所有节点为Follower状态 ， 响应Leader的日志同步请求 ， 响应Candidate的请求 ， 把请求到 Follower 的事务转发给 Leader；
Candidate（候选者-负责选票）
负责选举投票 ， Raft 刚启动时由一个节点从 Follower 转为 Candidate 发起选举 ， 选举出Leader 后从 Candidate 转为 Leader 状态；


推荐阅读


上一篇：淘宝客推广怎么操作 淘宝网如何推广宝贝

下一篇：漏洞扫描技巧篇 「Web 漏洞扫描器」