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

本文涉及的产品
云数据库 RDS MySQL,集群系列 2核4GB
推荐场景:
搭建个人博客
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
RDS PostgreSQL Serverless,0.5-4RCU 50GB 3个月
推荐场景:
对影评进行热评分析
简介: FoundationDB一个具有事务语义的分布式KV存储,是最早的一批把NoSQL和分布式事务结合起来的数据库系统,它提供了NoSQL的高扩展,高可用和灵活性,同时保证了serializable的强ACID语义。

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

整体架构

image.png

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

v2-853b23ebc6095adb422360fcebca6139_b.png

Resolver的冲突检测算法:

image.png

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

image.png

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

image.png

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

v2-b1c7acb31ccd1e636aa0f5488f247f9a_b.png

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

image.png

在一个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存储,且冲突不能太多,不然重试+回滚太多,影响系统吞吐。
目录
相关文章
|
NoSQL Redis
Redis 之 WRONGTYPE Operation against a key holding the wrong kind of value【bug解决】
Redis 之 WRONGTYPE Operation against a key holding the wrong kind of value【bug解决】
8768 0
|
6月前
|
存储 分布式计算 数据可视化
实时数仓 Hologres产品使用合集之报错:ORCA failed to produce a plan : PlStmt Translation: Group by key is type of imprecise not supported如何解决
实时数仓Hologres是阿里云推出的一款高性能、实时分析的数据库服务,专为大数据分析和复杂查询场景设计。使用Hologres,企业能够打破传统数据仓库的延迟瓶颈,实现数据到决策的无缝衔接,加速业务创新和响应速度。以下是Hologres产品的一些典型使用场景合集。
384 0
|
前端开发 JavaScript Java
Distributed Object|学习笔记
快速学习 Distributed Object
108 0
Distributed Object|学习笔记
|
机器学习/深度学习 PyTorch 算法框架/工具
Re5:读论文 TWAG: A Topic-guided Wikipedia Abstract Generator
Re5:读论文 TWAG: A Topic-guided Wikipedia Abstract Generator
Re5:读论文 TWAG: A Topic-guided Wikipedia Abstract Generator
|
JavaScript
SAP PP使用ECR去修改Recipe主数据,报错:Generation not supported for change object
SAP PP使用ECR去修改Recipe主数据,报错:Generation not supported for change object
SAP PP使用ECR去修改Recipe主数据,报错:Generation not supported for change object
|
JSON 数据格式
OData metadata 定义中,entity type key 的作用是什么
OData metadata 定义中,entity type key 的作用是什么
144 0
OData metadata 定义中,entity type key 的作用是什么
SAP Cloud for Customer的duplicate check最后是通过什么模型实现的
SAP Cloud for Customer的duplicate check最后是通过什么模型实现的
72 0
SAP Cloud for Customer的duplicate check最后是通过什么模型实现的
SAP C4C Embedded Component里Lead ID和Lead TI页面的关系
SAP C4C Embedded Component里Lead ID和Lead TI页面的关系
SAP C4C Embedded Component里Lead ID和Lead TI页面的关系
How SAP concrete schema id is got based on transaction type plus catalog type
How SAP concrete schema id is got based on transaction type plus catalog type
122 0
How SAP concrete schema id is got based on transaction type plus catalog type
|
存储 缓存 监控
FoundationDB论文解读 A Distributed Unbundled Transactional Key Value Store
FoundationDB一个具有事务语义的分布式KV存储,是最早的一批把NoSQL和分布式事务结合起来的数据库系统,它提供了NoSQL的高扩展,高可用和灵活性,同时保证了serializable的强ACID语义。这个数据库很有意思,其对于事务/高可用/容错的设计都非常独特,概括来说,整体采用了松耦合的模块化设计,系统分为了3个组件:in-memory 事务管理分布式的storage管理分布式的sy
907 0