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

有效

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

本發明公開了一種混合內存鍵值對存儲系統的請求處理方法，包括：若為點查詢請求，則查找哈希表并返回查詢結果；若為范圍查詢請求，則構建對應的跳表命令并添加至每一個跳表的命令緩存隊列，等待直至獲取到所有跳表的返回結果，并按照字典序合并獲取到的返回結果并返回；若為寫請求，則在NVM中分配內存并寫入值；進一步判斷寫請求類型，若為更新請求，則更新哈希表，并構建對應的跳表命令；若為插入請求，則新建跳表節點并更新哈希表，并構建對應的跳表命令；根據寫請求中鍵的長度確定目標跳表，并將跳表命令添加至目標跳表的命令緩存隊列。本發明充分考慮介質的讀寫延遲，并且最優化占比較高的讀操作的處理性能，從而有效提升系統的整體性能。

技術領域

本發明屬于信息存儲技術領域，更具體地，涉及一種混合內存鍵值對存儲系統的請求處理方法。

背景技術

互聯網大數據應用和云計算應用要求對大規模數據的快速訪問，鍵值對存儲(KVS，Key Value Store)作為非關系型數據存儲的典型代表，采用非結構化的數據組織形式，提供高效的數據插入、點查詢(point query)、范圍查詢(scan)支持，憑借其高訪問性能、高可用性和高擴展性得以迅速發展，廣泛應用在數據密集型應用中，如網絡索引引擎、社交網絡等。內存鍵值對存儲以動態隨機訪問存儲器(DRAM，Dynamic Random AccessMemory)作為存儲介質，但是DRAM受可擴展性、能耗、成本等因素的影響越來越無法滿足大數據應用的容量需求。非易失存儲器(NVM，Non-Volatile Memory)具有高存儲密度、字節可尋址、低能耗、近DRAM訪問延遲、掉電后數據不丟失等特點，為內存鍵值對存儲提供了一種可行的解決方案。以NVM和DRAM作為混合內存的架構得到了廣泛的關注和研究，如何結合NVM和DRAM介質的特點，設計高性能的混合內存鍵值對存儲系統具有十分重要的意義。

索引設計是實現高性能內存鍵值對存儲系統的關鍵部分。現有內存鍵值對存儲系統采用哈希表、B+樹、跳表等數據結構作為索引，哈希表的點插入和查詢的速度最快，時間復雜度為O(1)，但是無法支持范圍查詢，B+樹和跳表的點查詢和點插入的時間復雜度為O(nlogn)，支持范圍查詢。

目前，NVM介質的讀、寫延遲分別約為DRAM讀、寫延遲的3～4倍和10～12倍，基于介質的讀寫延遲，現有的對混合內存鍵值對存儲系統性能優化的研究焦點在于針對寫操作的性能優化，相應地，索引設計也主要針對NVM和DRAM的寫延遲差距，如將插入和查詢復雜度為O(1)的哈希結構放在寫延遲較高NVM中，將時間復雜度較高的B+樹實現在寫延遲較低的DRAM中，以達到系統整體性能的穩定。

而在讀密集型的內存鍵值對存儲環境下，鍵值對存儲系統的讀操作性能起到更加關鍵的作用。研究表明，混合內存鍵值對存儲系統的讀數據比例遠高于寫數據，甚至高達30:1，這使得NVM的讀操作延遲成為整個系統性能遠不可忽略的一部分，由于缺乏對NVM讀延遲的考慮和系統讀性能的優化，現有索引設計對NVM過多的讀操作會導致系統整體性能的下降。

發明內容

針對現有技術的缺陷和改進需求，本發明提供了一種混合內存鍵值對存儲系統的請求處理方法，其目的在于，同時針對介質的讀寫延遲和讀請求所占的高比例對混合內存鍵值對存儲系統的整體性能進行優化。

為實現上述目的，本發明提供了一種混合內存鍵值對存儲系統的請求處理方法，混合內存鍵值對存儲系統包括DRAM和NVM，包括如下步驟：

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

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

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