当前业界主流的分布式一致性协议主要有下面这几个。本文回答两个问题:它们各自解决的是
同一类问题的哪一部分,以及选型时该看哪个。它们不是同一层次的替代品——先看清各自
解决的是问题的哪一部分:
| 协议 | 解决的问题 | 代表实现 | 一句话定位 |
|---|---|---|---|
| Totem | 集群成员管理 + 有序广播(令牌环) | corosync | 消息按令牌顺序提交给上层,靠成员管理保证全体一致 |
| Paxos | 多数派共识(状态机一致) | Chubby、Spanner | 允许少数节点故障的共识算法 |
| Raft | 多数派共识(工程化共识) | etcd、TiKV、Consul | 把共识拆成 Leader 选举 / 日志复制 / 状态安全三个子问题 |
| ZAB | 原子广播 + 崩溃恢复(协调服务专用) | ZooKeeper | 为 ZooKeeper 设计的原子广播协议,带恢复协议 |
先厘清一个常见误解:这几个协议都不是「二阶段提交」。二阶段提交(2PC)是一种
带协调者的阻塞式提交协议——协调者发 prepare,参与者投票后再发 commit,参与者
在收到 commit 前一直阻塞。而 Paxos / Raft / ZAB 是多数派共识协议:没有阻塞式
协调者,靠「过半节点同意」来决议。下面讲 Raft 和 ZAB 时会具体说明它们的提交流程
与 2PC 的差别。
Totem 协议
totem 协议,全称 The Totem Single-Ring Ordering and Membership Protocol,是一个基于令牌环的分布式一致性算法。corosync 基于 totem 协议实现。
一个令牌在集群节点之间传递,拿到令牌的节点才能发消息,消息通过 UDP 广播发送。所以 totem 只适合在局域网里的小集群使用,这种情况下算法性能还算高。
从 CAP 来看,totem 具有强一致性,但几乎没有分区容错性:网络出现分区时令牌环会断,集群可能形成两个环(脑裂),网络恢复后会造成消息丢失。
在多个节点组成的集群中,totem 实现让一个节点发送消息,其它所有节点都能全部收到,并且有序地提交给上层应用。
说起 totem 协议,最简单的形象就是:它将多个节点组成一个令牌环。多个节点手拉手形成一个圈,大家依次地传递 token,只有获取到 token 的节点才有发送消息的权利。简单有效地解决了在分布式系统中各个节点的同步问题——因为只有一个节点会在一个时刻发送消息,不会出现冲突。
当然,如果有节点发生意外时,令牌环就会断掉,此时大家不能够通信,而是重新组建出一个新的令牌环。
totem 的节点有四个状态,也是组建集群的 4 个阶段:
- Gather 阶段:这个阶段用于每个节点向外界广播自己的存在并收集其它节点的存在
- Commit 阶段:这个阶段会产生一个代表节点,该节点向其它所有节点收集信息,并将收集的信息传递给其它所有节点,用于后续阶段
- Recovery 阶段:这个阶段用于新旧集群交替时,旧集群成员用新集群传递旧集群的消息,使旧集群成员达到所有节点消息全部有序提交到上层
- Operational 阶段:这个阶段是集群组建完成正常工作的状态,这个状态下,一个节点发送的消息其它节点都会全部有序提交给上层
通信方式:
- 当集群有节点要发起通信时,需要等待 token
- 当拿到 token 后,先广播这次需要发送的数据,然后传递 token 来确认所有人都接收到消息
- 如果确认成功,释放 token
节点的加入和退出:
- 当集群中有节点加入时,加入的节点广播一个加入信息,所有人都开始广播自己的信息;当所有人都获得同伴信息后,开始由 id 最小的人提交一个 token,交由所有节点确认
- 如果都确认后,则节点正式加入,开始正常运行
- 当集群有节点退出时,由于令牌环断链触发 token 超时,则同样开始广播信息,然后由最小 id 提交 token,经过确认后恢复正常
Raft 协议
Paxos 算法的描述偏学术化,缺失了很多细节,无法直接应用于工程领域。实际工程应用中的分布式算法大多是 Paxos 的变种,Raft 协议就是其中工程化程度最高的一个——它不用 Paxos,但结构同源:把一致性问题拆成三个独立的子问题。
RAFT 算法分为两个阶段:Leader 选举、日志复制。也有三种角色,分别为:
- Leader(领导者):负责发送要进行共识的数据。如果客户端发送的数据不是发送到 Leader 而是其他角色,其他角色会进行转发至 Leader
- Follower(追随者):参与共识的角色
- Candidate(候选者):如果 Follower 在选举超时内没有收到 Leader 的心跳,就会转为 Candidate 发起选举
选举超时的区间通常是 150~300ms,并且是随机的。随机的目的不是「让谁先发竞选谁当选」,而是**减少多个 Candidate 同时发起选举造成选票分散(split vote)**的概率——所有节点各用一个随机定时器,通常只有一个先超时。
正常运行的情况下,会有一个 Leader,其他全为 Follower。Follower 只会响应 Leader 和 Candidate 的请求,而客户端的请求则全部由 Leader 处理;即使有客户端请求了一个 Follower,也会将请求重定向到 Leader。Candidate 代表候选人,出现在选举 Leader 阶段,选举成功后 Candidate 将会成为新的 Leader。
Raft 将一致性问题分解为 3 个独立的子问题:
- Leader 选举 Election:Leader 进程失效后能够自动选举出一个新的 Leader
- 日志复制 Replication:Leader 保证其他节点的日志与其保持一致
- 状态安全 Safety:Leader 保证状态机执行指令的顺序与内容完全一致
Leader 选举
- 所有节点初始状态为 Follower 状态,此时没有 Leader,必然会与 Leader 的心跳超时,此时 Candidate 就会发出 leader 竞选给其他节点;其他节点收到竞选请求后,并不会无条件同意——只有同时满足两个条件才投票:一是该 Candidate 在本任期内还没给自己投过票(每个节点每任期最多投一票),二是该 Candidate 的日志至少和自己一样新(比较最后一条日志的 term 与 index)。这两条规则正是 Raft 能保证 Leader Completeness 的根本:当选的 Leader 一定拥有全部已提交的条目。当一个 Candidate 收到大多数(n/2 + 1)节点的回复,就成为 Leader,然后与 Follower 保持心跳连接
- Raft 有个 Term(任期)的概念,只有在发生 Leader 选举阶段,term + 1,表示新的 Leader 产生。挂掉的节点,或者挂掉的 Leader 重启后,会发现自己的 term 小于最新的,此时就会退回到 Follower 状态,等待新 Leader 把日志复制过来
- 如果同时有多个 Candidate 发出竞选,并且都没有获得大多数投票,会一直进行竞选,直到选出 Leader
注意「同步之前丢失的消息」这个说法是不对的:Raft 里 Follower 不会「丢失」已提交的条目。
如果某个 Follower 的日志与新 Leader 冲突(同样的 index 但 term 不同),新 Leader 会用
自己的日志覆盖它(truncate + append),而不是「找回」什么丢失的消息。
日志复制
- Leader 收到客户端或者其他节点转发过来需要共识的值,会跟随心跳一起广播给其他节点,进行写入
- 其他节点写入后响应成功给 Leader,当 Leader 收到大多数(n/2 + 1)Follower 响应的成功,发出 commit 命令
- 其他节点收到 commit 后,进行事务提交,响应成功为 Leader;Leader 收到大多数的 commit 成功,Raft 完成
ZAB 协议
ZooKeeper 是一个为分布式应用提供可靠协调服务的分布式协调框架。在解决分布式一致性方面,ZooKeeper 并没有使用 Paxos,而是采用了 ZAB 协议。
ZAB 协议基本与 Raft 相同,都是 Multi-Paxos 的衍生。ZAB 与 Raft 在一些名词的叫法上有区别:如 ZAB 将某一个 Leader 的周期称为 epoch,而 Raft 则称之为 term。
两者的差异主要在确认方向与流水线方式,而不是心跳方向——ZAB 的 Leader 同样是向 Follower 发心跳与 Proposal。
真正的差别是:Raft 里 Follower 直接把 ACK 回给 Leader;ZAB 里每个 Follower 把自己的 ACK 放进各自的 FIFO 队列,Leader 再按序从队列里取走,形成 FACK 流水线——这正是 ZAB 能做到「按序提交、不需要额外排序」的原因。
消息广播模式
ZAB 协议的消息广播过程使用的是原子广播协议,形式上类似两阶段(提案 → 提交),但不是 2PC:它没有阻塞式协调者,quorum 决议不要求所有节点参与,因此不会出现 2PC 那种「协调者挂了 participant 就卡住」的情况。
- Leader 将客户端的 request 转化成一个 Proposal(提议)
- Leader 为每一个 Follower 准备了一个 FIFO 队列,并把 Proposal 发送到队列上
- Leader 收到多数派(quorum,n/2 + 1)的 ACK 反馈后,确认该 Proposal 达到提交条件
- Leader 向所有的 Follower 发送 commit
崩溃恢复
ZAB 定义了 2 个原则:
- ZAB 协议确保那些已经在 Leader 提交的事务最终会被所有服务器提交
- ZAB 协议确保丢弃那些只在 Leader 提出/复制、但没有提交的事务
所以,ZAB 设计了下面这样一个选举算法:能够确保提交已经被 Leader 提交的事务,同时丢弃已经被跳过的事务。
针对这个要求,如果让 Leader 选举算法能够保证新选举出来的 Leader 服务器拥有集群中所有机器编号(即 ZXID 最大)的事务,那么就能够保证这个新 Leader 一定具有所有已经提交的提案。
选型速查
| 需求 | 选谁 | 代价 |
|---|---|---|
| 强一致状态机(配置、锁、选主) | Raft / ZAB | 少数节点不可用时无法写入 |
| 集群成员管理 + 有序广播(小型局域网) | Totem | 分区即脑裂,恢复后丢消息 |
| 跨机房多活 | 先看多地多中心方案调研,再谈协议 | 多数派跨机房延迟会直接变成写延迟 |
参考资料
- Diego Ongaro, John Ousterhout — In Search of an Understandable Consensus Algorithm (Raft):https://raft.github.io/raft.pdf
- Benjamin Reed, Flavio Junqueira — A Simple Quorum-Based Protocol for Asynchronous Fault-Tolerant Consensus(ZAB):https://ieeexplore.ieee.org/document/4786406
- Sean M. Barratt, et al. — A Token Ring Approach to Network Protocol Management(Totem / corosync)
- corosync 项目文档:https://corosync.github.io/corosync/