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

张鸿骏 等:一种适应 GPU 的混合访问缓存索引框架 3041

第 2.3 节描述了基于 LRU 的缓存替换策略,第 2.4 节给出了 CUDA 编程技术的基本概念.
2.1 CHT基本概念
[9]
典型的 CHT 包含两种散列方法对键值数据(KV)进行映射 .图 1 给出了两个典型的插入场景,即将两个不
同的键值数据 KV 1 和 KV 2 插入到 CHT 中.其中,行号标明了散列索引的位置信息,每个位置的桶内按照典型的
CHT 设置有 4 个槽对键值数据进行存储.例如,H 1 和 H 2 表示两个独立的散列方法,每个键值数据可以通过这两
种散列方法映射到两个不同的候选位置上.对于 KV 1 ,映射到位置 0 和位置 2,对于 KV 2 ,映射到位置 3 和位置 5.
当插入 KV 1 时,通过两种散列方法找到对应的候选位置 0 和 2,这两个位置的桶中均有空闲槽用于插入新的键值
数据.根据具体 CHT 的算法,选择 0 或 2 位置的桶加以插入.

Fig.1 Set KV 1 and KV 2 on a CHT
图 1 在 CHT 中插入 KV 1 和 KV 2
当插入 KV 2 时,通过两种散列方法找到对应位置 3 和 5,发现位置 3 和位置 5 的桶中已无空闲槽.当遇到此
种情况时,CHT 会在候选位置的桶中选择一个槽内的键值数据进行踢出,将新的数据放入该槽内,同时通过散列
方法计算踢出键值数据的另一候选位置,如果有空闲槽,则放入,如果没有,则重复踢出置换操作,直至找到空闲
的槽.典型的 CHT 设有踢出置换次数阈值,当达到阈值后,停止踢出替换操作,CHT 进行扩容.CHT 踢出置换操作
的引入,使 CHT 中的空闲槽能更多地被使用,从而使得 CHT 的负载率可以大于 95%.在 KV 2 的插入场景中,由于
对应候选位置 3 和位置 5 的桶中已无空闲槽,则随机选择位置 5 桶中槽内值为 o 的键值数据进行踢出置换,将
KV 2 放入原有位置 5 桶中 o 对应的槽中.通过散列方法计算 o 的另一候选桶位置为 1,查询位置 1 的桶,发现无空
闲槽,则继续选择一个键值数据 d 进行踢出置换,将 o 放在原有 d 的槽空间中.再对 d 进行散列值计算,查看另一
候选位置 4 的桶,有空闲槽.将 d 放入空闲槽中,结束本次插入操作.Li 等人 [29] 证明了采用宽度优先,直至找到一
条可以置换的路径查找策略,是一种有效的踢出置换方式.
当进行查询时,通过 H 1 与 H 2 计算散列值,查找对应位置的桶中槽内键值数据,通过遍历与比较槽内键数据
来获取存储的值数据.
CHT 仅支持同一种任务类型同时发生,如并发插入操作或并发查询操作.当插入和查询操作同时发生时,插
入操作可能因无空闲槽,发生置换操作.此时,若查询正在置换的目标数据,或查询的目标数据在未正确返回前,
目标数据置换入另一桶中的槽内,将造成对已索引数据的查询失败.当发生上述两种情况导致插入与查询同时
进行时,散列表即丧失了数据完整性.CCHT 相对于 CHT 移除了无空闲槽时的置换操作,因此,支持插入和查询
操作并发执行,提升了散列表的并发性能.
2.2 CHT的典型实现
CHT 在实际应用中的性能,受到大量参数的影响.在 CHT 中,关键的散列函数个数与每个位置中的存储空
间个数影响了 CHT 的负载率及访问的延迟.当增加 CHT 中散列函数个数,允许键值数据映射到更多的位置上
时,由于对请求数据的候选地址变多,因此查找空闲槽的机会变大.这种多散列函数的方式可以有效地提升 CHT