Concurrent Deterministic Skiplist and Other Data Structures

本文设计并评估了一种适用于多核 NUMA 架构的并发确定性跳表，同时对比了无锁队列与哈希表实现的性能，提出了优化内存管理的策略，并建议通过分层使用并发数据结构来减少远程节点访问以降低内存延迟。

要点

这篇论文主要讲的是如何在超级计算机（拥有成百上千个处理核心）上，让几种常用的“数据整理工具”跑得更快、更稳。

想象一下，你经营着一个巨大的图书馆（这就是计算机的内存），里面有海量的书籍（数据）。现在，你有成千上万个图书管理员（CPU 核心）同时在工作，他们要不停地找书、放新书、或者把旧书扔掉。

如果管理不善，管理员们就会在书架间撞来撞去，或者因为找不到书而到处乱跑，导致效率极低。这篇论文就是为了解决这些混乱，设计了一套更聪明的“图书馆管理规则”。

以下是论文核心内容的通俗解读：

1. 核心挑战：大家挤在一起，怎么不吵架？

在普通的电脑上，管理员少，大家排队干活就行。但在超级计算机（NUMA 架构）上，核心太多，而且每个核心离“仓库”（内存）的距离不一样。

• 问题：如果所有管理员都去同一个仓库取书，路就会堵死（内存访问冲突）。
• 目标：设计一种方法，让每个管理员都能在自己的“小仓库”里快速干活，偶尔去大仓库取货时也不堵车。

2. 三大法宝（三种数据结构）

论文重点测试了三种整理数据的方法，并给它们穿上了“并发加速衣”：

A. 跳表（Skiplist）：像“高速公路”一样的书架

• 普通书架：找一本书，你得从第一排开始一本本数，很慢（像走楼梯）。
• 跳表：它在书架旁边修了多层高速公路。
  • 第一层是普通路，每本书都有。
  • 第二层是快速路，每隔几本书有一个出口。
  • 第三层是超高速路，间隔更远。
  • 找书时：先上高速路快速接近目标，再下高速走小路精准找到。
• 论文的创新：
  • 以前的跳表是“随机”修路的（像掷骰子决定哪层有路），虽然快，但有时候运气不好路修得不好。
  • 作者设计了一种**“确定性跳表”**（1-2-3-4 树），就像按照严格的数学公式修路，保证无论怎么找，速度都是稳定的。
  • 结果：虽然这种“严格修路”的方法在极端情况下（比如很多人同时放书）有点慢，但它非常稳定，而且作者发现，对于海量数据，随机跳表（掷骰子版）反而因为更灵活，跑得更快。

B. 无锁队列（Lock-free Queue）：像“流水线”一样的传送带

• 场景：管理员们需要把书从一个地方运到另一个地方（负载均衡）。
• 传统做法：大家排队，一个人拿完，下一个人才能拿（有锁，容易堵）。
• 论文的做法：
  • 把书放在成块的托盘（内存块）上，而不是一个个散放。
  • 管理员们像在玩“贪吃蛇”游戏，直接推托盘，不需要互相打招呼（无锁）。
  • 关键点：作者设计了一套**“回收站”系统**。用过的托盘不扔掉，而是洗洗干净放回仓库备用。这大大减少了去“采购部”（操作系统内存分配）买新托盘的时间，让流水线转得飞快。

C. 哈希表（Hash Table）：像“智能快递柜”

• 场景：根据书的编号（Key）直接找到书的位置。
• 问题：如果两个书的编号算出来是同一个柜子（冲突），柜子就塞不下了。
• 论文的做法：
  • 单层柜子：如果塞满了，整个柜子都要重新整理（重哈希），这时候所有管理员都得停下来等，效率极低。
  • 双层柜子（创新点）：作者设计了一种**“主柜 + 副柜”**的结构。
    • 主柜里如果塞满了，就自动在旁边开一个“副柜”专门放这些冲突的书。
    • 这样，当主柜在整理时，副柜还能继续工作，互不干扰。
  • 结果：这种“分层管理”让系统在核心数量激增时，依然能保持高速运转，比传统的 Intel 库（TBB）表现更好。

3. 内存管理：减少“跑腿”次数

在超级计算机里，从一个核心跑到另一个核心去拿数据（跨节点访问），就像从北京跑到上海取快递，非常慢且贵。

• 策略：作者让每个“区域”（NUMA 节点）都有自己的小仓库和回收站。
• 效果：管理员尽量在自己家门口干活，少跑远路。通过“预分配”和“循环利用”内存块，大大减少了因为找不到东西而导致的“页面错误”（Page Faults，相当于书柜被拆了重装）。

4. 总结与比喻

如果把超级计算机比作一个超大型物流中心：

1. 跳表是智能分拣系统，用多层传送带让包裹快速到达目的地。
2. 队列是自动化流水线，用托盘批量运输，并且把空托盘循环利用，不用每次都去工厂买新的。
3. 哈希表是智能快递柜，通过“主柜 + 副柜”的扩容机制，避免因为一个柜子满了而让整个物流中心停摆。
4. 内存管理是区域化仓储，让每个区的工人尽量在本地取货，减少跨城运输。

最终结论：
作者证明了，通过精心设计的“分层结构”和“本地化内存管理”，即使在拥有成百上千个核心的超级计算机上，这些数据结构也能像单人操作一样流畅，甚至更快。这对于处理大数据、云计算和人工智能任务至关重要。

简单来说，这篇论文就是教我们如何在人多手杂的超级计算机上，把“找东西、存东西、运东西”这三件事做得井井有条，互不干扰，效率翻倍。

技术摘要

这是一份关于《并发确定性跳表与其他数据结构》（Concurrent Deterministic Skiplist and Other Data Structures）论文的详细技术总结。

1. 研究背景与问题 (Problem)

随着多核 CPU 和异构计算架构（特别是 NUMA 架构）的普及，高性能计算应用面临着严峻的可扩展性挑战。

• 核心问题：传统的计算科学应用通常具有规则的内存访问模式，但在数据密集型应用（如点定位、范围搜索）中，内存访问往往缺乏空间和时间局部性，导致大量的缓存未命中（Cache Misses）和页面错误（Page Faults）。
• 具体痛点：
  • 现有并发数据结构局限性：现有的并发跳表（Skiplist）多为随机化实现，其高度依赖于随机数生成器，导致性能分析复杂且高度不确定。
  • 内存管理开销：在多线程环境下，频繁的 malloc/free 调用以及跨 NUMA 节点的远程内存访问会严重阻碍程序的可扩展性。
  • 哈希表与队列瓶颈：并发哈希表在动态调整大小（Resizing/Rehashing）时往往需要加锁，导致性能下降；并发队列在大规模负载下常因内存分配策略不当而表现不佳。
• 目标：设计并分析一种在 AMD Milan 多核 NUMA 节点上具有确定性性能、低延迟且高可扩展性的并发数据结构，特别是确定性跳表，并优化内存管理策略。

2. 方法论 (Methodology)

论文提出了一套针对多核 NUMA 架构优化的并发数据结构设计方案，主要包含以下三个核心部分：

A. 并发确定性跳表 (Concurrent Deterministic Skiplist)

• 设计基础：基于 Munro 和 Sedgewick 的 1-2-3-4 树（一种确定性跳表），而非随机跳表。
• 结构特性：
  • 确定性平衡：每个节点的高度是确定的，保证插入、查找和删除的时间复杂度严格为 $O(\log n)$。
  • 层级结构：叶子节点存储键值对，非叶子节点作为索引。层级间保持 $1/4$ 的链接比例约束。
  • 并发控制：
    • 插入：采用自顶向下的递归遍历，使用"L 形”锁（锁定节点及其子节点）进行局部重平衡（Re-balancing）。
    • 删除：采用惰性删除标记（Mark bit），并在非终端节点执行“借用”（Borrow）或“合并”（Merge）操作以维持平衡。
    • 查找：实现为无锁（Lock-free）。通过读取节点的标记位和原子更新的关键字/指针，检测并发修改并决定重试。
• 内存管理：引入引用计数和节点回收机制，避免 ABA 问题，减少内存分配开销。

B. 无界无锁队列 (Unbounded Lock-Free Queues)

• 设计改进：摒弃传统的链表结构，采用**基于数组的块（Block-based）**设计（类似 LCRQ 算法）。
• 内存策略：
  • 预分配与回收：使用内存池预分配块（Block），队列满时从池中获取新块，空时回收。
  • Full/Empty (fe) 信号：使用 fe 数组字段来协调读写操作的完成状态，解决数组队列中读写指针竞争的问题。
  • NUMA 感知：每个线程绑定到特定 NUMA 节点，优先访问本地队列块，减少跨节点内存访问。

C. 并发哈希表 (Concurrent Hash Tables)

• 对比方案：评估了三种实现：
  1. 固定槽位 + 单槽位二叉树解决冲突。
  2. 两级哈希表（Level-2 Hash Tables）+ 二叉树。
  3. 分裂顺序哈希表（Split-Order Hash Tables）及其两级变体。
• 优化策略：
  • 分片（Partitioning）：根据键的高位将数据分布到不同的 NUMA 节点，每个节点维护独立的哈希表。
  • 内存局部性：为每个哈希表或槽位分配独立的内存管理器，利用大页（Huge Pages）和 TBB 内存分配器，最大化空间和时间局部性。
  • 锁粒度：使用读写锁（RW Locks），允许并发读取，仅在插入/删除时加写锁。

3. 关键贡献 (Key Contributions)

1. 首个并发确定性跳表实现：
   • 提出了基于 1-2-3-4 树的并发实现，提供了严格的 $O(\log n)$ 性能保证，消除了随机跳表的不确定性。
   • 设计了无锁查找算法，显著提高了读操作的并发度。
2. NUMA 感知的内存管理策略：
   • 提出了一种分层使用并发数据结构的策略，将数据分布到不同的 NUMA 节点，大幅减少了跨节点的远程内存访问。
   • 设计了基于块回收的内存管理器，显著降低了页面错误和缓存未命中率。
3. 全面的性能基准测试：
   • 在 NCSA 的 Delta 超级计算机（AMD Milan 多核 NUMA 节点）上进行了大规模实验（高达 10 亿次操作）。
   • 将自定义实现与 Intel TBB 库及 Boost 库进行了详细对比。
4. 算法与实现的深度分析：
   • 提供了详细的线性化点分析和重平衡操作的数学推导，证明了在并发环境下重平衡操作的总数是线性的。

4. 实验结果 (Results)

实验在 4 到 128 个线程的范围内进行，主要发现如下：

• 跳表性能：
  • 确定性 vs 随机：在 1 亿次操作负载下，随机跳表（Lock-free Random Skiplist）在高线程数（如 128 线程）下表现优于确定性 1-2-3-4 树（耗时约 2.86s vs 34.28s）。这是因为确定性树的重平衡操作（加锁）在高并发下引入了较大的开销。
  • 无锁查找：确定性跳表的无锁查找版本比基于读写锁（RW Lock）的基线版本具有更好的可扩展性，但在高负载下仍受限于重平衡时的锁竞争。
• 队列性能：
  • 提出的基于数组块的无锁队列在 10 亿次操作下，性能优于 TBB 和 Boost 的实现。
  • 通过内存回收和 NUMA 本地化，有效减少了缓存未命中。
• 哈希表性能：
  • 两级结构优势：两级哈希表（Two-level）在大多数负载下优于固定大小哈希表，因为减少了二叉树的深度。
  • 分裂顺序表（Split-Order）：两级分裂顺序哈希表在 10 亿次操作下表现最佳（128 线程耗时约 5.17s），优于 TBB 实现（0.79s 为 100 万，1B 数据 TBB 为 6.00s，Split-Order 为 5.17s）。
  • 缓存行为：两级结构显著改善了空间局部性，减少了跨 NUMA 节点的页面错误。
• 内存管理：
  • 使用大页（Huge Pages）和自定义内存池显著降低了页面错误率，提升了整体吞吐量。

5. 意义与结论 (Significance & Conclusion)

• 理论意义：证明了确定性数据结构在并发环境下的可行性，尽管随机化结构在极端高并发下可能因重平衡开销较小而略胜一筹，但确定性结构提供了可预测的性能边界，便于系统分析和调试。
• 工程价值：
  • 为多核 NUMA 架构下的数据密集型应用提供了一套经过验证的优化方案。
  • 强调了内存局部性（Memory Locality）和NUMA 感知（NUMA-awareness）在并发数据结构设计中的核心地位。
  • 提出的内存回收和分层数据结构策略，对于构建大规模分布式系统或高性能数据库具有直接指导意义。
• 未来工作：
  • 计划将这些实现移植到 GPU 架构，利用其更高的并发能力。
  • 探索通过 MPI 或 RPC 将这些本地并发结构扩展为分布式系统，利用其线性化特性保证分布式正确性。

总结：该论文不仅实现了一种新颖的并发确定性跳表，更重要的是通过系统的实验和内存管理优化，揭示了在多核 NUMA 架构上构建高性能并发数据结构的最佳实践，即：结合无锁算法、细粒度锁、NUMA 感知分片以及高效的内存回收机制。