Redis布隆过滤器（Bloom Filter）

1. 概念

Bloom Filter可以理解为是一个m位的数组，它有k个相互独立的哈希函数。每当新来一个元素时，会使用这些哈希函数分别计算，将对应位置置为1。查询时也要进行k次哈希运算，如果对应的k个位置都为1，则表明元素可能存在。

Bloom Filter示意图：
假如当前的过滤器中已经记录了1、10，此时判断3是否存在，匹配之后发现并不存在



（图中的方格就代表着数组，每个数字指向二位数组的线就代表一个哈希元素。）

注：布隆过滤器只能判断某个值一定不存在，无法判断某个值一定存在。

2. 具体使用

2.1 google.guava

Google在guava包中提供了一个布隆过滤器的实现——com.google.common.hash.BloomFilter
put(T object) //往布隆过滤器中存入object
mightContain(T object) //判断object是否存在

直接贴代码，首先是pom

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>30.1.1-jre</version>
</dependency>

首先在配置类中创建BloomFilter的Bean，方便注入引用

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;

import java.nio.charset.Charset;

@Configuration
public class GoogleBloomFilter {

    @Bean
    public BloomFilter<String> initBloomFilterHelper() {
        return BloomFilter.create(Funnels.stringFunnel(Charset.forName("utf-8")), 1000, 0.00001);
    }
}

模拟插入操作，如果存在则不插入。

@RestController
@RequestMapping("/bloom")
@AllArgsConstructor
public class RedisController {

    private final BloomFilter bloomFilter;

    @GetMapping("/string/add")
    public String redisString(String value){
        boolean isExist = bloomFilter.mightContain(value);
        System.out.println(value+ "是否存在：" + isExist);
        if (!isExist) {
            System.out.println("插入：" + value);
            bloomFilter.put(value);
        }
        return String.valueOf(isExist);
    }
}

测试用例：
13333333333
13333333334
13333333335
13333333336
13333333337
13333333335
13333333337

结果：

13333333333是否存在：false
插入：13333333333
13333333334是否存在：false
插入：13333333334
13333333335是否存在：false
插入：13333333335
13333333336是否存在：false
插入：13333333336
13333333337是否存在：false
插入：13333333337
13333333335是否存在：true
13333333337是否存在：true
2.2 google.guava的BloomFilter源码解析

首先看一下BloomFilter的成员变量

/** BloomFilter的位集，也就是上文所说的数组 */
private final LockFreeBitArray bits;

/** 表示哈希函数的个数 */
private final int numHashFunctions;

/** 把任意类型的数据转换为Java基本数据类型，最终转化为byte数组 */
private final Funnel<? super T> funnel;

/** 内部接口，将元素T映射到numHashFunctions位索引的策略 */
private final Strategy strategy;

然后看一下4个构造方法

public static <T> BloomFilter<T> create(
    Funnel<? super T> funnel, int expectedInsertions, double fpp) {
    return create(funnel, (long) expectedInsertions, fpp);
}

public static <T> BloomFilter<T> create(
    Funnel<? super T> funnel, long expectedInsertions, double fpp) {
    return create(funnel, expectedInsertions, fpp, BloomFilterStrategies.MURMUR128_MITZ_64);
}

public static <T> BloomFilter<T> create(Funnel<? super T> funnel, int expectedInsertions) {
    return create(funnel, (long) expectedInsertions);
}

public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) {
    return create(funnel, expectedInsertions, 0.03); // FYI, for 3%, we always get 5 hash functions
}

四个构造方法没太大的区别，最后都会指向同一个create方法
这个方法中接收了4个参数：funnel（输入的数据），expectedInsertions（预计插入的元素总数），fpp（期望误判率），strategy（实现Strategy的实例，参考上面的公共构造方法，默认传递的是BloomFilterStrategies.MURMUR128_MITZ_64）

@VisibleForTesting
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 {
      //创建BloomFilter对象
      return new BloomFilter<T>(new LockFreeBitArray(numBits), numHashFunctions, funnel, strategy);
    } catch (IllegalArgumentException e) {
      throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e);
    }
}

最后再看一下BloomFilter这个构造方法，很简单，检查完了之后给4个成员变量赋值

/** Creates a BloomFilter. */
private BloomFilter(
    LockFreeBitArray bits, int numHashFunctions, Funnel<? super T> funnel, Strategy strategy) {
    checkArgument(numHashFunctions > 0, "numHashFunctions (%s) must be > 0", numHashFunctions);
    checkArgument(
        numHashFunctions <= 255, "numHashFunctions (%s) must be <= 255", numHashFunctions);
    this.bits = checkNotNull(bits);
    this.numHashFunctions = numHashFunctions;
    this.funnel = checkNotNull(funnel);
    this.strategy = checkNotNull(strategy);
}

再看一下mightContain方法和put方法

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

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

都是调用的成员变量strategy的方法，我们知道构造函数的strategy的参数都是BloomFilterStrategies.MURMUR128_MITZ_64这个枚举值，贴一下代码

MURMUR128_MITZ_64() {
    @Override
    public <T> boolean put(
        T object, Funnel<? super T> funnel, int numHashFunctions, LockFreeBitArray 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;
    }

    @Override
    public <T> boolean mightContain(
        T object, Funnel<? super T> funnel, int numHashFunctions, LockFreeBitArray 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;
    }

抽象来看，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，那么立即判断为不存在。

这种使用方式属于单机版的布隆过滤器的使用，在分布式场景下并不试用，所以需要redis来做一个分布式场景下的布隆过滤器

总结：

  1. BloomFilter类就是利用公式完成对参数的估算，创建了一个本地的BitArray数组（一个Long类型的数组，长度m）和需要哈希方法的次数k。
  2. 之后利用MURMUR128_MITZ_64这个枚举值中的方法来进行运算，在put方法中，利用计算出来的k个数值。在BitArray中，以这k个数值为下标，将原有为0的值修改为1。
  3. mightContain方法中，跟put方法同理，计算出k个数值，在BitArray中判断这些数值为下标的值是否为0，只要出现一个0则返回false。
  4. 仅适合一个节点的使用，因为分布式中每个节点的BloomFilter的bean都是独立的。
2.3 利用Redis Bitmaps进行重构

大致思路：创建一个新的BloomFilter，4个成员变量中，将Strategy这个变量改为使用Redis BitMap，其余的3个成员变量及计算方式保留。将MURMUR128_MITZ_64中的Hashing.murmur3_128()方法拿出来，得到计算出来的k个下标，之后循环这些下标将BitMap中的这些值修改为1。

了解下Redis Bitmaps的结构，推荐一篇不错的博客：https://www.cnblogs.com/54chensongxia/p/13794391.html

下面贴代码。
首先创建一个BloomFilter类

import com.google.common.base.Preconditions;
import com.google.common.hash.Funnel;
import com.google.common.hash.Hashing;

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;
        // 计算bit数组长度
        bitSize = optimalNumOfBits(expectedInsertions, fpp);
        // 计算hash方法执行次数
        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数组长度
     * @param n 预计插入的元素总数
     * @param p 期望误判率
     * @return
     */
    private int optimalNumOfBits(long n, double p) {
        if (p == 0) {
            // 设定最小期望长度
            p = Double.MIN_VALUE;
        }
        int sizeOfBitArray = (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
        return sizeOfBitArray;
    }

    /**
     * 计算hash方法执行次数
     * @param n 预计插入的元素总数
     * @param m bit数组长度
     * @return
     */
    private int optimalNumOfHashFunctions(long n, long m) {
        int countOfHash = Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
        return countOfHash;
    }
}

接下来就是初始化一个上面自己实现的布隆过滤器类的bean

import com.google.common.base.Charsets;
import com.google.common.hash.Funnel;
import com.yyhd.redisdemo.filter.BloomFilterHelper;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;

@Configuration
public class GoogleBloomFilter {

    @Bean
    public BloomFilterHelper<String> initBloomFilterHelper() {
        BloomFilterHelper<String> bloomFilter = new BloomFilterHelper((Funnel<String>) (from, into) -> {
            into.putString(from, Charsets.UTF_8);
        }, 1000000, 0.0000001);
        return bloomFilter;
    }
}

之后创建BloomFilterUtil（主要操作的类），利用BloomFilterHelper的murmurHashOffset计算出哈希方法的数组，循环数组以每个值为下标，将Redis BitMap中这些值设置为1。（我用的是jedis，具体方法不贴了网上有很多）

import com.yyhd.redisdemo.filter.BloomFilterHelper;
import com.yyhd.redisdemo.util.RedisUtil;
import lombok.AllArgsConstructor;
import org.springframework.stereotype.Component;

@Component
@AllArgsConstructor
public class BloomFilterUtil {

    private final BloomFilterHelper bloomFilterHelper;
    private final RedisUtil redisUtil;

    public <T> void addBloomFilter(String key, T value) {
        int[] offset = bloomFilterHelper.murmurHashOffset(value);
        for (int i : offset) {
            redisUtil.setbit(key, i, true);
        }
    }

    public <T> boolean includeByBloomFilter(String key, T value) {
        int[] offset = bloomFilterHelper.murmurHashOffset(value);
        for (int i : offset) {
            if (!redisUtil.getbit(key, i)) {
                return false;
            }
        }
        return true;
    }
}

最后进行测试：

@RestController
@RequestMapping("/bloom")
@AllArgsConstructor
public class RedisController {

    private final BloomFilterUtil bloomFilterUtil;

    @GetMapping("/string/add")
    public String redisString(String value){
        boolean isExist = bloomFilterUtil.includeByBloomFilter("mobile", value);
        System.out.println(value+ "是否存在：" + isExist);
        if (!isExist) {
            System.out.println("插入：" + value);
            bloomFilterUtil.addBloomFilter("mobile", value);
        }

        return String.valueOf(isExist);
    }
}

测试用例：
13333333333
13333333334
13333333335
13333333336
13333333337
13333333335
13333333337

输出结果：

13333333333是否存在：false
插入：13333333333
13333333334是否存在：false
插入：13333333334
13333333335是否存在：false
插入：13333333335
13333333336是否存在：false
插入：13333333336
13333333337是否存在：false
插入：13333333337
13333333335是否存在：true
13333333337是否存在：true
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 214,658评论 6赞 496
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,482评论 3赞 389
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 160,213评论 0赞 350
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,395评论 1赞 288
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,487评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,523评论 1赞 293
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,525评论 3赞 414
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,300评论 0赞 270
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,753评论 1赞 307
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,048评论 2赞 330
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,223评论 1赞 343
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,905评论 5赞 338
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,541评论 3赞 322
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,168评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,417评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,094评论 2赞 365
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,088评论 2赞 352

推荐阅读更多精彩内容