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

有效

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

1.一種布隆過(guò)濾器系統(tǒng)，其特征在于，包括：

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

計(jì)算過(guò)濾器bit數(shù)組模塊：根據(jù)初始化過(guò)濾器生成的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ù)庫(kù)Redis中查詢每一個(gè)bit值在數(shù)據(jù)庫(kù)Redis里面bit位的值：如果值為0，則表示沒(méi)有任何一個(gè)值映射到這個(gè)bit位上，value這個(gè)值不存在，調(diào)用更新或存儲(chǔ)過(guò)濾器模塊；如果返回的值為1，這value這個(gè)值已經(jīng)存在，調(diào)用刪除過(guò)濾器模塊；

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

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

初始化的n與p值后就可以控制bitSize與numHashFunctions值的生成大小，從而實(shí)現(xiàn)把新增到Redis中的值分區(qū)，每個(gè)區(qū)段的值有長(zhǎng)度限制從而達(dá)到相互不影響的目的；

所述numHashFunctions和bitSize決定過(guò)濾器bit位的長(zhǎng)度；

過(guò)濾器bit位的長(zhǎng)度會(huì)影響過(guò)濾器最終的查詢與更新值的效率與錯(cuò)誤率；

所述生成一個(gè)value的過(guò)程包括：

初始化value數(shù)組值，數(shù)組長(zhǎng)度為numHashFunctions，用戶使用過(guò)濾器時(shí)會(huì)傳入需要被驗(yàn)證的值key，然后把key生成hash 64位的long類型值，把這個(gè)long類型值生成10位長(zhǎng)度的int類型值hash1，再用這個(gè)long類型值無(wú)符號(hào)右移32位生成10位長(zhǎng)度的int類型值hash2；

然后按照numHashFunctions長(zhǎng)度來(lái)循環(huán)，按照hash1+i*hash2的計(jì)算方法生成nextHash值，i是循環(huán)下標(biāo)，判斷nextHash值是否小于0，小于0就對(duì)nextHash值取反運(yùn)算；

然后給value賦值，值生成方法為：bitSize對(duì)nextHash取余運(yùn)算：bit＝nextHash％bitSize，bit值的大小不超過(guò)bitSize值；

通過(guò)采用把p與n兩個(gè)參數(shù)變?yōu)閯?dòng)態(tài)，改造計(jì)算過(guò)濾器bit數(shù)組，包括初始化過(guò)濾器、計(jì)算過(guò)濾器bit數(shù)組、更新/存儲(chǔ)過(guò)濾器；在更新/存儲(chǔ)過(guò)濾器時(shí)創(chuàng)建一個(gè)新的key：countValue，用來(lái)存儲(chǔ)統(tǒng)計(jì)過(guò)濾器存放過(guò)的value的數(shù)量，通過(guò)countValue知道已經(jīng)存放的value總量，按照n等于2億數(shù)據(jù)量來(lái)切分n，把n等分或按照比例分為100份，相當(dāng)于劃分100個(gè)區(qū)間，根據(jù)countValue大小當(dāng)countValue每到達(dá)一個(gè)等份值時(shí)則更新p與n兩個(gè)參數(shù)，使其根據(jù)實(shí)際數(shù)據(jù)量增大而改變從而改變numHashFunctions和bitSize；bitSize的大小在100個(gè)區(qū)間里的每個(gè)區(qū)間中它的值是成倍數(shù)關(guān)系的，這樣的倍數(shù)關(guān)系會(huì)改變過(guò)濾器bit數(shù)組中每個(gè)bit位大小的區(qū)間；當(dāng)每個(gè)bit位大小的在100個(gè)區(qū)間中時(shí)相當(dāng)于把過(guò)濾器所有的bit位劃分了100份相對(duì)獨(dú)立的空間存儲(chǔ)；

countValue：記錄項(xiàng)目實(shí)際過(guò)濾或存儲(chǔ)的值，初始化為0，根據(jù)實(shí)際使用數(shù)量遞增，存放在Redis中保存；

n值：表示預(yù)訂的過(guò)濾值個(gè)數(shù)，初始化為2000000，以2000000為單位把目標(biāo)值200000000分100個(gè)區(qū)段，在項(xiàng)目運(yùn)行過(guò)程中單個(gè)區(qū)段固定不變；但當(dāng)countValue值的值等于n時(shí)，n值就會(huì)被重新初始化，重新初始化的值為：n乘2，也就是以n值為基礎(chǔ)倍數(shù)擴(kuò)增；

p值：表示可接受的數(shù)據(jù)過(guò)濾誤判概率，這個(gè)值的生成方法跟n值相同，初始化為0.0000001，在運(yùn)行過(guò)程中單個(gè)區(qū)段固定不變；但當(dāng)countValue值的值等于n時(shí)，p值就會(huì)被重新初始化，重新初始化的值為：p除2；

把p與n兩個(gè)參數(shù)變?yōu)閯?dòng)態(tài)，刪除過(guò)濾器的計(jì)數(shù)器Counter的值根據(jù)countValue值到達(dá)的區(qū)間而等比例增大Counter大小，使得過(guò)濾器的每一個(gè)階段擁有自己Counter，實(shí)現(xiàn)平衡空間利用率與資源占用的矛盾，保證過(guò)濾器的使用效率；

當(dāng)傳入需要?jiǎng)h除的value后，根據(jù)單個(gè)bit位把計(jì)數(shù)器Counter的值減1，逐個(gè)處理；

使numHashFunctions永遠(yuǎn)不會(huì)接近為1，控制到最小值接近或等于3，達(dá)到使過(guò)濾器的錯(cuò)誤率不會(huì)降低。