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的事务管理系统的缓存机制有关。

整体架构

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

Control plane

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

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

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

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

Data plane

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的状态。

bootstrap

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

reconfiguration

当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时刻的就不再相同了,串行化被破坏。

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

Resolver的冲突检测算法:

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

为了检测,其内部使用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的流程也比较特殊:

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

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。

Recovery

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信息,恢复如下:

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

由于在日常提交写日志时,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。

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

因此整个的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,采用了一种巧妙的策略:

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

在一个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存储,且冲突不能太多,不然重试+回滚太多,影响系统吞吐。
上一篇:Enhanced Subquery Optimizations in Oracle


下一篇:Incorporating Partitioning and Parallel Plans into the SCOPE optimizer