[發明專利]一種內存與前綴樹相結合的高效分布式元數據管理方法

在審

• 申請號: 202310349675.6
• 申請日: 2023-04-04
• 公開（公告）號: CN116501760A
• 公開（公告）日: 2023-07-28
• 發明（設計）人: 俞萬剛;薛梅婷;曾艷;袁俊峰;張紀林;萬健
• 申請（專利權）人: 杭州電子科技大學
• 主分類號: G06F16/2453
• 分類號: G06F16/2453;G06F16/2455;G06F16/27;G06F9/50
• 代理公司: 杭州奧創知識產權代理有限公司 33272
• 代理人: 王佳健

本發明公開了一種內存與前綴樹相結合的高效分布式元數據管理方法。該方法涉及元數據在分布式系統中的管理方式，包含使用改進的一致性Hash算法對元數據進行映射，并利用前綴樹的方式對元數據進行存儲以減少內存空間。本發明通過基于內存的形式，并且查找和添加都使用了二分查找，在查找和添加的性能方面大大提升。通過MDS節點的平衡因子，來解決元數據分布的均勻性，使得元數據能盡可能的均勻分布在各個MDS節點，提升了元數據管理的性能。另外本發明以高效的前綴樹去存儲實際的元數據索引，通過索引去直接從磁盤中獲取該元數據，利用了小量的空間換取了效率。

技術領域

本發明涉及元數據在分布式系統中的管理方法，包含使用改進的一致性Hash算法對元數據進行映射，并利用前綴樹的方式對元數據進行存儲以減少內存空間。

背景技術

元數據是用來描述數據的一種特殊數據，如在文件系統中，元數據是描述文件屬性的數據，其包括文件目錄內容，文件大小以及文件指針，元數據包含了從文件名到記錄數據的位置情況。

隨著互聯網的發展和多方面的數字化轉型，大量的應用都產生了海量的數據，如圖片數據和系統日志數據，這些海量數據需要大量的存儲資源來存儲和管理數據。為了更好的對這些數據進行管理，將這些圖片資源和日志數據進行壓縮存儲在文件系統中，并由操作系統去組織這些文件，最后將資源元數據存儲到一些結構化的數據庫當中，由數據庫充當文件到資源的映射工具。因此，海量元數據的管理成為了以文件系統為存儲介質的系統的一大難點。

分布式元數據管理常用的方法有：靜態子樹分區方法，適用于元數據查找較為頻繁的場景，當元數據動態增加時會使得分布式元數據服務器(Metadata?Server)之間的負載不均衡。動態子樹分區方法，子樹動態調正策略使得MDS之間通信會大大增加，系統性能會有一定的影響。Hash映射方法：數據特征相似時，存在數據“傾斜”現象，導致MDS之間負載不均勻問題。

為了應對單體數據庫面對海量數據的訪問壓力，采用多數據庫的集群方式，減輕單體數據庫的訪問，但是這樣的做法雖然減少了每個數據庫訪問的壓力，但是也導致了數據的冗余，在根本上沒有解決海量數據對于數據庫性能的影響。因此為了從根本解決海量數據給數據庫造成的影響，就需要減少單個數據庫的數據量才能改善性能，所以采用了數據分片存儲，海量的數據分片存儲在數據庫集群當中，減少單體數據庫的數據量，數據分片針對的是不同的元數據之間采用分片存儲而不是元數據之間分片，這樣的做法從而緩解了數據庫的壓力，進而提升元數據查詢效率，但是也導致了系統的復雜性大大提升，需要解決分片數據所帶來的分布式事務的問題，數據采用何種分片策略和數據分片后的復雜定位等問題。

發明內容

本發明根據現有技術的不足，針對應用生成的海量元數據，提出了一種基于內存與前綴樹相結合的高效分布式元數據管理方法，為海量的元數據提供高效的存儲和查詢方案。

本發明包括以下兩個階段：

第一個階段：通過改進的一致性Hash來定位元數據所在的分布式元數據服務器MDS；所述的改進的一致性Hash包含：MDS對象集合、Hash環和每個MDS所指向的元數據標識桶集合Key?Bucket。

第二個階段：從定位到的分布式元數據服務器MDS中獲取相對應的元數據，通過前綴樹來共享所有元數據Key相同的部分，將元數據所在的地址存儲到相對應的前綴樹的節點上。

與現有的技術相比，本發明的優勢在于:

1.通過基于內存的形式，其操作的效率會遠高于傳統的IO方式，并且查找和添加都使用了二分查找，在查找和添加的性能方面大大提升。

2.通過MDS節點的平衡因子，來解決元數據分布的均勻性，使得元數據能盡可能的均勻分布在各個MDS節點，不會過多的導致某個MDS節點的負載過高產生傾斜問題，提升了元數據管理的性能。