如何爲許多數據塊存儲散列，並通過散列檢索列表？

Question

我正在開發一個實施重複數據刪除的開源項目。 （關於該項目的鏈接，請參閱下面的兩個超鏈接） 當前項目的性能相當好，但隨着更多塊寫入磁盤會降低性能。 這是由於HashManager。對於每個寫入的塊，hashmanager存儲一個Hash-BlockId對。對於重複數據刪除過程，需要具有給定散列的塊標識符列表。 （使用的散列是Crc32） 對於HashManager的接口，請參閱the source。

接口的當前implementation將列表存儲在256個文件（crc & 0xFF）中，並將完整列表加載到內存中。當需要另一個列表時，先前的列表被保存並且下一個被加載。除了這可能導致內存耗盡的事實之外，這意味着降低性能。

有什麼好的選擇來解決這個問題？

（只是爲了clearify：塊完全檢查，看他們是否重複數據刪除之前匹配）

Answer 1

我不是在磁盤上的結構方面的專家，但我聽說B樹通常用於執行存儲在磁盤上的鍵值映射。所以我想你可以有一個B-Tree索引的CRC，然後將某種鏈接存儲到一個塊ID列表中。您也可以將列表組合到B樹結構中，通過有效地使用一個關鍵字（它是CRC和一個塊ID的連接），然後在B-樹上進行有效的前綴/範圍查詢。 「在計算機科學中，B樹是一種樹數據結構，它保持數據的排序並允許在對數時間內進行搜索，順序訪問，插入和刪除.B樹是二進制搜索的泛化（Comer 1979，p。123）與自平衡二叉搜索樹不同，B-樹針對讀取和寫入大塊數據的系統進行了優化，它通常用於數據庫和文件系統「。

Answer 2

如果您使用256個列表文件來存儲crcs，第一個明顯的步驟是將所有在列表0中以字節0開頭的crcs，列表文件1中所有以1字節爲1的crcs等等然後在每個文件中只存儲crc的最後三個字節。這將節省25％的關鍵存儲空間，並且可能也會加快處理速度。

第二件事是做一個4千兆位內存標誌陣列，以顯示是否一個4字節的crc已經在列表中註冊。這將極大地加速向陣列中添加新項目，因爲您會知道是否需要先查找現有條目 - 如果該位爲零，那麼crc尚未使用。根據數據域開發人員撰寫的一篇論文，這種不必要的查找是最慢的攝取過程（他們有不同的方法來避免它）。

我假設你正在保存列表，因爲你正在修改它們。我建議不要重寫整個列表，而是將所有更改放在文件末尾，以便可以追加到文件的末尾而不是重寫整個列表。使用一個鏈接列表結構，該鏈接列表結構以文件末尾的指針開始，每個附加內容在文件末尾的列表中寫入一個新的標題。您可以通過在列表中更高的位置添加一個刪除標記來標記要刪除的條目。然後，您可以定期垃圾收集每個列表以減少列表大小（例如，每週或每月進行一次批處理）。您可以對列表修改進行相同的操作。只需編寫一個新的條目來替換舊的條目，並帶上一個標誌。然後垃圾收集定期刪除舊的條目。

任何你可以做的事情來構造列表，所以你不需要在內存中加載整個事物，每次都會加快速度。儘可能少地移動數據，儘可能少。

這是我在堆棧溢出中寫的第一件事，所以請原諒，如果我的發佈不遵循首選的規範。

我注意到上面的說明我的回覆編輯區域，我不應該要求澄清，我想這是我可以有更多的樂趣，只是猜測確切的問題是什麼。我希望我的猜測很接近，我的答案包含有用的元素。