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

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

hardware computing capabilities and concurrency performance, various types of system software tasks with parallel computing as the core
have been optimized on the GPU and have achieved considerable performance promotion. Due to the sparseness and randomness, using
the existing parallel structure of the hash table directly on the GPU will inevitably bring high-frequency memory access and frequent bus
data transmission, which affects the performance of the hash table on the GPU. This study focuses on the analysis of memory access, hit
rate, and index overhead of hash table indexes in the cache system. A hybrid access cache index framework CCHT (cache cuckoo hash
table) adapted to GPU is proposed and provided. The cache strategy required by index and index overhead allows concurrent execution of
write and query operations, maximizing the use of the computing performance and concurrency characteristics of GPU hardware, reducing
memory access and bus transferring overhead. Through GPU hardware implementation and experimental verification, CCHT has better
performance than other cache indexing hash table while ensuring cache hit rate.
Key words: system software; cache index; hash table; GPU

在系统软件与高性能数据应用中,散列表(hash table)是一类重要和常见的数据索引结构.通过把关键码值
(key value)映射到表中一个内容位置来访问对应的数据记录,以大幅度加快数据查找的速度.在内存关系型数
据库 [1−3] 和关键码值类型数据库 [4,5] 领域,散列表作为核心的系统组件提供了关键的数据索引接结构,通过映射
[6]
函数将数据索引至对应位置.具体地,网络、云计算和物联网服务的重要系统组件 ,基于键值的内存缓存系统,
[8]
[7]
[5]
如 memcached 、Ramcloud 和 MemC3 ,都采用了散列表来提供内存内的高性能数据索引服务.内存缓存
系统通过将数据从相对内存访问速度慢的磁盘等存储介质加载入内存,以提升应用程序对数据访问的性能.
由于内存通常不能容纳所有数据,当内存空间满时,缓存替换系统通过缓存替换算法踢出部分缓存数据为新
数据提供空间.
[9]
在散列表的现有工作中,基于 cuckoo 算法的散列表 CHT(cuckoo hash table) 通过将原有单一数据映射到
多个桶(bucket)中.CHT 代替了传统散列表的映射与链表式操作的方法,具有快速访问与节省空间的特征,在散
列表管理 [10−12] 和数据存储系统 [4,8,13−16] 上得到了广泛的应用与研究.
典型的 CHT 不支持插入和查询操作同时发生.它将数据通过两种不同的散列算法映射到两个不同的桶中,
每个桶中有 4 个槽(slot)允许存放数据.每个数据对应一组键值数据(key-value pair).在执行插入操作时,判断映
射桶中是否有空闲槽,如果有,则进行插入;如果没有空闲槽,则通过对现有单元中存储数据进行散列与替换获
得空闲槽进行插入.进而,如果在键值对数据插入时需要替换槽中数据,CHT 会随机选择一个待替换键值对 KV′
进行置换,通过散列算法计算 KV′对应另一可选桶,将 KV 放入原有 KV′所在槽中;如果另一可选桶有空闲槽,则
将 KV′放入该空间槽中;如果该桶没有空闲槽,则在该桶内随机选择一个槽中的数据按相同方式继续进行置换,
直至找到空闲槽.装载率是存储数据数量与散列表槽数量的比值,用于衡量散列表当前负载情况.当装载率高
时,由于剩余空闲槽数量少,插入操作中数据置换频发,导致 CHT 频繁访问内存,同时 CPU 中出现大量临时性缓
存,散列表性能受到影响.
在基于键值的内存缓存系统中,这类系统主要的工作负载特点是读操作相比写操作更为频繁 [17,18] .当读操
作的请求未命中时,系统将读操作请求的数据写入内存缓存 [19] .当未命中的读操作请求数量增多时,由于频繁写
入缓存未命中的数据,导致了基于键值的内存缓存系统工作负载引入了更多的替换操作.当散列表装载率高时,
基于键值的内存缓存系统 CHT 频发,导致了大量内存访问,降低了缓存系统整体性能.因此,基于键值的内存缓
存系统散列索引方法在减少写操作访问内存的同时,需要保证系统的命中率,减少写操作数量.随着内存缓存数
据量的大幅增加,在多核 CPU 上并行散列表结构的索引系统已经逐渐出现性能瓶颈,亟需进一步改进散列表的
高性能和可扩展性.
硬件的发展与变迁推动着系统软件的演化 [20] .随着 GPU 硬件计算能力和并发性能的提升,更多的系统任务
在 GPU 上运行.键值存储缓存系统和关系型数据库中的 CHT 相关工作,在 GPU 等硬件的性能上得到了一定的
提升 [10,21−24] .然而,现有的 CHT 在多核 CPU 和 GPU 硬件上的并行优化方法中,系统在获取数据时的操作并不高
效,计算系统的性能仍然受到内存带宽的限制 [25−28] .首先,由于散列表的稀疏性和随机性,在访问数据保存在芯
片缓存后,下次访问之前,被其他访问的数据替换逐出芯片缓存,导致芯片缓存的低效利用以及大量获取数据的
内存访问,从而系统性能受到影响.Xie 等人 [29,30] 提出了针对 GPU 的 cache bypassing 方法来减少芯片缓存的低