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

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

LRU 的槽指针.为方便理解与后续方法描述,我们在图 3 中对每个桶添加时间戳标签,该时间戳等同于每个桶中
LRU 队列队尾单元的时间戳,标记每个桶中现有最早放入元素的时间.

Fig.3 Double LRU CCHT structure
图 3 双重 LRU 的 CCHT 缓存索引结构

在通过 CCHT 向内存缓存中插入键数据 key 和值数据 value 时,如算法 1 所示.如果内存缓存中有空闲缓存
空间,通过散列函数 Hash 1 (key)得到对应的散列值 H 1 ,检查 H 1 对应的桶中是否有空闲槽.如果有空闲槽,则将键
值数据插入该槽,更新占用标记,并将该槽置于全局 LRU 队列队首和桶内 LRU 队列队首;如果没有空闲槽,则通
过 Hash 2 (key)计算得到散列值 H 2 ,检查对应桶中是否有空闲槽,如果有空闲槽,则进行上述相同操作.如果 H 1 和
H 2 对应的桶中都没有空闲槽,则比较 timestamp,选择时间戳较小的桶.如果 H 2 的时间戳较小,说明散列值 H 2 对
应的桶中 LRU 队尾的槽相对散列值 H 1 对应的桶中 LRU 队尾的槽更久没有被访问.踢出散列值 H 2 对应的桶中
LRU 队尾的槽,包括释放对应的键值数据,在全局 LRU 队列与桶内 LRU 队列中进行踢出.将待插入的键值数据
插入该槽中,并将该槽置于全局 LRU 队列和桶内 LRU 队列队首.如果插入键值数据时,内存缓存中无空闲缓存
空间,则需要先通过全局 LRU 队列踢出队尾槽对应的键值数据与 LRU 队列槽指针.
通过 CCHT 查询方法与第 2.1 节中描述的通过 CHT 进行查询类似,如算法 2 所示.在返回查询结果的同时,
如 CCHT 中包含所需查询的键值数据,则将键值数据对应的槽放置在全局 LRU 队列队首和桶内 LRU 队列队首.
通过双重 LRU CCHT,将原有键值数据插入过程中的踢出置换操作变为缓存替换,去除了由于置换操作引
发的内存访问次数和查询空闲槽的时间.双重 LRU CCHT 通过全局 LRU 队列和桶内 LRU 队列独立使用保证
了内存缓存系统的命中率.这种方法相对于 LRU CHT,增加了用于桶内 LRU 队列的指针存储空间开销.因此,我
们提出了粗粒度 LRU CCHT,相对双重 LRU CCHT,节省了指针占用存储空间的开销.
算法 1. 双重 LRU CCHT 插入算法.
输入:键数据 key,值数据 value;
输出:插入完成状态.
if Existfreespace()!=true//if there exist free space
Evictglobaltail()//evict global LRU tail unit
UpdateLRU(H,i)
end if
H 1 =Hash 1 (key)//compute the hash value of key with hash function 1

if i=Findfree(H 1 )//find a free space in the Bucket H 1
Set(H 1 ,i,key,value)//insert key and value into free space
UpdateLRU(H,i)//update LRU queue