Redis布隆過濾器（Bloom Filter）

1. 概念

Bloom Filter可以理解為是一個m位的數(shù)組，它有k個相互獨立的哈希函數(shù)。每當新來一個元素時，會使用這些哈希函數(shù)分別計算，將對應位置置為1。查詢時也要進行k次哈希運算，如果對應的k個位置都為1，則表明元素可能存在。

Bloom Filter示意圖：
假如當前的過濾器中已經(jīng)記錄了1、10，此時判斷3是否存在，匹配之后發(fā)現(xiàn)并不存在



（圖中的方格就代表著數(shù)組，每個數(shù)字指向二位數(shù)組的線就代表一個哈希元素。）

注：布隆過濾器只能判斷某個值一定不存在，無法判斷某個值一定存在。

2. 具體使用

2.1 google.guava

Google在guava包中提供了一個布隆過濾器的實現(xiàn)——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>

首先在配置類中創(chuàng)建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

結(jié)果：

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的位集，也就是上文所說的數(shù)組 */
private final LockFreeBitArray bits;

/** 表示哈希函數(shù)的個數(shù) */
private final int numHashFunctions;

/** 把任意類型的數(shù)據(jù)轉(zhuǎn)換為Java基本數(shù)據(jù)類型，最終轉(zhuǎn)化為byte數(shù)組 */
private final Funnel<? super T> funnel;

/** 內(nèi)部接口，將元素T映射到numHashFunctions位索引的策略 */
private final Strategy strategy;

然后看一下4個構(gòu)造方法

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
}

四個構(gòu)造方法沒太大的區(qū)別，最后都會指向同一個create方法
這個方法中接收了4個參數(shù)：funnel（輸入的數(shù)據(jù)），expectedInsertions（預計插入的元素總數(shù)），fpp（期望誤判率），strategy（實現(xiàn)Strategy的實例，參考上面的公共構(gòu)造方法，默認傳遞的是BloomFilterStrategies.MURMUR128_MITZ_64）

@VisibleForTesting
static <T> BloomFilter<T> create(
    Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {
    //各種參數(shù)校驗
    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!
     */
    //計算數(shù)組長度
    long numBits = optimalNumOfBits(expectedInsertions, fpp);
    //計算出每個元素需要哈希方法的個數(shù)
    int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
    try {
      //創(chuàng)建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這個構(gòu)造方法，很簡單，檢查完了之后給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);
}

都是調(diào)用的成員變量strategy的方法，我們知道構(gòu)造函數(shù)的strategy的參數(shù)都是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位的字節(jié)數(shù)組，然后高低分別取8個字節(jié)（64位）創(chuàng)建2個long型整數(shù)hash1，hash2作為哈希值。循環(huán)體內(nèi)采用了2個函數(shù)模擬其他函數(shù)的思想，即上文提到的gi(x) = h1(x) + ih2(x) ，這相當于每次累加hash2，然后通過基于bitSize取模的方式在bit數(shù)組中索引。

這里之所以要和Long.MAX_VALUE進行按位與的操作，是因為在除數(shù)和被除數(shù)符號不一致的情況下計算所得的結(jié)果是有差別的，在程序語言里，“%”準確來說是取余運算（C，C++和Java均如此，python是取模），如-5%3=-2，而取模的數(shù)學定義是x mod y=x-y[x/y]（向下取整），所以-5 mod 3= -5-3*(-2)=1，因此當哈希值為負數(shù)的時候，其取余的結(jié)果為負（bitSize始終為正數(shù)），這樣就不方便在bit數(shù)組中取值，因此通過Long.MAX_VALUE(二進制為0111…1111)，直接將開頭的符號位去掉，從而轉(zhuǎn)變?yōu)檎龜?shù)。當然也可以取絕對值，在另一個MURMUR128_MITZ_32的實現(xiàn)中就是這么做的。

在put方法中，先是將索引位置上的二進制置為1，然后用bitsChanged記錄插入結(jié)果，如果返回true表明沒有重復插入成功，而mightContain方法則是將索引位置上的數(shù)值取出，并判斷是否為0，只要其中出現(xiàn)一個0，那么立即判斷為不存在。

這種使用方式屬于單機版的布隆過濾器的使用，在分布式場景下并不試用，所以需要redis來做一個分布式場景下的布隆過濾器

總結(jié)：

  1. BloomFilter類就是利用公式完成對參數(shù)的估算，創(chuàng)建了一個本地的BitArray數(shù)組（一個Long類型的數(shù)組，長度m）和需要哈希方法的次數(shù)k。
  2. 之后利用MURMUR128_MITZ_64這個枚舉值中的方法來進行運算，在put方法中，利用計算出來的k個數(shù)值。在BitArray中，以這k個數(shù)值為下標，將原有為0的值修改為1。
  3. mightContain方法中，跟put方法同理，計算出k個數(shù)值，在BitArray中判斷這些數(shù)值為下標的值是否為0，只要出現(xiàn)一個0則返回false。
  4. 僅適合一個節(jié)點的使用，因為分布式中每個節(jié)點的BloomFilter的bean都是獨立的。
2.3 利用Redis Bitmaps進行重構(gòu)

大致思路：創(chuàng)建一個新的BloomFilter，4個成員變量中，將Strategy這個變量改為使用Redis BitMap，其余的3個成員變量及計算方式保留。將MURMUR128_MITZ_64中的Hashing.murmur3_128()方法拿出來，得到計算出來的k個下標，之后循環(huán)這些下標將BitMap中的這些值修改為1。

了解下Redis Bitmaps的結(jié)構(gòu)，推薦一篇不錯的博客：https://www.cnblogs.com/54chensongxia/p/13794391.html

下面貼代碼。
首先創(chuàng)建一個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數(shù)組長度
        bitSize = optimalNumOfBits(expectedInsertions, fpp);
        // 計算hash方法執(zhí)行次數(shù)
        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數(shù)組長度
     * @param n 預計插入的元素總數(shù)
     * @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方法執(zhí)行次數(shù)
     * @param n 預計插入的元素總數(shù)
     * @param m bit數(shù)組長度
     * @return
     */
    private int optimalNumOfHashFunctions(long n, long m) {
        int countOfHash = Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
        return countOfHash;
    }
}

接下來就是初始化一個上面自己實現(xiàn)的布隆過濾器類的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;
    }
}

之后創(chuàng)建BloomFilterUtil（主要操作的類），利用BloomFilterHelper的murmurHashOffset計算出哈希方法的數(shù)組，循環(huán)數(shù)組以每個值為下標，將Redis BitMap中這些值設置為1。（我用的是jedis，具體方法不貼了網(wǎng)上有很多）

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

輸出結(jié)果：

13333333333是否存在：false
插入：13333333333
13333333334是否存在：false
插入：13333333334
13333333335是否存在：false
插入：13333333335
13333333336是否存在：false
插入：13333333336
13333333337是否存在：false
插入：13333333337
13333333335是否存在：true
13333333337是否存在：true
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容