~/blog/cuckoo-vs-bloom/ko.mdx

Cuckoo filter는 정말 Bloom filter보다 나은가

Cuckoo filter 논문의 부제는 Practically Better Than Bloom입니다. 버킷 크기별 적재율, 같은 공간에서의 오탐률, 삭제가 실제로 어떻게 동작하는지 직접 구현해 재 보니 '항상'은 아니었습니다.

Bloom filter는 원소를 지울 수 없습니다. 비트 하나가 여러 원소의 몫이라 하나를 지우면 다른 원소까지 사라집니다. 2014년 Fan 등이 발표한 Cuckoo filter는 원소 대신 지문(fingerprint)을 cuckoo 해시 테이블에 넣어 삭제를 지원하고, 같은 공간에서 오탐률도 더 낮다고 주장합니다.1 논문 부제가 “Practically Better Than Bloom”입니다. 두 구조를 Python으로 구현해서 이 주장이 어디까지 맞는지 확인했습니다. 해시는 blake2b, 환경은 Python 3(Apple Silicon 노트북)입니다. 아래 코드는 원소 수 집계 같은 부분을 뺀 발췌입니다. 시간이 아니라 비율만 재므로 언어는 결과에 영향이 없습니다.

지문 하나에 자리 두 개

Cuckoo filter는 원소 x의 지문 fp를 두 후보 버킷 중 빈 자리가 있는 곳에 넣습니다. 둘 다 차 있으면 한쪽의 지문 하나를 쫓아내고 그 지문을 자기 다른 자리로 보냅니다. 뻐꾸기가 남의 둥지에서 알을 밀어내는 것과 같다고 해서 이 이름이 붙었습니다.

가득 차면 하나를 쫓아냄 x hash(x) → i1 fingerprint(x) → fp i2 = i1 XOR hash(fp) 버킷 i1 버킷 i2

까다로운 점은 쫓겨난 지문의 다른 자리를 원래 원소 없이 알아내야 한다는 것입니다. 테이블에는 지문만 있으니까요. 논문의 해법이 partial-key cuckoo hashing입니다.

cuckoo.py
def _alt(s, i, fp):
return (i ^ h64(fp, 99)) % s.nb
def add(s, x):
fp, i1 = s._fp(x); i2 = s._alt(i1, fp)
for i in (i1, i2):
if len(s.t[i]) < s.bs:
s.t[i].append(fp); return True
i = s.rng.choice((i1, i2))
undo = []
for _ in range(s.mk):
j = s.rng.randrange(len(s.t[i]))
undo.append((i, j, s.t[i][j]))
fp, s.t[i][j] = s.t[i][j], fp
i = s._alt(i, fp)
if len(s.t[i]) < s.bs:
s.t[i].append(fp); return True
for i, j, old_fp in reversed(undo):
s.t[i][j] = old_fp
return False

다른 자리는 현재 자리와 지문의 해시를 XOR해서 구합니다. XOR은 자기 역원이므로 i1에서 i2를, i2에서 i1을 같은 식으로 얻습니다. 원래 키가 없어도 됩니다. 버킷 수가 2의 거듭제곱이어야 % nb가 이 성질을 깨지 않습니다.

두 후보 중 빈 자리가 있으면 바로 넣습니다. 테이블이 비어 있을 때는 대부분 여기서 끝납니다.

둘 다 차 있으면 무작위로 지문 하나를 꺼내고 내 지문을 그 자리에 넣습니다. 꺼낸 지문은 _alt로 자기 다른 자리를 찾아갑니다. 거기도 차 있으면 또 쫓아냅니다. 바꾼 슬롯과 그 자리에 있던 지문을 undo에 기록합니다.

정해진 횟수(여기서는 500번) 안에 빈 자리를 못 찾으면 삽입이 실패합니다. 테이블 전체가 찼다는 증명은 아닙니다. 이동 경로에서 빈 자리를 찾지 못했다는 뜻입니다. 이때 마지막으로 쫓겨난 지문은 테이블 밖의 fp에 남아 있으므로, 그대로 실패를 반환하면 기존 원소를 잃을 수 있습니다. 예제는 변경을 역순으로 되돌려 실패한 삽입 전의 테이블을 복원합니다. 같은 슬롯을 여러 번 바꿨을 수 있어 되돌리는 순서도 중요합니다.

버킷 크기와 적재율

버킷 하나에 지문을 몇 개 담느냐가 공간 효율을 정합니다. 버킷 2142^{14}개, 16비트 지문으로 첫 삽입 실패가 날 때까지 넣고 적재율을 봤습니다. 시드를 바꿔 세 번 반복했습니다.

버킷당 슬롯시도 1시도 2시도 3
152.3%53.2%48.9%
287.2%87.0%87.6%
496.6%96.3%96.6%
899.1%98.7%99.1%
"b=1" "b=2" "b=4" "b=8" 40 50 60 70 80 90 100 % 첫 실패 시점 적재율 (%)

슬롯이 하나면 절반을 겨우 채웁니다. 넷이면 96%까지 갑니다. 논문이 기본값으로 버킷당 4슬롯을 권하는 이유입니다. 8로 늘리면 더 채울 수 있지만 조회 때 비교할 지문이 두 배가 되고, 그만큼 오탐도 늘어납니다.

같은 공간에서 오탐률

공정하게 비교하려면 원소당 비트 수를 맞춰야 합니다. Cuckoo filter를 슬롯 2162^{16}개, 버킷당 4슬롯으로 만들어 95%까지 채우고, 같은 원소 수에 같은 총 비트를 Bloom filter에 줬습니다. Bloom의 해시 함수 개수 k는 최적값을 썼습니다. 넣지 않은 원소 40만 개로 조회했습니다.

지문 비트원소당 비트Cuckoo 오탐률Cuckoo 상한 2b/2f2b/2^fBloom kBloom 오탐률Bloom 이론값
88.422.98%3.13%61.78%1.75%
1212.630.182%0.195%90.219%0.232%
1616.840.014%0.012%120.028%0.031%

원소당 8비트 남짓에서는 Bloom이 이깁니다. 12비트부터 Cuckoo가 앞서고, 16비트에서는 오탐률이 절반입니다.

이유는 식에 있습니다. Cuckoo는 조회 때 버킷 두 개, 지문 2b=82b = 8개와 비교하므로 오탐률이 대략 2b/2f2b/2^f입니다. Bloom은 최적일 때 (1/2)k(1/2)^{k}이고 k≈0.69⋅m/nk \approx 0.69 \cdot m/n입니다.

εcuckoo≈2b2f,εbloom≈0.6185 m/n\varepsilon_{\text{cuckoo}} \approx \frac{2b}{2^{f}}, \qquad \varepsilon_{\text{bloom}} \approx 0.6185^{\,m/n}

원소당 비트가 늘 때 Cuckoo는 비트 하나당 오탐률이 절반으로 줄고 Bloom은 0.6185배로 줄어듭니다. 출발점은 Cuckoo가 2b2b 배만큼 불리하지만 기울기가 더 가파르니 어느 지점에서 교차합니다. 제 구현에서는 8과 12비트 사이였습니다. 논문은 버킷 안의 지문을 정렬해 압축하는 semi-sorting을 쓰면 교차점이 원소당 약 7비트까지 내려간다고 합니다. 저는 semi-sorting을 구현하지 않았습니다.

오탐률 3% 언저리를 쓰는 곳이라면 Bloom이 더 작습니다. 0.1% 이하가 필요하면 Cuckoo가 더 작습니다.

삭제는 얼마나 안전한가

삭제가 Cuckoo filter의 진짜 장점입니다. 원소 1만 개를 넣고 짝수 5천 개를 지운 뒤 조회했습니다.

확인 대상결과
남아 있어야 할 홀수5,000 / 5,000 있음
지운 짝수 중 “있음”으로 답한 수4

남은 4개는 지운 원소의 지문이 다른 원소 지문과 우연히 겹친 오탐입니다. 지운 뒤에도 오탐률만큼은 “있음”으로 답할 수 있다는 뜻이고, 이는 정상 동작입니다.

함정은 따로 있습니다. 넣은 적 없는 원소를 지우면 안 됩니다. 오탐으로 “있음”이 나오는 원소를 일부러 찾아 remove를 불렀더니, 같은 지문을 가진 진짜 원소 하나가 사라졌습니다. 필터는 지문만 보므로 둘을 구별할 수 없습니다. 같은 원소를 두 번 지우는 것도 마찬가지입니다.

따라서 Cuckoo filter의 삭제는 “확실히 넣었던 원소를 한 번만 지운다”는 조건을 호출하는 쪽이 지켜야 합니다. 원본 집합이 다른 곳에 있고 필터는 그 앞의 캐시 역할만 할 때는 쉽게 지켜지는 조건입니다. 외부 입력을 그대로 지우는 구조에서는 지켜지지 않습니다.

퀴즈삭제 조건을 확인합니다

답을 고르면 해설이 나옵니다.

1문제 중 0개 맞힘

  1. 원본에 없는 키를 Cuckoo filter가 '있음'으로 답했습니다. 이 응답만 믿고 삭제 요청을 처리해도 됩니까?

언제 무엇을 쓰나

상황고를 것
오탐률 1~3%, 삭제 없음Bloom
오탐률 0.1% 이하Cuckoo
삭제 필요, 지울 원소가 확실히 들어 있음Cuckoo
삭제 필요, 지울 원소를 보장할 수 없음원본에서 삽입 여부를 확인한 뒤 삭제
크기를 미리 알 수 없음둘 다 아님. Scalable Bloom 등

Counting Bloom도 삭제 조건을 없애 주지는 않습니다. 공유 비트를 카운터로 바꾸어 감소시킬 수 있지만, 넣지 않은 원소나 이미 지운 원소의 카운터를 감소시키면 다른 원소를 놓칠 수 있습니다. 근사 조회가 “있음”이라고 답했다는 이유만으로 지우면 안 됩니다. 삽입과 삭제 이력을 호출하는 쪽이 정확히 관리하거나 원본 집합에서 확인해야 합니다.

Cuckoo filter는 제한된 이동 안에 빈 자리를 못 찾으면 삽입이 실패합니다. 실패 경로에서는 위 예제처럼 변경을 되돌리거나 쫓겨난 지문을 별도로 보관해야 기존 원소를 잃지 않습니다. Bloom filter는 넘치게 넣어도 오탐률이 서서히 나빠질 뿐 실패하지 않습니다. 운영에서는 이 차이가 오탐률 수치보다 클 때가 많습니다.

정리

부제는 반쯤 맞습니다. 버킷당 4슬롯이면 96%까지 채우고, 원소당 12비트 이상에서는 같은 공간에 오탐률이 더 낮으며, 삭제도 됩니다. 그러나 원소당 8비트 언저리에서는 Bloom이 더 정확하고, 삭제는 호출하는 쪽의 규율에 기대며, 꽉 차면 실패합니다. “Bloom보다 낫다”보다는 “목표 오탐률이 낮고 삭제가 필요하면 낫다”가 측정에 맞는 문장입니다.

퀴즈필터 앞에 원본 집합을 둔다면

답을 고르면 해설이 나옵니다.

3문제 중 0개 맞힘

  1. 이 글의 같은 공간 비교에서 원소당 8.42비트를 쓰고 삭제는 필요 없습니다. 측정된 오탐률만 기준으로 고르면 무엇을 씁니까?

  2. 쫓겨난 지문의 원래 키를 저장하지 않았습니다. 버킷 수가 2의 거듭제곱일 때 다른 후보 버킷을 어떻게 찾습니까?

  3. 원소 수가 예상보다 계속 늘어납니다. 고정 크기 필터에 삽입할 때 두 구조의 차이는 무엇입니까?

각주

  1. Bin Fan, David G. Andersen, Michael Kaminsky, Michael D. Mitzenmacher, “Cuckoo Filter: Practically Better Than Bloom”, CoNEXT 2014. ↩

~/blog/cuckoo-vs-bloom/en.mdx

Is a cuckoo filter really better than a Bloom filter?

The cuckoo filter paper is subtitled Practically Better Than Bloom. Implementing both and measuring load factor by bucket size, false-positive rate at equal space, and deletion shows it is not always true.

You cannot delete from a Bloom filter. Each bit is shared by several items, so clearing one removes others too. The cuckoo filter, published by Fan et al. in 2014, stores fingerprints in a cuckoo hash table instead, which makes deletion possible, and claims a lower false-positive rate in the same space.1 The paper’s subtitle is “Practically Better Than Bloom”. I implemented both in Python to see how far that holds. Hashing is blake2b, the environment Python 3 on an Apple Silicon laptop. Only ratios are measured, not time, so the language does not affect the results. The code below is an excerpt with bookkeeping such as the item counter removed.

One fingerprint, two places

A cuckoo filter puts the fingerprint fp of item x into whichever of two candidate buckets has room. If both are full, it evicts one fingerprint and sends that one to its other place. The name comes from the cuckoo pushing eggs out of another bird’s nest.

evict one when full x hash(x) → i1 fingerprint(x) → fp i2 = i1 XOR hash(fp) bucket i1 bucket i2

The tricky part is finding an evicted fingerprint’s other place without the original item, because the table only holds fingerprints. The paper’s answer is partial-key cuckoo hashing.

cuckoo.py
def _alt(s, i, fp):
return (i ^ h64(fp, 99)) % s.nb
def add(s, x):
fp, i1 = s._fp(x); i2 = s._alt(i1, fp)
for i in (i1, i2):
if len(s.t[i]) < s.bs:
s.t[i].append(fp); return True
i = s.rng.choice((i1, i2))
undo = []
for _ in range(s.mk):
j = s.rng.randrange(len(s.t[i]))
undo.append((i, j, s.t[i][j]))
fp, s.t[i][j] = s.t[i][j], fp
i = s._alt(i, fp)
if len(s.t[i]) < s.bs:
s.t[i].append(fp); return True
for i, j, old_fp in reversed(undo):
s.t[i][j] = old_fp
return False

The other place is the current place XORed with a hash of the fingerprint. XOR is its own inverse, so the same expression takes i1 to i2 and i2 back to i1. The original key is not needed. The bucket count must be a power of two so that % nb does not break this.

If either candidate has a free slot, insert there. While the table is mostly empty, this is where nearly every insert ends.

If both are full, pick a random fingerprint, put ours in its slot, and send the evicted one to its other place via _alt. If that is full too, evict again. Record each changed slot and its previous fingerprint in undo.

If no free slot turns up within a fixed number of kicks (500 here), the insert fails. This does not prove the whole table is full; the relocation path failed to find room. The last displaced fingerprint is still outside the table in fp, so returning failure without repair can lose an existing member. The example rolls changes back in reverse order to restore the table before the failed insert. Order matters because a slot may have been changed several times.

Bucket size and load factor

How many fingerprints a bucket holds decides space efficiency. With 2142^{14} buckets and 16-bit fingerprints I inserted until the first failure and recorded the load factor, three times with different seeds.

Slots per bucketTrial 1Trial 2Trial 3
152.3%53.2%48.9%
287.2%87.0%87.6%
496.6%96.3%96.6%
899.1%98.7%99.1%
"b=1" "b=2" "b=4" "b=8" 40 50 60 70 80 90 100 % Load factor at first failure (%)

One slot barely fills half. Four reach 96%, which is why the paper recommends four slots per bucket. Eight fill more, but a lookup compares twice as many fingerprints and false positives grow accordingly.

False-positive rate in equal space

A fair comparison fixes bits per item. I built a cuckoo filter with 2162^{16} slots and four slots per bucket, filled it to 95%, and gave a Bloom filter the same item count and the same total bits, with the optimal number of hash functions k. Lookups used 400,000 items that were never inserted.

Fingerprint bitsBits per itemCuckoo FPRCuckoo bound 2b/2f2b/2^fBloom kBloom FPRBloom theory
88.422.98%3.13%61.78%1.75%
1212.630.182%0.195%90.219%0.232%
1616.840.014%0.012%120.028%0.031%

At a little over 8 bits per item Bloom wins. From 12 bits cuckoo leads, and at 16 its false-positive rate is half of Bloom’s.

The formulas explain it. A cuckoo lookup compares against two buckets, 2b=82b = 8 fingerprints, so its rate is about 2b/2f2b/2^f. An optimal Bloom filter has (1/2)k(1/2)^{k} with k≈0.69⋅m/nk \approx 0.69 \cdot m/n.

εcuckoo≈2b2f,εbloom≈0.6185 m/n\varepsilon_{\text{cuckoo}} \approx \frac{2b}{2^{f}}, \qquad \varepsilon_{\text{bloom}} \approx 0.6185^{\,m/n}

Each extra bit per item halves the cuckoo rate but only multiplies the Bloom rate by 0.6185. Cuckoo starts 2b2b times behind with a steeper slope, so the lines cross. In my implementation the crossover is between 8 and 12 bits. The paper reports it drops to about 7 bits per item with semi-sorting, which compresses the sorted fingerprints within a bucket. I did not implement semi-sorting.

If you live around a 3% false-positive rate, Bloom is smaller. If you need 0.1% or less, cuckoo is smaller.

How safe is deletion

Deletion is the cuckoo filter’s real advantage. I inserted 10,000 items, deleted the 5,000 even ones, and queried.

CheckResult
Odd items that should remain5,000 / 5,000 present
Deleted even items still answering “present”4

The 4 are deleted items whose fingerprint happens to collide with a remaining item’s. After deletion an item can still answer “present” at the false-positive rate, which is correct behaviour.

The trap is elsewhere: you must not delete an item that was never inserted. I searched for an item that is a false positive and called remove on it, and a real member with the same fingerprint disappeared. The filter only sees fingerprints and cannot tell the two apart. Deleting the same item twice does the same damage.

So deletion holds only if the caller guarantees it deletes items that were definitely inserted, once each. That is easy when the authoritative set lives elsewhere and the filter is a cache in front of it. It does not hold when external input is deleted directly.

QuizCheckpoint: authorizing deletion

Choose an answer to see the explanation.

0 of 1 right

  1. A cuckoo filter reports 'present' for a key absent from the source set. Can that response alone authorize deletion?

When to use which

SituationChoice
1–3% false positives, no deletionBloom
0.1% false positives or lessCuckoo
Deletion, deleted items known to be presentCuckoo
Deletion, no such guaranteeCheck insertion in the source set before deleting
Size unknown in advanceNeither; e.g. Scalable Bloom

Counting Bloom does not remove the deletion requirement either. Counters replace shared bits and can be decremented, but decrementing for an item never inserted, or already deleted, can make another member disappear from lookups. An approximate “present” response must not authorize deletion. The caller must track successful insertions and deletions exactly or check the source set.

A cuckoo filter can fail to find a slot within its relocation budget. Its failure path must roll back changes as above, or retain the displaced fingerprint separately, to avoid losing an existing member. Overfilling a Bloom filter only degrades its false-positive rate gradually. In production this difference often matters more than the rates.

Summary

The subtitle is half right. With four slots per bucket it fills to 96%, from 12 bits per item it has a lower false-positive rate in the same space, and it supports deletion. But around 8 bits per item Bloom is more accurate, deletion depends on the caller’s discipline, and a full filter fails. “Better than Bloom when the target false-positive rate is low and you need deletion” is the sentence the measurements support.

QuizPutting a filter in front of the source set

Choose an answer to see the explanation.

0 of 3 right

  1. In this post's equal-space comparison, you have 8.42 bits per item and need no deletion. Which measured false-positive rate favors your choice?

  2. An evicted fingerprint has no original key stored. With a power-of-two bucket count, how do you find its other candidate bucket?

  3. The item count keeps growing beyond your estimate. How do these fixed-size filters behave on insertion?

Notes

  1. Bin Fan, David G. Andersen, Michael Kaminsky, Michael D. Mitzenmacher, “Cuckoo Filter: Practically Better Than Bloom”, CoNEXT 2014. ↩

ko.mdx

단축키Keyboard

/ ⌘K
글 검색Search posts
t
밝은/어두운 테마Light or dark theme
l
한국어/영어, 읽던 자리 유지Korean or English, keeping your place
[ ]
이전/다음 절Previous or next section
?
이 목록This list

↑↓ 이동move↵ 열기openesc 닫기close