Redis BloomFilter ブルームフィルターの実装方法

ブルーム フィルターの概念

ブルームという人物が 1970 年にブルーム フィルター (英語名: Bloom Filter) を提案しました。これは実際には長いバイナリ ベクトルと一連のランダム マッピング関数です。ブルーム フィルターを使用すると、要素がコレクション内にあるかどうかを取得できます。利点はスペース効率とクエリ時間が通常のアルゴリズムよりもはるかに高いことですが、欠点は一定の誤認識率と削除の難しさです。

ブルーム フィルターの原理

ブルーム フィルターの原理は、要素がセットに追加されると、その要素が K 個のハッシュ関数を通じてビット配列内の K 点にマッピングされるというものです。それらを1にします。取得するとき、これらのポイントがすべて 1 であるかどうかを確認するだけで、それがセット内にあるかどうかを (おおよそ) 知ることができます: これらのポイントのいずれかが 0 である場合、チェックされた要素はそこに存在してはなりません; それらがすべて 1 である場合、次に、チェックされた要素が表示される可能性が高くなります。これがブルームフィルターの基本的な考え方です。

ブルーム フィルターと単一ハッシュ関数ビットマップの違いは、ブルーム フィルターが k 個のハッシュ関数を使用し、各文字列が k ビットに対応することです。これにより、競合の可能性が軽減されます

キャッシュの侵入

##すべてのクエリが DB に直接ヒットします

つまり、簡単に言うと、最初にデータベースからすべてのデータをフィルターに読み込みます。たとえば、データベースの ID は 1、2、3

になり、次に ID: 1 を使用します。例: 上の図で 3 回ハッシュした後、元の値が 0 だった 3 つの場所を 1 に変更しました。それからそれを 1 に変更します。 3 つのハッシュを取得し、3 つのハッシュの値が上記の 3 つの位置とまったく同じであることを確認します。これにより、フィルターに 1 があることが証明できます。

逆に、異なる場合は、存在しないことを意味します。

では、アプリケーションのシナリオはどこにあるのでしょうか?通常、キャッシュの故障を防ぐためにこれを使用します。

簡単に言うと、データベースの ID は 1 から始まり、その後自動的に増加します。その後、インターフェースが ID によってクエリされることがわかっているので、負の値を使用します。クエリする数値。この時点で、データがキャッシュにないことがわかります。データベースにアクセスして確認しますが、見つかりません。1 つのリクエストは次のようなものです。100、1,000、または 10,000 はどうでしょうか?基本的にDBでは扱えません、これをキャッシュに追加すると存在しなくなります、そんなデータは無いと判断したらチェックしません、そのまま返した方が良いのではないでしょうか？データは空ですか?

これがとても良いとしたら、欠点は何ですか?はい、続いて

ブルーム フィルターのデメリット

ブルーム フィルターの方が時間と空間の効率が良い理由は、判断の正確性が犠牲になるからです。

#コンテナ内に検索すべき要素が含まれていない可能性もありますが、ハッシュ演算の関係上、これらの要素のハッシュ位置k個の値はすべて1となるため、誤判定につながる可能性があります。ブルームフィルターにブラックリストを格納する場合、誤判定の可能性がある要素を格納するホワイトリストを設けることで誤判定率を低減することができます。

削除は困難です。コンテナ内に配置された要素は、ビット配列の k 番目の位置の 1 にマッピングされますが、削除する場合、単純に直接 0 に設定することは、他の要素の判定に影響を与える可能性があるためできません。 Counting Bloom Filter

FAQ

1 を使用できます。複数のハッシュ関数を使用する理由は何ですか?

ハッシュ関数を 1 つだけ使用すると、ハッシュ自体が競合することがよくあります。たとえば、長さ 100 の配列の場合、ハッシュ関数が 1 つだけ使用されている場合、要素を 1 つ追加した後、2 番目の要素を追加するときの競合の確率は 1%、3 番目の要素を追加するときの競合の確率は 2 になります。 %... ただし、2 つの要素が使用されている場合、衝突の確率は 1% です。ハッシュ関数では、要素を追加した後、2 番目の要素を追加するときの競合の確率は 10,000 分の 4 に減少します (競合の可能性は 4 つあり、シチュエーションの総数 100x100)

go 言語実装

package main
import (
	"fmt"
	"github.com/bits-and-blooms/bitset"
)
//设置哈希数组默认大小为16
const DefaultSize = 16
//设置种子，保证不同哈希函数有不同的计算方式
var seeds = []uint{7, 11, 13, 31, 37, 61}
//布隆过滤器结构，包括二进制数组和多个哈希函数
type BloomFilter struct {
	//使用第三方库
	set *bitset.BitSet
	//指定长度为6
	hashFuncs [6]func(seed uint, value string) uint
}
//构造一个布隆过滤器，包括数组和哈希函数的初始化
func NewBloomFilter() *BloomFilter {
	bf := new(BloomFilter)
	bf.set = bitset.New(DefaultSize)

	for i := 0; i < len(bf.hashFuncs); i++ {
		bf.hashFuncs[i] = createHash()
	}
	return bf
}
//构造6个哈希函数，每个哈希函数有参数seed保证计算方式的不同
func createHash() func(seed uint, value string) uint {
	return func(seed uint, value string) uint {
		var result uint = 0
		for i := 0; i < len(value); i++ {
			result = result*seed + uint(value[i])
		}
		//length = 2^n 时，X % length = X & (length - 1)
		return result & (DefaultSize - 1)
	}
}
//添加元素
func (b *BloomFilter) add(value string) {
	for i, f := range b.hashFuncs {
		//将哈希函数计算结果对应的数组位置1
		b.set.Set(f(seeds[i], value))
	}
}
//判断元素是否存在
func (b *BloomFilter) contains(value string) bool {
	//调用每个哈希函数，并且判断数组对应位是否为1
	//如果不为1，直接返回false，表明一定不存在
	for i, f := range b.hashFuncs {
		//result = result && b.set.Test(f(seeds[i], value))
		if !b.set.Test(f(seeds[i], value)) {
			return false
		}
	}
	return true
}
func main() {
	filter := NewBloomFilter()
	filter.add("asd")
	fmt.Println(filter.contains("asd"))
	fmt.Println(filter.contains("2222"))
	fmt.Println(filter.contains("155343"))
}

出力結果は次のとおりです:

true

false

false

以上がRedis BloomFilter ブルームフィルターの実装方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。