业内有公开资料的分布式关系型数据库和分布式nosql，存算一体的架构大多数都是基于共识算法或者异步复制的分布式日志，搭配rocksdb这类单机存储引擎构建的，这些系统有着类似的架构，但在许多细节上又不尽相同，甚至许多公司的nosql团队会同时维护着好几款架构不同的产品。本文希望给出一个分布式存储引擎的设计方案，能够涵盖市面上大多数分布式日志+单机存储引擎架构的存储系统需求，创造一个能够同时支撑分布式kv、表格、图甚至关系型数据库等存储系统的高性能基座。

分布式存储引擎仍然是以库的形式提供，使用方需要在分布式存储引擎上定义数据模型和网络协议等。
为了便于理解，前两章的单机存储引擎部分以rocksdb为例，第四章会讲相对于rocksdb的改进。
数据分片不在本文的讨论范围内，所以文中的都是以一个分片的多个副本为例。

共识算法和强一致

基于共识算法和单机存储引擎实现一个强一致分布式存储系统的方案已经非常成熟了，这里为了给后文做铺垫简单叙述一下：每个分片的多个副本中，选出一个master副本，所有写请求都编码成操作日志，由master提交，经过共识算法达成多数派，并且成功写到master本地存储引擎后，再向客户端返回成功，这样所有发到master的读写请求就是强一致的了。

下面再说一下跨区的部署模型，示例中的元数据部分不属于分布式存储引擎，这里为了逻辑完整，给出一种简单的元数据管理方案，另外如TiDB的PD方案原理是一样的。

强一致部署.png

上图的跨区部署架构中，etcd集群用来存储元数据，并且etcd的副本分布情况要与存储集群一致，从而保证机房发生故障时，etcd的多数派分布与存储集群相同。scheduler是一个无状态的调度组件，通过etcd抢主，选出一个工作的实例，抢主成功的实例必然与etcd的多数派连通，从而保证调度的有效性。

异步复制和最终一致-双模raft

基于共识算法的分布式架构，能够提供很高的数据安全性，并且能够支持强一致，但代价是更高的写入延迟，并且最少要有3副本，如果业务场景只需要最终一致，并且能够容忍节点故障导致丢失少量数据，那么就可以用异步复制来代替共识算法，从而获得更低的写入延迟并可以只部署2副本。

下面将给出一种基于raft的方案。按照raft的设计，日志只有在commit成功之后，才能提交到状态机，已经异步复制出去但没commit的日志，对状态机是不可见的，对这里可以略做修改，增加一个实时状态机，每个成员写异步日志成功立刻提交到实时状态机，日志commit成功后提交到commit状态机，从而支持commit和async两种访问模式：

• CommitWrite：原版raft的写入模式，日志commit并在commit状态机生效后才返回成功
• CommitRead：原版raft的读取模式，从commit状态机读数据
• AsyncWrite：raft的leader写完异步日志后，立刻提交到本地的实时状态机，提交成功立刻返回成功
• AsyncRead：直接读实时状态机，允许读到没commit的数据

以下是具体方案：
先不考虑主从切换造成的日志冲突问题，把rocksdb作为实时状态机，而它的历史上的snapshot作为commit状态机。master每次commit的点不是根据日志复制情况动态决定的，而是在异步提交阶段就先提前选好commit的点，commit点的日志写入本地rocksdb后，立刻创建一个snapshot。当commit点复制到多数节点后，本次commit就只到commit点，哪怕commit点之后的内容也已经复制到多数节点，仍然放到后续commit中。commit成功后，就将可读的commit状态机换成最近commit成功的点对应的snapshot，这样从这个snapshot里读到的数据就都是committed。

双模raft.png

• 阶段(a)，日志1是commit点，并且已经复制到多数派成功commit，所以此时commit读状态机是snapshot_1
• 阶段(b)，日志2是普通日志，虽然复制到多数派，但最后成功的commit点在它前面，所以它不算commit成功，如果它是CommitWrite写入的，此时不能返回成功，但此时在S1或S2执行AsyncRead，可以读到日志2。日志3是commit点，所以创建snapshot_3，但此时日志3还没有在多数派成功commit，所以commit读状态机还是snapshot_1
• 阶段(c)，日志3成功复制到多数派并commit，所以snapshot_3替代snapshot_1成为commit读状态机

接下来我们要处理日志冲突问题，原版raft中没有实时状态机，只需要找到最后一条index和term一致的日志，然后把后面的日志都替换掉就可以了，但在上文的方案中，这些日志都已经提交到follower的实时状态机了，此时我们还需要将实时状态机也回滚，具体方案如下：关闭rocksdb的WAL，只用分布式日志，关闭自动flush，改由外部主动触发flush，每次flush前，锁住写入，将已经写入的日志的index记到rocksdb里，然后flush，这样就能保证rocksdb持久化的部分总是能够精准对应index。leader和follower发生日志冲突时，找到最后一条一致的日志，同时重启follower的rocksdb，重启时丢弃memtable，重启后从rocksdb记录的index开始追日志，如果rocksdb记录的index比最后一条一致的日志晚，那么就说明错误数据已经持久化，为了保证最终一致性，这个follower只能丢掉全部本地数据，从leader重新全同步一份，但这种情况发生的概率是非常低的。

上述方案能够同时支持commit和async两种访问模式，但为了高可用仍然需要最少3副本，如果业务场景只需要async模式，是否有办法只部署2副本呢？当然是可以的，市面上有许多主从异步复制架构的系统可以参考，但为了尽量复用已有的功能，我们继续对前文的raft进行修改，让它能够支持2副本部署的纯异步模式。要支持2副本系统的高可用，就要把“多数派”相关的行为全部去掉，raft和“多数派”相关的行为只有commit、选主和成员变更，前文的async模式完全不依赖commit行为，commit行为可以直接去掉，剩下的选主和成员变更可做如下处理：纯异步模式中，选主和成员信息由外部的中心调度模块决定，所有成员强制同调度模块指定的leader保持一致，只要调度模块最终能够把leader信息通知到所有成员，那么系统就能够达到最终一致。

多点写入

在跨区部署的场景中，写入的数据可能来自不同的区，如果写请求只能发往leader，那么就会有大量的跨区写请求，有些业务不希望承受跨区的延迟，希望就近写入成功后立即返回，并且在写入点能够立即读到写入成功的数据，之后存储系统内部自行达成最终一致。由于多点写入时并没有全局同步，所以刚写完本地的操作是没有全局的顺序的，全局同步时常用全局时钟+CRDT的方案解决写冲突，但这类方案需要数据模型层面保证乱序执行仍能达到最终一致，而本文的定位是分布式存储引擎，所以要提供一种全局执行顺序最终一致的方案，从而避免对上层数据模型的依赖。

具体方案如下：增加一层并行日志，这部分日志有多串并行的日志，每个写入点对应一串日志，每串日志序号严格依次递增。全局有个leader副本，发到leader的写入仍然执行前文的逻辑。除了leader外的每个写入点维护一个临时状态机，发到本写入点的写请求，写完并行日志中自己的那串日志后，立刻提交到本地临时状态机，提交成功后返回写成功。每个写入点会将自己的并行日志异步复制给其它节点，其它节点收到新的并行日志后并不会立刻重放这些日志，只有leader节点会主动重放收到的并行日志，leader会按照前文的异步写入流程，将重放的并行日志提交到全局日志中，然后再提交到状态机，其它节点通过复制全局日志重放并行日志，这样就能保证全局执行顺序的一致了。每个写入点的临时状态机需要周期性清理，具体过程如下：每个写入点每过一个周期，在后台创建一个新的临时状态机，从全局日志中自己的并行日志编号后开始重放本地自己的那串并行日志，重放完成后锁住写入，替换掉前台的临时状态机，这样已经通过全局日志提交到底层状态机的数据就从临时状态机清理掉了。

多点写入.png

上图的例子中，S1是leader，通过写入点S2写入的数据有3条，这3条日志的前两条通过并行日志复制到了S1，S1把来自S2的2条日志异步提交到了全局日志。S2收到的全局日志中，提交的并行日志S2的最后一条编号是1，此时重建临时状态机，只需要从S2_2开始重放，重放完成后就可以把前台的临时状态机1-3替换掉。

最终一致的跨区部署

基于共识算法的强一致模型，一般要求读主写主，部署方案已经在本文第一章讲过，但在异步模式下，主调方只要求最终一致，所以不必把请求发到主副本，这就要让客户端能够看到所有副本，并且自己选择要访问的副本。在所有网路和节点都正常的情况下，每个客户端都能连通所有副本，但当发生机房级网络故障时，不同客户端所能连通的副本是不同的，但如果每个客户端各自做连通性检测，会额外耗费比较多资源，一种合理的做法是，每个机房部署一个region_scheduler和etcd集群，用来做机房内视角的视图检测和存储、分发，每个region_scheduler从全局etcd中订阅集群配置、master等信息，并且以自己的视角检测所有副本，并将连通性视图存到同机房的etcd集群中，机房内的客户端只需要订阅机房内的etcd存储的集群视图，并根据视图做路由就可以了。而全局etcd可以根据机房故障的降级预案设定具体的跨区部署方案，全局etcd用来存储集群配置、副本分布、leader等信息，全局scheduler负责选主、数据迁移等工作。

分布式flush和compact

rocksdb是一个单机存储引擎，在存算一体的分布式架构中，每个存储节点都要维护本地的rocksdb实例，每个实例各自做flush和compact，这在多副本的场景下相当于浪费了大量计算资源做重复的事情。现在单机网卡的性能增长远远高于cpu，故而都能想到，只用一份计算资源做flush和compact，然后通过网络将结果复制到所有副本。现在rocksdb是无法通过接口支持这种方案的，想要实现必然要有侵入式的改造，这里基于上文的分布式日志描绘一种方案，能够做到文件级别的最终一致。

切imutable_memtable、flush、compact等会影响文件内容的行为，所有元信息都先提交到分布式日志，这样flush对应的日志范围、flush和compact涉及的文件名等，都能全局保持一致，然后每个副本根据自己的角色，决定是自己根据元信息计算，还是直接去同步结果文件。leader完成本地的计算后，将结果提交到分布式日志，触发新文件生效、垃圾回收。这里可以做一个进一步的修改，把imutable_memtable归入L0，每个imutable_memtable对应一个sst，L0不算持久化，flush行为由每个节点各自决定时机，不做全局同步，这样每个节点能够更灵活地控制自己的内存。

以上就是本文的全部内容。