[發明專利]一種基于NVM的LSM樹的存儲結構及其數據存儲方法

在審

• 申請號: 202111179858.5
• 申請日: 2021-10-11
• 公開（公告）號: CN113821177A
• 公開（公告）日: 2021-12-21
• 發明（設計）人: 莊鑄滔;陳志廣
• 申請（專利權）人: 中山大學
• 主分類號: G06F3/06
• 分類號: G06F3/06
• 代理公司: 深圳市創富知識產權代理有限公司 44367
• 代理人: 高冰

1.一種基于NVM的LSM樹的存儲結構，其特征在于，包括：

DRAM層，用于將數據插入到數據結構WriteBatch并構建寫入對象隊列，根據寫入對象隊列將數據結構WriteBatch的數據寫入MemTable；

DISK層，用于將MemTable轉換為SSTable并基于NVM對SSTable進行合并，完成寫操作。

2.一種基于NVM的LSM樹存儲結構的數據存儲方法，其特征在于，包括寫操作：

將數據插入到數據結構WriteBatch并構建寫入對象隊列；

根據寫入對象隊列將數據結構WriteBatch的數據寫入MemTable；

將MemTable轉換為SSTable；

基于NVM對SSTable進行合并，完成寫操作。

3.根據權利要求2所述一種基于NVM的LSM樹存儲結構的數據存儲方法，其特征在于，所述將數據結構WriteBatch的數據寫入MemTable具體還包括：

判斷當前MemTable是否填滿；

判斷到MemTable填滿，將MemTable轉為Immutable MemTable并新創建一個MenTable。

4.根據權利要求3所述一種基于NVM的LSM樹存儲結構的數據存儲方法，其特征在于，所述將MemTable轉換為SSTable這一步驟，其具體包括：

將MemTable轉換為SSTable；

遍歷一遍Immutable MemTable，得到Immutable MemTable的數據項數量；

新建一個數據項數量與Immutable MemTable相同的SSTable，將Immutable MemTable的數據項在SSTable的最尾部插入。

5.根據權利要求4所述一種基于NVM的LSM樹存儲結構的數據存儲方法，其特征在于，所述基于NVM對SSTable進行合并，完成寫操作這一步驟，其具體包括：

創建Compaction對象和SSTable數組，所述Compaction對象包括SSTable合并的記錄信息，所述SSTable數組設有可容納鍵值對的數目閾值；

對將要合并的SSTable構建一個迭代器，所述迭代器將將要合并的SSTable的鍵值對從按鍵的大小從小到大依次返回；

遍歷該迭代器，對于每個返回的鍵值對，根據預設規則判斷該鍵值對是否可丟棄；

判斷到返回的鍵值對不可丟棄，將該鍵值對加入到新創建的SSTable；

當一個SSTable填滿時，新創建一個SSTable，將新創建的SSTable壓入SSTable數組的末端；

判斷到所有不可丟棄的鍵值對已插入到SSTable數組中，執行安裝替換，完成寫操作。

6.根據權利要求5所述一種基于NVM的LSM樹存儲結構的數據存儲方法，其特征在于，還包括讀操作：

在Mutable MemTable中查找待索引的鍵；

在Mutable MemTable中未查找到待索引的鍵，在Immutable MemTable中查找待索引的鍵；

在Immutable MemTable中未查找到待索引的鍵，在SSTable中查找待索引的鍵。

7.根據權利要求6所述一種基于NVM的LSM樹存儲結構的數據存儲方法，其特征在于，所述在Mutable MemTable中查找待索引的鍵這一步驟，其具體包括：

創建一個SkipList的迭代器并通過調用該迭代器的查詢功能來查找待索引的鍵；

返回查找結果。

8.根據權利要求7所述一種基于NVM的LSM樹存儲結構的數據存儲方法，其特征在于，所述在Immutable MemTable中未查找到待索引的鍵，在SSTable中查找待索引的鍵這一步驟，其具體包括：

在Mutable MemTable和Immutable MemTable中均沒有查找到待索引的鍵；

從L0層開始往上層查找，直至最高層；

查找到待索引的鍵，輸出待索引的鍵并結束；

沒有查找到待索引的鍵，則輸出沒有找到結果。