LWN：对NUMA更加优化的qspinlock！

关注了就能看到更多这么棒的文章哦～

NUMA-aware qspinlocks

By Jonathan Corbet
April 12, 2021
DeepL assisted translation
https://lwn.net/Articles/852138/

虽然 core kernel （核心部分的内核代码）中有些部分在几年前就达到了相对稳定的 "done"状态，但其他部分似乎距离完工还差很远。这部分有一个很好的例子，就是是内核中 spinlock 的实现。spinlock 在内核的底层来对数据访问进行仲裁。这类锁的性能表现对整个系统的性能有很大的影响，所以对其进行的优化工作可以得到很大好处。为了避免让人们认为这项工作已经完成，最近又出现了一个 NUMA-aware qspinlock patch set，展示了如何从内核的 spinlock 实现中继续提高性能。

之前用最简单的方式来实现的时候，spinlock 是内存中的一个 word，初始值为 1。任何希望获得锁的 CPU 都会执行一个原子操作 decrement-and-test（递减并判断），如果结果为 0，则说明成功获得这个锁。否则的话 CPU 需要在对这个值进行递增操作，接下来一直在这个小循环中 "spin（旋转）"，直到操作成功为止。内核早已抛弃了这种实现方式，原因有很多，性能就是其中之一。所有这些对 lock word 的原子操作都会导致 cache line 会在系统中（也就是多个 CPU 上）来回跳，哪怕这个锁的竞争并不激烈，cache line 的变化也会大大降低系统速度。

目前的 "qspinlock "实现是基于 MCS lock 的，它会将所有在等待这个锁的 CPU 排成队（queue），用链表来管理。一般来说，当人们担心 cache 的效率时，一般都会希望避免使用链表这种数据结构，但在这个场景中其实任何一方都不需要遍历这个链表。相反，每个 CPU 都只会在链表中跟自己有关的这一项上进行 spin 等待，并且只有在释放 lock 的时候才会走到下一项。关于 MCS 锁是如何工作更完整的描述，请看这篇文章，其中有一些通俗的示意图。

MCS locks on NUMA systems

MCS 锁看起来几乎是效率最高的方案了。每个 CPU 都只关注队列中自己这一项就好，所以处理器之间的 cache-line 跳来跳去的操作几乎完全被消除了。它们也保证了公平性，这个排队队列确保了没有一个 CPU 会过长时间拿不到访问权。但现在看来还有改进余地，至少在非一致性内存访问（NUMA，non-uniform memory-access）系统上是这样的。这种系统包含多个节点（node），每个节点包含若干 CPU，访问那些连接到本 CPU 节点的内存，比起连接到其他节点的内存速度更快。当然，无论内存连接在哪个节点上，对 cache 的访问都是（相对）最快的，但是在节点之间移动 cache line 的动作开销很大，甚至比在同一节点上的 CPU 之间发生 cache line 来回跳动的情况性能还要更加差。因此，需要尽量减少 NUMA 节点之间的 cache line 移动，从而改善性能。

如果某个 spinlock 被一个节点上的 CPU 释放了，随后被另一个节点上的 CPU 获得，那么它的 cache line 将不得不在两个节点之间移动了。相反，如果一个 spinlock 可以被传递给同一节点上的另一个 CPU，就没有这个昂贵的开销了。仅仅这一点区别就会已经会引入性能差异了，但不仅如此，别忘了 spinlock 是用来保护数据结构的。两个 CPU 在争夺某个锁的时候很可能是希望访问同一个数据，所以在节点之间移动这个锁也很可能意味着受保护的数据所在的 cache line 也会发生移动。对于竞争很严重的数据结构来说，由此带来的速度下降会很严重。

NUMA-awared qspinlock 会尽可能地将锁移交给同一节点上的另一个 CPU，来防止锁在 NUMA 节点之间来回移动。要做到这一点，那么管理这些等待锁的 CPU 的队列被分成了两个——主队列（primary）和次要队列（secondary queue）。如果一个 CPU 发现暂时抢不到锁，它会把自己加入主队列，像往常一样等待。不过，当一个 CPU 到了队列的最前端的时候，会看一下排在后面的 CPU，如果下一个 CPU 属于另一个 NUMA 节点，就会把下一个 CPU 分流到次要队列中。

这样一来，在等待的 CPU 都会被分到两个队列中去，其中一个队列（主队列）只包括与当前锁的主人在同一节点上的那些 CPU，另一个队列（次要队列）则包含所有其他的 CPU。当某个 CPU 释放锁时，会将锁交给主队列中的下一个 CPU，从而将锁保持在同一个 NUMA 节点上。只有当主队列清空时，锁才会移到另一个节点上，这时，次要队列就会变成主队列，这个过程又重新开始。

Tweaks and benchmarks

这个方案有一个明显的隐患：如果锁的竞争非常激烈，那么主队列可能永远不会清空，系统中的其他节点就会长时间拿不到锁。解决这个问题的办法是记下首次将 CPU 移到次要队列的时间。如果主队列在 10ms （缺省设置）后仍没有清空，整个次要队列将被插入到主队列的头部，从而迫使这个锁被转移到其他节点。可以用 numa_spinlock_threshold 这个 cmdline 参数来改变超时时间（在 1-100ms 的范围内）。

已经添加了一个名为 "减少洗牌（shuffle reduction）" 的优化。如果锁的争夺不是那么激烈，那么维护次要队列的这些额外工作并没有真正带来什么好处。为了减少这种额外的成本，代码使用了一个伪随机数生成器，每 128 个锁的获取中只会尝试创建一个次要队列。如果锁变得繁忙起来，这个操作会更加频繁地发生，此后就会一直维护这些次要队列，直到主队列再次被清空（或发生上面提到的超时事件）。

最后要讲的是，运行在中断模式（或不可屏蔽的中断，non-maskable interrupt）下的 CPU，以及运行实时任务的 CPU，都不会被移动到次要队列中。这使得这些 CPU（它们可能具有更高的优先级）能够相对快速地获得锁，尽管它们运行在不是最优的 NUMA 节点上。

patch set 中包含了一些基准测试数据。对于轻度竞争的锁来说，这个新的方案带来的性能优势相对较小。不过，随着竞争线程数量的增加，性能优势也在增加，对于严重竞争的工作场景，速度提升接近 2 倍。

这组 patch set 自 2019 年 1 月首次发布以来，已经经历了 14 次修订。这段时间里随着 review 意见的不断提出和解决，已经有了相当大的发展，目前似乎正在接近稳定状态，可能快要被合并了。不过，鉴于这项工作已经被审查了两年多了，而且它对内核的最基本的同步元语（synchronization primitive）之一进行了重大的修改，所以也仍然有可能会需要更长的时间才能合入 mainline。

这篇论文 对 NUMA-aware qspinlock 算法的细节进行了更多介绍，不过目前最新实现代码的细节与 f 论文所描述的会有一定的出入。

全文完
LWN 文章遵循 CC BY-SA 4.0 许可协议。

欢迎分享、转载及基于现有协议再创作～

长按下面二维码关注，关注 LWN 深度文章以及开源社区的各种新近言论～