以下は go 言語 チュートリアル コラムで紹介されています。より包括的な Golang バージョンの cuckoo フィルターを実装しました。お役に立てば幸いです。困っている友達へ。
「値が巨大なセットに含まれるかどうかを判断する」 (以下、総称してセット メンバーシップ テストと呼びます) は、一般的なデータ処理の問題です。過去の経験では、特定の誤検知率が許容される場合、ブルーム フィルターが第一の選択肢でしたが、現在はより良い選択肢、カッコー フィルターが用意されています。
最近のビジネスではフィルターを使用する必要があります。検索した結果、このシナリオではカッコー フィルターの方がコスト効率が高く、ブルーム フィルターよりも優れていることがわかりました。
最終的なテクノロジーの選択を決定するために、元の論文を読みました。その後、cuckoo フィルターを使用することに決めたとき、golang の包括的な実装がほとんどないことがわかりました。現在、GitHub 上でいくつかの高評価の実装が公開されています。いくつかの欠陥があり、スペース使用率を最大化できなかったため、元の論文とその論文の元の C 実装を参照して、Golang ライブラリのバージョンを移植して最適化しました。
コード アドレスはここにあります。スター付け、使用、貢献、デバッグを歓迎します: github.com/linvon/cuckoo-filter
cuckooフィルタに関する紹介記事はインターネット上に多数ありますので、ここではあまり詳しくは説明しませんが、以下の内容につながる要点のみを述べます
さらに詳しく知りたい場合は、元の論文を参照するか、私の中国語翻訳版をチェックしてください。
はカッコー ハッシュ アルゴリズムに基づいて実装されたフィルターであり、本質的にはストレージ アイテムのハッシュ値を格納するカッコー ハッシュ テーブルです。
ブルーム フィルターを理解している場合は、ブルーム フィルターの原理が、複数のハッシュ メソッドを使用してストレージ アイテムのさまざまなハッシュをビット配列にマッピングし、クエリ中にこれらのビットをチェックして存在するかどうかを判断することであることがわかるはずです。
カッコー フィルターは、ストレージ アイテムをハッシュし、そのハッシュ値から特定の桁数を取り出し、配列に格納します。クエリを実行すると、同じ桁数のハッシュが配列内に存在するかどうかが判断されます。
これらはハッシュ値も保存し、本質的にはマルチビット ハッシュを保存します。
まず、カッコー ハッシュ テーブルはよりコンパクトなので、より多くのスペースを節約できます。
まず、カッコー フィルターの概念について説明しましょう。フィルターは多くのバケットで構成されています。各バケットには、挿入されたアイテムのハッシュ値が格納されます。このハッシュ値には、固定桁数のみが格納されます。
フィルターには n 個のバケットがあり、バケットの数は保存されるアイテムの数に基づいて計算されます。ハッシュ アルゴリズムを通じて、アイテムをどのバケットに保存するかを計算できます。さらに、ハッシュ アルゴリズムを追加するたびに、アイテムの候補バケットを生成できます。挿入が繰り返されると、現在保存されているアイテムが候補バケットに追加されます。 入る。理論的には、ハッシュ アルゴリズムの数が増えるほどスペースの使用率が高くなりますが、実際のテストでは、k=2 のハッシュ関数を使用して 98% の使用率を達成しました。
各バケットには複数のフィンガープリントが保存されます。これはバケットのサイズによって異なります。異なるフィンガープリントが同じバケットにマッピングされる場合があります。バケットが大きいほどスペースの使用率は高くなりますが、同時にクエリごとに同じバケットでより多くのフィンガープリントがスキャンされるため、誤検知が発生する確率が高くなります。保存された指紋の数を減らして競合率を減らし、誤検知率を維持します。
この論文では、カッコーフィルターを実装するために必要ないくつかのパラメータが言及されていますが、主に
:
最初に 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 ライブラリに関連しています
Github で cuckoofilter の Golang 実装を調べた後、既存の実装にはいくつかの欠点があることがわかりました:
# 私自身のシナリオでは、より良いスペースとカスタムの誤検知率が必要なため、元の論文の C 実装を移植し、主に
以上がより包括的な Golang バージョンのカッコー フィルターを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
