FoundationDB论文解读 A Distributed Unbundled Transactional Key Value Store

FoundationDB一个具有事务语义的分布式KV存储，是最早的一批把NoSQL和分布式事务结合起来的数据库系统，它提供了NoSQL的高扩展，高可用和灵活性，同时保证了serializable的强ACID语义。

这个数据库很有意思，其对于事务/高可用/容错的设计都非常独特，概括来说，整体采用了松耦合的模块化设计，系统分为了3个组件：

• in-memory 事务管理
• 分布式的storage管理
• 分布式的system configuration管理

三个组件各自独立部署 + 配置，因此按照需求，各自provision来保证组件的可用性/扩展性。

另一个独特的地方是，它先用了2年时间开发完成了一套基于deterministic simulation的测试框架，然后才开始做的db产品。这个测试框架将系统中所有非确定性因素用mock模块来模拟，并可注入确定性的错误或事件，使得系统的运行完全可控且可复现，更容易发现bug和调试，也帮助提升新feature的开发速率。

从设计原则上，产品追求的是：提供最小的功能集合，即一个事务语义的分布式KV存储，并不提供其他功能如query language,data model,index,schema。。。这样反而为上层提供了灵活性，可以基于FDB构建各种类型的分布式系统。（Apple cloud/Snowflake/CouchDB...）

首先强的事务语义和最简单的data model对于上层的应用开发来说会更加方便，早期NoSQL为了扩展性牺牲了事务能力，只保证最终一致性，因此应用层必须对并发控制进行处理，大大增加了开发复杂度。而FDB则加上了强的串行化事务语义，因此上层应用可以方便的构建类似全局二级索引/唯一性约束等功能，且由于底层只是KV，所以很灵活，可以存储各种类型的数据，semi-structure/graph…

从FDB的角度，它对上层只提供，有序+事务+KV存储的抽象。

基本概念

• 总体的架构是松耦合的，分为control plane + data plane

1. control plane负责系统的管理和监控，使用active disk paxos   来存储系统metadata。
2. data plane负责用户+系统数据的存储，其中事务管理系统负责写路径，storage系统负责读路径，是解耦的，可以各自独立扩展。

• 利用OCC + MVCC的策略来实现串行化事务。
• 使用failure -> restart -> recovery的策略来处理failure，即快速失败快速恢复。
• 采用了类似Aurora的log is database的思路，对log进行多副本同步复制，是一种特例的quorum， 所有副本都同步落盘 ，才认为提交成功，才能返回客户端！因此f+1个副本，最多可允许f个失效。

设计

paper中主要讨论了transaction/replication/fault tolerance(recovery) 三个方面

设计原则

• 模块化分割，尽量 细分 且模块之间相互解耦

例如事务系统内，其提交(write path)和读取(read path)是可以独立扩展的，系统中根据事务功能的不同，区分了很多角色（timestamp管理,冲突检测,提交的协调,logging..），每个角色也可以独立配置和扩展。而全局来看也把各个功能尽量拆分开来，减少耦合。

• 快速failure快速恢复

与一般的数据库系统不同，它处理各种类型的failure方式都一致，就是发现failure后重启整个事务系统，通过recovery机制来修复failure，因此必须做到快速检测和快速恢复才行。生产环境中从出现问题->发现->主动shutdown->recovery，一般在5s以内。

• 确定性模拟测试系统

提升质量，使得bug可被reproduce。

对外接口是典型的key/value(get/set/getrange..)，事务机制是典型的OCC，开始时基于系统的快照做读取+修改，所有修改在client本地缓存，结束时带着read set/write set发起提交。由于需要缓存修改，系统对于Key/Value/事务的大小都是有限制的，这和client的缓存+in-memory的事务管理系统的缓存机制有关。

整体架构

存储系统一些关键的metadata，通过Active Disk paxos group保证高可用性，并选举出单个的Cluster Controller，controller会创建另外几个单实例进程：Data Distributor，Rate Keeper，Sequencer

Sequencer是事务系统的领头节点，它负责创建事务系统其它服务进程

Data Distributor 负责监控Storage Server的集群状态，并做负载均衡

Rate Keeper 其流控作用，避免系统overload

FDB本身针对的负载类型是OLTP + 小事务 + 读为主 + 高并发但低冲突。其内部的3层也都是松耦合的。

TS层负责in-memory内存处理，由Sequencer领头，创建Proxy / Resolver，整个TS层是无状态的，便于发生failure时，快速整体重启。 （如果Sequencer重启了，timestamp怎么单调递增？）

LS层负责WAL的存储，按照key range做分片存储，且每个分片有多个副本。

SS层负责实际数据的存储，和LS的分片对应，每个分片有自己的WAL日志，底层目前使用的是SQLite，后续会考虑Rocksdb。

从上面的架构图可以看到，读写路径是分离的，TS层+LS层和write path相关，而SS层和read path相关。这是其设计的核心思想，将功能尽可能细分为不同role，由不同服务进程负责，不同role各自独立配置和扩展。例如如果想提高读吞吐，扩展storage server，如果想提高写吞吐，扩展Resolver/proxy/LS。

boostrap/reconfiguration

可以看到FDB内部各个组件是有着相互的关联的：

Coordinator中存储着系统核心metadata，包括LS Server的配置，LS Server中则存储了Storage Server的配置。

运行中，Controller监控Sequencer，Sequencer监控Proxy / Resolver / LogSevers的状态。

系统启动时，Coordinator会选举出Controller，后者启动Sequencer，Sequencer则启动另外3组进程，然后从Coordinator中获取老的LS的配置，并从老的LS中获取SS的配置，利用老的LS执行必要的recovery过程，完成后老的TS系统就可以退休了，新的LS的信息写入Coordinator中，系统完成启动，开始对外提供服务。

当TS系统发生failure或者配置变化时，Sequencer检测到后会主动shutdown，Controller检测到后会重启新的Sequencer从而形成新的TS，新的Sequencer会阻止老的TS再提供服务，然后走和bootstrap类似的recovery流程即可。

为了标识不同的TS系统，引入了epoch的概念，任何时候新老TS交替，epoch就要+1。

事务管理

采用了比较经典的OCC套路，思路和SQL Server Hekaton 的并发控制有些类似：

客户端连接Proxy，获取读时间戳，Proxy向Sequencer获取read version返回client，client利用read version从storage server直接读取目标版本数据，在本地做修改并缓存，事务提交时带着read set+write set发给proxy，proxy首先向Sequencer获取commit version，然后发送Resolver做冲突检测，检测失败则返回client，client可以重试（所以要小事务）。

Resovler也是根据Key range分片启动多个实例，这样可以并发做冲突检测。

FDB实现的是可串行化事务，commit version的顺序就是事务提交顺序，因此可以认为事务需要在commit点瞬时完成，冲突检测就是判断在 [read version -> commit version ]之间，是否并发事务写入了冲突的数据。从下图可以看到，理论上Ti是在commit ts那一时刻瞬间完成了事务，因此Ti读取到的也应该是在commit ts时刻系统的快照，而在Ti start -> Ti end这个过程中，其他事务Tj修改了Ti读取的数据，read ts时刻看到的快照与commit ts时刻的就不再相同了，串行化被破坏。

Resolver的冲突检测算法：

为了检测，其内部使用skip-list维护一个LastCommit结构，即修改的key range -> commit version的一个映射，记录某个key range最近一次的提交version，便于找到对某个key/key_range，最近一次commit_ts是否在当前事务的[read_ts, commit_ts]之间（即冲突），不冲突即用当前事务commit version更新LastCommit。

这里有一个问题，由于是多个resovler并发检测冲突，可能一些resolver局部认为是无冲突的，因此更新了自己维护的LastCommit结构，导致后续不应该失败的事务发生冲突(false-positive）。FDB认为这不是大问题，首先它面向多租户应用，冲突较少，一般事务都会落入一个resovler。此外即使失败后重试，新的ts的read version增长后，超过这个伪提交事务的commit ts即可。

除了read-write事务，还有read-only事务，只获取read version从SS读取数据，然后client直接提交就可以，等同于在read ts瞬时完成，不需要检测冲突。 此外在read-write事务中还允许做放松串行化要求的snapshot read，这种read不放入read-set中，不做冲突检测。

所有Resovler返回成功时，Proxy认为事务可以提交，向LogServer发送log做多副本同步复制，所有副本的日志都落盘后，Proxy认为事务提交成功，返回给客户端。同时Storage Server异步的从LS获取log entry并apply，即使log entry还没有落盘也会apply，采用这种激进策略来保证data和log之间的低延迟。

可串行化的并发控制使得log entry之间形成了严格的顺序，大大简化了log管理的逻辑，可以用version来表示LSN，针对每个key，它所面对的实际是一个有序的log entry队列，依次apply就可以了。

Proxy写log的流程也比较特殊：

Proxy本地有缓存一份key range -> SS的映射关系，这样就可以知道要写入哪些SS和对应的LS。例如上图中，LS1 + LS4是要写入的LS，因此把这个事务的log都写入（形成副本），此外由于是3副本，再额外写一个LS，其余的LS也要发送，但只传递Log Header，其中包含的最主要信息是当前的LSN和Proxy上的KCV，即本Proxy已知的最大已提交事务，LS收到后会更新自己本地的KCV，这个KCV在recovery时会使用。

LS上的WAL -> SS和apply redo并不在commit path上，是异步持续完成，因此可以说FDB也遵循了”log is database”的思想。这种方式client做read一般可以读到目标version的数据，如果不行就等待或者向其他副本请求，都不行的话，可以超时后重试。

由于是异步apply，可以做batching，将一批更新缓存在SS上，批量刷盘提高IO效率。但这里也有个问题，由于LS中在内存中（未提交）的entry也可能被apply，因此SS是有脏数据的，在recovery时要rollback。

FDB做恢复是最为与众不同的，由于其基于recovery来做failure处理，因此recovery是常规操作，需要快速恢复。

由于redo log apply是在后台持续进行的，因此本质上它将redo apply从recovery中解耦出来，等于持续在checkpointing，在recovery期间不需要做redo/undo apply，只是确认当前的log序列需要恢复到哪个位置即可！！后续基于log -> data的过程仍然是异步。这保证了recovery的速度。

具体流程：

发现failure后，老Sequencer退出，新Sequencer启动，并从Coordinator获取老的TS的配置信息，包括老的LS的位置等，同时给Coordinator加个全局锁，避免并发recovery，然后关闭老的LS，禁止接收新的log写入，开始恢复，恢复完成后启动TS系统接收用户请求。

Proxy和Resolver都是stateless的，直接重启就可以，只有LogServer有log信息，恢复如下：

由于在日常提交写日志时，Proxy会把本地记录的KCV广播给所有LS(见持久化一节)，LS中就记录了自己见过的最大的KCV。选取所有LS中KCV的最大值，在这个值之前的事务，其日志已经完全复制并落盘，且已告知Proxy，可以作为上一个epoch的终点，称为PEV（previous epoch’s end version）。

同时每个LogServer都记录了本地已持久化的version (DV)，选取所有DV中的最小值，作为Recovery Version(RV)，在PEV -> RV之间的日志，已持久化且不在内存中，但不确定是否已提交（因为proxy没有该信息，可能崩溃的那个没持久化），因此这部分需要进行恢复(redo)，而 > RV的log entry，肯定没有多副本都持久化，因此不可能提交，这部分要undo。

因此整个的recovery流程，就是将老的LS中的[PEV+1 , RV]之间的部分，copy到新的LogServer中并完成log复制即可。这样这部分事务已成功排好队，后续在开始接受用户请求前，先启动一个事务将RV之后的log对应的数据rollback，然后就可以处理用户请求了（log已准备好继续append）。

复制

系统中不同组件，复制策略不同

1. Metadata，存储在Coordinator中的，通过Paxos变体实现复制，因此适用于quorum策略。
2. Log，存储在LogServer中，是全量同步复制，因此允许f个失败 (f+1个副本)。
3. Storage，由于Log已同步复制，存储就是异步复制到f+1个副本

为了做fault tolerent，storage的各个副本是有一定策略来分布到各个fault domain的，防止多个副本同时失效的情况，这个和Spanner的调度策略类似。

另外2个小的优化：

1. Transaction batching

在Proxy上为了减少与Sequencer/LS的交互成本，可以把不冲突的并发事务合并，获取同一个commit version，并一起下发到LogServer。相当于group commit。

这个策略是可以自适应的，在系统负载不大时，为了减少延迟，可以减小patch大小，当系统重负载时，为了保证吞吐则可以加大patch。

2. Atomic operations

对于一些只写不读的操作，其相互之间可以不做冲突检测，直接获取提交时间戳就可以，这对于某些counter类型的操作会提高效率，因为避免了从storage的一次读，也避免了resolve confilct。

Failover

对于跨Region的高可用和failover，采用了一种巧妙的策略：

在一个region内，建立多个AZ，各个AZ之间是独立失效的，因此整个region失效概率是很低的。region内分为Data center和Satellite site，主DC中允许TS + LS + SS，standby中的DC只保留LS + SS，而Satellite中只运行LS的副本，因此消耗的资源会少很多。

在primary region内，log还是同步复制的，跨region，则通过LogRouters，从主region的LS中异步拉取，同时LogRouter保证同一个log entry不会重复复制（怎么做没有细讲）。

DC之间有有优先级，例如上图DC1 > DC2。

每个region可以各自配置自己的复制策略：

1. 选择一个最高优先级的Satellite，做同步复制（k = 2)，如果这个satellite失效了，则再选次级satellite补上
2. 选择2个最高优先级的Satellites，做同步复制（k = 3)，如果一个satellite失效了，则fallback为选项1
3. 由于前2个都是完全同步复制，所以如果有那种长尾 的网络延迟，则commit会延迟，为此可以配置3副本，但复制时，允许一个异步复制，因此减小了长尾的概率。响应会更快些。

primary DC失效时，standy 的DC会启动一套TS，从主region中的logserver中拉取尚未同步的日志，并根据本region的复制策略，建立Satellites上的LS副本。如果完成后，primary DC已经恢复了且满足了复制要求，则fallback回primary DC，否则secondary DC开始提供服务。

Simulation test

这是FDB一个非常有特色的地方，很可惜这里的很多细节我没有搞清楚，只知道是基于Flow的异步编程框架，每个process都是单线程+callback处理。虽然他们在cmu的talk中也着重讲了下这个测试框架，但我听得模模糊糊。。。基本没体感，所以就不误人子弟了，希望有了解的大神指导下。

总结

总的来说，FDB有几大特色：

1. 非常松耦合的系统，read/write path是分开的，每个功能组件可以独立扩展来避免成为系统瓶颈。
2. log is database，redo apply + undo和recovery解耦，减少commit path的负载
3. 通过OCC + MVCC实现串行化事务，简化log的处理
4. 快速恢复，通过fast failure + fast recovery，来统一对于failure的处理方式，这个recovery路径比较快且稳定

但缺点也很明显：

1. 有限的功能集
2. 串行化事务对事务大小的限制
3. 面对场景比较确定，就是可扩展的，支持小事务高并发的KV存储，且冲突不能太多，不然重试+回滚太多，影响系统吞吐。