ユーザー サインアップ ページでユーザー名が指定された場合、それが既に登録されているかどうかをどのように判断しますか?

インデックス付きデータベースへのクエリは役に立ちますが、速度が遅く、ネットワーク呼び出しが発生します。

スピードアップするために、登録されたユーザー名のリストを Redis のようなキーと値のストアにキャッシュできます。

ただし、これは何百万ものレコードをキャッシュし、メモリ フットプリントを 2 倍にすることを意味します。

この一見些細な問題で、どうすればもっとうまくやれるでしょうか?

ブルーム フィルターが答えかもしれません。チェックしてみましょう。

ブルームフィルターとは？

ブルーム フィルターは、次の 1 つの簡単な質問に答えます。

特定のセットに要素が存在するか?

ブルーム フィルターは、確率的なデータ構造です。上記の質問を考えると、次のいずれかの回答が出力されます

• おそらくはい
• 100%いいえ

その最大の利点は、一定の時間と空間でこれを行うことです。

それはどのように機能しますか？

ブルーム フィルターは 2 つのコンポーネントで構成されます

• N サイズのビット配列
• いくつかのハッシュ関数

最初に、すべてのビットがゼロに設定された N サイズのビット配列として初期化されます。今のところ、配列の長さを 10 と仮定しましょう。

アイテムの追加

アイテムの追加は簡単です

• 「虎」というアイテムは、ハッシュ関数を使用してハッシュされます
• 生成されたハッシュは、境界付きインデックスを取得するために配列の長さによって変更されます
• 次に、ビット配列のインデックスが 1 に設定されます。

アイテムの追加と同様に、ハッシュ関数を使用して要素をハッシュし、それを変更して境界付きインデックスを取得します。

出力は次のように評価されます。

• ビット配列のインデックス値が 0 の場合、アイテムはセットにありません。
• それ以外の場合、アイテムはおそらくセットに含まれています

ブルームフィルターの保管

ブルーム フィルターを配列として格納する代わりに、そのビット表現を 10 進数に変換できます。

たとえば、1001119 を含む配列を変換してキャッシュに格納できます。

リストがあまり頻繁に変更されない場合、サーバーは 10 進数をクライアントに送信して、クライアント側で検証を行うことができます。

もっとうまくやれるでしょうか？

ハッシュ関数が "tiger" と "cow" の両方のインデックス 1 を出力する場合、"cow" がセットに含まれているかどうかを確認すると、そうでなくてもYes という答えが得られます。

次の解決策により、誤検知の可能性を減らすことができます。

• 配列の長さを増やす
• ハッシュ関数の数を増やす

1 つのインデックスの代わりに、複数のハッシュを使用して複数のインデックスを取得できます。

アイテムを追加すると、取得したすべてのインデックスが 1 に設定されます。

すべてのインデックスが 1 に設定されている場合にのみ、アイテムはおそらくセット内にあると主張されます。

これらの方法を活用することで、誤検知の可能性を大幅に下げることができました。

アプリケーション

実際の例をいくつか見てみましょう。

ユーザー サインアップ フローにユーザー名が存在するかどうかを確認する

• ユーザー名が作成されると、キー値ストアに格納されているブルーム フィルターにユーザー名が追加されます。
• ユーザーがユーザー サインアップ ページでユーザー名をキー入力すると、サーバーはまずブルーム フィルターにクエリを実行します。
• ユーザー名がブルーム フィルターに含まれていない場合、サーバーは即座にエラーをクライアントに返します。
• それ以外の場合、サーバーはデータベースでクエリとクロスチェックを行います。

• Medium は、ユーザーごとにブルーム フィルターを維持します。
• 記事を推奨する前に、Medium は記事 ID がユーザーのブルーム フィルターに存在するかどうかを確認します。
• ブルーム フィルターに確実に含まれていない記事は、ユーザーに推奨されます。

• URL にアクセスすると、Chrome はまずその URL が悪意のあるリストに含まれているかどうかを検証します。
• 毎回 Google サーバーにクエリを実行する代わりに、Google は事前に定義された悪意のあるリストを使用してブルーム フィルターを構築し、それをブラウザーに送信します。
• ブラウザーは、Web サイトにアクセスする前に URL をハッシュし、ブルーム フィルターと照合します。

誤検知が発生する可能性がありますが、ブルーム フィルターは、項目が確実にリストに含まれていないかどうかを確認したい場合に便利です。

時間と空間の両方で効率が高いため、フィルタリングの最初のレイヤーとして使用できます。

これがお役に立てば幸いです。また次回お会いしましょう。