阿里云操作系统团队、阿里云数据库团队以及上海交通大学新兴并行计算钻研核心一起单干的论文“Async-fork: Mitigating Query Latency Spikes Incurred by the Fork-based Snapshot Mechanism from the OS Level”被数据库系统畛域顶会 Very Large Data Bases Conferences (VLDB)录用为长论文。VLDB 从 1975 年开始举办，属于计算机数据库系统畛域顶级会议（CCF A 类），均匀录用率为 18.6%。
摘要
得益于超快的查问速度，内存键值对数据库（In-memory key-value store, 下称 IMKVS）被宽泛应用于提早敏感的在线应用程序中。
为了反对数据长久化，风行的 IMKVS（例如 Redis 与 KeyDB）应用零碎调用 fork 定期获取内存数据的快照。然而，这种基于 fork 的快照机制可能会引发在快照生成期间达到的查问提早大幅减少，进而影响在线程序的服务质量。这是因为 IMKVS 引擎在调用 fork 期间陷入内核态，为了保证数据的一致性，在此期间无奈解决用户查问申请。而当 IMKVS 内存占用较大时，fork 调用过程耗时十分长。
为此，咱们优化了 fork，这能够在不批改 IMKVS 的根底上，解决快照期间查问提早大幅减少的问题。
具体而言，咱们设计了一个新的 fork（称为 Async-fork），将 fork 调用过程中最耗时的页表拷贝局部从父过程挪动到子过程，父过程因此能够疾速返回用户态解决用户查问，子过程则在此期间实现页表拷贝。为了放弃父子过程之间的数据一致性，咱们设计了一套高效的被动同步机制。试验结果表明，与 Linux 中的默认 fork 相比，Async-fork 显著缩小了快照期间达到申请的尾提早（在 8GB IMKVS 实例上，p99 提早缩小了 81.76%；在 64GB 的实例上 p99 提早缩小了 99.84%）。
问题介绍
对于 IMKVS 而言，因为所有数据都驻留在内存中，数据长久化是实现数据备份与容灾的要害性能。风行的 IMKVS（Redis 与 KeyDB）实现数据长久化的形式是应用零碎调用 fork 获取内存中数据在某工夫点上的快照，并将快照转储到硬盘中。
如图 1(a)所示，父过程调用 fork 创立子过程，而子过程保有与父过程在调用 fork 的时刻雷同的数据。随后，子过程在后盾将数据写入硬盘，而父过程则持续解决用户的查问申请。只管这样的快照机制曾经将沉重的 IO 工作从父过程委派给子过程，但依然可能导致在 fork 调用期间达到的申请的提早激增（例如，图 1(a)中在 T0 时刻达到的申请）。
这是因为父过程在调用 fork 期间陷入内核态，无奈解决用户查问申请。因为 fork 调用的耗时随过程内存的占用增大而增大，提早激增的景象随 IMKVS 内存占用的增大而变得更为严重。试验表明，在 64GB 的 Redis 实例上，非快照期间申请的 p99 提早与最大提早别离为 0.08ms 与 6.46ms，而在快照期间申请的 p99 提早与最大提早别离为 911.95ms 与 1204.78ms。
图 1：The workflow of the parent and child process with(a)default fork,(b)shared page table(SPT)-based fork,(c)the proposed Async-fork in the snapshot procedure.
在默认 fork 的调用过程中，父过程须要将许多过程元数据（例如文件描述符、信号量、页表等）复制到子过程，而页表的复制是其中最耗时的局部（占据 fork 调用耗时的 97% 以上）。先前的研究者提出了基于共享页表的 fork 优化办法，这种办法倡议以写时复制（Copy-on-write, 下称 CoW）的形式在父子过程之间共享页表。
如图 1(b)所示，在共享页表计划中，页表复制不在 fork 调用期间进行，而是在未来产生批改时再进行复制。尽管共享页表可能很大水平上解决提早激增问题，但咱们的分析表明这样的设计在 IMKVS 中导致父过程从 fork 调用中返回用户态后频繁中断陷入内核态实现页表复制，对性能造成了不利影响。此外，共享页表还引入了数据透露破绽，这个破绽可能导致子过程持有与父过程不统一的数据，毁坏了快照一致性。因而，共享页表办法不适用于解决提早激增问题。
Async-fork 的核心思想与挑战
咱们提出了另一种 fork 的优化办法（称为 Async-fork），总体设计思路如图 1(c)所示。Async-fork 设计的核心思想是将复制页表的工作从父过程转移到子过程。这能够缩短父过程调用 fork 时陷入内核态的工夫，可能尽快返回用户态解决用户的查问申请，从而解决提早激增问题；另一方面，还确保了父过程和子过程都具备独占页表，从而防止引入数据透露破绽。
然而，实现上述设计并非易事。如图 2 所示，咱们面临的首要挑战是页表的异步操作可能导致快照不统一。以图 2 中的①为例，IMKVS 在 T0 时刻拍摄快照，而某个用户申请在 T2 时刻向 IMKVS 插入了新的键值对（k2, v2)，这导致父过程批改它的页表项（PTE2）。当这个被批改的页表项尚未被子过程复制时，新插入的键值对将被子过程最终写入硬盘，毁坏了快照一致性。因而，咱们在 Async-fork 中设计了一种被动同步机制，使父过程在批改页表项前，被动将被批改的页表项复制到子过程。
实际上，除了用户申请可能导致页表项批改外，操作系统中的许多内存操作都会引起页表项批改。例如，操作系统会定期在 NUMA 节点之间迁徙页面，导致波及的页表项被批改为不可拜访（图 2 中的②）。因而，被动同步机制必须捕捉父过程中所有可能的页表项批改操作，以严格保障一致性。
另一方面，Async-fork 执行的过程中可能会呈现谬误。例如，因为内存不足，子过程可能无奈复制页表项（图 2 中的③）。因而，咱们在 Async-fork 中退出了错误处理。如果 Async-fork 执行的过程中产生谬误，咱们保障将父过程复原到它调用 Async-fork 之前的状态。
图 2：The challenges in Async-fork.
Async-fork 的设计详解
在详解 Async-fork 的设计之前，首先简要介绍 Linux 虚拟内存的相干常识。过程有本人的虚拟内存空间，Linux 应用一组虚拟内存区域（Virtual memory area, 下称 VMA）来形容过程的虚拟内存空间。一个 VMA 形容虚拟内存空间中的一片间断区域。页表是用于将虚拟内存映射到物理内存的数据结构。页表由若干页表项（Page table entry，下称 PTE）组成，PTE 保护着虚拟地址到物理地址的转换信息和拜访权限。
为了升高内存老本，页表以多级基数树的形式存储，而 PTE 位于最初一级的叶节点，如图 3 所示。页表最多有五级，从上到下顺次为 PGD 级、P4D 级、PUD 级、PMD 级和 PTE 级。因为 P4D 通常是禁用的，因而咱们在本文中仅关注其余四级。每级中的一个节点是一个物理页，它是一个存储了若干项的表。每个项蕴含一个物理页的地址，而该物理页将作为下一级节点。当页大小设置为 4KB 时，每个级别中的表蕴含 512 个项。对于一个 VMA，存在一系列与之对应的 PTE，它们翻译了这个 VMA 中的所有虚拟地址，咱们将这些 PTE 称为“VMA 的 PTE”，而“VMA 的 PMD 项”则是树中这些 PTE 的所有父级 PMD 项的汇合。
图 3：The organization of the page table.
运行过程
算法 1 形容了 Async-fork 中父过程与子过程的运行过程。在默认 fork 中，父过程遍历每个 VMA，将每个 VMA 复制到子过程，并自上而下地复制该 VMA 对应的页表项到子过程。在 Async-fork 中，父过程同样遵循上述过程，但只负责将 PGD、PUD 这两级的项复制到子过程（Line 1 to Line 5）。
随后，父过程将子过程搁置到某个 CPU 上使子过程开始运行，而父过程返回到用户态（Line 7 to Line 14），如果在此期间检测到了 PTE 批改，则会触发被动同步机制，该机制用以确保 PTE 在批改前被复制到子过程，咱们将在下文详解被动同步机制。对于子过程而言，它遍历每个 VMA，并从父过程复制 PMD 项和 PTE（Line 15 to Line 24）。
被动同步机制
父过程返回用户态后，父过程的 PTE 可能被批改。因为只有父过程可能感知到这些批改，有两种形式能够确保该 PTE 被批改前被复制到子过程：
1）父过程被动地将该 PTE 复制到子过程，随后执行批改。
2）父过程告诉子过程复制该 PTE，期待复制实现，随后执行批改。因为这两种形式都会导致父过程期待且等待时间雷同，咱们抉择了前一种形式。
当一个 PTE 将被批改时（如何检测 PTE 批改将在下文详解），咱们抉择让父过程不仅复制这一个 PTE，还同时将位于同一个表上的所有 PTE（一共 512 个 PTE），连同它的父级 PMD 项复制到子过程。以图 4 为例，所有 PGD 与 PUD 条目均已被复制到子过程，而父过程中的 PTE1 将被批改。此时，父过程会将 PMD2、PTE0、PTE1 都复制到子过程。
图 4：An example of copying page table in Async-fork.”RW-1″represents writable and“RW=0″represents writeprotected.
防止反复复制——实际上，即便父过程中的 PTE 产生批改，也并不是总是须要将其复制给子过程，因为子过程可能曾经复制过这个 PTE 了。为防止不必要的复制，咱们应用 PMD 项上的 RW 位来标记是否被复制。具体而言，当父过程第一次返回用户态时，它所有 PMD 项被设置为写爱护（RW=0），代表这个 PMD 项以及它指向的 512 个 PTE 尚未被复制到子过程。当子过程复制一个 PMD 项时，通过查看这个 PMD 是否为写爱护，即可判断该 PMD 是否曾经被复制到子过程。如果尚未被复制，子过程将复制这个 PMD，以及它指向的 512 个 PTE。
在实现这个过程后，子过程将父过程中的该 PMD 设置为可写（RW=1），代表这个 PMD 项以及它指向的 512 个 PTE 曾经被复制到子过程。当父过程触发被动同步时，也通过查看 PMD 项是否为写爱护判断是否被复制，并在实现复制后将 PMD 项设置为可写。因为在复制 PMD 项和 PTE 时，父过程和子过程都锁定 PTE 表，因而它们不会同时复制同一 PMD 项指向的 PTE。
检测 PTE 批改——PTE 的批改既可能由用户操作导致，也可能由操作系统的内存操作导致。咱们将 PTE 的批改分为两类：
1）VMA 级的批改。有些操作作用于特定的 VMA，包含创立、合并、删除 VMA 等。VMA 的批改也可能导致 VMA 的 PTE 被批改。例如，用户发送查问删除大量键值对，而后 IMKVS（父过程）通过 munmap 回收对应的虚拟内存空间。
2)PMD 级的批改。例如，父过程的页可能因为内存不足被 OOM killer 回收。在 VMA 级的批改中，多个 PMD 项被波及，而在 PMD 级的批改中仅有一个 PMD 项被波及。表 1 总结了这些操作，并列出了这些操作中产生批改行为的函数（checkpoint）。
表 1：0perations that may modify VMAs/PTEs.
咱们在这些函数中插入了代码实现 PTE 批改检测。一旦这些函数被执行，父过程查看批改是否波及未复制的 PMD 项和 PTE（通过查看 PMD 是否写爱护），并将未复制的项复制到子过程。在 VMA 级的批改中，如果一个 VMA 形容了相当大的虚拟内存空间，父过程可能会破费绝对较长的工夫遍历查看这个 VMA 的 PMD 项。
为了减小查看开销，咱们在父子过程的 VMA 上引入双向指针，帮忙父过程疾速判断一个 VMA 的所有页表项是否曾经复制到子过程。每个 VMA 数据结构中被增加了一个指针，在 Async-fork 调用时由父过程初始化。父过程 VMA 中的指针指向子过程的 VMA，而子过程 VMA 中的指针指向父过程的 VMA，如图 4 所示。
通过这种形式，双向指针在父子过程的 VMA 间创立了连贯。如果一个 VMA 的所有页表项都被复制到子过程，则连贯被断开。具体而言，如果在子过程复制一个 VMA 的 PMD 项和 PTE 的过程中，父过程中未产生 VMA 级的批改，则子过程在复制操作实现后断开连接。否则，意味着父过程中产生了 VMA 级的批改，父过程将负责复制这个 VMA 的 PMD 项和 PTE 到子过程，并在复制实现后断开连接。
通过这种形式，当父过程中产生 VMA 级的批改时，父过程能够首先查看该 VMA 的指针连贯，以疾速判断该 VMA 的页表项是否已被全副复制。对于页表项曾经全副被复制的 VMA，父过程不再须要查看它的所有 PMD 项。双向指针还用于错误处理，将在下文形容。
错误处理
Async-fork 在复制页表时波及到内存调配，因而会产生谬误。例如，因为内存不足，过程可能无奈申请到新的 PTE 表。当谬误产生时，咱们应该将父过程复原到它调用 Async-fork 之前的状态，即确保父过程不会因为失败调用了 Async-fork 而产生扭转。
在 Async-fork 中，父过程 PMD 我的项目的 RW 位可能会被批改。因而，当产生谬误时，咱们须要将 PMD 项全副回滚为可写。谬误可能产生在：1) 父过程复制 PGD 项与 PUD 项时，2) 子过程复制 PMD 项与 PTE 时，以及 3) 在父过程触发被动同步期间。
对于第一种状况，父过程负责回滚所有写爱护的 PMD。对于第二种状况，子过程负责回滚所有残余的未复制的 PMD 我的项目，随后发送 SIGKILL 信号。当子过程返回用户态时，将接管到该信号并被杀死。对于第三种状况，父过程仅负责回滚正在复制的 VMA 中的 PMD 项，而后将错误代码存储到该 VMA 的双向指针中。子过程在复制 VMA 的 PMD 项与 PTE 之前（或实现复制之后），都会查看 VMA 中的双向指针中是否存在错误码。如果子过程遇到错误码，它立刻进行复制，并执行第二种状况的错误处理行为。这样能够防止谬误处理过程中父子过程之间的锁争用。
Async-fork 的实现及优化
图 5：The implementation of Async-fork.
图 5 形容了 Async-fork 在 Linux 中的实现。咱们向 fork 调用门路与内存子系统中的一些函数插入了钩子（hook）函数，钩子函数的函数体则封装到内核模块中。模块化实现容许维护者在运行时随时插入、卸载模块，以随时批改 Async-fork。钩子函数由默认 fork 调用门路上的 copy_page_range 函数改良而来，它通过接管一个参数（Fast 或 Slow）来管制页表复制行为。
灵活性——Async-fork 并没有实现为一个新的零碎调用，而是集成在默认 fork 中，用户能够在不批改程序原源码的状况下应用 Async-fork。咱们提供了一个接口以供用户抉择应用默认 fork 或 Async-fork。具体而言，咱们将该接口裸露到内存 cgroup 中。当用户将过程退出内存 cgroup 组后，能够向接口写入 0（应用默认 fork）或者正整数（应用 Async-fork）以抉择调用 fork 的形式。
额定开销——Async-fork 引入的额定开销来自向每个过程中的各 VMA 中增加指针（8B），因而额定的内存开销是 VMA 的数量乘以 8B，这样的开销通常能够忽略不计。
多架构反对——咱们将 Async-fork 实现在 x86 与 ARM64 上。事实上，Async-fork 能够实现在任何反对 hierarchical attributes 页表的架构上。
性能优化——咱们留神到当父过程触发被动同步时，父过程会陷入内核态，从而影响父过程的性能。一种缩小被动同步触发的办法是减速子过程的页表复制过程，这是因为被动同步仅可能在子过程复制页表期间产生。子过程复制页表的过程越短，父过程触发被动同步的概率越低。因为过程的 VMA 是互相独立的，咱们能够在子过程中启用多个内核线程并行复制各 VMA 的页表项，并取得靠近线性的减速比。启动多个内核线程可能耗费额定的 CPU 资源，咱们因而让这些线程周期性地查看是否应该被抢占并放弃 CPU 资源（通过调用 cond_resched 函数），以缩小对其余失常过程的烦扰。用户能够通过向内存 cgroup 组中裸露的接口写入正整数，以管制启用的内核线程数量。
试验数据分析
试验设置
咱们首先在单机上（试验环境如上表所示）验证了 Async-fork 的有效性，其次在本节开端的试验评估了 Async-fork 在实在生产环境中的成果。咱们在风行的 IMKVS（Redis-5.0.10 和 KeyDB-6.2.0）上验证 Async-fork 的有效性，并抉择了 Redis benchmark 和 Memtier benchmark 模仿多种场景的工作负载。
试验关注在快照期间达到的申请的尾提早（p99 提早和最大提早）。选取了最新的基于共享页表的 fork 优化技术 On-demand-fork（ODF）作为比照。在 ODF 中，因为页表在父子过程间共享，过程每次对共享数据的批改都会触发 PMD 项与 PTE 的拷贝（页表 CoW），本文对 ODF 中的这种开销进行了剖析。本文没有展现 Async-fork 与零碎中默认 fork 进行比照的后果，因为在所有场景中，Async-fork 都至多十倍优于默认 fork，在局部场景甚至百倍优于默认 fork。
整体性能评估
尾提早
图 6：The 99%-ile latency of snapshot queries.
图 7：The maximum latency of snapshot queries.
图 6 和图 7 别离展现了应用 Redis benchmark 生成写密集负载，在 Redis 和 KeyDB 中应用 ODF 和 Async-fork 生成快照时，快照期间达到申请的 p99 提早和最大提早。在 p99 提早方面，Async-fork 在所有场景中都优于 ODF，并且当实例变大时，两者的性能差距会减少。例如，在 64GB 实例上运行，应用 ODF 时申请的 p99 提早为 3.96ms (Redis) 和 3.24ms (KeyDB)，而 Async-fork 将 p99 提早缩小到 1.5ms（Redis，-61.9%）和 1.03ms（KeyDB,- 68.3%）。
在最大提早方面，Async-fork 仍然优于 ODF，即便实例大小为 1GB。对于一个 1GB 的 IMKVS 实例，应用 ODF 时最大提早别离为 13.93ms (Redis) 和 10.24ms (KeyDB)，而 Async-fork 将其缩小到 5.43ms (Redis，-60.97%) 和 5.64ms (KeyDB, -44.95%）。
图 8：The frequency of interruptions in the parent prolcess during the snapshot process.
在快照期间，IMKVS（父过程）可能会中断陷入内核态，进行解决用户申请，这将侵害 IMKVS 性能。Async-fork 的中断是因为父过程触发被动同步导致，而 ODF 的中断是页表 CoW 引起的。咱们应用 bcc 工具统计了快照期间父过程的中断次数，以及每次中断的持续时间，以剖析 Async-fork 优于 ODF 的起因。bcc 的统计后果以直方图显示（图 8），中断时长次要落在[16 , 31] 和 [32 , 63] 两个区间。
图 8 (a) 与 (b) 别离展现了不同 Redis 实例大小下，中断时长落在 [16us, 31us] 和[32us, 63us]的中断次数。咱们能够发现 Async-fork 显著缩小了父过程进入内核态的中断次数。例如，在 16GB 实例中，ODF 导致了 7348 此中断，而将中断次数升高到 446 次。Async-fork 大大减少了中断的起因是因为中断只有在子过程复制 PMD 项与 PTE 时才可能产生。而在 ODF 中，在子过程实现数据长久化（向硬盘写入所有数据）之前，父过程都可能会产生中断。一般来说，数据长久化的过程须要数十秒，而复制 PMD 项与 PTE 所需的工夫不超过 2 秒。在雷同的工作负载下，应用 ODF 时父过程更容易中断。
融化试验
读 / 写密集场景
图 9：The 99%-ile latency and maximum latency of snapshot queries under different workloads in an 8GB IMKVS.
图 9 展现应用 Memtier benchmark 生成不同读写模式的四种工作负载的后果。图中“1:1 (Uni.)”代表读写比为 1：1 的均匀分布工作负载，而“1:10 (Gau.)”是读写比为 1:10 的高斯分布工作负载。从图中可见，Async-fork 在各种负载均优于 ODF。Asycn-fork 带来的收益在写申请更多的负载中体现得更为显著，这是因为父过程在读密集型的工作负载中仅须要复制大量的页表项。一般来说，Async-fork 更适宜写密集的工作负载。在子过程生命周期内被批改的内存越多，Async-fork 带来的收益越多。
客户端连接数
图 10：The 99%-ile latency and the maximum latency of snapshot queries under different numbers of clients in an 8GB IMKVS. 图 10 展现了在 Redis benchmark 生成的写密集负载中应用不同数量客户端连贯 IMKVS 的后果。Async-fork 仍然显著优于 ODF，而性能差距随着客户端数量的减少而减少。这是因为当客户端数量减少时，更多申请会同时达到 IMKVS，导致更多的 PTE 被批改，叠加排队效应，父过程中断的工夫会变得更长。
用于并行复制的内核线程数
图 11：The 99%-ile and maximum latency of snapshot queries when Async-fork uses 1 or 8 threads.
图 12：(a) The time that the child process takes to copy PMDs/PTEs in Async-fork.(b) The 99%-ile and maximum latency in an 8GB Redis instance.
在 Async-fork 中，能够启用多个内核线程在子过程中并行复制 PMD 项与 PTE。图 11 显示了在不同 Redis 实例大小下快照期间申请的 p99 提早和最大提早。Async-fork-#i 代表总共应用 i 个线程并行复制的后果。察看发现，Async-fork-#1（仅子过程本人）依然带来比 ODF 更低的提早。与 ODF 相比，最大提早均匀升高了 34.3%。
另一方面，应用更多线程（Async-fork-#8）能够进一步升高提早。这是因为子过程越早实现 PMD 项与 PTE 的复制，父过程触发被动同步的概率就越低。图 12(a) 显示了子过程应用不同数量的内核线程复制 PMD 项与 PTE 所破费的工夫，而图 12(b) 显示了 8GB Redis 实例中相应的 p99 提早和最大提早。正如咱们所见，应用更多的内核线程无效地缩小了在子过程执行复制的工夫，而这个工夫越短则相应的提早越低。
Fork 调用时长
图 13：The execution time of Async-fork and ODF.
父过程 fork 调用的持续时间极大地影响了快照期间申请的提早。图 13 显示了父过程在不同 Redis 实例大小下从 Async-fork 和 ODF 调用中返回的工夫。在 64GB 的实例中，父过程从 Async-fork 中返回用时 0.61ms，从 ODF 中返回用时 1.1ms（而从默认 fork 中返回用时可达 600ms）。还能够察看到 Async-fork 的执行比 ODF 稍快，一个可能的起因是 ODF 为实现页表 CoW 须要引入额定计数器，从而导致了初始化的额定工夫老本。
生产环境中的成果
图 14：The 99%-ile latency and maximum latency of snap-shot queries with Async-fork in production.
Async-fork 已部署在咱们的 Redis 生产环境中。咱们在私有云中租用一个 Redis 服务器来评估生产环境中的 Async-fork 应用成果。租用的 Redis 服务器有 16GB 内存和 80GB SSD。咱们还租用了另一台具备 4 个 vCPU 和 16GB 的 ECS 作为客户端运行 Redis benchmark。
图 14 展现了应用默认 fork 和 Async-fork 时，快照期间达到申请的 p99 提早和最大提早。对于一个 8GB 的实例，申请的 p99 提早从 33.29 ms 缩小到 4.92 ms，最大提早从 169.57 ms 缩小到 24.63 ms。对于 16GB 的实例，前者从 155.69ms 缩小到 5.02ms，而后者从 415.19ms 缩小到 40.04ms。
总结
本文关注于内存键值对数据库在应用 fork 拍摄快照时引起的申请尾提早激增问题，并从操作系统的角度解决了该问题。通过对 fork 的深入分析，本文揭示了它对数据库申请提早的造成影响起因，并针对大内存实例的场景提出了优化办法——Async-fork。
Async-fork 设计的核心思想在于将复制页表的工作从父过程转移到子过程来。为保障一致性，咱们设计了高效的被动同步机制。Async-fork 在 Linux 内核中实现并部署于 Redis 生产环境中。试验结果表明，Async-fork 能够显著升高快照期间的申请尾提早。与默认 fork 相比，在 8GB 实例中缩小 81.76% 的尾提早，在 64GB 实例中缩小 99.84% 的尾提早。
原文链接
本文为阿里云原创内容，未经容许不得转载。