[發(fā)明專利]一種基于數據值分類的差異化鍵值數據存儲方法

有效

• 申請?zhí)枺?/td>: 202010182605.2
• 申請日: 2020-03-16
• 公開（公告）號: CN111399777B
• 公開（公告）日: 2023-05-16
• 發(fā)明（設計）人: 吳加禹;崔秋;唐劉;吳毅
• 申請（專利權）人: 平凱星辰（北京）科技有限公司
• 主分類號: G06F3/06
• 分類號: G06F3/06;G06F12/02;G06F16/906;G06F16/901
• 代理公司: 北京市立方律師事務所 11330
• 代理人: 張筱寧

本發(fā)明公開了一種基于數據值分類的差異化鍵值數據存儲方法，特征是包括鍵值數據的分類存儲、有序文件的分層管理、優(yōu)化底層數據值的局部有序性、差異化的磁盤空間回收策略步驟，通過對不同大小的數據值進行分類并采用鍵值分離結構以不同的有序性存儲，使得該系統在充分降低數據合并帶來的開銷的同時，支持對數據進行高效的點查詢以及范圍查詢；通過有序文件的分層管理以及局部有序性優(yōu)化，實現了以盡可能小的開銷保障系統中絕大多數有序文件在范圍查詢時可以順序讀取；利用差異化的磁盤空間回收策略能快速識別并回收系統中無效數據最密集的文件，并規(guī)避了中小數據值在空間回收過程中對數據索引的頻繁讀寫，從而可以高效回收和利用存儲空間。因此，采用本發(fā)明方法所設計的鍵值存儲系統可以在讀、寫及空間開銷等性能指標上均表現優(yōu)異。

技術領域

本發(fā)明屬于計算機存儲系統技術領域，具體涉及在鍵值存儲系統(KV?Stores)中，將鍵值(Key-Value)數據進行分類并采用差異化的存儲方法，實現高性能、低空間開銷的鍵值存取方法。

背景技術

據谷歌(Google)、臉書(Facebook)等公司的介紹，為了適應新型網絡應用和服務中海量非結構化與半結構化數據的存儲需求，基于鍵值(Key-Value)模型的存儲系統近年來被廣泛使用，包括谷歌的LevelDB、臉書的RocksDB、淘寶的Tair等均采用了鍵值存儲模型。這些主流的鍵值存儲系統都采用日志結構合并樹(LSM-Tree)作為其核心存儲結構，這種結構將鍵值數據在磁盤上組織成多層，通過層間壓縮(Compaction)操作來保證數據在各層內的絕對有序。但是頻繁的Compaction操作會導致嚴重的寫放大(WriteAmplification)問題，為了解決該問題，目前存在兩種主流技術研究方向：一是放松LSM-Tree中存儲鍵值對(KV?Pair)的層內有序性要求，每次Compaction操作僅合并同一層中的數據追加到下一層，允許層內數據范圍重疊，如德克薩斯大學奧斯汀分校的PebblesDB；二是采用鍵值分離的存儲結構，僅維護有序的鍵(Key)作為索引，將數據值(Value)按寫入順序存儲在分離的日志文件中，如威斯康星大學的WiscKey。這些研究采取的方法雖然降低了系統的寫入開銷，但均在不同程度上影響了讀性能，包括點查詢及范圍查詢，并且顯著增加了磁盤空間開銷。隨著網絡中數據規(guī)模的急劇增長，為了適應新型網絡應用的性能需要以及降低存儲成本，需要鍵值存儲系統同時具備高讀寫性能，以及較低的空間開銷。

發(fā)明內容

本發(fā)明的目的是為鍵值存儲系統提供一種基于數據值分類的差異化鍵值數據存儲方法，以盡可能低的維護開銷保障數據的讀取性能，并實現高效的空間回收，克服現有技術不能同時保障高讀寫性能以及低空間開銷的缺陷。

本發(fā)明基于數據值分類的差異化鍵值數據存儲方法，其特征在于包括以下步驟：

第一步：鍵值數據的分類存儲

采用數據值(Value)的分類方法，將鍵值數據按數據值大小分成大、中、小三類，并以鍵值分離的存儲結構將數據值分別存儲在磁盤上的無序數據區(qū)、有序數據區(qū)以及索引區(qū)三個不同區(qū)域：

所述無序數據區(qū)，由一系列無序文件組成,存儲大數據值，數據值在文件內按寫入順序存儲；

所述有序數據區(qū)，由一系列有序文件組成，存儲中數據值，數據值在文件內部按照鍵(Key)的字典序排列，不同有序文件之間可以存在范圍重疊；

所述索引區(qū)，結構為日志結構合并樹(LSM-Tree)，保存小鍵值對本身，以及大、中數據值在數據區(qū)中的位置；

所述數據值的分類方法為：以近似數據值的位置索引大小作為小鍵值對的最大數據值大小SmallThreshold，并根據存儲介質的并發(fā)隨機讀取性能設置大鍵值對的最小數據值大小LargeThreshold，滿足當數據值大于LargeThreshold時并發(fā)隨機讀取性能接近順序讀取；數據值文件的大小限制為MaxFileSize，其值應小于LSM-Tree中數據文件的大小；鍵值對在寫入時遵循以下流程：