より包括的な Golang バージョンのカッコーフィルターを実装する方法-Golang-php.cn

以下は go 言語 チュートリアルコラムで紹介されています。より包括的な Golang バージョンの cuckoo フィルターを実装しました。お役に立てば幸いです。困っている友達へ。

「値が巨大なセットに含まれるかどうかを判断する」 (以下、総称してセットメンバーシップテストと呼びます) は、一般的なデータ処理の問題です。過去の経験では、特定の誤検知率が許容される場合、ブルームフィルターが第一の選択肢でしたが、現在はより良い選択肢、カッコーフィルターが用意されています。
最近のビジネスではフィルターを使用する必要があります。検索した結果、このシナリオではカッコーフィルターの方がコスト効率が高く、ブルームフィルターよりも優れていることがわかりました。
最終的なテクノロジーの選択を決定するために、元の論文を読みました。その後、cuckoo フィルターを使用することに決めたとき、golang の包括的な実装がほとんどないことがわかりました。現在、GitHub 上でいくつかの高評価の実装が公開されています。いくつかの欠陥があり、スペース使用率を最大化できなかったため、元の論文とその論文の元の C 実装を参照して、Golang ライブラリのバージョンを移植して最適化しました。
コードアドレスはここにあります。スター付け、使用、貢献、デバッグを歓迎します: github.com/linvon/cuckoo-filter

cuckoo filter

cuckooフィルタに関する紹介記事はインターネット上に多数ありますので、ここではあまり詳しくは説明しませんが、以下の内容につながる要点のみを述べます

さらに詳しく知りたい場合は、元の論文を参照するか、私の中国語翻訳版をチェックしてください。

カッコーフィルターとは何ですか?

はカッコーハッシュアルゴリズムに基づいて実装されたフィルターであり、本質的にはストレージアイテムのハッシュ値を格納するカッコーハッシュテーブルです。

ブルームフィルターを理解している場合は、ブルームフィルターの原理が、複数のハッシュメソッドを使用してストレージアイテムのさまざまなハッシュをビット配列にマッピングし、クエリ中にこれらのビットをチェックして存在するかどうかを判断することであることがわかるはずです。

カッコーフィルターは、ストレージアイテムをハッシュし、そのハッシュ値から特定の桁数を取り出し、配列に格納します。クエリを実行すると、同じ桁数のハッシュが配列内に存在するかどうかが判断されます。

カッコーフィルターを選ぶ理由?

これらはハッシュ値も保存し、本質的にはマルチビットハッシュを保存します。

まず、カッコーハッシュテーブルはよりコンパクトなので、より多くのスペースを節約できます。
#2 番目の理由は、クエリの際、ブルームフィルターは複数のハッシュに対してさまざまなハッシュ関数を使用するのに対し、カッコーフィルターは 1 つのハッシュしか必要としないため、クエリ効率が非常に高いということです
3 番目に、cuckoo フィルターは削除をサポートしますが、Bloom フィルターは削除をサポートしません

利点はありますが、欠点は何でしょうか。ブルームフィルタ

ブルームフィルターが挿入されると、ハッシュが計算され、ビットが直接書き込まれますが、カッコーフィルターでは現在位置が次のように表示される場合があります。フィンガープリントは、この時点で、保存されているアイテムを候補バケットにキックする必要がありますが、バケットがいっぱいになるにつれて、競合の可能性がますます大きくなり、挿入時間がますます長くなります。したがって、その挿入パフォーマンスはブルームフィルタリングと比較されますが、フィルタは非常に貧弱です
重複要素の挿入: ブルームフィルタは重複要素の挿入には効果がなく、既存のビットをリセットするだけです。カッコーフィルターは既存の値を追い出すため、繰り返される要素の挿入には上限があります。
カッコーフィルターの削除は完全ではありません。繰り返しの挿入には上記の制限があり、関連する問題が発生します: 削除は同じハッシュ値が一度挿入された場合にのみ完全に完了します。要素が挿入されずに削除された場合、誤った削除が発生する可能性があり、これは誤検出率と同じ理由です。要素が複数回挿入されます。その場合、各削除では 1 つの値のみが削除されます。要素が削除される前に要素が何回挿入されたかを把握するか、削除が失敗するまでループで削除を実行する必要があります。

メリットとデメリットをすべて列挙しましたが、もう一度まとめてみましょう。この種のセットメンバーシップテストの問題では、ほとんどのシナリオでは読み取りが多くなり、書き込みが少なくなり、挿入を繰り返しても意味がありません。カッコーフィルターの削除は完全ではありませんが、何もしないよりはマシです。クエリとストレージも向上します。効率も向上します。、ほとんどの場合、それはより費用対効果の高い選択であると言うべきです。

実践ガイド

詳細な実装

まず、カッコーフィルターの概念について説明しましょう。フィルターは多くのバケットで構成されています。各バケットには、挿入されたアイテムのハッシュ値が格納されます。このハッシュ値には、固定桁数のみが格納されます。

フィルターには n 個のバケットがあり、バケットの数は保存されるアイテムの数に基づいて計算されます。ハッシュアルゴリズムを通じて、アイテムをどのバケットに保存するかを計算できます。さらに、ハッシュアルゴリズムを追加するたびに、アイテムの候補バケットを生成できます。挿入が繰り返されると、現在保存されているアイテムが候補バケットに追加されます。入る。理論的には、ハッシュアルゴリズムの数が増えるほどスペースの使用率が高くなりますが、実際のテストでは、k=2 のハッシュ関数を使用して 98% の使用率を達成しました。

各バケットには複数のフィンガープリントが保存されます。これはバケットのサイズによって異なります。異なるフィンガープリントが同じバケットにマッピングされる場合があります。バケットが大きいほどスペースの使用率は高くなりますが、同時にクエリごとに同じバケットでより多くのフィンガープリントがスキャンされるため、誤検知が発生する確率が高くなります。保存された指紋の数を減らして競合率を減らし、誤検知率を維持します。

この論文では、カッコーフィルターを実装するために必要ないくつかのパラメータが言及されていますが、主に

ハッシュ関数の数 (k): ハッシュの数、2 つで十分です
バケットサイズ (b): 各バケットに保存されるフィンガープリントの数

フィルターを埋めることができません100%、最大負荷率 α があり、各アイテムに割り当てられる保管スペースは f/α

フィルターの合計サイズが一定に保たれる場合、バケットが大きいほど負荷率は高くなりますつまり、スペース使用率が高くなります。高いですが、各バケットに保存されているフィンガープリントが多いほど、クエリ中に競合が発生する可能性が高くなります。同じ誤検出率を維持するには、バケットが大きくなるほど、必要なフィンガープリントも大きくなります
上記の理論的根拠に基づいて、得られる関連実験データは次のとおりです。

k=2 ハッシュ関数を使用する場合、バケットサイズ b=1 (つまり、、ハッシュテーブルの直接マッピング）、負荷係数 α は 50% ですが、バケットサイズ b=2、4、または 8 を使用すると、それぞれ 84%、95%、98% に増加します

偽陽性率 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)f/8)$ であることを確認する必要があります。そうしないと、占有スペースが大きくなります。

フィルタサイズの選択

フィルタの合計バケットサイズは 2 の指数倍数である必要があるため、設定するときはフィルターサイズ。$size/α ~=(<) 2^n$ を満たすようにしてください。サイズはフィルターに保存するデータの量です。必要に応じて、より小さいフィルターを選択し、複数のフィルターを使用して達成する必要があります。ターゲット効果