~/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를 두 후보 버킷 중 빈 자리가 있는 곳에 넣습니다. 둘 다 차 있으면 한쪽의 지문 하나를 쫓아내고 그 지문을 자기 다른 자리로 보냅니다. 뻐꾸기가 남의 둥지에서 알을 밀어내는 것과 같다고 해서 이 이름이 붙었습니다.
까다로운 점은 쫓겨난 지문의 다른 자리를 원래 원소 없이 알아내야 한다는 것입니다. 테이블에는 지문만 있으니까요. 논문의 해법이 partial-key cuckoo hashing입니다.
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에 남아 있으므로, 그대로 실패를 반환하면 기존 원소를 잃을 수 있습니다. 예제는 변경을 역순으로 되돌려 실패한 삽입 전의 테이블을 복원합니다. 같은 슬롯을 여러 번 바꿨을 수 있어 되돌리는 순서도 중요합니다.
버킷 크기와 적재율
버킷 하나에 지문을 몇 개 담느냐가 공간 효율을 정합니다. 버킷 개, 16비트 지문으로 첫 삽입 실패가 날 때까지 넣고 적재율을 봤습니다. 시드를 바꿔 세 번 반복했습니다.
| 버킷당 슬롯 | 시도 1 | 시도 2 | 시도 3 |
|---|---|---|---|
| 1 | 52.3% | 53.2% | 48.9% |
| 2 | 87.2% | 87.0% | 87.6% |
| 4 | 96.6% | 96.3% | 96.6% |
| 8 | 99.1% | 98.7% | 99.1% |
슬롯이 하나면 절반을 겨우 채웁니다. 넷이면 96%까지 갑니다. 논문이 기본값으로 버킷당 4슬롯을 권하는 이유입니다. 8로 늘리면 더 채울 수 있지만 조회 때 비교할 지문이 두 배가 되고, 그만큼 오탐도 늘어납니다.
같은 공간에서 오탐률
공정하게 비교하려면 원소당 비트 수를 맞춰야 합니다. Cuckoo filter를 슬롯 개, 버킷당 4슬롯으로 만들어 95%까지 채우고, 같은 원소 수에 같은 총 비트를 Bloom filter에 줬습니다. Bloom의 해시 함수 개수 k는 최적값을 썼습니다. 넣지 않은 원소 40만 개로 조회했습니다.
| 지문 비트 | 원소당 비트 | Cuckoo 오탐률 | Cuckoo 상한 | Bloom k | Bloom 오탐률 | Bloom 이론값 |
|---|---|---|---|---|---|---|
| 8 | 8.42 | 2.98% | 3.13% | 6 | 1.78% | 1.75% |
| 12 | 12.63 | 0.182% | 0.195% | 9 | 0.219% | 0.232% |
| 16 | 16.84 | 0.014% | 0.012% | 12 | 0.028% | 0.031% |
원소당 8비트 남짓에서는 Bloom이 이깁니다. 12비트부터 Cuckoo가 앞서고, 16비트에서는 오탐률이 절반입니다.
이유는 식에 있습니다. Cuckoo는 조회 때 버킷 두 개, 지문 개와 비교하므로 오탐률이 대략 입니다. Bloom은 최적일 때 이고 입니다.
원소당 비트가 늘 때 Cuckoo는 비트 하나당 오탐률이 절반으로 줄고 Bloom은 0.6185배로 줄어듭니다. 출발점은 Cuckoo가 배만큼 불리하지만 기울기가 더 가파르니 어느 지점에서 교차합니다. 제 구현에서는 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개 맞힘
원본에 없는 키를 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개 맞힘
이 글의 같은 공간 비교에서 원소당 8.42비트를 쓰고 삭제는 필요 없습니다. 측정된 오탐률만 기준으로 고르면 무엇을 씁니까?
본문 표에서 이 행의 Bloom 오탐률은 1.78%, Cuckoo는 2.98%입니다. 긴 지문을 쓴 행에서는 순서가 바뀌므로 제목만 보고 항상 Cuckoo를 고르면 안 됩니다.
쫓겨난 지문의 원래 키를 저장하지 않았습니다. 버킷 수가 2의 거듭제곱일 때 다른 후보 버킷을 어떻게 찾습니까?
XOR은 같은 값을 다시 적용하면 되돌아갑니다. 현재 버킷과 지문만으로 두 후보를 오갈 수 있고, 본문의 버킷 수 조건은 나머지 연산이 이 성질을 깨지 않도록 합니다.
원소 수가 예상보다 계속 늘어납니다. 고정 크기 필터에 삽입할 때 두 구조의 차이는 무엇입니까?
Cuckoo는 제한된 이동 안에 빈 슬롯을 찾아야 합니다. 실패하면 쫓겨난 지문이 밖에 남을 수 있어 예제는 변경을 역순으로 되돌립니다. Bloom은 비트를 계속 설정할 수 있지만 오탐률이 올라갑니다. 크기를 모르면 확장 가능한 구조를 검토해야 합니다.
각주
-
Bin Fan, David G. Andersen, Michael Kaminsky, Michael D. Mitzenmacher, “Cuckoo Filter: Practically Better Than Bloom”, CoNEXT 2014. ↩