本文翻译自《A Guide to the BookKeeper Replication Protocol (TLA+ Series Part 2)》，作者 Jack Vanlightly。原文链接：https://medium.com/splunk-maa…。

译者简介

王嘉凌 @中国移动云能力核心，挪动云 Pulsar 产品负责人，Apache Pulsar Contributor，沉闷于 Apache Pulsar 等开源我的项目和社区

咱们晓得关系型数据库中的数据是按表构造来存储，客户端能够将数据存储到表中以及从表中读取数据。Apache BookKeeper 中的数据是按日志构造来存储，客户端以日志的模式读写数据。日志构造是一种只反对数据追加操作的简略数据结构，反对多个客户端同时读取，以及非破坏性读取。

作为数据结构，日志和队列的性能十分类似，区别在于日志反对多个客户端同时独立地从不同地位读取残缺的数据。因而，日志必须反对非破坏性读取。而队列则是破坏性读取，队列的头部元素被读取后会被删除。这意味着队列中的每个元素只会被一个客户端读取到。

作为 Apache Pulsar 数据存储层的 Apache BookKeeper，自身也是一个简单的分布式系统。BookKeeper 利用多正本机制来实现数据的平安和高可用。多正本指的是每一份 entry 数据都会被复制到多个节点保留，以便在产生局部节点故障时依然能够提供读写服务，并且保障已保留的数据不会失落。BookKeeper 应用一套独有的多正本协定，这个协定规定了多个服务节点之间如何协同来实现服务的高可用以及保证数据的平安。

基于分片的日志数据结构

诸如 Apache Kafka 和 RabbitMQ 这样应用基于队列和日志的音讯队列，都是将每个队列或分区的数据视为一个整体来存储，这样一来整个数据必须全副存储在同一个存储节点。BookKeeper 应用了一套基于分片的日志数据结构，每个日志数据由一系列的分片数据（Segment）串联组成。Pulsar 的一个 Topic 分区 数据实际上是分为多个数据分片来保留。

咱们晓得每个 Pulsar Topic 都有一个惟一的 Pulsar broker 作为 owner，这个 broker 负责给所属的 Topic 创立数据分片，并将这些数据分片进行串联以便在逻辑上组成一个残缺的日志数据。

图 1：Pulsar Topic 的数据由一组数据分片串联组成

BookKeeper 将这些数据分片称为 Ledger，并将它们保留在 BookKeeper server 节点（称为 bookie 节点）。

图 2：Pulsar broker 将 topic 数据存储到多个 Bookie 节点

BookKeeper 多正本协定和每个 ledger 的生命周期非亲非故。多正本协定自身的实现封装在 BookKeeper 客户端类库中，每个 Pulsar broker 通过调用 BookKeeper 客户端类库中的接口来和 BookKeeper 进行交互，如创立 ledger，敞开 ledger，以及读写 entry。这些接口背地蕴含了非常复杂的协定逻辑，在本篇博客中咱们会逐层剖析并展现协定的实现细节。

首先，创立 ledger 的客户端即为这个 ledger 的惟一 owner，只有 owner 能够往 ledger 里写数据。对于 Pulsar 来说，这个客户端就是作为分区 Topic owner 的 broker，Broker 负责创立 ledger 来组成这个 Topic 的数据段。当这个客户端因为某些起因产生故障时，另一个客户端（对于 Pulsar 来说就是另一个 broker）会染指并接管这个 Topic，这个时候须要修复之前的 ledger 中处于正在复制（under-replicated）状态的 entry 数据（即 recovery 操作）并将 ledger 敞开。

图 3: Ledger 的生命周期

每个 Pulsar topic 仅蕴含一个 open 状态的 ledger 和多个 close 状态的 ledger。所有的写操作都会写入到 open 状态的 ledger，而读操作则能够从任何 ledger 中读取数据。

图 4: 写操作只会写入到 open 状态的 ledger

每个 ledger 都会保留到多个 bookie 节点上，每个 ledger 和存有这个 ledger 的 bookie 池（称为 ensemble）的对应关系保留在 ZooKeeper。当 open 状态的 ledger 大小达到了阈值，或者这个 ledger 的 owner 产生了故障，就会敞开这个 ledger 并从新创立一个新的 ledger。依据配置的多正本参数，新创建的 ledger 可能会被保留到另一组 bookie 池上。

图 5：Ledger 数据的多个正本保留在多个 bookie 节点，每个 Ledger 的元数据以及一个 Topic 蕴含的 ledger 信息保留在 ZooKeeper

数据写入 ledger 的过程

BookKeeper 蕴含以下 ledger 多正本配置相干的参数：

• Write quorum (每份 entry 数据须要写入多少个 bookie 节点), 简称 WQ。
• Ack Quorum (须要从多少个 bookie 节点收到写入胜利的响应后能够确认这份 entry 写入胜利), 简称 AQ。
• Ensemble size (用于存储 ledger 数据的 bookie 池的节点数量), 简称 E。当 E > WQ 时，entry 数据会交织地写入到不同的 bookie 节点。

一条 entry 数据理论写入的 bookie 节点的汇合成为写入汇合。当 E > WQ 时，相邻的 entry 的写入汇合可能会不一样。

Pulsar 为每个 Topic 裸露了设置 AQ、WQ、E 参数的 API 来自定义正本设置。

图 6：WQ=3，AQ=2 时的音讯写入和确认

最初增加确认 (Last Add Confirmed, LAC)

BookKeeper 客户端会继续更新已确认写入的 entry 中间断且最高的 entry ID，咱们称之为 Last Add Confirmed (LAC)。这是一条水位线，高于这个 entry ID 的 entry 都还没有被确认写入，而低于和等于这个 entry ID 的 entry 都曾经被确认写入。每一条发往 bookie 的 entry 数据中蕴含了以后最新的 LAC，这样每个 bookie 都能够晓得以后 LAC 的值，只管有一些提早存在。咱们还会在下文看到 LAC 除了作为已提交 entry 的水位线，还施展着其余作用。

Ledger 数据段

Ledger 自身也能够分成一个或多个数据段（fragment）。当 Ledger 创立时，蕴含了一个数据段，调配了一个 bookie 池用于存储这个 Ledger 的数据。当产生某个 bookie 写入失败时，客户端会用一个新的 bookie 来代替。这个时候会创立一个新的数据段，并从新发送未确认的 entry 数据和之后的 entry 数据到新的 bookie 上。当 bookie 再次写入失败时，又会再次创立一个新的数据段，以此类推。Bookie 写入失败并不意味着这个 bookie 节点不可用，网络稳定等其余状况也会造成单次的写入失败。不同数据段的数据存储在不同的 bookie 池上。数据段也通常被认为是写入汇合（Ensemble）。

图 7：第二个数据段的创立过程

Ledger 数据段能够看作是通知 BookKeeper 客户端去哪里找到某个 ledger 中的 entry 数据的元数据。Bookie 节点本身是不晓得这些元数据信息的，它们只负责存储接管到的 entry 数据并创立基于 ledger ID 和 entry ID 的索引。

图 8：往 B3 bookie 节点写入 entry 1000 失败并导致 ledger 创立第二个数据段

从 ledger 读取数据的过程

从 ledger 中读取数据的操作分为以下几种状况：

• 失常读取 entry 数据
• 长轮询读取 LAC 数据
• Quorum LAC 机制下的读取数据
• 恢复性读取数据

和写数据不一样的是，咱们只须要读取一个存有数据的 bookie 节点就能够失去想要的数据。如果这次读取失败了，也只须要从存有这个数据其余正本的 bookie 节点上从新读取数据即可。

客户端通常只心愿读取到已确认的数据，所以只会读取到 LAC 值标识的地位。在读取历史数据时，bookie 节点会根据以后的 LAC 值来告诉客户端何时进行读取。当客户端读取到 LAC 值并进行读取时，能够发动长轮询读取 LAC 数据。这个申请会先被 bookie 挂起，直到有新的 entry 数据被确认时才响应并返回新的 entry 数据。

另外两种读取数据的状况次要产生在数据修复时，咱们稍后再介绍。

实现不同的操作须要不同的响应数量

实现不同的操作须要从 bookie 节点接管到的胜利响应的数量不一样。比方，对于失常读数据的操作，只须要从一个 bookie 节点胜利收到响应即可实现。而有些操作则须要从多个 bookie 节点（quorum）收到胜利的响应才可实现。

这些操作依据须要收到响应数量的不同，能够分为以下几种类型：

• Ack quorum (AQ)
• Write quorum (WQ)
• Quorum Coverage (QC) QC = (WQ – AQ) + 1
• Ensemble Coverage (EC) EC = (E – AQ) + 1

Quorum Coverage (QC) 和 Ensemble Coverage (EC) 都满足于以下定义（以下两种定义实质上雷同，只是说法不同），QC 和 EC 的区别仅在于“汇合”的范畴：

• 对于指定申请，从足够多的 bookie 节点收到胜利响应，使得在给定汇合中 ack quorum（AQ）数量的 bookie 节点组成的任意组合中，都至多蕴含一个收到胜利响应的 bookie 节点。
• 对于指定申请，从足够多的 bookie 节点收到胜利响应，使得在给定汇合中不存在 ack quorum（AQ）数量的 bookie 节点没有收到胜利响应。

对于 Quorum Coverage (QC) 来说，这个汇合是指某个 entry 的写入汇合。QC 次要用于保障单个 entry 数据一致性的场景，如校验单个 entry 写入操作是否已被客户端确认。对于 Ensemble Coverage (EC) 来说，这个汇合是指存储以后 ledger 数据段对应的 bookie 池，EC 次要用于保障 ledger 数据段一致性的场景，如设置 ledger 的 fence 状态。

WQ 和 AQ 次要用于写数据，而 QC 和 EC 次要用于 ledger 修复过程。

Ledger 修复的过程

后面咱们讲到每个 ledger 只有一个客户端作为 owner，当这个客户端不可用时，另一个客户端就会染指并触发 ledger 修复过程而后敞开这个 ledger。对于 Pulsar 来说就相当于作为一个 Topic owner 的 broker 变得不可用，而后这个 Topic 的所有权转移到另一个 broker 上。

Ledger 修复过程包含找到最高的已被 bookie 确认的 entry ID，保障在这之前的每个 entry 都已复制了足够多的正本数量。之后将这个 ledger 敞开，此时会将这个 ledger 的状态设置为 CLOSED，并将最新的 entry ID 设置为最初被确认的 entry ID。

如何避免脑裂

BookKeeper 是一个分布式系统，这意味着网络稳定可能会导致集群被分隔成两个或者更多的区块。咱们构想如果一个客户端和 ZooKeeper 断开连接，那么这个客户端就被认为已不可用，另一个客户端会接管这个客户端负责的 ledger 并开始 ledger 修复流程。但这个客户端可能仍在失常运行，它能够失常的连贯到 BookKeeper 集群，于是就会呈现两个客户端试图同时操作同一个 ledger，这种状况就属于脑裂。脑裂是指一个分布式系统因为网络稳定决裂为多个独立的零碎，在肯定工夫后网络复原导致的数据不统一的状况。

BookKeeper 引入了 fence 这个概念来避免脑裂的产生。当第二个客户端（例如另一个 Pulsar broker）试图开始 ledger 修复流程时，会先将 ledger 设置为 fence 状态，在这个状态下 ledger 会拒接所有新的写入申请。当足够多的 bookie 节点将这个 ledger 状态设置为 fence 时，就算第一个客户端依然处于失常运行状态，它也不能再进行任何新的写入操作。而后第二个客户端就能够在没有其余客户端会持续写入数据或者试图修复同一个 ledger 的平安状态下开始 ledger 修复流程。

图 9：一个新的 Topic owner 开始将 ledger 设置为 fence，原先的 owner 写入新数据时无奈写入 Ack Quorum 设定的正本数，则无奈实现写入

修复流程第一步 — 设置 fence 状态

将 ledger 设为 fence 状态，并确认 LAC 的值。

Fence 申请实际上是一次 Ensemble Coverage 类型的读申请，获取 LAC 的值并带有 fencing 标识。每个 bookie 节点收到这个申请时会将这个 ledger 的状态设为 fence，并返回这个节点上对应 ledger 的 LAC 值。当客户端从足够多的 bookie 节点收到响应时，就示意申请胜利能够进行下一步操作。那么从多少个 bookie 节点收到响应才算足够呢？

咱们将 ledger 设置为 fence 状态是为了避免之前的客户端持续往 ledger 里写入数据。所以咱们只有保障还没有将这个 ledger 设置为 fence 状态的 bookie 节点的数量小于设置的 Ack Quorum 值，那么之前的客户端因为无奈收到足够多的写入确认而无奈写入新数据。新的客户端发动的 fence 操作不须要等到所有的 bookie 节点都将这个 ledger 设置为 fence，只须要满足还没有设置为 fence 状态的 bookie 节点数小于设置的 Ack Quorum 就可确认 fence 操作实现。满足这个条件所须要收到的响应数量就是 Ensemble Coverage。

修复流程第二步 — 修复 entry 数据

接下来，客户端从 LAC + 1 的 entry ID 开始发送恢复性读取数据的申请，并将这些 entry 数据从新写到新的 bookie 池中。写操作属于幂等操作，也就是说如果这个 entry 曾经写入到了某个 bookie 节点，再次向这个节点写入同样的 entry 不会造成数据反复写入。客户端会继续进行读和写的操作直到读完所有数据。确保在敞开 ledger 之前，这个 entry 的写入汇合中的所有 bookie 节点都写入了该 entry 的正本。

失常的读操作只须要从一个 bookie 节点接管到响应。与之不同的是，Recovery 读操作须要依据从这个 entry 的所有写入汇合的 bookie 节点上收到的响应内容来明确这个 entry 是否已确认。具体来说有以下两种状况：

• 已确认：收到 Ack Quorum 数量的胜利响应
• 未确认：收到 Quorum Coverage 数量的数据不存在响应 (已写入这个 entry 数据的 bookie 节点数量未达到 Ack Quorum)

如果所有响应都已收到，但两个阈值都未达到，那就无奈判断这个 entry 是否已确认，修复流程就会终止（可能存在收到其余谬误类型响应的状况，如网络稳定，这种状况无奈判断 entry 是否已胜利写入对应 bookie 节点）。修复流程能够反复执行直到能够明确每个 entry 最终的确认状态。

图 10：新的客户端在读取 entry 3 时收到了足够多的数据不存在申请，能够判断 entry 3 的状态为未确认。而后保障到 entry 2 为止的数据都复制到足够多的正本数

修复流程第三步 — 敞开 Ledger

一旦明确了所有已确认的 entry，且这些 entry 复制了足够多的正本数，客户端就会敞开 ledger。敞开 ledger 的操作次要是对 ZooKeeper 上 ledger 元数据的更新，将状态设置为 CLOSED，并将 Last Entry Id 设置为最新的已确认的 entry ID。这些操作和 bookie 自身不相干，bookie 也不会感知 ledger 是否被敞开，bookie 本身没有 open 或 closed 的概念。

ZooKeeper 上元数据的更新是一个基于版本控制的 CAS 操作。如果有另一个客户端同时在修复这个 ledger 并且曾经将 ledger 敞开，那么这次 CAS 操作就会失败。通过这种形式能够避免多个客户端同时对同一个 ledger 进行修复操作。

总结

本篇博客介绍了 BookKeeper 多正本协定的大部分实现内容。须要记住的重点是，bookie 节点只是单纯用来存储和读取 entry 数据的存储节点，在 BookKeeper 客户端中蕴含了创立 ledger、抉择存储 ledger 的 bookie 池、创立 ledger 数据段的操作，通过 Write Quorum 和 Ack Quorum 来保障多正本的机制，以及在产生故障时对 ledger 进行修复和敞开等一系列逻辑。

相干浏览

• 博文举荐|深刻解析 Apache BookKeeper 系列：第一篇 — 架构原理
• 博文干货|5 张图带你疾速入门 Pulsar 的存储引擎 BookKeeper

📣 Pulsar Storage 特地兴趣小组（SIG）已成立！扫描下方🤖️ Pulsar Bot 二维码，回复 BookKeeper 退出 Pulsar Storage 探讨群。

扫码退出

关注 公众号「Apache Pulsar」，获取更多技术干货