Redis 8 来了—而且是开源的
了解更多
分享
我遇到了一个问题。我的在线游戏“永恒工艺世界”（不是真正的游戏。但如果存在，它将来自海岸的暴雪！）中有数千万玩家。这是一个很棒的问题。这么多游戏玩家！
但是当一个新用户注册时，需要很长时间才能确定他们想要的用户名是否已被占用。这是一个足够简单的查询，但大量的数据使其速度变慢。
切换到 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%，容量为 100,000,000 个用户名。
布隆过滤器的实现对于它们所包含的功能来说非常容易。在准备撰写这篇博客文章时，我（和 Redis 的其他人）用 JavaScript 使用 Node.js 编写了一个布隆过滤器，另一个用 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
或者您可以只使用在线计算器，例如 这个。
布隆过滤器还有很多我们没有讨论的内容。
我们探索了一个简单的用例，但还有更多更多。如果您有很多数据，并且不需要完美，那么 Bloom 过滤器将为您服务。您可以使用 Bloom 过滤器来跟踪 Web 爬虫已爬取的 URL，或者记住社交媒体上的建议朋友，这样用户就不会一直看到相同的“可能认识的人”建议，因为他们已经说过不认识。或者，您可以将其输入字典中的所有单词，并将其用作拼写检查器。
我们也没有执行任何使用 Redis 的基准测试来比较集合和 Bloom 过滤器。但是我们之前已经在博客上写过相关内容，所以没有必要再写了！
如果您想更深入地探索 Bloom 过滤器，请查看 Redis 关于 Bloom 过滤器的文档，了解您可以对它们执行的所有操作。如果您想真正了解它们的工作原理，请用您选择的语言编写自己的 Bloom 过滤器。请在 Twitter 上与我分享！
