SIGMOD21-Foundationdb

由于Foundationdb是09年的产品，后来被苹果收购之后，历经闭源又重新开源。其相关的设计细节也都已经披露，这篇文章的价值应该也在于提升在学术圈的影响力。

Foundationdb采用了分层的设计，下图是Foundationdb的架构图，它由控制平台（Control Plane）和数据平台（Data Plane）组成。控制平台负责元数据的管理并通过Active Disk Paxos保证其高可用，数据平台又由transaction management system（TS）、log system（LS）以及storage system(SS)组成，各个组件之间支持独立扩展。

负责元数据的管理，比如集群配置等。它主要由Coordinators组成，构成paxos组，并选举一个ClusterController负责管理整个集群。

ClusterController创建三个进程，分别是Sequencer，DataDistributor和Ratekeeper，他们都是单点的，当crash或者fail时，重新创建即可。其中Sequencer负责为每个事务分配read和commit version；DataDistributor监控StorageServers是否失败，以及在保持StorageServers中负载均衡；Ratekeeper为集群提供过载保护。

数据平台

它由TS、LS以及SS组成，TS和SS是分离的，支持独立扩展。

• TS：执行事务处理，由Sequencer, Proxies和Resolvers组成，它们都是无状态的；

• LS：为TS存储WAL，它由一系列的LogServers；

• SS:  数据存储，由多个StorageServer组成，为客户端提供读操作，SS的存储引擎是SQLite。在FDB中，采用的是range sharding机制，将数据分配到不同的StorageServer。

Proxies为客户端提供MVCC version，并负责事务提交。Resolvers用于检测事务之间的冲突。Sequencer为事务提供read和commit version。Sequencer就是以前版本中master的概念，换了叫法。

客户端能直接从StorageServer读数据，能实现读性能的持线性扩展。写性能扩展通过增加Proxies, Resolvers和LogServers来完成。因此，这里MVCC信息存储在SS，而不是TS。由于只执行有限的元数据操作，Coordinator等单点组件不会成为瓶颈。

事务处理

事务处理的流程：

• 客户端向Proxies发起请求，获取read version；

• Proxies向Sequencer询问read version，该version不能小于之前提交的任意commit version，获取之后返回给客户端；

• 客户端根据read version从StorageServers读取相应的值；

• 客户端的写会缓存在本地，在commit时，客户端将事务数据发送给proxy，等待proxy的向量（commit或者abort）；

proxy进行commit的过程：

• proxy询问Sequencer获取commit verson（大于目前的read version以及任意的commit version）；

• 然后proxy将事务信息发送给Resolvers，Resolvers利用OCC解决并发冲突；

• 最后将无冲突的数据发送到LogServers，进行持久化操作。当proxy收到所有指定的LogServers的回复时，表示已经全部落盘。将commit version发送给Sequencer，之后，StorageServers异步的从LogServers进行pull新更改的数据。最后响应给客户端表示已commit。

除了上述之外，还支持read-only transactions and snapshot reads，可以在本地提交事务，不需要和集群中的其他节点通讯，十分方便。在进行事务提交时，也做了一些优化，为了减少事务commit开销，Proxy会将客户端的事务请求批量进行提交，并且批量提交的size可以根据系统状况动态调整。

Transaction System Recovery

FDB将redo log和undo log从recovery解耦，在recovery期间，不做checkpoint、undo和redo操作。在FDB中，StorageServers异步的从LogServers中pull数据，并在后台apply。

恢复流程：

• 当发现failure时，Sequencer从coordinator中读取之前事务系统的状态，并对其加锁；

• sequencer进行恢复操作，主要包括LogServers的信息，禁止它们处理事务。sequencer会重新创建Proxies，Resolvers和LogServers，sequencer写入当前的事务信息；

• Sequencer可以开始接受新的事务提交。

也就是说，不同于以前的多数派机制，当出现failure时，clustercontroller会进行系统重配置，全部创建新的进程来恢复事务系统。

在FDB中，Proxies、Resolvers是无状态的，因此不需要额外的恢复操作。LogServers保存了大量已commit事务的log，因此，其恢复至关重要。

首先介绍几个概念：Recovery Version (RV)， Durable Version (DV)，Known commit versio（KCV），epoch’s end version（PEV），其中DV表示持久化的最大LSN，KCV表示Proxy已提交的最大LSN，epoch相当于系统重配置的次数，因此PEV代表该epoch阶段的commit version。

假定会有m个LogServers需要恢复，Sequencer会将（PEV+1，RV）之间的数据从old LogServer复制到目前的，其中PEV等于m个LogServers中KCV的最大值，RV等于所有DV中的最小值。

Replication

FDB采用了多种复制策略进行容错：

• Coordinators之间采用Active Disk Paxos协议保证HA；

• LogServers采用同步复制保证HA；

• StorageServers通过异步复制保证HA，在StorageServers层，通过host和process两个层次构造复制组，并且要保证每个process组属于一个host组，因而只有当host组中的所有host都fail时，数据才会丢失，极大的提升了数据的可靠性。这里的组类似于copyset的概念。

SSI支持

FDB通过OCC和MVCC实现SSI，OCC来检测事务冲突，MVCC实现SI。

5S事务支持

只支持5s的事务，目的是为了限制事务系统或者存储服务器的内存使用。之所以选择支持5s，是因为该团队认为它对大多数的OLTP事务是足够的，如果超过5s限制，说明应用正在做低效率的事情，比如使用了串行读。针对超过5s的事务，FDB会将其切成多个小事务来完成相关操作。

确定性的测试框架

所有非确定的部分都被抽象出来，比如网络，磁盘等，可以模拟这些不可靠的组件，并可以确定性的重复执行。为了避免多线程带来的不确定性，采用的单线程的方式模拟集群并进行测试。为此FDB在C++的基础上开发了Flow语言。

虽然号称Newsql，但是目前FoundationDB由于对SQL支持不够，严格来说只是仍然是一个支持ACID的nosql键值存储系统；类似TIDB，采用分层的结构，有比较好的扩展能力，可以支持多种数据模型以及其他功能；使用OCC+MVCC实现SSI的系统，应该是比较早实现该功能的数据库系统；其确定性的仿真框架能够很好的模拟各种故障情况；但也有局限，比如只支持5s事务，key和value的size有限制等。

[1]https://github.com/apple/foundationdb/blob/master/design/recovery-internals.md

[2] https://apple.github.io/foundationdb/architecture.html

[3] https://apple.github.io/foundationdb/testing.html

[4] Jingyu Zhou et al.FoundationDB: A Distributed Unbundled Transactional Key Value Store.SIGMOD,2021.