使用 Node.js 和 Redis 探索 Bloom Filter 的魅力

在正确的用例中，布隆过滤器看起来就像魔法。这是一个大胆的说法，但在本教程中，我们将探讨这种奇怪的数据结构、如何最好地使用它，以及一些使用 Redis 和 Node.js 的实际示例。

布隆过滤器是一种概率性、单向数据结构。在这种情况下，“过滤器”一词可能会令人困惑；过滤器意味着它是一个活跃的事物，一个动词，但将它视为存储，一个名词可能更容易。使用简单的布隆过滤器，您可以做两件事：

1. 添加一个项目。
2. 检查之前是否未添加过某个项目。

这些是需要理解的重要限制 - 您无法删除项目，也无法在布隆过滤器中列出项目。此外，您无法确定过去是否已将某个项目添加到过滤器中。这就是布隆过滤器的概率性质发挥作用的地方——误报是可能的，但误报则不然。如果过滤器设置正确，误报的可能性会非常小。

存在布隆过滤器的变体，它们添加了其他功能，例如删除或缩放，但它们也增加了复杂性和限制。在继续了解变体之前，首先了解简单的布隆过滤器非常重要。本文仅介绍简单的布隆过滤器。

有了这些限制，您可以获得许多好处：固定大小、基于哈希的加密和快速查找。

当您设置布隆过滤器时，您需要为其指定一个大小。此大小是固定的，因此如果过滤器中有一项或十亿项，它永远不会增长超过指定的大小。当您向过滤器添加更多项目时，误报的可能性就会增加。如果您指定了较小的过滤器，则与使用较大的过滤器相比，误报率会增加得更快。

布隆过滤器建立在单向散列的概念之上。与正确存储密码非常相似，布隆过滤器使用哈希算法来确定传入其中的项目的唯一标识符。哈希本质上是无法逆转的，并且由看似随机的字符串表示。因此，如果有人获得了布隆过滤器的访问权限，它不会直接泄露任何内容。

最后，布隆过滤器速度很快。与其他方法相比，该操作涉及的比较次数要少得多，并且可以轻松存储在内存中，从而防止影响性能的数据库命中。

现在您已经了解了布隆过滤器的限制和优点，让我们来看看可以使用它们的一些情况。

设置

我们将使用 Redis 和 Node.js 来说明 Bloom 过滤器。 Redis 是 Bloom 过滤器的存储介质；它速度快，位于内存中，并且有一些特定的命令（GETBIT、SETBIT），可以提高实施效率。我假设您的系统上安装了 Node.js、npm 和 Redis。您的 Redis 服务器应该在 localhost 上的默认端口上运行，以便我们的示例正常工作。

在本教程中，我们不会从头开始实现过滤器；而是从头开始实现过滤器。相反，我们将重点关注 npm 中预构建模块的实际用途：bloom-redis。 bloom-redis 有一组非常简洁的方法：add、contains 和 clear。

如前所述，布隆过滤器需要哈希算法来生成项目的唯一标识符。 bloom-redis 使用众所周知的 MD5 算法，尽管它可能不适合 Bloom 过滤器（有点慢，有点过大），但可以正常工作。

独特的用户名

用户名，尤其是在 URL 中标识用户的用户名，需要是唯一的。如果您构建一个允许用户更改用户名的应用程序，那么您可能需要一个从未使用过的用户名，以避免用户名混淆和被攻击。

如果没有布隆过滤器，您需要引用一个包含曾经使用过的每个用户名的表，而大规模时这可能会非常昂贵。布隆过滤器允许您在用户每次采用新名称时添加一个项目。当用户检查用户名是否被占用时，您所需要做的就是检查布隆过滤器。它将能够绝对确定地告诉您所请求的用户名是否先前已添加。过滤器可能会错误地返回用户名已被使用，而实际上用户名尚未被使用，但这只是为了谨慎起见，不会造成任何真正的伤害（除了用户可能无法声明“k3w1d00d47”） .

为了说明这一点，让我们使用 Express 构建一个快速的 REST 服务器。首先，创建 package.json 文件，然后运行以下终端命令。

npm 安装bloom-redis --save

npm install express --save

npm install redis --save

bloom-redis 的默认选项大小设置为 2 MB。出于谨慎考虑，这是错误的，但它相当大。设置布隆过滤器的大小至关重要：太大会浪费内存，太小则误报率会太高。确定大小所涉及的数学非常复杂，超出了本教程的范围，但幸运的是，有一个布隆过滤器大小计算器可以完成这项工作，而无需破解教科书。

现在，创建 app.js 如下：

var
  Bloom         =   require('bloom-redis'),
  express       =   require('express'),
  redis         =   require('redis'),
  
  app,
  client,
  filter;

//setup our Express server
app = express();

//create the connection to Redis
client = redis.createClient();


filter = new Bloom.BloomFilter({ 
  client    : client, //make sure the Bloom module uses our newly created connection to Redis
  key       : 'username-bloom-filter', //the Redis key
  
  //calculated size of the Bloom filter.
  //This is where your size / probability trade-offs are made
  //http://hur.st/bloomfilter?n=100000&p=1.0E-6
  size      : 2875518, // ~350kb
  numHashes : 20
});

app.get('/check', function(req,res,next) {
  //check to make sure the query string has 'username'
  if (typeof req.query.username === 'undefined') {
    //skip this route, go to the next one - will result in a 404 / not found
    next('route');
  } else {
   filter.contains(
     req.query.username, // the username from the query string
     function(err, result) {
       if (err) { 
        next(err); //if an error is encountered, send it to the client
        } else {
          res.send({ 
            username : req.query.username, 
            //if the result is false, then we know the item has *not* been used
            //if the result is true, then we can assume that the item has been used
            status : result ? 'used' : 'free' 
          });
        }
      }
    );
  }
});


app.get('/save',function(req,res,next) {
  if (typeof req.query.username === 'undefined') {
    next('route');
  } else {
    //first, we need to make sure that it's not yet in the filter
    filter.contains(req.query.username, function(err, result) {
      if (err) { next(err); } else {
        if (result) {
          //true result means it already exists, so tell the user
          res.send({ username : req.query.username, status : 'not-created' });
        } else {
          //we'll add the username passed in the query string to the filter
          filter.add(
            req.query.username, 
            function(err) {
              //The callback arguments to `add` provides no useful information, so we'll just check to make sure that no error was passed
              if (err) { next(err); } else {
                res.send({ 
                  username : req.query.username, status : 'created' 
                });
              }
            }
          );
        }
      }
    });
  }
});

app.listen(8010);

登录后复制