5

基于redis实现分布式bloomfilter

 3 years ago
source link: https://www.zhyea.com/2021/09/04/redis-distributed-bloomfilter.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
  • 当前位置 : 
  • ZY笔记
  • /Java /
  • 基于redis实现分布式bloomfilter

基于redis实现分布式bloomfilter

2021年9月4日 作者：白42

如果想要判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。链表，树等等数据结构都是这种思路. 但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢(O(n),O(logn))。不过世界上还有一种叫作散列表（又叫哈希表，Hash table）的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列（Bit array）中的一个点。这样一来，我们只要看看这个点是不是1就可以知道集合中有没有它了。这就是布隆过滤器的基本思想。

Hash面临的问题就是冲突。假设Hash函数是良好的，如果我们的位阵列长度为m个点，那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳m / 100个元素。显然这就不叫空间效率了（Space-efficient）了。解决方法也简单，就是使用多个Hash，如果检查到一个元素不在集合中，那肯定就不在。如果计算到在集合中，虽然也有一定的错误率，但是错误率还是比较低的。

以上内容来自百度百科《布隆过滤器》词条，阐述了bloomfilter的基础原理。BloomFilter常被用于需要唯一性校验的场景，如爬虫等。

java中有许多bloomfilter的实现包，最常用的还是guava中的BloomFilter。但是现在的应用多存在分布式部署的现象，本地的BloomFilter实现已经不能满足需求了，我们需要一个分布式BloomFilter实现。redis的Bitmap是实现分布式BloomFilter的一个好基础。

首先，我们需要计算一个字符串的不同Hash值的方案，这里准备了一个BloomFilterHelper类：

import org.apache.commons.codec.digest.MurmurHash3;
public class BloomFilterHelper {
    private final int bitSize;
    private final int numHashFunctions;
    public BloomFilterHelper(int expectedInsertions, double fpp) {
        // 计算bit数组长度
        bitSize = optimalNumOfBits(expectedInsertions, fpp);
        // 计算hash方法执行次数
        numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize);
     * 计算offset
    public int[] murmurHashOffset(String value) {
        int[] offset = new int[numHashFunctions];
        long hash64 = hash64(value);
        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)));
     * 执行hash64运算
     * @param value 值
     * @return hash计算结果
    private long hash64(String value) {
        long[] result = MurmurHash3.hash128x64(value.getBytes());
        return result[0];

BloomFilterHelper类的构造器需要传入两个参数：expectedInsertions 和 fpp。

  • expectedInsertions ： 预期写入的字符串总数
  • fpp ：误判率

误判率当然是越低越好，但是也意味着要为存储的数据准备更多的空间，但redis的Bitmap天然是有上限的，因此需要根据实际情况做最优设计。

另外，这里使用了commons-codec这个包来计算字符串的hash值。采用的是Murmur hash64计算。

然后是向redis的Bitmap中写入相应信息：

    public void multiSetBit(final String key, boolean value, int... offsets) {
        redisTemplate.executePipelined((RedisCallback<Object>) connection -> {
            byte[] bytes = key.getBytes();
            for (long offset : offsets) {
                connection.setBit(bytes, offset, value);
            return null;

最后是要验证字符串对应的offset是否在Bitmap中。下面是从Bitmap中取值的代码：

    public List<Boolean> multiGetBit(String name, int... offsets) {
        List<Object> results = redisTemplate.executePipelined((RedisCallback<Object>) connection -> {
            for (long offset : offsets) {
                connection.getBit(name.getBytes(), offset);
            return null;
        List<Boolean> list = new LinkedList<>();
        results.forEach(obj -> list.add((Boolean) obj));
        return list;

以及相应的校验代码：

    public boolean check0(String key, int[] offsets) {
        List<Boolean> list = redisClient.multiGetBit(key, offsets);
        for (Boolean b : list) {
            if (!b) {
                return false;
        return true;
    public boolean checkAndSet(String value) {
        String key = new SimpleDateFormat("yyyyMMdd").format(new Date());
        long ttl = redisClient.ttl(key, TimeUnit.MILLISECONDS);
        if (ttl < 0) {
            redisClient.expire(key, 1, TimeUnit.DAYS);
        int[] offsets = bloomFilterHelper.murmurHashOffset(value);
        boolean r = check0(key, offsets);
        redisClient.multiSetBit(key, true, offsets);
        return r;

大体上就是这些内容了。

完整代码在GitHub：zhyea / springboot-redis。

发表评论 取消回复

评论

名称(必填)

邮箱(必填)

网址

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK