自适应软件缓存管理 (5)

对于每个新到的元素,我们会累计sketch的估量,并使用这些估量的平均值作为hint,指导当前的工作模式偏向哪一方(最近/最常)。以往的经验告诉我们,较低的值会偏向最常访问的负载,而较高的值会偏向最近访问的负载,而更高的值又会偏向极度频繁访问的负载。直觉上讲,如果负载偏向最常访问则访问的元素是分散的,计数器的数值相对较低;如果负载偏向最近访问,则访问的元素是相对集中的,被访问元素的计数器数值相对较高。最后,当负载具有(偏向最常访问的)较大的频率偏差时,一小部分元素的访问会非常频繁,因此这种情况下hint数值会非常高。图5展示了这种场景。

自适应软件缓存管理

图5. 每个周期包含三个访问的场景。图5a中,每种元素在每个周期仅出现一次。由于Reset操作,频率估计总是0,因此hint等于0。图5b中,使用最近访问方式来记录访问,现在每个数值的访问估值为0,1,2.因此,指示数值等于1。图5c中,我们修改了每个数值出现的次数来描述频率偏差,第一个周期的估值变为0,1,0,其他周期的估值为1,2,0,hint值为0.77。

为了区分(大)频率偏差和(高度)最近访问的影响,我们使用其他机制来评估分布偏差。众所周知,当在轴是元素等级和频率的log-log图中绘制Zipf分布的元素时,结果是一条直线,该直线的斜率是频率偏差(skew)参数。在每个配置周期内,我们会汇集最常访问的元素,并通过在这些项目的log-log值上执行线性回归来计算偏差估值。这种计算不会太频繁(即,每一百乘以缓存大小次数),也更实际。

我们结合hint数值和频率偏差估计(skew)来构造我们期望的指示器,如下:

\[indicator ≜ \frac{hint ·\left(1 − min\left\{1,skew^3\right\}\right)}{maxFre} \]

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zzzygy.html