网络知识 娱乐 化繁为简,聊一聊复制状态机系统架构抽象

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

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

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

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

复制状态机(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等。

四、总结

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

参考阅读

[1] Virtual Consensus in Delos

https://www.usenix.org/system/files/osdi20-balakrishnan.pdf

[2] Log-structured Protocols in Delos

https://maheshba.bitbucket.io/papers/delos-sosp2021.pdf

[3] Durability with BookKeeper

https://dl.acm.org/doi/10.1145/2433140.2433144