支持分页显存的高性能哈希表索引系统

摘要

哈希表以访问效率时间复杂度O(1)著称,作为一类可提供大规模数据高效访问的算法和数据结构为各类大数据应用所采用,例如,适用于各类新兴高性能(HPC)领域、数据库领域的工作负载和场景.随着高性能协处理器GPU硬件性能的日益提升,面向高性能GPU环境的哈希表并行优化已逐渐吸引了大量研究工作.当前的各类GPU哈希表优化方法和解决方案集中于利用GPU的大规模线程环境和高内存带宽来提升哈希表的事务高并发性处理和键值对数据快速访问.然而,由于现有GPU哈希表结构的研究工作普遍忽略了GPU资源有效管理,并没有以如何充分利用GPU线程资源和显存资源.同时,由于GPU显存空间的大小限制,用于存储哈希表结构数据的空间有限,无法应对更大规模的哈希表结构.因此,面向GPU环境下的哈希表方法的可扩展性和性能仍存在着技术挑战.本文提出并设计了一种面向GPU环境的可处理大规模并发事务的哈希表技术,命名为Starfish. Starfish提出了新的基于异步GPU流的“交换层”(swap layer)技术,用以支持GPU显存外的动态哈希表,同时也保障了GPU哈希表的索引方法性能.为了解决GPU大规模线程的访问带来的哈希冲突开销, Starfish设计了一类紧凑型数据结构,并研究了一种可分页显存的分配方法,不仅为GPU哈希表技术提供了静态哈希方法的高性能,而且也支持动态哈希的高可扩展性.性能评估实验表明, Starfish显著优于其他GPU哈希表技术,包括cudpp-Hash, SlabHash.