一、应用

ZooKeeper 可以用于发布/订阅、负载均衡、命令服务、分布式协调/通知、集群管理、Master 选举、分布式锁和分布式队列等功能 。

1.1 命名服务

在分布式系统中，通常需要一个全局唯一的名字，如生成全局唯一的订单号等，ZooKeeper 可以通过顺序节点的特性来生成全局唯一 ID，从而可以对分布式系统提供命名服务。

Image

1.2 配置管理

利用 ZooKeeper 的观察机制，可以将其作为一个高可用的配置存储器，允许分布式应用的参与者检索和更新配置文件。

1.3 分布式锁

可以通过 ZooKeeper 的临时节点和 Watcher 机制来实现分布式锁。

有一个分布式系统，有三个节点 A、B、C，试图通过 ZooKeeper 获取分布式锁。

  1. 访问 /lock （这个目录路径由程序自己决定），创建 带序列号的临时节点（EPHEMERAL） 。
Image
  1. 每个节点尝试获取锁时，拿到 /locks节点下的所有子节点（id_0000,id_0001,id_0002），判断自己创建的节点是不是最小的。

  • 如果是，则拿到锁。

    释放锁：执行完操作后，把创建的节点给删掉。

  • 如果不是，则监听比自己要小 1 的节点变化。

Image
  1. 释放锁，即删除自己创建的节点。
Image

图中，NodeA 删除自己创建的节点 id_0000，NodeB 监听到变化，发现自己的节点已经是最小节点，即可获取到锁。

1.4 集群管理

ZooKeeper 还能解决大多数分布式系统中的问题：

  • 如可以通过创建临时节点来建立心跳检测机制。如果分布式系统的某个服务节点宕机了，则其持有的会话会超时，此时该临时节点会被删除，相应的监听事件就会被触发。

  • 分布式系统的每个服务节点还可以将自己的节点状态写入临时节点，从而完成状态报告或节点工作进度汇报。

  • 通过数据的订阅和发布功能，ZooKeeper 还能对分布式系统进行模块的解耦和任务的调度。

  • 通过监听机制，还能对分布式系统的服务节点进行动态上下线，从而实现服务的动态扩容。

1.5 选举 Leader 节点

分布式系统一个重要的模式就是主从模式 (Master/Salves)，ZooKeeper 可以用于该模式下的 Matser 选举。可以让所有服务节点去竞争性地创建同一个 ZNode，由于 ZooKeeper 不能有路径相同的 ZNode，必然只有一个服务节点能够创建成功，这样该服务节点就可以成为 Master 节点。

1.6 队列管理

ZooKeeper 可以处理两种类型的队列：

  • 当一个队列的成员都聚齐时，这个队列才可用，否则一直等待所有成员到达，这种是同步队列。
  • 队列按照 FIFO 方式进行入队和出队操作，例如实现生产者和消费者模型。

同步队列用 ZooKeeper 实现的实现思路如下：

创建一个父目录 /synchronizing，每个成员都监控标志（Set Watch）位目录 /synchronizing/start 是否存在，然后每个成员都加入这个队列，加入队列的方式就是创建 /synchronizing/member_i 的临时目录节点，然后每个成员获取 / synchronizing 目录的所有目录节点，也就是 member_i。判断 i 的值是否已经是成员的个数，如果小于成员个数等待 /synchronizing/start 的出现，如果已经相等就创建 /synchronizing/start。

二、 分布式锁对比

实现方式一般有：

  • 基于数据库实现：
    • 建一张表（t_dlock），关键字段有：id、method_name、time。
    • 向表中插入记录成功，即为获取锁成功。需要注意的是，获取锁一般是通过自旋方式，并设置尝试次数，超过最大尝试次数，才判定获取锁失败。
    • 删除记录，即为释放锁。
    • 因为数据库没有淘汰机制，为了避免获取锁永不释放，应用需要自身实现定期检查，删除过期记录（根据 time 判断）。
  • 基于 Redis 实现
    • 生成一个分布式 ID 作为 key，通过 setnx 写入
    • 写入成功，即为获取锁成功。需要注意的是，获取锁一般是通过自旋方式，并设置尝试次数，超过最大尝试次数，才判定获取锁失败。
    • 删除 key，即为获取锁失败。
    • Redis 自身有内存淘汰策略，所以只要设置 expire，就可以让 key 自动过期。
  • 基于 ZooKeeper 实现
    • 创建一个节点，所有节点都 Watch 此节点。
    • 任意节点的任意线程只要向这个节点创建临时子节点成功，即为获取锁成功。
    • 由于创建临时子节点是原子性的，不存在竞态，不需要自旋尝试，性能很好。
    • 因为 ZooKeeper 只要和节点断开会话，就会自动删除临时节点。即为删除锁。所以无需过期机制。

从实现方式可以看出，三种方案的对比：

  • Mysql 方案性能最差，并且影响 Mysql 吞吐量。而且还要程序保证容错处理。不建议采用这种方案。
  • Redis 方案需要不断自旋尝试获取锁，应用会消耗一些性能开销。而且为了保证分布式锁的可重入性，需要设置对于所有节点、所有线程都唯一的分布式 ID，生成 ID 也需要一定的 CPU 开销。
  • ZooKeeper 方案实现最简单，最稳定。是推荐的方案。但是它也有一个问题：ZooKeeper 的主从架构，所有写都由 Master 节点负责，所以 ZooKeeper 自身有一定的性能瓶颈。

三、一致性算法 Paxos

Paxos 是一种基于消息传递且具有容错性的共识性（consensus）算法。

Paxos 算法解决的问题正是分布式一致性问题。在一个节点数为 2N+1 的分布式集群中，只要半数以上的节点（N + 1）还正常工作，整个系统仍可以正常工作。

img

3.1 背景

Paxos 是 Leslie Lamport 于 1990 年提出的一种基于消息传递且具有高度容错特性的共识（consensus）算法。

Paxos 算法包含 2 个部分：

  • Basic Paxos 算法：描述的多节点之间如何就某个值达成共识。
  • Multi Paxos 思想：描述的是执行多个 Basic Paxos 实例，就一系列值达成共识。

Paxos 算法解决的问题正是分布式共识性问题，即一个分布式系统中的各个进程如何就某个值（决议）达成一致。

Paxos 算法运行在允许宕机故障的异步系统中，不要求可靠的消息传递，可容忍消息丢失、延迟、乱序以及重复。它利用大多数 (Majority) 机制保证了 2N+1 的容错能力，即 2N+1 个节点的系统最多允许 N 个节点同时出现故障。

3.2 Basic Paxos 算法

1. 角色

Paxos 将分布式系统中的节点分 Proposer、Acceptor、Learner 三种角色。

img
  • 提议者（Proposer）：发出提案（Proposal），用于投票表决。Proposal 信息包括提案编号 (Proposal ID) 和提议的值 (Value)。在绝大多数场景中，集群中收到客户端请求的节点，才是提议者。这样做的好处是，对业务代码没有入侵性，也就是说，我们不需要在业务代码中实现算法逻辑。
  • 接受者（Acceptor）：对每个 Proposal 进行投票，若 Proposal 获得多数 Acceptor 的接受，则称该 Proposal 被批准。一般来说，集群中的所有节点都在扮演接受者的角色，参与共识协商，并接受和存储数据。
  • 学习者（Learner）：不参与接受，从 Proposers/Acceptors 学习、记录最新达成共识的提案（Value）。一般来说，学习者是数据备份节点，比如主从架构中的从节点，被动地接受数据，容灾备份。

在多副本状态机中，每个副本都同时具有 Proposer、Acceptor、Learner 三种角色。

这三种角色，在本质上代表的是三种功能：

  • 提议者代表的是接入和协调功能，收到客户端请求后，发起二阶段提交，进行共识协商；（类似 zk 的 leader）
  • 接受者代表投票协商和存储数据，对提议的值进行投票，并接受达成共识的值，存储保存；（类似 zk 的 follower）
  • 学习者代表存储数据，不参与共识协商，只接受达成共识的值，存储保存。 （类似 zk 的 observer）

2. 算法

Paxos 算法有 3 个阶段，其中，前 2 个阶段负责协商并达成共识：

  1. 准备（Prepare）阶段：Proposer 向 Acceptors 发出 Prepare 请求，Acceptors 针对收到的 Prepare 请求进行 Promise 承诺。
  2. 接受（Accept）阶段：Proposer 收到多数 Acceptors 承诺的 Promise 后，向 Acceptors 发出 Propose 请求，Acceptors 针对收到的 Propose 请求进行 Accept 处理。
  3. 学习（Learn）阶段：Proposer 在收到多数 Acceptors 的 Accept 之后，标志着本次 Accept 成功，决议形成，将形成的决议发送给所有 Learners。

这里采用的正式两阶段提交的思想。两阶段提交是达成共识的常用方式。

Paxos 算法流程中的每条消息描述如下：

  • Prepare: Proposer 生成全局唯一且递增的 Proposal ID (可使用时间戳加 Server ID)，向所有 Acceptors 发送 Prepare 请求，这里无需携带提案内容，只携带 Proposal ID 即可。
  • Promise: Acceptors 收到 Prepare 请求后，做出“两个承诺，一个应答”。
    • 两个承诺：
      • 不再接受 Proposal ID 小于等于当前请求的 Prepare 请求。
      • 不再接受 Proposal ID 小于当前请求的 Propose 请求。
    • 一个应答：
      • 不违背以前作出的承诺下，回复已经 Accept 过的提案中 Proposal ID 最大的那个提案的 Value 和 Proposal ID，没有则返回空值。
  • Propose: Proposer 收到多数 Acceptors 的 Promise 应答后，从应答中选择 Proposal ID 最大的提案的 Value，作为本次要发起的提案。如果所有应答的提案 Value 均为空值，则可以自己随意决定提案 Value。然后携带当前 Proposal ID，向所有 Acceptors 发送 Propose 请求。
  • Accept: Acceptor 收到 Propose 请求后，在不违背自己之前作出的承诺下，接受并持久化当前 Proposal ID 和提案 Value。
  • Learn: Proposer 收到多数 Acceptors 的 Accept 后，决议形成，将形成的决议发送给所有 Learners。

3.Prepare 阶段

下图的示例中，首先客户端 1、2 作为提议者，分别向所有接受者发送包含提案编号的准备请求：

img

接着，当节点 A、B 收到提案编号为 1 的准备请求，节点 C 收到提案编号为 5 的准备请求后，将进行这样的处理：

img

  • 由于之前没有通过任何提案，所以节点 A、B 将返回一个 “尚无提案” 的响应。也就是说节点 A 和 B 在告诉提议者，我之前没有通过任何提案呢，并承诺以后不再响应提案编号小于等于 1 的准备请求，不会通过编号小于 1 的提案。

  • 节点 C 也是如此，它将返回一个 “尚无提案”的响应，并承诺以后不再响应提案编号小于等于 5 的准备请求，不会通过编号小于 5 的提案。（所以客户端 1 发出的 1 号请求不会被响应）

另外，当节点 A、B 收到提案编号为 5 的准备请求，和节点 C 收到提案编号为 1 的准备请求的时候，将进行这样的处理过程：

img
  • 当节点 A、B 收到提案编号为 5 的准备请求的时候，因为提案编号 5 大于它们之前响应的准备请求的提案编号 1，而且两个节点都没有通过任何提案，所以它将返回一个 “尚无提案”的响应，并承诺以后不再响应提案编号小于等于 5 的准备请求，不会通过编号小于 5 的提案。
  • 当节点 C 收到提案编号为 1 的准备请求的时候，由于提案编号 1 小于它之前响应的准备请求的提案编号 5，所以丢弃该准备请求，不做响应。

4.Accept 阶段

首先客户端 1、2 在收到大多数节点的准备响应之后，会分别发送接受请求：

img
  • 当客户端 1 收到大多数的接受者（节点 A、B）的准备响应后，根据响应中提案编号最大的提案的值，设置接受请求中的值。因为该值在来自节点 A、B 的准备响应中都为空（也就是图 5 中的“尚无提案”），所以就把自己的提议值 3 作为提案的值，发送接受请求[1, 3]。
  • 当客户端 2 收到大多数的接受者的准备响应后（节点 A、B 和节点 C），根据响应中提案编号最大的提案的值，来设置接受请求中的值。因为该值在来自节点 A、B、C 的准备响应中都为空（也就是图 5 和图 6 中的“尚无提案”），所以就把自己的提议值 7 作为提案的值，发送接受请求[5, 7]。

当三个节点收到 2 个客户端的接受请求时，会进行这样的处理：

img

  • 当节点 A、B、C 收到接受请求[1, 3]的时候，由于提案的提案编号 1 小于三个节点承诺能通过的提案的最小提案编号 5，所以提案[1, 3]将被拒绝。

  • 当节点 A、B、C 收到接受请求[5, 7]的时候，由于提案的提案编号 5 不小于三个节点承诺能通过的提案的最小提案编号 5，所以就通过提案[5, 7]，也就是接受了值 7，三个节点就 X 值为 7 达成了共识。

Basic Paxos 是通过二阶段提交的方式来达成共识的。

除了共识，Basic Paxos 还实现了容错，在少于一半的节点出现故障时，集群也能工作。它不像分布式事务算法那样，必须要所有节点都同意后才提交操作，因为“所有节点都同意”这个原则，在出现节点故障的时候会导致整个集群不可用。也就是说，“大多数节点都同意”的原则，赋予了 Basic Paxos 容错的能力，让它能够容忍少于一半的节点的故障。

3.3 Multi Paxos 思想

兰伯特提到的 Multi-Paxos 是一种思想，不是算法。而 Multi-Paxos 算法是一个统称，它是指基于 Multi-Paxos 思想，通过多个 Basic Paxos 实例实现一系列值的共识的算法（比如 Chubby 的 Multi-Paxos 实现、Raft 算法等）。

Basic Paxos 的问题

Basic Paxos 有以下问题，导致它不能应用于实际：

  • Basic Paxos 算法只能对一个值形成决议。
  • Basic Paxos 算法会消耗大量网络带宽。Basic Paxos 中，决议的形成至少需要两次网络通信，在高并发情况下可能需要更多的网络通信，极端情况下甚至可能形成活锁。如果想连续确定多个值，Basic Paxos 搞不定了。

Multi Paxos 的改进

Multi Paxos 正是为解决以上问题而提出。Multi Paxos 基于 Basic Paxos 做了两点改进：

  • 针对每一个要确定的值，运行一次 Paxos 算法实例（Instance），形成决议。每一个 Paxos 实例使用唯一的 Instance ID 标识。
  • 在所有 Proposer 中选举一个 Leader，由 Leader 唯一地提交 Proposal 给 Acceptor 进行表决。这样没有 Proposer 竞争，解决了活锁问题。在系统中仅有一个 Leader 进行 Value 提交的情况下，Prepare 阶段就可以跳过，从而将两阶段变为一阶段，提高效率。

Multi Paxos 首先需要选举 Leader，Leader 的确定也是一次决议的形成，所以可执行一次 Basic Paxos 实例来选举出一个 Leader。选出 Leader 之后只能由 Leader 提交 Proposal，在 Leader 宕机之后服务临时不可用，需要重新选举 Leader 继续服务。在系统中仅有一个 Leader 进行 Proposal 提交的情况下，Prepare 阶段可以跳过。

Multi Paxos 通过改变 Prepare 阶段的作用范围至后面 Leader 提交的所有实例，从而使得 Leader 的连续提交只需要执行一次 Prepare 阶段，后续只需要执行 Accept 阶段，将两阶段变为一阶段，提高了效率。为了区分连续提交的多个实例，每个实例使用一个 Instance ID 标识，Instance ID 由 Leader 本地递增生成即可。

Multi Paxos 允许有多个自认为是 Leader 的节点并发提交 Proposal 而不影响其安全性，这样的场景即退化为 Basic Paxos。

Chubby 和 Boxwood 均使用 Multi Paxos。ZooKeeper 使用的 Zab 也是 Multi Paxos 的变形。