[發明專利]布隆過濾器生成方法和裝置

有效

• 申請號: 201310382258.8
• 申請日: 2013-08-28
• 公開（公告）號: CN104424256B
• 公開（公告）日: 2017-12-12
• 發明（設計）人: 李勇;朱俊華
• 申請（專利權）人: 華為技術有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 深圳市深佳知識產權代理事務所(普通合伙)44285
• 代理人: 唐華明

技術領域

本申請涉及數據處理技術領域，更具體的說是涉及一種布隆過濾器生成方法和裝置。

背景技術

信息技術的迅猛發展，使得數據量爆炸性增長，能夠保證數據存儲的安全性、高可靠性以及高擴展性等的數據存儲系統成為未來主要的研究重點。

在數據存儲系統中，為了保證高性能的寫操作，包括插入、更新和刪除，現有技術中采用的一種實現方式是append-only，append-only方式是指數據的更新和刪除不會修改已有的數據，而是類似于插入操作，更新數據和刪除數據也會寫入存儲介質中，最后再通過數據合并的方式得到最終的數據。

數據插入、更新和刪除時，通常以文件形式進行，每一文件可能包括多條記錄，通過數據主鍵能夠唯一標識一條記錄。因此，按照上述方式進行數據寫操作時，會生成很多的記錄，包括插入記錄、更新記錄、刪除記錄等，在進行數據查詢時，還未進行合并的記錄也會被加載查詢。

為了便于數據查詢，現有技術中，通常利用Bloom filter(布隆過濾器)，將文件中的數據主鍵單獨存儲在Bloom filter中。Bloom filter是一種空間效率很高的隨機數據結構，它利用位數組表示一個集合，當一個元素加入該集合時，通過K個哈希函數將該元素映射到位數組的K個位置處，該K個位置對應的位值置為1。進行數據查詢時，首先查詢該Bloom Filter中是否存儲有待查詢數據的數據主鍵，若存在，加載該Bloom Filter對應的文件進行查詢即可，若不存在，即結束本次查詢。

而發明人在實現本發明的過程中發現，現有技術中，由于文件數量很多，每一文件均會生成對應的Bloom filter，存儲數據主鍵，從而生成不同的Bloom filter，而由于每一數據主鍵存儲時，均需要經過若干個哈希函數進行多次哈希運算，并根據得到的哈希值修改Bloom filter對應的位值，處理運算量較大，特別是文件中數據主鍵較多時，會占用過多的系統資源。

發明內容

有鑒于此，本申請提供了一種布隆過濾器生成方法，用以解決現有技術中布隆過濾器生成處理運算量大，占用系統資源多的技術問題。

本申請還提供了一種布隆過濾器生成裝置，用以保證上述方法在實際應用中的實現。

為實現上述目的，本申請提供如下技術方案：

第一方面，提供了一種布隆過濾器生成方法，包括：

獲取待合并文件，其中，所述待合并文件包括刪除記錄；

當所述待合并文件中，所述刪除記錄的數量滿足誤判允許范圍時，獲取每一待合并文件的布隆過濾器Bloom filter，其中，不同待合并文件的Bloom filter容量相同；

將不同待合并文件的Bloom filter中的相同位置處的位值進行按位或操作，得到目標Bloom filter，作為所述不同待合并文件進行合并后的合并文件的Bloom filter。

在所述第一方面的第一種可能實現方式中，所述待合并文件中，所述刪除記錄的數量滿足誤判允許范圍具體是所述刪除記錄與所述待合并文件的所有記錄的數量比例小于或等于預設門限值。

在所述第一方面的第二種可能實現方式中，所述獲取每一待合并文件的布隆過濾器Bloom filter包括：

獲取每一待合并文件的按照預設容量，生成的布隆過濾器Bloom filter，其中，所述預設容量根據預期合并文件個數確定。

結合所述第一方面的第二種可能實現方式，還提供了所述第一方面的第三種可能實現方式，所述將不同待合并文件的Bloom filter中的相同位置處的位值進行按位或操作包括：

當所述待合并文件的數量小于或等于所述預期合并文件個數時，將不同待合并文件的Bloom filter中的相同位置處的位值進行按位或操作。

結合所述第一方面的第一種可能實現方式，還提供了所述第一方面的第四種可能實現方式，所述方法還包括：

檢測存儲介質的輸出輸入IO壓力是否大于承載壓力；

如果是，降低所述預設門限值；

如果否，增加所述預設門限值。

結合所述第一方面的第四種可能實現方式，還提供了所述第一方面的第五種可能實現方式，所述檢測所述存儲介質的輸入輸出IO壓力是否大于承載壓力具體是：

測試存儲介質的最大讀速度；

檢測所述存儲介質實時讀速度是否大于所述最大讀速度，當大于所述最大讀速度時，確定IO壓力大于承載壓力。