【guava】大資料量下的集合過濾—Bloom Filter

1.概述

轉載防丢失，請看原文

算法背景

相似文章：Bing搜尋核心技術BitFunnel原理

如果想判斷一個元素是不是在一個集合裡，一般想到的是将集合中所有元素儲存起來，然後通過比較确定。連結清單、樹、散清單（又叫哈希表，Hash table）等等資料結構都是這種思路，存儲位置要麼是磁盤，要麼是記憶體。很多時候要麼是以時間換空間，要麼是以空間換時間。

在響應時間要求比較嚴格的情況下，如果我們存在内裡，那麼随着集合中元素的增加，我們需要的存儲空間越來越大，以及檢索的時間越來越長，導緻記憶體開銷太大、時間效率變低。

此時需要考慮解決的問題就是，在資料量比較大的情況下，既滿足時間要求，又滿足空間的要求。即我們需要一個時間和空間消耗都比較小的資料結構和算法。Bloom Filter就是一種解決方案。

Bloom Filter 概念

布隆過濾器（英語：Bloom Filter）是1970年由布隆提出的。它實際上是一個很長的二進制向量和一系列随機映射函數。布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都遠遠超過一般的算法，缺點是有一定的誤識别率和删除困難。

Bloom Filter 原理

布隆過濾器的原理是，當一個元素被加入集合時，通過K個散列函數将這個元素映射成一個位數組中的K個點，把它們置為1。檢索時，我們隻要看看這些點是不是都是1就（大約）知道集合中有沒有它了：如果這些點有任何一個0，則被檢元素一定不在；如果都是1，則被檢元素很可能在。這就是布隆過濾器的基本思想。

Bloom Filter跟單哈希函數Bit-Map不同之處在于：Bloom Filter使用了k個哈希函數，每個字元串跟k個bit對應。進而降低了沖突的機率。

Bloom Filter的缺點

bloom filter之是以能做到在時間和空間上的效率比較高，是因為犧牲了判斷的準确率、删除的便利性

存在誤判，可能要查到的元素并沒有在容器中，但是hash之後得到的k個位置上值都是1。如果bloom filter中存儲的是黑名單，那麼可以通過建立一個白名單來存儲可能會誤判的元素。

删除困難。一個放入容器的元素映射到bit數組的k個位置上是1，删除的時候不能簡單的直接置為0，可能會影響其他元素的判斷。可以采用Counting Bloom Filter

Bloom Filter 實作

布隆過濾器有許多實作與優化，Guava中就提供了一種Bloom Filter的實作。

在使用bloom filter時，繞不過的兩點是預估資料量n以及期望的誤判率fpp，

在實作bloom filter時，繞不過的兩點就是hash函數的選取以及bit數組的大小。

對于一個确定的場景，我們預估要存的資料量為n，期望的誤判率為fpp，然後需要計算我們需要的Bit數組的大小m，以及hash函數的個數k，并選擇hash函數

(1)Bit數組大小選擇

　　根據預估資料量n以及誤判率fpp，bit數組大小的m的計算方式：

(2)哈希函數選擇

由預估資料量n以及bit數組長度m，可以得到一個hash函數的個數k：

哈希函數的選擇對性能的影響應該是很大的，一個好的哈希函數要能近似等機率的将字元串映射到各個Bit。選擇k個不同的哈希函數比較麻煩，一種簡單的方法是選擇一個哈希函數，然後送入k個不同的參數。
           

哈希函數個數k、位數組大小m、加入的字元串數量n的關系可以參考Bloom Filters - the math，Bloom_filter-wikipedia

看看Guava中BloomFilter中對于m和k值計算的實作，在com.google.common.hash.BloomFilter類中：

/**
 * 計算 Bloom Filter的bit位數m
 *
 * <p>See http://en.wikipedia.org/wiki/Bloom_filter#Probability_of_false_positives for the
 * formula.
 *
 * @param n 預期資料量
 * @param p 誤判率 (must be 0 < p < 1)
 */ 
@VisibleForTesting 
static long optimalNumOfBits(long n, double p) { 
  if (p == 0) { 
    p = Double.MIN_VALUE; 
  } 
  return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2))); 
} 
    
    
    
    
/**
 * 計算最佳k值，即在Bloom過濾器中插入的每個元素的哈希數
 *
 * <p>See http://en.wikipedia.org/wiki/File:Bloom_filter_fp_probability.svg for the formula.
 *
 * @param n 預期資料量
 * @param m bloom filter中總的bit位數 (must be positive)
 */ 
@VisibleForTesting 
static int optimalNumOfHashFunctions(long n, long m) { 
  // (m / n) * log(2), but avoid truncation due to division! 
  return Math.max(1, (int) Math.round((double) m / n * Math.log(2))); 
} 
　　
           

BloomFilter實作的另一個重點就是怎麼利用hash函數把資料映射到bit數組中。Guava的實作是對元素通過MurmurHash3計算hash值，将得到的hash值取高8個位元組以及低8個位元組進行計算，以得目前元素在bit數組中對應的多個位置。MurmurHash3算法詳見:Murmur哈希，于2008年被發明。這個算法hbase,redis,kafka都在使用。

這個過程的實作在兩個地方：

将資料放入bloom filter中

判斷資料是否已在bloom filter中

這兩個地方的實作大同小異，差別隻是，前者是put資料，後者是查資料。

這裡看一下put的過程，hash政策以MURMUR128_MITZ_64為例：

public <T> boolean put( 
    T object, Funnel<? super T> funnel, int numHashFunctions, LockFreeBitArray bits) { 
  long bitSize = bits.bitSize(); 
    
  //利用MurmurHash3得到資料的hash值對應的位元組數組 
  byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal(); 
    
    
  //取低8個位元組、高8個位元組，轉成long類型 
  long hash1 = lowerEight(bytes); 
  long hash2 = upperEight(bytes); 
    
  boolean bitsChanged = false; 
    
    
  //這裡的combinedHash = hash1 + i * hash2 
  long combinedHash = hash1; 
    
    
  //根據combinedHash，得到放入的元素在bit數組中的k個位置，将其置1 
  for (int i = 0; i < numHashFunctions; i++) { 
    bitsChanged |= bits.set((combinedHash & Long.MAX_VALUE) % bitSize); 
    combinedHash += hash2; 
  } 
  return bitsChanged; 
} 
           

判斷元素是否在bloom filter中的方法mightContain與上面的實作基本一緻，不再贅述。

Bloom Filter的使用

簡單寫個demo，用法很簡單，類似HashMap

package com.qunar.sage.wang.common.bloom.filter; 
    
import com.google.common.base.Charsets; 
import com.google.common.hash.BloomFilter; 
import com.google.common.hash.Funnel; 
import com.google.common.hash.Funnels; 
import com.google.common.hash.PrimitiveSink; 
import lombok.AllArgsConstructor; 
import lombok.Builder; 
import lombok.Data; 
import lombok.ToString; 
    
/**
 * BloomFilterTest
 *
 * @author sage.wang
 * @date 18-5-14 下午5:02
 */ 
public class BloomFilterTest { 
        
    public static void main(String[] args) { 
        long expectedInsertions = 10000000; 
        double fpp = 0.00001; 
    
        BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), expectedInsertions, fpp); 
    
        bloomFilter.put("aaa"); 
        bloomFilter.put("bbb"); 
        boolean containsString = bloomFilter.mightContain("aaa"); 
        System.out.println(containsString); 
    
        BloomFilter<Email> emailBloomFilter = BloomFilter 
                .create((Funnel<Email>) (from, into) -> into.putString(from.getDomain(), Charsets.UTF_8), 
                        expectedInsertions, fpp); 
    
        emailBloomFilter.put(new Email("sage.wang", "quanr.com")); 
        boolean containsEmail = emailBloomFilter.mightContain(new Email("sage.wangaaa", "quanr.com")); 
        System.out.println(containsEmail); 
    } 
    
    @Data 
    @Builder 
    @ToString 
    @AllArgsConstructor 
    public static class Email { 
        private String userName; 
        private String domain; 
    } 
    
} 
　　
           

Bloom Filter的應用

常見的幾個應用場景：

cerberus在收集監控資料的時候, 有的系統的監控項量會很大, 需要檢查一個監控項的名字是否已經被記錄到db過了, 如果沒有的話就需要寫入db.

爬蟲過濾已抓到的url就不再抓，可用bloom filter過濾

垃圾郵件過濾。如果用哈希表，每存儲一億個 email位址，就需要 1.6GB的記憶體（用哈希表實作的具體辦法是将每一個 email位址對應成一個八位元組的資訊指紋，然後将這些資訊指紋存入哈希表，由于哈希表的存儲效率一般隻有 50%，是以一個 email位址需要占用十六個位元組。一億個位址大約要 1.6GB，即十六億位元組的記憶體）。是以存貯幾十億個郵件位址可能需要上百 GB的記憶體。而Bloom Filter隻需要哈希表 1/8到 1/4 的大小就能解決同樣的問題。

好文章：

https://blog.csdn.net/jiaomeng/article/details/1495500

https://blog.csdn.net/he_ranly/article/details/94433004