BloomFilter

BloomFilter是一種空間效率的概率型數(shù)據(jù)結(jié)構(gòu)，由Burton Howard Bloom 1970年提出的钮莲。通常用來判斷一個元素是否在集合中免钻。具有極高的空間效率，但是會帶來假陽性(False positive)的錯誤崔拥。

False positive&&False negatives

由于BloomFiter犧牲了一定的準(zhǔn)確率換取空間效率极舔。所以帶來了False positive的問題。

False positive

BloomFilter在判斷一個元素在集合中的時候握童，會出現(xiàn)一定的錯誤率姆怪，這個錯誤率稱為False positive的。通吃杓ǎ縮寫為fpp.

False negatives

BloomFilter判斷一個元素不在集合中的時候的錯誤率稽揭。 BloomFilter判斷該元素不在集合中，則該元素一定不再集合中肥卡。故False negatives概率為0.

算法描述

BloomFilter使用長度為m bit的字節(jié)數(shù)組溪掀，使用k個hash函數(shù)，
增加一個元素: 通過k次hash將元素映射到字節(jié)數(shù)組中k個位置中步鉴，并設(shè)置對應(yīng)位置的字節(jié)為1.
查詢元素是否存在: 將元素k次hash得到k個位置揪胃，如果對應(yīng)k個位置的bit是1則認為存在，反之則認為不存在氛琢。

bit數(shù)組大小估算

其中m為bit數(shù)組大小喊递，fpp為預(yù)估的假陽性概率，n為預(yù)估插入值數(shù)量阳似，k為hash次數(shù)骚勘。具體公式推導(dǎo)可以參考wiki。
可以看見隨著插入數(shù)量的增多和假陽性概率降低(更高的準(zhǔn)確率)所需要的空間大小會增加。

以上介紹了BloomFilter的一些基本的概念俏讹，下面來看看BloomFilter的使用当宴。

BloomFilter Guava

Guava中實現(xiàn)了BloomFilter, 首先看一個簡單例子。

示例

    public void testGuavaBloomFilter() {
        BloomFilter<String> bloomFilter = BloomFilter.create((Funnel<String>) (from, into) -> {
            into.putString(from, Charsets.UTF_8);
        }, 100_0000, 0.000_0001);

        String testElement1 = "123";
        String testElement2 = "456";
        String testElement3 = "789";

        bloomFilter.put(testElement1);
        bloomFilter.put(testElement2);
        System.out.println(bloomFilter.mightContain(testElement1));
        System.out.println(bloomFilter.mightContain(testElement2));
        System.out.println(bloomFilter.mightContain(testElement3));

    }

通過BloomFiter類create方法創(chuàng)建了一個預(yù)計插入數(shù)為100w, fpp為0.0000001的BloomFilter. 調(diào)用BloomFiter#put插入元素泽疆，通過mightContain來判斷元素是否存在户矢。

內(nèi)部實現(xiàn)

上面介紹了BloomFilter的使用，下面來分析下BloomFilter的內(nèi)部實現(xiàn)殉疼。
Guava Bloomfilter 實現(xiàn)主要涉及到BloomFilter以及BloomFilterStrategies梯浪，我們首先看下BloomFilter的一些重要函數(shù)

1 create

BloomFilter調(diào)用create方法會傳入三個參數(shù)
1 funnel
2 expectedInsertions 預(yù)故插入的數(shù)量
3 fpp 假陽性的概率

  static <T> BloomFilter<T> create(
      Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {
        long numBits = optimalNumOfBits(expectedInsertions, fpp);
    int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
    try {
      return new BloomFilter<T>(new BitArray(numBits), numHashFunctions, funnel, strategy);
    } catch (IllegalArgumentException e) {
      throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e);
    }
  }

create會對傳入的參數(shù)進行校驗，然后調(diào)用optimalNumOfBits&&optimalNumOfHashFunctions 算出所需的bit數(shù)組的大小以及hash函數(shù)的個數(shù)株依。

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


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

optimalNumOfBits&&optimalNumOfHashFunctions方法實現(xiàn)BloomFilter bit數(shù)組大小以及hash函數(shù)的計算公式驱证。

put

  public boolean put(T object) {
    return strategy.put(object, funnel, numHashFunctions, bits);
  }

BloomFilter#put實現(xiàn)是直接調(diào)用BloomFilter.Strategy#put, BloomFilter.Strategy的實現(xiàn)是通過策略枚舉, 目前有兩個實現(xiàn)MURMUR128_MITZ_32,MURMUR128_MITZ_64.
但是create方法中默認只會使用到MURMUR128_MITZ_64. 所以我們主要看看MURMUR128_MITZ_64的實現(xiàn).

    //BloomFilterStrategies.MURMUR128_MITZ_64
    public <T> boolean put(
        T object, Funnel<? super T> funnel, int numHashFunctions, BitArray 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;

1 put方法使用128bit murmur3哈希算法對object進行hash得到128bit字節(jié)數(shù)組.
2 然后分別取低8位置創(chuàng)建hash1延窜，高8位創(chuàng)建hash2.
3 然后通過hash1+hash2累加來模擬實現(xiàn)k次哈希恋腕， 并取摸設(shè)置相應(yīng)的bit位為1.

mightContain

  public boolean put(T object) {
    return strategy.put(object, funnel, numHashFunctions, bits);
  }

BloomFilter#mightContain的實現(xiàn)也是直接調(diào)用BloomFilter.Strategy#mightContain

    //BloomFilterStrategies.MURMUR128_MITZ_64
    public <T> boolean mightContain(
        T object, Funnel<? super T> funnel, int numHashFunctions, BitArray 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;
    }

BloomFilterStrategies#mightContain和put方法類似通過hash1和hash2相加模擬k次哈希, 循環(huán)中任何一次對應(yīng)bit為0則認為不存在，否則認為是存在的逆瑞。
這個方法名取的很不錯荠藤，mightContain返回true只能表示對應(yīng)元素可能存在集合中，因為存在fpp可能性获高。

BloomFilter基于redis實現(xiàn)

上一部分已經(jīng)分析了guava中Bloomfilter實現(xiàn)哈肖，guava版實現(xiàn)主要問題在于無法支持集群環(huán)境. 為了支持集群環(huán)境主要考慮通過redis setbit來實現(xiàn)BloomFilter

SETBIT: Sets or clears the bit at offset in the string value stored at key.The bit is either set or cleared depending on value, which can be either 0 or 1. When key does not exist, a new string value is created. The string is grown to make sure it can hold a bit at offset. The offset argument is required to be greater than or equal to 0, and smaller than 2^32 (this limits bitmaps to 512MB). When the string at key is grown, added bits are set to 0

setbit在redis中value其實是以string類型存儲。支持自增長最大能支持增長到2^32,也就是512MB念秧。

實現(xiàn)

Guava中最后通過操作BloomFilterStrategies.BitArray,故這里改造主要考慮替換BitArray實現(xiàn)淤井。這里主要貼出一些主要的代碼。

#me.ttting.common.hash.BitArray
public interface BitArray {
    void setBitSize(long bitSize);

    boolean set(long index);

    boolean get(long index);

    long bitSize();
}

定義一個BitArray接口,改造BloomFilterStrategies面向BitArray接口編程摊趾。

    @Override
    public void setBitSize(long bitSize) {
        if (bitSize > MAX_REDIS_BIT_SIZE)
            throw new IllegalArgumentException("Invalid redis bit size, must small than 2 to the 32");

        this.bitSize = bitSize;
    }

    @Override
    public boolean set(long index) {
        boolean result;
        result = (Boolean) execute(jedis -> {
            Boolean setbit = jedis.setbit(key, index, true);
            return !setbit;
        });
        return result;
    }

    @Override
    public boolean get(long index) {
        boolean result;
        result = (Boolean) execute(jedis -> jedis.getbit(key, index));
        return result;
    }

基于jedis實現(xiàn)一個基于redis版本的Bloomfilter. 后續(xù)通過增加BitArray的實現(xiàn)可以替換成任意實現(xiàn)币狠。

示例

    public static void main(String[] args) {
        JedisPool jedisPool = new JedisPool("localhost", 6379);
        JedisBitArray jedisBitArray = new JedisBitArray(jedisPool, "test-1");
        BloomFilter<String> bloomFilter = BloomFilter.create((Funnel<String>) (from, into) 
        ->into.putString(from, Charsets.UTF_8), 1_0000_0000, 0.0000001, BloomFilterStrategies.MURMUR128_MITZ_32, jedisBitArray);

        bloomFilter.put("111");
        bloomFilter.put("222");
        System.out.println(bloomFilter.mightContain("111"));
        System.out.println(bloomFilter.mightContain("222"));
        System.out.println(bloomFilter.mightContain("333"));

    }

具體的使用和實現(xiàn)可見https://github.com/ttting/redis-bloomfilter