实验室博士生孙园园在华宇教授的指导下提出了基于哈希冲突缓解机制的实时数据查询方法,称为MinCounter。相关研究成果被IEEE Transactions on Parallel and Distributed Systems (TPDS)录用,题为”A Collision-Mitigation Cuckoo Hashing Scheme for Large-scale Storage Systems (大规模存储系统中基于缓解冲突的Cuckoo哈希机制)”。IEEE TPDS是中国计算机学会推荐的A类期刊,是并行与分布式系统领域中的重要国际期刊,这也是实验室首次独立完成的计算机学会A类期刊论文。
这种方法主要是考虑到在写入数据时对哈希表每个位置访问频率具有不均衡性,提出了一种哈希冲突缓解机制。给每个位置分配一个counter来记录在整个数据集插入操作过程中发生哈希冲突并执行踢出操作的次数。MinCounter的基本原理是选择unbusy的踢出路径而不是随机选择,这能尽快寻找到空闲位置来避免或减少哈希冲突并减少时延。通过大量实验测试和分析表明,相关研究方法在空间利用率和时间开销等方面显著优于目前已有的设计方法。
系统架构图和主要测试结果