Facebook Delos 中的虚拟共识协议

背景
Facebook 的软件系统栈一般包括两层：上层是数据平面，下层是控制平面。

facebook software stack

数据平面包括大量的服务，他们需要存储和处理海量数据。控制平面用来支撑数据平面，起到一些控制作用：调度、配置、命名、切片等等。控制平面通常是有状态的，比如控制的元信息，为了存储这些元信息，控制平面需要有自己的存储。控制平面对存储有以下要求：

容错：零依赖、可持久化、高可用。
丰富的 API：事务，范围查询，二级索引。
在 17 年的时候， Facebook 使用几种组件来充当控制平面的存储，包括：

MySQL：API 丰富，表达能力强，但是不支持容错。
ZooKeeper：容错，零依赖，但是 API 表达能力弱。
可以看出，他们都不能很好的同时满足控制平面对存储的需求。此外，作为单体架构，上述组件都比较难改造成同时支持容错和丰富 API 的系统。此外，还有一大问题，团队当时所面临的工期非常紧。最终，他们交出的答卷是 —— Delos。

架构
Delos 是一个基于共享日志（shared log）的控制面存储系统。db 层的实例通过 append 和 read 与共享日志进行交互，从而保持对外状态的一致性。根据近几十年的研究，使用共享日志作为 API，可以很好的向 db 层隐藏共识协议的大量细节。

design based sharedlog

读写流程

read write procedure via shared log

存储服务可以分为两层，db API 层和共享日志 runtime 层。如上图，以表格存储为例，在上层，DelosTable 负责提供表格存储的 API；在下层，DelosRuntime 负责共享日志的读写。则，一个典型的写流程如下：

客户端发起一个写请求
DelosTable 层将其转发给 DelosRuntime
DelosRuntime 将该请求序列化后追加到共享日志
各个服务器侦听到该追加后，读取其内容，以同一种顺序将其应用到本地状态机
在该架构中，有两个关键的设计点：

共享日志层提供了具有线性一致性保证的极简 API
基于该简明 API，上层可以方便的提供不同存储接口的实现
虚拟共识
到此为止，该架构设计看起来相当简单，但我们知道，复杂性只能被转移，但不可能凭空消失。可以看到，最复杂的共识协议被隐藏在了共享日志后面，于是问题随之而来：

我们需要如何快速实现一个满足共识协议的的共享日志组件？
随着技术的发展，如果我们之后想用更好的共识协议，该如何进行替换？
为了解决这些问题，Delos 提出了虚拟共识（Virtual Consensus）。通过抽象出一层虚拟共识协议，Delos 的共享日志组件可以快速复用现有实现，比如 Zookeeper；之后为了提高性能，也可以借助此该层对下层进行不停机迁移。

在 Delos 中，虚拟共识协议的承载层被称为 VirtualLog。对上，db 层基于 VirtualLog 层进行实现；对下，VirtualLog 被映射成一组物理共享日志，称为 Loglets。每个 loget 提供和共享日志同样的 API，外加一个 seal 命令。一旦被 seal，Loglet 便不再接受追加。为了存储 VirtualLog 逻辑空间到 Loglets 物理空间的映射，Delos 引入了新的组件：MetaStore。

MetaStore 是一个带版本的简单 KV 存储。通过存储的不同版本的 Loglet 的切换，VirtualLog 就自然的将流量打到新的 Loglet 上。如下图展示了 VirtualLog 向 MetaStore put 一个新版本（ver0 -> ver1）的映射信息，将流量无宕机的从 Zookeeper 切换到了 LogDevice 的过程。

virtualizing consensus via the VirtualLog

定制 Loglet
在满足基本需求后，为了进一步提升性能，Delos 想自己定制 Loglet，以满足以下特点：

简单：simple
快速：fast
容错：fault tolerant
NativeLoglet
只实现其中两点，比较容易；若要三者皆得，有点困难。Delos 通过分治策略，将其分解为两个组件：

MetaStore：进行容错
Loglet：专注性能
此时，所有一致性的来源便都移到了 MetaStore 之上。而 MetaStore 功能相对简单，只需保存空间映射，并提供容错的 reconfiguration 源语（即对映射进行操作，比如 loglet 切换），且 reconfiguration 是个低频操作。因此 MetaStore 的实现无需关注性能优化，只需要按照 Lamport 最初的 Paxos 进行实现即可，可以保证 MetaStore 实现的简洁性。

同时，将 Loglet 职能弱化，不再需要提供完全的容错机制，只需提供一个高可用的 seal 命令即可。如此一来，当一个 Loget 不可用时，VirtualLog 只需将其 seal，然后将流量切向其他 Loglet 即可。

据此，Delos 实现了新的 Loglet 实例——NativeLoglet 。

the NativeLoglet

直观感觉来说，NativeLoglet 类似一个弱化版的 LogDevice。其交互流程如下：

正常运行时，集群中某个 LogServer 充当 Sequencer
所有 DelosRuntime 发出的 Append 请求都要通过 Sequencer 定序后，追加到各个 LogServer
当 Sequencer 所在 LogServer 宕机后，DelosRuntime 直接向所有 LogServer 发送 CheckTail 请求，以 quorum 协议确定 tail
所有 DelosRuntime 都可以发起 seal 请求，对 NativeLoglet 进行 seal
注意，NativeLoget 中所有 LogServer 可以和 DelosRuntime 部署在一块（称作 Converged 模式），也可以单独部署（称作 Disaggregated 模式）。前者能够获取更好的本地读性能，并且让数据库实例和日志实例生命周期绑定。后者将数据库层和日志层分离，可以避免不同层的资源争夺，并允许各自按需伸缩。

converged vs disaggregated

下图是一个替换 NativeLoglet 后的性能提升对比：

NativeLoglet compare

StripedLoglet
为了进一步提升性能，在 VirtualLog 的抽象下，Delos 利用分片思想又造出了一种叫做 StripedLoglet 的实现。该实现在底层组合了多个 Loglets 实例，当 Append 请求到来时，将其 round robin 的打到各个底层 Loglet 系统中，从而极大提升性能。

此外，StripedLoglet 允许多个 DelosRuntime 使用不同策略进行并行 Append，并且允许暂时的空洞存在，之后使用类似滑动窗口的机制，进行捎带 ACK，从而进一步提升性能。

底层多个 Loglet 系统可以视情况共享一个集群或分散到多个集群.

striped loglet

The Last Thing：VirtualLog Triming
此外值得一说的细节是，VirtualLog 提供的 Trim 操作。得益于虚拟化的抽象，Delos 可以通过删除映射，将老的日志进行移除。当然，一种更好的做法是，将老的日志移动到 BackupLoget 的冷集群中，然后改变映射，对外提供一种无限日志的抽象，进而允许按年龄对不同日志段进行细粒度的存储控制。

另一方面，通过修改 MetaStore 中的映射，Delos 允许修改单个日志记录，对某些有问题的日志进行删除，以避免系统 hang 住或者反复重启宕机。这是之前的一致性协议无法做到的。