[發明專利]一種混合內存鍵值對存儲系統的請求處理方法

有效

• 申請號: 201811395627.6
• 申請日: 2018-11-22
• 公開（公告）號: CN109683811B
• 公開（公告）日: 2020-05-19
• 發明（設計）人: 童薇;馮丹;劉景寧;吳海源;秦俊青
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F3/06
• 分類號: G06F3/06
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 曹葆青;李智

1.一種混合內存鍵值對存儲系統的請求處理方法，所述混合內存鍵值對存儲系統包括DRAM和NVM，其特征在于，包括如下步驟：

(1)判斷請求類型，若為讀請求，則轉入步驟(2)；若為寫請求，則轉入步驟(4)；

(2)判斷所述讀請求的類型，若為點查詢請求，則根據所述點查詢請求的鍵查找哈希表，返回查詢結果，并轉入步驟(7)；若為范圍查詢請求，則轉入步驟(3)；

(3)根據所述范圍查詢請求構建對應的跳表命令，將所述跳表命令添加至每一個跳表的命令緩存隊列，并等待直至獲取到所有跳表的返回結果；按照字典序合并獲取到的返回結果，從而得到所述范圍查詢請求的查詢結果并返回；轉入步驟(7)；

(4)為所述寫請求在所述NVM中分配內存并寫入值，從而得到所述寫請求的值地址；

(5)判斷所述寫請求的類型，若為更新請求，則根據所述更新請求更新所述哈希表，并構建對應的跳表命令；若為插入請求，則根據所述插入請求新建跳表節點并更新所述哈希表，并構建對應的跳表命令；

(6)根據所述寫請求中鍵的長度確定目標跳表，并將所述跳表命令添加至所述目標跳表的命令緩存隊列；轉入步驟(7)；

(7)請求處理結束；

在處理請求的同時，還包括：

(S1)對于任意一個跳表S，若其命令緩存隊列Q為空，則等待直至所述命令緩存隊列Q不為空，并轉入(S2)；否則，轉入(S2)；

(S2)從所述命令緩存隊列Q中取跳表命令C并判斷請求類型，若為更新請求，則轉入(S3)；若為插入請求，則轉入(S4)；若為范圍查詢請求，則轉入(S5)；

(S3)根據所述跳表命令C中的跳表節點地址和值地址更新對應的跳表節點；轉入步驟(S1)；

(S4)根據所述跳表命令C中的跳表節點地址將新建的跳表節點插入所述跳表S；轉入步驟(S1)；

(S5)根據所述跳表命令C中的查詢范圍獲得所述跳表S中鍵的字典序位于所述查詢范圍內的所有跳表節點并返回值地址；轉入步驟(S1)；其中，所述哈希表建立于所述DRAM中，所述哈希表中的索引項存儲有鍵、值地址以及對應的跳表節點地址；所述跳表建立于所述NVM中，所述跳表有多個，每一個跳表分別與一個鍵的長度范圍相對應，并且每一個跳表分別設置有一個命令緩存隊列，所述跳表中的跳表節點存儲有鍵和值地址；所述跳表命令封裝有請求類型，所述查詢范圍為鍵的字典序范圍。

2.如權利要求1所述的混合內存鍵值對存儲系統的請求處理方法，其特征在于，還包括，若同一范圍查詢請求所對應的跳表命令均執行完成，則按照字典序合并各跳表命令返回的數據，從而得到所述范圍查詢請求的查詢結果。

3.如權利要求1所述的混合內存鍵值對存儲系統的請求處理方法，其特征在于，所述步驟(3)中，根據所述范圍查詢請求構建對應的跳表命令，包括：

獲得所述范圍查詢請求的查詢范圍R；構建跳表命令C_s，并設置跳表命令C_s的請求類型為范圍查詢請求，設置所述跳表命令C_s的查詢范圍為所述查詢范圍R；

其中，所述查詢范圍為鍵的字典序范圍。

4.如權利要求1所述的混合內存鍵值對存儲系統的請求處理方法，其特征在于，所述步驟(5)中，判斷所述寫請求的類型的方法為：

根據所述寫請求的鍵查找所述哈希表，若查找成功，則判定所述寫請求為更新請求；否則，判定所述寫請求為插入請求。

5.如權利要求1所述的混合內存鍵值對存儲系統的請求處理方法，其特征在于，所述步驟(5)中，根據所述更新請求更新所述哈希表，并構建對應的跳表命令，包括：

根據所述更新請求的鍵查找到對應的索引項I_u；

將所述索引項I_u中值地址更新為所述寫請求的值地址；

構建跳表命令C_u，設置所述跳表命令C_u的請求類型為更新請求，并將所述跳表命令C_u的跳表節點地址和值地址對應地設置為所述索引項I_u中存儲的跳表節點地址和值地址。