目錄

• 引子
• 布隆過濾器介紹
  • 產(chǎn)生的契機(jī)
  • 設(shè)計(jì)思想
  • 優(yōu)缺點(diǎn)與用途
  • 假陽性率的計(jì)算
• Guava中的布隆過濾器
  • BloomFilter類的成員屬性
  • BloomFilter的構(gòu)造
  • 估計(jì)最優(yōu)m值和k值
  • 哈希策略
  • 位數(shù)組具體實(shí)現(xiàn)
• 總結(jié)

引子

最近在研究推薦系統(tǒng)中已讀內(nèi)容排除以及重復(fù)內(nèi)容去重相關(guān)的問題，布隆過濾器是解決這類問題最好的工具之一，很值得專門寫一篇文章來詳細(xì)講解。

布隆過濾器介紹

布隆過濾器（Bloom Filter，下文簡稱BF）由Burton Howard Bloom在1970年提出，是一種空間效率高的概率型數(shù)據(jù)結(jié)構(gòu)。它專門用來檢測集合中是否存在特定的元素。聽起來是很稀松平常的需求，為什么要使用BF這種數(shù)據(jù)結(jié)構(gòu)呢？

產(chǎn)生的契機(jī)

回想一下，我們平常在檢測集合中是否存在某元素時(shí)，都會(huì)采用比較的方法?？紤]以下情況：

• 如果集合用線性表存儲，查找的時(shí)間復(fù)雜度為O(n)。
• 如果用平衡BST（如AVL樹、紅黑樹）存儲，時(shí)間復(fù)雜度為O(logn)。

• 如果用哈希表存儲，并用鏈地址法與平衡BST解決哈希沖突（參考JDK8的HashMap實(shí)現(xiàn)方法），時(shí)間復(fù)雜度也要有O[log(n/m)]，m為哈希分桶數(shù)。

  
  

總而言之，當(dāng)集合中元素的數(shù)量極多時(shí)，不僅查找會(huì)變得很慢，而且占用的空間也會(huì)大到無法想象。BF就是解決這個(gè)矛盾的利器。

設(shè)計(jì)思想

BF是由一個(gè)長度為m比特的位數(shù)組（bit array）與k個(gè)哈希函數(shù)（hash function）組成的數(shù)據(jù)結(jié)構(gòu)。位數(shù)組均初始化為0，所有哈希函數(shù)都可以分別把輸入數(shù)據(jù)盡量均勻地散列。

當(dāng)要插入一個(gè)元素時(shí)，將其數(shù)據(jù)分別輸入k個(gè)哈希函數(shù)，產(chǎn)生k個(gè)哈希值。以哈希值作為位數(shù)組中的下標(biāo)，將所有k個(gè)對應(yīng)的比特置為1。

當(dāng)要查詢（即判斷是否存在）一個(gè)元素時(shí)，同樣將其數(shù)據(jù)輸入哈希函數(shù)，然后檢查對應(yīng)的k個(gè)比特。如果有任意一個(gè)比特為0，表明該元素一定不在集合中。如果所有比特均為1，表明該集合有（較大的）可能性在集合中。為什么不是一定在集合中呢？因?yàn)橐粋€(gè)比特被置為1有可能會(huì)受到其他元素的影響，這就是所謂“假陽性”（false positive）。相對地，“假陰性”（false negative）在BF中是絕不會(huì)出現(xiàn)的。

下圖示出一個(gè)m=18, k=3的BF示例。集合中的x、y、z三個(gè)元素通過3個(gè)不同的哈希函數(shù)散列到位數(shù)組中。當(dāng)查詢元素w時(shí)，因?yàn)橛幸粋€(gè)比特為0，因此w不在該集合中。

優(yōu)缺點(diǎn)與用途

BF的優(yōu)點(diǎn)是顯而易見的：

• 不需要存儲數(shù)據(jù)本身，只用比特表示，因此空間占用相對于傳統(tǒng)方式有巨大的優(yōu)勢，并且能夠保密數(shù)據(jù)；
• 時(shí)間效率也較高，插入和查詢的時(shí)間復(fù)雜度均為O(k)；
• 哈希函數(shù)之間相互獨(dú)立，可以在硬件指令層面并行計(jì)算。

但是，它的缺點(diǎn)也同樣明顯：

• 存在假陽性的概率，不適用于任何要求100%準(zhǔn)確率的情境；
• 只能插入和查詢元素，不能刪除元素，這與產(chǎn)生假陽性的原因是相同的。我們可以簡單地想到通過計(jì)數(shù)（即將一個(gè)比特?cái)U(kuò)展為計(jì)數(shù)值）來記錄元素?cái)?shù)，但仍然無法保證刪除的元素一定在集合中。

所以，BF在對查準(zhǔn)度要求沒有那么苛刻，而對時(shí)間、空間效率要求較高的場合非常合適，本文第一句話提到的用途即屬于此類。另外，由于它不存在假陰性問題，所以用作“不存在”邏輯的處理時(shí)有奇效，比如可以用來作為緩存系統(tǒng)（如Redis）的緩沖，防止緩存穿透。

假陽性率的計(jì)算

假陽性是BF最大的痛點(diǎn)，因此有必要權(quán)衡，比如計(jì)算一下假陽性的概率。為了簡單一點(diǎn)，就假設(shè)我們的哈希函數(shù)選擇位數(shù)組中的比特時(shí)，都是等概率的。當(dāng)然在設(shè)計(jì)哈希函數(shù)時(shí)，也應(yīng)該盡量滿足均勻分布。

所以，在哈希函數(shù)的個(gè)數(shù)k一定的情況下：

• 位數(shù)組長度m越大，假陽性率越低；
• 已插入元素的個(gè)數(shù)n越大，假陽性率越高。

事實(shí)上，即使哈希函數(shù)不是等概率選擇比特的，最終也會(huì)得出相同的結(jié)果，可以借助吾妻-霍夫丁不等式（Azuma-Hoeffding inequality）證明。我數(shù)學(xué)比較垃圾，就不班門弄斧了。

有一些框架內(nèi)已經(jīng)內(nèi)建了BF的實(shí)現(xiàn)，免去了自己實(shí)現(xiàn)的煩惱。下面以Guava為例，看看Google是怎么做的。

Guava中的布隆過濾器

采用Guava 27.0.1版本的源碼，BF的具體邏輯位于com.google.common.hash.BloomFilter類中。開始讀代碼吧。

BloomFilter類的成員屬性

不多，只有4個(gè)。

  /** The bit set of the BloomFilter (not necessarily power of 2!) */
  private final LockFreeBitArray bits;

  /** Number of hashes per element */
  private final int numHashFunctions;

  /** The funnel to translate Ts to bytes */
  private final Funnel<? super T> funnel;

  /** The strategy we employ to map an element T to {@code numHashFunctions} bit indexes. */
  private final Strategy strategy;

• bits即上文講到的長度為m的位數(shù)組，采用LockFreeBitArray類型做了封裝。
• numHashFunctions即哈希函數(shù)的個(gè)數(shù)k。
• funnel是Funnel接口實(shí)現(xiàn)類的實(shí)例，它用于將任意類型T的輸入數(shù)據(jù)轉(zhuǎn)化為Java基本類型的數(shù)據(jù)（byte、int、char等等）。這里是會(huì)轉(zhuǎn)化為byte。
• strategy是布隆過濾器的哈希策略，即數(shù)據(jù)如何映射到位數(shù)組，其具體方法在BloomFilterStrategies枚舉中。

BloomFilter的構(gòu)造

這個(gè)類的構(gòu)造方法是私有的。要?jiǎng)?chuàng)建它的實(shí)例，應(yīng)該通過公有的create()方法。它一共有5種重載方法，但最終都是調(diào)用了如下的邏輯。

  @VisibleForTesting
  static <T> BloomFilter<T> create(
      Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {
    checkNotNull(funnel);
    checkArgument(
        expectedInsertions >= 0, "Expected insertions (%s) must be >= 0", expectedInsertions);
    checkArgument(fpp > 0.0, "False positive probability (%s) must be > 0.0", fpp);
    checkArgument(fpp < 1.0, "False positive probability (%s) must be < 1.0", fpp);
    checkNotNull(strategy);

    if (expectedInsertions == 0) {
      expectedInsertions = 1;
    }
    /*
     * TODO(user): Put a warning in the javadoc about tiny fpp values, since the resulting size
     * is proportional to -log(p), but there is not much of a point after all, e.g.
     * optimalM(1000, 0.0000000000000001) = 76680 which is less than 10kb. Who cares!
     */
    long numBits = optimalNumOfBits(expectedInsertions, fpp);
    int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
    try {
      return new BloomFilter<T>(new LockFreeBitArray(numBits), numHashFunctions, funnel, strategy);
    } catch (IllegalArgumentException e) {
      throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e);
    }
  }

該方法接受4個(gè)參數(shù)：funnel是插入數(shù)據(jù)的Funnel，expectedInsertions是期望插入的元素總個(gè)數(shù)n，fpp即期望假陽性率p，strategy即哈希策略。

由上可知，位數(shù)組的長度m和哈希函數(shù)的個(gè)數(shù)k分別通過optimalNumOfBits()方法和optimalNumOfHashFunctions()方法來估計(jì)。

估計(jì)最優(yōu)m值和k值

  @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)));
  }

  @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)));
  }

要看懂這兩個(gè)方法，我們得接著上一節(jié)的推導(dǎo)繼續(xù)做下去。

這就是optimalNumOfHashFunctions()方法的邏輯。那么m該如何估計(jì)呢？

這就是optimalNumOfBits()方法的邏輯。

從上也可以得出：

• 如果指定期望假陽性率p，那么最優(yōu)的m值與期望元素?cái)?shù)n呈線性關(guān)系。

• 最優(yōu)的k值實(shí)際上只與p有關(guān)，與m和n都無關(guān)，即：

所以，在創(chuàng)建BloomFilter時(shí)，確定合適的p和n值很重要。

哈希策略

在BloomFilterStrategies枚舉中定義了兩種哈希策略，都基于著名的MurmurHash算法，分別是MURMUR128_MITZ_32和MURMUR128_MITZ_64。前者是一個(gè)簡化版，所以我們來看看后者的實(shí)現(xiàn)方法。

  MURMUR128_MITZ_64() {
    @Override
    public <T> boolean put(
        T object, Funnel<? super T> funnel, int numHashFunctions, LockFreeBitArray bits) {
      long bitSize = bits.bitSize();
      byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal();
      long hash1 = lowerEight(bytes);
      long hash2 = upperEight(bytes);

      boolean bitsChanged = false;
      long combinedHash = hash1;
      for (int i = 0; i < numHashFunctions; i++) {
        // Make the combined hash positive and indexable
        bitsChanged |= bits.set((combinedHash & Long.MAX_VALUE) % bitSize);
        combinedHash += hash2;
      }
      return bitsChanged;
    }

    @Override
    public <T> boolean mightContain(
        T object, Funnel<? super T> funnel, int numHashFunctions, LockFreeBitArray bits) {
      long bitSize = bits.bitSize();
      byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal();
      long hash1 = lowerEight(bytes);
      long hash2 = upperEight(bytes);

      long combinedHash = hash1;
      for (int i = 0; i < numHashFunctions; i++) {
        // Make the combined hash positive and indexable
        if (!bits.get((combinedHash & Long.MAX_VALUE) % bitSize)) {
          return false;
        }
        combinedHash += hash2;
      }
      return true;
    }

    private /* static */ long lowerEight(byte[] bytes) {
      return Longs.fromBytes(
          bytes[7], bytes[6], bytes[5], bytes[4], bytes[3], bytes[2], bytes[1], bytes[0]);
    }

    private /* static */ long upperEight(byte[] bytes) {
      return Longs.fromBytes(
          bytes[15], bytes[14], bytes[13], bytes[12], bytes[11], bytes[10], bytes[9], bytes[8]);
    }
  };

其中put()方法負(fù)責(zé)向布隆過濾器中插入元素，mightContain()方法負(fù)責(zé)判斷元素是否存在。以put()方法為例講解一下流程吧。

1. 使用MurmurHash算法對funnel的輸入數(shù)據(jù)進(jìn)行散列，得到128bit（16B）的字節(jié)數(shù)組。
2. 取低8字節(jié)作為第一個(gè)哈希值hash1，取高8字節(jié)作為第二個(gè)哈希值hash2。
3. 進(jìn)行k次循環(huán)，每次循環(huán)都用hash1與hash2的復(fù)合哈希做散列，然后對m取模，將位數(shù)組中的對應(yīng)比特設(shè)為1。

這里需要注意兩點(diǎn)：

• 在循環(huán)中實(shí)際上應(yīng)用了雙重哈希（double hashing）的思想，即可以用兩個(gè)哈希函數(shù)來模擬k個(gè)，其中i為步長：

  這種方法在開放定址的哈希表中，也經(jīng)常用來減少?zèng)_突。

• 哈希值有可能為負(fù)數(shù)，而負(fù)數(shù)是不能在位數(shù)組中定位的。所以哈希值需要與Long.MAX_VALUE做bitwise AND，直接將其最高位（符號位）置為0，就變成正數(shù)了。

位數(shù)組具體實(shí)現(xiàn)

來看LockFreeBitArray類的部分代碼。

  static final class LockFreeBitArray {
    private static final int LONG_ADDRESSABLE_BITS = 6;
    final AtomicLongArray data;
    private final LongAddable bitCount;

    LockFreeBitArray(long bits) {
      this(new long[Ints.checkedCast(LongMath.divide(bits, 64, RoundingMode.CEILING))]);
    }

    // Used by serialization
    LockFreeBitArray(long[] data) {
      checkArgument(data.length > 0, "data length is zero!");
      this.data = new AtomicLongArray(data);
      this.bitCount = LongAddables.create();
      long bitCount = 0;
      for (long value : data) {
        bitCount += Long.bitCount(value);
      }
      this.bitCount.add(bitCount);
    }

    /** Returns true if the bit changed value. */
    boolean set(long bitIndex) {
      if (get(bitIndex)) {
        return false;
      }

      int longIndex = (int) (bitIndex >>> LONG_ADDRESSABLE_BITS);
      long mask = 1L << bitIndex; // only cares about low 6 bits of bitIndex

      long oldValue;
      long newValue;
      do {
        oldValue = data.get(longIndex);
        newValue = oldValue | mask;
        if (oldValue == newValue) {
          return false;
        }
      } while (!data.compareAndSet(longIndex, oldValue, newValue));

      // We turned the bit on, so increment bitCount.
      bitCount.increment();
      return true;
    }

    boolean get(long bitIndex) {
      return (data.get((int) (bitIndex >>> 6)) & (1L << bitIndex)) != 0;
    }
    // ....
}

看官應(yīng)該能明白為什么它要叫做“LockFree”BitArray了，因?yàn)樗遣捎迷宇愋虯tomicLongArray作為位數(shù)組的存儲的，確實(shí)不需要加鎖。另外還有一個(gè)Guava中特有的LongAddable類型的計(jì)數(shù)器，用來統(tǒng)計(jì)置為1的比特?cái)?shù)。

采用AtomicLongArray除了有并發(fā)上的優(yōu)勢之外，更主要的是它可以表示非常長的位數(shù)組。一個(gè)長整型數(shù)占用64bit，因此data[0]可以代表第0~63bit，data[1]代表64~127bit，data[2]代表128~191bit……依次類推。這樣設(shè)計(jì)的話，將下標(biāo)i無符號右移6位就可以獲得data數(shù)組中對應(yīng)的位置，再在其基礎(chǔ)上左移i位就可以取得對應(yīng)的比特了。

最后多嘴一句，上面的代碼中用到了Long.bitCount()方法計(jì)算long型二進(jìn)制表示中1的數(shù)量，堪稱Java語言中最強(qiáng)的騷操作之一：

 public static int bitCount(long i) {
    // HD, Figure 5-14
    i = i - ((i >>> 1) & 0x5555555555555555L);
    i = (i & 0x3333333333333333L) + ((i >>> 2) & 0x3333333333333333L);
    i = (i + (i >>> 4)) & 0x0f0f0f0f0f0f0f0fL;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    i = i + (i >>> 32);
    return (int)i & 0x7f;
 }

總結(jié)

本文講解了布隆過濾器的產(chǎn)生、設(shè)計(jì)思路和應(yīng)用場景，通過簡單推導(dǎo)明確了其假陽性問題。另外，又通過閱讀Guava中BloomFilter的相關(guān)源碼，了解了設(shè)計(jì)布隆過濾器的技術(shù)要點(diǎn)。之后還會(huì)另外寫文章講述我們在生產(chǎn)環(huán)境中的具體應(yīng)用。