乐趣区

关于布隆过滤器:布隆过滤器-与-Redis-BitMap

jiezi

1. 前言

在前些年的开发中就遇到几个相似的场景：

场景 1

场景：我以后业务表构造冗余了人员的信息字段，当人员的根本信息产生变更或删除时，会推送 MQ。我以后业务监听到有人员信息变更的 MQ 音讯，会查数据库，看看该人员在以后表中是否存在。如果存在则更新，如果不存在则无需解决。

问题：每当监听到人员变更的的 MQ 音讯，就须要查问表中是否存在，给数据库带来耗费。

尝试计划：将以后表中的所有人员 ID，存入 redis Set 汇合中。在监听到人员变更的 MQ 音讯时，先去 Set 中检查一下是否存在。如果存在再去更新数据库。

尝试计划的问题：当人员数量几十万的时候，redis Set 汇合也会很大，redis key 太大影响性能，检查人员是否存在也会变慢。

场景 2

咱们有些高频调用的查问接口，因为调用频率高，查库简单，因而曾经做了缓存。缓存的策略是：如果查问对应的缓存 key 存在，则从缓存获取；如果不存在，则在查库，如果查库能取得有效值，再将后果存入缓存。

带来的问题：接口对外裸露后，因为前台调用方不可控，可能总会查问不存在的 key。造成缓存穿透，频繁的有效查库。

尝试计划：针对缓存穿透，当查问某个 key，在库中不存在时。在缓存中仍然创立一个 key，value 设为 null。

尝试计划的问题：设为 null 的 key，就只有等过期工夫到了后，自行删除。有些时候上一秒查库不存在，给对应的 key 缓存了一个为 null 的 value。但下一秒库中有了，走缓存拿到的仍然是 null。

更好的解决方案

对于下面可能遇到的问题，和尝试的解决方案，有一个更好的解决方案：布隆过滤器。

能够了解为场景 1 外面的那个 Set，只不过容量更小，检索性能更高。那么针对场景 2 缓存穿透的问题，将所有的缓存 key 存入布隆过滤器中，如果在过滤器中的 key，再通过缓存、数据库获取。

2. 布隆过滤器

布隆过滤器（Bloom Filter）是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。次要用于判断一个元素是否在一个汇合中。

通常咱们会遇到很多要判断一个元素是否在某个汇合中的业务场景，个别想到的是将汇合中所有元素保存起来，而后通过比拟确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。然而随着汇合中元素的减少，咱们须要的存储空间也会出现线性增长，最终达到瓶颈。同时检索速度也越来越慢。上述三种构造的检索工夫复杂度别离为：

  • O(n)：链表
  • O(logn)：树
  • O(1)：哈希表

这个时候，布隆过滤器（Bloom Filter）就应运而生。

2.1. 原理

当一个元素被退出汇合时，通过 N 个 Hash 函数将这个元素进行 Hash，算出一个整数索引值，而后对数组长度进行取模运算，从而失去一个地位，每个 Hash 函数都会失去一个不同的地位，而后再把位数组中的几个地位点都置为 1。

检索时，也会把哈希的几个地位算进去，而后看看位数组中对应的几个地位是否都为 1，只有有一个位为 0，那么就阐明布隆过滤器里不存在这个元素。

然而，这几个地位都为 1，并不能齐全阐明这个元素就肯定存在其中。因为散列函数是会有碰撞的，不同的输出，可能在哈希后为同一个地位。即有可能这些地位为 1 是因为其余元素的存在，这就是布隆过滤器会呈现误判的起因。

因而查问某个变量的时候咱们只有看看这些点是不是都是 1 就能够大概率晓得汇合中有没有它了

  • 如果这些点有任何一个 0，则被查问变量肯定不在。
  • 如果都是 1，则被查问变量很可能存在。

2.2. 个性与优缺点

1. 不存在时肯定不存在

一个元素如果判断后果为存在的时候元素不肯定存在，然而判断后果为不存在的时候则肯定不存在。

起因：布隆过滤器的误判是指多个输出通过哈希之后，在雷同的 bit 位的值置 1 了，这样就无奈判断到底是哪个输出产生的，因而误判的本源在于雷同的 bit 位被屡次映射且置 1。

2. 只增不删

布隆过滤器能够增加元素，然而不能删除元素。因为删掉元素会导致误判率减少。

起因：上述起因中的状况，多个输出通过哈希之后，在雷同的 bit 位的值置 1 了，也造成了布隆过滤器的删除问题。因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。如果咱们间接删除这一位的话，会影响其余的元素。

如果须要删除一批元素，能够思考从新初始化一个布隆过滤器，替换原来的。

3. 长处

  • 占用空间极小，插入和查问速度极快；
  • 布隆过滤器能够示意选集，其它任何数据结构都不能；

3. 毛病

  • 误算率随着元素的减少而减少；
  • 个别状况下无奈删除元素；

2.3. 利用场景

基于上述的性能，咱们大抵能够把布隆过滤器用于以下的场景之中：

1. 大数据判断是否存在来实现去重

这就能够实现出上述的去重性能，如果你的服务器内存足够大的话，那么应用 HashMap 可能是一个不错的解决方案，实践上工夫复杂度能够达到 O(1) 的级别，然而当数据量起来之后，还是只能思考布隆过滤器。

2. 判断用户是否拜访过

判断用户是否浏览过某视频或文章，比方抖音或头条，当然会导致肯定的误判，但不会让用户看到反复的内容。

3. 爬虫 / 邮箱等零碎的过滤

平时不晓得你有没有留神到有一些失常的邮件也会被放进垃圾邮件目录中，这就是应用布隆过滤器误判导致的。

4. 人造适宜缓存穿透场景

布隆过滤器人造就能应答缓存穿透的场景。

首先，布隆过滤器的利用策略正好和缓存是相同的：

  • 缓存策略：缓存中不存在的，再去查 db。
  • 布隆过滤器策略：过滤器中存在的，再去查缓存（db）。

而后，因为它的个性：一个元素如果判断后果为存在的时候元素不肯定存在，然而判断后果为不存在的时候则肯定不存在。

这表明它的误判率并不影响它的策略：

  • 当判断后果为存在时：不肯定存在。带来的不好的后果，顶多就是多查一次缓存。
  • 当判断后果为不存在时：肯定不存在。策略中判断不存在时，以后申请就会被拦挡，这方面是没有误判的。

所以说，布隆过滤器人造适宜缓存穿透的场景，它的误判率对与该场景没有丝毫影响。

2.4. 实现

有很多布隆过滤器的实现，就如同之前将限流器的实现有 guava 和 redisson，布隆过滤器的实现也一样。

上面两种实现形式十分相似，都会初始化两个参数：

  • 初始容量：当理论元素的数量超过这个初始化容量时，误判率回升。设置的过大，会节约存储空间，设置的过小，就会影响准确率，所以在应用之前肯定要尽可能地准确预计好元素数量，还须要加上肯定的冗余空间以防止理论元素可能会意外高出设置值很多。
  • 冀望错误率：冀望错误率越低，须要的空间就越大。错误率越小，须要的存储空间就越大，对于不须要过于准确的场景，错误率设置稍大一点也能够。

2.4.1. guava

1. pom

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>23.0</version>
</dependency>

2. main

    private static String STR_1="str_1";
    private static String STR_2="str_2";
    private static String STR_101="str_101";

    public static void main(String[] args) {BloomFilter<String> bloomFilter=BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),10000,0.0001);
        for (int i = 0; i < 100; i++) {bloomFilter.put("str_" + i);
        }
        log.info("{}是否存在：{}",STR_1,bloomFilter.mightContain(STR_1));
        log.info("{}是否存在：{}",STR_2,bloomFilter.mightContain(STR_2));
        log.info("{}是否存在：{}",STR_101,bloomFilter.mightContain(STR_101));
    }

执行后返回的后果是：

23:30:45.960 [main] INFO pers.kerry.redislimitservice.controller.DemoController - str_1 是否存在：true
23:30:45.965 [main] INFO pers.kerry.redislimitservice.controller.DemoController - str_2 是否存在：true
23:30:45.966 [main] INFO pers.kerry.redislimitservice.controller.DemoController - str_101 是否存在：false

Guava 提供的布隆过滤器的实现还是很不错的，然而它有一个重大的缺点就是只能单机应用（另外，容量扩大也不容易），而当初互联网个别都是分布式的场景。为了解决这个问题，咱们就须要用到 Redis 中的布隆过滤器了。

2.4.2. redisson

1. pom

        <dependency>
            <groupId>org.redisson</groupId>
            <artifactId>redisson-spring-boot-starter</artifactId>
            <version>3.15.5</version>
        </dependency>

2. application

spring:
  redis:
    redisson:
      config:
        singleServerConfig:
          address: redis://127.0.0.1:6379
          database: 0

3. controller

    @GetMapping("bloom-filter")
    public boolean bloomFilter(String str) {RBloomFilter<String> bloomFilter = redissonClient.getBloomFilter("bloom:filter:test1");
        bloomFilter.tryInit(10000, 0.0001);
        for (int i = 0; i < 100; i++) {bloomFilter.add("str_" + i);
        }
        return bloomFilter.contains(str);
    }

3. Redis BitMap

上述讲到 Redisson 基于布隆过滤器的实现，实质上是 redis 反对了布隆过滤器，这里就要讲到 redis 的 BitMap 构造。

redis BitMap 并不作为 redis 根底数据类型，redis 的根本数据类型只有 5 种：string、list、set、zset、hash。

而 BitMap 就是基于 SDS（Simple Dynamic String，简略动静字符串）实现的，所以针对 BitMap Key 的名称执行 TYPE KEY_NAME 命令时，返回的是 string。

因而，咱们在讲 BitMap 数据结构之前，先讲一下 SDS。

3.1. SDS 字符串

1. 数据结构

SDS 的数据结构定义为：

struct sdshdr {

    unsigned int len;

    unsigned int free;

    char buf[];};
  • len：记录 buf 数组中已应用字节的数量，即等于 SDS 所保留字符串的长度。
  • free：记录 buf 数组中未应用字节的数量
  • buf：char 数组，用于保留理论字符串数据，留神数组开端总会保留一个空字符串 ’\0’。

2. 着重介绍一下 buf

它是 char 数组，char 是 C 语言中的字符类型，占 1 个字节（Byte），即 8 个位（Bit）。

buf 尾部主动追加一个 ’\0’ 字符并不会计算在 SDS 的 len 中，这是为了遵循 C 字符串以空字符串结尾的常规，使得 SDS 能够间接应用一部分 string.h 库中的函数，如 strlen。

3. SDS 长处

SDS 具备以下长处，但这里就不开展了。这里就简略列一下，可前期专门看这方面的材料：

  • 常数复杂度获取字符串长度。
  • 杜绝缓冲区溢出。
  • 缩小批改字符串长度时所需的内存重调配次数。
  • 二进制平安。
  • 兼容局部 C 字符串函数。

3.2. BitMap 位图

在简略理解 SDS 的数据结构后，就比拟不便了解 BitMap 了。

如果咱们须要记录某一用户在一年中每天是否有登录咱们的零碎这一需要该如何实现呢？如果应用 KV 存储，每个用户须要记录 365 个，当用户量上亿时，这所须要的存储空间是惊人的。

Redis 为咱们提供了 BitMap 位图这一数据结构，每个用户每天的登录记录只占据一位，365 天就是 365 位。8 位（Bit）1 个字节（Byte），因而仅仅须要 46 字节就可存储，极大地节约了存储空间。

BitMap 简称位图，是由多个二进制位组成的数组，数组中的每个二进制位都有与之对应的偏移量，能够通过这些偏移量对位图中指定的一个或多个二进制位进行操作。

1. 命令

Redis 提供了 SETBIT、GETBIT、BITCOUNT、BITOP 四个常用命令用于解决二进制位数组。

  • SETBIT：为位数组指定偏移量上的二进制位设置值，偏移量从 0 开始计数，二进制位的值只能为 0 或 1。返回原地位值。
  • GETBIT：获取指定偏移量上二进制位的值。
  • BITCOUNT：统计位数组中值为 1 的二进制位数量。
  • BITOP：对多个位数组进行按位与、或、异或运算。

最罕用的两个命令 setbit、getbit 执行的复杂度都是 O(1)，算是拿空间换工夫的做法。

2. 数据结构

BitMap 是基于 SDS 实现的，所以说数据结构上一样。还记得之前 SDS 的数据结构中，buf 是一个 char 字节数组吧，数组中每个元素 char 有 8 个位，每个位中就能够存储咱们 BitMap 中的数据。

gitbit 命令的源码如下：

void getbitCommand(client *c) {
    robj *o;
    char llbuf[32];
    uint64_t bitoffset;
    size_t byte, bit;
    size_t bitval = 0;
    // 获取 offset
    if (getBitOffsetFromArgument(c,c->argv[2],&bitoffset,0,0) != C_OK)
        return;
    // 查找对应的位图对象
    if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL ||
        checkType(c,o,OBJ_STRING)) return;
  // 计算 offset 位于位数组的哪一行
    byte = bitoffset >> 3;
    // 计算 offset 在一行中的第几位，等同于取模
    bit = 7 - (bitoffset & 0x7);
    // #define sdsEncodedObject(objptr) (objptr->encoding == OBJ_ENCODING_RAW || objptr->encoding == OBJ_ENCODING_EMBSTR)
    if (sdsEncodedObject(o)) {
        // SDS 是 RAW 或者 EMBSTR 类型
        if (byte < sdslen(o->ptr))
            // 获取指定地位的值
            // 留神它不是真正的一个二维数组不能用 ((uint8_t*)o->ptr)[byte][bit] 去获取呀~
            bitval = ((uint8_t*)o->ptr)[byte] & (1 << bit);
    } else {
        //  SDS 是 REDIS_ENCODING_INT 类型的整数，先转为 String
        if (byte < (size_t)ll2string(llbuf,sizeof(llbuf),(long)o->ptr))
            bitval = llbuf[byte] & (1 << bit);
    }

    addReply(c, bitval ? shared.cone : shared.czero);
}

getbit 命令的执行过程如下：

  1. 计算 byte=offset/8，byte 值示意指定的 offset 位于位数组的哪个字节(计算在第几行)；
  2. 指定 buf[i] 中的 i 了，接下来就要计算在 8 个字节中的第几位呢？应用 bit=(offset mod 8)+1 计算可得；
  3. 依据 byte 和 bit 在位数组中定位到目标值返回即可。

以 GETBIT array 3 为例，array 示意上图中三个字节的位数组。

  1. byte=[3/8] 失去值为 0，阐明在 buf[0] 上
  2. bit=(3 mod 8)+1 失去值为 4
  3. 定位到 buf[0] 字节的从左至右第 4 个地位上

援用：

  • 敖丙：Redis 源码之 BitMap
退出移动版