BloomFilter基于redis的实现

BloomFilter

BloomFilter是一种空间效率的概率型数据结构，由Burton Howard Bloom 1970年提出的。通常用来判断一个元素是否在集合中。具有极高的空间效率，但是会带来假阳性(False positive)的错误。

False positive&&False negatives

由于BloomFiter牺牲了一定的准确率换取空间效率。所以带来了False positive的问题。

False positive

BloomFilter在判断一个元素在集合中的时候，会出现一定的错误率，这个错误率称为False positive的。通常缩写为fpp.

False negatives

BloomFilter判断一个元素不在集合中的时候的错误率。 BloomFilter判断该元素不在集合中，则该元素一定不再集合中。故False negatives概率为0.

算法描述

BloomFilter使用长度为m bit的字节数组，使用k个hash函数，
增加一个元素: 通过k次hash将元素映射到字节数组中k个位置中，并设置对应位置的字节为1.
查询元素是否存在: 将元素k次hash得到k个位置，如果对应k个位置的bit是1则认为存在，反之则认为不存在。

bit数组大小估算

其中m为bit数组大小，fpp为预估的假阳性概率，n为预估插入值数量，k为hash次数。具体公式推导可以参考wiki。
可以看见随着插入数量的增多和假阳性概率降低(更高的准确率)所需要的空间大小会增加。

以上介绍了BloomFilter的一些基本的概念，下面来看看BloomFilter的使用。

BloomFilter Guava

Guava中实现了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方法创建了一个预计插入数为100w, fpp为0.0000001的BloomFilter. 调用BloomFiter#put插入元素，通过mightContain来判断元素是否存在。

内部实现

上面介绍了BloomFilter的使用，下面来分析下BloomFilter的内部实现。
Guava Bloomfilter 实现主要涉及到BloomFilter以及BloomFilterStrategies，我们首先看下BloomFilter的一些重要函数

1 create

BloomFilter调用create方法会传入三个参数
1 funnel
2 expectedInsertions 预故插入的数量
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会对传入的参数进行校验，然后调用optimalNumOfBits&&optimalNumOfHashFunctions 算出所需的bit数组的大小以及hash函数的个数。

  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方法实现BloomFilter bit数组大小以及hash函数的计算公式。

put

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

BloomFilter#put实现是直接调用BloomFilter.Strategy#put, BloomFilter.Strategy的实现是通过策略枚举, 目前有两个实现MURMUR128_MITZ_32,MURMUR128_MITZ_64.
但是create方法中默认只会使用到MURMUR128_MITZ_64. 所以我们主要看看MURMUR128_MITZ_64的实现.

    //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字节数组.
2 然后分别取低8位置创建hash1，高8位创建hash2.
3 然后通过hash1+hash2累加来模拟实现k次哈希， 并取摸设置相应的bit位为1.

mightContain

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

BloomFilter#mightContain的实现也是直接调用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次哈希, 循环中任何一次对应bit为0则认为不存在，否则认为是存在的。
这个方法名取的很不错，mightContain返回true只能表示对应元素可能存在集合中，因为存在fpp可能性。

BloomFilter基于redis实现

上一部分已经分析了guava中Bloomfilter实现，guava版实现主要问题在于无法支持集群环境. 为了支持集群环境主要考虑通过redis setbit来实现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。

实现

Guava中最后通过操作BloomFilterStrategies.BitArray,故这里改造主要考虑替换BitArray实现。这里主要贴出一些主要的代码。

#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实现一个基于redis版本的Bloomfilter. 后续通过增加BitArray的实现可以替换成任意实现。

示例

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

    }

具体的使用和实现可见https://github.com/ttting/redis-bloomfilter