信息存储系统教育部重点实验室 English Version

博士生孙园园的论文被会议ATC 2017录用

点击次数:发布时间:2017-05-17 09:29作者:admin

 实验室博士生孙园园的论文“SmartCuckoo: A Fast and Cost-Efficient Hashing Index Scheme for Cloud Storage Systems”被2017年USENIX年度技术会议 (2017 USENIX Annual Technical Conference, ATC 2017)作为长文全文录用。

 快速查询服务对于提高大规模存储系统的整体性能至关重要。Cuckoo hashing机制因其简单易用的特性被广泛应用于支持查询服务。然而传统的cuckoo hashing机制无法解决元素插入过程中潜在存在的踢出路径无限循环问题,这将导致较高的索引表构建时延,严重影响系统性能。

 博士生孙园园在华宇教授的指导下,提出了一种高效的cuckoo hashing方法 (SmartCuckoo)能在实际插入操作之前预测结果。SmartCuckoo将哈希关系表示为有向图并利用其跟踪记录元素位置,来准确预测无限循环的发生,避免了执行逐步探测昂贵的成本开销。其将索引表中每个桶看作是图的一个节点,将索引表中每个元素看作是图的一条边,每次插入操作将新增的探测桶加入对应子图,图边数同时加1。该有向图中每个子图至多存在一个回路,当子图中有且只有一个回路(子图边数等于节点数)时,该子图为满载子图;反之为非满载子图。当执行插入操作时,若子图满载,即插入该元素的踢出路径会形成回路导致无限循环,因此插入操作一定失败;带子图非满载时,该子图中一定存在一个空位,经过有限次踢出操作时,所有元素都将插入索引表中,则插入操作一定成功。大量实验结果表明,SmartCuckoo能够准确预测元素插入结果,并且能够在保持其高效的查询性能的同时很大程度地提高系统的插入操作吞吐量。

 这项研究成果发表在中国计算机学会推荐的A类国际会议USENIX ATC 2017 (2017年7月12日-7月14日,美国加州圣克拉拉)。ATC是计算机系统领域的旗舰会议,本届会议收到283篇投稿,最终录用60篇,录用率为21%。

Top