[發明專利]基于Cuckoo哈希計算的數據存儲優化方法及系統

有效

• 申請號: 201710415853.5
• 申請日: 2017-06-06
• 公開（公告）號: CN107256130B
• 公開（公告）日: 2019-09-24
• 發明（設計）人: 華宇;孫園園;馮丹
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F3/06
• 分類號: G06F3/06
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 廖盈春;李智

本發明公開了一種基于Cuckoo哈希計算的數據存儲優化方法及系統，首先將索引表中每個桶看作一個子圖節點，將表中存儲的每個元素看作一條邊，并從其實際存儲位置指向元素的候選位置，因此整個索引表成為包含多個連通子圖的有向圖；然后在元素實際插入前通過哈希計算識別其所屬的一個或兩個子圖；再根據子圖狀態預測插入結果；最后根據預測結果執行插入操作或者直接存入臨時空間。本發明利用Cuckoo哈希機制將海量數據扁平化哈希到整個索引表中，合理解決集合內數據的哈希沖突，在保證查詢效率的情況下使負載均衡，有效提高索引表利用率，并提前預測數據插入結果；通過對數據存儲前預測結果來避免無效的踢出開銷，提高了數據存儲效率。

技術領域

本發明屬于計算機存儲技術領域，更具體地，涉及一種基于Cuckoo哈希計算的數據存儲優化方法及系統。

背景技術

隨著近年來互聯網、云計算、物聯網、社交媒體以及其他信息技術的迅速發展，各行各業積累的數據都呈現出爆炸式增長趨勢。例如，Facebook每天處理的數據超過500TB，阿里巴巴擁有的數據量超過100PB，新浪微博用戶數超過5億，每天產生的微博數超過1億條等，許多商業公司通常每天要處理TB級甚至PB級的數據。根據國際數據公司(International DataCorporation,IDC)2014年的報告，全球產生的數據總量每兩年翻一番，在2020年將達到44ZB。

大數據時代的到來給海量數據的管理帶來了新的挑戰和契機。其中，大數據(尤其是非結構化數據)的快速檢索作為一個非常關鍵的問題亟待解決。在云計算系統中，大量資源被用于支持查詢相關的操作，例如計算資源、存儲資源以及網絡資源，然而對于查詢請求如何快速返回精確結果仍然是一個巨大的挑戰。為了提高系統性能和整體效率，目前也有許多改進工作，例如對加密云數據的多關鍵字查詢，對并行數據處理的查詢優化，利用分層Bloom filter索引加速查詢，利用持續監控過程優化查詢，對云數據的近似成員查詢，文件系統中的近似查詢，對云數據的分類查詢檢索，查詢服務的自動管理等等。但是由于這些方法具有空間效率不高以及高復雜度的分層尋址的缺點，它們都無法滿足實時查詢的需求。

基于哈希的數據結構具有常數級尋址復雜度和快速查詢響應的特性，它在查詢的實時性和準確性方面優勢顯著，成為為解決大數據管理的關鍵技術之一。

Cuckoo哈希是多選擇哈希機制的一個有效變體。在cuckoo哈希機制中，每一個元素能夠被放置在哈希表中多個備選哈希桶的任一位置。當多個備選位置都被其他元素占據(不為空)時，該元素任意踢出某一個桶中存在的元素，而不是直接返回插入失敗或者通過鏈表存儲。被踢出的元素接著執行相同操作，直到所有的元素都找到存儲的位置。相比于傳統哈希表中只使用一個哈希函數的情況，cuckoo哈希這種機制能夠確保數據的均勻分布。由于這種常數級復雜度的扁平化尋址的特性，在查詢操作中只需要探測哈希表一次就可以得到查詢結果。在最壞情況下，每次至多探測被查詢元素的所有候選位置，因此確保了常數級的查詢時間復雜度。

然而在索引表構建過程中，傳統的cuckoo哈希方法中在元素的候選位置中隨機選擇一個位置進行插入與移動。當元素所有候選位置都被占據時，這種隨機選擇更加劇了哈希尋址的不確定性。在踢出操作中，這種隨機選擇方案可能會造成踢出路徑的重復甚至無限循環，產生大量無效的踢出操作，這將導致元素插入操作中的高時延。

發明內容

針對現有技術的以上缺陷或改進需求，本發明的目的在于提供了一種基于Cuckoo哈希計算的數據存儲優化方法及系統，由此解決現有的云存儲系統中構建基于Cuckoo哈希索引表時元素插入所導致的踢出路徑無限循環的技術問題。

為實現上述目的，按照本發明的一個方面，提供了一種基于Cuckoo哈希計算的數據存儲優化方法，包括以下步驟：

S1、根據元素屬性隨機選擇兩個相互獨立的哈希函數計算得到元素在索引表中對應的兩個候選哈希桶；