从分布式系统一致性看zk与etcd系统设计

“在分布式系统设计中，怀疑，悲观和偏执狂都是值得的；事实上，从不太可靠的基础构建更可靠的系统是计算机领域的⼀个古老思想。”

ZooKeeper 作为一个分布式应用协调系统，在配置管理、主节点选举、服务注册中心等方面一直都是Java生态圈的业界标杆，从其开源以来被广泛应用在国内外的顶级开源系统的架构中（Hadoop、Kafka、Dubbo），而 etcd 作为golang技术栈的后起之秀，在性能、可靠性、一致性等方面常拿来和zk做比较，在某些方面和应用场景上都是超过了zk的；

最近一直在看《数据密集型系统设计》这本书，一直想结合成熟的开源分布式系统与理论一起学习，加上之前公司技术栈用的都是zk，对etcd一直不太熟悉，希望能借这个机会掌握其高深的系统设计的一些皮毛；

本文主要分为两部分：

• 一、介绍两者的来源以及数据结构对比；
• 二、分布式一致性算法、以及在zk和etcd的应用浅析；

注：本文所讨论的etcd特性都是基于v3版本；

名字来源

ZooKeeper 是由雅虎公司设计并开源的，名称来源据说是由于当时有很多系统名称都是以动物名称命名，zk在最初设计愿景上是成为各个分布式系统的协调管理者，便有了动物园管理者这个名字；

而 etcd 的名字则是由两部分含义组成(参见 etcd Document)，unix系统的"/etc"目录和 "d"istribute systems（分布式系统），/etc目录在类unix系统中负责存储系统配置数据，由此可见 etcd 在设计者的期望中，是一个具有高稳定性、高一致性的分布式配置数据库；

ZooKeeper 数据模型

ZooKeeper 的逻辑数据结构是和unix文件系统类似的树状结构，与文件系统不同是，节点既可以是file也可以是directory，其最小数据单元被称为 ZNode，每个 ZNode 上可以保存数据，同时也可以挂载子节点，从而形成一棵树；ZNode 又分为持久节点和临时节点，持久节点除非主动执行删除操作，否则将会永久保存；而临时节点则与客户端会话绑定，会话结束时自动被删除；另外还允许给每个节点赋予sequence属性，用以实现节点的顺序性；

如 Dubbo 使用 ZooKeeper 作为注册中心时数据结构，在注册服务提供节点Provider时，会根据dynamic配置确定是否使用持久节点，dynamic为true（默认为true）则只创建临时节点，通过watch机制来实现服务动态失效；对于服务消费节点Consumer因为不需要动态变化，创建永久节点即可，具体结构见下图：

另外 ZooKeeper 在阿里并没有作为服务注册中心大规模使用，根因还是在于 ZooKeeper 作为CP系统为了保障数据一致性，牺牲了一定的可用性，并不适合作为一个大规模的服务注册中心（下文讨论分布式一致性问题时再做详细的分析）

附：阿里巴巴为什么不用 ZooKeeper 做服务发现

etcd 数据模型

etcd v2版本是内存存储实现，并未实时落盘，这里我们只讨论v3版本数据模型；etcd 设计用于可靠存储不频繁更新的数据，数据模型上使用多版本持久化kv数据存储；key可以使用任意字符，同时对key存储时按照词典顺序进行排序，便于对key进行范围查询(range queries)，因此也可以实现如zk ”/app“ 般的层级目录结构；

etcd 底层 b+tree 键值对的方式持久化物理数据（目前使用boltdb），其中kv中的key是一个三元组(major, sub, type)：

• major 代表 key 的主 revision，major 每次事务提交+1；
• sub 用于区分相同主 revision 下不同的 key，sub 在同一个事务中，每操作一次+1；
• type 用于表示key的特殊属性，如 type=t，代表当前节点已被打上 tombstone 标识，表示已被压缩删除；（ etcd 需要定期执行 Compact 策略以节省磁盘空间）

kv 中的值包含对前一个 revision 的改动，例如对前一个修订版本的增量修改；

在 boltdb 中存储的 key 是 revision，因此需要在内存中维护一个用户 key 与 reversion 之间的映射关系 KeyIndex，在 KeyIndex 中存储的对象包括用户原始 key、generations、modified 数据，其中 generations 包含了 key 的历史修改版本：

type keyIndex struct {
  key         []byte
  modified    revision // the main rev of the last modification
  generations []generation
}

// generation contains multiple revisions of a key.
type generation struct {
  ver     int64
  created revision // when the generation is created (put in first revision).
  revs    []revision
}
复制代码

generation 对象中包含着历史 revision 数组，每次新增 reversion 则在 revs 数组追加新版本，etcd 也是以此来实现 MVCC(多版本控制) ，同时内存索引也是 b+tree 的形式，用以加速查询；但是 KeyIndex 也存在一个问题，如果对一个 key 进行许多次变更，generation[0].revs 数组将会变得非常大，此时需要依赖 etcd 的 compact 机制进行压缩，主动抛弃部分历史版本；

以下是 etcd 代码注释 key_index.go 中描述的一个 key 的生命周期处理过程：

// For example: put(1.0);put(2.0);tombstone(3.0);put(4.0);tombstone(5.0) on key "foo"
// generate a keyIndex:
// key:     "foo"
// rev: 5
// generations:
//    {empty}
//    {4.0, 5.0(t)}
//    {1.0, 2.0, 3.0(t)}
//
// Compact a keyIndex removes the versions with smaller or equal to
// rev except the largest one. If the generation becomes empty
// during compaction, it will be removed. if all the generations get
// removed, the keyIndex should be removed.
//
// For example:
// compact(2) on the previous example
// generations:
//    {empty}
//    {4.0, 5.0(t)}
//    {2.0, 3.0(t)}
//
// compact(4)
// generations:
//    {empty}
//    {4.0, 5.0(t)}
//
// compact(5):
// generations:
//    {empty} -> key SHOULD be removed.
//
// compact(6):
// generations:
//    {empty} -> key SHOULD be removed.
复制代码

对于被执行 tombstone 操作即 delete，一旦发生删除就会结束当前的 generation，生成新的一个 empty 的 generation，并将最后一次操作 reversion 加上 type=t 的标识；

总结：内存 b+tree 中维护着用户 key 和 keyIndex 的映射，keyIndex 负责加速查询和维护 revision 的映射关系，通过 revision 即可从实际db存储中取出用户value。

一致性算法与共识

我们回到文章最开始的引用的《数据密集型应用系统设计》书中的一段话:

”在分布式系统设计中，怀疑，悲观和偏执狂都是值得的；事实上，从不太可靠的基础构建更可靠的系统是计算机领域的⼀个古老思想。“

分布式系统与单节点系统有着非常显著的区别，你会在系统设计实践中遇到各种千奇百怪的故障和问题，包括：

• 集群内部分失效（内核故障，磁盘故障，节点重启等）
• 不可靠的网路（数据丢包，网络分区，网络拥塞，网络超时等）；
• 不可靠的时钟（NTP同步又依赖于网络，本地时间跳跃等）；

在典型的分布式环境下，没有全局变量，没有共享内存，节点甚至不清楚现在的准确时间，更不用说其他更复杂情况。信息的流转只能通过不可靠的网络从一个节点传输到另外的节点，单个节点无法做出准确的决策，而是需要多个节点之间达到某种共识，通过共识使所有节点就某项提议达成一致，这就需要用到十几年来分布式领域研究人员探索总结出的一致性算法，其中较为著名的如 Paxos算法，Raft算法，Zab 等；

Paxos算法

首先简单介绍一下 Paxos算法，Paxos算法 中有三种角色：

• Proposer：负责发起提案（Proposal）；
• Acceptor：负责响应并接受提案（Proposal），提案被多数接受后则代表提案被批准（Chosen）；
• Learner：只负责同步被批准（Chosen）的提案，不直接参与提案的批准过程；

一个Proposal发起到Chosen，在Paxos算法中是一次两阶段的过程；

1. Prepare阶段由Proposer发起一次提案Proposal，Proposal包括全局唯一的proposalId以及提案内容value，由Acceptor批准收到的Proposal
2. Accept阶段被多数派批准的Proposal即形成决议，并被Learner同步；

其中对于 Acceptor、Proposer 的行为，在算法中又有多个约束来保障算法的准确性，Paxos算法以其复杂度著称，难以做到完美的工程化实践，因此在 Basic-Paxos 算法的基础上演化出了Multi-Paxos（Leader稳定不变时，移除部分Prepare和Promise阶段，降低开销）和 Fast-Paxos 等优化方案（详见Paxos算法）；后文中我们主要了解分析ZooKeeper的Zab协议（ZK原子广播协议），以及在etcd中有着工程化实践的raft算法；

Zab协议

Zab协议借鉴了Paxos算法里的一些思想，但并不是 paxos 的一种具体实现，其全称为 Zookeeper Atomic Broadcast（Zookeeper 原子广播协议），Zookeeper 使用Zab协议构建主备系统架构以保证分布式数据系统一致性；

简单描述Zab协议：在 Zookeeper 集群中使用单一进程负责处理事务操作，即 Leader 节点，并通过原子广播协议把事务转化为 Proposal，同步到所有 Follower 节点；

由此可见 Zookeeper 为了保证数据一致性以及顺序性，只使用leader节点处理写请求，其写请求的性能是不具备有水平拓展能力的。

Zab协议 有两种基本模式：

• 崩溃恢复
• 消息广播

一、消息广播模式

1. Leader 接受客户端事务请求，并转为 Proposal 广播；
2. 并在广播前为每个 Proposal 分配一个全局单调递增的唯一ID，也是zk的事务ID（ZXID），每个 Proposal 需保证按照 ZXID 的顺序进行排序处理；
3. Leader 会为每个 Follower 分配一个单独的队列，并将 Proposal 放入队列中，按照 FIFO 策略进行消息发送；
4. Follower 收到 Proposal 之后首先将事务日志写入磁盘，并发送 Ack 给 Leader，收到超过半数的 Ack 之后，Leader 会再广播commit消息给 Follower 节点，并完成本地的事务提交。

二、崩溃恢复模式

当 Zookeeper 集群启动或者由于网络原因导致 Leader 节点失去了与过半 Follower 的联系，则进入恢复模式重新选主；在崩溃恢复中 Zab协议需要保证这些特性：

• 确保已经在 Leader 节点已提交的事务（Committed），最终被所有服务器提交；
• 确保只是在 Leader 节点上被提出的事务，需要被丢弃；

Zab协议为了实现上面的需求，在事务ID（ZXID）设计中，ZXID 是64位的数字，其低32位为单调递增简单计数器，Leader 节点每增加一个事务则对其加1，其高32位数字则代表了 Leader 周期的 epoch 值，每选举出一个新的 Leader 即从其本地事务日志中取出最大的 ZXID，取高32位进行加1，使用其作为新的 epoch，并使低32位从0重新开始生成新的 ZXID。

Zab协议通过这一机制简化 Leader 崩溃恢复期间数据重新同步的流程，极端情况下大量集群节点数据的恢复和重新选举数据同步，可能会花费一些时间，在重新选举的过程中zk的服务是不可用的，这也是Zab协议中为保证数据强一致性做出的一定可用性牺牲；

综上对Zab协议的各个场景的了解可以看出，zk的系统设计目标是高一致性的分布式系统，满足CAP理论中的CP条件，存在写性能无法扩展、崩溃恢复缓慢等问题，具体的：

1. CP系统设计无法满足注册中心高可用的需求，更不可能允许注册中心出现服务不可用的情况；
2. 写性能无法水平扩展，服务规模壮大之后可能每次服务大量重启都是灾难；
3. zk依赖于Session的活性检测并不完全可靠，健康检测更应该由服务提供方主动反馈；
4. 容灾考虑，注册中心即使完全宕机也不能影响服务调用，需要通过客户端主动实现服务缓存机制，zk原生客户端并不支持；
5. zk作为分布式系统家族中的年长者，无法得到及时的支持，往往需要zk用户自己主导和维护；

对于前文中提到的zk作为注册中心的场景，这些问题都是后期规模壮大之后致命性问题，因此合理考虑项目中对于zk的使用场景也是至关重要，在读多写少的高一致性需求场景下（如大数据离线计算，元数据存储等等），zk仍是分布式架构中一把利器。

Raft算法

Raft算法对比于Paxos算法降低了协议的复杂度，更加便于工程师理解，并做出工程化实践；在Raft算法将共识算法问题分为了两个子问题：领导选举、日志同步；

一、领导选举（Leader Election）

Raft 集群中的成员分三种状态：

1. Leader，负责处理所有的事务操作，并同步至其他副本节点；
2. Follower，从Leader获取同步数据，写入本地日志，每个Follower与Leader维持心跳；
3. Condidate，Leader和Follower的中间态，指Leader崩溃失去心跳响应之后，Follower转化为Condidate，并发起新的一轮选主，直到新的Leader生成。

Raft 协议在集群中维护着一个唯一的term，即 Leader 任期，每发起新的的一轮选举都会对 term_id 进行递增，在初始化时集群中所有成员均是 Follower，在选举开始期间所有 Follower 均可参与选举，Follower 将本地最大 term_id + 1并发起发起选举投票，之后状态变更为 Condidate，等待其他 server 进行投票，只有收到超过半数的投票才能成为 Leader，其余 Condidate 则变回 Follower 开始日志同步（这里不考虑拜占庭将军问题，理论上集群环境内对各节点都是信任的）；

对于异常场景，没有任一 Condidate 收到超过半数的投票怎么处理？在Raft协议中有两个timeout来负责处理这些异常场景：

• election timeout
  Follower 等待成为 Condidate 的时间，这个timeout是150~300ms之间的随机时间，由此保证不会多个节点同时成为 Condidate 并发起投票；同时每个节点只会投第一次投票，当节点投出票之后则重置 election timeout，以保证没有收到 Leader 选举成功的消息时，可以重新发起选举；

• heartbeat timeout
  Leader 选举成功之后，Follower 和 Leader 之间维持的心跳超时时间，当 Follower 丢失心跳之后则重新开始等待成为 Condidate，并在等待之后发起选举投票；

二、日志同步（Log Replication）

在选举出 Leader 之后，则开始进行数据同步，即日志同步；和 Zab 一样，Raft 中也是主节点负责接收所有客户端的处理请求；具体的一次数据同步流程：

1. Leader 接收到事务请求之后，落入本地日志中，通常是 wal 日志，并标记为 uncommitted 状态，并发送数据同步请求给所有的 Follower，这里的数据同步请求与心跳请求一致，都是使用 Append Entries 消息进行同步；
2. Follower 收到 Append Entries Message 之后需要对 Leader 返回 ACK；
3. Leader 收到过半 ACK 之后则会 commit 事务，并返回客户端成功，同时使 Follower 进行提交；

在 Raft算法 中需要保证所有 committed 的日志应用到所有节点中，假如有 Follower 因为网络问题丢失了一次事务，或者收到了事务没有发出 ACK，这里和 Zab 思路也是基本一致，即在 Leader 节点为每个 Follower 维护一个记录当前 Follower 处理的日志index，每次发送 Append Entries 即携带着 term、index和data数据（在 etcd 的 wal 日志即是如此），如果 Follower 出现前文中提到的异常，则会一直重发 Append Entries 直到成功。

以上文字描述Raft协议处理过程可能比较枯燥，本文中只是描述了一些常见的场景，更多的如主从切换，网络分区，集群拓扑调整等场景，感兴趣的朋友可以看这个 Raft动画演示，会更加容易理解，同时也可看下知乎上这篇文章
Raft 协议详解，对Raft协议有非常详细的介绍。

场景对比

最后参考etcd官方文档给出的对比 etcd why，在使用场景、应用功能等方面对 etcd 和 Zookeeper 做出对比以及说明。

etcd 和 Zookeeper 两个系统解决的是同一个问题，即：分布式系统协调和元数据存储，但 etcd 作为后来者，可以站在 Zookeeper 这个前辈的肩膀上，更具有前瞻性，在系统设计中充分参考学习zk的设计和实现，在一致性协议实践和数据结构设计等多方面都有借鉴的地方，在学习的同时，etcd 也在zk基础上实现了一些超出zk的能力：

• 动态集群拓扑调整（动态扩容，缩容）
• 高负载下更稳定的读写能力
• MVCC多版本并发控制数据模型
• 可靠的事件监控，并且基于MVCC数据模型实现指定版本重放
• 租约机制将connection与session分离
• 更安全的API调用

同时 etcd 在多语言调用支持上也是更优于 Zookeeper，Zookeeper 由于实现机制原因，基本限制在 Java 生态中，etcd 则提供了非常便利的api供多语言调用，简单的curl命令即可调用其Http服务。

因此在系统架构设计时，出于需要更高的性能，更多的功能以及更及时的社区支持能力等方面的考虑，可以优先选用 etcd，同时 etcd 也可以支持一些老系统延用 Zookeeper 的api形式调用 etcd 集群能力，详细参考 zetcd。

另外对于RPC服务发现场景，有更专注于该细分领域的系统如 Consul、Eureka、Nacos 等，出于长远的架构规划、具体应用场景的考虑，这些开源软件系统都比 etcd 和 Zookeeper 更加适合于作为分布式远程调用架构中的服务发现组件，在更大规模的服务发现场景中都有着最佳实践。

原文地址

引用列表：

1. ZooKeeper 官网文档
2. 从 Paxos 到 Zookeeper
3. Dubbo zk注册中心文档
4. etcd 架构与实现解析
5. etcd 设计原理解析
6. etcd v3原理解析
7. Raft 协议详解