最后,我们将提出的方案与来自不同途径的实验结果(一些来自于前面的工作,一些来自于Caffeine的用户[23])进行了评估。 在我们的评估中,与最佳替代方案相比,我们的自适应方案始终富有竞争力。
2 相关工作Belady的最优缓存管理策略[5]可以面向未来,并从缓存中淘汰最早访问的元素。但由于无法预测未来,因此在大多数领域中,该策略是不现实的。它可以作为缓存策略性能的上限。在实践中,缓存管理策略涉及典型访问模式的启发和优化。
LRU基于这种假设:最近最少访问的元素,则未来不可能再次访问。这样,一旦缓存满后,它会淘汰LRU元素,为新到的元素让出空间。而LFU认为访问频率是一种好的对未来行为[2, 3, 13, 17, 18]的评估器。LFU需要监控大量不存在于缓存中的元素,因此可能会造成大量开销。[13]使用一个近似sketch来最小化这类开销。此外,LFU策略经常会引入过期,通过对应的特定滑动窗口[17]或指数衰减样本来计算频率[2,3]。其他方式包括通过重用距离[1,16,20]来计算后续到同一条目的访问时差。 但后者需要记住大量的幽灵条目。
空间是优化的另一个维度。在一些场景下,元素的大小差异很大,因此需要将大小算进去[6, 9, 32]。通过自适应大小来调节缓存准入的可能性,进而最大化目标命中率[6]。相反,很多缓存策略会维护一个固定数目的元素,而不关心元素大小,只有当缓存的元素大小相同或类似时才不会对效率造成影响,如块缓存和分页缓存。另外,很多知名的视频点播和流系统会将文件分割为相同大小的块,每一块都可以独立缓存。这里,我们关注固定大小的元素。
Hyperbolic缓存是最近提出的一个各方面比较好的缓存管理策略。Hyperbolic缓存可以使用相同的数据结构来模拟多种淘汰策略,因此能够根据负载采取相应的动作。另一个自适应策略是Adaptive Replacement Cache (ARC) [24]。这两种策略的共同缺陷是在最常(访问)方式下没有竞争力,而且ARC需要维护大量幽灵表项。
LRFU[19]结合了最近和最常两种方式来评估缓存中的每个元素,通过参数λ来控制平衡。当使用"正确的"λ来为一个给定的负载初始化LRFU时可能会获得高命中率,而选择"错误的"值则可能导致性能问题。根据负载自动化调节λ仍然是一个问题。另一个妨碍LRFU被广泛采纳的原因是其本身高昂的实现和运行时代价。
最近出现的Mini-Sim [31]方法建议同时模拟多种缓存配置,每种模拟会通过在所有访问中进行随机采样来降低计算开销。这种方法的问题是由于采用了在r次访问中采样一次的方式,因此在一个短周期内可能会丢失多次访问(这里1/r作为采样率),无法捕获基于最近(访问)的负载的特征。Mini-Sim会随机采样1/r次,然后将代表所有访问的采样元素提供给模拟配置。为了节省空间,将模拟缓存大小设置为c/r,c为原始缓存大小。回顾一下,我们的目标是找出一个最佳配置参数,而不是决定哪个元素应该出现在实际缓存中。
Mini-Sim有如下缺陷。模拟配置必须持有它们所保存的元素的幽灵表项,这样会导致空间浪费,且执行时间与同时配置的模拟数量和采样率成比例。我们针对Mini-Sim和W-TinyLFU进行了实验,发现在缓存了上千个元素且使用基于最常访问的负载上,Mini-Sim需要更大的采样率才能获得相同精确的结果。在实践中,在基于最常访问的负载上,基于元素ID的采样的精度要稍低,因为如果没有采用到常用的元素,则MiniSim的结果会与实际负载的行为有所出入。此外,由于使用的是采样,MiniSim需要相对更长的时间来适应负载的变化。相比之下,我们的方法更具冒险精神 - 在没有事先模拟新配置的性能的情况下直接更改配置。
最近的LeCaR研究[30]使用机器学习技术来结合LRU和LRF替换策略,其展示的结果要优于ARC,且在负载变化时表项良好。
还有一些工作考虑到了SSD缓存的特点,更重要的是[8]中的工作描述了为何Belady的最优观点不适用于SSDs,并提出了一个新的离线优化算法(该算法不仅最大化命中率,还考虑到容器放置问题以减少写入放大和设备磨损)。Pannier[21]专注于SSD的容器缓存实现细节,他使用一个自适应信用系统来限制SSD写入预定义配额的数据量。这和我们的[15]工作类似,它维护了一个使用幽灵表项的对象的频率统计信息,且仅允许最常用的对象进入SSD缓存,使用ARC作为缓存替换算法。本质上,这种方法和TintLFU类似,区别是使用了幽灵表项,而不是sketches。