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

有效

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

1.一種布隆過濾器生成方法，其特征在于，包括：

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

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

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

2.根據權利要求1所述方法，其特征在于，所述待合并文件中，所述刪除記錄的數量滿足誤判允許范圍具體是所述刪除記錄與所述待合并文件的所有記錄的數量比例小于或等于預設門限值。

3.根據權利要求1所述的方法，其特征在于，所述獲取每一待合并文件的布隆過濾器Bloom filter包括：

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

4.根據權利要求3所述的方法，其特征在于，所述將不同待合并文件的Bloom filter中的相同位置處的位值進行按位或操作包括：

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

5.根據權利要求2所述的方法，其特征在于，所述方法還包括：

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

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

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

6.根據權利要求5所述的方法，其特征在于，所述檢測所述存儲介質的輸入輸出IO壓力是否大于承載壓力具體是：

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

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

7.根據權利要求1所述的方法，其特征在于，將不同待合并文件的Bloom filter中的相同位置處的位值進行按位或操作，得到目標Bloom filter，作為所述不同待合并文件進行合并后的合并文件的Bloom filter包括：

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

8.根據權利要求4所述的方法，其特征在于，當所述刪除記錄的數量不滿足誤判允許范圍，或者所述待合并文件的數量大于所述預期合并文件個數時，所述方法還包括：

當所述待合并文件進行合并時，確定合并過程中得到的每一條記錄的數據主鍵；

將所述數據主鍵的鍵值進行哈希運算，并將得到的哈希值映射到預設合并Bloom filter的相應位置處。

9.一種布隆過濾器生成裝置，其特征在于，包括：

第一獲取模塊，用于獲取待合并文件，其中，所述待合并文件包括刪除記錄；

第一判斷模塊，用于判斷所述第一獲取模塊獲取的待合并文件中，所述刪除記錄的數量是否滿足誤判允許范圍；

第二獲取模塊，用于當所述第一判斷模塊結果為是時，獲取每一待合并文件的布隆過濾器Bloom filter，其中，不同待合并文件的Bloom filter容量相同；

第一生成模塊，用于將不同待合并文件的Bloom filter中的相同位置處的位值進行按位或操作，得到目標Bloom filter，作為所述不同待合并文件進行合并后的合并文件的Bloomfilter。

10.根據權利要求9所述的裝置，其特征在于，所述第一判斷模塊判斷所述第一獲取模塊獲取的待合并文件中，所述刪除記錄的數量是否滿足誤判允許范圍具體是判斷所述刪除記錄與所述待合并文件的所有記錄的數量比例是否小于或等于預設門限值。

11.根據權利要求9所述的裝置，其特征在于，所述第二獲取模塊獲取每一待合并文件的布隆過濾器Bloomfilter具體是獲取每一待合并文件的按照預設容量生成的布隆過濾器Bloomfilter，其中，所述預設容量根據預期合并文件個數確定。