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]，但会导致更高的误报率和更高的内存消耗[23，64]。

• 使用局部技术来解决哈希冲突（如quotient滤波器[8]和计数quotient滤波器[51]）移动冲突的位置的所有后续元素来解决哈希冲突。尽管只需要对存储介质进行顺序访问，但每次插入操作都会产生大量额外的写入请求，从而降低性能。

其他技术挑战：

• 同时降低随机访问和顺序写入的次数，以便在持久内存上获得更高的性能。因为持久内存的顺序读取、随机读取、顺序写入和随机写入带宽分别比DRAM[31]慢3倍、8倍、11倍和14倍。

• 有效地支持并发。如何设计正确高效的并发算法，利用多个核心的性能。

• 减少支持恢复的开销。但程序异常结束且插入操作意外中断，部分更新的数据将持久存在AMQ数据结构中，当程序重新启动时，需要回滚部分更新的数据。以前的工作，如持久内存上的树和哈希表[31，42，44]，使用日志记录技术从故障中恢复。然而，对于轻量级AMQ数据结构，日志记录的开销很高，大大降低了AMQ数据架构的性能。

本文方法

本文提出了一种新的AMQ数据结构，称为Wormhole Filters，通过减少随机访问和顺序写入，减少了日志记录的数量，以适用于持久内存。

• 数据结构。提出了两种创新技术：距离指纹对和基于桶的虫洞哈希表。距离指纹对可以同时减少随机访问和顺序写入，还可以减少支持恢复的开销。基于桶的虫洞哈希表可以增强操作的缓存局部性。

• 插入算法。提出了基于距离指纹对的持久内存插入算法。对于插入操作，虫洞过滤器通过移动少量相邻元素来解决哈希冲突，减少了插入期间对持久内存的随机访问和顺序写入的次数。此外，这种设计只需要顺序获取少量锁，从而实现对并发的支持。

• 查找/删除算法。提出了基于桶的虫洞哈希表的持久内存查找/删除算法。虫洞过滤器可以以恒定的时间复杂度执行查找和删除操作，查找和删除操作只需要顺序访问少量的存储桶，这些存储桶可以被持久存储器的访问粒度所覆盖，从而实现高吞吐量。

• 恢复算法。提出了轻量级的持久内存恢复算法。通过精心设计的桶结构和插入机制，减少了插入所需的日志记录数量，从而减少了支持恢复的开销。

理论分析和实验结果表明，Wormhole Filters的性能优于最先进AMQ数据结构。实现了最佳基线的23.26倍插入吞吐量、1.98倍正向查找吞吐量和8.82倍删除吞吐量。

总结

针对利用持久内存的近似成员关系查询（AMQ）数据结构（如Bloom过滤器），现有方法随机访问和顺序写入次数多，为了支持恢复开销高，不适用于持久内存。本文提出Wormhole Filters，设计了新数据结构距离指纹对和基于桶的虫洞哈希表，通过减少随机访问和顺序写入，减少了日志记录的数量，以适用于持久内存。