一、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技术自媒体）