쿠쿠 필터
쿠쿠 필터 (Cuckoo filter) (cuckoo-filter-2)
쿠쿠 필터(Cuckoo filter)는 집합에 어떤 요소가 존재하는지 확인하는 확률적 데이터 구조예요. 블룸 필터(Bloom filter)처럼 요소 존재 여부를 아주 빠르고 공간 효율적으로 확인할 수 있으면서도, 삭제도 가능하고 어떤 시나리오에서는 블룸 필터보다 더 나은 성능을 보여줘요. 이 페이지에서는 쿠쿠 필터를 어떻게 만들고, 항목을 넣고, 확인하고, 삭제하는지 하나씩 옆에서 설명드릴게요.
쿠쿠 필터 명령 요약: 12개 명령 (view reference)
블룸 필터가 해시 함수가 결정한 위치의 비트를 뒤집어 놓은 비트 배열이라면, 쿠쿠 필터는 버킷(bucket) 배열이에요. 두 해시 함수가 결정한 버킷 중 하나에 값의 지문(fingerprint)을 저장하죠. 항목 x에 대한 멤버십 쿼리는 x가 들어갈 수 있는 버킷들에서 x의 지문을 찾고, 동일한 지문이 발견되면 true를 반환해요. 쿠쿠 필터의 지문 크기는 오탐률(false positive rate)을 직접 결정합니다.
사용 사례 (Use cases)
타겟 광고 캠페인 (광고, 소매)
이 애플리케이션은 "사용자가 이 캠페인에 이미 가입했나?"라는 질문에 답해요.
캠페인마다 쿠쿠 필터를 하나씩 만들고 타겟 사용자 ID로 채워요. 방문할 때마다 사용자 ID를 쿠쿠 필터 중 하나와 대조하죠.
- 아니오라면, 사용자는 아직 캠페인에 가입하지 않은 상태예요. 광고를 보여줘요.
- 사용자가 광고를 클릭하고 가입하면, 해당 쿠쿠 필터에서 사용자 ID를 제거해요.
- 예라면, 사용자는 이미 그 캠페인에 가입한 상태예요. 다음 광고/쿠쿠 필터를 시도해요.
할인 코드/쿠폰 검증 (소매, 온라인 쇼핑)
이 애플리케이션은 "이 할인 코드/쿠폰이 이미 사용됐나?"라는 질문에 답해요.
모든 할인 코드/쿠폰으로 채운 쿠쿠 필터를 하나 만들어요. 시도할 때마다 입력된 코드를 필터와 대조하죠.
- 아니오라면, 쿠폰이 유효하지 않은 거예요.
- 예라면, 쿠폰이 유효할 수 있어요. 메인 데이터베이스를 확인해요. 유효하면 쿠쿠 필터에서
used(사용됨)로 제거해요.
참고: 이 두 사례 외에도 쿠쿠 필터는 블룸 필터의 모든 사용 사례에 아주 잘 맞아요.
예제 (Examples)
이제 빈 쿠쿠 필터를 초기 용량 1,000개 항목으로 만들고, 항목을 추가하고, 존재 여부를 확인하고, 제거하는 방법을 배워볼게요. CF.ADD는 필터가 없으면 새로 만들 수 있지만, 여러분의 요구에 최적화된 크기가 아닐 수 있어요. 원하는 용량으로 필터를 설정하려면 CF.RESERVE를 쓰는 게 좋아요.
res1 = r.cf().reserve("bikes:models", 1000000)
print(res1) # >>> True
res2 = r.cf().add("bikes:models", "Smoky Mountain Striker")
print(res2) # >>> 1
res3 = r.cf().exists("bikes:models", "Smoky Mountain Striker")
print(res3) # >>> 1
res4 = r.cf().exists("bikes:models", "Terrible Bike Name")
print(res4) # >>> 0
res5 = r.cf().delete("bikes:models", "Smoky Mountain Striker")
print(res5) # >>> 1
블룸 vs 쿠쿠 필터 (Bloom vs. Cuckoo filters)
블룸 필터는 보통 항목을 삽입할 때 더 나은 성능과 확장성을 보여줘요. 그래서 데이터셋에 항목을 자주 추가한다면 블룸 필터가 이상적일 수 있어요. 반면 쿠쿠 필터는 확인(체크) 연산이 더 빠르고, 삭제도 허용한답니다.
쿠쿠 필터 크기 정하기 (Sizing Cuckoo filters)
쿠쿠 필터의 주요 파라미터와 특징은 다음과 같아요.
p목표 오탐률f비트 단위 지문 길이α채움율 또는 부하 계수 (0≤α≤1)b버킷당 항목 수m버킷 수n항목 수C항목당 평균 비트 수
쿠쿠 필터 버킷은 여러 항목을 담을 수 있어요(각 항목이 지문 하나를 저장). 모든 항목이 지문으로 차게 되면 새 요소를 저장할 빈 슬롯이 없어져 필터는 "가득 참(full)" 상태가 되죠. 그래서 쿠쿠 필터는 항상 일정 비율을 비워 두는 게 좋아요.
그 결과 항목의 "실제" 메모리 비용은 지문 크기 위에 그 오버헤드를 포함해야 해요. α가 부하 계수(지문 크기 / 전체 필터 크기)이고 f가 항목의 비트 수라면, 분할 상환 공간 비용은 f/α bits가 돼요.
새 필터를 초기화할 때 용량(capacity)과 버킷 크기를 고르게 됩니다.
CF.RESERVE {key} {capacity} [BUCKETSIZE bucketSize] [MAXITERATIONS maxIterations] [EXPANSION expansion]
용량 고르기 (capacity)
쿠쿠 필터의 용량은 다음과 같이 계산돼요.
capacity = n*f/α
여기서 n은 필터에 넣을 예상 요소 수, f는 8로 설정된 지문 길이(비트), α는 채움 계수예요. 용량을 구하려면 먼저 채움 계수를 골라야 해요. 채움 계수는 데이터의 밀도, 당연히 메모리도 결정해요. 용량은 다음 "2의 거듭제곱(2n)" 수로 올림 처리됩니다.
참고: 쿠쿠 필터에 반복된 항목을 삽입하면 여러 번 추가하려 시도해서 필터가 빨리 가득 찰 수 있어요.
쿠쿠 필터의 작동 방식 때문에, 필터는 용량에 도달하기 전에 가득 찼다고 선언할 가능성이 커요. 따라서 채움율은 100%에 거의 도달하지 못해요.
버킷 크기 고르기 (BUCKETSIZE)
각 버킷의 항목 수예요. 버킷 크기가 클수록 채움율은 좋아지지만, 오류율도 높아지고 성능도 약간 느려져요.
error_rate = (buckets * hash_functions)/2^fingerprint_size = (buckets*2)/256
버킷 크기를 1로 쓰면 채움율 55%, 오탐률 2/256 ≈ 0.78%로 달성 가능한 최소 오탐률이에요. 버킷을 크게 할수록 오류율은 선형으로 높아지지만 필터의 채움율은 좋아져요. 예를 들어 버킷 크기 3은 오류율 2.34%에 채움율 80%, 버킷 크기 4는 오류율 3.12%에 채움율 95%를 내요.
확장 계수 고르기 (EXPANSION)
필터가 스스로 가득 찼다고 선언하면 성능 저하와 오류율 증가를 대가로 추가적인 서브 필터를 생성해 자동으로 확장해요. 새 서브 필터는 이전 서브 필터 크기에 EXPANSION(필터 생성 시 선택)을 곱한 크기로 만들어져요. 버킷 크기와 마찬가지로 추가 서브 필터는 오류율을 선형으로 키워요(복합 오류는 모든 서브 필터 오류의 합). 새 서브 필터의 크기는 마지막 서브 필터 크기에 확장 계수를 곱한 값이라는 점을 꼭 기억하세요. 어느 시점에 확장해야 할 걸 알면 더 큰 확장 값을 고르는 게 좋아요. 기본값은 cf-expansion-factor예요.
"어차피 확장할 거라면 굳이 높은 확장률로 작은 필터를 만드는 이유가 뭘까?"라고 궁금할 수 있겠네요. 답은 이렇습니다. 필터를 많이 유지해야 하는 경우(사용자당, 제품당 필터 하나 등) 대부분은 작게 유지되지만, 활동이 많은 일부 필터만 확장해야 하기 때문이에요.
확장 계수는 다음 "2의 거듭제곱(2n)" 수로 올림 처리됩니다.
최대 반복 횟수 고르기 (MAXITERATIONS)
MAXITERATIONS는 들어오는 지문의 슬롯을 찾기 위한 시도 횟수를 지정해요. 필터가 가득 차면 높은 MAXITERATIONS 값은 삽입을 느리게 만들어요. 기본값은 cf-max-iterations예요.
흥미로운 사실 (Interesting facts)
- 이전 서브 필터의 사용되지 않은 용량은 가능할 때 자동으로 사용돼요.
- 필터는
cf-max-expansions번까지 성장할 수 있어요. - 다시 구축(rebuild)하는 대신 항목을 삭제해서 필터 한도를 지킬 수 있어요.
- 같은 요소를 여러 번 추가하면 여러 항목이 생겨 필터가 가득 차요.
성능 (Performance)
쿠쿠 필터에 요소를 추가하는 시간 복잡도는 O(1)이에요.
마찬가지로 요소를 확인하고 삭제하는 것도 시간 복잡도가 O(1)이에요.