Linux 内核101：NUMA下的竞争管理
本文参考了以下这篇论文：
回顾一下上篇文章
上一篇文章 简单地介绍了一下多 CPU 下的 NUMA 架构。NUMA 架构中将内存划分为多个不同的区域，将CPU 和临近的内存组成一个 node 节点，OS 调度的时候会优先使用临近的内存，从而解决了之前 UMA 架构下 BUS 带来的性能问题（因为多个 CPU 会对这一条总线产生竞争）。同时也讲到了在MySQL在 NUMA 架构下遇到的 “swap insanity”问题，也就是当MySQL 占用的内存超过 (100 / node 总数) % 时，由于『优先使用临近内存』这个调度模式的存在，造成了内存分配不均，导致系统整体内存充足的情况下，依然出现大量『不正常』的的 swap 现象。如下图所示：
本文内容概括
本文将从『资源竞争管理』的角度切入，将会看到UMA 时代的竞争管理算法将不再适用于 NUMA，并给出具体的原因分析和解决方案。看完之后相信你一定会对 NUMA有更加深刻的理解，并对多CPU 时代的编程有个感性的认识。
UMA 竞争管理算法对 NUMA 不适用
有共享资源的地方，就会有竞争。有竞争，就会有性能损失。
一直以来，多核系统的共享资源竞争都是一个大问题。内核之间互相竞争共享资源，比如 last-level cache（LLC）、系统请求队列和内存管理器等。目前比较流行的解决方案叫做 contention-aware scheduler（竞争感知调度程序，下面简称为 CAS），也就是说它能够区分在互相竞争共享资源的 threads，然后把他们分开到不同的 domain。有数据显示，这种调度方法可以提高最坏情况下80%、平均10%的性能。
这种算法在 UMA 中是有效的。但是需要考虑到的是， NUMA 相比 UMA 有一点很大的不同，那就是 UMA 只有一个 memory node，配备一个 memory controller；而 NUMA中 每个 node 里面都有一个 memory node，各自配备了一个 memory controller，如下图所示：16个核被分为了4个 node，每个 node 有一个独立的 memory（当然每个核都可以访问任意位置的内存）。
那么这种调度方式到底起不起作用呢？如果只是简单的想一下的话，也许会觉得为什么不行呢？如果同一个 node 里面的 threads 竞争特别激烈，那我就把其中一个移到另一个 node 上，虽然说这会带来一定的延迟，但是竞争就解决了啊。
然后，事情没那么简单，一切真理都来自于实践，实践发现，在 NUMA 上面实施这种调度算法的时候，非但没能很好地解决竞争，反而性能下降了30%。至于原因，下文将会给出。
为什么不适用？
在 NUMA 架构下，CAS 会感知有哪些相互竞争的 threads，然后把其中一个移到不同的 domain 中。这会导致一种情况：thread的内存没有分配在该thread 运行的那个 node 里面，比如说上图中，一个 thread 本来运行在 c1上，之后由于竞争被移到 c5上了，但是它的 memory 还在 M1。我们把这种由于移动 thread，导致 thread 和它的内存分家的行为称作『NUMA-agnostic migrations』（agnostic 中文意思是不可知，自已意会一下~）。
NUMA-agnostic migrations导致了一些问题，比较明显一点的是thread 获取内存的延迟提高了，不过这还不是关键。更重要的是，NUMA-agnostic migrations无法缓解一些关键资源（memory controller）的竞争问题，甚至还引起对更多资源（interconnect connection）的竞争。
下面这张图很重要，请仔细看：
解释一下：T 和 C 分别表示两个程序（thread）
- 图0：两个程序相安无事，没有竞争关系。
- 图1：CT 的内存在一个 node，对 memory controller（MC） 产生了竞争关系。（应该还有访问延迟，图中可能忘记标注了）
- 图2： 两个程序都需要试用进行CPU 之间的快速通道，产生了interconnect connection（IC）竞争。同时还有访问远程 memory 带来的访问延迟（RL）。
- 图3：memory controller （MC）竞争，加上远程访问延时（RL）。
- 图4：TC 位于一个 CPU 里面，对 last-level cache（CA） 产生竞争关系。
- 图5：CA + RL
- 图6：CA + MC
- 图7：最坏的情况，CA + MC + IC + MC
实验发现，图3的性能下降了110%。原因在于 threads 还是在相互竞争 memory controller。NUMA-agnostic migrations在迁移 thread 的时候，很有可能最后会导致这种情况出现。
假如现在有两个threads，A 和 B，A 运行在图一中的 c1上，B 运行在 c2上，他们之间存在竞争关系（竞争last-level cache）。现在有一个 contention-aware 调度器检测到了 A 和 B 的竞争关系，于是把 B 移动到 c5上去了，现在A 和 B 不再竞争 last-level cache 了。事实上在 UMA 系统中这的确是起作用了（虽然对于 memory controller 的竞争还是存在的）。
但是对于 NUMA，A 和 B 的 memory 还在一个地方，对于 最关键资源memory controller 的竞争没有得到解决。而且还引来了两个问题，这两个问题会严重影响 B 的性能。
- interconnect connection。（这点影响会很严重）
- remote access。
总结一下
NUMA-agnostic migrations无法提高 甚至还会降低NUMA竞争管理的性能，按照对性能的影响程度排序有：
- 没能够解决对 memory controller 的竞争关系（memory 还在原来那个地方）。
- 引起了额外的 interconnect connection。
- 引起了额外的 remote access。
原论文中还提到了作者自己研究出的一种解决方案，有兴趣的同学可以去啃一下原文。
相信你看完了，应该对 NUAM 架构有了一个比较感性的认识了吧。觉得写的不错（看在gakki 的情面上）不点个赞鼓励一下？
广告时间，欢迎大家关注我的微信公众号。同时本文同步于 github： https://github.com/liaochangjiang/TechDaily
