缓存数据库 Redis 版的 ExBloomFilter 基于 Scalable Bloom Filter 实现，具备动态扩容能力，且能够在扩容过程中保持错误率的稳定性。本文介绍缓存数据库 Redis 版的 ExBloomFilter 数据结构相关信息，包括功能特性、原理、适用场景，以及具体的命令语法。

前提条件

• 实例的版本需同时满足如下要求才可使用 ExBloomFilter 数据结构：
  • 数据库版本需为 Redis 7.0。
  • Proxy 小版本需大于等于 1.22.0。
  • Serve 小版本需大于等于 7.17.3。

  说明

  您可以在实例信息查看实例的数据库版本和小版本信息，具体操作步骤，请参见查看实例信息。

• 实例状态需为运行中。关于实例状态的更多说明，请参见实例状态。

背景信息

Bloom 是一种高空间利用率的概率性数据结构（space-efficient probabilistic data structure），属于 sketches 的一种，在处理大规模数据时，仅需占用较少内存就能判定一个元素是否存在。相较于提供了类似用于判断元素是否存在功能的传统 Redis 数据结构（如 Hash、Set 以及 String 的 Bitset 等），ExBloomFilter 在内存占用、可动态扩容、可自定义错误率且在扩容时保持错误率稳定性等方面具备显著优势，非常适合于需要高效判定大量数据是否存在并且允许存在一定错误率的业务场景，您可以直接使用 ExBloomFilter 提供的 Bloom Filter 接口，免去您二次封装和在本地自行实现布隆过滤器功能的操作。

功能原理

缓存数据库 Redis 版提供的 ExBloomFilter 是基于可扩展布隆过滤器（Scalable Bloom Filter）实现的，具备动态扩容能力，且能够在扩容过程中保持错误率的稳定性。
ExBloomFilter 作为一种 Scalable Bloom Filter 的实现，具有动态扩容的能力，同时错误率维持不变。而 Scalable Bloom Filter 是在 Bloom Filter 的基础上进行优化的，下文将简单介绍 Bloom Filter 与 Scalable Bloom Filter 的基本原理。

• Bloom Filter
  Bloom Filter 本质上由一个 Bit 数组和 k 个不同的哈希函数组成，初始状态下该数组中的所有 Bit 都为 0，而哈希函数的作用是将输入元素映射到 Bit 数组中的不同位置。
  将一个元素添加到 Bloom Filter 中时，系统会先使用这 k 个哈希函数分别对该元素进行计算得到 k 个哈希值，然后将 Bit 数组中这 k 个哈希值所对应的位置设为 1。需要注意的是，一个 Bit 位可能被不同数据共享，即不同的元素经过哈希函数计算后可能会映射到相同的位置，导致这些位置被误设为 1。
  例如，如果 Bloom Filtre 中使用了 3 个哈希函数 (h_1)、(h_2)、(h_3)，将元素 (x1) 添加 Bloom Filter 时经过上述 3 个哈希函数计算得到的值分别为 (i_1)、(i_3)、(i_6)；添加元素 (x2) 时得到的值分别为 (i_6)、(i_8)、(i_10)，那么就将 Bit 数组中索引为 (i_1)、(i_3)、(i_6)、(i_8)、(i_10) 的 Bit 设为 1。(x1) 和 (x2) 在 Bit 数组中的位置示意图如下所示。
  

  查询一个元素是否在 Bloom Filter 中时，系统同样会先使用这 k 个哈希函数对该元素进行计算得到 k 个哈希值，然后检查 Bit 数组中这 k 个哈希值所对应的位置是否都为 1。如果这 k 个位置中有任何一个为 0，那么这个元素肯定不在 Bloom Filter 中；如果这 k 个位置都为 1，那么这个元素会被认为在 Bloom Filter 中。
  例如，查询元素 (y_1) 和 (y_2) 是否在 Bloom Filter 中时，先通过上述 3 个哈希函数 (h_1)、(h_2)、(h_3) 进行计算，查询元素 (y_1) 时得到的值为 (i_2)、(i_5)、(i_10)，元素 (y_2) 时得到的值为 (i_1)、(i_6)、(i_8)。(y1) 和 (y2) 在 Bit 数组中的位置示意图如下所示。
  

  从上图可知，(y2) 虽然未被添加到 Bloom Filter 中，但其在 Bit 数组中的所有位置都为 1，因此 Bloom Filter 将元素 (y2) 判断为存在。这是因为不同的元素经过哈希函数计算后可能会被映射到相同的位置，导致这些位置被误设为 1。
  因此 Bloom Filter 会存在误判的可能，这种可能性被称为误判率（False positive rate），即可能将不在集合中的元素判定为在集合中，但不会将在集合中的元素判定为不在集合中。

• Scalable Bloom Filter

  随着元素的不断添加，过滤器的错误率也会越来越高，而 Scalable Bloom Filter 在 Bloom Filter 的基础上进行了优化，能够根据数据量的增长动态自动扩容以适应更多元素的插入，同时保持相对稳定的错误率。
  Scalable Bloom Filter 采用了分层设计，当需要扩容时，不仅仅会扩大单个 Bloom Filter 的规模，同时还会增加新的层次，每一层都是一个独立的 Bloom Filter。
  新元素会被添加到最后一层的 Bloom Filter 中，查询时也会先从最后一层开始查询，直至查询到第一层。更多详情，请参见 Scalable Bloom Filter。

适用场景

缓存数据库Redis版提供的 ExBloomFilter 适用于以下典型场景：

• 商品广告推荐投放：通过 Bloom Filter 记录用户已购商品，在为用户推荐新商品前先查询该商品是否已在用户的 Bloom Filter 中，从而实现向用户推荐感兴趣且未购买过的商品。
• 海量数据过滤去重：在处理海量数据（如爬取网页的 URL、用户访问日志等）时，可将网页的 URL 或用户的访问 IP 经过哈希处理后添加到 Bloom Filter 中，在处理新数据前先查询该数据是否已在 Bloom Filter 来避免重复处理，减少不必要的网络请求和资源浪费。

使用建议

• 提前规划好初始容量（即需要添加的元素数量）与预期错误率。若预计容量远超过 100，建议使用 BF.RESERVE 命令创建 ExBloomFilter，而不建议直接通过 BF.ADD 创建。原因如下：
  • 通过 BF.ADD（或 BF.MADD）命令添加元素时，若目标 key 指定的 ExBloomFilter 不存在， Redis 会自动创建一个初始容量（capacity）为 100，错误率（error_rate）上限为 0.01 的 ExBloomFilter。若您的需要容量远超 100，后续只能通过扩容来增加元素。而 ExBloomFilter 的扩容方式为增加 Bloom Filter 层数，每层容量随之增长。持续扩容会使 ExBloomFilter 的层数不断增多，进而导致查询任务需遍历多层 Bloom Filter，严重降低性能。
  • 通过 BF.RESERVE 命令则可在创建 Bloom Filter 时自定义初始容量（capacity）和预期错误率（error_rate）。错误率越低，准确率越高，ExBloomFilter 的内存占用量越大，CPU 使用率越高；当元素数量超出初始容量值时，误判率会上升。
• ExBloomFilter 虽然提供了扩容能力，但实际使用时建议仅将此作为一种保障手段，尽量避免扩容操作。当实际容量超出初始容量时，ExBloomFilter 可通过扩容确保业务正常写入，避免线上事故。
• ExBloomFilter 仅支持插入新元素，但无法删除已有元素，这会使 ExBloomFilter 内存占用持续上升。为防止 ExBloomFilter 不断增大进而引发 OOM（Out Of Memory），使用时建议关注以下方面：
  • 业务数据拆分
    当大量数据存入单个 ExBloomFilter 时，不仅会使该 key 过大影响查询性能，而且大部分查询的请求流量会集中到该 key 所在的分片，形成热点 key 甚至访问倾斜。因此若业务数据量较大，建议您将业务数据拆分至多个 ExBloomFilter，若您使用的是启用分片集群实例，可以将 ExBloomFilter 分散到各分片，均衡内存容量与流量，发挥分片集群实例的优势。
  • 定期重建或轮转切换 ExBloomFilter
    若业务允许，您可以定期使用 DEL 命令删除 ExBloomFilter，再从后端数据库拉取数据重建，来控制 ExBloomFilter 大小。
    您也可以选择在使用初期创建多个冗余 ExBloomFilter，使用中通过轮转切换来控制单个 ExBloomFilter 大小，这样可避免频繁删除重建 ExBloomFilter 对线上业务的影响，但创建多个ExBloomFilter 会造成部分内存空间的浪费。

命令语法

命令列表

ExBloomFilter 支持的命令如下表所示。

注意事项

• 当前 ExBloomFilter 功能正处于灰度发布中，如需使用，请提交工单联系技术支持申请使用。

• 申请完成后，拥有 Administrator 角色的账号默认具备 ExBloomFilter 相关命令的所有权限。您也可以根据业务需要创建一个允许使用所有 ExBloomFilter 类命令的新角色（即该角色的 ACL 规则需设置为 +@exbloom），创建角色后，您需要通过拥有该角色的账号登录 Redis 后即可使用 ExBloomFilter 相关命令。创建角色的具体操作步骤，请参见创建角色。

• 缓存数据库 Redis 版支持对 ExBloomFilter 数据类型进行大、热 Key 分析，能够帮助及时发现并分析数据库中的热 Key 和大 Key 详情，为您优化热 Key 和大 Key 提供数据参考。具体操作步骤，请参见大 Key 分析和热 Key 分析。

• 成功申请使用 ExBloomFilter 功能后，实例将不再支持任何数据恢复功能，包括：

  • 按备份集恢复
  • 按时间点恢复
  • 恢复已删除实例

• ExBloomFilter 中的一个 Bit 位可能被不同数据共享（即不同的元素经过哈希函数计算后可能会映射到相同的位置），因此 ExBloomFilter 未提供删除 ExBloomFilter 中已存在元素的命令（否则会影响其他元素的数据），但您可以使用如下原生 Redis 命令实现删除 ExBloomFilter 的目的。

  命令	语法	说明
  EXPIRE	EXPIRE key seconds [NX | XX | GT | LT]	设置 ExBloomFilter 的超时时间，超过该时间的 ExBloomFilter 会被自动删除。
  UNLINK	UNLINK key [key ...]	异步删除一个或多个 ExBloomFilter。当通过 UNLINK 命令删除 ExBloomFilter 时，这些 ExBloomFilter 会被标记为待删除状态，而真正的删除操作会放在后台线程中进行，不会阻塞 Redis 的当前进程。
  DEL	DEL key [key ...]	同步删除一个或多个 ExBloomFilter。当通过 DEL 命令删除 ExBloomFilter 时，删除操作会立即阻塞 Redis 当前线程，直到这些 ExBloomFilter 对应的内存空间被完全回收释放。如果待删除的 ExBloomFilter 数据量过大，可能会影响 Redis 整体性能。

BF.RESERVE

BF.RESERVE testbf 0.01 100

OK

BF.ADD

BF.ADD testbf test_i1

1

BF.MADD

BF.MADD testbf test_i1 test_i2 test_i3

1) 0
2) 1
3) 1

BF.EXISTS

BF.EXISTS testbf test_i1

1

BF.MEXISTS

BF.MEXISTS testbf test_i2 test_i3 test_i4

1) 1
2) 1
3) 0

BF.INSERT

BF.INFO

BF.INFO testbf

1) total_items:25,num_blooms:2
2) bytes:16 bits:128 hashes:7 hashwidth:64 capacity:13 items:13 error_ratio:0.01
3) bytes:64 bits:512 hashes:8 hashwidth:64 capacity:46 items:12 error_ratio:0.005