总结

1. 本文的写作和图表值得学习。
2. 预取算法的设计也可以在之后的项目中参考。该算法并不一定用在远程内存场景下（见文图 8）。

动机

1. 访存低延迟对用户体验至关重要

（常识）

2. 基于现有 OS 抽象的 memory disaggregation 开销较高

作者介绍了两个基于现有 OS 抽象的解决方案：

1. 基于 VFS 的 Remote Regions
2. 基于虚拟内存的 Infiniswap （该团队的前作）

这两者均复用了 Linux 的 IO 系统，而 Linux 的 IO 系统是面向 HDD 优化的，有以下 2 个缺点：

1. 数据路径较长，IO 的排队等处理造成了不必要的延迟。
2. 预取算法是严格的（strict），窗口大小仅为 2，且不区分进程。依据 workload 不同，可能既太 aggressive 又太 conservative。
   1. aggressive: pattern 识别错误，使得 cache 被无用 cache 占用，造成 cache pollution。
   2. conservative: 没有识别到 pattern，本可以预取却没有预取。

{{:public:rg:readinggroup:summary:screen_shot_2020-11-18_at_20.58.47.png?400|}}

可供替换的预取算法也都有各自的缺点（当然 Leap 解决了这些维度上的问题）

{{:public:rg:readinggroup:summary:screen_shot_2020-11-18_at_20.55.42.png?400|}}

设计

{{:public:rg:readinggroup:summary:screen_shot_2020-11-18_at_20.57.55.png?400|}}

1. 简化且进程相关的 data path

将 Linux IO 操作从 critical path 中移除。针对每个进程引入独立的 data path。

2. 提出非严格的预取算法

该算法有以下特征：

1. 自适应的模式检测窗口大小
2. 自适应的预取数量

模式检测：在文章中，称为 trend detection。假设窗口长度为 w， d[i] = a[i+1]-a[i]，则认为 d[i] 中出现次数最多的元素（majority，大多数）就是当前程序所遵循的访问模式（消除不规则访问的影响）。这个检测可以在 O(w) 时间内完成。每次检测时，w 会从小到大直到找到模式或到达指定的最大值，因为小的 w 检测速度更快。

预取长度：在文章中，称为 prefetch window，有点 confusing 所以这里称为预取长度（识别到了 trend，那么到底要沿着这个 trend 取多少页面呢？）。作者为了避免一些突发的不规则访问破坏掉预取，因此引入了若干操作让预取长度的变化比较“顺滑”。

3. eager cache eviction

上述算法可以大大提高预取有效性。

观察：导致 cache evict 时要扫描一遍 cache，造成较高 latency。

目标：降低 latency -> 减少 cache。

假设：如果预取页面被用到了，说明这个页面被再次用到的概率很低（由 locality 导出）。

所以 Leap 设计预取页面在被用到后会被 evict。（通过引入一个链表来在 cache 之外额外管理预取页面。）