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

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

的负载率.但当进行查找操作时,由于散列函数的增多,导致需要查看更多位置的桶与槽,进而导致了访问延迟
的增高与处理器中 cache line 中加载次数的增多.在实际使用过程中,CHT 的散列函数设置成在能够保证槽的充
分利用和高负载率的同时,还能有效缩短查找时间,降低访问延迟.
在 CHT 中,增加每个桶内槽空间的数量,可以有效提升负载率.当桶内槽数量增加时,在一次插入和读取操
作的过程中访问单一桶中槽的数量增多,从而减少了第 2 次或者更多次的散列操作,有效增加了 CHT 的负载率.
[9]
在 CHT 实际应用中,大部分的设计采用了每个桶配有 4 个或 8 个槽空间 .采用这种配置的原因是一个处理器
中的 cache line 可以一次缓存一个或者两个位置的数据.如果每个桶中使用更多的槽,在进行键值数据比较时,
将导致更多的处理器 cache line 加载,访问延迟有所增加.
CHT 的主要特性是能够提供快速的查询.在响应读取请求时,最大的查找空间数为 n×s,其中,n 为散列函数
个数,s 为单个桶中对应的槽空间个数.对于桶中用于槽的存储区域,采用定长存储空间的分配方式,方便通过数
组或者向量的方式对数据进行访问.这种方式使 CHT 更易于在不同处理器架构上进行实现,如 CPU、GPU 和
Xeon Phi.

2.3 基于LRU的缓存替换策略
在内存缓存系统中,系统将部分数据从持久化存储介质缓存到内存中,用来降低数据访问延迟.由于内存的
存储空间有限,小于所有的数据存储空间需求,当内存缓存空间占满时,需要通过缓存替换策略踢出已缓存数
据,获取空闲空间存放新的缓存数据.缓存替换策略保证了更有价值的缓存数据留在内存中,通常采用命中率来
衡量其有效性.在系统实现时,通常将增加访问吞吐与延迟作为综合的考量指标.在实际使用中,需根据不同的
应用负载选择适合的替换策略.如在 Web 应用的场景下,最近热门的数据被频繁访问,则适用最近最少使用
(LRU)替换算法 [7,8] .
LRU 算法是典型的缓存替换算法.其核心思想是将最近访问的数据单元作为最有价值单元,需要替换时,踢
出距离上次访问最长时间的数据单元.LRU 算法流程如图 2 所示,LRU 算法的数据单元存储空间上限为 4,存储
空间右侧为最近访问的数据,同时,对于每个数据单元标记操作的时间标签,操作包含插入与读取操作.在执行
第 1 步~第 4 步时,在存储空间未满的状态下,依次将数据单元 A,B,C,D 插入到存储空间中.在第 5 步时,由于存储
空间已满,LRU 算法选择距离上次访问最长时间的数据单元 A 进行踢出,并插入新数据单元 E;在第 6 步时,由于
数据单元 B 被访问,将数据单元 B 移至存储空间最右侧,同时更新时间标签;第 7 步时,需要插入新数据单元 F,
由于存储空间已满,与第 5 步相同,此步踢出最左侧数据单元 C,将 F 放入最右侧存储空间中.LRU 由于存在算法
[5]
实现简单、在一定场景下命中率高、对应用性能影响小的特点,被缓存替换系统广泛使用,如 memcached 、
[8]
[4]
memC3 、MICA 等.

Fig.2 Using LRU replacement police manages data items

图 2 通过 LRU 缓存替换策略管理数据单元
LRU 算法在实现过程中,通常采用链表和时间戳两种方式.采用链表方式进行实现时,通常与邻接散列表结
[5]
合使用 ,通过数据单元内的指针快速访问散列表和 LRU 算法管理的数据结构.采用时间戳的方式,常用于固定