使用Node.js和Redis了解Bloom過濾器的魔力

在正确的用例中，Bloom過濾器似乎很神奇。這是一個大膽的聲明，但是在本教程中，我們将探索奇怪的資料結構，如何最好地使用它，以及一些使用Redis和Node.js的實際示例。

布隆過濾器是一種機率的單向資料結構。在這種情況下，“過濾器”一詞可能會造成混淆。 filter表示它是一個活躍的事物，一個動詞，但将其視為存儲（名詞）可能會更容易。使用簡單的Bloom過濾器，您可以做兩件事：

添加一個項目。
檢查以前是否未添加項目。

這些是要了解的重要限制-您不能删除項目，也不能在Bloom過濾器中列出這些項目。另外，您不能肯定地說過去是否有項目添加到過濾器中。這就是布隆過濾器的機率性質出現的地方—可能出現誤報，但不會出現誤報。如果正确設定了過濾器，則誤報極少發生。

存在布隆過濾器的變體，它們增加了其他功能，例如删除或縮放，但也增加了複雜性和局限性。在繼續使用變體之前，首先了解簡單的Bloom過濾器很重要。本文将僅介紹簡單的Bloom過濾器。

有了這些限制，您将獲得許多好處：固定大小，基于哈希的加密和快速查找。

設定布隆過濾器時，請為其指定大小。此大小是固定的，是以，如果過濾器中有一項或十億個項目，它将永遠不會超過指定的大小。當您向過濾器中添加更多項目時，誤報的機會就會增加。如果您指定了一個較小的過濾器，則此誤報率将比較大的過濾器增加得更快。

布隆過濾器建立在單向哈希的概念上。就像正确存儲密碼一樣，Bloom過濾器使用雜湊演算法來确定傳遞給它的項目的唯一辨別符。從本質上講，哈希是無法逆轉的，并且由看似随機的字元串表示。是以，如果有人通路了Bloom過濾器，它将不會直接顯示任何内容。

最後，布隆過濾器非常快速。與其他方法相比，該操作所涉及的比較少得多，并且可以輕松地将其存儲在記憶體中，進而防止資料庫性能下降。

現在您已經了解了Bloom過濾器的局限性和優點，下面讓我們看一下可以使用它們的情況。

建立

我們将使用Redis和Node.js來說明Bloom過濾器。 Redis是Bloom過濾器的存儲媒體。它是快速的，記憶體中的，并且具有一些特定的指令（

GETBIT

，

SETBIT

），這些指令可提高實作效率。我假設您在系統上安裝了Node.js，npm和Redis。您的Redis伺服器應該在

localhost

的預設端口上運作，我們的示例才能正常工作。

在本教程中，我們不會從頭開始實作過濾器；取而代之的是，我們将重點關注npm中預構模組化塊的實際用途： bloom-redis 。 bloom-redis有一套非常簡潔的方法：

add

，

contains

和

clear

。

如前所述，Bloom過濾器需要一種雜湊演算法來生成商品的唯一辨別符。 Bloom-redis使用了著名的MD5算法，該算法雖然可能不是Bloom濾波器的理想選擇（有點慢，對比特的過大殺傷力），但效果很好。

唯一的使用者名

使用者名，尤其是在URL中辨別使用者的使用者名，必須唯一。如果您建構了一個允許使用者更改使用者名的應用程式，那麼您可能會希望使用從未使用過的使用者名，以避免使用者名的混淆和割傷。

如果沒有Bloom過濾器，則您需要引用一個表，該表包含曾經使用過的每個使用者名，并且從規模上講，這可能會非常昂貴。布隆過濾器使您可以在使用者每次采用新名稱時添加一個項目。當使用者檢查是否使用了使用者名時，您要做的就是檢查Bloom過濾器。它可以絕對确定地告訴您是否先前已添加了所請求的使用者名。過濾器可能會錯誤地傳回未使用的使用者名，但這在謹慎方面是錯誤的，并且不會造成實際傷害（除了使用者可能無法聲明“ k3w1d00d47”之外）。

為了說明這一點，讓我們用Express建構一個快速的REST伺服器。首先，建立您的

package.json

檔案，然後運作以下終端指令。

npm install bloom-redis --save

npm install express --save

npm install redis --save

Bloom-redis的預設選項的大小設定為2 MB。在謹慎方面這是錯誤的，但是它很大。設定Bloom過濾器的大小至關重要：太大會浪費記憶體，太小會導緻誤報率太高。确定大小所涉及的數學運算非常複雜，超出了本教程的範圍，但是值得慶幸的是，這裡有一個Bloom Bloom大小電腦可以完成工作而不會破解教科書。

現在，如下建立您的

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);

要運作此伺服器：

node app.js

轉到浏覽器并将其指向：

https://localhost:8010/check?username=kyle

。響應應為：

{"username":"kyle","status":"free"}

。

現在，通過将浏覽器指向

http://localhost:8010/save?username=kyle

。響應将是：

{"username":"kyle","status":"created"}

。如果傳回位址

http://localhost:8010/check?username=kyle

，則響應将為

{"username":"kyle","status":"used"}

。同樣，傳回

http://localhost:8010/save?username=kyle

将導緻

{"username":"kyle","status":"not-created"}

。

在終端上，您可以看到過濾器的大小：

redis-cli strlen username-bloom-filter

。

現在，隻有一項，它應該顯示

。

現在，繼續嘗試使用

/save

路由添加更多使用者名。嘗試任意數量。

如果然後再次檢查大小，您可能會注意到大小略有增加，但并非每次添加都變大。很好奇吧？在内部，Bloom過濾器在使用者名存儲區儲存的字元串的不同位置設定單個位（1/0）。但是，它們不是連續的，是以，如果先在索引0處設定一個位，然後在索引10,000處設定一個位，則兩者之間的所有值都将為0。對于實際用途，了解每個操作的精确機制一開始并不重要，隻要知道是正常的，您在Redis中的存儲将永遠不會超過您指定的值。

新鮮内容

網站上的新鮮内容使使用者回頭客，那麼您如何每次向使用者展示新内容呢？使用傳統的資料庫方法，您可以在表中添加帶有使用者辨別符和故事辨別符的新行，然後在決定顯示内容時查詢該表。就像您想象的那樣，您的資料庫将快速增長，尤其是随着使用者和内容的增長。

在這種情況下，假陰性（例如，不顯示看不見的内容）幾乎沒有後果，這使得Bloom過濾器成為可行的選擇。乍一看，您可能會認為您需要為每個使用者使用Bloom過濾器，但是我們将使用使用者辨別符和内容辨別符的簡單連接配接，然後将該字元串插入到我們的過濾器中。這樣，我們可以為所有使用者使用單個過濾器。

在此示例中，讓我們建構另一個顯示内容的基本Express伺服器。每次您通路

/show-content/any-username

路線（ any-username是任何URL安全值）時，都會顯示一條新内容，直到該站點不存在為止。在此示例中，内容是有關Gutenberg項目的前十本書的第一行。

我們将需要再安裝一個npm子產品。從終端運作：

npm install async --save

您的新app.js檔案：

var
  async         =   require('async'),
  Bloom         =   require('bloom-redis'),
  express       =   require('express'),
  redis         =   require('redis'),
  
  app,
  client,
  filter,
  
  // From Project Gutenberg - opening lines of the top 10 public domain ebooks
  // https://www.gutenberg.org/browse/scores/top
  openingLines = {
    'pride-and-prejudice' : 
      'It is a truth universally acknowledged, that a single man in possession of a good fortune, must be in want of a wife.',
    'alices-adventures-in-wonderland' : 
      'Alice was beginning to get very tired of sitting by her sister on the bank, and of having nothing to do: once or twice she had peeped into the book her sister was reading, but it had no pictures or conversations in it' }

如果您仔細注意開發工具中的往返時間，您會發現請求帶有使用者名的單個路徑越多，花費的時間就越長。雖然檢查過濾器需要固定的時間，但在此示例中，我們正在檢查是否存在更多項目。布隆過濾器隻能告知您有限資訊，是以您正在測試每個項目的存在。當然，在我們的示例中，這非常簡單，但是測試數百個項目的效率很低。

陳舊資料

在此示例中，我們将建構一個小型Express伺服器，該伺服器将執行以下兩項操作：通過POST接受新資料，并顯示目前資料（帶有GET請求）。将新資料釋出到伺服器後，應用程式将檢查過濾器中是否存在該資料。如果不存在，則将其添加到Redis中的集合中，否則将傳回null。 GET請求将從Redis擷取它，并将其發送到用戶端。

這與前兩種情況不同，因為誤報是不可能的。我們将使用布隆過濾器作為第一道防線。給定Bloom過濾器的屬性，我們隻能肯定地确定過濾器中沒有東西，是以在這種情況下，我們可以繼續進行操作，讓資料進入。如果Bloom過濾器傳回的可能是過濾器中的資料，将對照實際資料源進行檢查。

那麼，我們可以獲得什麼呢？我們獲得了不必每次都與實際來源進行核對的速度。在資料源很慢的情況下（外部API，pokey資料庫，平面檔案的中間），确實需要提高速度。為了示範速度，我們在示例中添加150ms的實際延遲。我們還将使用

console.time

console.timeEnd

記錄Bloom過濾器檢查和非Bloom過濾器檢查之間的差異。

在此示例中，我們還将使用數量非常有限的位：僅1024。它将快速填充。填滿後，它将顯示出越來越多的誤報-随着誤報率填滿，您将看到響應時間增加。

該伺服器使用與以前相同的子產品，是以将

app.js

檔案設定為：

var
  async           =   require('async'),
  Bloom           =   require('bloom-redis'),
  bodyParser      =   require('body-parser'),
  express         =   require('express'),
  redis           =   require('redis'),
  
  app,
  client,
  filter,
  
  currentDataKey  = 'current-data',
  usedDataKey     = 'used-data';
  
app = express();
client = redis.createClient();

filter = new Bloom.BloomFilter({ 
  client    : client,
  key       : 'stale-bloom-filter',
  //for illustration purposes, this is a super small filter. It should fill up at around 500 items, so for a production load, you'd need something much larger!
  size      : 1024,
  numHashes : 20
});

app.post(
  '/',
  bodyParser.text(),
  function(req,res,next) {
    var
      used;
      
    console.log('POST -', req.body); //log the current data being posted
    console.time('post'); //start measuring the time it takes to complete our filter and conditional verification process
    
    //async.series is used to manage multiple asynchronous function calls.
    async.series([
      function(cb) {
        filter.contains(req.body, function(err,filterStatus) {
          if (err) { cb(err); } else {
            used = filterStatus;
            cb(err);
          }
        });
      },
      function(cb) {
        if (used === false) {
          //Bloom filters do not have false negatives, so we need no further verification
          cb(null);
        } else {
          //it *may* be in the filter, so we need to do a follow up check
          //for the purposes of the tutorial, we'll add a 150ms delay in here since Redis can be fast enough to make it difficult to measure and the delay will simulate a slow database or API call
          setTimeout(function() {
            console.log('possible false positive');
            client.sismember(usedDataKey, req.body, function(err, membership) {
              if (err) { cb(err); } else {
                //sismember returns 0 if an member is not part of the set and 1 if it is.
                //This transforms those results into booleans for consistent logic comparison
                used = membership === 0 ? false : true;
                cb(err);
              }
            });
          }, 150);
        }
      },
      function(cb) {
        if (used === false) {
          console.log('Adding to filter');
          filter.add(req.body,cb);
        } else {
          console.log('Skipped filter addition, [false] positive');
          cb(null);
        }
      },
      function(cb) {
        if (used === false) {
          client.multi()
            .set(currentDataKey,req.body) //unused data is set for easy access to the 'current-data' key
            .sadd(usedDataKey,req.body) //and added to a set for easy verification later
            .exec(cb); 
        } else {
          cb(null);
        }
      }
      ],
      function(err, cb) {
        if (err) { next(err); } else {
          console.timeEnd('post'); //logs the amount of time since the console.time call above
          res.send({ saved : !used }); //returns if the item was saved, true for fresh data, false for stale data.
        }
      }
    );
});

app.get('/',function(req,res,next) {
  //just return the fresh data
  client.get(currentDataKey, function(err,data) {
    if (err) { next(err); } else {
      res.send(data);
    }
  });
});

app.listen(8012);

由于使用浏覽器釋出到伺服器可能很棘手，是以讓我們使用curl進行測試。

curl --data “your data goes here" --header "Content-Type: text/plain" http://localhost:8012/

快速的bash腳本可用于顯示如何填充整個過濾器：

#!/bin/bash
for i in `seq 1 500`;
do
  curl --data “data $i" --header "Content-Type: text/plain" http://localhost:8012/
done

檢視填充或完整過濾器很有趣。由于這個很小，您可以使用

redis-cli

輕松檢視它。通過在添加項目之間從終端運作

redis-cli get stale-filter

，您将看到單個位元組增加。每個位元組的完整過濾器為

\xff

。此時，過濾器将始終傳回正值。

結論

布隆過濾器不是萬能的解決方案，但在正确的情況下，布隆過濾器可以為其他資料結構提供快速，高效的補充。一本書的用途是什麼，

console.time

console.timeEnd

記錄Bloom過濾器檢查和非Bloom過濾器檢查之間的差異。

在此示例中，我們還将使用數量非常有限的位：僅1024。它将快速填充。填滿後，它将顯示出越來越多的誤報-随着誤報率填滿，您将看到響應時間增加。

該伺服器使用與以前相同的子產品，是以将

app.js

檔案設定為：

javascript var async = require（'async'），Bloom = require（'bloom-redis'），bodyParser = require（'body-parser'），express = require（'express'），redis = require（' redis'），

應用，用戶端，過濾器，

currentDataKey ='目前資料'，usedDataKey ='已使用資料';

app = express（）; 用戶端= redis.createClient（）;

filter = new Bloom.BloomFilter（{client：client，key：'stale-bloom-filter'，//出于說明目的，這是一個超小的過濾器。應填充約500個項目，是以對于生産負荷，你需要更大的東西！size：1024，numHashes：20}）;

app.post（'/'，bodyParser.text（），function（req，res，next）{使用的var;

app.get（'/'，function（req，res，next）{//僅傳回新資料用戶端。get（currentDataKey，function（err，data）{if（err）{next（err）;} else { res.send（data）;}}）;}）;

app.listen（8012）; ```

由于使用浏覽器釋出到伺服器可能很棘手，是以讓我們使用curl進行測試。

curl --data “your data goes here" --header "Content-Type: text/plain" http://localhost:8012/

快速的bash腳本可用于顯示如何填充整個過濾器：

bash #!/bin/bash for i in `seq 1 500`; do curl --data “data $i" --header "Content-Type: text/plain" http://localhost:8012/ done

檢視填充或完整過濾器很有趣。由于這個很小，您可以使用

redis-cli

輕松檢視它。通過在添加項目之間從終端運作

redis-cli get stale-filter

，您将看到單個位元組增加。每個位元組的完整過濾器為

\xff

。此時，過濾器将始終傳回正值。

布隆過濾器不是萬能的解決方案，但在正确的情況下，布隆過濾器可以為其他資料結構提供快速，有效的補充。愛麗絲想

console.time

console.timeEnd

記錄Bloom過濾器檢查和非Bloom過濾器檢查之間的差異。

在此示例中，我們還将使用數量非常有限的位：僅1024。它将快速填充。填滿後，它将顯示出越來越多的誤報-随着誤報率填滿，您将看到響應時間增加。

該伺服器使用與以前相同的子產品，是以将

app.js

檔案設定為：

javascript var async = require（'async'），Bloom = require（'bloom-redis'），bodyParser = require（'body-parser'），express = require（'express'），redis = require（' redis'），

應用，用戶端，過濾器，

currentDataKey ='目前資料'，usedDataKey ='已使用資料';

app = express（）; 用戶端= redis.createClient（）;

app.post（'/'，bodyParser.text（），function（req，res，next）{使用的var;

app.get（'/'，function（req，res，next）{//僅傳回新資料用戶端。get（currentDataKey，function（err，data）{if（err）{next（err）;} else { res.send（data）;}}）;}）;

app.listen（8012）; ```

由于使用浏覽器釋出到伺服器可能很棘手，是以讓我們使用curl進行測試。

curl --data “your data goes here" --header "Content-Type: text/plain" http://localhost:8012/

快速的bash腳本可用于顯示如何填充整個過濾器：

bash #!/bin/bash for i in `seq 1 500`; do curl --data “data $i" --header "Content-Type: text/plain" http://localhost:8012/ done

檢視填充或完整過濾器很有趣。由于這個很小，您可以使用

redis-cli

輕松檢視它。通過在添加項目之間從終端運作

redis-cli get stale-filter

，您将看到單個位元組增加。每個位元組的完整過濾器為

\xff

。此時，過濾器将始終傳回正值。

布隆過濾器不是萬能的解決方案，但是在正确的情況下，布隆過濾器可以為其他資料結構提供快速，高效的補充，而無需圖檔或對話？

console.time

console.timeEnd

記錄Bloom過濾器檢查和非Bloom過濾器檢查之間的差異。

在此示例中，我們還将使用數量非常有限的位：僅1024。它将快速填充。填滿後，它将顯示出越來越多的誤報-随着誤報率填滿，您将看到響應時間增加。

該伺服器使用與以前相同的子產品，是以将

app.js

檔案設定為：

javascript var async = require（'async'），Bloom = require（'bloom-redis'），bodyParser = require（'body-parser'），express = require（'express'），redis = require（' redis'），

應用，用戶端，過濾器，

currentDataKey ='目前資料'，usedDataKey ='已使用資料';

app = express（）; 用戶端= redis.createClient（）;

app.post（'/'，bodyParser.text（），function（req，res，next）{使用的var;

app.get（'/'，function（req，res，next）{//僅傳回新資料用戶端。get（currentDataKey，function（err，data）{if（err）{next（err）;} else { res.send（data）;}}）;}）;

app.listen（8012）; ```

由于使用浏覽器釋出到伺服器可能很棘手，是以讓我們使用curl進行測試。

curl --data “your data goes here" --header "Content-Type: text/plain" http://localhost:8012/

快速的bash腳本可用于顯示如何填充整個過濾器：

bash #!/bin/bash for i in `seq 1 500`; do curl --data “data $i" --header "Content-Type: text/plain" http://localhost:8012/ done

檢視填充或完整過濾器很有趣。由于這個很小，您可以使用

redis-cli

輕松檢視它。通過在添加項目之間從終端運作

redis-cli get stale-filter

，您将看到單個位元組增加。每個位元組的完整過濾器為

\xff

。此時，過濾器将始終傳回正值。

Bloom過濾器不是萬能的解決方案，但是在正确的情況下，Bloom過濾器可以為其他資料結構提供快速，有效的補充。'，'a-christmas-carol'：'Marley死了：首先。，'metamorphosis'：“有一天早上，當Gregor Samsa從夢trouble以求的夢中醒來時，他發現自己躺在床上變成了可怕的害蟲。”，“ frankenstein”：“您會高興地聽到，一場災難并沒有帶來災難。您曾以如此邪惡的預兆看到的企業。”，“哈克貝利芬冒險”：“您不要

console.time

console.timeEnd

記錄Bloom過濾器檢查和非Bloom過濾器檢查之間的差異。

在此示例中，我們還将使用數量非常有限的位：僅1024。它将快速填充。填滿後，它将顯示出越來越多的誤報-随着誤報率填滿，您将看到響應時間增加。

該伺服器使用與以前相同的子產品，是以将

app.js

檔案設定為：

javascript var async = require（'async'），Bloom = require（'bloom-redis'），bodyParser = require（'body-parser'），express = require（'express'），redis = require（' redis'），

應用，用戶端，過濾器，

currentDataKey ='目前資料'，usedDataKey ='已使用資料';

app = express（）; 用戶端= redis.createClient（）;

app.post（'/'，bodyParser.text（），function（req，res，next）{使用的var;

app.get（'/'，function（req，res，next）{//僅傳回新資料用戶端。get（currentDataKey，function（err，data）{if（err）{next（err）;} else { res.send（data）;}}）;}）;

app.listen（8012）; ```

由于使用浏覽器釋出到伺服器可能很棘手，是以讓我們使用curl進行測試。

curl --data “your data goes here" --header "Content-Type: text/plain" http://localhost:8012/

快速的bash腳本可用于顯示如何填充整個過濾器：

bash #!/bin/bash for i in `seq 1 500`; do curl --data “data $i" --header "Content-Type: text/plain" http://localhost:8012/ done

檢視填充或完整過濾器很有趣。由于這個很小，您可以使用

redis-cli

輕松檢視它。通過在添加項目之間從終端運作

redis-cli get stale-filter

，您将看到單個位元組增加。每個位元組的完整過濾器為

\xff

。此時，過濾器将始終傳回正值。

Bloom過濾器不是萬能的解決方案，但在正确的情況下，Bloom過濾器可以為其他資料結構提供快速，有效的補充。如果您沒有讀過《湯姆·索亞曆險記》一書，就不會了解我。但是那個

console.time

console.timeEnd

記錄Bloom過濾器檢查和非Bloom過濾器檢查之間的差異。

在此示例中，我們還将使用數量非常有限的位：僅1024。它将快速填充。填滿後，它将顯示出越來越多的誤報-随着誤報率填滿，您将看到響應時間增加。

該伺服器使用與以前相同的子產品，是以将

app.js

檔案設定為：

javascript var async = require（'async'），Bloom = require（'bloom-redis'），bodyParser = require（'body-parser'），express = require（'express'），redis = require（' redis'），

應用，用戶端，過濾器，

currentDataKey ='目前資料'，usedDataKey ='已使用資料';

app = express（）; 用戶端= redis.createClient（）;

app.post（'/'，bodyParser.text（），function（req，res，next）{使用的var;

app.get（'/'，function（req，res，next）{//僅傳回新資料用戶端。get（currentDataKey，function（err，data）{if（err）{next（err）;} else { res.send（data）;}}）;}）;

app.listen（8012）; ```

由于使用浏覽器釋出到伺服器可能很棘手，是以讓我們使用curl進行測試。

curl --data “your data goes here" --header "Content-Type: text/plain" http://localhost:8012/

快速的bash腳本可用于顯示如何填充整個過濾器：

bash #!/bin/bash for i in `seq 1 500`; do curl --data “data $i" --header "Content-Type: text/plain" http://localhost:8012/ done

檢視填充或完整過濾器很有趣。由于這個很小，您可以使用

redis-cli

輕松檢視它。通過在添加項目之間從終端運作

redis-cli get stale-filter

，您将看到單個位元組增加。每個位元組的完整過濾器為

\xff

。此時，過濾器将始終傳回正值。

布隆過濾器不是萬能的解決方案，但在正确的情況下，布隆過濾器可以為其他資料結構提供快速，高效的補充。'，'sherlock-holmes冒險'：'緻福爾摩斯她永遠是女人。”，“弗雷德裡克·道格拉斯的生平叙述”：“我出生在希爾斯伯勒附近的塔克霍，距馬裡蘭州塔爾伯特縣的伊斯頓約十二英裡。”，“ the-prince'：“對人實行統治的所有州，所有權力都曾經是共和國或公國。”，“ tom-saw-sawyer冒險”：“ TOM！” };

app = express（）; 用戶端= redis.createClient（）;

filter = new Bloom.BloomFilter（{client：client，key：'3content-bloom-filter'，// Redis密鑰大小：2875518，//〜350kb //大小：1024，numHashes：20}）;

app.get（'/ show-content /：user'，function（req，res，next）{//我們将周遊contentIds，檢查它們是否在過濾器中。建議不要花大量時間在每個contentId上花費時間///但是，在這種情況下，contentId的數量很少/固定，并且我們的filter.contains函數很快，沒關系。var // creates在openingLines contentIds = Object.keys（openingLines）中定義的鍵的數組，//從URI使用者= req.params.user，擷取路徑的一部分，checkingContentId，found = false，done = false；

//由于filter.contains是異步的，是以我們使用異步庫執行循環async.whilst（//檢查函數，異步循環将在此結束函數（）{return（！found &&！done）;}， function（cb）{//從contentIds數組中擷取第一項checkingContentId = contentIds.shift（）;

app.listen（8011）; </ pre>

This is different than the previous two situations, in that false positives would not be okay. We'll be using the Bloom filter as a first line of defense. Given the properties of Bloom filters, we'll only know for certain that something isn't in the filter, so in this case we can go ahead and let the data in. If the Bloom filter returns that is probably in the filter, we'll do a check versus the actual data source.

So, what do we gain? We gain the speed of not having to check versus the actual source every time. In situations where the data source is slow (external APIs, pokey databases, the middle of a flat file), the speed increase is really needed. To demonstrate the speed, let's add in a realistic delay of 150ms in our example. We'll also use the

console.time

console.timeEnd

to log the differences between a Bloom filter check and a non-Bloom filter check.

In this example, we'll also use an extremely constrained number of bits: just 1024. It will fill up quickly. As it fills, it will show more and more false positives—you'll see the response time increase as the false positive rate fills up.

This server uses the same modules as before, so set the

app.js

file to:

```javascript var async = require('async'), Bloom = require('bloom-redis'), bodyParser = require('body-parser'), express = require('express'), redis = require('redis'),

app, client, filter,

currentDataKey = 'current-data', usedDataKey = 'used-data';

app = express(); client = redis.createClient();

filter = new Bloom.BloomFilter({ client : client, key : 'stale-bloom-filter', //for illustration purposes, this is a super small filter. It should fill up at around 500 items, so for a production load, you'd need something much larger! size : 1024, numHashes : 20 });

app.post( '/', bodyParser.text(), function(req,res,next) { var used;

app.get('/',function(req,res,next) { //just return the fresh data client.get(currentDataKey, function(err,data) { if (err) { next(err); } else { res.send(data); } }); });

app.listen(8012); ```

Since POSTing to a server can be tricky with a browser, let's use curl to test.

curl --data “your data goes here" --header "Content-Type: text/plain" http://localhost:8012/

A quick bash script can be used to show how filling up the entire filter looks:

bash #!/bin/bash for i in `seq 1 500`; do curl --data “data $i" --header "Content-Type: text/plain" http://localhost:8012/ done

Looking at a filling or full filter is interesting. Since this one is small, you can easily view it with

redis-cli

. By running

redis-cli get stale-filter

from the terminal between adding items, you'll see the individual bytes increase. A full filter will be

\xff

for every byte. At this point, the filter will always return positive.

Bloom filters aren't a panacea solution, but in the right situation, a Bloom filter can provide a speedy, efficient complement to other data structures.

翻譯自: https://code.tutsplus.com/articles/understanding-the-magic-of-bloom-filters-with-nodejs-redis--cms-25397

使用Node.js和Redis了解Bloom過濾器的魔力

建立

唯一的使用者名

新鮮内容

陳舊資料

結論

繼續閱讀

【python】【資料處理】畫多元資料分布圖

NOSQL安全攻擊

mybatis_入門程式Mybatis入門

mysql使用source指令導入.sql檔案

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

登入plsql 報錯 the account is locked --使用者被鎖

Effective Java 8:通用程式設計

SequoiaDB巨杉資料庫C++驅動概述

OOM三種類型

工廠模式-三種類型

【python】netconf協定對接管理裝置

「Python 網絡自動化」NETCONF —— Python 使用 NETCONF 管理配置 H3C 網絡裝置

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method

在python中建立excel并寫入