[發(fā)明專利]高并發(fā)索引B+鏈表數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)與實(shí)現(xiàn)方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201811129622.9
• 申請(qǐng)日: 2018-09-27
• 公開（公告）號(hào): CN109407978B
• 公開（公告）日: 2020-07-28
• 發(fā)明（設(shè)計(jì)）人: 舒繼武;陸游游;胡慶達(dá);劉昊
• 申請(qǐng)（專利權(quán)）人: 清華大學(xué)
• 主分類號(hào): G06F3/06
• 分類號(hào): G06F3/06;G06F12/02
• 代理公司: 北京清亦華知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11201
• 代理人: 張潤(rùn)

本發(fā)明公開了一種高并發(fā)索引B+鏈表數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)與實(shí)現(xiàn)方法，該方法包括：同時(shí)使用基于數(shù)組的和基于元素得到數(shù)據(jù)結(jié)構(gòu)；對(duì)于數(shù)據(jù)結(jié)構(gòu)的非葉子節(jié)點(diǎn)，采用預(yù)設(shè)的B+樹數(shù)據(jù)結(jié)構(gòu)，置放于DRAM中，使位于DRAM上的非葉子節(jié)點(diǎn)保證訪問的局部性；對(duì)于數(shù)據(jù)結(jié)構(gòu)的葉子節(jié)點(diǎn)，采用單向鏈表數(shù)據(jù)結(jié)構(gòu)，置放于NVM中，使位于NVM上的葉子節(jié)點(diǎn)避免排序和平衡的開銷。該方法使用基于數(shù)組的數(shù)據(jù)組織形式和基于元素的數(shù)據(jù)組織形式、鏈表數(shù)據(jù)結(jié)構(gòu)構(gòu)建索引數(shù)據(jù)結(jié)構(gòu)的葉子節(jié)點(diǎn)、B+樹數(shù)據(jù)結(jié)構(gòu)構(gòu)建索引數(shù)據(jù)結(jié)構(gòu)的內(nèi)部節(jié)點(diǎn)、跳表數(shù)據(jù)結(jié)構(gòu)去除排序和平衡的操作，可以實(shí)現(xiàn)無鎖并發(fā)機(jī)制和有效空間管理，并保證高效的并發(fā)訪問性能和快速的系統(tǒng)恢復(fù)。

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

本發(fā)明涉及非易失性主存存儲(chǔ)技術(shù)領(lǐng)域，特別涉及一種高并發(fā)索引B+鏈表數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)與實(shí)現(xiàn)方法。

背景技術(shù)

非易失性主存(Non-Volatile Memory，NVM)是一種新型的內(nèi)存存儲(chǔ)介質(zhì)，具有可字節(jié)尋址、掉電后信息非易失、存儲(chǔ)密度高、不需要?jiǎng)討B(tài)刷新、靜態(tài)功耗低等優(yōu)點(diǎn)。同時(shí)，也存在一些不足之處，如讀寫性能不對(duì)稱，有限的寫次數(shù)和寫功耗較高等缺點(diǎn)。它的出現(xiàn)對(duì)存儲(chǔ)領(lǐng)域帶來了新的巨大機(jī)遇和挑戰(zhàn)，引發(fā)了產(chǎn)業(yè)界和學(xué)術(shù)界對(duì)異構(gòu)混合內(nèi)存體系架構(gòu)及其相關(guān)系統(tǒng)軟件的研究熱潮。非易失性內(nèi)存對(duì)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)、系統(tǒng)軟件、軟件庫(kù)以及應(yīng)用程序都有很多新的啟示。非易失性內(nèi)存設(shè)備可以與現(xiàn)有的動(dòng)態(tài)隨機(jī)存取存儲(chǔ)器(DynamicRandom Access Memory，DRAM)設(shè)備共同構(gòu)成混合主存，其中應(yīng)用程序中臨時(shí)性的數(shù)據(jù)存儲(chǔ)在DRAM上，而把需要持久保存的數(shù)據(jù)存儲(chǔ)在NVM上。非易失主存的出現(xiàn)促使研究人員著手設(shè)計(jì)基于主存的存儲(chǔ)系統(tǒng)，包括文件系統(tǒng)和數(shù)據(jù)庫(kù)系統(tǒng)。

傳統(tǒng)的索引數(shù)據(jù)結(jié)構(gòu)如B+樹，在NVM新型介質(zhì)上面臨著新的挑戰(zhàn)，如高的寫入延遲，有限的并發(fā)性和空間的低利用率等問題。導(dǎo)致這些問題的原因主要在于傳統(tǒng)的B+樹，對(duì)節(jié)點(diǎn)的組織仍然采取基于數(shù)組的結(jié)構(gòu)，采用這種結(jié)構(gòu)導(dǎo)致的排序和平衡等方面的問題使得寫代價(jià)較高，這種代價(jià)在需要額外維持故障一致性的情況下，將會(huì)變得更大并因此會(huì)導(dǎo)致較大的寫放大開銷。其次，粗粒度的數(shù)組結(jié)構(gòu)會(huì)以整體為粒度進(jìn)行鎖定，高開銷的排序和平衡操作會(huì)進(jìn)一步地增加持有一個(gè)鎖的持續(xù)時(shí)間，該開銷將會(huì)在較大的NVM介質(zhì)寫延遲上體現(xiàn)地更加明顯。

另外，一些針對(duì)NVM進(jìn)行優(yōu)化的數(shù)據(jù)結(jié)構(gòu)，將會(huì)導(dǎo)致版本元素的多版本垃圾和樹節(jié)點(diǎn)利用率過低，會(huì)導(dǎo)致嚴(yán)重的空間利用率的問題。同時(shí)，針對(duì)NVM的內(nèi)存分配器也會(huì)帶來一定的性能下降。

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

本發(fā)明旨在至少在一定程度上解決相關(guān)技術(shù)中的技術(shù)問題之一。

為此，本發(fā)明的目的在于提出一種高并發(fā)索引B+鏈表數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)與實(shí)現(xiàn)方法，該方法可以內(nèi)部地去除排序和平衡的操作，并且實(shí)現(xiàn)無鎖的并發(fā)機(jī)制和有效的空間管理。

為達(dá)到上述目的，本發(fā)明一方面實(shí)施例提出了一種高并發(fā)索引B+鏈表數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)與實(shí)現(xiàn)方法，包括以下步驟：同時(shí)使用基于數(shù)組的和基于元素得到數(shù)據(jù)結(jié)構(gòu)；對(duì)于所述數(shù)據(jù)結(jié)構(gòu)的非葉子節(jié)點(diǎn)，采用預(yù)設(shè)的B+樹數(shù)據(jù)結(jié)構(gòu)，并置放于DRAM中，以使位于所述DRAM上的非葉子節(jié)點(diǎn)保證訪問的局部性；對(duì)于所述數(shù)據(jù)結(jié)構(gòu)的葉子節(jié)點(diǎn)，采用單向鏈表數(shù)據(jù)結(jié)構(gòu)，并置放于NVM中，以使位于所述NVM上的葉子節(jié)點(diǎn)避免排序和平衡的開銷。

本發(fā)明實(shí)施例的高并發(fā)索引B+鏈表數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)與實(shí)現(xiàn)方法，通過使用基于數(shù)組的數(shù)據(jù)組織形式和基于元素的數(shù)據(jù)組織形式，使用鏈表數(shù)據(jù)結(jié)構(gòu)構(gòu)建索引數(shù)據(jù)結(jié)構(gòu)的葉子節(jié)點(diǎn)，使用B+樹數(shù)據(jù)結(jié)構(gòu)構(gòu)建索引數(shù)據(jù)結(jié)構(gòu)的內(nèi)部節(jié)點(diǎn)，使用跳表數(shù)據(jù)結(jié)構(gòu)可以內(nèi)部地去除排序和平衡的操作，并且實(shí)現(xiàn)無鎖的并發(fā)機(jī)制和有效的空間管理，消除排序和平衡操作帶來的持久化開銷以及保證高效的并發(fā)訪問性能，并實(shí)現(xiàn)快速的系統(tǒng)恢復(fù)。

另外，根據(jù)本發(fā)明上述實(shí)施例的高并發(fā)索引B+鏈表數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)與實(shí)現(xiàn)方法還可以具有以下附加的技術(shù)特征：