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，設計了新數據結構距離指紋對和基于桶的蟲洞哈希表，通過減少隨機訪問和順序寫入，減少了日志記錄的數量，以適用于持久內存。