论文部分内容阅读
数据量的快速增长给海量存储系统的性能、容量和可拓展性等带来了巨大挑战。存储系统需要消耗大量资源来支持面向海量数据的高吞吐量和低时延的查询服务。然而现有海量存储系统中的内存数据组织结构无法高效支持查询。基于哈希计算的数据组织结构具有常数量级寻址复杂度和快速查询响应等特性,特别是在查询实时性和准确性方面具有显著优势,因此成为优化存储系统性能的一种可行的解决方案。但是,由于哈希函数本身会产生冲突的特性,需要在结构设计和系统实现中充分考虑和解决相关哈希冲突带来的问题。现有的方法在处理哈希冲突时产生了高时延、低效率等问题,布谷鸟哈希(Cuckoo Hashing)能够给数据元素提供备选位置来缓解哈希冲突,提高索引结构构建性能。而针对读操作密集型应用(网页搜索、神经网络训练等)具有可容忍少量查询结果错误的特性,局部灵敏哈希(Locality Sensitive Hashing,LSH)因其具有保持数据局部性和数据降维的特性常被用于支持近似最近邻(Approximate Nearest Neighbor,ANN)查询。然而这两种哈希算法自身也面临一些问题,尤其是布谷鸟哈希表在索引构建过程中因处理哈希冲突而带来的高时延的问题,以及局部灵敏哈希为保证查询准确率而带来的昂贵的存储开销已成为存储系统的性能瓶颈。如何减少哈希表构建过程中由哈希冲突带来的时延和提高近似最近邻查询的准确率以及空间存储效率是现有海量存储系统中内存数据组织结构研究中的热点和难点问题。首先,本文研究了内存数据组织结构构建过程中预判无限循环问题。布谷鸟哈希中通过踢出操作来处理哈希冲突,然而存在踢出路径过长而形成无限循环的风险。当布谷鸟哈希使用两个哈希函数时,数据元素插入操作的踢出路径有且只有两条。通过预先跟踪记录位置关系就可以知道这两条路径最终的状态,而无需执行实际的踢出操作。基于这一观察,提出了一种预判无限循环的布谷鸟哈希方案SmartCuckoo。该方案将哈希表转换为伪森林图(pseudoforest),每个哈希桶等价于伪森林中的一个节点,而每个存储的元素作为伪森林中的一条边。SmartCuckoo的核心思想是将元素间的哈希关系表示为一个有向图并利用其来跟踪记录元素位置来准确预判元素插入过程中无限循环的发生,避免执行逐步探测的开销,从而节省了时间开销和系统资源。实验评估表明SmartCuckoo相对于传统方案提高了25%-75%的插入操作吞吐量以及超过50%的混合操作吞吐量。其次,针对单线程内存数据组织结构效率低下的问题提出并发方案。布谷鸟哈希在执行查询操作时在最坏情况下探测元素所有备选位置的时间开销仍为恒定规模,体现出快读特性;而在元素插入过程中,可能需要执行递归踢出操作将元素踢出当前位置然后插入其备选位置,直到找到空位置或者判定插入失败,因此具有慢写性能瓶颈。为了降低写操作性能开销,提出一种并发布谷鸟哈希方案CoCuckoo。该方案考虑到在伪森林图中,共享踢出路径的插入操作会访问同一子图,而访问不同子图的插入操作不会冲突,因此利用图粒度锁机制来减轻各线程对锁资源的争用,使得一次只允许一个线程访问共享路径,以此支持并发写入和读取操作并提高性能。测试结果表明,CoCuckoo的吞吐量相较于传统方案libcuckoo显著提高了50%-130%。第三,本文针对包含多哈希函数的内存数据组织结构无法有效预判无限循环的问题而研究缓解哈希冲突的方法。在哈希表构建过程中,各哈希桶中发生哈希冲突的频率是不均衡的,即有些桶会经常发生哈希冲突而成为“热”的哈希桶,而有些位置不会频繁发生哈希冲突而成为“冷”的哈希桶。针对这一观察特征,提出了一种基于冲突频率感知来缓解哈希冲突的布谷鸟哈希方案MinCounter。该方案给哈希表中每个哈希桶分配一个计数器来实时记录在该位置发生冲突的次数,当数据元素在插入过程中发生哈希冲突而需要执行踢出操作时,自主选择“冷”(计数器最小的)哈希桶来形成“不忙碌”(冲突少的)的踢出路径以尽快找到可用于存储的空桶,从而缓解哈希冲突和数据迁移。实验评估表明与传统布谷鸟方案相比,MinCounter减少了20%-55%的哈希冲突,降低超过35%的索引构建时间开销,并提升了5%的哈希表利用率。最后,本文研究了针对读操作密集型应用的内存数据组织结构支持近似最近邻查询问题。传统局部灵敏哈希中的函数参数是随机设置的,因此需要大量的哈希表才能保证查询准确性,造成昂贵的额外存储和计算开销。针对这一问题,提出了一种基于数据分布感知的局部灵敏哈希方案DLSH。该方案的核心思想是利用主成分分析(Principal Component Analysis,PCA)获取数据分布的主成分并作为LSH机制中哈希函数的投影向量,进一步量化函数权重,调整函数间隔值的参数以提高查询准确性,同时根据候选结果命中频率精炼查询结果集以减少计算开销。实验评估表明与传统局部灵敏哈希方案相比,DLSH提高了20%-50%的查询精确率,25%-60%的F-Measure值,同时显著减少了98%的空间开销以及50%-85%的查询时间开销。