Page 74 - 《软件学报》2020年第10期

3050 Journal of Software 软件学报 Vol.31, No.10, October 2020

当 query 占比为 50%时,双重 LRU CCHT 与粗粒度 LRU CCHT 的效果对比 LRU CHT 更加明显地减少了平均
访问内存次数.在 latest,query 50%、zipf,query 50%、uniform,query 50%中的 70%、80%、90%,双重 LRU CCHT
平均降低了 10.59%、32.86%、97.25%,粗粒度 LRU CCHT 平均降低了 9.50%、32.91%、97.29%.原因是在 query
占比为 50%的工作负载中,有大量的插入操作.随着缓存空间的增加,LRU CHT 和随机 CHT 方法需要更多的踢
出替换操作以获得空闲的索引空间,导致了大量的内存访问.而双重 LRU CCHT 和粗粒度 LRU CCHT 随着缓存
空间的增加,没有访问更多的索引位置.
5.3 命中率
命中率是指在工作负载测试集加载过程中,查询成功的次数占所有查询次数的比值.图 8 描述了在 6 种不
同的工作负载下,5 种缓存索引算法的命中率.在 zipf 和 uniform 分布的 4 种工作负载中,双重 LRU CCHT 和粗
粒度 LRU CCHT 与 LRU CHT 的命中率表现相同,命中率均随着缓存空间的增加而增加.其中,双重 LRU CCHT
与 LRU CHT 的命中率差值最大不超过 0.12%,粗粒度 LRU CCHT 与 LRU CHT 的命中率差值最大不超过
0.22%.在 latest 分布的两种工作负载中,双重 LRU CCHT 与 LRU CHT 的命中率差值最大不超过 0.18%,粗粒度
LRU CCHT 与 LRU CHT 的命中率差值最大不超过 0.56%.CCHT 中引入了在散列表桶内无空闲槽时,通过桶内
LRU 算法踢出槽用于插入操作.CCHT 相对 LRU CHT 和 LRU 开散列表增加了缓存踢出次数,导致了命中率的
偏差.同时,由于采用了基于 LRU 队列的踢出策略,保证了 CCHT 的命中率相对 CHT 偏差要小.

Fig.8 Cache hit radio with hash table size
图 8 命中率随缓存空间大小的变化

5.4 索引开销分析
索引开销是指,在存储过程中,当缓存空间已满时,LRU 队列中槽索引指针的数目.CCHT 在移除 CHT 置换
操作的同时,引入了用于 LRU 队列的槽指针索引空间开销.本节实验分析了双重 LRU CCHT 与粗粒度 LRU
CCHT 在不同缓存空间大小情况下的索引开销,见表 3.当缓存空间大小与散列表大小比值大于等于 30%时,粗
粒度 LRU CCHT 的开销明显小于双重 LRU CCHT 的开销.当缓存空间大小与散列表大小的比值为 90%时,粗粒
度 LRU CCHT 比双重 LRU CCHT 减少了 31.71%.当比值小于等于 20%时,粗粒度 LRU CCHT 索引开销大于双