动机
- 启发式缓存替换算法对工作负载行为做了强烈的隐式假设，无法适应不同场景以及负载的动态变化，严重影响了命中率性能。
- 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 分布，如对象的访问次数。
