面向云数据库，超低延迟文件系统PolarFS诞生了
随着国内首款Cloud Native自研数据库POLARDB精彩亮相ICDE 2018的同时，作为其核心支撑和使能平台的PolarFS文件系统的相关论文"PolarFS: An Ultra-low Latency and Failure Resilient Distributed File System for Shared Storage Cloud Database"也被数据库顶级会议VLDB 2018录用。8月，阿里云数据库团队亮相于巴西里约召开的VLDB 2018，对整个业界起到了非常积极的影响。
VLDB(Very Large Data Base)和另外两大数据库会议SIGMOD、ICDE构成了数据库领域的三个顶级会议。VLDB国际会议于1975在美国的弗雷明汉马 (Framingham MA) 成立，是数据库研究人员，供应商，参与者，应用开发者，以及用户一年一度的顶级国际论坛。
VLDB主要由四个主题构成，分别为：Core Database Technology (核心数据库技术)，Infrastructure for Information Systems (基础设施信息系统)，Industrial Applications and Experience (工业应用与经验) 以及 Experiments and Analyses（实验和分析）。
从09年至今的数据分析来看，VLDB的论文接受率总体是比较低，其中，核心数据库主题中的论文接受率大概为16.7%；基础设施信息系统方面的论文接受率大约为17.9%；工业应用与经验的论文接收比例近视为18%；而实验和分析部分的为19%左右。由此可见，论文被VLDB接收不是件容易的事情，必须是创新性很高，贡献很大的论文才有机会被录用。
本文着重介绍PolarFS的系统设计与实现。
背景
如同Oracle存在与之匹配的OCFS2，POLARDB作为存储与计算分离结构的一款数据库，PolarFS承担着发挥POLARDB特性至关重要的角色。PolarFS是一款具有超低延迟和高可用能力的分布式文件系统，其采用了轻量的用户空间网络和I／O栈构建，而弃用了对应的内核栈，目的是充分发挥RDMA和NVMe SSD等新兴硬件的潜力，极大地降低分布式非易失数据访问的端到端延迟。目前，PolarFS的3副本跨节点写入的访问总延迟已经非常接近单机本地PCIe SSD的延迟水平，成功地使得POLARDB在分布式多副本架构下仍然能够发挥出极致的性能。
设计初衷
针对数据库设计分布式文件系统会带来以下几点好处：
计算节点和存储节点可以使用不同的服务器硬件，并能独立地进行定制。例如，计算节点不需要考虑存储容量和内存容量的比例，其严重依赖于应用场景并且难以预测。
多个节点上的存储资源能够形成单一的存储池，这能降低存储空间碎化、节点间负载不均衡和空间浪费的风险，存储容量和系统吞吐量也能容易地进行水平扩展。
数据库应用的持久状态可下移至分布式文件系统，由分布式存储提供较高的数据可用性和可靠性。因此数据库的高可用处理可被简化，也利于数据库实例在计算节点上灵活快速地迁移。
此外，云数据库服务也会因此带来额外的收益：
云数据库可以采用虚拟计算环境如KVM等部署形态，其更安全、更易扩展和更易升级管理。
一些关键的数据库特性，如一写多读实例、数据库快照等可以通过分布式文件系统的数据共享、检查点等技术而得以增强。
cdn.com/d089eef647b6416cfd15480ad2b6a40618d1be07.png">
系统结构
系统组件
PolarFS系统内部主要分为两层管理：
存储资源的虚拟化管理，其负责为每个数据库实例提供一个逻辑存储空间。
文件系统元数据的管理，其负责在该逻辑存储空间上实现文件管理，并负责文件并发访问的同步和互斥。
PolarFS的系统结构如图所示：
libpfs 是一个用户空间文件系统库，负责数据库的I/O接入。
PolarSwitch 运行在计算节点上，用于转发数据库的I／O请求。
ChunkServer 部署在存储节点上，用于处理I／O请求和节点内的存储资源分布。
PolarCtrl 是系统的控制平面，它包含了一组实现为微服务的管理者，相应地Agent代理被部署到所有的计算和存储节点上。
在进一步介绍各部分之前，我们先来了解下PolarFS存储资源的组织方法：
PolarFS的存储资源管理单元分为3层：Volume、Chunk、Block。
Volume
Volume是为每个数据库提供的独立逻辑存储空间，其上建立了具体文件系统供此数据库使用，其大小为10GB至100TB，可充分适用于典型云数据库实例的容量要求。
在Volume上存放了具体文件系统实例的元数据。文件系统元数据包括inode、directory entry和空闲资源块等对象。由于POLARDB采用的是共享文件存储架构，我们在文件层面实现了文件系统元数据一致性，在每个文件系统中除DB建立的数据文件之外，我们还有用于元数据更新的Journal文件和一个Paxos文件。我们将文件系统元数据的更新首先记录在Journal文件中，并基于Paxos文件以disk paxos算法实现多个实例对Journal文件的互斥写访问。
Chunk
每个Volume内部被划分为多个Chunk，Chunk是数据分布的最小粒度，每个Chunk只存放于存储节点的单个NVMe SSD盘上，其目的是利于数据高可靠和高可用的管理。典型的Chunk大小为10GB，这远大于其他类似的系统，例如GFS的64MB。
这样做的优势是能够有效地减少Volume的第一级映射元数据量的大小（例如，100TB的Volume只包含10K个映射项）。一方面，全局元数据的存放和管理会更容易；另一方面，这使得元数据可以方便地缓存在内存中，从而有效避免关键I/O路径上的额外元数据访问开销。
但这样做的潜在问题是，当上层数据库应用出现区域级热点访问时，Chunk内热点无法进一步打散，但是由于我们的每个存储节点提供的Chunk数量往往远大于节点数量（节点:Chunk在1:1000量级），PolarFS可支持Chunk的在线迁移，并且服务于大量数据库实例，因此可以将不同实例的热点以及同一实例跨Chunk的热点分布到不同节点以获得整体的负载均衡。
Block
在ChunkServer内，Chunk会被进一步划分为多个Block，其典型大小为64KB。Blocks动态映射到Chunk 中来实现按需分配。Chunk至Block的映射信息由ChunkServer自行管理和保存，除数据Block之外，每个Chunk还包含一些额外Block用来实现Write Ahead Log。我们也将本地映射元数据全部缓存在ChunkServer的内存中，使得用户数据的I／O访问能够全速推进。
下面我们详细介绍PolarFS的各个系统组件。
libpfs
libpfs是一个轻量级的用户空间库，PolarFS采用了编译到数据库的形态，替换标准的文件系统接口，这使得全部的I／O路径都在用户空间中，数据处理在用户空间完成，尽可能减少数据的拷贝。这样做的目的是避免传统文件系统从内核空间至用户空间的消息传递开销，尤其数据拷贝的开销。这对于低延迟硬件的性能发挥尤为重要。
其提供了类Posix的文件系统接口（见下表），因而付出很小的修改代价即可完成数据库的用户空间化。
PolarSwitch
PolarSwitch是部署在计算节点的Daemon，它负责I/O请求映射到具体的后端节点。数据库通过libpfs将I/O请求发送给PolarSwitch，每个请求包含了数据库实例所在的Volume ID、起始偏移和长度。PolarSwitch将其划分为对应的一到多个Chunk，并将请求发往Chunk所属的ChunkServer完成访问。
ChunkServer
ChunkServer部署在后端存储节点上。一个存储节点可以有多个ChunkServer。每个ChunkServer绑定到一个CPU核，并管理一个独立的NVMe SSD盘，因此ChunkServer之间没有资源争抢。
ChunkServer负责Chunk内的资源映射和读写。每个Chunk都包括一个WAL，对Chunk的修改会先进Log再修改，保证数据的原子性和持久性。ChunkServer使用了3DXPoint SSD和普通NVMe SSD混合型WAL buffer，Log会优先存放到更快的3DXPoint SSD中。
ChunkServer会复制写请求到对应的Chunk副本（其他ChunkServer）上，我们通过自己定义的Parallel Raft一致性协议来保证Chunk副本之间在各类故障状况下数据正确同步和保障已Commit数据不丢失。
PolarCtrl
PolarCtrl是PolarFS集群的控制核心。其主要职责包括：
监控ChunkServer的健康状况，确定哪些ChunkServer有权属于PolarFS集群；
Volume创建及Chunk的布局管理（即Chunk分配到哪些ChunkServer）；
Volume至Chunk的元数据信息维护；
向PolarSwitch推送元信息缓存更新；
监控Volume和Chunk的I/O性能；
周期性地发起副本内和副本间的CRC数据校验。
PolarCtrl使用了一个关系数据库云服务用于管理上述metadata。
中心统控，局部自治的分布式管理
分布式系统的设计有两种范式：中心化和去中心化。中心化的系统包括GFS和HDFS，其包含单中心点，负责维护元数据和集群成员管理。这样的系统实现相对简单，但从可用性和扩展性的角度而言，单中心可能会成为全系统的瓶颈。去中心化的系统如Dynamo完全相反，节点间是对等关系，元数据被切分并冗余放置在所有的节点上。去中心化的系统被认为更可靠，但设计和实现会更复杂。
PolarFS在这两种设计方式上做了一定权衡，采用了中心统控，局部自治的方式：PolarCtrl是一个中心化的master，其负责管理任务，如资源管理和处理控制平面的请求如创建Volume。ChunkServer负责Chunk内部映射的管理，以及Chunk间的数据复制。当ChunkServer彼此交互时，通过ParallelRaft一致性协议来处理故障并自动发起Leader选举，这个过程无需PolarCtrl参与。
PolarCtrl服务由于不直接处理高并发的I／O流，其状态更新频率相对较低，因而可采用典型的多节点高可用架构来提供PolarCtrl服务的持续性，当PolarCtrl因崩溃恢复出现的短暂故障间隙，由于PolarSwitch的缓存以及ChunkServer数据平面的局部元数据管理和自主leader选举的缘故，PolarFS能够尽量保证绝大部分数据I／O仍能正常服务。
I/O 流程
下面我们通过一个I/O的处理来说明各组件的互动过程。
PolarFS执行写I/O请求的过程如上图所示：
POLARDB通过libpfs发送一个写请求，经由ring buffer发送到PolarSwitch。
PolarSwitch根据本地缓存的元数据，将该请求发送至对应Chunk的主节点。
新写请求到达后，主节点上的RDMA NIC将写请求放到一个提前分好的buffer中，并将该请求项加到请求队列。一个I／O轮询线程不断轮询这个请求队列，一旦发现新请求到来，它就立即开始处理。
请求通过SPDK写到硬盘的日志block，并通过RDMA发向副本节点。这些操作都是异步调用，数据传输是并发进行的。
当副本请求到达副本节点，副本节点的RDMA NIC同样会将其放到预分buffer中并加入到复制队列。
副本节点上的I／O轮询线程被触发，请求通过SPDK异步地写入Chunk的日志。
当副本节点的写请求成功回调后，会通过RDMA向主节点发送一个应答响应。
主节点收到一个复制组中大多数节点的成功返回后，主节点通过SPDK将写请求应用到数据块上。
随后，主节点通过RDMA向PolarSwitch返回。
PolarSwitch标记请求成功并通知上层的POLARDB。
数据副本一致性模型
ParallelRaft协议设计动机
一个产品级别的分布式存储系统需要确保所有提交的修改在各种边界情况下均不丢失。PolarFS在Chunk层面引入一致性协议来保证文件系统数据的可靠性和一致性。设计之初，从工程实现的成熟度考虑，我们选择了Raft算法，但对于我们构建的超低延迟的高并发存储系统而言，很快就遇到了一些坑。
Raft为了简单性和协议的可理解性，采用了高度串行化的设计。日志在leader和follower上都不允许有空洞，其意味着所有log项会按照顺序被follower确认、被leader提交并apply到所有副本上。因此当有大量并发写请求执行时，会按顺序依次提交。处于队列尾部的请求，必需等待所有之前的请求已被持久化到硬盘并返回后才会被提交和返回，这增加了平均延迟也降低了吞吐量。我们发现当并发I／O深度从8升到32时，I／O吞吐量会降低一半。
Raft并不十分适用于多连接的在高并发环境。实际中leader和follower使用多条连接来传送日志很常见。当一个链接阻塞或者变慢，log项到达follower的顺序就会变乱，也即是说，一些次序靠后的log项会比次序靠前的log项先到。但是，Raft的follower必需按次序接收log项，这就意味着这些log项即使被记录到硬盘也只能等到前面所有缺失的log项到达后才能返回。并且假如大多数follower都因一些缺失的项被阻塞时，leader也会出现卡顿。我们希望有一个更好的协议可以适应这样的情形。
由于PolarFS之上运行的是Database事务处理系统，它们在数据库逻辑层面的并行控制算法使得事务可以交错或乱序执行的同时还能生成可串行化的结果。这些应用天然就需要容忍标准存储语义可能出现的I／O乱序完成情况，并由应用自身进一步保证数据一致性。因此我们可以利用这一特点，在PolarFS中依照存储语义放开Raft一致性协议的某些约束，从而获得一种更适合高I／O并发能力发挥的一致性协议。
我们在Raft的基础上，提供了一种改进型的一致性协议ParallelRaft。ParallelRaft的结构与Raft一致，只是放开了其严格有序化的约束。
乱序日志复制
Raft通过两个方面保障串行化：
当leader发送一个log项给follower，follower需要返回ack来确认该log项已经被收到且记录，同时也隐式地表明所有之前的log项均已收到且保存完毕。
当leader提交一个log项并广播至所有follower，它也同时确认了所有之前的log项都已被提交了。ParallelRaft打破了这两个限制，并让这些步骤可乱序执行。
因此，ParallelRaft与Raft最根本的不同在于，当某个entry提交成功时，并不意味着之前的所有entry都已成功提交。因此我们需要保证：
在这种情况下，单个存储的状态不会违反存储语义的正确性；
所有已提交的entry在各种边界情况下均不会丢失；
有了这两点，结合数据库或其他应用普遍存在的对存储I／O乱序完成的默认容忍能力，就可以保证它们在PolarFS上的正常运转，并获得PolarFS提供的数据可靠性。
ParallelRaft的乱序执行遵循如下原则：
当写入的Log项彼此的存储范围没有交叠，那么就认为Log项无冲突可以乱序执行；
否则，冲突的Log项将按照写入次序依次完成。
容易知道，依照此原则完成的I／O不会违反传统存储语义的正确性。
接下来我们来看log的ack-commit-apply环节是如何因此得到优化并且保持一致性的。
乱序确认（ack）：当收到来自leader的一个log项后，Raft follower会在它及其所有之前的log项都持久化后，才发送ack。ParallelRaft则不同，任何log entry成功持久化后均能立即返回，这样就优化了系统的平均延迟。
乱序提交（commit）：Raft leader串行提交log项，一个log项只有之前的所有项提交之后才能提交。而ParallelRaft的leader在一个log项的多数副本已经确认之后即可提交。这符合存储系统的语义，例如，NVMe SSD驱动并不检查读写命令的LBA来保证并行命令的次序，对命令的完成次序也没有任何保证。
乱序应用（apply）：对于Raft，所有log项都按严格的次序apply，因此所有副本的数据文件都是一致的。但是，ParallelRaft由于乱序的确认和提交，各副本的log都可能在不同位置出现空洞，这里的挑战是，如何保证前面log项有缺失时，安全地apply一个log项？
ParallelRaft引入了一种新型的数据结构look behind buffer来解决apply中的问题。
ParallelRaft的每个log项都附带有一个look behind buffer。look behind buffer存放了前N个log项修改的LBA摘要信息。
look behind buffer的作用就像log空洞上架设的桥梁，N表示桥梁的宽度，也就是允许单个空洞的最大长度，N的具体取值可根据网络连续缺失log项的概率大小，静态地调整为合适的值，以保证log桥梁的连续性。
通过look behind buffer，follower能够知道一个log项是否冲突，也就是说是否有缺失的前序log项修改了范围重叠的LBAs。没有冲突的log项能被安全apply。如有冲突，它们会被加到一个pending list，待之前缺失的冲突log项apply之后，才会接着apply。
通过上述的异步ack、异步commit和异步apply，PolarFS的chunk log entry的写入和提交避免了次序造成的额外等待时间，从而有效缩减了高并发3副本写的平均时延。
ParallelRaft协议正确性
我们在ParallelRaft的设计中，确保了Raft协议关键特性不丢失，从而保障了新协议的正确性。
ParallelRaft协议的设计继承了原有Raft协议的Election Safety、 Leader Append-Only及Log Matching 特性。
冲突log会以严格的次序提交，因此协议的State Machine Safety特性能够最终得以保证。
我们在Leader选举阶段额外引入了一个Merge阶段，填补Leader中log的空洞，能够有效保障协议的Leader Completeness特性。
PolarFS中与POLARDB紧密相关的设计
文件系统多副本高速写入--数据库单实例的超高TPS，数据高可靠
PolarFS设计中采用了如下技术以充分发挥I/O性能：
PolarFS采用了绑定CPU的单线程有限状态机的方式处理I/O，避免了多线程I/O pipeline方式的上下文切换开销。
PolarFS优化了内存的分配，采用MemoryPool减少内存对象构造和析构的开销，采用巨页来降低分页和TLB更新的开销。
PolarFS通过中心加局部自治的结构，所有元数据均缓存在系统各部件的内存中，基本完全避免了额外的元数据I/O。
PolarFS采用了全用户空间I/O栈，包括RDMA和SPDK，避免了内核网络栈和存储栈的开销。
在相同硬件环境下的对比测试，PolarFS中数据块3副本写入性能接近于单副本本地SSD的延迟性能。从而在保障数据可靠性的同时，极大地提升POLARDB的单实例TPS性能。
下图是我们采用Sysbench对不同负载进行的初步测试比较。
POLARDB on PolarFS
Alibaba MySQL Cloud Service RDS
用例负载：OLTP，只读、只写（update : delete : insert = 2:1:1）、读写混合（read : write = 7:2）。数据库测试集数据量为500GB。
可以发现POLARDB在PolarFS下取得了较好的性能，PolarFS同时支持了POLARDB的高TPS和数据的高可靠性。
文件系统共享访问--写多读的数据库QPS强扩展，数据库实例的Failover
PolarFS是共享访问的分布式文件系统，每个文件系统实例都有相应的Journal文件和与之对应的Paxos文件。Journal文件记录了metadata的修改历史，是共享实例之间元数据同步的中心。Journal文件逻辑上是一个固定大小的循环buffer。PolarFS会根据水位来回收journal。Paxos文件基于Disk Paxos实现了分布式互斥锁。
由于journal对于PolarFS非常关键，它们的修改必需被Paxos互斥锁保护。如果一个节点希望在journal中追加项，其必需使用DiskPaxos算法来获取Paxos文件中的锁。通常，锁的使用者会在记录持久化后马上释放锁。但是一些故障情况下使用者不释放锁。为此在Paxos互斥锁上分配有一个租约lease。其他竞争者可以重启竞争过程。当PolarFS当节点开始同步其他节点修改的元数据时，它从上次扫描的位置扫描到journal末尾，将新entry更新到memory cache中。
下图展示了文件系统元数据更新和同步的过程。
节点1分配块201至文件316后，请求互斥锁，并获得。
Node 1开始记录事务至journal中。最后写入项标记为pending tail。当所有的项记录之后，pending tail变成journal的有效tail。
Node1更新superblock，记录修改的元数据。与此同时，node2尝试获取node1拥有的互斥锁，Node2会失败重试。
Node2在Node1释放lock后拿到锁，但journal中node1追加的新项决定了node2的本地元数据是过时的。
Node2扫描新项后释放lock。然后node2回滚未记录的事务并更新本地metadata。最后Node2进行事务重试。
Node3开始自动同步元数据，它只需要load增量项并在它本地重放即可。
PolarFS的上述共享机制非常适合POLARDB一写多读的典型应用扩展模式。一写多读模式下没有锁争用开销，只读实例可以通过原子I/O无锁获取Journal信息，从而使得POLARDB可以提供近线性的QPS性能扩展。
由于PolarFS支持了基本的多写一致性保障，当可写实例出现故障时，POLARDB能够方便地将只读实例升级为可写实例，而不必担心底层存储产生不一致问题，因而方便地提供了数据库实例Failover的功能。
文件系统级快照--POLARDB的瞬时逻辑备份
对于百TB级超大数据库实例的备份而言，数据库快照是必须支持的功能。
PolarFS采用了自有的专利快照技术，能够基于位于底层的多个ChunkServer的局部快照，构建Volume上的统一的文件系统即时映像。POLARDB利用自身数据库的日志，能够基于此文件系统映像快速构建出此具体时点的数据库快照，从而有效支持数据库备份和数据分析的需求。
可以发现，POLARDB的高性能、强扩展、轻运维等具备竞争优势的优异特性，与PolarFS的紧密协作息息相关，PolarFS发挥了强大的使能作用。
结论
PolarFS是一个专为云数据库而设计的分布式文件系统，其能够支持跨节点高可靠性同时提供极致的性能。PolarFS采用了新兴硬件和先进的优化技术，例如OS-bypass和zero-copy，使得PolarFS中数据块3副本写入性能接近于单副本本地SSD的延迟性能。PolarFS在用户空间实现了POSIX兼容接口，使得POLARDB等数据库服务能够尽量少地修改即可获得PolarFS带来的高性能的优势。
可以看到，面向数据库的专有文件系统，是保障未来数据库技术领先的一个不可或缺的关键一环。数据库内核技术的进展及其专有文件系统的使能，是一个相辅相成的演进过程，二者的结合也会随着当今系统技术的进步而愈加紧密。
未来我们将探索NVM和FPGA等新硬件，以期通过文件系统与数据库的深度结合来进一步优化POLARDB数据库的性能。
作者：鸣嵩，弘然，明书，旭危，宁进，文义，韩逸，翊云
