[發明專利]一種基于混合DRAM-NVM內存的動態哈希表操作方法

有效

• 申請號: 202010172848.8
• 申請日: 2020-03-12
• 公開（公告）號: CN111459846B
• 公開（公告）日: 2022-03-18
• 發明（設計）人: 王芳;馮丹;鄒曉敏;劉超杰
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F12/02
• 分類號: G06F12/02
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 李智

1.一種基于混合DRAM-NVM內存的動態哈希表操作方法，其特征在于，包括：段分裂操作、插入操作、查詢操作、刪除操作以及恢復操作；

將所述動態哈希表中存儲哈希單元所在段地址的數組結構目錄存儲在DRAM上，將所述動態哈希表中對數組結構目錄進行同步備份的基數樹結構目錄存儲在NVM上，以持久化數組結構目錄，使得系統崩潰后數組結構目錄得以重建；具體為：將所述數組結構目錄存儲在DRAM的一維數組中，初始化為2個目錄項，每次擴展時，構建一個雙倍大小的目錄，再將舊目錄的數據遷移到新數組；將所述基數樹結構目錄存儲在NVM的基數樹中，每個節點占據64字節存儲單元，存儲8個段地址，每次擴展時，原子地增加一個新的樹節點；

采用多層結構存儲哈希單元，將哈希單元存儲在NVM上，且使哈希單元的元素key的哈希值前k位索引哈希表目錄中的段地址；其中，哈希表目錄包括數組結構目錄和基數樹結構目錄；k為正整數。

2.根據權利要求1所述的基于混合DRAM-NVM內存的動態哈希表操作方法，其特征在于，在所述哈希單元中，將存儲元素鍵值key和存儲元素值value拆分成多個4字節的塊，并使key的4字節塊和value的4字節塊兩兩進行組合，形成8字節的key-value塊進行存儲；系統崩潰后，還原key值并計算其哈希值，若該哈希值不能索引到當前位置，則表明此元素不一致，丟棄此元素。

3.根據權利要求1所述的基于混合DRAM-NVM內存的動態哈希表操作方法，其特征在于，將所述動態哈希表中所存儲的哈希單元中哈希值的公共位記為全局深度gd，存放在哈希表目錄中，其中，全局深度占據8字節存儲單元，當數組結構目錄雙倍擴展時，使全局深度自增1；

其中，所述多層結構包括多個段，每個段包括2ⁿ個桶和一個后備區域，每個桶包括多個哈希單元；其中，后備區域用于存儲哈希沖突項，占據m個桶；桶占據64個字節；多層結構中的段與哈希表目錄中的段地址相對應；將每個段中存儲的哈希單元中哈希值的公共位記為局部深度ld，用于標注是否需要擴展數組結構目錄；其中，ld＝gd-log₂r，r為指向同一個段的段地址的數量，記為引用計數；n、m為正整數。

4.根據權利要求3所述的基于混合DRAM-NVM內存的動態哈希表操作方法，其特征在于，使所述哈希單元中哈希值的前k位索引哈希表目錄中該哈希單元所在的段地址；使哈希值的后n位索引多層結構中該哈希單元所在的桶位置。

5.根據權利要求1-4任意一項所述的基于混合DRAM-NVM內存的動態哈希表操作方法，其特征在于，對基于混合DRAM-NVM內存的動態哈希表進行段分裂的操作方法，包括以下步驟：

1.1)當待拆分段的局部深度小于目錄的全局深度時，創建一個新的段，重新計算待拆分段中所有的哈希元素的哈希值，將哈希值的前綴與新段索引相等的哈希元素遷移到新段中，修改對應的兩個目錄，并修改兩個段的局部深度，即被拆分段的局部深度加一，新段的局部深度與被拆分段相等；

1.2)當待拆分段的局部深度等于目錄的全局深度時，對于基數樹結構的目錄，直接增加一個節點，對于數組結構的目錄，創建一個雙倍舊目錄大小的新目錄，將舊目錄的項遷移到新目錄中；然后采用步驟1.1)所述的方法進行后續段拆分操作。