为什么要使用布隆过滤器？

布隆过滤器（bloomfilter）有两大作用，一是为了防止缓存穿透，二是为了在百万级数据里快速高效的去重

什么是布隆过滤器？

1，布隆过滤器是用来判断一个元素是否出现在给定集合中的重要工具，具有快速，比哈希表更节省空间等优点，而缺点在于有一定的误识别率（false-positive，假阳性），亦即，它可能会把不是集合内的元素判定为存在于集合内，不过这样的概率相当小，在大部分的生产环境中是可以接受的；
2，其原理比较简单，假设S集合中有n个元素，利用k个哈希函数，将S中的每个元素映射到一个长度为m的位（bit）数组B中不同的位置上，这些位置上的二进制数均置为1，如果待检测的元素经过这k个哈希函数的映射后，发现其k个位置上的二进制数不全是1那么这个元素一定不在集合S中，反之，该元素可能是S中的某一个元素；
3，综上描述，那么到底需要多少个哈希函数，以及创建长度为多少的bit数组比较合适，为了估算出k和m的值，在构造一个布隆过滤器时，需要传入两个参数，即可以接受的误判率fpp和元素总个数n（不一定完全精确)；
4，哈希函数的要求尽量满足平均分布，这样既降低误判发生的概率，又可以充分利用bit数组的空间；

google guava的布隆过滤器

Guava中，布隆过滤器的实现主要涉及到2个类，BloomFilter和BloomFilterStrategies，首先来看一下BloomFilter：

 /** The bit set of the BloomFilter (not necessarily power of 2!) */private final BitArray 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;

这是它的4个成员变量：

1，BitArrays是定义在BloomFilterStrategies中的内部类，封装了布隆过滤器底层bit数组的操作，后文详述；
2，numHashFunctions表示哈希函数的个数，即上文提到的k；
3，Funnel，这是Guava中定义的一个接口，它和PrimitiveSink配套使用，主要是把任意类型的数据转化成Java基本数据类型（primitive value，如char，byte，int……），默认用java.nio.ByteBuffer实现，最终均转化为byte数组；
4，Strategy是定义在BloomFilter类内部的接口，代码如下，有3个方法，put（插入元素），mightContain（判定元素是否存在）和ordinal方法（可以理解为枚举类中那个默认方法）

interface Strategy extends java.io.Serializable {/*** Sets {@code numHashFunctions} bits of the given bit array, by hashing a user element.** <p>Returns whether any bits changed as a result of this operation.*/<T> boolean put(T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits);/*** Queries {@code numHashFunctions} bits of the given bit array, by hashing a user element;* returns {@code true} if and only if all selected bits are set.*/<T> boolean mightContain(T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits);/*** Identifier used to encode this strategy, when marshalled as part of a BloomFilter. Only* values in the [-128, 127] range are valid for the compact serial form. Non-negative values* are reserved for enums defined in BloomFilterStrategies; negative values are reserved for any* custom, stateful strategy we may define (e.g. any kind of strategy that would depend on user* input).*/int ordinal();}

对于创建布隆过滤器，BloomFilter并没有公有的构造函数，只有一个私有构造函数，而对外它提供了5个重载的create方法，在缺省情况下误判率设定为3%，采用BloomFilterStrategies.MURMUR128_MITZ_64的实现。其中4个create方法最终都调用了同一个create方法，由它来负责调用私有构造函数，其源码如下：

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 BitArray(numBits), numHashFunctions, funnel, strategy);} catch (IllegalArgumentException e) {throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e);}}

在create中接受了4个参数，funnel（输入的数据），expectedInsertions（预计插入的元素总数），fpp（期望误判率），strategy（实现Strategy的实例），然后它计算了bit数组的长度以及哈希函数的个数（公式参考前文），最后用numBits创建了BitArray，并调用了构造函数完成赋值操作

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

接着再来看一下BloomFilterStrategies类，首先它是实现了BloomFilter.Strategy 接口的一个枚举类，其次它有两个2枚举值，MURMUR128_MITZ_32和MURMUR128_MITZ_64，分别对应了32位哈希映射函数，和64位哈希映射函数，后者使用了murmur3 hash生成的所有128位，具有更大的空间，不过原理是相通的，我们选择默认的MURMUR128_MITZ_64来分析：

MURMUR128_MITZ_64() {@Overridepublic <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 indexablebitsChanged |= bits.set((combinedHash & Long.MAX_VALUE) % bitSize);combinedHash += hash2;}return bitsChanged;}@Overridepublic <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 indexableif (!bits.get((combinedHash & Long.MAX_VALUE) % bitSize)) {return false;}combinedHash += hash2;}return true;}

抽象来看，put是写，mightContain是读，两个方法的代码有一点相似，都是先利用murmur3 hash对输入的funnel计算得到128位的字节数组，然后高低分别取8个字节（64位）创建2个long型整数hash1，hash2作为哈希值。循环体内采用了2个函数模拟其他函数的思想，即上文提到的gi(x) = h1(x) + ih2(x) ，这相当于每次累加hash2，然后通过基于bitSize取模的方式在bit数组中索引。

这里之所以要和Long.MAX_VALUE进行按位与的操作，是因为在除数和被除数符号不一致的情况下计算所得的结果是有差别的，在程序语言里，“%”准确来说是取余运算（C，C++和Java均如此，python是取模），如-5%3=-2，而取模的数学定义是x
mod y=x-y[x/y]（向下取整），所以-5 mod 3=
-5-3*(-2)=1，因此当哈希值为负数的时候，其取余的结果为负（bitSize始终为正数），这样就不方便在bit数组中取值，因此通过Long.MAX_VALUE(二进制为0111…1111)，直接将开头的符号位去掉，从而转变为正数。当然也可以取绝对值，在另一个MURMUR128_MITZ_32的实现中就是这么做的。

在put方法中，先是将索引位置上的二进制置为1，然后用bitsChanged记录插入结果，如果返回true表明没有重复插入成功，而mightContain方法则是将索引位置上的数值取出，并判断是否为0，只要其中出现一个0，那么立即判断为不存在。

 static final class BitArray {final long[] data;long bitCount;BitArray(long bits) {this(new long[Ints.checkedCast(LongMath.divide(bits, 64, RoundingMode.CEILING))]);}// Used by serializationBitArray(long[] data) {checkArgument(data.length > 0, "data length is zero!");this.data = data;long bitCount = 0;for (long value : data) {bitCount += Long.bitCount(value);}this.bitCount = bitCount;}/** Returns true if the bit changed value. */boolean set(long index) {if (!get(index)) {data[(int) (index >>> 6)] |= (1L << index);bitCount++;return true;}return false;}boolean get(long index) {return (data[(int) (index >>> 6)] & (1L << index)) != 0;}/** Number of bits */long bitSize() {return (long) data.length * Long.SIZE;}
...
}

之前也提到了Guava没有使用java.util.BitSet，而是封装了一个long型的数组，另外还有一个long型整数，用来统计数组中已经占用（置为1）的数量，在第一个构造函数中，它把传入的long型整数按长度64分段（例如129分为3段），段数作为数组的长度，你可以想象成由若干个64位数组拼接成一个超长的数组，它的长度就是64乘以段数，即bitSize，在第二个构造函数中利用Long.bitCount方法来统计对应二进制编码中的1个数，这个方法在JDK1.5中就有了，其算法设计得非常精妙，有精力的同学可以自行研究。

另外两个重要的方法是set和get，在get方法中，参考put和mightContain方法，传入的参数index是经过bitSize取模的，因此一定能落在这个超长数组的范围之内，为了获取index对应索引位置上的值，首先将其无符号右移6位，并且强制转换成int型，这相当于除以64向下取整的操作，也就是换算成段数，得到该段上的数值之后，又将1左移index位，最后进行按位与的操作，如果结果等于0，那么返回false，从而在mightContain中判断为不存在。在set方法中，首先调用了get方法判断是否已经存在，如果不存在，则用同样的逻辑取出data数组中对应索引位置的数值，然后按位或并赋值回去。

到这里，对Guava中布隆过滤器的实现就基本讨论完了，简单总结一下：

1，BloomFilter类的作用在于接收输入，利用公式完成对参数的估算，最后初始化Strategy接口的实例；
2，BloomFilterStrategies是一个枚举类，具有两个实现了Strategy接口的成员，分别为MURMUR128_MITZ_32和MURMUR128_MITZ_64，另外封装了long型的数组作为布隆过滤器底层的bit数组，其中在get和set方法中完成核心的位运算。

使用Redis整合BloomFilter

前面说的BloomFilter算法是单机的，可以使用JDK自带的BitSet来实现。但是拥有大数据量的系统绝不是一台服务器，所以需要多台服务器共享。结合Redis的BitMap就能够完美的实现这一需求。利用redis的高性能以及通过pipeline将多条bit操作命令批量提交，实现了多机BloomFilter的bit数据共享。唯一需要注意的是redis的bitmap只支持2^{32大小，对应到内存也就是512MB,数组的下标最大只能是2}32-1。不过这个限制我们可以通过构建多个redis的bitmap通过hash取模的方式分散一下即可。万分之一的误判率，512MB可以放下2亿条数据。
直接上代码：

BloomFilterHelper

import com.google.common.base.Preconditions;
import com.google.common.hash.Funnel;
import com.google.common.hash.Hashing;/*** @author shihaowei* @date 2020/8/7 3:33 下午*/
public class BloomFilterHelper<T> {private int numHashFunctions;private int bitSize;private Funnel<T> funnel;public BloomFilterHelper(Funnel<T> funnel, int expectedInsertions, double fpp) {Preconditions.checkArgument(funnel != null, "funnel不能为空");this.funnel = funnel;bitSize = optimalNumOfBits(expectedInsertions, fpp);numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize);}public int[] murmurHashOffset(T value) {int[] offset = new int[numHashFunctions];long hash64 = Hashing.murmur3_128().hashObject(value, funnel).asLong();int hash1 = (int) hash64;int hash2 = (int) (hash64 >>> 32);for (int i = 1; i <= numHashFunctions; i++) {int nextHash = hash1 + i * hash2;if (nextHash < 0) {nextHash = ~nextHash;}offset[i - 1] = nextHash % bitSize;}return offset;}/*** 计算bit数组的长度*/private int optimalNumOfBits(long n, double p) {if (p == 0) {p = Double.MIN_VALUE;}return (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));}/*** 计算hash方法执行次数*/private int optimalNumOfHashFunctions(long n, long m) {return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));}
}

BloomFilterCache

/*** @author shihaowei* @date 2020/8/7 3:41 下午*/
@Component
public class BloomFilterCache {private static final Logger LOG = LoggerFactory.getLogger(BloomFilterCache.class);private static final Integer PIPLINE_LIST_LEN = 1000;@Resource(name = "jedisTemplate")private JedisTemplate jedisTemplate;/*** 根据给定的布隆过滤器添加值** @param bloomFilterHelper* @param key* @param value* @param <T>*/public <T> void addByBloomFilter(BloomFilterHelper<T> bloomFilterHelper, String key, T value) {if (value == null) {return;}Preconditions.checkArgument(bloomFilterHelper != null, "bloomFilterHelper不能为空");int[] offset = bloomFilterHelper.murmurHashOffset(value);for (int i : offset) {jedisTemplate.execute(s -> {s.setbit(key, i, true);});}}/*** 根据给定的布隆过滤器批量添加值** @param bloomFilterHelper* @param key* @param values* @param <T>*/public <T> void addByBloomFilter(BloomFilterHelper<T> bloomFilterHelper, String key, List<T> values) {if (values.size() < 1) {return;}Preconditions.checkArgument(bloomFilterHelper != null, "bloomFilterHelper不能为空");List<List<T>> subList = getSubList(values, PIPLINE_LIST_LEN);jedisTemplate.execute(jedis -> {subList.stream().forEach(s -> {// 通过管道异步添加数据Pipeline p = jedis.pipelined();s.stream().forEach(h -> {int[] offset = bloomFilterHelper.murmurHashOffset(h);for (int i : offset) {p.setbit(key, i, true);}});p.sync();});});}/*** 根据给定的布隆过滤器判断值是否存在*/public <T> boolean includeByBloomFilter(BloomFilterHelper<T> bloomFilterHelper, String key, T value) {Preconditions.checkArgument(bloomFilterHelper != null, "bloomFilterHelper不能为空");int[] offset = bloomFilterHelper.murmurHashOffset(value);for (int i : offset) {boolean flag = jedisTemplate.execute(s -> {return s.getbit(key, i);});if (!flag) {return false;}}return true;}/*** 删除过滤key** @param key*/public void removeByBloomFilter(String key) {jedisTemplate.key().del(key);}/*** 拆分list队列** @param list* @param len* @param <T>* @return*/private <T> List<List<T>> getSubList(List<T> list, Integer len) {if (list == null || list.size() == 0 || len < 1) {return null;}List<List<T>> resultList = new ArrayList<>();for (int i = 0; i < list.size(); i++) {if (i % len == 0) {int count = i / len;List<T> subList = list.stream().limit((count + 1) * len).skip(count * len).collect(Collectors.toList());resultList.add(subList);}}return resultList;}
}

测试

@Test(priority = 10, testName = "测试布隆过滤器")public void testBloomFilterCache(){BloomFilterHelper<String> bloomFilterHelper = new BloomFilterHelper((Funnel<String>)(from,into) ->into.putString(from, Charsets.UTF_8),150000,0.00001);bloomFilterCache.addByBloomFilter(bloomFilterHelper,"app_bloomfilter_key","aaaaa");boolean a = bloomFilterCache.includeByBloomFilter(bloomFilterHelper, "app_bloomfilter_key", "aaaaa");System.out.println("aaaaa ======>"+a);boolean b = bloomFilterCache.includeByBloomFilter(bloomFilterHelper, "app_bloomfilter_key", "bbbbb");System.out.println("bbbbb ======>"+b);}