[發明專利]DRAM-NVM混合索引結構的構建方法及操作方法

在審

• 申請號: 202110789870.1
• 申請日: 2021-07-13
• 公開（公告）號: CN113590612A
• 公開（公告）日: 2021-11-02
• 發明（設計）人: 萬繼光;謝長生;盛濤濤;周元輝;陶偉
• 申請（專利權）人: 華中科技大學;深圳華中科技大學研究院
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/242;G06F11/14
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 祝丹晴

本發明公開了一種DRAM?NVM混合索引結構的構建方法及操作方法，所構建的索引結構包括索引層、中間層和數據層；索引層存儲在DRAM中；中間層包括元數據節點，存儲在DRAM中，且在NVM中存在備份；數據層包括LogTree，LogTree為樹形結構，其個數與元數據節點的個數相同，與元數據節點一一對應；初始狀態下，LogTree存儲于NVM中，記為NvmTree；在讀寫過程中，將訪問熱度大于預設訪問熱度閾值的LogTree進行備份并緩存在DRAM中來創建CacheTree；此時，LogTree包括初始存儲于NVM中的NvmTree、緩存在DRAM中的CacheTree和存儲于NVM中的日志；日志用于存儲對CacheTree進行寫操作的記錄；數據層中的LogTree用于存儲用戶寫入的鍵值對中的目標關鍵字key和指向value的指針；本發明能夠在保證讀寫性能的前提下，能夠大大加快故障恢復的過程。

技術領域

本發明屬于信息存儲技術領域，更具體地，涉及一種DRAM-NVM混合索引結構的構建方法及操作方法。

背景技術

近十多年以來，隨著計算機與網絡技術的持續發展，信息數據規模呈爆炸式增長。當前計算機系統中各種存儲設備在性能、容量、持久性等方面差異較大，給數據的存儲方式帶來了巨大的影響。索引結構是現代數據庫的核心構件，存儲架構的改變和持久性內存的特性為優化索引結構帶來了機遇和挑戰，故研究一種索引結構具有重要意義。

新型非易失性內存(Non-Volatile Memory，NVM)因為其具有的可字節尋址、非易失、低功耗、較高存儲密度等優勢，以及接近DRAM的性能，已經成為構建下一代存儲系統的重要存儲器件。現有的索引結構有很多基于NVM或者NVM與DRAM的混合介質，如NovelLSM、Path Hash、NVTree、FPTree等。但現有的基于NVM或NVM與DRAM混合介質的索引結構，并不能兼顧高讀寫性能與快速的故障恢復。以FPTree為例，這是一種基于DRAM-NVM混合介質的B+樹索引結構。它將葉子節點持久化在NVM中，而將中間節點置于DRAM上，在恢復時利用持久化的葉子節點重建DRAM中的中間節點。FPTree葉子節點內部數據無序排列，并對葉子節點內部的每個關鍵字都計算出一個1B的哈希值，作為指紋數據，存放在同一個cache line中。在查詢時，通過掃描指紋數據來快速定位到關鍵字的位置。這種結構雖然能夠降低cache的不命中率、提升查詢性能，但是B+樹中間節點在系統掉電或故障后會丟失，在系統恢復時需要重建中間節點，在數據量較大時恢復時間較長，影響了系統的可用性。

發明內容

針對現有技術的以上缺陷或改進需求，本發明提供一種DRAM-NVM混合索引結構的構建方法及操作方法，用以解決現有技術無法兼顧高讀寫性能與快速的故障恢復的技術問題。

第一方面，本發明提供了一種DRAM-NVM混合索引結構的構建方法，包括：構建索引層、中間層和數據層，得到DRAM-NVM混合索引結構；

索引層為樹形結構，存儲在DRAM中；中間層包括1個或多個元數據節點，存儲在DRAM中，且在NVM中存在備份；且當元數據節點為多個時，各元數據節點前后連接形成鏈表結構；數據層包括日志持久化樹LogTree；LogTree為樹形結構，其個數與元數據節點的個數相同，與元數據節點一一對應；初始狀態下，LogTree存儲于NVM中，記為NvmTree；在讀寫過程中，若LogTree的訪問熱度大于預設訪問熱度閾值，則通過對LogTree進行備份并緩存在DRAM中來創建CacheTree；此時，LogTree包括初始存儲于NVM中的NvmTree、緩存在DRAM中的CacheTree和存儲于NVM中的日志；其中，日志用于存儲對CacheTree進行寫操作的記錄；

索引層用于索引中間層的元數據節點；

中間層用于對數據層中的LogTree進行尋址，并記錄數據層中各LogTree的訪問熱度；中間層中的元數據節點包括指向其所對應的LogTree中的CacheTree根節點指針、NvmTree的根節點指針和日志的指針，以及其所對應的LogTree的訪問熱度；