SIGMOD21 FoundationDB: A Distributed Unbundled Transactional Key Value Store

FoundationDB是一个开源的事务性键值存储，它是最早将NoSQL体系结构的灵活性和可伸缩性与ACID事务(又名NewSQL)的强大功能结合起来的系统之一。FoundationDB采用分离架构，将内存事务管理系统、分布式存储系统和内置分布式配置系统解耦。每个子系统都可以独立地进行供应和配置，以实现所需的可伸缩性、高可用性和容错特性。FoundationDB独特地集成了一个确定性仿真框架，用于在无数可能的故障下测试系统的每个新特性。这种严格的测试使FoundationDB非常稳定，并允许开发人员快速引入和发布新特性。FoundationDB提供了一个最小的和精心选择的特性集，这使得一系列不同的系统(从半关系数据库、文档和对象存储到图形数据库等等)可以作为层构建在上面。

• Divide-and-Conquer：为系统中不同进程赋予不同的角色，可以通过扩展每个角色的进程数量来扩展，分离了客户端读和客户端写(即事务提交)的伸缩性。
• Make failure a common：对于分布式系统来说，Failure是一种常态，而不是例外。在FDB的事务管理系统中，通过recovery路径来处理所有的failure，而不是修复所有可能的故障场景，事务系统在检测到故障时主动关闭。因此，所有的故障处理都减少到一个recovery操作，这成为一个常见的、经过良好测试的代码路径。只要恢复是快速的，这种错误处理策略是可取的，并通过简化正常事务处理而获得好处。
• Fail fast and recover fast:为了提高可用性，FDB努力最小化平均恢复时间(Mean-Time-To-Recovery, MTTR)，其中包括检测故障、主动关闭事务管理系统和恢复的时间。在我们的生产集群中，总时间通常少于5秒。
• Simulation testing：FDB依靠一个随机的、确定性的仿真框架来测试其分布式数据库的正确性。因为模拟测试既有效又可重复，它们不仅暴露了深层次的bug[46]，而且还提高了开发人员的生产力和FDB的代码质量

FDB集群有一个用于管理关键系统元数据和集群范围编排的控制平面，以及用于事务处理和数据存储的数据平面。

控制平面负责在协调器上持久保存关键系统元数据，即事务系统的配置。 这些协调器形成一个disk Paxos 组。

• ClusterController 监控集群中的所有服务器并启动三个单例进程：Sequencer、DataDistributor 和 Ratekeeper，如果它们失败或崩溃，则会重新启动。
• DataDistributor 负责监控故障并在 StorageServer 之间平衡数据。 Ratekeeper 为集群提供过载保护。
• Sequencer 为每个事务分配一个读取版本和一个提交版本
• Proxy为客户端提供MVCC读取版本并编排事务提交，解决程序检查事务之间的冲突。logserver充当复制的、分片的、分布式持久队列，其中每个队列为StorageServer存储WAL数据。
• SS由许多用于服务客户端读取的StorageServer组成，其中每个StorageServer存储一组数据分片，即连续的键范围。StorageServers是系统中的大多数进程，它们一起形成了一个分布式b-树。目前，每个StorageServer上的存储引擎都是SQLite的修改版本，增强了范围清除速度更快、将删除延迟到后台任务，并添加了对异步编程的支持。

客户端事务首先联系其中一个代理获取一个读版本(即时间戳)。然后Proxy请求Sequencer提供一个保证不少于之前发布的事务提交版本的读版本，这个读版本被发送回客户端。然后，客户机可以对StorageServers发出多个读操作，并获得该特定读版本的值。客户端写入在本地缓存，而不与集群联系。在提交时，客户端将事务数据(包括读和写集(即键范围))发送到一个Proxy，并等待来自Proxy的提交或终止响应。如果事务不能提交，客户端将选择重启事务。

Proxy通过三个步骤提交客户端事务。首先，Proxy与Sequencer联系，以获得一个大于现有读版本或提交版本的提交版本。Sequencer以每秒100万个版本的速度来选择提交版本。然后，Proxy将事务信息发送到范围分区的Resolvers，这些Resolvers通过检查读写冲突来实现FDB的乐观并发控制。如果所有resolver返回时没有冲突，则事务可以继续到最后提交阶段。否则，Proxy将将事务标记为已中止。最后，提交的事务被发送到一组logserver以实现持久性。事务在所有指定的logserver回复Proxy后被认为是提交的，Proxy报告提交的版本给Sequencer(确保以后的事务的读版本在这个提交之后)，然后回复给客户端。同时，StorageServers不断地从LogServers拉出日志，并将已提交的更新应用到磁盘。

除了上述读写事务外，FDB还支持只读事务和快照读取。FDB中的只读事务既可序列化(在读版本时发生)又具有性能(MVCC)，客户端可以在本地提交这些事务，而无需与数据库联系。这一点尤其重要，因为大多数事务都是只读的。FDB中的快照读通过减少冲突有选择地放松事务的隔离属性，即并发写不会与快照读发生冲突。

Support Strict Serializability

FDB通过OCC和MVCC的结合实现了SSI (Serializable Snapshot Isolation)。事务 从Sequencer获取其读版本和提交版本，其中在 启动时，确保读版本不小于任何已提交版本，提交版本大于任何现有的读或提交版本。这个提交版本为事务定义了一个串行历史记录，并用作日志序列号(Log Sequence Number, LSN)。因为 观察所有之前提交的事务的结果，所以FDB实现了严格的序列化。为了确保LSN之间没有间隙，Sequencer会返回之前的提交版本(即之前的LSN)和提交版本。代理将LSN和以前的LSN发送给解析器和日志服务器，以便它们可以按照LSN的顺序串行地处理事务。同样，StorageServers也从LogServers中提取日志数据，增加lsn。

Recovery

Recovery过程从检测到failure开始，重建新的事务系统，直到所有旧的LogServer不再需要时终止。在每个epoch中，Sequencer首先读取之前事务系统的配置，同志LogServer停止接收事务，创建新的Proxies，Reslovers以及LogServer。在新的事务系统创建之后，Sequencer更新事务系统配置。

因为Proxy和Resolver是无状态的，所以它们的恢复不需要额外的工作，logserver保存已提交事务的日志，需要确保所有之前提交的事务都是持久化的，并且StorageServers可以检索。新的LogServer需要从旧的LogServer中获取需要重放的日志，具体如下图所示

LogServer保存了

1. KCV即Proxy已经提交的最大LSN（在此之前的事务都已经提交）
2. DV即LogServer已经持久化的LSN

PEV即所有LogServer KCV中最大的一个（怎么保证之前的日志已经被StorageServer处理完成），RV即DV中最小的值。两者之间的日志需要从旧的LogServer中拷贝。当Sequencer接收新的事务时，会将RV通知StorageServer，StorageServer将会回滚比RV更大的事务。

Simulation Testing

上图说明了FDB的模拟器过程，其中抽象了所有的不确定性和通信来源，包括网络、磁盘、时间和伪随机数生成器，可以确定性复现结果。FDB是用Flow编写的，这是对c++的一种新的语法扩展，添加了类似于异步/等待的并发原语。

总体来看，FDB的特点在于解耦架构，所有failure都通过recovery过程处理，以及全数据库Simulation。但解耦的架构将导致涉及的网络交互会较多，适用于冲突较小的负载，写入的数据短时间内不会被访问到。