BitArrays 是定义在BloomFilterStrategies中的内部类,封装了布隆过滤器底层bit数组的操作。
numHashFunctions表示哈希函数的个数,即上文公式提到的k。
Funnel主要是把任意类型的数据转化成Java基本数据类型(primitive value,如char,byte,int……),默认用java.nio.ByteBuffer实现,最终均转化为byte数组。
Strategy是定义在BloomFilter类内部的接口,代码如下,有3个方法,put(插入元素),mightContain(判定元素是否存在)和ordinal方法(可以理解为枚举类中那个默认方法)。
BloomFilterStrategies类,首先它是实现了BloomFilter.Strategy 接口的一个枚举类,其次它有两个2枚举值,MURMUR128_MITZ_32和MURMUR128_MITZ_64,分别对应了32位哈希映射函数和64位哈希映射函数,后者使用了murmur3 hash可生成128位哈希值,具有更大的空间,不过原理是相通的。
MURMUR128_MITZ_64实现原理可以参考()。
BitArray是guava bloom filter底层bit数组的一个实现类。Guava使用的是一个long型数组实现了类似BitSet的数据结构。第一个构造函数传入了一个bit位的位数bits,然后bits除以64并向上取整得到long型数组的大小。get和set操作根据bit位的索引index,找到对应的操作对象data[index >>> 6](等价于data[index / 64]),分别跟(1L << index)与操作和或操作相应的结果。
Redis Bloom Filter分布式系统直接使用guava bloom filter在某些业务场景下不是很方便,既然是分布式环境,最好还是通过分布式缓存封装一版布隆过滤器。
通过对guava bloom filter的分析,由单机版改造成分布式版,只需要重新实现三个guava bloom filter的三个类(BloomFilter,BloomFilterStrategies,BitArray)。
RedisBitArray改造不是很麻烦,只需要引入操作分布式缓存的JedisCluster对象就好了。get和set操作对应JedisCluster对象的getbit和setbit操作(针对String类型的值,Redis通过 位操作 实现了BitMap数据结构)。
BloomFilter和BloomFilterStrategies的改造相对比较简单,这里就不详细说明了。
Routing Bloom Filter为什么要有路由布隆过滤器?通过上面的公式可以知道,当要插入的样本数量n越大,那么需要分配的内存容量m也会越大。也就是布隆过滤器的不当使用极易产生大 Value,增加 内存溢出或者阻塞风险,因此生成环境中建议对体积庞大的布隆过滤器进行拆分,拆分的规则我们定义为按照一定的路由规则对应到不同的布隆过滤器。
(1) 设计方案