布隆过滤器

布隆过滤器是一种概率型数据结构，用于检查集合中是否存在某个项目

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

布隆过滤器不存储集合中的所有项目，而是仅存储项目的哈希表示，因此会牺牲一定的精度。这种权衡的优势在于布隆过滤器非常节省空间且速度很快。

布隆过滤器可以保证某个项目不存在于集合中，但只能对其存在性进行估计。因此，当它响应某个项目不存在于集合中（否定回答）时，你可以确信事实确实如此。但每 N 个肯定回答中会有一个是错误的。尽管乍一看这似乎很不寻常，但这种不确定性在计算机科学中仍然有其应用之地。在许多情况下，否定回答可以防止更昂贵的操作，例如检查用户名是否已被占用、信用卡是否已被报告为被盗、用户是否已看过广告等等。

用例

金融欺诈检测（金融）

此应用回答了“用户之前是否在此位置支付过？”的问题，从而检查用户购物习惯中的可疑活动。

每个用户使用一个布隆过滤器，并在每笔交易时进行检查。提供极快的响应（本地延迟）。如果用户移动，则在不同区域进行复制。防止性能随规模增长而下降。

为此类应用使用 Redis 布隆过滤器可带来以下好处

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

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

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

广告投放（零售、广告）

此应用回答了以下问题

用户是否已看过此广告？
用户是否已购买此产品？

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

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

为此类应用使用 Redis 布隆过滤器可带来以下好处

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

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

此应用回答了以下问题：此用户名/电子邮件/域名/slug 是否已被使用？

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

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

查询时间随规模增长保持不变。

为此类应用使用 Redis 布隆过滤器可带来以下好处

执行常见操作的非常快速高效的方式
无需投资昂贵的基础设施

示例

考虑一家生产一百万种不同自行车的自行车制造商，您想避免在新车型中使用重复的型号名称。布隆过滤器可用于检测重复项。在下面的示例中，您将创建一个可容纳一百万条记录、错误率为 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-Sync


package io.redis.examples;

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

import static org.junit.jupiter.api.Assertions.assertEquals;

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]

        jedis.close();
    }
}

package example_commands_test

import (
	"context"
	"fmt"

	"github.com/redis/go-redis/v9"
)


func ExampleClient_bloom() {
	ctx := context.Background()

	rdb := redis.NewClient(&redis.Options{
		Addr:     "localhost:6379",
		Password: "", // no password docs
		DB:       0,  // use default DB
	})


	res1, err := rdb.BFReserve(ctx, "bikes:models", 0.01, 1000).Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res1) // >>> OK

	res2, err := rdb.BFAdd(ctx, "bikes:models", "Smoky Mountain Striker").Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res2) // >>> true

	res3, err := rdb.BFExists(ctx, "bikes:models", "Smoky Mountain Striker").Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res3) // >>> true

	res4, err := rdb.BFMAdd(ctx, "bikes:models",
		"Rocky Mountain Racer",
		"Cloudy City Cruiser",
		"Windy City Wippet",
	).Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res4) // >>> [true true true]

	res5, err := rdb.BFMExists(ctx, "bikes:models",
		"Rocky Mountain Racer",
		"Cloudy City Cruiser",
		"Windy City Wippet",
	).Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res5) // >>> [true true true]

}


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



public class Bf_tutorial
{
    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 布隆过滤器，大部分大小计算工作都已为您完成

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

1. 误报率 (`error_rate`)

该比率是介于 0 和 1 之间的十进制值。例如，对于期望的 0.1% 误报率（千分之一），error_rate 应设置为 0.001。

2. 预期容量 (`capacity`)

这是您预期过滤器中总共包含的项目数量，对于静态集合来说很简单，但当集合随时间增长时，这会变得更具挑战性。正确确定这个数字很重要，因为如果**容量过大**，最终会浪费内存。如果**容量过小**，过滤器将会满载，并且必须在其顶部叠加新的子过滤器（子过滤器叠加）。当过滤器由多个子过滤器叠加而成时，添加操作的延迟保持不变，但存在性检查的延迟会增加。这是由于检查的工作方式：常规检查会首先在顶部（最新的）过滤器上执行，如果返回否定回答，则检查下一个，依此类推。延迟增加正是源于此。

3. 扩展 (`EXPANSION`)

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

过滤器将为每个新的子过滤器继续添加更多哈希函数，以保持您期望的错误率。

您可能会想“既然我知道会扩展，为什么还要创建容量较小、扩展率较高的过滤器？”答案是：对于需要保留大量过滤器（例如每个用户或每个产品一个过滤器）的情况，其中大多数过滤器将保持较小，但一些活动较多的过滤器将不得不扩展。

4. `NONSCALING`

如果您知道不会扩展，请使用 NONSCALING 标志，因为这样过滤器将少使用一个哈希函数。请记住，如果您确实达到了最初分配的容量，您的错误率将开始增长。