[發(fā)明專利]一種基于混合DRAM-NVM內(nèi)存的動(dòng)態(tài)哈希表操作方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202010172848.8
• 申請(qǐng)日: 2020-03-12
• 公開（公告）號(hào): CN111459846B
• 公開（公告）日: 2022-03-18
• 發(fā)明（設(shè)計(jì)）人: 王芳;馮丹;鄒曉敏;劉超杰
• 申請(qǐng)（專利權(quán)）人: 華中科技大學(xué)
• 主分類號(hào): G06F12/02
• 分類號(hào): G06F12/02
• 代理公司: 華中科技大學(xué)專利中心 42201
• 代理人: 李智

本發(fā)明公開了一種基于混合DRAM?NVM內(nèi)存的動(dòng)態(tài)哈希表操作方法，包括：段分裂操作、插入操作、查詢操作、刪除操作以及恢復(fù)操作；其中，將動(dòng)態(tài)哈希表中存儲(chǔ)哈希單元所在段地址的數(shù)組結(jié)構(gòu)目錄存儲(chǔ)在DRAM上，將動(dòng)態(tài)哈希表中對(duì)數(shù)組結(jié)構(gòu)目錄進(jìn)行同步備份的基數(shù)樹結(jié)構(gòu)目錄存儲(chǔ)在NVM上，以持久化數(shù)組結(jié)構(gòu)目錄，使得系統(tǒng)崩潰后數(shù)組結(jié)構(gòu)目錄得以重建；并采用多層結(jié)構(gòu)存儲(chǔ)哈希單元，將哈希單元存儲(chǔ)在NVM上；本發(fā)明采用了交叉存儲(chǔ)鍵值對(duì)和原子段拆分機(jī)制來保證數(shù)據(jù)的一致性，所提供的哈希表充分利用了混合內(nèi)存的優(yōu)勢，數(shù)據(jù)一致性的開銷較小，并且具有很低的訪問延遲。

技術(shù)領(lǐng)域

本發(fā)明屬于計(jì)算機(jī)數(shù)據(jù)存儲(chǔ)領(lǐng)域，更具體地，涉及一種基于混合DRAM-NVM內(nèi)存的動(dòng)態(tài)哈希表操作方法。

背景技術(shù)

近年來，一些新型的非易失內(nèi)存(Non-Volatile Memory，NVM)技術(shù)開始涌現(xiàn)，如相變存儲(chǔ)器(phaseChange Memory，PCM)、憶阻器(ReRAM)、自旋扭矩磁存儲(chǔ)器(STT-MRAM)和3D-XPoint等。NVM既有傳統(tǒng)磁盤的掉電非易失性，也有DRAM的快速訪存、按字節(jié)修改尋址的特性。這些優(yōu)良特性使其有望取代DRAM作為主存。但是當(dāng)前的NVM技術(shù)仍具有不對(duì)稱的讀寫延遲和有限的磨損次數(shù)等缺點(diǎn)，更適合與DRAM一起連接在內(nèi)存總線上組成混合內(nèi)存。

計(jì)算機(jī)內(nèi)存介質(zhì)和體系結(jié)構(gòu)的改變使傳統(tǒng)的索引結(jié)構(gòu)變得不再高效，因?yàn)樗鼈儧]有充分利用NVM的字節(jié)尋址特性并且忽略了數(shù)據(jù)一致性的問題。保障NVM的崩潰一致性需要使數(shù)據(jù)的更新按照指定的順序?qū)懭氲絅VM中，但是CPU和內(nèi)存控制器為了優(yōu)化性能可能會(huì)對(duì)內(nèi)存操作進(jìn)行重排序。因此，現(xiàn)有方案會(huì)使用內(nèi)存刷新和內(nèi)存屏障指令顯式地約束操作的順序，如intelX86中的clfush和mfence。但是這些指令會(huì)帶來不小的性能開銷。目前沒有高效的優(yōu)化機(jī)制來減少mfence和clflush指令帶來的開銷。另外，現(xiàn)代處理器只保證8字節(jié)的原子寫。當(dāng)更新大于8字節(jié)的數(shù)據(jù)時(shí)系統(tǒng)發(fā)生故障或意外斷電，系統(tǒng)重啟后，只有那些部分更新的數(shù)組結(jié)構(gòu)可以被恢復(fù)，這樣會(huì)帶來數(shù)組結(jié)構(gòu)的一致性問題。為了解決這一問題，需要使用日志或者寫時(shí)復(fù)制技術(shù)。這些機(jī)制會(huì)帶來額外的寫操作，并且其技術(shù)實(shí)現(xiàn)過程還存在隱含的順序約束，如，持久化日志之后才能執(zhí)行更新操作。

目前已經(jīng)出現(xiàn)了很多基于持久性內(nèi)存的哈希索引的研究，然而這些方法全部是基于只有NVM作為內(nèi)存的系統(tǒng)，不能很好地利用混合DRAM-NVM內(nèi)存的優(yōu)點(diǎn)。其中，對(duì)于靜態(tài)哈希，當(dāng)哈希沖突不可解時(shí)，需要?jiǎng)?chuàng)建一個(gè)雙倍大小的新表，再將舊表中所有的哈希元素遷移到新表中，產(chǎn)生不可容忍的訪問延遲。而對(duì)于可擴(kuò)展哈希，雖然對(duì)可擴(kuò)展哈希表進(jìn)行操作時(shí)，可以按需動(dòng)態(tài)分配和取消分配哈希桶，但是其將處于關(guān)鍵路徑的目錄放置在慢速的NVM中，訪問延遲較高。除此之外，現(xiàn)有的哈希表操作方法在數(shù)據(jù)一致性的保障機(jī)制上，都需要采用緩存行刷新和內(nèi)存屏障指令，花費(fèi)的開銷也較大。

發(fā)明內(nèi)容

本發(fā)明提供一種基于混合DRAM-NVM內(nèi)存的動(dòng)態(tài)哈希表操作方法，在滿足系統(tǒng)崩潰時(shí)數(shù)據(jù)可恢復(fù)的前提下，解決現(xiàn)有的哈希表操作方法由于將處于關(guān)鍵路徑的目錄放置在慢速的NVM中而導(dǎo)致的訪問延遲較高的技術(shù)問題。

為了實(shí)現(xiàn)上述目的，本發(fā)明提出了一種基于混合DRAM-NVM內(nèi)存的動(dòng)態(tài)哈希表操作方法，包括：段分裂操作、插入操作、查詢操作、刪除操作，以及恢復(fù)操作；

其中，動(dòng)態(tài)哈希表中存儲(chǔ)哈希單元所在段地址的數(shù)組結(jié)構(gòu)目錄存儲(chǔ)在DRAM上，將動(dòng)態(tài)哈希表中對(duì)數(shù)組結(jié)構(gòu)目錄進(jìn)行同步備份的基數(shù)樹結(jié)構(gòu)目錄存儲(chǔ)在NVM上，以持久化數(shù)組結(jié)構(gòu)目錄，使得系統(tǒng)崩潰后數(shù)組結(jié)構(gòu)目錄得以重建；

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