[發明專利]一種無垃圾回收的鍵值分離存儲方法和系統

有效

• 申請號: 201910540348.2
• 申請日: 2019-06-21
• 公開（公告）號: CN110389942B
• 公開（公告）日: 2021-07-30
• 發明（設計）人: 周可;王樺;劉莉;林立亞
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F16/21
• 分類號: G06F16/21;G06F16/215;G06F16/22
• 代理公司: 武漢臻誠專利代理事務所(普通合伙) 42233
• 代理人: 宋業斌

本發明公開了一種無垃圾回收的鍵值分離存儲方法，屬于計算機存儲技術領域，解決現有鍵值分離鍵值存儲系統在更新密集型工作負載下無法實現高性能的問題。本發明主要針對更新密集型工作負載，通過對失效數據的有效管理，實現就地更新，從而消除存儲過程中的垃圾回收操作，避免鍵值存儲系統中有效數據的頻繁重寫，減少鍵值存儲系統的寫放大。對于更新密集型工作負載，本發明首先采用鍵值分離的方法將數據存儲在值存儲管理區，并將數據中的鍵存儲在LSM樹中進行管理，接下來通過收集、管理和復用失效數據索引對失效數據實現就地更新、覆蓋回收，去除垃圾回收過程，避免由于垃圾回收而產生的開銷，提升鍵值存儲系統的性能。

技術領域

本發明屬于計算機存儲技術領域，更具體地，涉及一種無垃圾回收的鍵值分離存儲方法和系統。

背景技術

基于日志結構合并樹(Log-Structured Merge Tree，簡稱LSM樹)的鍵值存儲系統是面向寫密集型應用的存儲方案，其能提供較好的寫性能。然而，LSM樹在讀寫操作中會產生較高的寫放大，當有更多的鍵值數據寫入LSM樹時，LSM樹將進行頻繁的數據合并操作，這樣也會導致產生大量的額外I/O操作；此外，當這樣的寫放大達到50倍或以上時，對于鍵值存儲系統的寫性能和固態盤(Solid state disk，簡稱SSD)的耐久性都是不利的。

為了減少上述LSM樹的數據合并操作所帶來的開銷，研究者們提出了鍵值分離思想，其具體是將值存儲在僅支持追加寫的循環日志中，而使用LSM樹管理鍵和元數據(即循環日志中鍵值對所在的地址)。鍵值分離的主要目的是減小LSM樹中數據規模的大小，同時保留LSM樹的索引特性，以便實現高效的插入、更新和查詢。

然而，上述基于鍵值分離的鍵值存儲系統依然存在不可忽略的缺陷：當其被應用于更新密集型工作負載時，會產生較高的寫放大和性能損失，其根本原因在于，當用于值存儲的循環日志的大小超過閾值時，需要進行頻繁的垃圾回收操作，以釋放被更新或被刪除的失效數據所占用的空間，而垃圾回收操作會導致大量的系統開銷，并在更新密集型工作負載下產生接近于傳統基于LSM樹的鍵值存儲方案鍵值存儲系統的寫放大倍數。

發明內容

針對現有技術的以上缺陷或改進需求，本發明提供了一種無垃圾回收的鍵值分離存儲方法和系統，其目的在于，解決現有基于鍵值分離的鍵值存儲系統在應用于更新密集型工作負載時，會產生較高的寫放大和性能損失的技術問題。

為實現上述目的，按照本發明的一個方面，提供了一種無垃圾回收的鍵值分離存儲方法，包括以下步驟：

(1)獲取鍵值對數據，并判斷預先建立的失效數據隊列中是否存在失效數據，如果是則進入步驟(6)，否則進入步驟(2)；

(2)將該鍵值對數據存儲在磁盤的日志文件中；

(3)獲取該鍵值對數據在日志文件中的偏移地址，將該偏移地址和該鍵值對數據中的鍵一起存儲在LSM樹中；

(4)判斷LSM樹中的相鄰層之間是否發生了文件合并操作，如果是則進入步驟(5)，否則返回步驟(1)；

(5)獲取文件合并操作過程中產生的失效數據，并將該失效數據存儲在預先建立的失效數據隊列中，其中該失效數據包括該失效數據的偏移地址、及其對應的鍵，過程結束；

(6)從失效數據隊列中取出位于最頭部的失效數據，將待寫入鍵值對數據寫入磁盤中該失效數據的偏移地址處，并將該偏移地址和該待寫入鍵值對數據中的鍵一起存儲在LSM樹中，過程結束。

優選地，預先建立的失效數據隊列用于存儲LSM樹的文件合并操作過程中產生的失效數據。

優選地，日志文件是值日志。

按照本發明的另一方面，提供了一種無垃圾回收的鍵值分離存儲系統，包括：