手机网站前端用什么做,网络开发工具有哪些,网站多多,上市公司网站建设EuroSys 2024 Paper 论文阅读笔记整理
问题
近似成员关系查询#xff08;AMQ#xff09;数据结构可以高效地近似确定元素是否在集合中#xff0c;例如Bloom滤波器[10]、cuckoo滤波器[23]、quotient滤波器[8]及其变体。但AMQ数据结构的内存消耗随着数据规模的增长而快速增长…EuroSys 2024 Paper 论文阅读笔记整理
问题
近似成员关系查询AMQ数据结构可以高效地近似确定元素是否在集合中例如Bloom滤波器[10]、cuckoo滤波器[23]、quotient滤波器[8]及其变体。但AMQ数据结构的内存消耗随着数据规模的增长而快速增长这限制了其处理大量数据的能力。原因在于单个AMQ数据结构的内存消耗增加多个AMQ数据结构同时运行。
AMQ数据结构的优化目标包括空间占用、吞吐量和重建开销。新兴的持久存储器提供了接近DRAM的访问速度和TB级的容量有助于AMQ数据结构处理海量数据。然而由于密集的随机访问和/或顺序写入现有的AMQ数据结构在持久性存储器上表现不佳。
挑战
根据解决哈希冲突的方式用于不同存储介质的现有AMQ数据结构通常可以分为两类但都不适合移植到持久内存 使用全局技术来解决哈希冲突如Bloom过滤器[10]和cuckoo过滤器[23]。在整个数据结构中分布元素来解决哈希冲突。但不可避免地导致对存储介质的大量随机访问降低了持久存储器上数据结构的性能。一些工作试图缓解这个问题如阻塞Bloom过滤器[55]和单个哈希阻塞Bloom滤波器[54]但会导致更高的误报率和更高的内存消耗[2364]。 使用局部技术来解决哈希冲突如quotient滤波器[8]和计数quotient滤波器[51]移动冲突的位置的所有后续元素来解决哈希冲突。尽管只需要对存储介质进行顺序访问但每次插入操作都会产生大量额外的写入请求从而降低性能。
其他技术挑战 同时降低随机访问和顺序写入的次数以便在持久内存上获得更高的性能。因为持久内存的顺序读取、随机读取、顺序写入和随机写入带宽分别比DRAM[31]慢3倍、8倍、11倍和14倍。 有效地支持并发。如何设计正确高效的并发算法利用多个核心的性能。 减少支持恢复的开销。但程序异常结束且插入操作意外中断部分更新的数据将持久存在AMQ数据结构中当程序重新启动时需要回滚部分更新的数据。以前的工作如持久内存上的树和哈希表[314244]使用日志记录技术从故障中恢复。然而对于轻量级AMQ数据结构日志记录的开销很高大大降低了AMQ数据架构的性能。
本文方法
本文提出了一种新的AMQ数据结构称为Wormhole Filters通过减少随机访问和顺序写入减少了日志记录的数量以适用于持久内存。 数据结构。提出了两种创新技术距离指纹对和基于桶的虫洞哈希表。距离指纹对可以同时减少随机访问和顺序写入还可以减少支持恢复的开销。基于桶的虫洞哈希表可以增强操作的缓存局部性。 插入算法。提出了基于距离指纹对的持久内存插入算法。对于插入操作虫洞过滤器通过移动少量相邻元素来解决哈希冲突减少了插入期间对持久内存的随机访问和顺序写入的次数。此外这种设计只需要顺序获取少量锁从而实现对并发的支持。 查找/删除算法。提出了基于桶的虫洞哈希表的持久内存查找/删除算法。虫洞过滤器可以以恒定的时间复杂度执行查找和删除操作查找和删除操作只需要顺序访问少量的存储桶这些存储桶可以被持久存储器的访问粒度所覆盖从而实现高吞吐量。 恢复算法。提出了轻量级的持久内存恢复算法。通过精心设计的桶结构和插入机制减少了插入所需的日志记录数量从而减少了支持恢复的开销。
理论分析和实验结果表明Wormhole Filters的性能优于最先进AMQ数据结构。实现了最佳基线的23.26倍插入吞吐量、1.98倍正向查找吞吐量和8.82倍删除吞吐量。
总结
针对利用持久内存的近似成员关系查询AMQ数据结构如Bloom过滤器现有方法随机访问和顺序写入次数多为了支持恢复开销高不适用于持久内存。本文提出Wormhole Filters设计了新数据结构距离指纹对和基于桶的虫洞哈希表通过减少随机访问和顺序写入减少了日志记录的数量以适用于持久内存。
