Clever Geek Handbook

Web開発者向けのブルームフィルター

ハブラーでは、すでにブルームフィルターについて多くが語られています 。 これは、要素自体を保存せずに要素がセットに属しているかどうかを確認できるデータ構造であることを思い出させてください。 偽陽性の可能性がありますが、否定的な答えは常に信頼できます。 精度が1％のフィルターでは、要素ごとに数ビットしか必要ありません。



この構造は、データウェアハウスへのクエリの数を制限するためによく使用され、明らかに存在しない要素の呼び出しを遮断します。 さらに、一意のイベント、ユーザー、ビューなどの数のおおよその計算に使用できます。 興味深いアプリケーションのその他の例。



ただし、Web開発者がブルームフィルターを使用するのを思いとどまらせる可能性のある困難があります。



保管


すべてのサーバー上のWebアプリケーションのすべてのインスタンスは、大きなビットベクトル内の複数のビットを迅速に変更またはチェックできる、いくつかの共通データセットにアクセスできる必要があります。 さらに、データを安全にディスクに保存する必要があります。



ハッシング


実際にブルームフィルターの理論上の操作パラメーターに近づけるには、ソース要素からのハッシュを使用して正確な作業を行う必要があります。 長さがmビットc kハッシュ関数のフィルターでは、元の要素から0〜m -1 に一様に分布するk個の独立した値の形成が必要です。



私がよく見たほとんどの実装は32ビットのMurmurhashを使用し、そのハッシュの数に応じて、連続する各ハッシュにソルトを追加します。 このアプローチが偽陽性の漸近確率を増加させないという証拠はありません。



さらに、32ビットハッシュが使用される場合、これにより、フィルターサイズの上限が512メガバイトに設定されます。 これは小さくはありませんが、それほど多くはありません。特に、偽陽性の割合が非常に低い場合、および/またはフィルター内の要素の数が非常に多い場合に必要です。



私の意見では、希望する範囲の値を持つ任意の数のハッシュ関数を取得する方法は多くないため、元のメッセージの情報エントロピーのみを使用します。

  1. 1つのかなり広い関数の出力を等しい部分にカットします。 この場合、関数は有用なビットを破棄する必要がないように、ビット単位のパラメトリック出力幅を持っている必要があります。
  2. 可変幅h 1およびh 2の2つの独立したハッシュ関数のみを持ち、式h 1 + i * h 2 （関数値の数のモジュロ）に従ってg iの導関数を形成します。 ここで最近この方法について学びました 。




性能


この設計がストレージ要求を抑止するアプリケーションを見つけるためには、保護されたストレージより少なくとも1桁速く応答する必要があります。



ほとんどの場合、Web開発者が操作するインタープリター言語で実装すると、これが難しくなる可能性があり、最も重要なことは、コアではない不要なタスクです。



提案されたソリューション



ブルームフィルターをWebアプリケーションのインフラストラクチャに簡単に統合できるソリューションを提供したいと思います。



これは、ブルームフィルターをRAMとディスクに保存するコンテナーサーバーです。 フィルター操作へのアクセスは、HTTPを介して提供されます。



ストレージの永続性は、デーモンをブロックしないスナップショットによって提供されます。 スナップショットは、重要な名前で一時ファイルに書き込まれ、記録の終了後にのみ古いスナップショットを置き換えます。 サーバーがシャットダウンし、プロセスがシグナルUSR1を受信すると、タイマーでデータセットの保存が行われます。



ハッシュ生成アルゴリズムは、長さk * wビットのMD6ハッシュをwビットのkキーにスライスします。 MD6のラウンド数は標準です。



HTTPインターフェースは、開発者側での統合を容易にするために選択されました。ほとんどの開発プラットフォームは、同期、非同期、並列（curl-multi）HTTP要求を実装するツールを開発しました。 インターフェースが単純であるにもかかわらず、HTTP標準のすべての利点を採用し、単一の接続内で要求をパイプライン化できます。



私が提供するアプリケーションは、実稼働システムで長い間テストされており、安定していると見なすことができます。



サーバーはlibevent2を使用してCで記述されています。 インテル®Pentium®プロセッサーG4400 @ 3.30GHzで、アプリケーションは300バイトの要素のチェックと追加に関してApache Benchmarkで〜35000 RPSを示します。



サポートおよびテストされたプラットフォーム：





例


デフォルトのパラメーター（1 GB、10キー-偽陽性0.1％の確率で500,000,000個の要素）を使用してデーモンを起動します。 

 $ bloom habrahabr.snap
スペースの作成...
新しいファイルストレージの初期化...
スナップショットを保存しています...
初期スナップショットが書き込まれました。




チェック項目： 

 $ curl http：// localhost：8889 / check？e = Hello％20Habr％21
欠落




アイテムを追加： 

 $ curl http：// localhost：8889 / add？e = Hello％20Habr％21
追加されました




もう一度確認してください： 

 $ curl http：// localhost：8889 / check？e = Hello％20Habr％21
現在




可用性を確認し、1つのリクエストを追加します。 

 $ curl http：// localhost：8889 / checkthenadd？e =存在しない
欠落
 $ curl http：// localhost：8889 / checkthenadd？e =存在しない
現在




代替ソリューション





アプリケーション側で動作し、Redisの共通データを含むライブラリが存在します。 それらは、 SETBIT



およびGETBIT



を使用してRedisビットマップのビットを操作しGETBIT



。



それに比べて、それらの利点：



短所：



More articles:


All Articles