Redis BloomFilter Bloom 필터 구현 방법

Bloom 필터 개념

Bloom이라는 남자가 1970년에 Bloom 필터(영어명: Bloom Filter)를 제안했습니다. 실제로는 긴 이진 벡터와 일련의 무작위 매핑 함수입니다. 블룸 필터는 요소가 컬렉션에 있는지 검색하는 데 사용할 수 있습니다. 장점은 일반 알고리즘에 비해 공간 효율성과 쿼리 시간이 훨씬 높다는 점이며, 단점은 일정 수준의 오인식률과 삭제가 어렵다는 점입니다.

블룸 필터 원리

블룸 필터의 원리는 집합에 요소가 추가되면 K개의 해시 함수를 사용하여 해당 요소를 비트 배열의 K개 포인트로 매핑하고 1로 설정하는 것입니다. 검색할 때 이 포인트가 모두 1인지 여부만 확인하면 세트에 있는지 여부를 대략 알 수 있습니다. 이 포인트 중 하나라도 0이면 검사된 요소가 모두 1이면 해당 요소가 없어야 합니다. 그런 다음 체크된 요소일 가능성이 높습니다. 이것이 블룸필터의 기본 아이디어이다.

블룸 필터와 단일 해시 함수 비트맵의 차이점은 블룸 필터가 k개의 해시 함수를 사용하고 각 문자열이 k비트에 해당한다는 점입니다. 이를 통해 충돌 가능성을 줄입니다

캐시 침투

모든 쿼리는 DB에 직접 도달합니다

간단히 말해서 먼저 데이터베이스의 모든 데이터를 In the filter에 로드합니다. , 예를 들어 현재 데이터베이스의 ID는 1, 2, 3

입니다. 그런 다음 ID: 1을 예로 사용합니다. 위 그림에서 3번 해싱한 후 원래 값인 0을 1

으로 3번 변경했습니다. 쿼리를 위해 데이터가 들어왔을 때 id의 값이 1이면 1을 3번 해시하여 3개의 해시 값이 위의 3개 위치와 완전히 동일하다는 것을 알게 됩니다. 1이 필터

이고 그 반대도 다르다면 존재하지 않는다는 뜻입니다. 그렇다면 적용 시나리오는 어디에 있나요? 일반적으로 캐시 고장을 방지하기 위해 사용합니다

간단히 말하면 데이터베이스의 ID는 1로 시작하여 자체적으로 증가합니다. 그러면 인터페이스가 ID로 쿼리된다는 것을 알고 있으므로 음수를 사용하여 쿼리하겠습니다. 이때 캐시에 그런 데이터가 없다는 걸 알게 됐고, 데이터베이스를 확인해봐도 아무것도 나오지 않았다. 요청이 하나 있는데 100, 1,000, 10,000 정도는 어떨까? 귀하의 DB는 기본적으로 이를 처리할 수 없습니다. 이것을 캐시에 추가하면 더 이상 존재하지 않게 됩니다. 그런 데이터가 없다고 판단되면 그냥 데이터를 반환하는 것이 낫지 않을까요? 그거 비어있어?

이거 너무 효과가 좋은데 단점이 뭔가요? 네, 아래를 살펴보겠습니다

블룸 필터의 단점

블룸 필터가 시간과 공간적으로 더 효율적일 수 있는 이유는 판단의 정확성과 삭제의 편의성이 희생되기 때문입니다

컨테이너에는 포함되지 않을 수도 있지만 찾아야 할 요소들이 있는데, 해시 연산으로 인해 k개의 해시 위치에 있는 이들 요소들의 값이 모두 1이기 때문에 오판으로 이어질 수 있다. 오판의 가능성이 있는 요소를 저장하기 위해 화이트리스트를 구축함으로써, 블룸 필터가 블랙리스트를 저장할 때 오판율을 줄일 수 있습니다.

삭제가 어렵습니다. 컨테이너에 배치된 요소는 비트 배열의 k번째 위치에 1로 매핑되며, 삭제 시 다른 요소의 판단에 영향을 미칠 수 있으므로 단순히 0으로 설정할 수는 없습니다. Counting Bloom Filter를 사용할 수 있습니다

FAQ

1. 왜 여러 해시 함수를 사용합니까?

해시 함수를 하나만 사용하면 해시 자체가 충돌하는 경우가 많습니다. 예를 들어 길이가 100인 배열의 경우 하나의 해시 함수만 사용하면 한 요소를 추가한 후 두 번째 요소를 추가할 때 충돌 확률은 1%, 세 번째 요소를 추가할 때 충돌 확률은 2입니다. %... 하지만 두 요소를 추가하면 충돌 확률은 1%입니다. 해시 함수는 요소를 추가한 후 두 번째 요소를 추가할 때 충돌 확률이 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 Bloom 필터 구현 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!