BIGO 技术 | Paxos 的工程实践与极致优化

一、Paxoskv 的研发背景

在 BIGO 内部，存储系统主要包含表格类存储系统 MyShard，分布式 key/value 类存储系统 ssdb [1]和 pika [2]，以及其它用于对象存储的分布式系统。key/value 的存储内部大量采用 ssdb 和 pika，虽然 ssdb 和 pika 都是很优秀的存储系统，但在 BIGO 业务场景的具体实践中，BIGO 技术遭遇到了不少的问题和挑战。例如，ssdb 和 pika 都是采用基于 binlog 的 primary/backup [3]复制模型，primary/backup 模型很好地解决了读扩展问题的同时，也带来了如下图所示的一些问题：

1) primary/backup 之间的数据同步，不仅涉及到数据是否会丢失的问题，还涉及到整个存储集群对外可以提供什么样的一致性模型的问题。而单一的同步方式，无论是采用异步、半同步还是强同步的方式，都无法满足不同业务差异化的需求。

2) primary 上 data 操作和 binlog 操作的原子性，既和复制的进度管理有关，又和多副本系统中的一致性有关。比如在 MySQL 内部，innodb 和 binlog 之间采用内部 XA 事务来解决这个问题，但在现有系统上如何解决好这个问题就比较有挑战。

3) primary/backup 模型，比较难处理多 region 写入的问题。简单的多点写入不仅无法提供正确的一致性边界，而且可能导致更新静默丢失等问题，从而给故障定位和运维带来较大的负担。

4) primary/backup 模型在多区部署的情况下，存在 primary 节点 fanout 放大、跨 region 流量冗余传输、backup 节点资源利用受限等潜在问题。

5) pika 也提供类似 NRW [25]的复制模型，但即使采用 R+W > N 的 quorum 配置，如果不采用 read repair 等手段，也无法提供线性一致性，具体示例参考“2.3.6”章节。

总之，相对于 BIGO 多元化的业务种类和快速增长的数据规模，现有存储系统在数据一致性、系统可用性、性能和跨 region 部署能力等方面，已经无法满足 BIGO 内部业务系统的诉求。具体而言，BIGO 业务对存储系统的核心诉求包含：

● 具备从线性一致性到最终一致性的多种一致性模型，不同业务场景可以根据自身的 SLA，在 RTO 和 RPO 之间权衡；

● 具备多点写入的能力，即宏观上是一个 multi-master 的系统，在容错设计内的节点故障，不对系统可用性产生影响；

● 具备深度的掌控/定制能力，可以下沉部分高频业务场景到存储层；简化开发的同时，有利于提升业务的核心竞争力；

● 具备友好的水平扩展能力，可以快速地扩/缩容；在交付效率和资源利用方面更进一步；

基于上面这些背景，我们开发了 paxoskv。其设计目标是：具备线性一致性/因果一致性/最终一致性可选的能力，具备多点写入的能力，具备水平扩展能力，读写性能和 ssdb、pika 相当。

二、Paxoskv 的技术实现

2.1 系统架构

Paxoskv 的系统架构示意如下，每一个 set 对应一个逻辑数据分区，每一个 set 在服务端有多个 replica(图中以 3 副本为例：replica1/replica2/replica3)。每一个 set 内的 key，按照一致性 hash 划分为多个 key space，每一个 key space 对应到具体 replica。这样做的目的是为了让每一个 replica 都具备处理请求的能力，与之对应的是 raft [23]这类强 leader 协议，所有的写请求必须路由到 leader 节点，由 leader 节点发起。这样对 follower 节点的资源利用不是十分充分，一定程度上降低了整个集群的处理能力。

每一个 replica server 可以包含多个 set 的 replica，同时对多个 set 进行服务。一个 replica server 所服务的 replica 数量，可以随着迁移、物理机器扩容等因素而不时变化。整个集群的元数据存储在 etcd [16]中，smart client 通过 watch 的方式及时感知整个集群拓扑情况的变化。

2.2 设计选型

在 paxoskv 的设计选型上，我们主要结合了“Paxoskv 的研发背景”部分描述的现状、BIGO 内部业务的诉求、以及较为前沿的分布式存储系统技术，来进行综合的判断和取舍。设计中，BIGO 技术借鉴了 WPaxos [24]中的很多想法，最终选择 paxoskv 的理论支撑和工程实践设计如下：

● 在复制模型方面，RW 节点间 paxoskv 采用 leaderless 的 multi-paxos 架构，既允许多点写入、又借助于 multi-paxos 来保证多个副本间状态的一致性；

● 为避免 data 操作和 binlog 操作原子性的问题，RW 到 RO 节点、RO 节点到 RO 节点间 paxoskv 通过复制存储引擎的 WAL 来回避这个问题，同时也带来了成本和复制实时性方面的一些收益；

● 为应对多 region 部署的需求，和 cloud spanner [5]类似，paxoskv 内部节点分为 RW(read-write)和 RO(read-only)两种角色，在 region 内部 RW 间采用 multi-paxos 做强同步复制，跨 region 通过 RO 做异步复制，多个 region 间采用 chain-replication，避免产生冗余的跨 region 流量；

● 另外，paxoskv 是一个 key 一个独立的 multi-paxos log 序列，不同的 multi-paxos log 之间完全隔离，比较好地可以让大量的 paxos 实例并行运行，从而提升集群层面的并发响应能力；

2.3 深度优化

2.3.1 Leaderless

目前主流基于 multi-paxos 的多副本存储系统中，都是采用 set 划分的方式，一个 set 管理一个数据分片，一个 set 对应一个 multi-paxos log。Paxoskv 的实现中，为了满足系统水平扩展性的需求，也是采用 set 化的思想，不过一个 set 中包含多个 multi-paxos log。具体而言是每一个 key 都有自己独立的 multi-paxos log。在同一个 set 内，在 smart client 发起请求时，会根据一致性 hash，将同一个 set 中的不同 key 均匀地分布到多个副本之间。所以 paxoskv 是具备多点写入能力的 leaderless 架构，在微观层面，对于同一个 key，如果集群拓扑稳定，则走 fast accept 路径，反之则走 slow accept 路径，即原生的 paxos 算法两阶段流程。

Leaderless 设计的一个好处是可以提供集群层面更好的可用性保证，在基于 raft [23]或 primary/backup [3]的设计中，通常采用租约的方式来保证系统中同一时刻只有一个 Raft leader 或 primary 节点，以避免在网络分区等情况下产生“多主”问题。租约方式的不足是，租约期设置太小容易导致误判，网络抖动被认为是节点不可用；租约期设置太大，又会导致真正故障发生时，上一任租约过期到选出新租约持有节点的间隔较长，这个过度窗口期整个集群是不可用的，会影响系统的 SLA。

如下图所示(图片来源[7])，Paxos 算法天然具备 leaderless 属性，无论是否有稳定的 proposer leader 节点存在，都可以保证算法的 safety，最多牺牲一些 liveness。工程实践中，可以通过随机避让和重试等手段来提升 paxos 实例的 liveness。这也是我们选择 paxos 作为共识算法的原因之一：

BIGO 实际的业务场景中，同一个 key 从不同的 client 并发请求，且部分 client 和其对应的 paxoskv 节点遭遇网络分区(进而认为节点不可用，转而切换到其它节点重试)发生的概率非常低。所以在向一个节点请求超时后，可以快速换节点发起重试请求，这样系统的不可用时间窗口就大幅降低了。

2.3.2 Log is data

Log is data 最早较为正式的起源是新国大 2012 年 VLDB 的论文《LogBase: A Scalable Log-structured Database System in the Cloud》[8]，目前已经成为云原生数据库架构的重要设计理念之一，主要是为了解决传统 WAL + data page 数据库架构中写入 IO 容易成为瓶颈的不足。如下图所示：

在 paxoskv 的实现中，value 本身是 paxos log 的一部分，是比较合适采用 log is data 思想的场景。即 BIGO 技术把运行 paxos 达成共识的 paxos log 和最终对业务提供读/写的 value 融为一体，无需先写 paxos log，再 replay paxos log 到存储引擎。但 paxoskv 目前的实现中，还是会带来一定程度的读/写放大，尤其是 value 较大的场景体现较为明显，采用多版本机制是更合理的方法，这是后续需要优化的方向之一。

2.3.3 Fast accept

如下图所示(图片来源[9])，原生的 paxos 算法分为两个阶段：第一阶段包含 phase-1a propose 和 phase-1b promise；第二阶段包含 phase-2a accept 和 phase-2b accepted；每一个阶段消耗 1 个 RTT。Paxoskv 虽然采用 leaderless 的架构，但实现中借鉴了主流 multi-paxos 工程实现中具备 stable leader 的优化。对于同一个 key，如果最新的 chosen log 其发起者正好是当前节点(Proposer ID 会被记录在 paxos log 的 meta 信息中)，那么就不需要执行原生 paxos 算法的第一个阶段(phase-1a propose/phase-1b promise)，直接发起 phase-2a accept 请求，我们称 paxoskv 中的这种流程为 fast accept(在具体的工程实现中，为了保证协议的正确性，fast accept 的提案会以 1:Proposer ID 作为提案编号发起，而非 fast accept 的提案会以 2: Proposer ID 作为提案编号发起)。因此，大多数集群拓扑稳定的情况下，paxoskv 都可以走 fast accept 路径。

2.3.4 Fast chosen

如下图所示(图片来源[9])，原生的 paxos 算法中，有 Proposer/Acceptor/Learner 三个角色，一个典型的 paxos 算法执行流程如下图所示：

我们可以看到，即便是走 fast accept 的路径，从发起 accept 请求到确定一个提案已经 chosen，需要 1.5 个 RTT(Proposer → Acceptor → Distinguished Proposer/Learner → Acceptor)，在更新频繁的场景，可以在下一个请求之上 piggyback 上一个提案的 chosen 通知。注意，如果每一个 acceptor 在 accepted 一个提案后，可以广播给所有的 Acceptor，以快速确定是否已经满足多数派计数从而达成 chosen 状态，但工程实现中一般不会这样做，因为消息复杂度太高。

paxoskv 的实现中，在 3 副本的情况下，Proposer 会先本地 accepted，然后再发送 accept 请求给 acceptors，这样一来，任何一个 acceptor 只要本地判断满足 accepted 的条件，加上 Proposer 的一个 accepted 计数，就可以确定满足 majority accepted 的条件，从而快速进入 chosen 状态。和前面提到的下一个请求之上 piggyback 上一个提案的 chosen 通知方式相比，写入的延时没有明显的改善，但这里可以和 log is data 的思想结合，对于 acceptor 来说，确定 chosen 后一次磁盘写入就完成了本次 paxos 的流程，节省了一次写 Rocksdb [10]的 IO 操作。当然，fast chosen 只有在 3 副本的配置下才能生效(BIGO 的实际部署中，目前都是 3 副本的配置)。

2.3.5 WAL replication

在采用 binlog 进行复制的系统中，在产生 binlog 的节点上要面临更新 data 和 binlog 原子性的问题。binlog 通常又分为基于 statement 和基于 ROW 的两种格式，涉及到的问题包含如何保证在其它副本上 replay binlog 后产生相同的数据页、同时还要考虑同步的 binlog 的大小、binlog 是否可以被并行 replay 等问题。

在 paxoskv 的实现中，因为最终存储数据的引擎是 Rocksdb [10]，所以 BIGO 技术采用基于 Rocksdb WAL log 的复制。如下图所示：

paxoskv WAL replication 的实现主要依赖 Rocksdb [10]的 GetLatestSequenceNumber()和 GetUpdatesSince()这两个 API。在初始化或者复制中断恢复时，采用 pull/push 结合的模式来对齐同步位点，具体的实现和 MySQL 5.7 基于 GTID 的 binlog 复制比较类似[11]。

2.3.6 Linearizable quorum read

在强一致的存储系统中，实现线性一致性读写，一般是通过在 paxos proposer leader 上实现 master lease 来完成，亦或者从集群中实施多数派读来实现。上述主流实现方式中，leader 节点容易成为集群的瓶颈，follower 节点的资源则比较难以充分利用。paxoskv 针对这个问题，借鉴《Linearizable Quorum Reads in Paxos》[12]中的算法，优化了 paxoskv 的线性一致性读的流程，实际验证表明性能有 80+%以上的提升。

简单的 quorum 读并不能保证线性一致性，例如传统的 NRW 模型，即便在选择 R + W > N 的 strict quorum 配置下，也会破坏线性一致性。如下图所示，Reader A 先发起读请求，返回了新版本的值 x=1；此后某个时间点 Reader B 后发起读请求，却返回了旧版本的值 x=0，破坏了线性一致性的约束。图片来源于《Designing Data-Intensive Applications》：

具体的实现算法为 Paxos Quorum Reads(简称为 PQR)，图片来源于《Linearizable Quorum Reads in Paxos》[12]论文：

算法分为 quorum-read 和 rinse 两个阶段。quorum-read 阶段，smart client 从除 leader 之外的多数派中读取最新被 accepted 的 slot。每一个 replica 不管 accepted slot 是否存在 gap，直接返回自己所见的最大 accepted slot，例如某一个 replica 本地 accepted 的 slot 是[1,4]和 6，那么返回 6 给 smart client。smart client 收集所有回复中最大的 accepted slot，作为发起 rinse 阶段的 accepted slot，这个 slot 的 value 会作为最终返回给调用的 value；但这个 accepted 的 slot 可能还没有完成 commit，所以 smart client 必须等待以确保这个 slot 已经完成持久化的 commit，通过这种方式来完成 client 视角的强一致性。

在 rinse 阶段中，smart client 向 quorum-read 阶段的 replica 集合中任意一个 replica 发送请求，检查对应的 accepted slot 是否已经被 commit。如果被选中的 replica 回复已经 commit，smart client 以这个 commit 的 value 返回给调用者。

这种方式还是需要 2 个 RTT 才能完成强一致性的读，paxoskv 在实现的时候，在 quorum-read 阶段，返回最新的 accepted slot 和最新的 committed slot。如果多数派的 replica 返回了相同的 accepted slot 和 committed slot，实际上这就是集群中最新的数据；换句话说，保证了线性一致性的约束。因此，paxoskv 中大多数场景下，线性一致性都只需要一个 RTT 就可以完成。

三、总结与展望

自从 Paxos 算法 1989 年[9]问世以后，工业界很多重量级产品都基于 Paxos 算法或其变种来构建高可用能力和提升数据的一致性，例如大家熟悉的 Google Chubby [14]、Apache Zookeeper [15]，以及比较新的 etcd [16]和 consul [17]等。但这些实现都强依赖一个中心化的 leader 节点，所以这类系统基本都只能部署在 IDC 内，或者同城的 IDC 之间，我们称这类协议为 leader-based 的协议。

Paxos [9]算法也一直是学术界的热点，比较新的研究成果包含 Mencius [18]协议和 EPaxos [19]协议，这两者都属于 Leaderless 的协议，Mencius [18]协议通过对 paxos 实例进行静态的预分配，虽然达到了多点写入的目的，但其提交的延时还是依赖于集群中最慢的节点。而 EPaxos 协议应用于实际工程中，主要的缺陷是通常需要 3/4（大于常规的多数派 [n/2]+f）的节点通讯正常，其次是协议工程化复杂度较高。所以虽然 Mencius [18]和 EPaxos [19]比较好的解决了多点写入的问题，但是由于上述限制，还是无法部署于副本之间延时比较高的场景，比如异地多 IDC 之间。

应对 leader-based 协议只能单点写入的另外一个途径是 sharding，比如 Google Spanner [20]、ZooNet [21]和 Bizur [22]等，但这些解决方案美中不足是对数据进行了静态分区，而且以分区为粒度生成 multi-paxos log 一定程度上降低了并发能力。实际的业务负载中，通常数据的局部性会不时动态变化，因此比较理想的情况是存储系统具备根据业务 access patterns 和服务器的负载等维度，应用相关的策略来动态调整数据对象的读/写访问接入点。在下一阶段的迭代中，paxoskv 将重点打造下面两个主要功能：

3.1 Access patterns/Load aware

前面提到，在同一个 set 内 paxoskv 采用一致性 hash 来将不同的 key 打散到不同的节点上，但如果业务的 key 分布相对稳定，即某一部分 key 都稳定在一个固定的 IDC 内进行读写，那么一个比较自然的调整就是将这部分 key 的读写请求发往离 client 最近的节点，这样达到比较优化的端到端延时。和 work stealing [13]设计类似，更通用的抽象是根据不同的 access patterns，以不同的 key 分布策略来动态调整每一个 key 的就近接入点。与此类似，我们也可以根据节点间的负载，来动态迁移一部分 key 的接入点，来达到整个集群层面资源利用更合理的效果。

3.2 Lightweight Multi-Key Transaction

paxoskv 在 BIGO 内部上线后，收到了很多反馈和需求，其中大部分是产品化能力加强的需求，其中技术侧比较迫切的需求是实现多个 key 操作的原子性，比如在赠送相关的业务场景，实质是一个 A 减 B 加的过程。paxoskv 在下一个迭代中，将提供跨多个 set 的轻量级 multi-key 事务。

四、收获与感谢

从 paxoskv 设计研发到上线落地的过程中，BIGO 技术深刻地体会到开发一个健壮的分布式存储系统所面临的挑战和取舍。比如如何测试并验证系统的正确性，如何验证系统在遭遇异常后的自愈能力。再比如我们选择了 key 粒度的 multi-paxos log，虽然带来了多点写入和并发能力提升方面的收益，但是也给集群的成员变更、全局快照备份等方面带来了很大的复杂度。这些问题我们将在后续的介绍中陆续展开，也借这个机会感谢所有给我们提出宝贵建议和反馈的同学们！

（稿件来源 BIGO 技术自媒体）