Pulsar 的共识机制和成员管理
参考：
Jack Vanlightly 的这篇博客虽然是讲的BookKeeper，但实际上，整体还是Pulsar的内容偏多。因为单纯的BookKeeper本身并不涉及到共识机制和成员管理的内容。
共识机制与存储分离
对比一下 Raft 和 Kafka 的共识方式，如下图，
Raft 和 Kafka 的参与共识的节点和数据存储的节点是合一的，一个节点即参与共识，也完成数据存储。数据写入请求都是先发送到 Leader 节点，再同步到 Follower 节点。这样的设计，成为内置（internal）共识机制。
这个设计的一个很大的问题就是集群的成员管理相对固定，博客的原文是，
A byproduct of replication being performed by stateful fully integrated nodes is that cluster membership is relatively static.
如果想要增加或者删除节点，就会比较受限，非常麻烦。Pulsar 的设计是不一样的，分离了共识节点和存储节点。存储节点是单纯的存储功能，不需要处理自己在共识机制中的角色（实际上也没有角色），也不需要处理存储数据复制的问题。共识机制放在了客户端，也就是 Pulsar Broker 上处理，如下，
对 Bookie 节点来说，Bookie 本身只是存储，提供通用的 Entry 存储功能。共识机制放在 Broker 处理，也就是说，Broker 在维护 Leader 的角色。
对 Raft 来说，如果节点故障一段时间后恢复，只需要将 Leader 节点上的数据复制过去就可以恢复节点，但 Pulsar 的 Leader 因为没有存储数据，处理起来就会非常麻烦（后文详述）。
但是因为分离了共识机制和存储，也会带来好处，Broker 可以快速的改变成员，来应对数据节点的故障，这个特性称为动态成员管理。那 Pulsar 是如何实现动态成员管理的特性的呢？
Commit Index
比较 Raft、Kafka、Pulsar，这三者都有 Commit Index 的概念，虽然在不同系统中的名称不一样。其基本特点是，都需要达到一定数量的写入成功，才可以确认 Commit Index，比较一下，
- Raft 需要集群的大多数节点确认，才可以 Commit Entry；
- Kafka 需要 min-insync-replicas 个确认，才能确认持久化成功；
- Pulsar 需要 Ack Quorum (AQ) 个确认，才确认 Commit Entry；
为了方便描述，这个数量在后文统一称为提交数量（Commit Quorum）。
数据确认提交后，会返回 Entry Log 中提交成功的点，Raft 称呼这个点叫 Commit Index；Kafka 称之为高水位（High Watermark）；BookKeeper 称之为 LAC（Last Add Confirmed）。这个机制的存在主要是保护各个节点数据的一致性。
对于 Raft 和 Kafka，Commit Index 是和数据一起从 Leader 传输到 Follower，最后，所有的节点都更新到了 Commit Index 和数据。Leader 对 Commit Index 的认知是略微超前 Follower 的，但通常情况下，这也没问题。如下图，
对 Pulsar 来说，存储和共识机制是分离的，LAC 需要存储在 Bookie 中，但这些信息对 Bookie 来说几乎是没有用的。写入的过程也比较有特色，顺序是：写入数据 -> 更新 Leader Broker 的 LAC -> 更新 Bookie 的 LAC 存储。相比 Raft 和 Kafka，要多了一个步骤，不过由于可以流水线组合处理，实际性能也不会差。如下图，
Raft Commit Index 的部分似乎并不精确，Raft 会收到大多数节点的 Ack 之后，才会更新 Commit Index。Leader 当然会比 Follower 更早知道下一个 Commit Index，但只有收到 Follower 的 Ack，才可以确认这个 Commit Index。
Kafka 的数据副本特性
动态成员管理可以解决什么样的问题？主要是副本创建、数据复制的灵活性，先看看 Raft 的例子。
当部分节点缓慢，或者故障的时候，由于 Raft 选择的是相对固定的成员管理方案，无法及时变更成员。为了提升系统整体的可用性，只能放弃一些安全性，选择了在有少量节点，不超过一半，有故障的前提下，依然可以提供服务。
Kafka 的选择也很类似，只要 min-insync-replicas 个节点能正常运行，就可以提供服务，不需要整个副本集合完全正常运行。
但是，这样的选择会破坏 liveness。liveness 是分布式算法领域的属性，用来衡量分布式算法的好坏，比如，
- liveness: something good eventually happens. 或者说，算法期望的结果最终将发生；
- safty: nothing bad happens. 或者说，不会发生恶性结果；
对 Raft 和 Kafka 来说，liveness 要求，数据将在所有节点上最终复制成功。达到这个目标，有以下一些事实前提，
- Entry 按时间顺序追加在 Leader 的日志/Entry文件中；
- Leader 将日志/Entry发送给 Follower，要求 Follower 按同样的顺序进行存储；
- 提交的日志/Entry达到大多数（Raft），或者 min-insync-replicas（Kafka） 个时，就不考虑丢失；
- Follower 节点上的日志/Entry文件和 Leader 完全一致，特指从 Commit Index 开始往前的部分；
对于这样一个复制机制，从第一个节点写入 Entry 开始，到 Entry 复制到所有副本上，Entry 通常会处于3种状态，如下，
最开始，Entry 追加到头部，但还没有更新 Commit Index，可能丢失；然后，Leader 收到足够多的 Ack，更新 Commit Index，Entry 就持久化到了足够多的副本中，不会丢失了；最后，Entry 持久化到了所有副本中，处理完成。从上图来看，在系统运行的任何一个时刻，我们有，
Uncommit Index(Head) >= Commit Index >= Full-replicated Index
对系统使用来说，我们希望 Uncommit Index(Head)、Commit Index、Full-replicated Index 尽量接近，Tail 部分尽量大。但事与愿违，如果几个节点中，有一个比较慢，始终追赶不上其他节点同步副本的速度，或者有一个节点故障后丢失数据，需要从零开始恢复，这个时候，我们只能依赖副本复制机制。在复制期间，liveness 是受损的。
Pulsar 的数据副本特性
Pulsar 是通过写入数量（Write Quorum）和响应数量（Ack Quorum）来管理副本的，细节这里不介绍了。
对 Pulsar 来说，分离共识机制和存储，使得共识机制在无存储的 Broker 上实现，当发现一个 Bookie 节点不可用的时候，就马上选取另一个 Bookie 替代。如下，
对集群的整体改动，也就是修改一下 Zookeeper 中账本的元数据，然后重新发送一下 Uncommitted Entry 去新 Bookie 就好了（因为已经 Commit 的 Entry 认为不需要再同步了）。这会导致 Ledger 的数据被分成多份，称之为 Fragment，放在多个 Bookie 上。每次有 Bookie 故障，就发起成员变更，并切分一个 Fragment 出来，以应对这个问题。如下图，一个 Ledger 分为了4个 Fragment，
当仔细分析 Ledger 头部的 Entry 存储时，我们会发现结构和 Kafka 类似，如下，
当成员变更发生时，Bookie 会丢弃尚未达到 Ack Quorum 的 Entry，只保留 Commit Index 之前的部分。新的 Bookie 从 Commit Index 之后开始，如下图，
成员变更时，Pulsar 并不会处理 Full-replicated Index 和 Commit Index 之间的数据，于是导致 Bookie 上多个 Fragment 的存储可能尾部出现空洞，变成这样，
Pulsar 不在成员变更的时候处理这个空洞的原因也是很自然的，因为很有可能此时 Bookie 处于故障阶段，Pulsar 即使想补足数据也是很难做到的。空洞的数据最终会由单独的恢复程序补足，但这并不是主流程的一部分。对比一下 Kafka 和 Pulsar 的存储结构图，
虽然 Pulsar 的存储中间会发生空洞，但是当发现节点无法及时返回的时候，Pulsar 会立刻开始调整成员，恢复到正常的副本数，所以每个空洞都不会很大；而 Kafka 的存储虽然没有空洞，但是可能出现 Full-replicated Index 远远落后于 Commit Index 的情况。可见 Pulsar 的设计对系统整体的 liveness 有改进。
当 WQ=AQ 时
出于数据安全性的考虑，可能 WQ=AQ 是一个选择。假设 WQ=AQ=3，如果有节点发生故障，我们可以得到下图，
可以看到，由于 WQ=AQ，那么，就始终有 Commit Index == Full-replicated Index，不会有节点处于未被完全同步的状态。如果 Bookie 发生故障，还是从 Commit Index 开始新的 Fragment，数据的空洞问题解决了。当然，这个方法也有问题。
比如，必须准备有足够多的 Bookie 节点，否则当节点故障的时候，如果没有新 Bookie 的加入，就无法继续运行。
还有，可用性会有小幅度降低，因为在成员变更的时候，取决于 Zookeeper 操作的性能，在此期间，Broker是无法运行的。
注：这两个原因有些似是而非，在 AQ < WQ 的时候，也会有一样的问题。当 AQ < WQ 时，如果发生故障，会延迟一段时间进行成员变更，这一小段的可用性是可以保证的，但这个时间几乎可以忽略不计。还有，因为 Ack 数量增多，系统延迟必然变大，但是如果 Bookie 的性能可以跟得上的话，其实延迟问题应该不显著。
虽然，从系统整体上来看，我也认为 AQ < WQ 是最佳实践。
后记
Pulsar 的动态成员管理功能是一个很好的功能，但是其来源并不是存储与共识机制分离，而是单 Topic 多 Ledger，单 Ledger 多 Fragment 等特性的一个具体的应用而已。
