关于zookeeper:谈谈分布式一致性算法-paxos-zab-raft-gossip

概述

这篇 blog 次要探讨常见的分布式一致性算法：

• paxos
• zab (zookeeper atomic broadcast)
• raft
• gossip

重点在于比照这些算法的相同点和差别。思考算法的设计和取舍.

paxos

paxos 是最早提出的分布式一致性算法.
见 http://lamport.azurewebsites….

重要概念

Roles

实际中, 节点往往同时承载 proposer/acceptors/learner 的性能.

proposer

提案人，A proposer sends a proposed value to a set of acceptors. 能够了解为能够执行写入的 master 节点。留神 paxos 协定并没有限度 Proposer 的数量. 在实践中为了防止核心节点生成全序 proposal number 的单点故障, 应用了选主协定. 参考上面的 leader.

leader

见论文的第三节：Implementing a State Machine
必须有一个核心节点生成全序的 proposal number. 被选为主节点的 proposer 才可发动 proposal.
In normal operation, a single server is elected to be the leader, which acts as the distinguished proposer (the only one that tries to issue proposals) in all instances of the consensus algorithm.

acceptors

投票人，An acceptor may accept the proposed value. 即形成 majority 或 quorum 的节点。

learner

被动承受选举后果的角色。能够了解为只读的从库。

client

客户端. 发动申请和接管返回.

work flow

Basic Paxos without failures

下图来自: https://en.wikipedia.org/wiki…

Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(1)
   |         |<---------X--X--X       |  |  Promise(1,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Accept!(1,V)
   |         |<---------X--X--X------>|->|  Accepted(1,V)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

算法外围

1. acceptor 不会承受 proposal number 更小的 prepare, 会返回 accept 过的 highest-numbered.
2. 被提交的 value 只有在阶段 2 才会被抉择.

因为所有最高的 proposal number, 都是通过了 majority 的 accept 的, 所以相对不会产生如下状况:
更低版本议题笼罩更高版本议题的状况, 如,
(proposal number 1, V1) 笼罩 (proposal number 2, V2).

为什么 paxos 要有 prepare 阶段

paxos 容许同时存在多个 proposer, prepare 阶段能够确保不笼罩 higher proposal number.

paxos 算法是线性的吗?

paxos 算法没有明确要求 proposal number 的生成是严格有序的. 也没有规定 learner 严格有序地按 proposal number 读取.
在严格有序的状况下, paxos 才是线性的.

zab

zab 是 zookeeper 实现的分布式一致性算法.
见: http://www.cs.cornell.edu/cou…

why not paxos

线性一致性

It is important in our setting that we enable multiple outstanding ZooKeeper operations and that a prefix of operations submitted concurrently by a ZooKeeper client are committed according to FIFO order.
paxos 没有间接反对线性一致性. 如果多个 primaries 同时执行多个事务, 事务提交的程序是无奈保障的, 这个将导致最终的后果不统一.
下图阐明了这种不统一, 27A -> 28B 变成了 27C -> 28B. 如果心愿防止这种不统一, 只能限度一次只能执行一个 proposal. 显然这样会导致系统吞吐低下. 若应用合并 transactions 的形式优化的话, 又会导致系统提早进步. 合并 transactions 的 size 也很难抉择.

疾速复原

在多个 primaries 同时执行多个事务的状况下, paxos 不同的 processes 在同一个 sequence number 下可能有不同的值. 新的 master 必须对所有未 learned 的 value 走一遍 paxos phases 1, 即通过 majories 取得正确的值.

重要概念

Roles

leader

zab 是通过单主节点, 即 leader 播送来实现线性, 即全序 (论文中的 PO, primary order) 的播送.

follower

选主, abdeliver 主节点的播送.

epoch

新纪元, 每次选主胜利, 都会有有 epoch_new > epoch_current.

proposes 和 commit

proposes 和 commit 对应 paxos 的 Promise/Accept.
proposes 和 commit 都蕴含 (e, (v, z)):
e: epoch 对应 master 的任期 number
v: commit transaction value, 对应理论的值
z: commit transaction identifier (zxid), 对应提交版本号.
正是 commit 的全序线性化保障, 保障了各个节点的 value 变动具备线性一致性.

work flow

选主(discovery 和 synchronization)

如何确认 prospective leader？

尚未在了论文中找到 prospective leader 的准确形容，有含糊形容在 V. Z AB IN DETAIL 如下：

When a process starts, it enters the ELECTION state. While in this state the process tries to elect a new leader or become a leader. If the process finds an elected leader, it moves to the FOLLOWING state and begins to follow the leader.

为什么选主须要 discovery 和 synchronization 分两个阶段?

• discovery 阶段通过少数 follower 的 cepoch 确保 leader 有最新的 commit 和 history(f.p 和 h.f)．
• synchronization 阶段确保 leader 将最新的 commit/history 同步到了少数节点．

broadcast

少数成员 ack 后，即可平安 commit 和返回 client. 参照 discovery 阶段，因为会抉择所有节点中最新的 history，故，只须要少数节点 ack，即可返回写入胜利.
返回失败不肯定意味着写入不胜利，可能是

• 胜利，但返回未被收到。
• 失败，leader 播送之前解体。
• 失败，leader 在少数成员 ack 前解体，之后的选主未选中 ack 的 follower 的 history。

写入失败不肯定失败，写入胜利能够确保胜利。

raft

raft 是目前最易于实现，最易懂的分布式一致性算法，和 zab 一样，raft 必须先选出主节点。

why not paxos

• 难懂
• 不容易构建具备实际意义的实现.

paxos 指 single-decree paxos, 在工程中价值不大, 而 multi-paxos 的诸多细节并未给出.

和 zab 的异同

异

• 选主逻辑不同, raft 通过随机的选主超时触发选主. 只有一个阶段
• broadcast 逻辑不同, 见上面的 log.

从论文登程, raft 思考到了更多工程上的细节, 如日志压缩, 和扭转集群节点都是 zab/paxos 未提及的.

同

• single master and multi followers
• 任期概念 raft (term) zab (epoch)

外围形象

Roles

leader

同 zab, raft 有一个 strong leader. 必须先选出主节点, 才可提供写入服务.

follower

同 zab, follower 可投票, 写入主节点播送的 log(by AppendEntries rpc)

term

同 zab, 每选出一个 leader, 都对应一个全序的 term.

log

日志, 即 zab 的 propose 和 commit.
AppendEntries 设计得极为精美. 同时能够作为

• heartbeat
• propose
• commit (leaderCommit 字段能够 commit 所有小于等于 leaderCommit 的 log)

work flow

Leader election

https://raft.github.io/
有具体的选主过程. 能够随便操作节点, 察看各个状况下的边界. 参照 paxos 的文本化流程, 上面是一个失常状况下的选主:

Node1                 Node2                 Node3
   |                    |                     |
timeout                 |                     |
   X----RequestVote---->|                     |
   X--------------------|-----RequestVote---->|
   |<-------vote--------X                     |
   |<-------vote--------|-------------- ------X
become leader           |                     |

Log replication

Figure 6: Logs are composed of entries, which are numbered
sequentially. Each entry contains the term in which it was
created (the number in each box) and a command for the state
machine. Anentryisconsidered committed if itissafeforthat
entry to be applied to state machines.

认真思考 AppendEntries RPC 的 Receiver implementation:

• 不承受小于以后 term 的 log. 播送 AppendEntries 的节点只可能有两种, 一, 误以为本人仍是 leader 的老 leader. 二, 以后 leader, 一个分区中的 Node 可能不停进步 term, 但它取得少数节点投票成为 leader 之前, 不会收回播送. 这一点保障了, 只承受以后任期 term 的 log.
• 不承受 prevLogIndex 和 prevLogTerm 不匹配的 log. 若 prevLogIndex 和 prevLogTerm 不匹配. 阐明 prevLogIndex 之上有多个 leader 播送, leader 的 log 和 follower 的 log 不统一. leader 通过缩小 nextIndex 重试来修复和 follower 的不统一. 直到所有未 commit 的 log 都达成统一.
• 如果以后 entry 的值不统一, 应用 leader 的. leader 的 log 是可信的.
• 如果有新的 entries, 增加.
• 如果 leaderCommit > commitIndex, 设置 commitIndex = min(leaderCommit, index of last new entry)

当少数节点都返回对应 success 时, AppendEntries 的 entries 即可认为是写入, 能够返回给 client. 这是通过在选主时施加的额定限度来保障的, 具备更新(比拟 log index 和 term). log 的节点才可博得选举. 那么, 只有一个 log 在少数节点写入了(就算没有 commit), 选主时, 肯定会抉择一个具备该 entry 的节点:

• 不切换 leader 的状况下, 不会写入更新的 log
• 切换 leader 须要少数节点的批准, 肯定会抉择一个具备该 log 的节点. 因为该 log 是最新的.

Cluster membership changes

Figure11: Timeline for a configuration change. Dashed lines
show configuration entries that have been created but not
committed,and solidlinesshow thelatestcommittedconfigu-
ration entry. The leader first creates theC old,new configuration
entry in its log and commits it to C old,new (a majority of C old
and a majority of C new ). Then it creates the C new entry and
commits it to a majority of C new . There is no point in time in
whichC old and C new can both make decisions independently.

关键在于可能做决定的 majority 的切换.

gossip

gossip 一致性算法和 paxos/zab/raft 有较大差别, 不存在主节点, 没有线性化保障. 通过有限重试的播送, 确保变动在一段时间后, 可能同步到所有节点.

work flow

实现算法的要害在与, 如何将所有节点的 gossip 播送合并成一个状态, 即, 节点 a 能够申明节点 a 上有 k1=v1, 节点 b 申明节点 b 上有 k1=v2. 那么合并的状态是 a 上有 k1=v1, b 上有 k1=v2. 只有合并的算法是统一的, 如, 能够抉择并存, 优先 a 或优先 b, 那么收到对应播送的节点, 状态可保持一致.
因为没有线性化保障, 播送的内容不能用差量, 而应该用全量.

Active thread (peer P):                 Passive thread (peer Q):
(1) selectPeer(&Q);                     (1)
(2) selectToSend(&bufs);                (2)
(3) sendTo(Q, bufs);            ----->  (3) receiveFromAny(&P, &bufr);
(4)                                     (4) selectToSend(&bufs);
(5) receiveFrom(Q, &bufr);      <-----  (5) sendTo(P, bufs);
(6) selectToKeep(cache, bufr);          (6) selectToKeep(cache, bufr);
(7) processData(cache);                 (7) processData(cache)
Figure 1: The general organization of a gossiping protocol.

分布式共识的要害

不论是 paxos, zab, raft，实现一致性的外围原理都相似：

• 少数节点批准后才可提交．
• 批准后不可撤回．
• 这个过程是幂等的．

不论是节点解体后持续提交，还是由其它节点持续提交，会在少数节点达成共识.

参考

https://en.wikipedia.org/wiki…
http://lamport.azurewebsites….
https://stackoverflow.com/que…
http://www.cs.cornell.edu/cou…
https://raft.github.io/
https://web.stanford.edu/~ous…