翻译来源@知乎-清碎
论文地址：https://www.vldb.org/pvldb/vol11/p1849-cao.pdf
摘要
PolarFS是一个具有超低延迟和高可用性的分布式文件系统，专为目前已在阿里云上投入使用的POLARDB数据库服务而设计。PolarFS在用户空间中利用了轻量级的网络栈和I/O栈，充分利用了诸如RDMA、NVMe和SPDK等新兴技术。通过这种方式，极大地降低了PolarFS的端到端时延，实验表明，在SSD上，PolarFS的写时延与本地文件系统（以SSD为介质）的写时延相当接近。
为了在保证副本一致性的同时最大化PolarFS的I/O吞吐量，我们开发了ParallelRaft。ParallelRaft是一个从Raft派生而出的共识协议，它通过利用数据库的乱序I/O完成的容忍能力打破了Raft的严格序列化。ParallelRaft继承了Raft的可理解性和易于实现性，同时为PolarFS提供了更好的I/O可伸缩性。我们还描述了PolarFS的共享存储架构，它为POLARDB提供了强大的支持。
1. 引言
近年来，存储与计算的解耦已经成为云计算行业的一种趋势。这样的设计使架构更加灵活，并有助于利用共享存储能力:
- 计算节点和存储节点可以使用不同类型的服务器硬件，可以单独定制。例如，计算节点不再需要考虑内存与磁盘的比例。而该比例对应用场景的依赖性很大，很难预测。
- 集群内存储节点的硬盘可以组成一个单独的存储池，降低了碎片化、节点间硬盘使用不均衡和空间浪费的风险。存储集群的容量和吞吐量可以轻松透明地扩展。
- 因为数据全部存储在存储集群中，所以计算节点上没有本地持久状态，这使得数据库迁移更容易、更快捷。由于底层分布式存储系统的数据复制和其他高可用特性，数据可靠性也得到提高。
云数据库服务也受益于这种体系结构。首先，基于虚拟化技术，数据库可以构建在更安全、更易扩展的环境上，比如Xen[4]、KVM[19]或Docker[26]。其次，后端存储集群可以提供快速的I/O、数据共享和快照等功能，在其支持下，数据库的一些关键特性，比如多个只读实例和checkpoint，都可以获得增强。
然而，数据存储技术仍在快速更新，因此当前的云平台难以充分利用新兴的硬件标准，如RDMA和NVMe SSD。例如，一些被广泛使用的开源分布式文件系统，如HDFS[5]和Ceph[35]，被发现具有比本地磁盘高得多的延迟。当使用最新的PCIe ssd时，性能差距甚至可以达到数量级。在CPU和内存配置相同对情况下，直接在这些存储系统上运行的MySQL等关系型数据库的性能明显低于本地PCIe ssd硬盘。
为了解决这个问题，AWS、谷歌云平台、阿里云等云计算厂商提供了instance store。instance store使用本地SSD盘和高I/O虚拟机实例，满足客户对高性能数据库的需求。不幸的是，在instance store上运行云数据库有几个缺点：
- instance store容量有限，不适合大型数据库服务。
- instance store不能承受底层磁盘驱动器故障。为了保证数据的可靠性，数据库必须自己管理数据复制。
- instance store使用通用文件系统，如ext4或XFS。当使用像RDMA或PCIe SSD这样的低I/O延迟硬件时，内核空间和用户空间之间的消息传递成本会降低I/O吞吐量。
- 更糟糕的是，instance store不能支持shared-everything的数据库集群架构，而shared-everything是高级云数据库服务的关键特性。
在本文中，我们描述了PolarFS的设计和实现。它作为一个分布式文件系统，通过以下机制提供超低延迟、高吞吐量和高可用性。
- PolarFS充分利用了RDMA和NVMe SSD等新兴硬件，并在用户空间中实现了轻量级的网络堆栈和I/O堆栈，以避免陷入内核态和处理内核锁。
- PolarFS提供了一个类posix的文件系统API，目的是将其编译到数据库进程中，替换操作系统提供的文件系统接口，从而使整个I/O路径保持在用户空间中。
- PolarFS数据平面的I/O模型还旨在消除锁并避免关键数据路径上的上下文切换：所有不必要的内存拷贝也被消除，同时大量使用DMA来在主内存和RDMA NIC/NVMe磁盘之间传输数据。
有了所有这些特性，PolarFS的端到端延迟大大降低了，与SSD上的本地文件系统非常接近。
部署在云生产环境中的分布式文件系统通常有数千台机器。在这样的规模内，硬件或软件缺陷引起的故障是常见的。因此，需要一个共识协议，以确保所有提交的修改不会在极端情况下丢失，副本总是可以达成协议，并成为按bit相同的。
Paxos家族[23,22,7,18,38]协议在解决共识方面得到了广泛认可。而Paxos的变体Raft[28]更容易理解和实现。许多分布式系统都是基于Raft开发的。然而，一旦Raft应用于PolarFS，我们发现在使用额外的低延迟硬件(如NVMe SSD和RDMA，其延迟在几十微秒左右)时，Raft严重阻碍了PolarFS的I/O可扩展性。因此，我们开发了一个基于Raft的增强共识协议ParallelRaft，它允许无序日志的确认、提交和应用，同时让PolarFS符合传统的I/O语义。使用该协议，PolarFS的I/O并发性得到了显著改善。
最后，我们在PolarFS的基础上实现了POLARDB，这是一个从AliSQL (MySQL/InnoDB的一个分支)[2]改进而来的关系型数据库系统，它是阿里云计算平台上最近推出的数据库服务。POLARDB遵循共享存储体系结构，并支持多个只读实例。如图1所示，POLARDB的数据库节点分为两种类型:主节点和只读(RO)节点。主节点可以同时处理读、写请求，而RO节点只支持读请求。
主节点和RO节点共享PolarFS中相同数据库目录下的redo log文件和数据文件。PolarFS支持的POLARDB具有以下特点:
- PolarFS可以同步主节点对文件元数据的修改(如文件截断或扩展、文件创建或删除)到RO节点，因此RO节点可以看到所有的修改。
- PolarFS确保对文件元数据的并发修改被序列化，这样文件系统本身在所有数据库节点上是一致的。
- 在网络分区的情况下，可能会有两个或两个以上的节点同时作为主节点在PolarFS中写共享文件，PolarFS可以确保只有真正的主节点被成功服务，防止数据损坏。
该篇论文的贡献包括：
- 我们描述了如何构建PolarFS，一个具有超低延迟、利用了新兴硬件和软件优化的最先进的分布式文件系统。(第3、4和7节)
- 我们提出了ParallelRaft，一个实现共识的新协议。ParallelRaft是为大规模、支持容错和分布式的文件系统设计的。在Raft的基础上对其进行了修改，以适应存储语义。与Raft相比，ParallelRaft在PolarFS中为高并发I/O提供了更好的支持。(第5节)
- 我们介绍了PolarFS的关键特性，这些特性为POLARDB的共享存储架构提供了强有力的支持。(第6节)
- 本文其他部分的结构如下：第2节给出了PolarFS使用的新兴硬件的背景信息；第8节介绍并讨论我们的实验评估；第9节回顾相关工作；第10节总结全文。
2. 背景
本节简明阐述了NVMe SSD, RDMA和他们相应的编程模型。
NVMe SSD.
SSD正在从SAS、SATA等传统协议发展到NVMe, NVMe具有高带宽和低延迟的I/O互连。NVMe SSD可以在100µs以下的时延下提供高达500K的IOPS (I/O operations per second)，而最新推出的3D XPoint SSD可以将I/O时延降低到10µs左右，并提供比NAND SSD更好的QoS。随着SSD的速度越来越快，传统内核I/O栈的开销成为瓶颈[37,36,31]。正如先前的研究[6]所揭示的那样，仅仅完成一个4KB的I/O请求就需要执行大约20,000条指令。最近，Intel发布了存储性能开发工具包(SPDK)[12]，这是一套工具和库，主要用于构建 基于高性能NVMe设备的、可伸缩的、用户模式的存储应用程序。它通过将所有必要的驱动程序移到用户空间，并以轮询模式而不是依赖于中断的模式来实现高性能，这避免了内核上下文切换并消除了中断处理开销。
RDMA.
RDMA技术提供了数据中心内部服务器之间的低延迟网络通信机制。例如，在连接到同一台交换机的两个节点之间传输一个4KB的数据包需要大约7µs的时间，这比传统的TCP/IP网络堆栈要快得多。之前的大量研究[9,14,15,17,24,25,30]表明RDMA可以提高系统性能。
应用程序通过Verbs API访问一个队列对(QP，queue pair)，从而与RDMA NIC交互。一个QP由一个发送队列和一个接收队列组成，每个QP都与另一个完成队列(CQ)相关联。CQ通常用作完成事件/信号的轮询目标。
Send/Recv动词通常被称为双边操作，因为每个Send操作都需要一个由远程进程调用的匹配的Recv操作，而Read/Write动词被称为单边操作，因为远程内存是由NIC操作的，而不涉及任何远程CPU。PolarFS使用了Send/Recv和Read/Write动词的混合。小负荷直接通过Send/Recv动词转移。对于大块数据或一批数据，节点使用Send/Recv动词在远程节点上协商目标内存地址，然后通过Read/Write动词完成实际的数据传输。通过轮询用户空间中的CQ而不是依赖于中断，PolarFS消除了上下文切换。
3. 架构
PolarFS由两个主要层组成。底层是存储管理，上层是文件系统的元数据管理，提供文件系统API。存储层负责存储节点的所有磁盘资源，并为每个数据库实例提供一个数据库卷。文件系统层支持卷中的文件管理，负责文件系统元数据并发访问的互斥和同步。对于数据库实例，PolarFS将文件系统元数据存储在其卷中。
这里我们展示了PolarFS集群中的主要组件，如图2所示。libpfs是一个用户空间文件系统实现库，带有一组类POSIX的文件系统API，它被链接到POLARDB进程；PolarSwitch位于计算节点上，将I/O请求从应用程序重定向到ChunkServers；ChunkServer部署在存储节点上处理I/O请求；PolarCtrl是控制平面，包括一组在微服务中实现的主节点，以及部署在所有计算和存储节点上的代理。PolarCtrl使用MySQL实例作为元数据存储库。
PolarCtrl存储节点间的主从关系 or 计算节点与存储节点的映射关系？
3.1 文件系统层
文件系统层提供了一个共享且并行的文件系统，旨在由多个数据库节点并发访问。例如，在POLARDB场景中，当主数据库节点执行一个创建表DDL语句时，将在PolarFS中创建一个新文件，从而使在RO节点上执行的select语句能够访问该文件。因此，需要在节点间同步文件系统元数据的修改，以保持一致性，同时序列化并发形式的修改以避免元数据被破坏。
3.1.1 libpfs
libpfs是完全在用户空间中运行的轻量级文件系统实现。如图3所示，libpfs提供了一组类似posix的文件系统API。将数据库移植到PolarFS上运行非常容易。
当数据库节点启动时，pfs_mount 挂载连接到其卷并初始化文件系统状态。volname是分配给POLARDB实例的卷的全局标识符；而hostid是数据库节点的索引，用于在磁盘paxos投票算法中作为标识符(参见6.2节)。在挂载过程中，libpfs从卷中加载文件系统元数据，并在主存中构造数据结构，例如目录树、文件映射表和块映射表(参见6.1节)。pfs_umount在数据库销毁期间卸载卷并释放资源。在卷空间增长之后，应该调用pfs_mount_growfs 以识别新分配的块并将其标记为可用。Rest函数是文件、目录操作函数，相当于POSIX API中的对应函数。文件系统元数据管理的详细信息将在第6节中描述。
3.2 存储层
存储层为文件系统层提供管理和访问卷的接口。每个数据库实例分配一个卷，每个卷由一个Chunk列表组成。卷的容量范围为10GB ~ 100TB，可以满足绝大多数数据库的需求，此外，卷的容量可以通过追加Chunk来按需扩展。如传统存储设备一般，一个卷可以在512B对齐方式下随机访问（读、写）。对单个I/O请求中携带的对同一Chunk的修改是原子性的。
块（Chunk）
卷被划分为多个Chunk，这些Chunk分布在chunkserver之间。Chunk是数据分布的最小单位。在ChunkServer上，一个Chunk不会跨多个磁盘，它的副本默认情况下会被复制到三个不同的ChunkServer(总是位于不同的机架)。当热点存在时，Chunk可以在ChunkServers之间迁移。
在PolarFS中，Chunk的大小设置为10GB，明显大于其他系统中的单位大小（例如GFS[11]使用的Chunk大小为64MB）。这种选择减少了元数据数据库中维护的元数据的数量，并简化了元数据管理。例如，一个100TB的卷只包含10,000个Chunk。在元数据数据库中存储10,000条记录的成本相对较小。此外，所有这些元数据都可以缓存到PolarSwitch的主内存中，从而避免了关键I/O路径上额外的元数据访问成本。
这种设计的缺点是一个Chunk上的热点不能被进一步分离。但是，由于Chunk与服务器的比例很高(现在约为1000:1)，通常有大量的数据库实例(数千或更多)，以及服务器间的Chunk迁移能力，PolarFS可以在整个系统级别实现负载平衡。（？？？服务器指的是chunkserver还是计算实例）
Block
一个Chunk在ChunkServer中被进一步划分为block，每个block被设置为64kb。根据需要对block进行分配和映射，以实现精简配置。一个10GB的chunk包含163840个block。chunk的LBA (Logical Block Address，逻辑block地址，线性地址，范围从0到10GB)到block的映射表存储在ChunkServer本地，每个磁盘上空闲块的bitmap同样存储在ChunkServer本地。单个chunk的映射表占用640 KB的内存，这是一个非常小的内存，可以缓存到ChunkServer的内存中。
3.2.1 PolarSwitch
PolarSwitch是一个部署在数据库服务器上的守护进程，服务器上同时还部署着一个或多个数据库实例。在每个数据库进程中，libpfs将I/O请求转发给PolarSwitch守护进程。每个请求包含寻址信息(如卷标识符、偏移量和长度)，从这些信息可以识别相关的块。一个I/O请求可能跨越多个块，在这种情况下，请求被进一步划分为多个子请求。最后，一个元素请求被发送到chunk的leader所在的ChunkServer。
PolarSwitch通过查找本地元数据缓存（该份缓存与PolarCtrl同步），来查找同属一个chunk的所有副本的位置。一个chunk的一系列副本形成一个共识组，一个是领导者，其他的是追随者。只有leader才能响应I/O请求。共识组中的领导权变更也会同步并缓存在PolarSwitch的本地缓存中。如果发生响应超时，PolarSwitch需要检测是否发生leader选举，以指数回退的方式持续重试，如果发生leader选举，则切换到新的leader并立即重传。
3.2.2 ChunkServer
chunkserver部署在存储服务器上。存储服务器上运行多个ChunkServer进程，每个ChunkServer拥有一个独立的NVMe SSD盘，并绑定一个专用的CPU核，这样两个ChunkServer之间就不会出现资源争用。ChunkServer负责chunk的存储，并提供对chunk的随机访问。每个chunk包含一个WAL(write ahead log)，对chunk的修改会在更新块之前附加到日志中，以确保原子性和持久性。ChunkServer使用一块固定大小的3D XPoint SSD buffer作为WAL的写缓存，日志优先放置在3D XPoint buffer中。如果缓冲区是满的，ChunkServer将尝试回收过期日志。如果3D XPoint缓冲区仍然没有足够的空间，则将日志写入NVMe SSD。 Chunk blocks始终写入NVMe SSD。（这边的chunk blocks是指普通数据？）
ChunkServers使用ParallelRaft协议互相复制I/O请求，并形成一个一致性组。一个ChunkServer可能由于各种原因从它的共识组下线，并且下线的处理方式可能不同。有时它是由偶然、临时的故障引起的，例如网络暂时不可用，或服务器升级和重启。在这种情况下，最好是等待断开的ChunkServer恢复在线，再次加入组并赶上其他人。在其他情况下，故障是永久性的或可能持续很长时间，例如服务器损坏或离线。这时，故障的ChunkServer上的所有chunk都应该迁移到其他ChunkServer上，以便重新获得足够数量的副本。
断开连接的ChunkServer将总是努力自动重新加入共识组，以缩短不可用时间。然而，PolarCtrl可以做出补充性决策。PolarCtrl定期收集之前断开连接的ChunkServers的列表，并挑选出似乎有永久故障的ChunkServers。有时候很难做决定，例如，磁盘速度较慢的ChunkServer可能比其他ChunkServer有更长的延迟，但它总是可以响应活跃度探测。基于关键部件的性能metrics进行统计的机器学习算法在此处是有帮助的。
3.2.3 PolarCtrl
PolarCtrl是PolarFS集群的控制平面。它部署在一组专用机器(至少3台)上，以提供高可用性服务。PolarCtrl提供集群控制服务，如节点管理、volume管理、资源分配、元数据同步、监控等。PolarCtrl负责:
- 跟踪集群中所有ChunkServer的成员和活性，如果ChunkServer负载过重或不可用持续时间超过阈值，则开始将chunk副本从一个服务器迁移到其他服务器。
- 维护元数据数据库中所有volume和chunk位置的状态。
- 创建volume，并将chunk分配给ChunkServers。
- 使用push和pull两种方法同步元数据到PolarSwitch。
- 监控每个volume和chunk的时延/IOPS指标，沿着I/O路径收集跟踪数据。
- 定期调度副本内部和副本之间的CRC检查码。
PolarCtrl通过控制平面命令 周期性地将集群元数据(例如某个volume的chunk的位置)与PolarSwitch同步。PolarSwitch将元数据保存在其本地缓存中。当从libpfs接收到I/O请求时，PolarSwitch会根据本地缓存将请求路由到相应的ChunkServer。偶尔，如果本地缓存落后于中心元数据存储库，PolarSwitch会从PolarCtrl处获取元数据。
如何判断本地缓存落后？
作为一个控制平面，PolarCtrl不在关键I/O路径上，它的业务连续性可以通过传统的高可用性技术来提供。即使在PolarCtrl崩溃和恢复之间的较短时间内，由于PolarSwith上缓存的元数据和ChunkServer的自我管理，PolarCtrl的I/O流也不太可能受到影响。
4. I/O 执行模型
当POLARDB访问它的数据时，它将通过PFS接口 将文件I/O请求委托给libpfs，具体操作通常是通过PFS pread或PFS pwrite。对于写请求，几乎不需要修改文件系统元数据，因为设备块是通过pfs fallocate预先分配给文件的，从而避免了写节点和读节点之间昂贵的元数据同步。这是数据库系统的常规优化。
在大多数常见情况下，libpfs只是根据挂载时已经构建的索引表，将文件偏移量映射为block偏移量，并将文件I/O请求分割为一个或多个较小的固定大小的block I/O请求。转换之后，block I/O请求由libpfs通过它们之间的共享内存发送给PolarSwitch。
直接分解为block粒度而非chunk粒度，写放大如何解决？
共享内存被构造为多个环形缓冲区。在共享内存的一端，libpfs将一个block I/O请求排在循环缓冲区中，然后等待它的完成，该缓冲区以轮询方式进行选择。在另一端，PolarSwitch不断地轮询所有的环形缓冲区，其中一个线程专用于环形缓冲区。一旦它发现新的请求，PolarSwitch将请求从环形缓冲区中取出，并根据从PolarCtrl处获取的路由信息，将它们转发给ChunkServers。
Chunkserver使用WAL (write ahead logging)技术来确保原子性和持久性，即I/O请求在提交和应用之前先被写入日志。日志被复制到一组副本中，使用一个名为ParallelRaft的共识协议(将在下一节详细介绍)来保证副本之间的数据一致性。一个I/O请求只有被持久化记录到大多数副本的日志中，才会被认为已提交。只有在此之后，该请求才能被响应到客户端并应用到数据块上。
图4显示了一个写I/O请求是如何在PolarFS中执行的。
- POLARDB通过PolarSwitch和libpfs之间的环形缓冲区向PolarSwitch发送写I/O请求。
- PolarSwitch根据本地缓存的集群元数据将请求传输到对应chunk的leader节点。
- 当新的写请求到达时，leader节点的RDMA网卡将写请求放入预注册的缓冲区，并在请求队列中添加一个请求条目。一个I/O循环线程不断轮询请求队列。一旦它看到一个新请求到达，它就立即开始处理该请求。
- 通过SPDK将请求写入磁盘上的日志block，并通过RDMA传播到follower节点。这两个操作都是异步调用，实际的数据传输将并行进行。
- 当复制请求到达follower节点时，跟随节点中的RDMA网卡也会将复制请求放入预注册的缓冲区，并将其添加到复制队列中。
- follower节点上的I/O循环线程被触发，通过SPDK异步将请求写入磁盘。
- 当写回调 成功返回时，follower通过RDMA向leader发送确认响应。
- 当成功收到大多数follower的响应后，leader通过SPDK对该数据块进行写请求。
- 之后leader通过RDMA回复PolarSwitch。
- 然后，PolarSwitch标记请求已完成，并通知客户端。
读I/O请求(更简单)由leader单独处理。在ChunkServer中有一个名为IoScheduler的子模块，它负责仲裁并发I/O请求在ChunkServer上执行的磁盘I/O操作的顺序。IoScheduler保证读操作总是能够检索最近提交的数据。
ChunkServer采用轮询模式和事件驱动有限状态机作为并发模型。I/O线程一直轮询来自RDMA和NVMe队列的事件，在同一个线程中处理传入的请求。当一个或多个异步I/O操作发出后，并有其他请求需要处理时，I/O线程将暂停处理当前请求，并将上下文保存到状态机中，然后切换到处理下一个传入的事件。
每个I/O线程使用一个专用的core，并使用分离的RDMA和NVMe队列对。因此，一个I/O线程的实现没有锁开销，因为在I/O线程之间没有共享的数据结构，即使在单个ChunkServer上有多个I/O线程。
5. 一致性模型
5.1 修正的Raft
生产中所使用的分布式存储系统需要一个共识协议，以保证所有已提交的修改在任何情况下都不会丢失。在设计初始阶段，考虑到实现的复杂性，我们选择了Raft。然而，一些问题很快就出现了。
Raft被设计成高度序列化的，以便简单易懂。它不允许leader或follower上的日志有空洞，这意味着日志条目由follower确认，由leader提交，并依次应用到所有副本。因此，当写请求并发执行时，它们将按顺序提交。在前面所有的请求被持久化到磁盘并得到响应之前，队列尾部的那些请求不能被提交和响应，这增加了平均延迟并降低了吞吐量。我们观察到，当I/O深度从8上升到32时，吞吐量下降了一半。
在一个leader和一个follower之间，用多个连接来传输日志的环境，这种场景Raft不太适用。当一个连接阻塞或变慢时，日志条目将无序地到达follower。换句话说，一些排在队列前面的日志条目实际上会比排在后面的日志条目到达得晚。但是，一个Raft follower必须按顺序接受日志条目，这意味着直到之前丢失的日志条目到达，follower都不能发送一个确认来通知leader后续的日志条目已经被持久化到磁盘。此外，当大多数follower被某些丢失的日志条目阻塞时，leader会被卡住。然而，在实践中，对于高并发的环境，使用多个连接是很常见的。我们需要修改Raft协议来支撑这种情况。
在数据库等事务处理系统中，并发控制算法允许以交错和无序的方式执行事务，同时生成可序列化的结果。这些系统自然可以容忍由传统存储语义引起的乱序I/O完成，并自行处理，以确保数据一致性。实际上，MySQL和AliSQL等数据库并不关心底层存储的I/O序列。
个人理解：原版Raft通过过程的有序性确保结果的有序性，而数据库系统往往只关心结果的有序性而非过程的有序性。也正是对于过程的无序性的容忍，数据库才能支持高并发场景。正是这一点的冲突，使得本文作者决定修改Raft算法，使得其与数据库系统同步，放弃过程的有序性，只关注结果的有序性。
数据库的锁系统将保证在任何时候，只有一个线程可以在一个特定的页面上工作。当不同的线程并发地在不同的页面上工作时，数据库只需要成功地执行I/O，它们的完成顺序并不重要。因此，我们利用这一点，在PolarFS中放松了Raft的一些限制，开发了一个更适合高I/O并发的共识协议。
“只有一个线程可以在一个特定的页面上工作“存疑，MySQL的行锁机制通过bitmap数据结构使得多个事务可以对同一页面操作，个人觉得多个事务可以对应多个线程同时操作特定页面。
本文提出了一种改进的Raft共识协议ParallelRaft，并将在接下来的章节中介绍ParallelRaft是如何解决上述问题的。ParallelRaft的结构与Raft非常相似。它通过复制日志来实现复制的状态机。节点分为leader和follower， leader将日志条目复制到follower。我们遵循与Raft一样的问题分解方法，将ParallelRaft划分为更小的部分：日志复制、leader选举和catch up。
5.2 Out-of-Order Log
Replication Raft的序列化有两个方面：
- leader向follower发送日志条目后，follower需要确认该日志条目已被接收并记录，这也暗示了之前所有的日志条目都已被查看并保存。
- 当leader提交一个日志条目，会广播这个事件给所有的follower，这也意味着该条目之前所有的日志条目也已经被提交。
ParallelRaft打破了这些限制，并无序地执行所有这些步骤。因此，ParallelRaft和Raft有一个基本的区别。在ParallelRaft中，当一个日志条目已被标为已提交时，并不意味着前面所有的日志条目都已成功提交。为了保证该协议的正确性，我们必须保证：
- 如果没有这些串行限制，all the committed states will also be complaint with the storage semantics used by classical rational databases.
- 所有已提交的修改在任何情况下都不会丢失。
这边be complaint with怎么理解？与…相符？
ParallelRaft的乱序执行遵循如下规则：如果日志项的写入范围没有重叠，则认为这些日志项没有冲突，可以按照任何顺序执行；若有重叠，冲突条目在到达时将按照严格的顺序执行，这样，新的数据就不会被旧的版本覆盖。ParallelRaft可以很容易地知道冲突，因为它存储了未应用的任何日志条目的LBA范围摘要。下面的部分描述了如何优化ParallelRaft的Ack-Commit-Apply步骤，以及如何维护必要的一致语义。
Out-of-Order Acknowledge
Raft中，在从leader处接收到一个复制的日志条目后，如果前面还有日志条目没有被持久化存储，那么一个follower将不会承认该条目，这将引入额外的等待时间。此外，当有大量并发I/O写执行时，平均延迟将显著增加。然而，在ParallelRaft中，一旦日志条目被成功写入，跟随者可以立即确认它。通过这种方式，可以避免额外的等待时间，从而优化平均延迟。
raft中，当follower和leader日志不一致时，附加⽇志 RPC 的请求会被follower拒绝，leader收到拒绝消息后减少相应的nextindex。 follower也可以返回冲突条⽬的起始位置，帮助leader更好定位。
Out-of-Order Commit
Raft中，leader按照串行顺序提交日志条目，只有在前面的所有日志条目都被提交后，日志条目才能被提交。而在ParallelRaft中，一个日志条目如果在大多数副本中被确认，则可以立即提交。对于存储系统来说，这种提交语义是可以接受的，因为存储系统通常不像TP系统那样承诺强一致性语义。例如，NVMe不检查读、写命令的LBA，所以不确保并发命令之间的任何类型的顺序，也不保证这些命令[13]的完成顺序。
Apply with Holes in the Log
和Raft一样，ParallelRaft中所有日志条目都按照严格的顺序（它们被记录在日志中的顺序）应用，因此数据文件在所有副本中是一致的。然而，由于无序的日志复制和提交，ParallelRaft允许日志中存在空洞。在前面的日志项仍然缺失的情况下，如何安全地应用日志项？这给ParallelRaft带来了挑战。
ParallelRaft在每个日志条目中引入了一种名为look behind buffer的新数据结构来解决这个问题。look behind buffer包含被前面N个日志条目修改过的LBA(logical block address)，因此look behind buffer宛如 在日志中可能存在的空洞上 建立的桥梁。N是这座桥的跨度，也是允许的日志空洞的最大尺寸。请注意，尽管日志中可能存在几个洞，但所有日志条目的LBA摘要总可以是完整的，除非任何洞的大小大于N。
通过这个数据结构，follower可以判断一个日志条目是否发生冲突。当发生冲突时，这个日志条目修改的LBA将与在它之前却丢失了的日志条目重叠。如果日志条目与任何其他条目不冲突，则可以被安全地应用，否则应该将它们添加到一个挂起的列表中，并在检索到丢失的条目后予以回复。根据我们在带有RDMA网络的PolarFS的经验，N设置为2对于它的I/O并发来说已经足够好了。
基于上述的乱序执行方法和规则，可以成功地实现数据库所需的存储语义。此外，通过消除ParallelRaft对PolarFS不必要的串行限制，还可以缩短多副本并发写的延迟。
5.3 领导人选举
在进行新的leader选举时，和Raft一样，ParallelRaft可以选择拥有最新term和最长log entry的节点。在Raft中，新当选的领导人包含了所有以前任期内提交的条目。然而，在ParallelRaft中选出的leader一开始可能不满足这个要求，因为日志上可能有空洞。
因此，需要一个额外的合并阶段，以使leader在开始处理请求之前拥有所有已提交的条目。合并阶段结束前，新选出的节点只是leader candidate，合并阶段结束后，它拥有所有已提交的日志条目，成为真正的leader。在合并阶段，leader candidate节点需要从其他成员处获取它所没有的条目并进行合并。在此之后，leader将开始提交之前任期的日志条目给其他成员，这与Raft相同。在合并条目时，ParallelRaft也使用类似于Raft的机制。
具有相同的term和index的条目将被认为是相同的条目。有几个异常情况：
- 对于一个已提交但缺失的条目，leader candidate总是可以从至少一个follower candidate中找到相同的已提交条目，因为这个已提交的条目已被集群多数节点接受。
- 对于一条没有提交也没有保存到任何候选节点上的记录，leader可以安全地跳过这个日志记录，因为根据ParallelRaft或Raft机制，它之前不可能被提交。
- 如果有部分candidates保存了这个未提交的条目(index相同，但term不同)，那么leader candidate就会选择term最高的条目版本，并识别该条目为有效条目。我们必须这样做是因为另外两个事实:
- ParallelRaft服务于用户请求之前必须要完成合并阶段，这意味着，如果存在一个entry拥有更高的term，那么有相同index但term更低的entry之前一定没有成功提交过，并且term更低的entry一定从未参与过之前成功完成的合并阶段，否则term较高的entry不可能拥有相同的index。
- 当一个系统崩溃时，如果candidate中保存着一个未提交的entry，这个entry的ack可能已被发送给之前的leader，并且leader还回复了client。所以我们不能简单地抛弃该entry，否则用户数据可能会丢失。(更准确地说，如果故障节点数量 加上 这个拥有未提交的entry的节点 的总数(这些entry具有相同索引的最高项)超过了同一集群中其他节点的数量，那么这个条目可能已经被故障的leader提交了。因此，为了用户数据的安全，我们应该提交改entry。)
以3副本的情况为例，图5展示了leader选举的过程：
- follower candidate对象将其本地日志条目发送给leader candidate对象。leader candidate接收这些日志条目，并将其与自己的日志条目合并。
- leader candidate对象同步状态到follower candidate对象。之后，leader candidate可以提交所有的条目，并通知follower候选人提交。
- leader candidate升级为leader，而follower candidate也升级为follower。
使用上述机制，所有已提交的条目都可以被新的leader恢复，这意味着ParallelRaft不会丢失任何已提交的状态。
在ParallelRaft中，会不时地创建一个检查点，在检查点之前的所有日志条目都被应用到数据块上，并且允许检查点包含一些在检查点之后提交的日志条目。为简单起见，可以将检查点之前的所有日志条目视为pruned（被删除的），尽管在实践中它们会保留一段时间，直到资源不足或达到某个阈值。
异步gc的思想
在我们的实际实现中，为了方便Catch Up的实现，ParallelRaft选择具有最新checkpoint 的节点作为leader candidate，而不是具有最长日志的节点。在合并阶段，新的leader会在开始服务时达到相同的状态。因此，这种选择并不会影响ParallelRaft的正确性。
5.4 Catch Up
当一个滞后的跟随者想要跟上leader的当前数据状态时，它将使用fast-catch-up或streaming-catch-up来与leader重新同步。使用哪一个取决于follower的状态有多陈旧。针对leader和follower之间差异较小的情况，设计了fast-catch-up机制，来实现增量同步。还有一种情况，follower可能远远落后于leader。例如，follower已经离线好几天了，所以完整的数据重新同步是不可避免的。因此，PolarFS针对这种情景提出了一种名为streaming-catch-up的方法。
图6给出了重新同步开始时，leader和follower的不同情况。在案例1中，leader的checkpoint比follower的最新日志index更加新，并且这两者间相差的日志记录可能已被leader回收删除了。因此，fast-catch-up不能处理这种情况，应该使用streaming-catch-up代替。案例2和案例3则可以通过fast-catch-up来解决。
在以下情况下，我们总是可以假设leader的checkpoint比follower的更新，因为如果这个条件不满足，leader可以立即创建一个比其他任何checkpoint更新的checkpoint。
checkpoint之后的日志条目可以分为四类：提交并应用、提交但未应用、未提交和空洞。
Fast Catch Up：
Follower在checkpoint之后可能会有漏洞，在fast catch up时会将其补上。首先，通过look behind buffer可以发现所有丢失的修改的LBA，所以可以用它来填补follower和leader的checkpoint之间的空洞。这些空洞可以直接通过复制leader的数据block来填补，这些数据block包含比follower的checkpoint更新的数据。其次，通过读取leader的日志block来填补leader的checkpoint之后的空洞。
在案例3中，follower可能包含一些来自旧term的未提交日志条目。像Raft一样，这些条目被删除，然后按照上面的步骤处理。
Streaming Catch Up
在Streaming Catch Up中，比checkpoint的更旧的日志历史对于完整数据的重新同步是无用的，而checkpoint之后的数据块和日志条目的内容都是必要的以重建整体数据状态。当复制chunk时，整个chunk被分割成128KB的小块，并使用大量的小任务，每个小任务只同步一个128KB的块。我们这样做是为了建立一个更可控的重新同步。进一步的设计思想将在第7.3节中讨论。
5.5 ParallelRaft的正确性
Raft保证了以下特性以支撑协议正确性：选举安全性、Leader Append-Only、日志匹配、Leader完整性和状态机安全性。很容易证明parallelfraft具有选举安全、Leader Append-Only和日志匹配的特性，因为ParallelRaft没有对它们进行改造。
ParallelRaft的无序提交是它与标准Raft的关键区别。ParallelRaft日志可能缺少一些必要的条目。因此，我们需要考虑的关键场景是，新当选的leader应该如何处理这些遗漏的条目。ParallelRaft增加了一个leader选举的合并阶段。在合并阶段，leader将复制这些丢失的日志条目，重新确认是否应该提交这些条目，然后在必要时在集群中提交它们。在5.3节描述的合并阶段之后，Leader完整性得到保证。
此外，如5.2节所述，在PolarFS中数据库的无序提交也是可以接受的。
然后我们证明乱序应用不会破坏状态机安全特性。尽管ParallelRaft允许节点的无序、独立应用，由于 look behind buffer (5.2节)的存在，冲突日志只能以一个严格的顺序被应用，这意味着状态机(数据 + 已提交的日志条目)在同一集群中的所有节点将相互一致。
有了以上所有这些属性，ParallelRaft的正确性就得到了保证。
5.6 ParallelRaft相关
我们做了一个简单的测试来展示ParallelRaft如何提高I/O并发性。图7显示了在I/O深度为1 ~ 32和单个FIO作业时，Raft和ParallelRaft的平均时延和吞吐量。两种算法都使用RDMA实现。开始时的轻微性能差异可以忽略，因为它们是独立实现的不同软件包。随着I/O深度的增加，两种协议之间的性能差距越来越大。当I/O深度增加到32时，Raft的延迟大约是ParallelRaft的2.5倍，且Raft的IOPS还不到ParallelRaft的一半。值得注意的是，当I/O深度大于8时，Raft的IOPS明显下降，而ParallelRaft整体保持在一个稳定的高水平。结果证明了ParallelRaft 方案作出的改进的有效性。乱序确认和提交提高了I/O并行性，使得即使在较重工作负载下，PolarFS仍能保持稳定的高性能。
总结：ParallelRaft将Raft中日志、ack、提交的有序性限制解除，但对于应用的有序性仍要保持。
6. FS层实现
在PolarFS的文件系统层中，元数据管理可以分为两部分。一部分是组织元数据来访问和更新数据库节点中的文件和目录。第二种是协调和同步数据库节点之间的元数据修改。
6.1 元数据管理
文件系统有三种元数据：directory entry、inode和block tag。单个directory entry持有文件路径的名称组件和一个inode的引用。directory entry的集合被组织成目录树。inode描述普通文件或目录。对于普通文件，inode持有一组block tag的引用，每个block tag描述一个文件block号到卷block号的映射；对于目录，inode持有该父目录中的一组子目录项的引用。(上面提到的引用实际上是元对象标识符，具体如下所述)。
这三种元数据被抽象为一种称为元对象的数据类型，该类型具有一个字段，用于保存directory entry、inode或block tag的特定数据。这种通用数据类型用于访问磁盘和内存中的元数据。创建新文件系统时，元对象在连续的4k扇区中初始化，并为每个元对象分配一个唯一的标识符。在pfs mount中，所有元对象都被加载到内存中，并被划分为chunks和类型组。
在内存中使用元组(元对象标识符，元对象类型)访问元对象。标识符的上半部分用于查找元对象所属的chunk，类型是用来查找chunk中的对应组，最后将标识符的下半部分用作索引 以访问组中的元对象。
要更新一个或多个元对象，需要准备一个事务，并将每次更新记录为一个事务操作。事务操作保存其修改对象的旧值和新值。一旦所有更新都完成，事务就可以提交了。提交过程需要数据库节点之间的协调和同步，具体描述见下文。如果提交失败，则使用保存在事务中的旧值回滚这次更新。
6.2 协调和同步
为了支持文件系统元数据的同步，PolarFS将元数据修改作为事务记录到一个日志文件中。数据库节点对日志文件进行轮询以获取新的事务。一旦找到，新的事务就会被节点检索和重放。
通常，只有一个实例在写入日志文件，而有多个实例在读取日志文件。在网络分区或管理的情况下，可能会有多个实例写入日志文件。在这些情况下，我们需要一种机制来协调对日志文件的写操作。为此，PolarFS使用磁盘paxos算法[10]。请注意，这里使用的磁盘paxos算法的目的与ParallelRaft非常不同。后者是为了确保chunk副本之间的数据一致性。
磁盘paxos算法运行在由4K大小的页面组成的文件上，这些页面可以以原子方式进行读写。这些页面被解释为一个leader记录 + 各个数据库节点的数据block。每个数据库节点使用数据block页来写入自身的proposal，并读取其他节点的proposal。lerder记录页包含当前paxos获胜者和日志锚的信息。磁盘paxos算法只由写节点运行。只读节点不运行磁盘paxos，相反，他们通过检查leader记录页中的日志锚的形式进行轮询。如果日志锚发生变化，只读节点就知道日志文件中有新的事务了，它们将检索这些新事务来更新其本地元数据。
这个磁盘paxos算法是运行在分布式的页面上的？没太理解
我们用一个示例来解释事务提交过程，如图8所示。它有以下步骤:
- 节点1在将block 201分配给文件316后，获得paxos锁，该锁最初是空闲的。
- 节点1开始记录事务到日志。最近写入的条目的位置被标记为pending tail。存储完所有条目后，pending tail就成为日志的有效尾部
- 节点1用修改后的元数据更新超级块。同时，节点2尝试获取已经被节点1持有的互斥锁。节点2一定会失败，稍后将重试。
- 节点1释放锁后，节点2成为互斥锁的合法所有者，但节点1在日志中添加了新条目，这使得节点2的本地元数据缓存已经过期。
- 节点2扫描新条目，释放锁。然后，节点2回滚未被记录的事务并更新本地元数据。最后，节点2重试执行事务。
- 节点3开始自动同步元数据，它只需要加载增量条目，并在本地内存中重放这些条目即可。
7. 设计选择和经验
除了系统架构、I/O模型和共识协议外，还有一些有趣的设计主题值得讨论。它们中的一些属于PolarFS本身，其他的则针对数据库特性。
7.1 集中式和分散式
分布式系统有两种设计模式：集中式和分散式。
- 集中式系统，如GFS[11]和HDFS[5]，包含一个单独的master，该master负责保持元数据和节点间关系管理，这种系统实现是相对简单的，但master可能会在可用性和可伸缩性上成为整个系统的瓶颈。
- 像Dynamo[8]这样的分散系统正好相反，在该系统中，节点是点对点关系，元数据在所有节点之间进行分片和冗余。一个分散的系统应该会更可靠，但也在实现和reasoning方面更复杂。
PolarFS在集中式和分散式设计之间进行了trade-off。一方面，PolarCtrl是一个集中式的master，它负责管理的任务(如资源管理)，并接受控制平面的请求(如创建卷)。另一方面，ChunkServers正在相互交流，运行一个共识协议，在不涉及PolarCtrl的情况下自主处理故障和恢复。
7.2 自底向上的快照
快照是数据库的一种常见需求。PolarFS支持快照特性，这简化了上层的POLARDB快照设计。
在PolarFS中，存储层为上层提供可靠的数据访问服务，POLARDB和libpfs有自己的日志机制来确保他们的事务的原子性和持久性。PolarFS存储层提供 disk outage consistency 的快照，并且POLARDB和libpfs可以通过底层的PolarFS快照重建它们自己的一致性数据映像。
这里的disk outage consistency 是指，如果快照命令是在T时间点触发的，则存在T0时间点，T0之前的所有I/O操作都应该包含在当前快照中，而T之后的I/O操作必须被排除。然而，I/O操作在间隔[T0, T]内的状态是不确定的，这通常是一个非常短的时间跨度。这种行为类似于在磁盘仍在写入时关闭电源所发生的情况。
当意外的灾难发生或需要主动审计时，PolarCtrl将最新的数据快照分配给POLARDB实例，POLARDB和libpfs将使用存储的日志来重建一致的状态。
PolarFS以一种新颖的方式实现了 disk outage consistency 快照，在进行快照时不会阻塞用户I/O操作。当用户发出快照命令时，PolarCtrl通知PolarSwitch进行快照。从那时起，PolarSwitch将一个快照标记添加到后续的请求中，该标记表示它的主机请求发生在快照请求之后。在接收到带有快照标签的请求时，ChunkServer会在处理该请求之前做一个快照。ChunkServer通过复制block映射元信息来进行快照(ChunkServer makes a snapshot by copying block mapping meta information)，这是快速的。处理后续的请求时，采用“写时复制”的方式修改这些block。在带有快照标签的请求完成后，PolarSwitch将停止向传入的请求添加快照标签。（即确定存储层收到快照信号后就不用再传了）
这边是说一份数据要进行快照，会有一个线程去进行快照操作。另一方面对外的服务不停止，如果有对这份数据的修改，就再复制一份全新的该数据，在新的数据上进行修改。对吗？
7.3 外部服务和内部可靠性
工业系统的可靠性是非常重要的，尤其是像PolarFS这样的系统，它正在承担7X24的公共云服务。在这样一个系统中，应该有各种各样的可靠性维护任务，以防止服务和相关收入的损失。对于PolarFS来说，如何足够高效地运行这些任务，并为繁重的用户工作负载提供流畅的服务，是一个很大的挑战。
举一个实际的例子，在ParallelRaft中，当经历一个沉重的工作负载时，leader将持续生成大量的日志，即使在很长一段时间的日志抓取后，follower也无法赶上。由于I/O节流，复制整个数据块的时间也可能相当长且不可预测。这可能会导致我们做出权衡：恢复所需的时间越短，需要的资源就越多，对系统性能的牺牲就越大；然而，如果需要很长时间才能恢复，系统的可用性将面临风险。
我们的解决方案是将一个chunk水平地分割成小的逻辑piece，比如128kb的piece。一个chunk的完整数据同步也被分割成许多小的子任务，每个子任务只负责重新同步单个128 KB的piece。这些更小的子任务的运行时间更短、更可预测。此外，可以在sub-resync-tasks间插入空闲周期，以控制streaming catch up所需的网络/磁盘带宽。
其他耗时的任务，如检查副本之间一致性的完整数据验证例程，也可以以类似的方式实现。我们必须考虑使用同步流控制（synchronization flow control ），以在外部服务质量和PolarFS系统可靠性之间取得平衡。由于篇幅限制，我们将不在这里进一步讨论这种权衡的细节。
8. 评估
我们已经实现了PolarFS，并在阿里云上发布了POLARDB公共数据库服务。在本节中，我们评估和分析了PolarFS和POLARDB的性能和可伸缩性。对于PolarFS，我们通过将其与本地NVMe上的Ext4和Ceph35上的CephFS进行比较，在集群层面对其进行了评估。对于POLARDB，我们将其与我们原来的MySQL云服务RDS和本地Ext4上的POLARDB进行了比较。
8.1 PolarFS 实验准备
略
8.2 I/O延迟
PolarFS 和 CephFS 相较于 Ext4 的延迟比：
| 随机写 | 顺序写 | 随机读 | 顺序读 | |
|---|---|---|---|---|
| PolarFS | 1.6-4.7 | 1.6-4.8 | 1.3-1.8 | 1.5-8.8 |
| CephFS | 6.5-75 | 6.3-56 | 2-4 | 3.4-14.9 |
PolarFS 的性能比 CephFS 好很多，这有几个原因。
- PolarFS 分配了一个线程运用有限状态机处理 I/O，如第 4 节所述。这避免了由多个线程组成的 I/O 管道所需的线程上下文切换和重新调度。
- PolarFS优化了内存分配和分页，内存池用于在一个I/O生命周期内分配和释放内存，减少对象的构造和销毁操作，还使用huge page来减少TLB未命中和分页，CephFS中没有相应的设计。
- PolarFS 中关于数据对象的所有元数据都保存在内存中，而 CephFS 中的每个 PG（Placement Group）只有部分元数据保存在一个小缓存中。因此，对于大多数 I/O 操作PolarFS 不需要额外的元数据 I/O，但 CephFS 有时必须为元数据执行额外的 I/O。
- PolarFS 中的 用户空间 RDMA 和 SPDK 相比于 CephFS 中的内核 TCP/IP 和块驱动程序 具有更低的延迟。
8.3 I/O 吞吐
图 10 显示了三个文件系统的总体 I/O 吞吐量。 对于随机读/写，本地 SSD 上的 Ext4、PolarFS 和 CephFS IOPS 都随客户端作业数扩展； Ext4 的扩展瓶颈是单个本地 SSD IOPS，PolarFS 的瓶颈是网络带宽，而 CephFS 的瓶颈是它的数据包处理能力。 Ext4 和 PolarFS 的随机 4k 写/读 I/O 吞吐量是 4.4/5.1，比 CephFS 高 4/7.7。
对于顺序读/写，几乎所有请求都由本地系统和分布式系统的单个磁盘处理。 Ext4 和 PolarFS 都可以随着客户端作业的数量很好地扩展，直到由于 I/O 瓶颈而达到极限，而 CephFS 的瓶颈是它的软件，它不能使磁盘 I/O 带宽饱和。
在没有额外的网络 I/O 的情况下，在 1 个客户端的情况下，Ext4顺序读取吞吐量远高于 PolarFS 和 CephFS，但随着客户端数量增加到 2，其顺序读取吞吐量急剧下降，吞吐量与两客户端的随机读吞吐量大致相同。 我们多次重复评估，结果可重现。 我们猜测这是由我们的 NVMe SSD 的特性引起的。 NVMe SSD 具有内置的 DRAM 缓冲区。 当固件猜测工作负载看起来像顺序读取时，它会将后续数据块预取到 DRAM 缓冲区中。 我们猜测预取机制在非交错 I/O 模式下会工作得更好。
8.4 评估polardb
除了与 PolarFS 集成外，POLARDB 还应用了一系列基于阿里云 RDS 的数据库优化。 结果显示，POLARDB 的 Read/Write/RW-Mixed 吞吐量几乎是 RDS 的 2.79/4.72/1.53 倍。
9. 相关工作
存储系统
GFS [11] 及其开源实现HDFS [5]，提供分布式系统服务，GFS和HDFS均采用主从架构，master负责维护系统元信息，数据块领导租赁，以及故障恢复。与它们不同，PolarFS采用混合架构。PolarFS的master节点主要负责资源管理，它一般不会介入I/O路径，这使得master升级和容错变得更为容易。
Ceph [35] 是一个广泛部署的存储系统。它使用 CRUSH 哈希算法来定位数据对象，为正常 I/O 执行和容错带来了简单的设计。 RAMCloud [29] 是一个低延迟键值系统，它通过以随机方式在集群之间复制数据并利用集群资源并行恢复故障来提供快速恢复。随机的数据放置会使一台机器在云环境中托管数千个用户的数据，这意味着单机崩溃会影响到数千个用户，这对于云服务提供商来说是无法接受的。在将数据块分配给真实服务器这个方面，PolarFS 的master在故障影响和 I/O 性能之间提供了细粒度的权衡。
ReFlex [20] 使用 NVMe SSD 实现远程磁盘，它提出了一个 QoS 调度器，该调度器可以enforce tail latency and throughput service-level objectives，但与 PolarFS 不同的是，它的远程磁盘是单副本并且没有可靠性支持。 CORFU [3] 将闪存设备集群组织为单个共享日志，多个客户端可以通过网络同时访问该日志。 共享日志的设计简化了分布式环境中的快照和复制，但是增加了现有系统使用CORFU的工程难度，而PolarFS为用户提供了块磁盘抽象和类POSIX的文件系统接口。
Aurora [32] 是 Amazon 在其 ECS 服务之上的云关系数据库服务。 Aurora 将数据库redo log处理下推到存储端，以此来解决计算端和存储端之间的网络性能限制。 Aurora 还修改了 MySQL 的 innodb 事务管理器以改善日志复制，而 POLARDB 在 PolarFS 上进行了大量投资，使用了类似 POSIX 的 API，对数据库引擎本身则几乎没有修改。 Aurora的redo log下推设计打破了数据库和存储层之间的抽象，使得每一层的修改更加困难，而PolarFS和POLARDB保留了每一层的抽象，使得每一层更容易采用最新的技术。
Consensus Protocols
Paxos [22] 是最著名的分布式系统共识算法之一，但是，它难以理解和正确实现。Paxos 的作者只是证明了 Paxos 可以解决一个实例的共识问题，并没有展示如何使用“MultiPaxos”解决实际问题。 目前，大多数共识算法，例如zookeeper使用的Zab [16]，都被认为是“Multi-Paxos”算法的变种。 Zab 用于提供原子广播的原始属性，但也很难理解。 Raft [28] 是为可理解性而设计的，它也是“Multi-Paxos”算法的变种。 它引入了两个主要约束，第一个是提交日志必须是顺序的，第二个是提交顺序必须是序列化的。 这两个约束让 Raft 很容易理解，但同时也引入了对并发 I/O 性能的影响。 一些系统使用多组 raft 来提高 I/O 并行性，将键分成组，但它不能解决提交日志包含跨多个组的键的问题。ParallelRaft通过不同的方式实现这一目标。提交日志允许有漏洞，日志条目可以无序提交，但冲突日志条目除外，冲突日志条目将以严格的顺序提交。
RDMA Systems
与传统的 TCP/UDP 网络协议相比，RDMA 以更少的 CPU 使用率将往返延迟降低了一个数量级，很多新系统使用 RDMA 来提高性能。 FaRM [9] 是一种基于 RDMA 的分布式共享内存，用户可以使用它的程序原语来构建他们的应用程序。 DrTM [34] 是一个基于 RDMA 和硬件事务内存的分布式内存数据库，RDMA 可以快速访问远程端的数据，也可以导致硬件事务内存中的本地事务中止，DrTM 结合 RDMA 和硬件事务内存实现分布式交易。 FaRM 和 DrTM 都专注于内存中的事务，但是 PolarFS 使用 RDMA 来构建分布式存储。
Pilaf [27] 是基于RDMA和自验证数据结构的密钥值存储，但与PolarFS不同，密钥值接口相对简单，并且Pilaf中没有分布式共识协议。
APUS [444] 使用RDMA构建可扩展的Paxos，而PolarFS提供了对高并行I/O友好的Parallel raft。PolarFS使用RDMA来构建可靠的block设备，由于RDMA比传统网络协议消耗更少的CPU，因此PolarFS可以以 run-to-completion的方式处理I/O，从而避免了上下文切换。结合RDMA和SPDK，存储节点可以在整个I/O生命周期中不接触其有效负载而完成I/O，所有有效负载的移动都由硬件完成。
10. 结论
PolarFS 是一种分布式文件系统，提供极高性能和高可靠性。 PolarFS 采用新兴硬件和最先进的优化技术，例如 OS-bypass 和零拷贝，使其具有与 SSD 上的本地文件系统相当的延迟。为了满足数据库应用对 IOPS 的高要求，我们开发了一种新的共识协议 ParallelRaft。 ParallelRaft 在不牺牲存储语义一致性的前提下，放宽了 Raft 严格的写入顺序，提高了 PolarFS 的并行写入性能。在重负载下，我们的方法可以将平均延迟减半，系统带宽加倍。 PolarFS 在用户空间实现了类似 POSIX 的接口，这使得 POLARDB 能够通过微小的修改实现性能提升。
