[發明專利]一種針對非易失內存的哈希表構建方法及系統

有效

• 申請號: 201710332674.5
• 申請日: 2017-05-12
• 公開（公告）號: CN107153707B
• 公開（公告）日: 2020-08-14
• 發明（設計）人: 華宇;左鵬飛;馮丹
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F16/22
• 分類號: G06F16/22
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 廖盈春;李智

本發明公開了一種針對非易失內存的哈希表構建方法及系統。本發明方法構建一個哈希表，該哈希表邏輯上構建成一個倒立的完全二叉樹，該二叉樹的所有葉子節點是可尋址的單元，所有的非葉子節點是不可尋址單元且作為葉子節點處理哈希沖突的備用單元；從葉子節點到根節點路徑上的所有非葉子節點用于存儲在該葉子節點處發生哈希沖突的沖突元素；進一步刪除該二叉樹底部的多層只保留頂部剩余的層；該哈希表中每個元素對應兩個不同的哈希位置，這兩個哈希位置通過使用兩個不同的哈希函數計算得到。本發明還實現了一種針對非易失內存的哈希表構建系統。本發明技術方案所構建的哈希表不會造成任何額外的寫，并且具有高的空間利用率和低的請求延遲。

技術領域

本發明屬于計算機數據存儲領域，更具體地，涉及一種針對非易失內存的哈希表構建方法及系統。

背景技術

傳統的內存技術DRAM和SRAM，已經被廣泛使用在計算機系統的內存層次中分別作為主存和片上緩存。但是這些傳統的內存技術面臨不斷增加的泄漏功耗和有限的可擴展性等問題。新型的非易失內存技術(NVM)，如相變存儲器(PCM)，阻變存儲器(ReRAM)和自旋扭矩存儲器(STT-RAM)，由于具有高密度、高可擴展性和接近于零的待機能耗等優點，被提出作為DRAM和SRAM的替代品。然而，NVM在寫耐久性和寫性能上具有一定的局限性。NVM的存儲單元只能容忍有限次數的寫，例如PCM的每個存儲單元只能寫1000萬到1億次。對NVM的寫操作不僅磨損有限的耐久性，并且造成比讀操作更高的延遲和能耗開銷。

隨著計算機體系結構中內存特性的重大改變，出現了一個重要的問題，也就是：如何改進內存中的數據結構來更有效地適應NVM。本發明主要關注基于哈希的數據結構。由于快速地查詢響應和常數級的尋址復雜度，哈希表被廣泛應用在主存和緩存中來創建索引和查詢表。在傳統的內存技術DRAM和SRAM上設計哈希表主要考慮兩個因素：空間利用率和請求延遲。相比于DRAM和SRAM，在NVM上設計哈希表的一個重要挑戰是，處理有限的寫耐久性和讀寫不對稱性。

在基于哈希的數據結構中，哈希沖突實際上是無法避免的。傳統的處理哈希沖突的哈希表構建方法主要包括鏈哈希法、線性探測法、雙選擇哈希法、布谷鳥哈希法和羅賓漢哈希法等。但是，根據經驗分析和試驗評估，大部分現有的哈希表構建方法都會造成許多額外的內存寫，這對于NVM的寫耐久性是不友好的。

發明內容

針對現有技術的以上缺陷或改進需求，本發明提供了一種針對非易失內存的哈希表構建方法及系統，其目的在于將哈希表邏輯上構建成一個倒立的完全二叉樹，葉子節點是可尋址的單元，非葉子節點是不可尋址單元且作為葉子節點處理哈希沖突的備用單元，用于存儲沖突元素，刪除該二叉樹底部的多層，同時每個元素對應兩個不同的哈希位置，兩個哈希位置通過使用兩個不同的哈希函數計算得到。由此不會對NVM造成任何額外的寫，并且具有高的空間利用率和低的請求延遲。

為實現上述目的，按照本發明的一個方面，提供了一種針對非易失內存的哈希表構建方法，該方法包括以下步驟：

(1)位置共享：將哈希表中的所有存儲單元邏輯上組織成一個倒立的完全二叉樹，該二叉樹頂層的所有葉子結點為哈希函數尋址單元，當葉子結點發生哈希沖突的時候，沖突元素儲存在葉子結點到根節點路徑上的非葉子結點中；

(2)路徑縮減：只保留所述二叉樹最頂部的K層；

(3)雙路徑哈希：所述哈希表中每個元素使用兩個不同的哈希函數對應到兩個不同的哈希位置。

進一步地，將所述二叉樹的所有節點由頂層到底層依次存儲在一個一維數組中，二叉樹中第N層所有節點占據所述一維數組中的2^L-(L-N)個位置。

進一步地，所述哈希表中每個單元存儲三項數據，分別是單元標識、存儲元素鍵值和存儲元素值；單元標識為“0”表示該單元為空，單元標識為“1”表示該單元被占用。

進一步地，所述哈希表包括以下操作：