一、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，尽管带来了多点写入和并发能力晋升方面的收益，然而也给集群的成员变更、全局快照备份等方面带来了很大的复杂度。这些问题咱们将在后续的介绍中陆续开展，也借这个机会感激所有给咱们提出贵重倡议和反馈的同学们！
参考资料
[1]:http://ssdb.io/zh_cn/
[2]:https://github.com/pika/pika
[3]:https://en.wikipedia.org/wiki…_(computing)#Primary-backup_and_multi-primary_replication
[4]:https://www.cs.cornell.edu/co…
[5]:https://cloud.google.com/span…
[6]:http://muratbuffalo.blogspot….
[7]:https://www.slideshare.net/In…
[8]:http://vldb.org/pvldb/vol5/p1004_hoangtamvo_vldb2012.pdf
[9]:https://en.wikipedia.org/wiki…_(computer_science)
[10]:https://github.com/facebook/r…
[11]:https://dev.mysql.com/doc/ref…
[12]:https://www.usenix.org/system…
[13]:https://en.wikipedia.org/wiki…_stealing
[14]:Chubby,https://static.googleusercont…
[15]:Zookeeper,https://github.com/apache/zoo…
[16]:etcd,https://github.com/etcd-io/etcd
[17]:consul,https://github.com/hashicorp/…
[18]:Mencius,https://www.usenix.org/legacy…_papers/mao/mao.pdf
[19]:EPaxos,https://www.cs.cmu.edu/~dga/p…
[20]:Spanner,https://www.usenix.org/system…
[21]:Zoonet,https://www.usenix.org/system…_paper-lev-ari.pdf
[22]:Bizur,https://arxiv.org/abs/1702.04242
[23]:Raft,https://www.usenix.org/confer…
[24]:WPaxos,https://cse.buffalo.edu/tech-…
[25]:http://courses.cse.tamu.edu/c…
（稿件起源 BIGO 技术自媒体）