布隆过滤器

布隆过滤器是一种概率数据结构，用于检查集合中是否存在元素

布隆过滤器是 Redis Stack 中的一种概率数据结构，它允许您使用固定大小的极小内存空间来检查集合中是否存在元素。

布隆过滤器不存储集合中的所有元素，而是只存储元素的哈希表示，因此会牺牲一些精度。但好处是，布隆过滤器非常节省空间并且速度很快。

布隆过滤器可以保证一个元素不在集合中，但只能对它的存在给出估计。所以当它回答一个元素不在集合中（一个否定的答案）时，你可以确定情况确实如此。但是，每 N 个肯定的答案中就会有一个是错误的。虽然乍一看这似乎很奇怪，但这种不确定性在计算机科学中仍然有它的位置。在很多情况下，一个否定的答案可以阻止更昂贵的操作，例如检查用户名是否已经被占用，信用卡是否被报告为失窃，用户是否已经看到过广告等等。

用例

金融欺诈检测（金融）

此应用程序回答问题：“用户之前是否从这个位置付款过？”，从而检查用户购物习惯中的可疑活动。

为每个用户使用一个布隆过滤器，在每次交易时进行检查。提供极快的响应（本地延迟）。在用户移动的情况下，在不同的区域复制。防止随着规模的扩大而降低性能。

将 Redis Stack 的布隆过滤器用于此类应用程序，可以提供以下好处

快速完成交易
在网络分区的情况下，降低交易中断的可能性（连接需要保持更短的时间）
为信用卡持卡人和零售商提供额外的安全层

布隆过滤器可以帮助金融行业回答的其他问题包括

用户是否曾经购买过此类产品/服务？
当用户在经过验证的在线商店（如亚马逊、苹果应用商店等大型零售商）购买时，是否需要跳过一些安全步骤？
此信用卡是否被报告为丢失/被盗？在最后一种情况下使用布隆过滤器的一个额外好处是，金融机构可以交换他们被盗/被封锁的信用卡号码列表，而无需透露号码本身。

广告投放（零售、广告）

此应用程序回答以下问题

用户是否已经看过这个广告？
用户是否已经购买了这个产品？

为每个用户使用一个布隆过滤器，存储所有购买的产品。推荐引擎会推荐一个新产品，并检查该产品是否在用户的布隆过滤器中。

如果没有，则向用户展示广告，并将其添加到布隆过滤器中。
如果有，则重新开始该过程，并重复，直到找到一个不在过滤器中的产品。

将 Redis Stack 的布隆过滤器用于此类应用程序，可以提供以下好处

以经济高效的方式实现定制的近实时体验
无需投资昂贵的基础设施

检查用户名是否已被占用（SaaS、内容发布平台）

此应用程序回答以下问题：此用户名/电子邮件/域名/标识符是否已被使用？

为每个注册的用户名使用一个布隆过滤器。新用户输入所需的用户名。该应用程序会检查用户名是否在布隆过滤器中。

如果没有，则创建用户，并将用户名添加到布隆过滤器中。
如果有，该应用程序可以选择检查主数据库或拒绝用户名。

查询时间在规模上保持不变。

将 Redis Stack 的布隆过滤器用于此类应用程序，可以提供以下好处

一种快速有效地执行常见操作的方法
无需投资昂贵的基础设施

示例

假设一家自行车制造商生产了 100 万种不同类型的自行车，你想避免在新车型中使用重复的车型名称。可以使用布隆过滤器来检测重复项。在下面的示例中，你将创建一个容纳 100 万个条目的过滤器，误报率为 0.1%。添加一个车型名称，并检查它是否存在。然后添加多个车型名称，并检查它们是否存在。

>_ Redis CLI

> BF.RESERVE bikes:models 0.001 1000000
OK
> BF.ADD bikes:models "Smoky Mountain Striker"
(integer) 1
> BF.EXISTS bikes:models "Smoky Mountain Striker"
(integer) 1
> BF.MADD bikes:models "Rocky Mountain Racer" "Cloudy City Cruiser" "Windy City Wippet"
1) (integer) 1
2) (integer) 1
3) (integer) 1
> BF.MEXISTS bikes:models "Rocky Mountain Racer" "Cloudy City Cruiser" "Windy City Wippet"
1) (integer) 1
2) (integer) 1
3) (integer) 1

Python

"""
Code samples for Bloom filter doc pages:
    https://redis.ac.cn/docs/latest/develop/data-types/probabilistic/bloom-filter/
"""
import redis

r = redis.Redis(decode_responses=True)

res1 = r.bf().reserve("bikes:models", 0.01, 1000)
print(res1)  # >>> True

res2 = r.bf().add("bikes:models", "Smoky Mountain Striker")
print(res2)  # >>> True

res3 = r.bf().exists("bikes:models", "Smoky Mountain Striker")
print(res3)  # >>> True

res4 = r.bf().madd(
    "bikes:models",
    "Rocky Mountain Racer",
    "Cloudy City Cruiser",
    "Windy City Wippet",
)
print(res4)  # >>> [True, True, True]

res5 = r.bf().mexists(
    "bikes:models",
    "Rocky Mountain Racer",
    "Cloudy City Cruiser",
    "Windy City Wippet",
)
print(res5)  # >>> [True, True, True]

Node.js

import assert from 'assert';
import { createClient } from 'redis';

const client = createClient();
await client.connect();


const res1 = await client.bf.reserve('bikes:models', 0.01, 1000);
console.log(res1);  // >>> OK

const res2 = await client.bf.add('bikes:models', 'Smoky Mountain Striker');
console.log(res2);  // >>> true

const res3 = await client.bf.exists('bikes:models', 'Smoky Mountain Striker');
console.log(res3);  // >>> true

const res4 = await client.bf.mAdd('bikes:models', [
  'Rocky Mountain Racer',
  'Cloudy City Cruiser',
  'Windy City Wippet'
]);
console.log(res4);  // >>> [true, true, true]

const res5 = await client.bf.mExists('bikes:models', [
  'Rocky Mountain Racer',
  'Cloudy City Cruiser',
  'Windy City Wippet'
]);
console.log(res5);  // >>> [true, true, true]

Java


package io.redis.examples;

import redis.clients.jedis.UnifiedJedis;
import org.junit.Test;
import org.junit.Assert;
import java.util.List;

public class BloomFilterExample {

    public void run() {
        UnifiedJedis jedis = new UnifiedJedis("redis://localhost:6379");


        String res1 = jedis.bfReserve("bikes:models", 0.01, 1000);
        System.out.println(res1); // >>> OK


        boolean res2 = jedis.bfAdd("bikes:models", "Smoky Mountain Striker");
        System.out.println(res2); // >>> True

        boolean res3 = jedis.bfExists("bikes:models", "Smoky Mountain Striker");
        System.out.println(res3); // >>> True

        List<Boolean> res4 = jedis.bfMAdd("bikes:models",
                "Rocky Mountain Racer",
                "Cloudy City Cruiser",
                "Windy City Wippet");
        System.out.println(res4); // >>> [True, True, True]

        List<Boolean> res5 = jedis.bfMExists("bikes:models",
                "Rocky Mountain Racer",
                "Cloudy City Cruiser",
                "Windy City Wippet");
        System.out.println(res5); // >>> [True, True, True]
    }
}


using NRedisStack.RedisStackCommands;
using NRedisStack.Tests;
using StackExchange.Redis;



public class Bf_tutorial
{

    [SkipIfRedis(Is.OSSCluster)]
    public void run()
    {
        var muxer = ConnectionMultiplexer.Connect("localhost:6379");
        var db = muxer.GetDatabase();


        bool res1 = db.BF().Reserve("bikes:models", 0.01, 1000);
        Console.WriteLine(res1);    // >>> True

        bool res2 = db.BF().Add("bikes:models", "Smoky Mountain Striker");
        Console.WriteLine(res2);    // >>> True

        bool res3 = db.BF().Exists("bikes:models", "Smoky Mountain Striker");
        Console.WriteLine(res3);    // >>> True

        bool[] res4 = db.BF().MAdd("bikes:models", new RedisValue[]{
            "Rocky Mountain Racer",
            "Cloudy City Cruiser",
            "Windy City Wippet"
        });
        Console.WriteLine(string.Join(", ", res4)); // >>> True, True, True

        bool[] res5 = db.BF().MExists("bikes:models", new RedisValue[]{
            "Rocky Mountain Racer",
            "Cloudy City Cruiser",
            "Windy City Wippet"
        });
        Console.WriteLine(string.Join(", ", res5)); // >>> True, True, True

        // Tests for 'bloom' step.


    }
}

注意：即使只有少数项目，也始终存在误报的可能性，这意味着一个项目可能“存在”，即使它没有明确添加到布隆过滤器中。要更深入地了解布隆过滤器的概率性质，请查看此页面底部的链接文章。

保留布隆过滤器

借助 Redis Stack 的布隆过滤器，大部分大小调整工作都已为您完成

BF.RESERVE {key} {error_rate} {capacity} [EXPANSION expansion] [NONSCALING]

1. 误报率（`error_rate`）

该比率是介于 0 到 1 之间的十进制值。例如，对于所需的 0.1%（1/1000）的误报率，error_rate 应设置为 0.001。

2. 预期容量（`capacity`）

这是您预计过滤器中总共包含的元素数量，当您拥有一个静态集合时，这很简单，但当您的集合随着时间的推移而增长时，它会变得更具挑战性。正确获取此数字非常重要，因为如果您**过度扩大**，最终会导致浪费内存。如果您**过小**，过滤器将填满，一个新的过滤器将不得不堆叠在它的上面（子过滤器堆叠）。在过滤器由多个子过滤器堆叠在一起的情况下，添加的延迟保持不变，但存在检查的延迟会增加。造成这种情况的原因是检查的方式：常规检查将首先在最顶层（最新）过滤器上执行，如果返回否定答案，则检查下一个过滤器，依此类推。这就是增加的延迟来源。

3. 缩放（`EXPANSION`）

由于数据结构“填满”，向布隆过滤器添加元素永远不会失败。相反，误报率开始增长。为了使误报率接近过滤器初始化时设置的误报率，布隆过滤器将自动缩放，这意味着当容量达到时，将创建一个额外的子过滤器。
新子过滤器的尺寸是最后一个子过滤器的尺寸乘以 EXPANSION。如果要存储在过滤器中的元素数量未知，我们建议您使用 2 或更大的扩展值来减少子过滤器的数量。否则，我们建议您使用 1 的扩展值来减少内存消耗。默认扩展值为 2。

过滤器将为每个新的子过滤器添加更多哈希函数，以保持您所需的误报率。

您可能想知道“如果我知道无论如何都要进行缩放，为什么我要创建一个具有高扩展率的小型过滤器？”；答案是：对于需要保存许多过滤器（例如，每个用户一个过滤器，或每个产品一个过滤器）的情况，其中大多数过滤器将保持较小，但一些具有更多活动的过滤器将不得不进行缩放。

4. `NONSCALING`

如果您知道自己不会进行缩放，请使用 NONSCALING 标志，因为这样过滤器将使用一个更少的哈希函数。请记住，如果您最终达到了最初分配的容量，您的误报率将开始增长。