뻐꾸기 필터의 보다 포괄적인 Golang 버전을 구현하는 방법-Golang-php.cn

튜토리얼 칼럼에서 소개한 내용입니다. 필요한 친구들에게 도움이 되기를 바랍니다! "값이 거대한 집합에 있는지 확인"(이하 총칭하여 집합 멤버십 테스트라고 함)은 일반적인 데이터 처리 문제입니다. 과거 경험에서는 특정 오탐률이 허용되면 Bloom 필터가 첫 번째 선택이지만 이제는 더 나은 선택인 Cuckoo 필터가 있습니다. 최근 비즈니스에서는 필터를 사용해야 합니다. 검색 결과 우리 시나리오에서는 블룸 필터보다 뻐꾸기 필터가 더 비용 효율적이고 더 우수하다는 것을 알았습니다. 최종 기술 선택을 결정하기 위해 원본 논문을 읽었습니다. 나중에 뻐꾸기 필터를 사용하기로 결정했을 때 현재 GitHub의 여러 고급 구현이 거의 없다는 것을 발견했습니다. 결함이 있고 공간 활용도가 극대화되지 않아 원본 논문과 논문의 원본 C++ 구현을 참조하여 Golang 라이브러리 버전을 이식하고 최적화했습니다.

코드 주소는 여기입니다. 별표 표시, 사용, 기여 및 디버그를 환영합니다: github.com/linvon/cuckoo-filter

Cuckoo 필터

인터넷에 뻐꾸기 필터에 대한 소개 기사가 많이 있습니다. 여기 더 이상 없습니다. 소개, 주요 내용만 언급하여 다음 콘텐츠를 소개합니다자세한 내용을 알고 싶으시면 원문을 참고하시거나 제 중국어 번역 버전을 확인해 보세요

뻐꾸기 필터란 무엇인가요?

는 뻐꾸기 해시 알고리즘을 기반으로 구현된 필터입니다. 본질적으로 저장 항목의 해시 값을 저장하는 뻐꾸기 해시 테이블입니다. 블룸 필터에 대해 알고 계시다면 블룸 필터의 원리는 여러 해싱 방법을 사용하여 저장 항목의 다양한 해시를 비트 배열에 매핑하고 쿼리할 때 이러한 비트가 존재하는지 확인하는 것입니다.

뻐꾸기 필터는 저장 항목을 해시하고 해시 값에서 특정 자릿수를 가져와 배열에 저장합니다. 쿼리 시 배열에 동일한 자릿수의 해시가 있는지 확인합니다.

쿠쿠 필터를 선택하는 이유는 무엇인가요?

또한 해시 값을 저장하는데, 본질적으로 다중 비트 해시를 저장하는 것이 왜 뻐꾸기 필터가 더 나은가요?

첫째, 뻐꾸기 해시 테이블은 더 컴팩트해지기 때문에 더 많은 공간을 절약할 수 있습니다.

두 번째는 쿼리할 때 Bloom 필터는 여러 해시에 대해 다양한 해시 함수를 사용하는 반면, Cuckoo 필터는 하나의 해시만 필요하기 때문에 쿼리 효율성이 매우 높기 때문입니다
세 번째는 Cuckoo 필터가 지원한다는 것입니다 삭제는 되는데 블룸 필터는 삭제를 지원하지 않습니다
장점은 있는데 단점은 무엇인가요? Bloom 필터와 비교

Cuckoo 필터는 위치와 저장 값을 통해 서로 XOR하여 후보 버킷과 선호 버킷을 얻을 수 있습니다. 이 대응에는 버킷 크기가 지수배여야 합니다. of 2

블룸 필터를 삽입하면 해시가 계산되어 비트에 직접 기록됩니다. 그러나 뻐꾸기 필터를 계산한 후에는 현재 위치에 지문이 저장되어 있는 것처럼 보일 수 있습니다. 저장된 지문이 필요하므로 버킷이 가득 차면 충돌 가능성이 커지고 삽입 시간도 길어지므로 Bloom에 비해 삽입 성능이 매우 떨어집니다. filter

중복 요소 삽입: 천 긴 필터는 중복 요소를 삽입할 때 효과가 없으며 기존 비트만 재설정합니다. 뻐꾸기 필터는 기존 값을 쫓아내기 때문에 반복되는 요소 삽입에는 상한이 있습니다. 뻐꾸기 필터의 삭제는 완벽하지 않습니다. 반복 삽입에는 위와 같은 제한이 있으며 삭제 시에도 관련 문제가 발생합니다. : 동일한 해시 값을 한 번만 삽입해야 삭제가 완벽합니다. 요소를 삽입하지 않고 삭제하면 실수로 삭제될 수 있습니다. 이는 요소를 여러 번 삽입하면 매번 삭제되는 것과 같은 이유입니다. 하나의 값만 삭제됩니다. 삭제하기 전에 요소가 몇 번 삽입되었는지 알아야 합니다. 또는 삭제가 실패할 때까지 루프에서 삭제를 실행해야 합니다. 장점과 단점이 모두 나열되어 있습니다. 다시 요약해 보겠습니다. 이런 종류의 집합 멤버쉽 테스트 문제의 경우 대부분의 시나리오에는 더 많은 읽기와 더 적은 쓰기가 포함되며 반복 삽입은 의미가 없습니다. 비록 뻐꾸기 필터 삭제가 완벽하지는 않지만 아무것도 없는 것보다는 낫고 쿼리와 저장도 더 좋습니다. 효율성은 대부분의 경우 더 비용 효율적인 선택이라고 말해야 합니다.

실용 가이드

구현 세부 사항

먼저 뻐꾸기 필터의 개념에 대해 이야기해 보겠습니다. 필터는 여러 개의 버킷으로 구성되며, 이 값은 고정된 값입니다. 자릿수가 저장됩니다.

필터에는 n개의 버킷이 있으며, 버킷 수는 저장할 항목 수에 따라 계산됩니다. 해시 알고리즘을 통해 항목이 어느 버킷에 저장되어야 하는지 계산할 수 있습니다. 또한 각 추가 해시 알고리즘은 항목에 대한 후보 버킷을 생성할 수 있으며, 반복적으로 삽입되면 현재 저장된 항목이 후보 버킷으로 삭제됩니다. .들어가세요. 이론적으로는 해시 알고리즘이 많을수록 공간 활용도가 높아지지만 실제 테스트에서는 k=2 해시 함수를 사용하면 98%의 활용률을 달성할 수 있습니다.

각 버킷에는 여러 개의 지문이 저장됩니다. 이는 버킷의 크기에 따라 동일한 버킷에 매핑될 수 있습니다. 버킷이 클수록 공간 활용도가 높아지지만, 동시에 각 쿼리에 대해 동일한 버킷에서 더 많은 지문이 스캔되므로 오탐이 발생할 확률이 높아집니다. 충돌률을 줄이기 위해 저장된 지문 수를 유지합니다.

논문에는 뻐꾸기 필터 구현에 필요한 여러 매개변수가 언급되는데 주로

해시 함수 수(k): 해시 수, 2이면 충분합니다.
버킷 크기(b): 몇 개의 지문이 저장되어 있는지 각 버킷
지문 크기(f): 각 지문에 저장된 키의 해시 값 비트 수

논문을 자세히 읽어보세요. 5장에서 저자는 실험 데이터를 사용하여 지문을 선택하는 방법을 알려줍니다. 가장 적합한 구성 매개변수를 통해 다음과 같은 결론을 얻을 수 있습니다

필터를 100% 채울 수 없으며 최대 부하율 α가 있으며 각 항목에 할당된 저장 공간은 f/α입니다
전체 크기를 유지할 때 필터를 변경할 때 버킷이 클수록 부하율이 높아집니다. 즉, 공간 활용도가 높아지지만 각 버킷에 저장된 지문이 많을수록 쿼리 중 충돌 가능성이 높아집니다. 거짓양성률은 변하지 않고 버킷이 클수록 로드 계수가 높아집니다. 더 큰 지문이 필요합니다.

위의 이론적 근거에 따라 얻은 관련 실험 데이터는 다음과 같습니다.

k=2 해시 함수는 다음과 같습니다. 사용하면 버킷 크기 b=1(즉, 해시 테이블의 직접 매핑)일 때 부하율 α는 50%이지만 버킷 크기 b=2, 4 또는 8을 사용할 경우 84%, 95로 증가합니다. % 및 98% 각각
오탐률 r을 보장하려면 $2b/2 ^fleq 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

이런 방식으로 뻐꾸기 필터를 만들기 위해 매개변수를 선택하는 방법을 결정할 수 있습니다:

우선, 이것으로 충분합니다 충분한 공간 활용을 달성할 수 있는 두 가지 해시 함수를 사용하겠습니다. 필요한 거짓 긍정 비율에 따라 사용할 버킷 크기를 결정할 수 있습니다. 물론 b의 선택은 절대적이지 않습니다. r>0.002인 경우에도 b=4를 사용하여 반 정렬된 버킷을 활성화할 수 있습니다. 그런 다음 b를 기반으로 목표 오탐률을 달성하는 데 필요한 f의 크기를 계산하여 모든 필터 매개변수가 결정됩니다.

위의 결론을 Bloom 필터의 각 항목에 대한 $1.44log_2(1/r)$와 비교하면, half sorting이 활성화된 경우, r<0.03일 때, half sorting이 있으면 뻐꾸기 필터 공간이 더 작아진다는 것을 알 수 있습니다. 활성화되지 않은 경우 정렬하면 약 r<0.003으로 저하됩니다.

몇 가지 고급 설명

해시 알고리즘 최적화

두 개의 해시 알고리즘이 필요하다고 명시했지만 실제 구현에서는 하나의 해시 알고리즘을 사용하면 충분합니다. 대체 버킷 계산 방법의 경우 첫 번째 해시 값을 해당 위치에 저장된 지문과 XOR하여 두 번째 해시 값을 계산할 수 있습니다. 지문의 해시와 위치의 해시를 별도로 계산해야 하는 것이 걱정된다면 하나의 알고리즘을 사용하여 64비트 해시를 만들 수 있습니다. 상위 32비트는 위치를 계산하는 데 사용되고 하위 비트는 지문을 계산하는 데 32비트가 사용됩니다.

반정렬 버킷은 왜 b=4인 경우에만 사용할 수 있나요?

반정렬의 핵심은 각 지문의 4자리를 취해 b지문의 4자리 저장을 모든 가능성을 정리한 후 16진수로 표현하는 것입니다. 순서대로 위치를 인덱싱하여 해당 배열을 찾아 실제 저장된 값을 얻을 수 있습니다.

다음 함수를 통해 모든 상황 유형의 수를 계산할 수 있습니다

func getNum(base, k, b, f int, cnt *int) {
    for i := base; i < 1<> 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$을 충족하도록 노력하세요. 크기는 필터가 저장하려는 데이터의 양입니다. 필요한 경우 더 작은 값을 선택해야 합니다. 필터, 목표 효과를 얻으려면 여러 필터를 사용하세요

Golang 구현
이 부분은 주로 Golang 라이브러리와 관련이 있습니다
Github에서 cuckoofilter의 golang 구현을 살펴본 후, 기존 구현에는 몇 가지 단점이 있음을 발견했습니다. 

대부분의 라이브러리는 b와 f를 고정했습니다. 즉, 거짓양성률도 고정되어 있으며 적응성이 좋지 않습니다
모든 라이브러리 f는 바이트 단위이며 표현만 가능합니다. 8의 배수로 조정하면 위양성율을 조정하는 것이 불편합니다
모든 라이브러리는 반정렬 버킷을 구현하지 않으므로 블룸 필터에 비해 장점이 크게 줄어듭니다

자신의 시나리오에는 더 나은 공간과 맞춤형 오탐지가 필요하기 때문입니다 rate 이므로 원본 논문의 C++ 구현이 이식되었으며 주로 

 매개변수 조정 지원 
 반 정렬 버킷 지원 

 컴팩트한 비트 배열로 압축된 공간 및 비트 단위로 지문 저장 
 
이진 직렬화 지원