より包括的な Golang バージョンのカッコー フィルターを実装する方法
- 藏色散人転載
- 2021-03-11 11:23:112908ブラウズ
以下は go 言語 チュートリアル コラムで紹介されています。より包括的な Golang バージョンの cuckoo フィルターを実装しました。お役に立てば幸いです。困っている友達へ。
「値が巨大なセットに含まれるかどうかを判断する」 (以下、総称してセット メンバーシップ テストと呼びます) は、一般的なデータ処理の問題です。過去の経験では、特定の誤検知率が許容される場合、ブルーム フィルターが第一の選択肢でしたが、現在はより良い選択肢、カッコー フィルターが用意されています。
最近のビジネスではフィルターを使用する必要があります。検索した結果、このシナリオではカッコー フィルターの方がコスト効率が高く、ブルーム フィルターよりも優れていることがわかりました。
最終的なテクノロジーの選択を決定するために、元の論文を読みました。その後、cuckoo フィルターを使用することに決めたとき、golang の包括的な実装がほとんどないことがわかりました。現在、GitHub 上でいくつかの高評価の実装が公開されています。いくつかの欠陥があり、スペース使用率を最大化できなかったため、元の論文とその論文の元の C 実装を参照して、Golang ライブラリのバージョンを移植して最適化しました。
コード アドレスはここにあります。スター付け、使用、貢献、デバッグを歓迎します: github.com/linvon/cuckoo-filter
cuckoo filter
cuckooフィルタに関する紹介記事はインターネット上に多数ありますので、ここではあまり詳しくは説明しませんが、以下の内容につながる要点のみを述べます
さらに詳しく知りたい場合は、元の論文を参照するか、私の中国語翻訳版をチェックしてください。
カッコーフィルターとは何ですか?
はカッコー ハッシュ アルゴリズムに基づいて実装されたフィルターであり、本質的にはストレージ アイテムのハッシュ値を格納するカッコー ハッシュ テーブルです。
ブルーム フィルターを理解している場合は、ブルーム フィルターの原理が、複数のハッシュ メソッドを使用してストレージ アイテムのさまざまなハッシュをビット配列にマッピングし、クエリ中にこれらのビットをチェックして存在するかどうかを判断することであることがわかるはずです。
カッコー フィルターは、ストレージ アイテムをハッシュし、そのハッシュ値から特定の桁数を取り出し、配列に格納します。クエリを実行すると、同じ桁数のハッシュが配列内に存在するかどうかが判断されます。
カッコーフィルターを選ぶ理由?
これらはハッシュ値も保存し、本質的にはマルチビット ハッシュを保存します。
まず、カッコー ハッシュ テーブルはよりコンパクトなので、より多くのスペースを節約できます。
- #2 番目の理由は、クエリの際、ブルーム フィルターは複数のハッシュに対してさまざまなハッシュ関数を使用するのに対し、カッコー フィルターは 1 つのハッシュしか必要としないため、クエリ効率が非常に高いということです
- 3 番目に、cuckoo フィルターは削除をサポートしますが、Bloom フィルターは削除をサポートしません
- と比較して、カッコーフィルタはバックアップ候補バケット方式を採用しており、位置と格納値によるXOR演算により候補バケットと優先バケットを取得できます。バケットのサイズは 2 の指数倍数である必要があります。
- ブルーム フィルターが挿入されると、ハッシュが計算され、ビットが直接書き込まれますが、カッコー フィルターでは現在位置が次のように表示される場合があります。フィンガープリントは、この時点で、保存されているアイテムを候補バケットにキックする必要がありますが、バケットがいっぱいになるにつれて、競合の可能性がますます大きくなり、挿入時間がますます長くなります。したがって、その挿入パフォーマンスはブルーム フィルタリングと比較されますが、フィルタは非常に貧弱です
- 重複要素の挿入: ブルーム フィルタは重複要素の挿入には効果がなく、既存のビットをリセットするだけです。カッコー フィルターは既存の値を追い出すため、繰り返される要素の挿入には上限があります。
- カッコー フィルターの削除は完全ではありません。繰り返しの挿入には上記の制限があり、関連する問題が発生します: 削除は同じハッシュ値が一度挿入された場合にのみ完全に完了します。要素が挿入されずに削除された場合、誤った削除が発生する可能性があり、これは誤検出率と同じ理由です。要素が複数回挿入されます。その場合、各削除では 1 つの値のみが削除されます。要素が削除される前に要素が何回挿入されたかを把握するか、削除が失敗するまでループで削除を実行する必要があります。
実践ガイド
詳細な実装
まず、カッコー フィルターの概念について説明しましょう。フィルターは多くのバケットで構成されています。各バケットには、挿入されたアイテムのハッシュ値が格納されます。このハッシュ値には、固定桁数のみが格納されます。
フィルターには n 個のバケットがあり、バケットの数は保存されるアイテムの数に基づいて計算されます。ハッシュ アルゴリズムを通じて、アイテムをどのバケットに保存するかを計算できます。さらに、ハッシュ アルゴリズムを追加するたびに、アイテムの候補バケットを生成できます。挿入が繰り返されると、現在保存されているアイテムが候補バケットに追加されます。 入る。理論的には、ハッシュ アルゴリズムの数が増えるほどスペースの使用率が高くなりますが、実際のテストでは、k=2 のハッシュ関数を使用して 98% の使用率を達成しました。
各バケットには複数のフィンガープリントが保存されます。これはバケットのサイズによって異なります。異なるフィンガープリントが同じバケットにマッピングされる場合があります。バケットが大きいほどスペースの使用率は高くなりますが、同時にクエリごとに同じバケットでより多くのフィンガープリントがスキャンされるため、誤検知が発生する確率が高くなります。保存された指紋の数を減らして競合率を減らし、誤検知率を維持します。
この論文では、カッコーフィルターを実装するために必要ないくつかのパラメータが言及されていますが、主に
- ハッシュ関数の数 (k): ハッシュの数、2 つで十分です
- バケット サイズ (b): 各バケットに保存されるフィンガープリントの数 #フィンガープリント サイズ (f): 各フィンガープリント保存キーのハッシュ値のビット数
- #論文を詳しく読んでください。第 5 章では、著者は実験データに基づいて、最適な構築パラメータを選択する方法を説明しています。次の結論が得られます。
- フィルターの合計サイズが一定に保たれる場合、バケットが大きいほど負荷率は高くなりますつまり、スペース使用率が高くなります。高いですが、各バケットに保存されているフィンガープリントが多いほど、クエリ中に競合が発生する可能性が高くなります。同じ誤検出率を維持するには、バケットが大きくなるほど、必要なフィンガープリントも大きくなります
- 上記の理論的根拠に基づいて、得られる関連実験データは次のとおりです。
- 偽陽性率 r を保証するには、 $2b/2 ^f\leq r$ を保証する必要があり、その場合、フィンガープリント f のサイズはおよそ $f ≥ log_2(2b/r)=log_2(1/r) となります。 log_2(2b)$ の場合、各項目の償却コストは $C ≤ [log_2( 1/r) log_2(2b)]/α$
- 実験データは、r>0.002 の場合を示しています。バケットあたり 2 つのエントリは、バケットあたり 4 つのエントリを使用するよりもわずかに良い結果を生成します。r が 0.00001
- セミソート バケットを使用すると、ストレージを 1 ビット削減できる各ストレージ アイテムのスペースですが、b=4 のフィルターにのみ作用します
:
最初に 2 つのハッシュ関数を使用します。これで十分であり、十分なスペース使用率を実現できます。必要な誤検知率に応じて、使用するバケット サイズを決定できます。もちろん b の選択は絶対的なものではありません。r>0.002 の場合でも、b=4 を使用して半ソート バケットを有効にすることができます。次に、b に基づいて目標の偽陽性率を達成するために必要な f のサイズを計算し、すべてのフィルター パラメーターを決定します。上記の結論をブルーム フィルターの各項目の $1.44log_2(1/r)$ と比較すると、半並べ替えが有効な場合、r
いくつかの高度な説明
ハッシュ アルゴリズムの最適化2 つのハッシュ アルゴリズムが必要であると指定しましたが、実際には実装では、代替バケット計算方法が論文で言及されているため、ハッシュ アルゴリズムを使用するだけで十分です。2 番目のハッシュ値は、最初のハッシュ値とその場所に保存されているフィンガープリントによって XOR 計算できます。指紋のハッシュと位置のハッシュを別々に計算する必要があることが心配な場合は、1 つのアルゴリズムを使用して 64 ビットのハッシュを作成するだけで済みます。上位 32 ビットは位置の計算に使用され、下位の 32 ビットは位置の計算に使用されます。フィンガープリントの計算に使用される 32 ビット。
b=4 の場合にのみ半ソートされたバケットを使用できるのはなぜですか?ハーフソートの本質は、各指紋の 4 桁を取得することです。4 桁は 16 進数で表現できます。b 個の指紋の 4 桁の格納は b 16 と表現できます。考えられるすべての基数を順番に並べると、それらの位置にインデックスを付けて実際に格納された値を取得することで、対応する配置を見つけることができます。
次の関数を通じてすべての状況タイプの数を計算できます
func getNum(base, k, b, f int, cnt *int) {
for i := base; i < 1<<f; i++ {
if k+1 < b {
getNum(i, k+1, b, f, cnt)
} else {
*cnt++
}
}}func getNextPow2(n uint64) uint {
n--
n |= n >> 1
n |= n >> 2
n |= n >> 4
n |= n >> 8
n |= n >> 16
n |= n >> 32
n++
return uint(n)}func getNumOfKindAndBit(b, f int) {
cnt := 0
getNum(0, 0, b, f, &cnt)
fmt.Printf("Num of kinds: %v, Num of needed bits: %v\n", cnt, math.Log2(float64(getNextPow2(uint64(cnt)))))}
b=4 の場合、合計 3786 個の順列があり、これは 4096、つまり 12 ビットよりも少なくなります。すべての置換インデックスを保存するために使用できます。すべてのフィンガープリントを直接保存する場合、4X4=16 ビットが必要となり、4 ビットが節約されます。つまり、フィンガープリントごとに 1 ビットが保存されます。
b が 2 の場合、ハーフソートを有効にするかどうかは同じ格納桁数を必要とし、意味がないことがわかります。 b が大きすぎると、保存する必要があるインデックスも急速に拡大し、クエリのパフォーマンスが大幅に低下するため、b=4 が最もコスト効率の高いオプションになります。
さらに、4 桁のフィンガープリントを保存するためのエンコーディングの選択は、保存に便利な 16 進数で表現できるためです。
ハーフ ソートを使用する場合のパラメーターの選択
ハーフソートを使用する場合は、$ceil(b(f-1)/8)
フィルタ サイズの選択
フィルタの合計バケット サイズは 2 の指数倍数である必要があるため、設定するときはフィルター サイズ。$size/α ~=(<) 2^n$ を満たすようにしてください。サイズはフィルターに保存するデータの量です。必要に応じて、より小さいフィルターを選択し、複数のフィルターを使用して達成する必要があります。ターゲット効果
Golang 実装
この部分は主に Golang ライブラリに関連しています
Github で cuckoofilter の Golang 実装を調べた後、既存の実装にはいくつかの欠点があることがわかりました:
- ほとんどのライブラリは b と f が固定されており、偽陽性率も固定されており、適応性は良好ではありません
- すべてライブラリ f はバイト単位でのみ指定できます。8 の倍数で調整できますが、誤検知率を調整するのは不便です。
- すべてのライブラリは半ソート バケットを実装していないため、Bloom と比較して利点が大幅に減少します。フィルター
# 私自身のシナリオでは、より良いスペースとカスタムの誤検知率が必要なため、元の論文の C 実装を移植し、主に
- ## を含むいくつかの最適化を行いました。 ##調整パラメータのサポート
- 半ソートバケットのサポート ##空間をコンパクトなビット配列に圧縮し、フィンガープリントをビットごとに保存
- # #バイナリ シリアル化のサポート
以上がより包括的な Golang バージョンのカッコー フィルターを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。