Node.js と Redis を使用してブルーム フィルターの威力を探る

適切な使用例では、ブルーム フィルターは魔法のように見えます。これは大胆な発言ですが、このチュートリアルでは、この奇妙なデータ構造、それを最大限に活用する方法、そして Redis と Node.js を使用したいくつかの実践的な例について説明します。

ブルーム フィルターは確率的な一方向のデータ構造です。この文脈では「フィルター」という単語は混乱を招く可能性があります。フィルターは動詞である能動的なものを意味しますが、ストレージである名詞と考えるほうが簡単かもしれません。単純なブルーム フィルターを使用すると、次の 2 つのことができます:

1. 項目を追加します。
2. アイテムが以前に 追加されていないかを確認します。

これらは理解しておくべき重要な制限です。アイテムを削除したり、ブルーム フィルターにアイテムをリストしたりすることはできません。さらに、アイテムが過去にフィルターに追加されたかどうかを判断することはできません。ここで、ブルーム フィルターの確率的な性質が関係します。偽陽性は発生する可能性がありますが、偽陰性は発生しません。フィルターが正しく設定されていれば、誤検知の可能性は非常に低くなります。

ブルーム フィルターには、削除や拡大縮小などの追加機能を追加するバリアントが存在しますが、複雑さと制限も追加します。バリエーションに進む前に、まず単純なブルーム フィルターを理解することが重要です。この記事では、単純なブルーム フィルターのみを紹介します。

これらの制限により、固定サイズ、ハッシュベースの暗号化、高速検索など、多くの利点が得られます。

ブルーム フィルターを設定するときは、そのサイズを指定する必要があります。このサイズは固定されているため、フィルター内に 1 個または 10 億個の項目がある場合でも、指定されたサイズを超えることはありません。フィルタに項目を追加すると、誤検知の可能性が高くなります。小さいフィルターを指定すると、大きいフィルターを使用した場合よりも偽陽性率が速く増加します。

ブルーム フィルターは、一方向ハッシュの概念に基づいて構築されています。パスワードを正しく保存するのと同じように、ブルーム フィルターはハッシュ アルゴリズムを使用して、渡されたアイテムの一意の識別子を決定します。ハッシュは本質的に不可逆であり、一見ランダムな文字列で表されます。したがって、誰かがブルーム フィルターにアクセスしたとしても、直接的には何も明らかになりません。

最後に、ブルーム フィルターは高速です。この操作では、他の方法に比べて比較の回数がはるかに少なく、メモリに簡単に保存できるため、パフォーマンスに影響を与えるデータベース ヒットを防ぐことができます。

ブルーム フィルターの制限と利点を理解したところで、ブルーム フィルターを使用できるいくつかの状況を見てみましょう。

＃＃＃設定＃＃＃

Redis と Node.js を使用したブルーム フィルターについて説明します。 Redis はブルーム フィルターの記憶媒体であり、高速でメモリ内にあり、実装をより効率的に行う特定のコマンド (

GETBIT

、

SETBIT) を備えています。システムに Node.js、npm、Redis がインストールされていると仮定します。この例が正しく動作するには、Redis サーバーが localhost のデフォルト ポートで実行されている必要があります。 このチュートリアルでは、フィルターを最初から実装するのではなく、フィルターを最初から実装します。代わりに、npm で事前に構築されたモジュール Bloom-redis の実用的な使用に焦点を当てます。 bloom-redis には、add

、

contains、clear という非常に簡潔なメソッドのセットがあります。 前述したように、ブルーム フィルターではアイテムの一意の識別子を生成するためにハッシュ アルゴリズムが必要です。 Bloom-redis はよく知られた MD5 アルゴリズムを使用しており、ブルーム フィルターには適していない可能性がありますが、正常に機能します (少し遅く、少しやりすぎです)。

一意のユーザー名

ユーザー名、特に URL 内でユーザーを識別するものは一意である必要があります。ユーザーがユーザー名を変更できるアプリケーションを構築する場合、ユーザー名の混乱や攻撃を避けるために、決して使用されないユーザー名が必要になる場合があります。

ブルーム フィルターを使用しない場合、これまでに使用されたすべてのユーザー名を含むテーブルを参照する必要があり、大規模になると法外なコストがかかる可能性があります。ブルーム フィルターを使用すると、ユーザーが新しい名前を採用するたびに項目を追加できます。ユーザーがユーザー名が使用されているかどうかを確認するときに必要なのは、ブルーム フィルターを確認することだけです。要求されたユーザー名が以前に追加されたことがあるかどうかを確実に知ることができます。実際にはユーザー名が取得されていないのに、フィルターがユーザー名が取得されたと誤って返す場合がありますが、これは単なる予防策であり、実際の害はありません (ユーザーが「k3w1d00d47」を宣言できない可能性があることを除けば) .

これを説明するために、Express を使用して高速 REST サーバーを構築してみましょう。まず、

package.json

ファイルを作成し、次のターミナル コマンドを実行します。

npm install Bloom-redis --save

npm install Express --save

npm install redis --save

bloom-redis のデフォルトのオプション サイズは 2 MB に設定されています。注意して間違っていますが、かなり大きいです。ブルーム フィルターのサイズの設定は非常に重要です。大きすぎるとメモリを浪費し、小さすぎると誤検知率が高くなりすぎます。サイズの決定に必要な計算は複雑であり、このチュートリアルの範囲を超えていますが、幸いなことに、教科書を解読することなくその仕事を行うブルーム フィルター サイズ計算ツールがあります。

ここで、app.js を次のように作成します:

リーリー

このサーバーを実行するには: 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 ユーザー名-bloom-filter。

ここで、1 つの項目については、

338622 と読み取られるはずです。

次に、

/save ルートを使用してさらにユーザー名を追加してみます。好きなだけ試すことができます。

寸法を再度確認すると、寸法がわずかに増加していることがわかりますが、追加するたびに増加しているわけではありません。興味がありますよね？内部的には、ブルーム フィルターは、username-bloom に格納されている文字列内の異なる位置に個々のビット (1/0) を設定します。ただし、これらは連続していないため、インデックス 0 にビットを設定し、次にインデックス 10,000 にビットを設定すると、その間のビットはすべて 0 になります。実際の目的では、最初に各操作の正確な仕組みを理解することは重要ではありません。これは正常であり、指定した以上のデータを Redis に保存することは決してないことだけを理解してください。

新鮮なコンテンツ

Web サイト上の新鮮なコンテンツはユーザーを再訪させる可能性があります。では、毎回新しいコンテンツをユーザーに表示するにはどうすればよいでしょうか?従来のデータベース アプローチを使用すると、ユーザー識別子とストーリー識別子を含むテーブルに新しい行を追加し、コンテンツを表示することに決めたときにテーブルをクエリします。ご想像のとおり、データベースは、特にユーザーとコンテンツが増加するにつれて、非常に急速に拡大します。

この場合、偽陰性の影響 (未表示のコンテンツが表示されないなど) は非常に小さいため、ブルーム フィルターが実行可能なオプションになります。一見すると、各ユーザーにブルーム フィルターが必要だと思うかもしれませんが、ユーザー識別子とコンテンツ識別子の単純な連結を使用し、その文字列をフィルターに挿入します。このようにして、すべてのユーザーに対して単一のフィルターを使用できます。

この例では、コンテンツを表示する別の基本的な Express サーバーを構築しましょう。ルート

/show-content/any-username (any-username は URL セーフな値です) にアクセスするたびに、サイトが終了するまで新しいコンテンツが表示されます。中身が空っぽ。この例では、コンテンツはプロジェクト グーテンベルクの書籍トップ 10 の最初の行です。

別の npm モジュールをインストールする必要があります。ターミナルから実行します。

npm install async --save

新しい app.js ファイル:

リーリー

開発ツールのラウンドトリップ時間に細心の注意を払うと、ユーザー名を使用して単一のパスをリクエストする回数が増えるほど、時間がかかることがわかります。フィルターのチェックには一定の時間がかかりますが、この場合はさらに多くのアイテムの存在をチェックしています。ブルーム フィルターで伝えられる内容は限られているため、各項目の存在をテストすることになります。もちろん、この例では非常に単純ですが、何百ものプロジェクトをテストするのは非効率です。

古いデータ

この例では、POST 経由で新しいデータを受け取り、(GET リクエストを使用して) 現在のデータを表示するという 2 つのことを実行する小規模な Express サーバーを構築します。新しいデータがサーバーに POST されると、アプリケーションはそのデータがフィルターに存在するかどうかを確認します。存在しない場合は Redis のコレクションに追加します。存在しない場合は null を返します。 GET リクエストは Redis からそれを取得し、クライアントに送信します。

これは最初の 2 つの状況とは異なり、誤検知は許可されません。ブルームフィルターを防御の第一線として使用します。ブルーム フィルターの特性を考慮すると、フィルター内に何かが存在しないことのみを確認できるため、この場合はデータを入力し続けることができます。ブルーム フィルターがフィルター内にある可能性のあるデータを返した場合は、実際のデータ ソースと照合します。

那么，我们得到了什么？我们获得了不必每次都检查实际来源的速度。在数据源速度较慢的情况下（外部 API、小型数据库、平面文件的中间），确实需要提高速度。为了演示速度，我们在示例中添加 150 毫秒的实际延迟。我们还将使用 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);

由于使用浏览器 POST 到服务器可能会很棘手，所以让我们使用curl 来测试。

curl --data“您的数据放在这里”--header“内容类型：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 。此时，过滤器将始终返回正值。

结论

布隆过滤器并不是万能的解决方案，但在适当的情况下，布隆过滤器可以为其他数据结构提供快速、有效的补充。

如果您仔细注意开发工具中的往返时间，您会发现使用用户名请求单个路径的次数越多，所需的时间就越长。虽然检查过滤器需要固定的时间，但在本例中，我们正在检查是否存在更多项目。布隆过滤器能够告诉您的信息有限，因此您正在测试每个项目是否存在。当然，在我们的示例中，它相当简单，但测试数百个项目效率很低。

以上がNode.js と Redis を使用してブルーム フィルターの威力を探るの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。