日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
牛哄哄的布隆過濾器，有什么用？

圖片來自 包圖網(wǎng)

萬載ssl適用于網(wǎng)站、小程序/APP、API接口等需要進(jìn)行數(shù)據(jù)傳輸應(yīng)用場景，ssl證書未來市場廣闊！成為創(chuàng)新互聯(lián)的ssl證書銷售渠道，可以享受市場價格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：13518219792（備注：SSL證書合作）期待與您的合作！

本文會介紹布隆過濾器，空間換時間，以較低的內(nèi)存空間、高效解決這個問題。

性能不夠，緩存來湊

現(xiàn)在的年輕人都喜歡網(wǎng)購，沒事就逛逛淘寶，剁剁手，買些自己喜歡的東西，釋放下工作壓力。

地址：

 
 
 
 
    
  
  
  
  
  1. https://detail.tmall.com/item.htm?id=628993216729 
    2.

上圖是一個天貓 iPhone12 的商品詳情頁，id 表示商品的編號。

我們都知道淘寶的訪問量是非常高的，為了提升系統(tǒng)的吞吐量，做了很多性能優(yōu)化，其中非常重要一點是將信息異構(gòu)到緩存中。

有句話說的好：性能不夠，緩存來湊。但是，使用緩存時，我們要關(guān)注一個重要問題，如果緩存沒有命中怎么辦?

緩存沒有命中，怎么辦?

如上圖：

  • 我們先查詢緩存，判斷緩存中是否有數(shù)據(jù)
  • 如果有數(shù)據(jù)，直接返回
  • 如果緩存為空，我們需要再查一次數(shù)據(jù)庫，并將數(shù)據(jù)格式異構(gòu)化，然后預(yù)熱到緩沖中，然后將結(jié)果返回

注意：步驟③存在風(fēng)險漏洞，如果緩存中數(shù)據(jù)不存在，壓力會轉(zhuǎn)嫁給數(shù)據(jù)庫。假如被競爭對手利用，搞無效請求流量攻擊，瞬間大量請求打到數(shù)據(jù)庫中，對系統(tǒng)性能產(chǎn)生很大影響，很容易把數(shù)據(jù)庫打掛，這種現(xiàn)象稱為緩存穿透。

那么如何處理緩存穿透?

我們的思路是，緩存中能不能判斷這個數(shù)據(jù)庫值的存在性，如果真的不存在，直接返回，也避免一次數(shù)據(jù)庫查詢。

由于不存在是個無限邊界，所以，我們采用反向策略，將存在的值建立一個高效的檢索。每次緩存取值時，先走一次判空檢索。

簡單歸納下，這個框架的要求：

  • 快速檢索
  • 內(nèi)存空間要非常小

經(jīng)調(diào)研，我們發(fā)現(xiàn)布隆過濾器具備以上兩個條件。

什么是布隆過濾器?

布隆過濾器(Bloom Filter)是 1970 年由布隆提出的。它實際上是一個很長的二進(jìn)制向量和一系列隨機映射函數(shù)。

布隆過濾器可以用于檢索一個元素是否在一個集合中：

優(yōu)點：空間效率和查詢時間都遠(yuǎn)遠(yuǎn)超過一般的算法。

缺點：有一定的誤識別率，刪除困難。

布隆過濾器如何構(gòu)建?

布隆過濾器本質(zhì)上是一個 n 位的二進(jìn)制數(shù)組，用 0 和 1 表示。假如我們以商品為例，有三件商品，商品編碼分別為，id1、id2、id3。

①首先，對 id1，進(jìn)行三次哈希，并確定其在二進(jìn)制數(shù)組中的位置。

三次哈希，對應(yīng)的二進(jìn)制數(shù)組下標(biāo)分別是 2、5、8，將原始數(shù)據(jù)從 0 變?yōu)?1。

②對 id2，進(jìn)行三次哈希，并確定其在二進(jìn)制數(shù)組中的位置。

三次哈希，對應(yīng)的二進(jìn)制數(shù)組下標(biāo)分別是 2、7、98，將原始數(shù)據(jù)從 0 變?yōu)?1。

下標(biāo) 2，之前已經(jīng)被操作設(shè)置成 1，則本次認(rèn)為是哈希沖突，不需要改動。

Hash 規(guī)則：如果在 Hash 后，原始位它是 0 的話，將其從 0 變?yōu)?1;如果本身這一位就是 1 的話，則保持不變。

布隆過濾器如何使用?

如下圖：

跟初始化的過程有點類似，當(dāng)查詢一件商品的緩存信息時，我們首先要判斷這件商品是否存在：

  • 通過三個哈希函數(shù)對商品 id 計算哈希值
  • 然后，在布隆數(shù)組中查找訪問對應(yīng)的位值，0 或 1
  • 判斷，三個值中，只要有一個不是 1，那么我們認(rèn)為數(shù)據(jù)是不存在的。

注意：布隆過濾器只能精確判斷數(shù)據(jù)不存在情況，對于存在我們只能說是可能，因為存在 Hash 沖突情況，當(dāng)然這個概率非常低。

如何減少布隆過濾器的誤判?

①增加二進(jìn)制位數(shù)組的長度。這樣經(jīng)過 hash 后數(shù)據(jù)會更加的離散化，出現(xiàn)沖突的概率會大大降低。

②增加 Hash 的次數(shù)，變相的增加數(shù)據(jù)特征，特征越多，沖突的概率越小。

布隆過濾器會不會很費內(nèi)存?

帶著疑問，我們來做個實驗：假設(shè)有 1 千萬個數(shù)據(jù)，我們需要記錄其是否存在。存在的話標(biāo)記 1，不存在標(biāo)記為 0。技術(shù)選型，框架采用 Redis 的 BitMap 存儲。

數(shù)據(jù)初始化預(yù)熱代碼：

 
 
 
 
    
  
  
  
  
  1. redisTemplate.executePipelined(new RedisCallback() { 
    2. 
  
  
  
  
  2.     @Nullable 
    3. 
  
  
  
  
  3.     @Override 
    4. 
  
  
  
  
  4.     public Long doInRedis(RedisConnection connection) throws DataAccessException { 
    5. 
  
  
  
  
  5.         connection.openPipeline(); 
    6. 
  
  
  
  
  6.         for (int offset = 10000000; offset >= 0; offset--) { 
    7. 
  
  
  
  
  7.             boolean value = offset % 2 == 0 ? true : false; 
    8. 
  
  
  
  
  8.             connection.setBit("bloom-filter-data-1".getBytes(), offset, value); 
    9. 
  
  
  
  
  9.         } 
    10. 
  
  
  
  
  10.         connection.closePipeline(); 
    11. 
  
  
  
  
  11.         return null; 
    12. 
  
  
  
  
  12.     } 
    13. 
  
  
  
  
  13. }); 
    14. 
  
  
  
  
  14. System.out.println("數(shù)據(jù)預(yù)熱完成"); 
    15.

性能有點慢，我們也可以采用分組形式，10000 個數(shù)一組，多批次提交。

數(shù)據(jù)上傳完了后，大小 1.19M，跟我們設(shè)想的一樣。

計算公式：10000000/8/1024/1024=1.19M

Java 應(yīng)用中，如何使用布隆過濾器?

Java 語言的生態(tài)非常繁榮，提供了很多開箱即用的開源框架供我們使用。布隆過濾器也不例外，Java 中提供了一個 Redisson 的組件，它內(nèi)置了布隆過濾器。

首先引入依賴包：

 
 
 
 
    
  
  
  
  
  1.  
    2. 
  
  
  
  
  2.     org.redisson 
    3. 
  
  
  
  
  3.     redisson 
    4. 
  
  
  
  
  4.     3.11.1 
    5. 
  
  
  
  
  5.  
    6.

代碼示例：

 
 
 
 
    
  
  
  
  
  1. /** 
    2. 
  
  
  
  
  2.  * @author  
    3. 
  
  
  
  
  3.  */ 
    4. 
  
  
  
  
  4. @Test 
    5. 
  
  
  
  
  5. public void test5() { 
    6. 
  
  
  
  
  6.     Config config = new Config(); 
    7. 
  
  
  
  
  7.     config.useSingleServer().setAddress("redis://172.16.67.37:6379"); 
    8. 
  
  
  
  
  8.     RedissonClient cient = Redisson.create(config); 
    9. 
  
  
  
  
  9.     RBloomFilter bloomFilter = cient.getBloomFilter("test5-bloom-filter"); 
    10. 
  
  
  
  
  10.     // 初始化布隆過濾器，數(shù)組長度100W，誤判率 1% 
    11. 
  
  
  
  
  11.     bloomFilter.tryInit(1000000L, 0.01); 
    12. 
  
  
  
  
  12.     // 添加數(shù)據(jù) 
    13. 
  
  
  
  
  13.     bloomFilter.add("Tom哥"); 
    14. 
  
  
  
  
  14.     // 判斷是否存在 
    15. 
  
  
  
  
  15.     System.out.println(bloomFilter.contains("微觀技術(shù)")); 
    16. 
  
  
  
  
  16.     System.out.println(bloomFilter.contains("Tom哥")); 
    17. 
  
  
  
  
  17. } 
    18.

運行結(jié)果：

 
 
 
 
    
  
  
  
  
  1. false   // 肯定不存在 
    2. 
  
  
  
  
  2. true    // 可能存在，有1%的誤判率 
    3.

注意：誤判率設(shè)置過小，會產(chǎn)生更多次的 Hash 操作，降低系統(tǒng)的性能。通常我們的建議值是 1%。

布隆過濾器二進(jìn)制數(shù)組，如何處理刪除?

初始化后的布隆過濾器，可以直接拿來使用了。但是如果原始數(shù)據(jù)刪除了怎么辦?布隆過濾器二進(jìn)制數(shù)組如何維護(hù)?

直接刪除不行嗎?還真不行!因為這里面有 Hash 沖突的可能，會導(dǎo)致誤刪。

怎么辦?

  • 方案 1：開發(fā)定時任務(wù)，每隔幾個小時，自動創(chuàng)建一個新的布隆過濾器數(shù)組，替換老的，有點 CopyOnWriteArrayList 的味道。
  • 方案 2：布隆過濾器增加一個等長的數(shù)組，存儲計數(shù)器，主要解決沖突問題，每次刪除時對應(yīng)的計數(shù)器減一，如果結(jié)果為 0，更新主數(shù)組的二進(jìn)制值為 0。

布隆過濾器的應(yīng)用場景

如下：

本文重點介紹的，解決緩存穿透。

網(wǎng)頁爬蟲對 URL 的去重，避免爬取相同的 URL 地址。

反垃圾郵件，從數(shù)十億個垃圾郵件列表中判斷某郵箱是否垃圾郵箱。

作者：Tom哥

編輯：陶家龍

出處：轉(zhuǎn)載自公眾號微觀技術(shù)(ID：weiguanjishu)


本文題目：牛哄哄的布隆過濾器，有什么用？
本文URL：http://www.dlmjj.cn/article/cdsjcih.html