化繁为简，聊一聊复制状态机系统架构抽象

2022 年 8 月 04 日
本文字数：3856 字
阅读完需：约 13 分钟

作者：严祥光(祥光) 阿里基础产品团队

复制状态机让多台机器协同工作犹如一个强化组合，广泛应用于数据复制和高可用等场景，本文将从复制状态机模型出发，结合业界前沿研究分享该如何更好地抽象复制状态机系统的架构。

复制状态机（Replicated State Machine）是指多台机器具有完全相同的状态，运行完全相同的确定性状态机。它让多台机器协同工作犹如一个强化的组合，其中少数机器宕机不影响整体的可用性。

复制状态机是实现容错的基本方法，被广泛应用于数据复制和高可用等场景，一直是工业界和学术界的关注热点。越来越多的系统采用复制状态机来实现高可用，如 ZooKeeper、ETCD、MySQL Group Replication、TiDB 等，各种复制协议和系统架构的研究也层出不穷。如何抽象一个复制状态机系统的架构，使之更加通用和易用呢？本文从复制状态机模型出发，结合一些业界的前沿研究，总结复制状态机系统的架构抽象，在系统架构设计时具有一定参考意义。

一、复制状态机

复制状态机是指多台机器具有完全相同的状态，运行完全相同的确定性状态机。这多台机器组成一个整体对外服务，其中部分机器失效不影响整体的可用性。Raft 提出了如图 1 所示的复制状态机架构，通过复制日志来实现复制状态机，复制日志又使用共识（Consensus）协议来实现，保证日志的一致性。

图 1：Raft 提出的复制状态机架构

可以看到复制状态机的核心在于复制日志，共识协议是实现复制日志的具体方法。因此可以进一步抽象，如图 2 所示，将复制状态机抽象成两部分：上层的业务状态机（State Machine）和底层的复制日志（Replicated Log）。上层业务状态机负责具体的业务逻辑，无需关心日志复制的细节，在需要复制日志时直接向底层的复制日志模块写入日志，复制日志模块使用共识协议将日志复制到其它节点，并在日志提交后通知上层业务状态机执行日志中的操作。共识协议细节隐藏在下层的复制日志中，业务逻辑和共识协议可以独立演进，互不影响，并且复制日志可以做成通用模块，不同的业务状态机可以复用同一套复制日志的代码。

图 2：将复制状态机抽象为上层的业务状态机与底层的复制日志

图 2 所示的抽象已经比较通用了，也是目前业界很多的复制状态机系统采用的架构抽象。这种架构中复制日志模块以库的形式链接到业务状态机的程序中，解耦的不是很彻底，在升级维护以及动态扩展上有诸多不便，也不太适应云原生的架构。

那么复制状态机系统还能否更进一步的抽象呢？考虑图 2 中的复制日志模块，它本质上是使用复制在多个节点间实现了日志共享，它抽象出来的实际上是一个共享日志的语义。因此我们可以将复制日志进一步的抽象成共享日志，如图 3 所示，业务状态机可以向底层的共享日志层写入新的日志，并可以从共享日志层读取日志来执行。业务状态机和共享日志可各自独立扩展，独立升级维护。

图 3：将复制状态机抽象为上层的业务状态机与底层的共享日志

图 3 所示的存储计算分离的架构使得共享日志层变成了一个存储系统，可以使用很多存储系统中的技术，仿佛打开了一扇新世界的大门，实事上，有关这些抽象在 Facebook Delos 的两篇顶会论文上面有详细阐述 [1] [2]。我们在共享日志章节描述共享日志层的抽象，在业务状态机章节描述业务状态机层的抽象。

二、共享日志

共享日志提供日志读写服务，业务状态机通过共享日志来同步状态，保证状态一致。为了保证复制状态机的高可用性，共享日志需要具备高可用性。共享日志本质上是一个 Append Only 的存储系统，可以借鉴 GFS、HDFS、盘古等存储系统的设计，业界已有一些成型的系统，典型的如 Apache 的 BookKeeper，还有 Facebook 的 Delos 系统中的虚拟共识（Virtual Consensus）等。

2.1 Apache BookKeeper

Apache BookKeeper 是一个高扩展、强容错、低延迟的在线日志存储系统，提供了持久性、复制以及强一致的特性，基于 Apache BookKeeper 可以快速构建可靠的在线服务。Apache BookKeeper 中可以动态的创建、删除日志，称为 Ledger。

图 4：Apache BookKeeper 架构

如图 4 所示，Apache BookKeeper 包含三个核心组件：Client、Metadata Store 和 Bookie。Metadata Store 负责保存 Ledger 和集群相关的元数据，Bookie 则是系统的存储节点，负责 Ledger 里 Entry 的存储，Client 则负责提供访问系统的接口。Ledger 是 BookKeeper 的基本逻辑单元，包含了一系列连续的 Entries，BookKeeper 可以保证 Entry 顺序写入，并且最多被写入一次，Entry 一旦被写入将不能被修改。一个 Ledger 被划分为多个 Fragment，每个 Fragment 包含一组连续的 Entries。Bookie 负责 Ledger 的存储，实际是 Ledger 的 Fragment 的存储。每个 Bookie 保存了一个 Ledger 的一部分 Fragment，每个 Fragment 包含了一组连续的 Entries，每个 Ledger 同一时刻只有最后一个 Fragment 能被写入，当该 Fragment 写入失败的时候，会重新生成一个新的 Fragment 继续写入。每个 Fragment 会被复制到多个 Bookie 上以提供容错能力，这一组 Bookie 被称为 Ensemble。

2.2 Delos 中的虚拟共识

Delos 提出了虚拟共识的概念，隐藏共识的细节，并提出虚拟日志（Virtual Log）的抽象，获得了 OSDI'20 的 Best Paper。Virtual Log 是一个 Append Only 的日志，提供 append/checkTail/readNext 等接口，并且进一步支持共识协议的热升级，这一点是 Apache BookKeeper 所不具备的。

Virtual Log 的抽象使得上层只用假设该 Log 里的每一个 Entry 都已经复制并持久化在不同的节点上，不用关心背后使用哪种共识协议实现的，甚至可以多种共识协议同时存在。一批连续的 Log Entires 被映射成一组物理共享日志，称为 Loglet，对应一种共识协议或者使用某种共识协议实现的 Log 存储系统。

Loglet 提供与 Virtual Log 同样的接口，外加一个 seal 接口。一旦被 seal，Loglet 便不再接受新的追加写入，需要切换到一个新的 Loglet 上才能继续追加写入。Virtual Log 的逻辑空间到 Loglets 的物理空间的映射保存在一个单独的 MetaStore 服务中，在进行共识协议替换的时候，只需修改 MetaStore 中的映射，切换存储的位置即可。MetaStore 是一个带版本的 KV 存储。通过存储的不同版本的 Loglet 的切换，Virtual Log 就自然的将流量打到新的 Loglet 上。

图 5：Delos 中的虚拟共识

通过引入虚拟共识的抽象，使得 Loglet 不再需要提供完全的容错机制，简化了 Loglet 的实现，当一个 Loglet 不可用时，Virtual Log 只需要将其 seal，然后切换到其他 Loglet 上继续写入。Loglet 只需要提供一个高可用的 seal 接口即可，大大简化了 Loglet 的实现，避免了实现 Paxos/Raft 等共识协议的复杂性。虚拟共识的抽象也便于系统的长期演进，可以不断的演进新的 Loglet 替换掉老的 Loglet，以获得更高的性能、更低的成本等。实际上 Delos 一开始直接使用 ZKLoglet 快速上线，后面研发了 NativeLoglet 替换掉 ZKLoglet，获得了十倍的性能提升。

三、业务状态机

业务状态机负责实现具体的业务逻辑，跟具体的业务逻辑密切相关，乍一想好像没法再进行抽象，其实不然。Facebook 的 Delos 系统在 SOSP'21 提出了 Log-Structured 协议，一种基于共享日志的复制状态机的实现，基于该协议可以在不同的节点间一致地复制其应用状态。

Log-Structured 协议提供了一组接口，应用通过该接口与协议引擎进行交互。使用 IEngine 接口，应用可以通过 propose 接口提议一个 Entry 到共享日志；registerUpcall 注册一个 Applicator 的实例从共享日志接收新的 Entry，一旦有新的 Entry 写入，该 Applicator 实例的 apply 接口将被调用；sync 接口确保所有在共享日志中的 Entry 都已经通知给了应用，并返回一个只读视图以便读取最新状态。应用则可以将其本地的状态保存到持久化的存储系统中，如 RocksDB，论文里将其称为 LocalStore。

图 6：Log-Structured 协议接口

Log-Structured 协议是一个可堆叠的复制状态机。如图 7 所示的例子，每一个 Engine 都像是下面一层 Engine 的应用，上层的 Engine 会调用下层 Engine 的 propose/sync，下层 Engine 则会调用上层 Engine 的 apply。每一层 Engine 都会实现图 6 中 IEngine 接口，并且在实现中调用下一层的接口。同时，每一层 Engine 都可以直接访问 LocalStore 从而持久化其需要的状态。当一个 Entry 被 propose 到某个 Engine 时，该 Engine 会在 Entry 里加上自己的 Header，然后 propose 到下面一层 Engine。同样地，当下面一层 Engine 调用其 apply 时，会从 Entry 里解析出来自己的 Header 并更新 LocalStore，然后再调用上面一层 Engine 的 apply。最上层是具体的应用，提供具体的应用接口给用户。最下面的 Engine，称之为 BaseEngine，是专门和共享日志交互的 Engine。

图 7：堆叠的 Engine 之间的交互示例

通过这种堆叠的模式，通常新加一个功能就是加入一个新的 Engine 到 engine stack 里，一些通用的 Engine 可以在不同的业务状态机中复用，可以快速开发出不同的业务状态机。实际上 Delos 为了实现不同需求的数据库实现了 9 种 Engine，通过这些 Engine 的组合快速构建了不同的数据库，如提供 MySQL 语义的 DelosTable，提供 ZooKeeper 语义的 Zelos，提供队列服务的 DelosQ 等。

四、总结

本文介绍了复制状态机系统的架构抽象，首先复制状态机可以抽象成上层的业务状态机和底层的共享日志，然后分别介绍了共享日志和业务状态机的架构抽象。共享日志在业界已经有不少成熟的系统，并且已经抽象的比较通用了，但业务状态机的架构抽象的案例还较少，希望在未来能看到更多的关于业务状态机的架构抽象，能够更好的复用代码，快速实现新的业务状态机。