[ATC '20] Effectively Prefetching Remote Memory with Leap

发表于 更新于

这是一篇论文阅读笔记。

Leap 是一个内核态的、面向分布式 NVM 的缓存预取和逐出策略，可以运行在大部分基于 NVM 的存储系统之下；在 Linux 内核中实现的 Leap 使访问远程页的中位数延迟和尾延迟分别降低 104.4× 和 22.62×，带来最高 10.16× 的性能提升。

研究背景和动机

页缓存——包括缓存预取、逐出策略，以及缓存未命中时的处理方式——实际上是一个研究了很长时间的话题了，而且经久不衰。不幸的是 Linux 自带的页缓存机制做得并不是很到位，尤其是在 NVM 场景下。这体现在以下两个方面：

  • 一旦出现 cache miss，页访问请求就要进入 Block IO 队列，然后经过 batching 等过程被处理；这个流程延迟很高，大约有 34 μs；
  • 预取策略简单粗暴，一旦出现两个连续的页访问，就去预取后面的页，否则就当做没有访问模式而什么也不做。

很显然，这些策略是面对 HDD、SSD 这些传统的低速存储介质设计的（甚至主要是针对 HDD，对 SSD 并不是那么友好）；对于 NVM 来说，我们没有必要去 batch 请求，同时也不会受制于 HDD 的物理限制，不必追求完全的连续访问，可以去识别更多的页的访问模式，去做更加灵活的预取。因此，原有的块访问接口以及页的预取、逐出策略都是可以改进的。

Leap 的设计

Leap 针对上面两个问题分别给了解决方案：

  • 首先，Leap 更改了数据路径，数据页不走 Linux 的块访问接口了，直接带来大概 10 倍的性能提升。
  • 其次，Leap 增加了对 stride（即每次跨越固定页数的访问模式）的识别，在识别到访问模式的时候进行预取，并且通过识别众数避免短期的不规律访存带来的影响。

前者没有什么需要解释的点，有意思的点主要是后者，也就是页预取、逐出策略。

访问模式识别

Leap 不记录对内存中的页（热的页）的访问，只在发生 I/O 请求或 page fault 后记录对应的页的地址，以此减小记录的开销。

每记录一次新的地址，Leap 都会发起一次访问模式识别。它首先计算页的地址的一阶差分，然后从差分序列最新的 $w$ 个元素中寻找众数。如果找到，那么认为识别到了一个访问模式；如果找不到，那么置 $w \leftarrow w\times 2$，重新寻找访问模式。

这种逐步扩大窗口的方式可以避免短期的一些噪声对识别带来影响。另外，作者使用的 Boyer-Moor 众数寻找算法（不是同名的字符串匹配算法）在寻找的区间扩大后可以接着运行，不用重新扫一遍。另外，我们也不需要维护全部的访问历史，只需要用个环形队列维护最近的 $H_{\rm size}$ 个就可以了。作者取的值是 $H_{\rm size} = 32$，每次模式识别的开销很小。

预取策略

预取策略有一些很奇妙的设计，不过具体设计比较复杂，可以去参考论文中的 Algorithm 2。值得一提的点有以下几个：

  • 预取的页数和上次预取的页的 hit 数目正相关
  • 无论如何，预取的页数最小为上一次预取的一半
  • 如果要预取，但是又找不到一个访问模式，那么就预取这次访问的页周围的几页

第一点让这个策略能在带宽不足或者没有规律访问模式的时候收敛，第二点能让它避免短期噪声的干扰，第三点能比较好地应对一些具有空间局部性，但是又没有明显规律的访问模式。总体的设计是比较均衡的。

逐出策略

Leap 采用了比较激进的逐出策略。这种激进是有道理的，因为我们讨论的对象是页而不是内存，页在被用一次之后短期不再被使用的概率相比一个内存单元（或者缓存行）要大得多。因此，一个页只要被 hit 了，那么它就被 Leap 标记为逐出候补，最后由一个后台进程将其按照 LRU 的方式逐出。据作者说，这样可以让申请一页的时间减少 750 ns（大约降低 36%）。

有的工作负载和我们之前说的不同，会反复访问某一页；Leap 也会识别这种情况，然后不再去逐出这些页。

性能表现

相当不错，用了 Leap 之后，页的序列访问和 stride 访问延迟都降低了很多。

作者们设计了三个指标来评价缓存策略：

  • 准确性（Accuracy）：等于 cache hit 数量除以预取到 cache 中的页数；
  • 覆盖率（Coverage）：等于命中预取的页的 cache hit 数量除以总的 I/O 请求（page fault）次数；
  • 时效性（Timeliness）：等于一个被准确预取的页从加载到 cache 到第一次 cache hit 的时间差。

作者又另外搞了三个指标：总的预取页数、总的 cache miss 数，以及为了体现 Leap 访存路径优越性的负载运行时间。

从结果来看，后面三个指标上 Leap 全面领先。准确性方面，Next-N-Line 策略领先，不过因为它往 cache 中加载了更多的页，这也是必然的。覆盖率方面 Leap 最优。时效性方面，有着 30 年历史的 Stride 策略领先，但是它另外五个指标表现不够好；与此同时 Next-N-Line 的时效性令人发指的差，比 Leap 高了两个数量级。

总而言之，Leap 还是相当均衡的一个缓存策略。

我的一些想法

Leap 可以识别 stride 访问模式，但文中自己放了一张图：

这四个应用就是作者用来做 evaluation 的，可以看出它们都没有多少 stride 访问模式……那为啥要做呢？挺迷惑的。

最后摘抄一下作者们自己写的 future work：

  • 做线程粒度的 I/O 请求追踪，有希望识别不同线程上的多个页访问模式；
  • Leap 拦截了 I/O 请求，所以 Leap 启动的时候是不能访问块设备的，这部分需要改进；
  • 考虑负载均衡、容错、数据局部性、隔离性这些东西。

再感叹一下，缓存策略这个主题真是经久不衰。