在 Linux 内核的内存管理体系中，交换子系统（swap subsystem）承担着将匿名页面换出到磁盘、并在需要时换入内存的关键职责。这一子系统的性能直接影响系统在内存压力下的响应能力与吞吐量。长期以来，内核开发者持续优化交换子系统的实现，从早期的链表结构到 radix tree，再到 Linux 4.20 引入的 Xarray，每一次更迭都带来了显著的性能提升。然而，最新的补丁系列表明，Xarray 并非终点 —— 一种名为 Swap Table 的新型数据结构正在被引入，以进一步现代化交换子系统的元数据管理，实现约 20% 至 30% 的性能跃升，同时降低内存占用并简化代码复杂度。
从链表到 Xarray：元数据管理的技术演进
理解 Swap Table 的设计价值，需要首先回顾 Linux 交换子系统元数据管理的历史演进。在 Linux 2.6 内核时代之前，交换缓存（swap cache）的元数据管理主要依赖于简单的链表结构，用于维护活跃与非活跃页面的列表，以及进行页面回收策略（如 LRU 老化）。然而，随着系统内存容量的增长和硬件特性的演进，链表结构在稀疏索引场景下的低效性日益凸显 —— 遍历链表查找特定交换条目需要线性的时间复杂度 O (n)，且链表节点之间缺乏空间局部性（spatial locality），导致 CPU 缓存命中率低下。
约在 2006 年左右，Linux 内核引入了 radix tree（基数树）来替代链表，作为 page cache 和 swap cache 的核心索引结构。radix tree 允许通过交换偏移量（swap offset）在 O (log n) 时间内定位页面，显著提升了查找效率。然而，radix tree 的 API 设计被认为存在诸多问题：术语晦涩（如 "insert" 操作在存在重复键时的语义不明确）、锁管理复杂（要求用户自行处理 preload 和锁定逻辑）、异常条目（exception entries）的概念令开发者感到困惑。这些问题导致许多内核子系统选择自行实现专用数据结构，而非复用 radix tree。
Linux 4.20 版本引入的 Xarray 正是为了解决这一困境而生。Matthew Wilcox 在 2018 年 linux.conf.au 的演讲中详细阐述了 Xarray 的设计理念：保留 radix tree 的高效内核实现，但将隐喻从 "树" 改为 "自动调整大小的数组"。这一转变带来了多方面的优势：默认处理锁定机制，移除了烦琐的 preload 机制；提供 Normal API 和 Advanced API 分层，简化了普通用户的调用方式；同时支持 RCU（Read-Copy-Update）无锁查找，内置三个标记位（XA_MARK_0/1/2）用于元数据标签（如脏页标记），并支持多索引条目（multi-index entries）以节省内存 —— 例如一个 order-9 的条目覆盖 512 个索引，仅需少量节点即可存储。Xarray 迅速成为 page cache 的默认实现，但其引入也伴随着一定的复杂性开销。
Swap Table 的设计理念与 Xarray 的局限性
尽管 Xarray 在 page cache 场景中表现出色，但在交换子系统的特定应用场景下，其树状结构仍存在可优化的空间。2025 年 5 月，由腾讯工程师 Kairui Song 提交的一系列补丁（[PATCH 00/28]）正式引入了 Swap Table 概念，旨在用简单的数组结构替换 Xarray 在 swap cache 中的角色。这一设计的核心洞察在于：在 swap-in 和 swap-out 路径中，内核通常已经持有 swap cluster（交换簇）的上下文信息；既然我们已经知道了目标页面所属的簇，为何还需要在树状结构中遍历多个节点进行查找？
Swap Table 的本质是一个每个交换簇（cluster，通常对应一页大小）专属的指针数组，用于存储 swap cache 值，每个条目的大小与传统 PTE（页表项）相同。与 Xarray 的树状查找不同，Swap Table 允许在簇内进行直接的数组索引查找，实现真正的 O (1) 时间复杂度。根据内核文档的描述，一个 Swap Table 的大小通常匹配现代 64 位系统上的 PTE 页表尺寸（即一个物理页框）。这种设计带来了几个关键优势：首先是局部性（locality）的大幅提升，访问相邻的交换条目意味着访问数组中相邻的内存位置，这对 CPU 缓存极为友好；其次是锁定粒度的细化，Swap Table 的修改仅需获取簇级锁（cluster lock），而非全局锁或树级锁，减少了并发访问的争用；最后是内存占用的优化，每个 swap entry 的内存占用从 12 字节降至 10 字节，空闲时的动态分配机制进一步降低了系统整体内存压力。
更重要的是，Swap Table 统一了原本分散的元数据结构。在此之前，swap cache、swap map（用于跟踪每个交换条目的引用计数）和 cgroup map（用于 cgroup 级别的内存统计）各自维护独立的数据结构，不仅增加了内存开销，也使得代码逻辑变得碎片化。Swap Table 成为了这三种元数据的唯一基础数据结构，通过统一的条目格式（支持 NULL、folio 指针、shadow 指针等状态）简化了整个子系统的架构。
性能跃升与工程实践参数
Swap Table 带来的性能改进在多个基准测试中得到了量化验证。根据补丁提交者公布的测试数据，在使用 usemem 工具进行的顺序写入测试（1G memcg，pmem 作为 swap 设备）中，系统时间从 217.39 秒降低至 161.59 秒，降幅达 25.67%；吞吐量从 3933.58 MB/s 提升至 4975.55 MB/s，增幅达 26.48%。在更具挑战性的随机访问模式下，这一趋势得以保持。在使用 ZRAM（内存压缩设备）进行内核编译的测试矩阵中，不同内存限制和并行度组合下的系统时间普遍降低了 18% 至 38%，展现出 Swap Table 在重负载场景下的稳定性。
值得特别关注的是，Swap Table 的引入使得 mTHP（Multi-Sized Transparent Huge Pages，多尺寸透明巨型页）的 swap-in 成为可能并得到优化。旧设计中，mTHP swap-in 和 read-ahead 路径与 swap count 逻辑耦合，仅在 SWP_SYNCHRONOUS_IO 设备且所有相关条目的交换计数等于 1 时才生效 —— 这一限制显然不合理，因为 read-ahead 和 mTHP 行为本应与交换计数无关。Swap Table 通过统一的查找路径消除了这一耦合限制，不仅提升了性能，还可能减少 mTHP 的碎片化问题。此外，旧设计中每个 swap device 维护多个 address_space 实例的做法也被废弃，进一步简化了代码并减少了内存占用。
在工程实践中，启用 Swap Table 需要关注几个关键参数与监控指标。首先是 swap table 的动态分配行为 —— 该特性在补丁 28 中实现，允许在需要时按簇动态分配 swap table，而非在 SWAP 设备激活时就预先分配全部内存，这显著降低了空闲内存占用。其次是锁定策略：Swap Table 的修改操作需要获取簇锁（folio 必须在获取簇锁之前被锁定），而查找操作则受到 RCU 和原子读的保护，返回 folio 后用户必须自行锁定 folio 再进行后续操作。内核开发者可以通过 /sys/kernel/debug/swap_table（如果启用）或 /proc/vmstat 中的相关计数器监控 swap cache 查找的命中率与延迟分布。
后续演进与集成展望
Swap Table 的引入并非终点，而是一个重要的基础设施改进，为未来的优化开辟了道路。补丁提交者明确列出了几项后续工作方向。其一是与 Nhat Pham 提出的虚拟交换空间（Virtual Swap Space）设计相集成；虚拟交换空间允许更灵活地管理压缩缓存（如 zswap）和 swap 设备之间的关系，而 Swap Table 的低开销和灵活性为这种集成提供了理想的底层支持。其二是基于 folio 的批量操作优化；当前补丁已经引入了 folio_alloc_swap、folio_dup_swap、folio_put_swap 等 folio 基础 API，为更高效的批量页面处理奠定了基础。其三是移除 swap cgroup 控制映射（cgroup control map）；这将进一步简化代码并提升性能，但需要更充分的测试验证。
从技术演进的角度来看，Swap Table 的设计体现了 Linux 内核开发的一贯哲学：不追求一步到位的完美方案，而是通过渐进式的重构逐步逼近最优解。从链表到 radix tree，再到 Xarray，最后到 Swap Table，每一次演进都建立在前一阶段成果的基础上，并针对特定场景进行深度优化。这种演进路径也提醒我们，在选择数据结构时需要充分考虑具体的访问模式与约束条件 —— 在 swap cache 场景下，既然簇上下文已知，简单数组的 O (1) 查找显然优于树状结构的 O (log n) 遍历。
综上所述，Swap Table 通过用简单数组替换 Xarray，在交换子系统的元数据管理上实现了显著的优化：约 20% 至 30% 的性能提升、每个条目 2 字节的内存节省、更细粒度的并发控制，以及更简洁统一的代码架构。对于系统管理员和内核开发者而言，这意味着在内存压力场景下更可预测的响应延迟、更低的 CPU 系统时间开销，以及未来与虚拟交换空间等新特性集成的可能性。
参考资料
- LWN.net: "[PATCH 00/28] mm, swap: introduce swap table" (2025.05)
- Linux Kernel Documentation: "Swap Table"
- LWN.net: "The XArray data structure" (2018)
- Linux Kernel Documentation: "XARRAY"