文档：布隆过滤器

在 Valkey 中，布隆过滤器数据类型/命令在 valkey-bloom 模块中实现，该模块是与 8.0 及以上版本兼容的官方 Valkey 模块。用户需要将此模块加载到其 Valkey 服务器上才能使用此功能。

布隆过滤器是一种空间高效的概率数据结构，允许添加元素并检查元素是否存在。可能会出现误报，即过滤器错误地指示某个元素存在，即使它并未被添加。然而，布隆过滤器保证不会出现漏报（错误地指示某个元素不存在，即使它已被添加）。

基本布隆命令

  • BF.ADD 向布隆过滤器添加一个项目
  • BF.CARD 返回布隆过滤器的基数
  • BF.EXISTS 检查项目是否已添加到布隆过滤器中
  • BF.INFO 返回有关布隆过滤器的信息

请参阅布隆过滤器命令的完整列表。

布隆过滤器的常见用例

布隆过滤器可以帮助电子商务网站、流媒体服务、广告网络或营销平台回答以下问题

  • 是否已向用户展示过广告？
  • 是否已向用户发送过促销邮件或通知？
  • 用户是否已购买过某产品？

示例：为每个用户使用布隆过滤器存储他们已购买的所有产品。推荐引擎可以建议一个新产品，并检查它是否在用户的布隆过滤器中。

  • 如果产品不在过滤器中，则向用户展示广告，并将产品添加到过滤器中。
  • 如果产品已在过滤器中，则表示广告已向用户展示过，推荐引擎会寻找不同的广告来展示。

欺诈检测

布隆过滤器可用于回答“此卡是否已被标记为被盗？”的问题。为此，使用一个包含被报告为被盗卡片的布隆过滤器。当使用一张卡片时，检查它是否存在于布隆过滤器中。如果未找到该卡片，则表示它未被标记为被盗。如果卡片存在于过滤器中，则可以对照主数据库进行检查，或者拒绝购买。

过滤垃圾邮件/有害内容

布隆过滤器提供了一种有效的方式来筛选潜在威胁和有害内容。以下是它们的有效使用方法

示例：布隆过滤器可以回答“URL 是否恶意？”的问题。任何输入的 URL 都将与恶意 URL 布隆过滤器进行检查。

  • 如果不是，则允许访问该站点。
  • 如果是，则可以拒绝访问或对 URL 进行全面检查。

示例：布隆过滤器可以回答此内容是否有害或垃圾邮件的问题。创建一个包含垃圾邮件地址或垃圾电话号码的布隆过滤器。当收到电子邮件或短信时，检查号码或电子邮件是否存在于布隆过滤器中。

  • 如果不是，则可以将消息显示给用户。
  • 如果是，则可以将消息发送到垃圾邮件文件夹或对电子邮件或号码进行全面检查。

检查用户名是否已被占用

布隆过滤器可以回答以下问题：此用户名/电子邮件/域名/slug 是否已被使用？

在此用户名示例中，我们可以使用布隆过滤器来跟踪所有已注册的用户名。当新用户尝试使用他们想要的用户名注册时，应用程序会检查该用户名是否存在于布隆过滤器中。

  • 如果不存在，则创建用户并将用户名添加到布隆过滤器中。
  • 如果存在，应用程序可以决定检查主数据库或拒绝该用户名。

可扩展和不可扩展的布隆过滤器

布隆过滤器数据类型可以根据用户配置，作为“可扩展布隆过滤器”或“不可扩展布隆过滤器”工作。

可扩展和不可扩展布隆过滤器之间的区别在于，可扩展布隆过滤器没有固定的容量，而是可以增长。不可扩展布隆过滤器将具有固定容量，这意味着只能插入固定数量的项目。可扩展布隆过滤器由一个长度 >= 1 的“子过滤器”向量组成，而不可扩展的将只包含 1 个子过滤器。

当可扩展布隆过滤器达到其容量时，添加一个新的唯一项目将触发一次扩容，并创建一个新的子过滤器并将其添加到子过滤器向量中。这个新的子过滤器将具有更大的容量（上一个布隆过滤器的容量 * 布隆对象的扩展率）。

当不可扩展布隆过滤器达到其容量后，如果用户尝试添加新的唯一项目，将返回错误

扩展率是可扩展布隆过滤器在扩容时容量增加的速率。例如，我们有一个在创建时容量为 100 且扩展率为 2 的布隆过滤器。在添加 101 个唯一项目后，它将扩容并创建一个容量为 200 的新子过滤器。然后，在再添加 200 个唯一项目（总共 301 个项目）后，将在扩容时添加一个容量为 400 的新子过滤器，依此类推。

何时使用可扩展和不可扩展过滤器

如果容量（我们想要添加的项目数量）已知且固定，则首选使用不可扩展布隆过滤器。反之，如果容量未知/动态计算，则使用可扩展布隆过滤器是理想的选择。

使用不可扩展过滤器有一些好处。不可扩展过滤器将比多次扩容（例如 > 100 次）的过滤器具有更好的性能。此外，通常情况下，不可扩展过滤器在相同容量下比多次扩容的可扩展过滤器使用更少的内存。

但是，为了确保您不会遇到任何与容量相关的错误，并希望即用即付的容量，可扩展性更好。

布隆属性

  • 容量 - 在发生扩容之前或（不可扩展情况下）在拒绝添加唯一项目之前需要添加的唯一项目数量。

  • 误报率（错误率）- 控制布隆检查/设置操作产生误报的概率。示例：添加项目返回 0（或项目检查返回 1），表示项目已添加，即使它没有。

  • 扩展 - 这是可扩展布隆过滤器的一个属性，它通过确定新创建的子过滤器的容量来控制布隆过滤器扩容时的总容量增长。这个新容量等于上一个过滤器的容量 * 扩展率。

高级属性

以下两个属性可以在 BF.INSERT 命令中指定

  • 种子 - 这是为布隆过滤器创建哈希函数的键。对于可扩展布隆过滤器，所有子过滤器都使用相同的种子。此属性仅在您有特定的 32 字节种子并希望布隆过滤器使用它时有用。默认情况下，每个布隆过滤器都将使用随机种子。

  • 收紧比率 - 这是可扩展布隆过滤器的一个属性，它通过使实际误报率更接近用户在创建布隆过滤器时请求的误报率，来控制布隆过滤器在扩容时的整体正确性。这是通过使用收紧比率在新创建的子过滤器上设置更严格的误报来实现的。我们不建议微调此项，除非有特定用例需要更低的内存使用率和更高的误报率，反之亦然。

默认布隆属性

这些是默认的布隆属性，以及允许自定义的命令和配置。

属性默认值命令名称配置名称
容量100BF.INSERT, BF.RESERVEBF.BLOOM-CAPACITY
误报率0.01BF.INSERT, BF.RESERVEBF.BLOOM-FP-RATE
可扩展/不可扩展可扩展BF.INSERT, BF.RESERVEBF.BLOOM-EXPANSION
扩展率2BF.INSERT, BF.RESERVEBF.BLOOM-EXPANSION
收紧比率0.5BF.INSERTBF.BLOOM-TIGHTENING-RATIO
种子随机种子BF.INSERTBF.BLOOM-USE-RANDOM-SEED

由于布隆过滤器的默认扩展率为 2，这意味着通过 BF.ADD、BF.MADD、BF.INSERT 命令默认创建的任何布隆过滤器都将是可扩展的布隆过滤器。用户可以使用 BF.RESERVE <filter-name> <error-rate> <capacity> NONSCALING 或在 BF.INSERT 中指定 NONSCALING 来创建不可扩展的布隆过滤器。此外，布隆过滤器创建的其他默认属性可以在上表中和下面的 BF.INFO 命令响应中看到。这些默认属性可以通过布隆模块上的配置进行配置。

默认布隆过滤器信息的示例

127.0.0.1:6379> BF.ADD default_filter item
1
127.0.0.1:6379> BF.INFO default_filter
 1) Capacity
 2) (integer) 100
 3) Size
 4) (integer) 384
 5) Number of filters
 6) (integer) 1
 7) Number of items inserted
 8) (integer) 2
 9) Error rate
10) "0.01"
11) Expansion rate
12) (integer) 2
13) Tightening ratio
14) "0.5"
15) Max scaled capacity
16) (integer) 26214300

性能

涉及添加项目或检查项目存在的布隆命令的时间复杂度为 O(N * K)，其中 N 是布隆过滤器使用的哈希函数数量，K 是正在插入的元素数量。这意味着 BF.ADD 和 BF.EXISTS 都具有 O(N) 的时间复杂度，因为它们只操作一个项目。

对于可扩展布隆过滤器，每次扩容都会增加在任何添加/存在操作期间执行的检查次数（使用每个子过滤器的哈希函数）。因此，建议用户在评估用例/工作负载后选择容量和扩展率，以避免多次扩容并减少检查次数。

其他布隆过滤器命令的时间复杂度为 O(1)：BF.CARD、BF.INFO、BF.RESERVE 和 BF.INSERT（未提供项目时）。

监控

要检查服务器的整体布隆过滤器指标，您可以使用 INFO BF 或 INFO MODULES 命令。

在不同场景下调用 INFO BF 的示例

127.0.0.1:6379> INFO BF
# bf_bloom_core_metrics
bf_bloom_total_memory_bytes:0
bf_bloom_num_objects:0
bf_bloom_num_filters_across_objects:0
bf_bloom_num_items_across_objects:0
bf_bloom_capacity_across_objects:0

# bf_bloom_defrag_metrics
bf_bloom_defrag_hits:0
bf_bloom_defrag_misses:0
127.0.0.1:6379> bf.add key value
(integer) 1
127.0.0.1:6379> info bf
# bf_bloom_core_metrics
bf_bloom_total_memory_bytes:384
bf_bloom_num_objects:1
bf_bloom_num_filters_across_objects:1
bf_bloom_num_items_across_objects:1
bf_bloom_capacity_across_objects:100

# bf_bloom_defrag_metrics
bf_bloom_defrag_hits:0
bf_bloom_defrag_misses:0

布隆过滤器核心指标

  • bf_bloom_total_memory_bytes: 所有布隆过滤器当前使用的总字节数。

  • bf_bloom_num_objects: 当前布隆过滤器的总数量。

  • bf_bloom_num_filters_across_objects: 当前所有布隆过滤器中的子过滤器总数量。

  • bf_bloom_num_items_across_objects: 当前所有布隆过滤器中的项目总数量。

  • bf_bloom_capacity_across_objects: 当前所有布隆过滤器的总容量。

布隆过滤器碎片整理指标

  • bf_bloom_defrag_hits: 布隆过滤器上发生的碎片整理命中总数。

  • bf_bloom_defrag_misses: 布隆过滤器上发生的碎片整理未命中总数。

处理大型布隆过滤器

布隆过滤器面临着两个值得注意的验证。

  1. 内存使用

    每个布隆过滤器的内存使用限制默认由 BF.BLOOM-MEMORY-USAGE-LIMIT 模块配置定义，其默认值为 128 MB。如果命令导致创建/扩容使总内存使用量超过此限制，则该命令将被拒绝。此配置可修改，并可根据需要增加。

  2. 子过滤器数量（可扩展布隆过滤器情况下）

    当布隆过滤器扩容时，会添加一个新的子过滤器。子过滤器数量的限制取决于误报率和收紧比率。每个子过滤器都有更严格的误报，这由收紧比率控制。如果尝试扩容的命令导致子过滤器达到 0 的误报，则该命令将被拒绝。

您可以使用 VALIDATESCALETO 作为 BF.INSERT 的可选参数，以帮助确定布隆过滤器是否可以在不触及上述任何限制的情况下扩容到指定容量。否则，命令将被拒绝。

如下所示，当尝试创建容量无法通过扩容（考虑到内存限制）实现的布隆过滤器时，命令将被拒绝。但是，如果容量可以通过扩容实现（即使有这些限制），则布隆过滤器的创建将成功。

示例

127.0.0.1:6379> BF.INSERT validate_scale_fail VALIDATESCALETO 26214301
(error) ERR provided VALIDATESCALETO causes bloom object to exceed memory limit
127.0.0.1:6379> BF.INSERT validate_scale_valid VALIDATESCALETO 26214300
[]

BF.INFO 命令的 MAXSCALEDCAPACITY 字段可用于查找可扩展布隆过滤器可以扩展到的最大容量。

127.0.0.1:6379> BF.INFO validate_scale_valid MAXSCALEDCAPACITY
(integer) 26214300
Slack 图标 Slack GitHub 图标 GitHub LinkedIn 图标 LinkedIn X 图标 X.com 邮件图标 联系我们
行为准则 论坛 关于 常见问题

© Valkey 贡献者。

Valkey 和 Valkey 徽标是 LF Projects, LLC 的商标。

商标政策. 隐私政策. 使用条款. 有关其他政策，请参阅 lfprojects.org。

Valkey 包含来自 Redis Ltd. 的某些 3-Clause BSD 许可的 Redis 代码以及其他源代码。Redis Ltd. 不是其他源代码的来源。Redis 是 Redis Ltd. 的注册商标。

标志设计者：Ziyang。