快速未来的浪潮即将席卷您的城市。
加入我们参加 Redis 发布会
分享
我遇到一个问题。我的在线游戏《永恒世界》（并非真实游戏，但如果存在，它将来自海岸暴风雪！）拥有数千万玩家。这是一个令人欣喜的问题，如此多的游戏玩家！
但当新用户注册时，要确定他们想要的用户名是否已被占用需要花费很长时间。这是一个简单的查询，但海量数据导致速度缓慢。
切换到 Redis 有助于解决这个问题。不再使用简单但速度缓慢的 SQL 查询
> SELECT COUNT(*) FROM Users WHERE UserName = 'EricTheCleric'
我们最终获得了简单但快速的 Redis 命令
> SISMEMBER Users 'EricTheCleric'
成功！
但所有这些用户仍在占用大量的内存。数千万用户会产生这样的影响。是否有办法使我们的数据更小、更紧凑？
有。我向您介绍布隆过滤器。
布隆过滤器是一种概率数据结构。我们之前就讨论过 它们。简而言之，概率数据结构使用哈希函数，以牺牲一些不确定性为代价，提供更快速、更小的数据结构。将布隆过滤器视为具有有限功能的集合。我们只能向其中添加元素并检查特定元素是否在其中。但对于该检查的响应有点奇怪。布隆过滤器有两种可能的响应：
可能。这就是奇怪之处，即不确定性。但不要害怕。在 概率特性 中使用布隆过滤器，您可以完全控制不确定性的程度。我将向您展示如何使用它并控制不确定性。
让我们回到《永恒世界》。我的游戏中有数千万个独特的用户名，需要在创建新用户之前进行检查。
之前，我使用以下方法
> SISMEMBER Users 'EricTheCleric'
然后，如果用户名可用，则使用以下方法
> SADD Users 'EricTheCleric'
让我们使用布隆过滤器查看此过程。这里有两种可能的场景
艾丽丝·奥罗曼瑟想要创建一个《永恒世界》账户。我们检查她的用户名是否在布隆过滤器中
> BF.EXISTS UserFilter 'AliceTheAllomancer'
BF.EXISTS 返回 0, 表示 AliceTheAllomancer 不在集合中，并且可用。我们添加她：
> BF.ADD UserFilter 'AliceTheAllomancer'
> SADD Users 'AliceTheAllomancer'
非常容易。
鲍勃·野蛮人还想创建一个账户。我们查看他想要的用户名是否在布隆过滤器中：
> BF.EXISTS UserFilter 'BobTheBarbarian'
BF.EXISTS 返回 1。用户名可能已被占用。选择一个新的用户名。
现在，我知道你在想什么。如果它实际上没有被占用，我们应该检查吗？如果我们无情地拒绝了鲍勃·野蛮人想要的用户名，而它实际上是可用的，怎么办？
虽然我理解您不想让手持大型战斧的野蛮人感到愤怒，但这是正在进行的基本权衡。我们以牺牲有限的不确定性为代价，获得了性能和紧凑性。在这种情况下（尤其是因为战斧是虚拟的），这是一个不错的交易。
如果您只是调用 BF.ADD 并允许它为您创建布隆过滤器，您将获得默认值。这些值对于包含数十个项目的较小布隆过滤器来说很好，但对于上述示例，它们完全不合适。
设置布隆过滤器时，使用 BF.RESERVE 来控制设置：
> BF.RESERVE UserFilter 0.001 100000000
这将在密钥 UserFilter 下设置一个布隆过滤器，错误率为 0.001 或 0.1%，容量为 1 亿个用户名。
布隆过滤器的实现对于它们包含的功能来说出人意料地简单。在准备撰写这篇博文时，我（以及Redis 中的其他人员）使用 Node.js 在JavaScript 中编写了一个布隆过滤器，并在C# 中使用 .NET Core 编写了另一个。请注意，我编写这些布隆过滤器是为了教育目的，而不是为了性能，因此不要在生产中使用它们。
本质上，布隆过滤器是一个指定宽度的位数组。当向过滤器添加条目时，它将通过指定数量的哈希函数（通常是使用不同种子值的相同哈希算法）运行。这些哈希函数的结果用于生成位数组的索引。对于每个索引，在数组中放置一个 1。
一个示例可能使这一点更易于理解。让我们创建一个非常小的过滤器，位宽度为 8 位
| 位 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 索引 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
我们使用具有两个不同种子的哈希函数。当我们添加条目时，我们将调用哈希函数两次以获取两个数字。我们将模运算这些数字除以位宽度以生成我们的索引。以下是伪代码：
index = some_hash_function('AliceTheAllomancer', seed) % 8
假设对于艾丽丝·奥罗曼瑟，这会产生数字 2 和 6。然后，我们通过在位置 2 和 6 中放置一个 1 来更新我们的位数组。
| 位 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 索引 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
让我们添加鲍勃·野蛮人。我们让他通过我们的哈希函数，得到 3 和 6。我们的位数组现在如下所示
| 位 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
| 索引 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
很好。请注意，艾丽丝和鲍勃最终都将位 6 设置为 1。哈希冲突。不是问题。这就是我们使用多个哈希函数的原因。
现在让我们看看某个元素是否在布隆过滤器中。为此，我们将要检查的条目通过相同的哈希函数运行。如果我们运行艾丽丝·奥罗曼瑟，我们会像之前一样得到 2 和 6；如果我们运行鲍勃·野蛮人，我们会像之前一样得到 3 和 6。这是预期的，因为哈希函数是确定性的。
对于艾丽丝，我们检查位 2 和 6。它们都是 1，因此艾丽丝可能在布隆过滤器中。对于鲍勃，我们检查位 3 和 6。结果相同。
让我们检查一个我们知道不在过滤器中的元素，即埃里克·神职人员。埃里克的哈希值产生 0 和 6。由于所有位都没有设置为 1，因此埃里克绝对不在布隆过滤器中。
但弗里茨·格斗家呢？我们还没有见过他。他的哈希值产生 2 和 3。位 2 和 3 都被设置为 1，2 由艾丽丝设置，3 由鲍勃设置。弗里茨没有被添加，但他可能在过滤器中。嗯。
这就是布隆过滤器不确定性的来源。可以通过增加位宽度和/或哈希函数的数量来改善它。执行这两者中的任何一项都会消耗更多内存，因此始终存在权衡。这就是生活。
你可以使用一些代数和以下公式来计算错误率，其中 p 是错误率，k 是哈希函数的数量，m 是位宽，n 是你期望插入的最大元素数量：
p=(1 – e-kn/m)k
或者你可以直接使用一个在线计算器，比如 这个。
布隆过滤器还有很多我们没有提到的内容。
我们探索了一个简单的用例，但还有很多其他用例。如果你有很多数据并且不需要完美，布隆过滤器可以帮助你。你可以使用布隆过滤器来跟踪网页爬虫已经爬取的 URL，或者在社交媒体上记住推荐的朋友，这样用户就不会一直看到他们已经表示不认识的相同的“可能认识的人”建议。或者你可以将字典中的所有单词都放入布隆过滤器中，并将其用作拼写检查器。
我们也没有对 Redis 进行任何基准测试，以比较集合和布隆过滤器。但是我们之前已经 写过这方面的博客，所以没必要了！
如果你想更深入地了解布隆过滤器，请查看 Redis 文档 中关于布隆过滤器的部分，了解你可以用它们做的一切。如果你真的想了解它们的运作原理，请用你选择的语言编写你自己的布隆过滤器。并在 Twitter 上分享给我！
