[發(fā)明專利]布隆過濾器系統(tǒng)及過濾方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202010628830.4
• 申請(qǐng)日: 2020-07-02
• 公開（公告）號(hào): CN111930923B
• 公開（公告）日: 2021-07-30
• 發(fā)明（設(shè)計(jì)）人: 方賢斌;曠黎明;師文慶
• 申請(qǐng)（專利權(quán)）人: 上海微億智造科技有限公司;常州微億智造科技有限公司
• 主分類號(hào): G06F16/335
• 分類號(hào): G06F16/335
• 代理公司: 上海段和段律師事務(wù)所 31334
• 代理人: 李佳俊;郭國中

本發(fā)明提供了一種布隆過濾器系統(tǒng)及過濾方法，包括：初始化過濾器模塊：每個(gè)過濾器初始化時(shí)需要傳入p與n兩個(gè)參數(shù)，n為插入的元素個(gè)數(shù)，p為誤報(bào)率，生成哈希函數(shù)個(gè)數(shù)numHashFunctions和布隆過濾器長度bitSize。本發(fā)明極大節(jié)省了單次處理時(shí)間與降低實(shí)際濾誤判概率，過濾器會(huì)達(dá)到更穩(wěn)定更可靠。不會(huì)因?yàn)楹笃跀?shù)據(jù)量大了之后過濾器處理時(shí)間長而拖累其它程序服務(wù)使用。在量化效果上用改造后的過濾器比現(xiàn)有過濾器的綜合性能快100倍左右。

技術(shù)領(lǐng)域

本發(fā)明涉及數(shù)據(jù)過濾技術(shù)領(lǐng)域，具體地，涉及布隆過濾器系統(tǒng)及過濾方法。

背景技術(shù)

隨著技術(shù)發(fā)展與數(shù)據(jù)量的增加，為了最求大數(shù)據(jù)量的準(zhǔn)確性與可用性成為了發(fā)展很快的方向，不論在互聯(lián)網(wǎng)大數(shù)據(jù)上還是在工業(yè)大數(shù)據(jù)場(chǎng)景中涉及的越來越多的應(yīng)用場(chǎng)景。

目前相關(guān)領(lǐng)域存在著很多的過濾器插件，但在使用過程中發(fā)現(xiàn)有很多的弊端與瓶頸，如在過濾器過濾速度上與過濾錯(cuò)誤率上隨著數(shù)據(jù)量的增大而過濾速度呈曲線降低，錯(cuò)誤率也呈現(xiàn)曲線上升，很多公司在解決問題時(shí)采用投入更多硬件資源來集群，但是效果也差強(qiáng)人意且比較耗費(fèi)成本。

如果不處理p與n兩個(gè)參數(shù)的話會(huì)使numHashFunctions變的越來越小和bitSize在一開始就過大，而numHashFunctions變小和bitSize變大后會(huì)導(dǎo)致布隆過濾器效率低下，且每個(gè)bit位都在同一個(gè)區(qū)間內(nèi)，當(dāng)數(shù)據(jù)量增大后后續(xù)生成value值生成相同bit值的概率變的越來越大，當(dāng)不同value值得單個(gè)bit值重復(fù)率變大時(shí)，過濾器生成的bit數(shù)組相同的概率會(huì)同步增加，這種概率增加對(duì)過濾器來說是致命的，應(yīng)為過濾的目的是處理大量數(shù)據(jù)的準(zhǔn)確性與可用性，如果過濾器失去了這個(gè)屬性，則降低了過濾器的實(shí)際作用。bitSize的變大會(huì)導(dǎo)致存儲(chǔ)在過濾器中的空間更多，對(duì)資源占用更大，當(dāng)存儲(chǔ)的value越多時(shí)會(huì)造成過濾器的更新/存儲(chǔ)、讀取的性能變的低下。

如果因?yàn)閮?nèi)存龐大而造成在實(shí)際業(yè)務(wù)中使用過濾器時(shí)拖累性能，在高并發(fā)，高可用的應(yīng)用場(chǎng)景中是非常危險(xiǎn)的，會(huì)影響其它業(yè)務(wù)的處理能力。在過濾器很重要且性能也很重要的情況下，提高過濾器的性能與高可用性變成是唯一的選擇。

發(fā)明內(nèi)容

針對(duì)現(xiàn)有技術(shù)中的缺陷，本發(fā)明的目的是提供一種布隆過濾器系統(tǒng)及過濾方法。

根據(jù)本發(fā)明提供的一種布隆過濾器系統(tǒng)，包括：

初始化過濾器模塊：每個(gè)過濾器初始化時(shí)需要傳入p與n兩個(gè)參數(shù)，n為插入的元素個(gè)數(shù)，p為誤報(bào)率，生成哈希函數(shù)個(gè)數(shù)numHashFunctions和布隆過濾器長度bitSize；

計(jì)算過濾器bit數(shù)組模塊：根據(jù)初始化過濾器生成的numHashFunctions和bitSize以及傳入的被計(jì)算的值key這三個(gè)數(shù)據(jù)生成一個(gè)value，所述value根據(jù)numHashFunctions生成多個(gè)long類型值，然后將多個(gè)long類型值根據(jù)bitSize生成多個(gè)int類型的bit數(shù)組，最終返回bit數(shù)組；

判重模塊：根據(jù)返回的bit數(shù)組進(jìn)行循環(huán)獲得每一個(gè)bit值，在數(shù)據(jù)庫Redis中查詢每一個(gè)bit值在數(shù)據(jù)庫Redis里面bit位的值：如果值為0，則表示沒有任何一個(gè)值映射到這個(gè)bit位上，value這個(gè)值不存在，調(diào)用更新或存儲(chǔ)過濾器模塊；如果返回的值為1，這value這個(gè)值已經(jīng)存在，調(diào)用刪除過濾器模塊；

更新或存儲(chǔ)過濾器模塊：如果判斷value這個(gè)值不存在于過濾器中后，就可以把返回的bit數(shù)組分別指向到bit位置，存儲(chǔ)到Redis中存儲(chǔ)；

刪除過濾器模塊：如果判斷value這個(gè)值已經(jīng)存在于過濾器中，則傳入的被計(jì)算的值key為需要?jiǎng)h除的key值，根據(jù)單個(gè)bit位把刪除過濾器的計(jì)數(shù)器Counter的值減1，逐個(gè)處理。

優(yōu)選地，所述numHashFunctions和bitSize決定過濾器bit位的長度；