0%

LHD(NSDI 18)

动机

  1. 启发式缓存替换算法对工作负载行为做了强烈的隐式假设,无法适应不同场景以及负载的动态变化,严重影响了命中率性能。
  2. prior policies rely on implementation primitives that unnecessarily limit their design.(复杂缓存策略需要复杂的数据结构,例如 GDSF 使用 heap,缓存插入和驱逐的时间复杂度较高;LRU 则是因为需要进行同步所以吞吐量也很低)

Least Hit Density (LHD)

从式子来看,命中概率越大,对象越应该保留在缓存;对象越大,占用更大的空间,生命周期越长,占用更久的空间,给缓存总体的 OHR 带来负面影响。特别地,当缓存对象命中或驱逐时,它的 “生命周期” 都算作结束。而 LHD 做的事情,就是动态预测每个对象的 expected hits-per-space-consumed(hit density),驱逐密度最低的对象。

挑战:在不知道对象未来的命中次数、生命周期的情况下,如何预测对象的命中密度。

上图中的公式(5)表示:当对象已经在缓存存活 a,它的命中密度。其中分子是对象在 [1, ∞] 时间段的命中概率之和,也就是期望命中概率,分母则是对象大小和期望剩余生命周期的乘积。

因此,LHD 可以在线监控所有对象的 H 和 L 的分布,分布中的每个点表示,在生命周期 x 时命中以及在生命周期 x 时命中或驱逐的概率。有了这两个分布,就可以通过上图中的公式(5)计算所有缓存对象的命中密度(所有缓存对象已经在缓存中待的时间作为元数据保留)。

更进一步,如果有额外信息,可以对额外信息中表示的每个类别计算一组 H 和 L 分布,如对象的访问次数。