論文速讀：VLDB-20 Dash: Scalable Hashing on Persistent Memory

這是VLDB2020的論文，也是近幾年基於持久記憶體資料結構工作中我個人比較喜歡的文章之一。

相關背景介紹：

Intel Optane Memory（PMem）是一種大容量的非易失儲存，大概長這樣：

PMem幾個關鍵特徵：

1。 容量大，一般一根DRAM容量是4-64GB，PMem容量128-512GB，一臺單機記憶體容量輕鬆上TB。

2。 和SSD不一樣，PMem插在記憶體插槽上，訪問單位是位元組，而像傳統塊裝置訪問單位是一個4KB的block

3。 和DRAM比，PMem上儲存的資料在機器掉電或重啟後依然還在

4。 PMem讀寫效能都比DRAM慢

在PMem問世之前，有一些列基於持久儲存設計的資料結構都是基於模擬器設計的，但模擬器和真實的PMem之前還是有很多效能上的差別。

要解決的問題：

之前設計的持久記憶體hash，比如CCEH和Level Hashing跑在PMem上效能不佳，如何基於真實的PMem硬體設計一種新的PMem-based的hash資料結構，設計目標：

1。 快

2。 Load factor高（真實儲存的資料/hash總共佔的記憶體空間）

解決問題的方法：

子問題1：

Hash因為有衝突的存在，一次hash的Put或Get操作都會先把key（比如key是A）計算出hash值，再在hash值對應的桶或者段裡讀取所有的key並和正在查詢的key A進行對比key是否存在。這意味著每一次無論hash的寫（Put）還是讀（Get）操作，都會存在大量讀現有儲存key的操作，這種讀操作在DRAM上效能沒有問題，但在PMem大量的讀嚴重影響效能

解:

是在每個桶內把所有已經儲存的key算一個fingerprint用小空間儲存，這樣每次hash到某個桶只需要讀取一個小的fingerprint塊來判斷查詢的key是否存在。

子問題2：

Hash隨著key插入越來越多，出現衝突的機率也越來越大，從而降低hash的Get和Put的效率。當key插入到一定數量，hash就會觸發rehash擴容從而用更大的空間來儲存hash從而減少衝突的機率，但是這樣做Load factor就降低了

解：

作者們提出了一些列的方法，比如每次插入如果衝突key只插入到當前桶+1和-1的桶內，比如用stash桶兜住一些key，這塊設計建議看原文，有不少細節。

寫在最後：

本文在工程上做得比較完整，支援變長key，快速恢復等，專案已開源。