PolarDB及其分布式文件系统PolarFS的架构实现

PolarDB及其分布式文件系统PolarFS的架构实现

PolarDB是阿里云基于MySQL推出的新一代云原生（Cloud Native）数据库产品，所谓云原生数据库，指的是一种融合了众多创新技术而跨界的云数据库服务，它可以更好地服务于云环境下的应用场景，本质上是云的能力和SQL能力的融合。

因为PolarDB并不开源，所以我们不能从代码层面进行解读，只能从阿里云公开的技术资料以及他们在VLDB 2018上发表的分布式文件系统PolarFS（PolarDB的共享存储文件系统）的论文基础上进行解读和分析。

云原生数据库出现的背景

在云原生数据库出现之前，传统的MySQL RDS已经在云服务上有了尝试，但是在尝试过程中，出现了很多传统MySQL RDS无法解决的痛点问题，比如说：

• 扩展困难。传统MySQL不管是纵向扩展机器硬件，还是横向增加备库都需要迁徙数据，扩展周期比较长，无法从容应对突如其来的业务高峰，这使得数据库服务不能服务于那些负载不确定的应用。
• 成本浪费。传统MySQL的只读库需要拥有一份与主库完全相同的数据副本，用户想要增加只读库的数目，不仅要增加计算成本还要增加存储成本。
• 主从切换时间长。传统MySQL通常采用主从异步复制的HA架构，主从切换后从库可能需要重建，导致切换时间太长，数据库系统长时间不可用。
• 复制延迟高。传统MySQL的读写分离通常采用redolog来进行主从复制，但是这种逻辑复制延迟较高，备库常常会出现读延迟。
• 存储不均衡。在传统的MySQL云服务上，有些机器上可能是大实例，而有些机器上是小实例，往往大实例导致会存储资源不够用，而小实例又浪费了很多存储资源。
• binlog日志。传统的MySQL为了兼容多种存储引擎，记录了两种事务日志（binlog和redolog），binlog 逻辑复制性能较差，不同日志间的一致性管理又会影响系统的性能。

有了上面这些痛点，传统的MySQL RDS渐渐不能满足应用的需求，云原生数据库就应运而生了。

说到云原生数据库，就不得不提到AWS的Aurora数据库。其在2014年下半年发布后，轰动了整个数据库领域。Aurora对MySQL存储层进行了大刀阔斧的改造，将其拆为独立的存储节点(主要做数据块存储，数据库快照的服务器)。上层的MySQL计算节点(主要做SQL解析以及存储引擎计算的服务器)共享同一个存储节点，可在同一个共享存储上快速部署新的计算节点，高效解决服务能力扩展和服务高可用问题。基于日志即数据的思想，大大减少了计算节点和存储节点间的网络IO，进一步提升了数据库的性能。再利用存储领域成熟的快照技术，解决数据库数据备份问题。被公认为关系型数据库的未来发展方向之一。

毫无疑问，其后推出的云原生数据库产品多多少少受收到了Aurora的影响，这其中就包括本文介绍的PolarDB数据库，它也是借鉴了很多Aurora的技术实现，采用了计算和存储分离和全用户态的架构，并且大量使用新硬件。

PolarDB架构

PolarDB在进行架构设计时，遵循四个原则：

• 计算和存储分离；
• 全用户态，零拷贝；
• ParellelRaft，支持乱序确认、乱序提交。
• 大量使用新硬件：RDMA、NVMe、SPDK等等。

上图给出了PolarDB的架构概览，可以看到PolarDB的上层是计算层，下层是存储层，存储和计算是分离的，中间通过RDMA高速网络相连接。在计算层有一个主节点，这个主节点负责处理读写请求，其余是备节点，备节点是只读节点。主节点个所有备节点之间采用的是Shared Everything架构，即共享存储层数据和日志文件。

存储和计算分离之后，相当于将数据库系统一体化的架构做了水平的切分。这样做主要以下几点优势：

• 可以根据计算层和存储层不同的特点去配置不同的硬件和资源。在计算节点，我们更关注的是CPU和内存，而存储层更关注的则是IO的响应时间和成本。
• 存储和计算分离之后，数据库应用的持久状态下沉到存储层，计算层不持有数据，所以数据库实例可以在计算节点上灵活地做各种迁移和扩展。在存储层，PolarDB的存储是一个共享的分布式文件系统，它可以有自己的复制策略来提供较高的数据可用性和可靠性。
• 存储分离之后，存储层上的多个节点的存储资源就可以形成单一的存储池，存储资源池化能够解决传统数据库中存储碎片、节点间负载不均衡以及存储空间浪费等问题。

显然，采用存储和计算分离的架构设计可以完美解决上述传统MySQL RDS的绝大多数痛点问题。虽然存储和计算分离的好处多多，但是目前可用的分布式共享文件系统却寥寥无几，不论是Hadoop生态圈占统治地位的HDFS，还是在通用存储领域风生水起的Ceph，都不能满足数据库系统的性能需求，并且还存在大量与现有数据库系统的适配问题。

因此，想要让数据库系统实现存储和计算的分离的同时还能够具备良好的性能和可靠性，还需要针对数据库来设计专门的分布式文件系统。因此，PolarDB还专门设计了PolarFS（共享的分布式文件系统）来实现上述的存储和计算分离的架构设计。

分布式共享文件系统PolarFS

上面这张图给出了从PolarFS视角下看到的PolarDB的实现架构。简单点来看，PolarDB可以分两个部分：

• 第一部分为数据库服务（上图中的POLARDB），这部分主要是负责客户端SQL请求解析、事务处理、查询优化等数据库服务的计算操作。
• 第二部分为分布式文件系统PolarFS（上图中的libpfs、PolarCtrl、PolarSwitch、ChunkServers），主要负责数据存储、数据IO、数据一致性、元数据管理等数据库服务的存储操作。

第一部分的数据库服务是完全兼容MySQL的，这是传统数据库的知识，我们这里就不做介绍了。第二部分的分布式文件系统PolarFS则是PolarDB数据库实现存储和计算分离最重要的特性和基础，下面会针对其每一个组件进行单独介绍。

PolarFS存储资源的组织方式

在介绍PolarFS各组件的功能之前，我们先介绍一下PolarFS存储资源的组织方式。PolarFS将存储资源分为三层来进行封装和管理，分别为：Volume（卷）、Chunk（区）、Block（块）。

Volume

当用户申请创建PolarDB数据库实例时，系统就会为该实例分配一个Volume（卷），每一个数据库实例就对应一个Volume。每一个Volume由多个Chunks组成，一个Volume的容量大小范围是10GB至100TB，数据库系统可以通过向Volume添加Chunks来按需扩展数据库实例的容量。这也就是说PolarDB支持用户创建的实例大小范围为10GB至100TB，这满足了绝大多数云数据库实例的容量要求。Volume上也存放了文件系统的元数据，这些元数据包括：

• directory entry：目录项，一个目录项保存了一个文件的路径，一个目录项中同时也包含一个inode的引用。所有目录项被组织成了一棵目录树（directory tree）。
• inode：一个inode描述的是一个常规文件或者是一个目录，这表示每一个文件名对应一个indode，不论其表示的是常规文件还是目录。对于常规文件来说，这个inode保存了一组块标记（block tag）的引用，用来指示这个文件存储在哪些块上。而对于一个目录来说，这个inode保存了该父目录中的子目录项。
• block tag：每一个块标记描述了一个文件块号（file block number）到一个卷块号（volume block number）的映射。

在PolarFS中，这三种元数据被抽象为一种叫做元对象（metaobject）的数据类型，用这个公共的数据类型可以用来访问磁盘和内存中的元数据。PolarFS用一个MySQL数据库实例来存储文件系统的元数据，并且在各节点的内存中也缓存这些元数据信息。

由于PolarFS是一种共享访问分布式文件系统，因此还要保证文件系统元数据在各节点之间的一致性，比如一个节点增加、删除了文件，或者是改变了文件的大小，这些更改元数据的操作都要持久化到磁盘中并及时同步到各节点上。为了实现元数据的一致性，PolarFS中每个文件系统实例都有相应的Journal文件和Paxos文件来管理元数据的更新。关于PolarFS元数据的更新、协调和同步会在后面做更加详细地描述。

Chunk

一个Volume分成了多个Chunks，这些Chunks则分布在各个ChunkServers上。Chunk是数据分发的最小单位了，单个Chunk只会存放于存储节点的一个NVMe SSD盘上，它不会跨越ChunkServer出现在多个盘上，并且其副本默认复制到不同机器的三个ChunkServer上，这样做的目的是利于数据高可靠和高可用的管理。使用ParallelRaft（变种的Raft协议，后面会介绍）在保证副本的一致性的同时，还最大化了IO的吞吐量。

在PolarFS中，Chunk的大小被置为10G。选择这么大的容量作为文件系统最小的存储单元可以大大减少元数据的数量，并且还能够简化元数据的管理。同时，这样做可以使元数据方面的缓存在各节点的内存中，从而有效避免了关键IO路径上额外的元数据访问开销。但这样做也有不足，比如当上层应用出现区域级的热点访问时，Chunk内的热点数据无法进一步打散。但由于每个存储节点提供的Chunk数量往往远大于节点数量（节点:Chunk在1:1000量级），同时PolarFS可以支持Chunk的在线迁移，因此可以将热点Chunk分布到不同节点上以获得整体的负载均衡。

Block

在ChunkServers内，Chunk进一步被划分为Block，每个Block的大小为64KB。PolarFS可以根据按需分配Block，并将其映射到Chunk中，以此来实现精简配置。Chunk至Block的映射信息由ChunkServer自行管理和保存，除数据Block之外，每个Chunk还包含一些额外Block用来实现Write Ahead Log。我们也将本地映射元数据全部缓存在ChunkServer的内存中，使得用户数据的I／O访问能够全速推进。

PolarFS的各个组件

介绍完PolarFS存储资源的组织方式后，下面我们来详细介绍PolarFS各组件的功能。

libpfs

libpfs是一个轻量级的用户空间库，PolarFS采用了编译到数据库的形态，替换标准的文件系统接口，这使得全部的I／O路径都在用户空间中，数据处理在用户空间完成，尽可能减少数据的拷贝。这样做的目的是避免传统文件系统从内核空间至用户空间的消息传递开销，尤其数据拷贝的开销，比较典型的例子是：数据库系统向磁盘写入数据之前，需要先写操作系统的文件系统缓存，然后才会真正的写入到磁盘中。这一点对于PolarFS采用的大量低延迟新硬件来说至关重要。

其提供了类POSIX的文件系统接口API（见下图）来访问底层的存储，因而付出很小的修改代价即可完成数据库的用户空间化。

当数据库节点启动时，会调用pfs_mount()挂载其对应的volume，并且初始化文件系统状态，该操作会加载文件系统的元数据并将其缓存在本地计算节点上。数据库系统销毁期间调用pfs_umount()来分离volume并释放资源。在对卷进行扩容后，通过调用pfs_mount_growfs()函数来识别新分配的块，同时增加其空间映射到文件系统中。

PolarSwitch

PolarSwitch是部署在计算节点的Daemon，它负责将I/O请求映射到具体的存储节点上。数据库（POLARDB）通过libpfs将I/O请求发送给PolarSwitch，每个请求包含了数据库实例所在的Volume id、起始偏移和长度。在某些情况下，一个I/O请求可能会需要跨越访问多个Chunks，这时PolarSwitch会进一步将I/O请求划分为多个子请求。最终，PolarSwitch将这些请求发往Chunk的Leader（三副本一致性协议中的主）所属的ChunkServer完成访问。

具体来说，PolarSwitch根据自己缓存的Volume id到Chunk的映射表，知道该I/O请求属于那个Chunk。PolarSwitch还缓存了该Chunk的三个副本分别属于哪几个ChunkServer以及哪个ChunkServer是当前的Leader节点，PolarSwitch只将请求发送给Leader节点。

ChunkServer

ChunkServer部署在存储节点上，一个存储节点可以有多个ChunkServer。每个ChunkServer绑定到一个CPU核，并管理一个独立的NVMe SSD盘，因此ChunkServers之间没有资源争抢。

ChunkServer负责Chunk内的资源映射和读写。每个Chunk都包括一个Write Ahead Log（WAL），对Chunk的修改会先写Log再修改，保证数据的原子性和持久性。ChunkServer使用了一块固定大小的3D XPoint SSD buffer作为WAL的写缓存，Log会优先存放到更快的3D XPoint SSD中，如果3D XPoint buffer不够用，Log才会写入NVMe SSD中。对Chunk中数据的修改都是直接写到NVMe SSD中。

ChunkServer会复制写请求到对应的Chunk副本（其他机器的ChunkServer）上，PolarFS通过自己定义的Parallel Raft一致性协议保证了在各类故障状况下数据的正确同步并且保障已Commit数据不丢失。与此同时，Parallel Raft一致性协议能够更好的支持高并发的I/O。

PolarCtrl

PolarCtrl是PolarFS集群的控制平台，他被部署在一组专用的机器上（至少三个）去提供高可用服务。PolarCtrl还是集群的控制中心，主要负责集群的节点管理、Volume管理、资源分配、元数据同步、监控负载等等。更具体的说，其主要的职责包括：

• 跟踪存储节点上所有ChunkServers的活跃度和将康状况，包括剔除出现故障的ChunkServer，迁移负载过高的ChunkServer上的部分Chunk等；
• 维护元数据库中所有Volume和Chunk位置的状态；
• 创建Volume及Chunk的布局管理，比如Volume上的Chunks应该分配到哪些ChunkServers上；
• Volume至Chunks的元数据信息维护，并将元数据信息同步到PolarSwitch中；
• 监控Volume和Chunk的IO性能，沿着IO路径收集和跟踪数据；
• 定期发起副本内和副本间的CRC数据校验。

PolarCtrl用一个MySQL数据库实例来存储和管理上述文件系统的元数据。

中心统控，局部自治的分布式管理

分布式文件系统的设计有两种范式：中心化和去中心化。中心化的系统包括GFS和HDFS，其包含单中心点，负责维护元数据和集群成员管理。这样的系统实现相对简单，但从可用性和扩展性的角度而言，单中心可能会成为全系统的瓶颈。去中心化的系统如Dynamo完全相反，节点间是对等关系，元数据被切分并冗余放置在所有的节点上。去中心化的系统被认为更可靠，但设计和实现会更复杂。

PolarFS在这两种设计方式上做了一定权衡，采用了中心统控，局部自治的方式：PolarCtrl是一个中心化的控制平台，其负责集群的管理任务。ChunkServer负责Chunk和Bolck内部映射的管理，以及Chunk间的数据复制。当ChunkServer彼此交互时，通过ParallelRaft一致性协议来处理故障并自动发起Leader选举，这个过程无需PolarCtrl参与。

PolarCtrl服务由于不直接处理高并发的IO流，其状态更新频率相对较低，因而可采用典型的多节点高可用架构来提供PolarCtrl服务的持续性，当PolarCtrl因崩溃恢复出现的短暂故障间隙，由于PolarSwitch的缓存以及ChunkServer数据层的局部元数据管理和自主leader选举的缘故，PolarFS能够尽量保证绝大部分数据IO仍能正常服务。

PolarFS的IO流程

当上层的数据库服务（POLARDB）需要访问下层数据的时候，它将通过调用libpfs的API接口将IO请求下发到下层的文件系统，通常调用的是pfs_pread()和pfs_pwrite()这两个接口。对于写请求来说，几乎是不需要修改文件系统的元数据，这是因为在此之前libpfs已经调用pfs_posix_fallocate()接口预分配了足够的存储Chunks给了相关文件，从而避免了读写节点和只读节点之间昂贵的元数据同步，这是数据库系统中常见的优化措施。

在大多数常见情况下，libpfs只是根据启动挂载时已经构建的索引表将文件偏移量映射到块的偏移量，并将IO请求切分为一个或者多个更小的块IO请求。在切分后，这些块IO请求由libpfs通过共享内存发送到PolarSwitch。此共享内存的构造为多个环形的缓冲区（Ring Buffer）。在环形缓冲区的一端，libpfs将块IO请求加入这个缓冲区内，并等待此IO请求的完成；在另一端，PolarSwitch用专用线程去不断轮询所有的环形缓冲区，一旦其发现了新的IO请求，它就会将它们从缓冲区中取出，并根据本地缓存的路由信息（PolarCtrl同步的）将它们转发到对应的ChunkServer上。

写IO请求流程

上图显示了一个写IO请求是如何在PolarFS内部执行的。具体的步骤为：

• POLARDB通过libpfs发送一个写IO请求，经由ring buffer发送到PolarSwitch；
• PolarSwitch根据本地缓存的元数据，将请求发送至对应Chunk的Leader节点（ChunkServer1）；
• 请求到达ChunkServer1后，节点上的RDMA NIC将此请求放到一个预分配好的内存buffer中，并将该请求对象加到请求队列中。一个IO轮询线程不断轮询这个请求队列，一旦发现有新请求则立即开始处理；
• IO处理线程通过异步调用将此请求通过SPDK写到Chunk对应的WAL日志块上（通常是 3D XPoint SSD buffer），同时将该请求通过RDMA异步发给Chunk的Follower节点（ChunkServer2、ChunkServer3）。由于都是异步调用，所以数据传输是并发进行的；
• 当请求到达ChunkServer2、ChunkServer3后，同样通过RDMA NIC将其放到预分配好的内存buffer并加入到复制队列中；
• Follower节点上的IO轮询线程被触发，该请求通过SPDK异步地写入该节点的Chunk副本对应的WAL日志块；
• 当Follower节点的写请求成功后，会在回调函数中通过RDMA向Leader节点发送一个确认响应；
• Leader节点收到ChunkServer2、ChunkServer3任一节点成功的应答后，即形成Raft组的majority。主节点通过SPDK将该请求写到指定的数据块上；
• 随后，Leader节点通过RDMA NIC向PolarSwitch返回请求处理结果；
• PolarSwitch标记请求成功并通知上层的POLARDB返回客户端。

读IO请求流程

读IO请求无需这么复杂的步骤，lipfs发起的读IO请求直接通过PolarSwitch路由到数据对应Chunk的Leader节点（ChunkServer1），从其中读取对应的数据返回即可。需要说明的是，在ChunkServer上有个子模块叫IoScheduler，用于保证发生并发读写访问时，读操作能够读到最新的已提交数据。

全用户态的IO处理

PolarFS用全用户态的设计来处理IO请求，任何逻辑都跑在用户态。一个请求从数据库引擎发出，然后libpfs会把它映射成一组IO请求，之后PolarSwitch会把这些请求通过RDMA发送到存储层，随后ParellelRaft 的leader节点处理这些请求并通过SPDK持久化到日志磁盘上，同时再通过RDMA同步两份数据到两个followers，最后leader将这些请求通过SPDK写到数据磁盘上。在这整个过程上全都是应用调用，并没有系统调用，这也就没有上下文切换，同时也没有多余的数据拷贝，没有上下文切换加零拷贝使得POLARDB拥有了很好的性能。

当然，实现全用户态的IO处理离不了大量新硬件的加持，可以说POLARDB性能优势基本上就是来自于全用户态的架构和大量新硬件的加持，而这点也是相辅相成的。

基于ParallelRaft的一致性模型

PolarFS设计了基于Raft的ParallelRaft一致性协议来适应更大规模的容错和分布式文件系统。相对Raft协议，ParallelRaft不仅能够保证在极端情况下数据的可靠性，还能够提供更高的IO并发处理。

Raft协议的关键特性

• Leader选举安全特性：Raft 协议保证了在任意一个任期（term）内，最多只有一个 leader，新leader节点拥有以前term的所有已提交的日志，保证选举之后不会丢失已提交的数据。
• 日志匹配原则：Raft协议保证每个副本日志append的连续性；当leader发送一条log 给follower，follower需要返回ack来确认该log项已经被收到且持久化，同时也隐式地表明所有之前的log项均已收到且持久化。
• Leader Append-only 原则：Raft协议中leader日志的提交（commit）也是连续的；当leader commit一条log项并广播至所有follower，它也同时确认了所有之前的log项都已被提交了。

Raft 的这些关键特性时相互关联和满足的，比如说这里的Leader选举安全特性是由日志匹配原则和Leader Append-only 原则保证的，如果这两个特性被破坏，Raft协议的Leader选举安全性也就被破坏，这可能会导致选主后数据的不一致。

Raft协议的缺陷

为了选举的安全性和易于理解，Raft设计成了高度串行化的协议。Leader和Follower的日志都不允许出现空洞，这也就是说所有的Log都是由follower按序确认、leader按序提交并按序应用（apply）于所有副本，所有这些操作都是顺序的。这样当写请求并行执行的时候，也要按照顺序提交。队列前面的请求还没有处理，在队列尾部的请求就不能提交和确认，这样就增大了平均延迟和吞吐。

整个过程的按序串行的操作导致了Raft协议不适合多连接并行场景，比如当Leader和Follower之间有多个连接，如果某个连接卡住了或者变慢了，备机就会收到乱序的日志，此时提前到达的后序Log也不能及时确认，一直要到那些先前丢失的Log到达才可以按序应答。此外，当大多数Follower因为一些丢失的Log被阻塞时，Ledar上就不能提交了。

在实际场景中，在高并发环境下，使用多个连接并行的方式来提升并发吞吐量是很常见的。ParallelRaft就是在Raft协议的基础上解决了这个问题。

ParallelRaft的乱序日志复制

为了消除Raft协议的性能瓶颈，就要打破它的有序原则，也就是要打破Raft协议的日志匹配原则原则和Leader Append-only原则，但是还不能破坏Leader选举的安全性。ParallelRaft做到了日志的乱序复制，即当某条log项成功提交时，并不意味着它之前的所有日志项都已经成功提交。

ParallelRaft乱序日志复制的主要特性：

• 乱序确认（Out-of-Order Acknowledge）：一旦log项持久化成功，follower不用等它之前的log持久化完成就可以立即给leader确认应答，这样减少了平均延迟时间。
• 乱序提交（Out-of-Order Commit）：某条log项收到大多数follower确认应答之后，leader不用等它之前的log的多数应答完成就可以立即提交这条log项。

ParallelRaft做到了日志的乱序复制，即当某条log项成功提交时，并不意味着它之前的所有日志项都已经成功提交。虽然ParallelRaft通过日志的乱序确认和提交大大提升了数据库的吞吐量，但是没有这些串行化的限制也会引入两个新的问题：

• 应用带空洞的日志：因为log不是按序确认提交的，所以log也不是按序写入的，会出现带有空洞的日志（后序的log先写入）。面对带空洞的日志，怎么保证日志应用的正确性？这也就是说应用乱序提交的日志（有空洞的日志）也要保证数据库存储的数据和状态是正确的，不能因为乱序提交就出现数据库语义的不一致。
• Leader的选举安全特性被破坏：因为Leader的日志是乱序提交的，会出现带空洞的日志。这样就保证不了选主后新Leader节点拥有以前任期内的所有已提交的日志，这破坏了Raft协议的Leader选举安全特性，所以在选主后可能会丢失已提交的数据。

应用带空洞的日志（Apply with Holes in the Log）

为了解决应用带空洞的日志的问题，ParallelRaft引入了一个新的数据结构：look behind buffer，每一条日志项都会包含该数据结构。look behind buffer包含前面N条日志修改的逻辑块地址(Logical Block Address)，这使得look behind buffer就像是一座架在日志空洞上的桥，N是这个桥的长度，就是允许出现的最大空洞长度。

虽然日志中可能存在多个空洞，但是所有日志项的逻辑块修改地址的汇总信息总是完整的，有了look behind buffer就可以拥有完整序列化话的逻辑块修改地址信息，除非有空洞的长度比N大。这个N可以根据实际使用场景做配置，PolarDB测试结果显示N设置为2就已经完全能够满足它的IO并发度。

在应用空洞日志的时候，就可以根据look behind buffer确定先后提交的日志是否会产生冲突，这保证了当前应用的日志修改的逻辑地址不会与某些先序日志后提交的日志修改的逻辑块地址产生重叠。这样，与先序日志无冲突的日志可以安全的应用，否则就加到一个pending列表中，稍后等先序日志到达后再做应用。

综上所述，ParallelRaft利用look behind buffer完美解决了空洞日志的应用问题。

Leader选举的安全

跟Raft的选举模式一样，ParallelRaft也是选择拥有最新任期（term）和最多日志项的节点为主。但由于ParallelRaft采用乱序的日志复制，导致了选出来的新主的日志可能会存在空洞，这使得选举的安全性被破坏，即不能保证新Leader节点拥有以前任期内的所有已提交的日志，至于为什么要保证选举的安全性，可以去看看Raft的论文，主要就是为了在复制（实现主备一致性）的时候不丢失已经提交的数据。

为了解决Leader的选举安全特性被破坏的问题，ParallelRaft在选主的过程中增加Merge阶段来填补新Leader日志的空洞。

上图显示ParallelRaft选主的过程。首先，Follower Candidate会将自己本地的日志项发送给Leader Candidate，Leader Candidate接收到这些日志项后与自己本地的日志项合并（merge）。其次，Leader Candidate将合并后的状态与Follower Candidate进行同步。之后，Leader Candidate可以提交所有的合并后的日志项，并通知Follower Candidate提交日志。最后，Leader Candidate正式升级为Leader，与此同时Follower Candidate也升级为Follower。

在合并阶段，并不是简单的把日志的空洞给补上就可以了，这里还需要一套完善的机制来保证填补的日志空洞必须是在前一任期内已经持久化到大多数节点上的，这代表这些日志是已经有效的数据。这套机制包括：

• 如果Leader Candidate上的日志空洞缺失的是已经提交的日志项（该日志被旧主提交），那么一定可以从当前的Follower Candidate中找回来，因为已提交的日志项总是已经被集群中大多数节点持久化，而多数派与Follower Candidate一定存在交集，所以一定可以找回来填补这个空洞。
• 如果Leader Candidate上的日志空洞缺失的是未提交的日志项（该日志未被旧主提交），并且这个日志项也没有在任何一个Follower Candidate中持久化，则可以直接跳过这个日志项。因为该条日志在选主前并没有被大多数节点持久化，认为是无效数据。
• 如果Leader Candidate上的日志空洞缺失的是未提交的日志项（该日志未被旧主提交），而这个日志项在某些Follower Candidate中被持久化，则Leader Candidate就选择最高任期的日志项（index号是一样的）填补这个空洞，认为此日志项是有效的。

Merge过程的核心就是要确定本机的空洞日志状态是如何的。对于被旧主提交过的日志，我们要保证其不能丢。而对于被旧主提交过的日志，只要是其被集群中某些节点持久化了，我们就可以认为其是有效日志，这不会影响数据库语义的一致性。

ParallelRaft的选主过程在经过了Merge阶段之后，新Leader节点就拥有了之前任期的所有已提交的日志项，可以看出来这个过程其实就是一个basic paxos。其实，Raft协议的设计初衷就是利用日志的连续性简化Leader的选举过程，牺牲了一定的性能换来协议的简洁性，看来还是鱼和熊掌不能兼得啊！

PolarFS元数据的协调和同步

在前面介绍PolarFS存储资源的组织方式和各组件功能的时候我们提到过，PolarFS将三种元数据（directory entry、inode、block tag）被抽象为一种叫做元对象（metaobject）的数据类型，这个公共的数据类型可以用来访问磁盘和内存中的元数据。PolarFS用一个MySQL数据库实例来存储文件系统的元数据，并且在各节点的内存中也缓存这些元数据信息。

由于PolarFS是一种共享访问分布式文件系统，因此还要保证文件系统元数据在各节点之间的一致性，比如一个节点增加、删除了文件，或者是改变了文件的大小，这些更改元数据的操作都要持久化到磁盘中并及时同步到各节点上。

更新元数据和更新普通数据一样，我们也要保证修改数据的事务性。所以，在PolarFS中元数据的更新都被视为事务操作，事务操作中保存了修改对象的旧值和新值，在完成所有更新即可提交事务。为了在分布式环境下实现元数据更新一致性，PolarFS在提交过程中还需要一个合理的协调和同步机制。如果提交失败，则可以让元数据事务回滚到旧值的状态。

PolarFS的每个数据库实例都有相应的Journal文件和与之对应的Paxos文件。Journal文件记录了文件系统元数据的修改历史（相当于元数据修改的日志），作为共享实例的各个计算节点之间元数据同步的中心。Journal文件逻辑上是一个固定大小的循环buffer，数据库的只读节点都会轮询该buffer来获取新的元数据更新事务，一旦在Journal中发现了新的元数据更新，各个只读节点就会应用这个事务日志来更新本地缓存的元数据。

由于Journal文件对于PolarFS非常关键，它们的修改必需被Paxos互斥锁保护。正常情况下，只有一个读写节点会去写Journal文件，而其他的只读节点只会去读它。但是在网络分区管理的情况下，可能会有多个节点去写Journal文件。在这种情况下，就需要一个合理的机制去协调针对Journal文件的写入。PolarFS在Paxos文件中继承了Disk Paxos算法，这使得它可以被原子地进行读和写，从而实现了Journal分布式互斥访问。如果一个节点希望在journal中追加项，其必须使用Disk Paxos算法来获取Paxos文件中的锁。通常，锁的持有者会在记录持久化后马上释放锁。但是一些故障情况下（比如读写节点crash）持有者不释放锁，为此在Paxos互斥锁上还维持有一个租约lease，租约过期后其他竞争者可以重启锁竞争过程。

上图用一个例子展示了PolarFS元数据的更新和同步的事务提交流程：

• Node 1是读写节点，其调用pfs_fallocate()接口将Volume的第201个block分配给FileID为316的文件后，通过Paxos文件请求互斥锁，并顺利获得锁；
• Node 1开始记录事务至Journal中。最后写入的项标记为pending tail，当所有的项记录完成之后，pending tail变成Journal的有效tail。
• Node1更新superblock，记录修改的元数据，此过程相当于写数据而不是写日志，写Journal文件相当于写日志。与此同时，node2尝试获取访问互斥锁，由于此时node1拥有的互斥锁，Node2会失败并在稍后重试。
• Node2在Node1释放lock后拿到锁（可能此时产生网络分区，Node2也成为了读写节点），但Journal中Node1追加的新项决定了Node2的本地缓存的元数据是过时的。
• Node2扫描新项后释放lock。然后Node2回滚这个未记录的事务并更新本地的元数据，最后Node2进行事务重试。
• Node3是只读节点并开始同步元数据，其只需要加载Journal文件中的增量项并在本地内存中重放即可。

PolarFS的元数据更新机制非常适合PolarDB一写多读的典型应用扩展模式。正常情况下一写多读模式没有锁争用开销，只读实例可以通过原子IO无锁获取Journal信息，从而使得PolarDB可以提供近线性的QPS性能扩展。

由于PolarFS支持了基本的多写一致性保障，当读写实例出现故障时，POLARDB能够方便地将只读实例升级为读写实例，而不必担心底层存储产生不一致问题，因而方便地提供了数据库实例Failover的功能。

PolarDB的物理复制

从上面的介绍来看，PolarFS采用了计算和存储分离的架构，上层的计算节点共享下层的存储池里的日志和数据。这也就是说，计算层的读写节点和只读节点共享了存储层的数据和日志。那么是不是只要将只读节点配置文件中的数据目录换成读写节点的数据目录，数据库系统就可以直接工作了呢？

实际上，PolarFS在和MySQL做适配的时候还会存在一系列的问题，比如：

• 缓存一致性问题。如果在读写节点上修改数据，由于InnoDB buffer pool的缓存机制，修改的脏数据页还没有被flush到底层磁盘存储中，而这时如果只读节点上的查询就看不到这些脏数据；即使读写节点将脏数据刷到了磁层磁盘，只读节点也会有优先查询本地buffer pool中缓存的旧数据。
• 多版本一致性读问题。InnoDB通过Undo日志来实现事务的MVCC，读写节点在进行Undo日志Purge的时候并不会考虑此时在只读节点上是否还有事务要访问即将被删除的Undo Page，这就会导致记录旧版本被删除后，只读节点上事务读取到的数据是错误的。
• DDL问题。读写实例上执行DDL语句改变了底层存储的文件状态，会造成只读节点访问底层存储出错。比如，只读节点删除一个表，反映到底层存储上就是删除相关的表文件，而此时只读节点上如果有针对这个表的事务操作，就会因为访问不到这个表的底层文件而出错。

因此，多个计算节点共享同一份数据并不是一件容易的事情。为了解决上述问题，PolarDB显然还需要有一套完善的主从同步复制机制。在MySQL中，原先是通过Binlog同步的方式来实现主从的逻辑复制。然而在PolarDB中，为了提升数据库本身和主备复制的性能，放弃了binlog的逻辑复制，取而代之的是基于Redo log的物理复制机制。

有了基于Redo log的物理复制，不仅可以解决缓存的一致性问题，还大大提升了复制的性能。一方面，得益于计算和存储分离的架构，在复制的时候只需要更新只读节点缓存中的数据页（过滤了很多没有缓存的数据页），并且物理复制的速度也比逻辑复制快很多。因此，PolarDB可以大大降低主备之间的复制延迟，甚至在某些情况下可以做到主备之间的强同步。

• 但针对一些特殊的问题，还需要一些额外的处理，比如上述的多版本一致性读问题和DDL问题：
  针对多版本一致性读问题，有两种处理方式：一种是所有只读节点定期向读写节点汇报自己的最大能删除的Undo数据页，由读写节点统筹安排Purge操作；另外一种是当读写节点删除Undo数据页时候，只读节点接收到Redo log同步日志后，会判断即将被删除的数据页是否还在被使用，如果在使用则等待，超过一个时间后直接给客户端报错。
• 针对DDL问题，如果主库对一个表进行了表结构变更操作（DDL操作），在操作返回成功前，必须通知所有的只读节点(有一个最大的超时时间)，这个表的结构已经发生了变化。当然，这种强同步操作会给性能带来极大的影响，有进一步的优化的空间。

虽然物理复制能带来性能上的巨大提升，但是逻辑日志由于其良好的兼容性也并不是一无是处，所以PolarDB依然保留了Binlog的逻辑，方便用户开启。

参考
PolarFS: An Ultra-low Latency and Failure Resilient Distributed File System for Shared Storage Cloud Database
阿里云PolarDB及其共享存储PolarFS技术实现分析（上）
阿里云PolarDB及其共享存储PolarFS技术实现分析（下）
PolarDB · 新品介绍 · 深入了解阿里云新一代产品 PolarDB
从架构深度解析阿里云自研数据库POLARDB
面向云数据库，超低延迟文件系统PolarFS诞生了
PolarFS的ParallelRaft
PolarFS中的ParallelRaft

今天的文章PolarDB及其分布式文件系统PolarFS的架构实现分享到此就结束了，感谢您的阅读。