====== 总结 ======


  - 本文的写作和图表值得学习。
  - 预取算法的设计也可以在之后的项目中参考。该算法并不一定用在远程内存场景下（见原文图 8）。
  - 应该学习做 breakdown analysis: 做了很多事情，究竟是哪个优化产生了作用？

===== 动机 =====
==== 1. 访存低延迟对用户体验至关重要 ====
（常识）

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

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

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

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

  - 数据路径较长，IO 的排队等处理造成了不必要的延迟。
  - 预取算法是严格的（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. 提出非严格的预取算法 ====


该算法有以下特征：

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

**模式检测**：在文章中，称为 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 之外额外管理预取页面。）

===== Eval =====


==== Breakdown ====


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

  - 预取贡献了大部分的延迟下降。
  - Eager eviction 在此基础上降低了最大延迟。

（不过很遗憾这个 breakdown 做得并不很全面。）