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