Redis

Redis数据库——布隆过滤器(BloomFilter)

编程Cookbook

• 8 min read
Redis数据库——布隆过滤器(BloomFilter)

大家好，这里是编程Cookbook。本文详细介绍Redis的布隆过滤器，解决缓存穿透的原理，及其改进的计数型布隆过滤器。

布隆过滤器概述

布隆过滤器（Bloom Filter）是一种概率型数据结构，用于检测某个元素是否在一个集合中。其特点是能告诉你某个元素“一定不存在 或者 可能存在”于某个集合中。布隆过滤器实际上是由一个很长的二进制向量和多个随机映射函数构成：

二进制向量：由0和1组成，初始状态为0。

  • 0表示某元素一定不在集合中。
  • 1表示该元素可能在集合中。

用途

布隆过滤器广泛应用于需要高效处理大规模数据的场景，尤其是减少磁盘I/O或网络请求的场合。例如：

  • 网页 URL 去重：通过布隆过滤器检查网址是否已存在，若已存在则不再读取。
  • 垃圾邮件识别：通过发送方地址命中布隆过滤器的黑名单来过滤垃圾邮件。
  • 黑名单：用于检测某个元素是否在黑名单中。
  • 查询加速：尤其是基于键值对（KV）结构的数据查询。
  • 集合元素重复判断：判断一个元素是否已经出现。
  • Redis 缓存穿透问题：避免不必要的缓存查询。

原理

在常规的数据结构中，判断某个元素是否存在通常使用 HashMap，通过哈希函数将元素映射为键（key），再通过哈希表查询。HashMap 的时间复杂度是 O(1)，但其存储开销较大（尤其是在数据集很大时）。当数据集存储在远程服务器上时，内存限制使得 HashMap 不适用。

布隆过滤器采用的 K个哈希函数 能够通过映射一个元素到 位数组中的K个位置

布隆过滤器通过使用 K个哈希函数 和 长度为m的位数组 来判断一个元素是否属于某个集合。它的核心思想是将元素映射到位数组的多个位置，这些位置被置为1。查询时检查对应位置是否为1，若有任一位置为0，则该元素绝对不存在。如果所有位置都为1，元素可能存在，但不一定真实存在。由于映射点是共享的，多个元素可能覆盖相同的位，因此布隆过滤器可能会存在误报。

关键组件：

  • 位数组（Bit Array）：用于存储数据的位数组，所有位初始化为 0。每个元素通过哈希函数映射到位数组中的多个位置。
  • 哈希函数（Hash Functions）：布隆过滤器使用多个不同的哈希函数（通常是 k 个哈希函数）来对同一个元素进行哈希运算，得到多个不同的哈希值，这些值将指向位数组中的不同位置。

实现过程

插入元素

  1. 给定一个元素 x，使用 k 个哈希函数 H1(x), H2(x), ..., Hk(x) 计算出 k 个索引。
  2. 将这些哈希值映射到位数组中对应的位置，将该位置的位设置为 1。

查询元素的过程

  1. 给定一个元素 x，使用相同的 k 个哈希函数 计算出 k 个索引。
  2. 检查位数组中这些位置的值。如果 所有位置 都是 1，那么元素“可能存在”于集合中。
  3. 如果 任一位置 是 0，则该元素绝对不存在于集合中。

误判率（假阳性率）与设计参数

布隆过滤器的假阳性率取决于以下几个因素：

  • 位数组的大小（m）：位数组越大，每个元素对应的位置越多，哈希冲突的几率越小，误判率越低。
  • 哈希函数的个数（k）：使用更多的哈希函数能够降低误判率，但也会增加计算开销。
  • 元素的数量（n）：插入的元素越多，位数组中的填充率越高，误判率越高。

优点

  • 节省空间：布隆过滤器只使用二进制数据，占用空间非常小。
  • 高效查询：查询时间复杂度为 O(K)，K为哈希函数个数，查询速度非常快。
  • 保密性：布隆过滤器本身不存储任何原始数据，仅存储二进制数据。

缺点

  • 误报：由于哈希函数的映射特性，布隆过滤器可能会误报，即返回元素“可能存在”，但实际上并不存在。
  • 不能删除：布隆过滤器无法删除某个元素，因为多个元素可能共享同一哈希位，删除某个元素可能影响其他元素的查询。

计数型布隆过滤器（Counting Bloom Filter）

1. 基本结构

与标准布隆过滤器的结构不同，计数型布隆过滤器使用一个 计数器数组（而不是位数组）。每个数组元素被替换成一个整数值，用来记录该位置被多少次哈希映射过。这些计数器通常是无符号整数（比如 uint），并且初始化为 0。

  • 位数组（bit array）：布隆过滤器通常是一个只包含 0 和 1 的数组，用于表示一个集合中的元素是否存在。
  • 计数器数组（count array）：计数型布隆过滤器中的每个位置包含一个计数器，记录该位置被多少个不同元素哈希映射到。

2. 插入操作

插入操作的过程与标准布隆过滤器类似，但每次哈希映射到某个位置时，不是将该位置的位设置为 1，而是将对应位置的计数器加 1。

  1. 对元素 x 使用 k 个哈希函数，生成 k 个哈希值，得到 k 个对应的数组索引。
  2. 对每个哈希值对应的计数器进行 加 1，即增加该位置的计数器值。

3. 查询操作

查询操作与标准布隆过滤器相似，通过 k 个哈希函数 计算出元素映射的位置，并检查这些位置的计数器值。

  1. 对元素 x 使用 k 个哈希函数，计算出 k 个数组位置。
  2. 检查这些位置的计数器值。如果所有的计数器值都大于 0，则元素“可能存在”。如果任意位置的计数器为 0，则该元素绝对不存在于集合中。

4. 删除操作

删除操作是计数型布隆过滤器的一个重要特性。由于计数器数组用于跟踪每个位置的插入次数，我们可以通过减少计数器的值来实现删除操作。

  1. 对元素 x 使用 k 个哈希函数，计算出 k 个数组位置。
  2. 对每个位置的计数器进行 减 1，如果计数器值大于 0，则减少，否则不做任何操作。

优点

  • 支持删除操作：标准的布隆过滤器不能删除元素，因为删除一个元素可能会破坏其他元素的查询结果。而计数型布隆过滤器通过维护计数器来支持删除操作，从而使得某个元素可以被删除。
  • 插入和查询时间复杂度都为 O(k)，与标准布隆过滤器相同，因此查询效率依然非常高。

缺点

  • 内存消耗：由于每个位置都使用一个计数器（而不是位数组的单一二进制位），计数型布隆过滤器的内存消耗比标准布隆过滤器大。特别是如果计数器的位数较多（例如使用 32 位计数器），则会显著增加内存开销。
  • 计数溢出问题：计数器的值有上限（如 32 位计数器最大值为 2^32 - 1），当计数器溢出时，可能会导致错误的删除或查询结果，因此需要注意计数器溢出的情况。可以使用更大的计数器类型来减少溢出的风险，或者设计一定的溢出机制。

总结

布隆过滤器是一种用于高效判断元素是否存在于集合中的数据结构，具有空间节省和查询高效的优点，但存在误报率和无法删除元素的缺点。通过合理选择位数组长度和哈希函数个数，可以在空间效率和误报率之间进行平衡。计数型布隆过滤器通过扩展哈希位为计数器，解决了删除元素的问题。