最后,我们发现增加每次元素访问时的计数器增量会使得过滤器更倾向最近(访问)。这是因为更大的增量会更快地使计数器达到最大值,意味着计数器的值更多地反映了每个最近被访问的元素(而非元素的访问次数)。而且,我们会在总的增量达到采样大小时执行Reset操作,因此只需更少的元素就能触发Reset操作,更快触发过期。因此,大大降低了对历史频率的计数,而更关注最近产生的活动。
例如,增量为8,代表该元素的计数器会在元素进入时增加8,即估计的访问频率为8。第一次Reset操作之后,估计的频率会减半到4,第二次之后,会减半到2,以此类推。在极端情况下,当增量设置为S/C时,W-TinyLFU的行为最非常接近最近(访问),参见图3。
图3.该场景下,3个元素在不同时间仅出现了一次。增量为1的默认W-TinyLFU会将3个元素评为1(在上一次Reset之后)或0(在上一次Reset之前), 因此无法确定这三个元素的先后。图3a中的增量为2,在一个Reset操作之后变为1,Reset操作的频率也是前者的2倍,此时可以确定,最近访问了橘色和绿色的元素(而非红色的元素)。图3b的增量为4,再次加倍了Reset的次数,这种情况下,橘色和绿色之间多了一次Reset操作,因此我们探测到最近访问了橘色元素。
修改增量而非采样长度或Reset数值的动机主要出于工程的角度。即,除以2的操作可以高效地通过移位操作实现,而除以其他因子可能需要浮点运算。而且,修改sketch的大小可能会改变sketch的精度或需要动态内存分配。相反,修改增量值的影响较小,且实践中也容易实现。
4.2 潜在的自适应框架 4.2.1 爬山方案爬山方案是一种简单的优化技术,用于查找一个函数的本地最优值。在我们的上下文中,首先在一个特定的方向上修改配置,即增大Window缓存大小。然后对比新老配置下的命中率。如果命中率有所提升,则在相同的方向上继续进行下一步验证,即持续增大window大小。反之,则向相反的方向进行验证。图4展示了爬山算法。
图4. 爬山算法。在监控阶段,比较当前的命中率和先前获得的命中率,如果当前命中率提升,则在相同的方向上更新配置。否则,在相反的方向上更新对应的配置
该方法的主要优点是我们不需要额外的元数据来重新配置缓存,而前面的自适应算法则需要元数据和幽灵表项[4,24]。爬山是很多缓存策略常用的算法。
在该算法中,我们首先修改一个特定方向上的缓存配置,然后评估其对性能的影响。即,我们事先并不知道该配置是否能够提升命中率。理解改方案的难点主要在于如何决定每次调节的步长,以及调节的频率,因此需要权衡这两个动作。
乍一看,使用小而频繁的步似乎吸引人。这是因为此时小步造成的惩罚更小,且对变更的响应更快。但使用这种方式的问题在于测量短时间内的命中率时会产生噪声。因此,使用频率过高的步时,很难区分命中率的变更是由于新配置导致的还是由于噪声导致的。
上述原因使我们对策略做出不那么频繁且相对较大的变更。频率较低的变更为我们提供了足够的时间来评估配置对性能的影响范围,并增大了命中率之间的差异,使之更容易被观察到。这意味着在调节window大小时我们会轮流使用21种可能的配置(0%, 1%, 5%, 10%等),以及在调节sketch参数时会使用15种可能的配置(注意我们的W-TinyLFU sketch的计数器最大值为15)。此外我们将判定间隔设置为10倍缓存大小的访问量,这给我们提供了足够的时间来评估新配置的影响。
4.2.2 最常-最近指示器我们的目标是实时获取一个反映最常-最近平衡点的指示器,这种指示器会直接选择合适的配置,而无需采用逐渐增加步的方式。
指示器使用与W-TinyLFU过滤器[13]相同的sketch来评估元素的频率(增量值固定为1)。因此,当我们调节W-TinyLFU的Window缓存的大小(而非sketch增量)时,指示器会共享相同的(带W-TinyLFU过滤器的)sketch。