ブルームフィルタかカッコウハッシュか？質問する

Question

ブルームフィルターとカッコウフィルターは同様の状況で使用されますが、その背後には多くの違いがあり、通常、どちらがより良い選択であるかが決まります。

ブルームフィルタは、データベースエンジン、特に Apache Cassandra で内部的に使用されます。他の投稿者が述べたように、理由は、低速なセット操作のコストを削減するためです。基本的に、コストの高い「これはおそらく存在しないか、確実に存在しないか」という操作では、ブルームフィルタを使用して、実行されるチェックの数を減らすことができます。

今日の SaaS モデルのもう 1 つの一般的な例は、呼び出しごとに料金が発生するリモート REST サービスです。「このアドレスは無効ですか」などのバイナリ回答を持つ API 呼び出しでは、ブルームフィルターを使用して重複クエリを 90% 以上排除できます。ブルームフィルターとカッコウフィルターには誤検出があるため、「このアドレスは有効ですか」という逆操作には役立ちません。

覚えておくべき重要なことは、ブルームフィルターとカッコーフィルターには偽陰性がないということです。このため、これらのフィルターは「これは間違いなくスパムではないか、あるいはスパムかもしれない」などのチェックには役立ちますが、ユーザー権限のチェックなど、偽陽性が許容されない操作には役立ちません。この点では、概念的にはキャッシュの反対と考えることができます。ブルーム/カッコーフィルターとキャッシュはどちらも、ブール値の回答による高価な操作のコストを削減するために主に使用されますが、キャッシュには偽陽性がなく、ブルーム/カッコーには偽陰性がありません。

Cuckoo/Bloom の顕著な違いは次のとおりです。

組み合わせ。ブルームフィルターは、同じパラメーターで作成されている限り、効率的に結合できます。高速で、帯域幅もほとんど必要ありません。ブルームフィルターは大規模分散システムで頻繁に使用されるのは、このためです。ブルームフィルターの交換は高速です。カッコウフィルターは簡単に構成できないため、このような状況ではあまり役に立ちません。
誤検出率。カッコウフィルターの方がスペース効率が良いです。両方の構造の多くの使用例は、低レベルのネットワークに重点が置かれています。貧弱なハードウェアでは、同じ誤検出率でカッコウフィルターの効率が約 40% 高いことが重要な場合があります。C++ のリファレンス実装では、各バケット内のアイテムを並べ替えてスペースをさらに節約し、バケット内のアイテムの位置を利用してより小さなフィンガープリントを保存します。後で説明する追加のライブラリ (私のライブラリを含む) では、この処理は行われないようです。誰かが私のライブラリを使用する場合は、追加するかもしれません :)。
一定の偽陽性率。ブルームフィルターは、設計サイズを超えると、偽陽性率が漸近的に悪化します。アイテムを永久に挿入し続けることはできますが、最終的には偽陽性率がほぼ 100% になります。Cuckoo フィルターは Cuckoo ハッシュに基づいているため、挿入が実際に失敗する容量が設定されています。ランダムでないアイテムハッシュを繰り返し挿入すると、Cuckoo フィルターは、設計された充填レベルよりはるかに前に挿入に失敗する可能性があります。
速度。これは主観的でハードウェアに大きく依存しますが、Cuckoo フィルターは平均的に高速です (私の経験では)。ほとんどの Bloom フィルター設計ではハッシュ関数を 2 回実行します。特にセキュアハッシュ関数を使用する場合、挿入されたアイテムを 1 回だけハッシュする Cuckoo フィルターと比較して、これが大きなハンディキャップになる可能性があります。私が見たコードでは、Bloom フィルターと Cuckoo フィルターにさまざまなハッシュ関数が使用されています。Google の Guava Bloom は Murmur3 を使用し、他の多くの実装は SHA1 などを使用しています。ハッシュ衝突がユースケースで悪用される可能性がある場合は、ライブラリがセキュアハッシュを使用していることを確認してください。重要なのは、Bloom フィルターの挿入にはほぼ一定時間かかるのに対し、Cuckoo フィルターの平均時間は一定であるということです。Cuckoo フィルターが容量の数パーセント以内になると、挿入速度が大幅に低下します。それでも、挿入速度のみが遅くなり、他のすべての操作は平均時間が一定です。
柔軟性。ブルームフィルターは挿入と包含のみをサポートします。カッコウフィルターは、削除と限定カウントもサポートします。リファレンスデザインでは、カッコウフィルターはアイテムが挿入された回数を最大 7 回まで判断できます。ブルームフィルターは、はい/いいえのみを判断できます。カッコウフィルターは挿入されたアイテムの削除もサポートしており、これはブルームに比べて多くのユースケースで大きな利点です。ブルームフィルターを使用する場合、古いアイテムを削除できないため、フィルターが「いっぱい」になったとき (推定される誤検出率がしきい値を超えたとき) にフィルターを最初から再作成するのが一般的です。挿入が失敗し始めたときにカッコウフィルターでフィルターの再構築が依然として発生するため、ユースケースによってはこれが意味をなさない場合があります。状況によっては、再構築する代わりにアイテムを削除してフィルター制限内に収めることができるため、カッコウフィルターの方が便利です。
サポート。Cuckoo フィルターは、多くの言語では存在しない新しい安定したライブラリです。

ブルームフィルタの最大の利点は、ほとんどの言語でより成熟したライブラリサポートがあることです。ブルームフィルタの背後にある数学も、科学者によってよく理解されています。カッコウフィルタの特性のほとんどは経験的に決定されていますが、ブルームフィルタには確固とした数値的根拠があります。そのため、カッコウフィルタは、ほとんどの状況でカッコウフィルタの方がパフォーマンスが優れていることが実験的証拠で示されていますが、パフォーマンスの検証が必要なリアルタイムシステムやクリティカルシステムには適していません。

恥知らずな宣伝: 私は Java 用の Cuckoo フィルターライブラリの開発者です。カッコウフィルター4J論文で使用されているバケットセミソートが欠落しているため、スペース効率はリファレンス実装よりもやや低くなります。プロジェクトの readme には、私が知っている他の実装へのリンクがあります。どの構造が優れているかは、使用例によって異なりますが、主に、使用している言語に堅牢な Cuckoo フィルター実装が存在するかどうかによって決まります。

Cuckoo/Bloom フィルターを本番環境で使用する前に、必ずソースを確認してください。私は独自のフィルターを作成する前にさまざまなライブラリを読みましたが、その多くには 32 ビットの基になる配列や明らかなパフォーマンスの問題が原因で、サイレントサイズ制限がありました。ほとんどはテストがまったくありませんでした。Google の Guava Bloom 実装は、コードの品質とテストが断然優れていました (64 ビット配列の制限もサポートしています)。Guava Bloom の唯一の欠点は、安全なハッシュ関数を使用するオプションがなく、マルチスレッドではないことです。

実稼働システムでは、速度を上げるためにマルチスレッドが必要な場合があります。Guava の Bloom に対する解決策は、スレッドごとに異なるフィルターを作成し、それらを時々組み合わせることです。Cuckoo フィルターは組み合わせることができないため、Cuckoo フィルターライブラリに同時スレッドを追加しました。私が知っている他のフィルターは、スレッドセーフではないか、同時実行ではありません。

Answer 1