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

在審

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

1.一種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的訪問熱度；

所述數據層中的LogTree用于存儲用戶寫入的鍵值對中的目標關鍵字key和指向value的指針。

2.根據權利要求1所述的索引結構的構建方法，其特征在于，所述預設訪問熱度閾值的設置方法包括：

預設用于緩存CacheTree的DRAM的最大容量為M，預設CacheTree的最大存儲容量為S，獲取所述數據層中各LogTree的訪問熱度最高的前M/S個訪問熱度，將前M/S個訪問熱度中的最小訪問熱度作為所述預設訪問熱度閾值。

3.根據權利要求1或2所述的索引結構的構建方法，其特征在于，所述索引層為B+樹；所述LogTree為B+樹；當元數據節點為多個時，各元數據節點前后連接形成雙向鏈表結構。

4.采用權利要求1-3任意一項所述的DRAM-NVM混合索引結構的構建方法所構建的索引結構的讀寫請求處理方法，其特征在于，包括：

當接收到寫請求時，執行寫操作：

S11、基于請求中的目標關鍵字key查詢索引層，得到所述目標關鍵字key所對應的元數據節點指針，確定中間層的元數據節點，并累積所述元數據節點所對應的LogTree的訪問熱度；在NVM中為請求中的value分配持久化空間，并進行持久化，得到指向value的指針；

S12、判斷所述元數據節點所對應的LogTree中的CacheTree是否處于CacheTree的創建或同步操作下，若是，則轉至步驟S13；否則，轉至步驟S14；

S13、將所述目標關鍵字key和所述指向value的指針寫入到所述元數據節點所對應的LogTree中日志里，操作結束；

S14、將所述目標關鍵字key和所述指向value的指針插入到所述元數據節點所對應的LogTree中：判斷所述元數據節點所對應的LogTree中是否存在CacheTree，若存在，則將所述目標關鍵字key和所述指向value的指針插入到CacheTree中，并將所述目標關鍵字key和所述指向value的指針寫入到所述元數據節點所對應的LogTree中日志里；否則，將所述目標關鍵字key和所述指向value的指針插入到NvmTree中；

當接收到讀請求時，執行讀操作：

S21、基于請求中的目標關鍵字key查詢索引層，得到所述目標關鍵字key所對應的元數據節點指針，確定中間層的元數據節點，并累積所述元數據節點所對應的LogTree的訪問熱度；

S22、判斷所述元數據節點所對應的LogTree中的CacheTree是否處于CacheTree的創建或同步操作下，若是，則轉至步驟S23；否則，轉至步驟S24；

S23、在所述元數據節點所對應的LogTree中的日志中查詢所述目標關鍵字key對應的操作記錄，若能夠查詢到，則通過所述操作記錄中的指向value的指針獲取value值，操作結束；否則，轉至步驟S24；

S24、判斷所述元數據節點所對應的LogTree中是否存在CacheTree，若存在，則基于所述目標關鍵字key在CacheTree中進行查詢，得到指向value的指針，并通過所述指向value的指針獲取value值；否則，基于所述目標關鍵字key在NvmTree中進行查詢，得到指向value的指針，并通過所述指向value的指針獲取value值；

其中，CacheTree的同步操作包括：當日志大小大于預設日志大小時，更新CacheTree所在的LogTree中的NvmTree，使其與CacheTree相同。