[發(fā)明專利]基于布隆過濾器的數(shù)據(jù)查重系統(tǒng)及方法

在審

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

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

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

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

背景技術(shù)

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

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

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

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

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

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

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

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

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

判重模塊：根據(jù)返回的bit數(shù)組進(jìn)行循環(huán)獲得每一個bit值，在數(shù)據(jù)庫Redis中查詢每一個bit值在數(shù)據(jù)庫Redis里面bit位的值：如果值為0，則表示沒有任何一個值映射到這個bit位上，value這個值不存在；如果返回的值為1，這value這個值已經(jīng)存在。

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

過濾器bit位的長度會影響過濾器最終的查詢與更新值的效率與錯誤率。

優(yōu)選地，所述生成一個value的過程包括：