(常识)
作者介绍了两个基于现有 OS 抽象的解决方案:
这两者均复用了 Linux 的 IO 系统,而 Linux 的 IO 系统是面向 HDD 优化的,有以下 2 个缺点:
1. aggressive: pattern 识别错误,使得 cache 被无用 cache 占用,造成 cache pollution。 2. conservative: 没有识别到 pattern,本可以预取却没有预取。
可供替换的预取算法也都有各自的缺点(当然 Leap 解决了这些维度上的问题)
将 Linux IO 操作从 critical path 中移除。针对每个进程引入独立的 data path。
该算法有以下特征:
模式检测:在文章中,称为 trend detection。假设窗口长度为 w, d[i] = a[i+1]-a[i],则认为 d[i] 中出现次数最多的元素(majority,大多数)就是当前程序所遵循的访问模式(消除不规则访问的影响)。这个检测可以在 O(w) 时间内完成。每次检测时,w 会从小到大直到找到模式或到达指定的最大值,因为小的 w 检测速度更快。
预取长度:在文章中,称为 prefetch window,有点 confusing 所以这里称为预取长度(识别到了 trend,那么到底要沿着这个 trend 取多少页面呢?)。作者为了避免一些突发的不规则访问破坏掉预取,因此引入了若干操作让预取长度的变化比较“顺滑”。
上述算法可以大大提高预取有效性。
观察:导致 cache evict 时要扫描一遍 cache,造成较高 latency。
目标:降低 latency → 减少 cache。
假设:如果预取页面被用到了,说明这个页面被再次用到的概率很低(由 locality 导出)。
所以 Leap 设计预取页面在被用到后会被 evict。(通过引入一个链表来在 cache 之外额外管理预取页面。)