江苏龙网

  1. 主页 > 生活百科 > >

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

一致性算法


Term（任期）
在 Raft 中使用了一个可以理解为周期（第几届、任期）的概念 ， 用 Term 作为一个周期 ， 每个 Term 都是一个连续递增的编号 ， 每一轮选举都是一个 Term 周期 ， 在一个 Term 中只能产生一个 Leader；当某节点收到的请求中 Term 比当前 Term 小时则拒绝该请求 。
选举（Election）
选举定时器
Raft 的选举由定时器来触发 ， 每个节点的选举定时器时间都是不一样的 ， 开始时状态都为Follower 某个节点定时器触发选举后 Term 递增 ， 状态由 Follower 转为 Candidate ， 向其他节点发起 RequestVote RPC 请求 ， 这时候有三种可能的情况发生：
1：该 RequestVote 请求接收到 n/2+1（过半数）个节点的投票 ， 从 Candidate 转为 Leader ， 向其他节点发送 heartBeat 以保持 Leader 的正常运转 。
2：在此期间如果收到其他节点发送过来的 AppendEntries RPC 请求 ， 如该节点的 Term 大则当前节点转为 Follower ， 否则保持 Candidate 拒绝该请求 。
3：Election timeout 发生则 Term 递增 ， 重新发起选举
在一个 Term 期间每个节点只能投票一次 ， 所以当有多个 Candidate 存在时就会出现每个Candidate 发起的选举都存在接收到的投票数都不过半的问题 ， 这时每个 Candidate 都将 Term递增、重启定时器并重新发起选举 ， 由于每个节点中定时器的时间都是随机的 ， 所以就不会多次存在有多个 Candidate 同时发起投票的问题 。
在 Raft 中当接收到客户端的日志（事务请求）后先把该日志追加到本地的 Log 中 ， 然后通过heartbeat 把该 Entry 同步给其他 Follower ， Follower 接收到日志后记录日志然后向 Leader 发送ACK ， 当 Leader 收到大多数（n/2+1）Follower 的 ACK 信息后将该日志设置为已提交并追加到本地磁盘中 ， 通知客户端并在下个 heartbeat 中 Leader 将通知所有的 Follower 将该日志存储在自己的本地磁盘中 。
安全性（Safety）
安全性是用于保证每个节点都执行相同序列的安全机制如当某个 Follower 在当前 Leader commitLog 时变得不可用了 ， 稍后可能该 Follower 又会倍选举为 Leader ， 这时新 Leader 可能会用新的Log 覆盖先前已 committed 的 Log ， 这就是导致节点执行不同序列；Safety 就是用于保证选举出来的 Leader 一定包含先前 commited Log 的机制；
选举安全性（Election Safety）：每个 Term 只能选举出一个 Leader
Leader 完整性（Leader Completeness）：这里所说的完整性是指 Leader 日志的完整性 ， Raft 在选举阶段就使用 Term 的判断用于保证完整性：当请求投票的该 Candidate 的 Term 较大或 Term 相同 Index 更大则投票 ， 该节点将容易变成 leader 。
raft 协议和 zab 协议区别
相同点
? 采用 quorum 来确定整个系统的一致性,这个 quorum 一般实现是集群中半数以上的服务器,
? zookeeper 里还提供了带权重的 quorum 实现.
? 都由 leader 来发起写操作.
? 都采用心跳检测存活性
? leader election 都采用先到先得的投票方式
不同点
? zab 用的是 epoch 和 count 的组合来唯一表示一个值, 而 raft 用的是 term 和 index
? zab 的 follower 在投票给一个 leader 之前必须和 leader 的日志达成一致,而 raft 的 follower则简单地说是谁的 term 高就投票给谁
? raft 协议的心跳是从 leader 到 follower, 而 zab 协议则相反
? raft 协议数据只有单向地从 leader 到 follower(成为 leader 的条件之一就是拥有最新的 log),而 zab 协议在 discovery 阶段, 一个 prospective leader 需要将自己的 log 更新为 quorum 里面最新的 log,然后才好在 synchronization 阶段将 quorum 里的其他机器的 log 都同步到一致.
NWRN：在分布式存储系统中 ， 有多少份备份数据
W：代表一次成功的更新操作要求至少有 w 份数据写入成功
R： 代表一次成功的读数据操作要求至少有 R 份数据成功读取
NWR值的不同组合会产生不同的一致性效果 ， 当W+R>N 的时候 ， 整个系统对于客户端来讲能保证强一致性 。而如果 R+W<=N ， 则无法保证数据的强一致性 。以常见的 N=3、W=2、R=2 为例：
N=3 ， 表示 ， 任何一个对象都必须有三个副本（Replica） ， W=2 表示 ， 对数据的修改操作（Write）只需要在 3 个 Replica 中的 2 个上面完成就返回 ， R=2 表示 ， 从三个对象中要读取到 2个数据对象 ， 才能返回 。


推荐阅读


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

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