쿠쿠 해싱과 지문 필터

원소마다 자리를 두 개씩 주는 설계 하나로 최악 O(1) 조회와 삭제 지원이 동시에 따라옵니다.

두 자리만 확인하면 끝나는 조회

체이닝 해시 테이블의 조회 비용은 버킷에 연결된 원소 수에 비례합니다. 쿠쿠 해싱은 조회 비용의 상한을 상수로 제한합니다. 해시 함수 h1, h2와 배열 T1, T2를 사용합니다. 키 k는 T1[h1(k)]와 T2[h2(k)] 중 정확히 한 곳에만 저장합니다.

조회가 슬롯 두 개만 읽으면 되므로 최악의 경우에도 O(1)입니다.

삽입에는 추가 비용이 듭니다. 대상 슬롯이 차 있으면 새 키가 기존 키를 추방(evict)하고 그 슬롯을 사용합니다. 추방된 키는 자신의 대체 슬롯으로 이동합니다. 대체 슬롯도 차 있으면 해당 슬롯의 키를 다시 추방합니다.

뻐꾸기가 남의 둥지에서 알을 밀어내는 습성에서 이름이 왔습니다.

삽입 A -> T1[h1(A)] 에 B 가 있음   => A 가 B 를 밀어냄
        B -> T2[h2(B)] 에 C 가 있음   => B 가 C 를 밀어냄
          C -> T1[h1(C)] 비어 있음     => 체인 종료

이 이동 과정에 순환이 생기면 삽입이 끝나지 않습니다. 구현은 최대 이동 횟수(MaxLoop)를 제한합니다. 제한을 넘으면 새 해시 함수 쌍으로 전체를 재삽입(rehash)합니다. 슬롯이 하나인 두 해시 함수 구성의 부하율 임계값은 약 50%입니다.

임계값에 가까워질수록 긴 킥아웃 체인과 재해시 가능성이 커집니다. 버킷당 여러 슬롯을 쓰는 쿠쿠 필터에는 이 50% 수치를 그대로 적용하지 않습니다.

해시 함수를 늘리면 생기는 여유

해시 함수를 d개(d ≥ 3)로 늘리면 후보 자리가 d개가 되어 임계값이 크게 올라갑니다. 다만 그 구간에서 삽입 비용이 상수로 유지되는지는 오래 열려 있던 문제였습니다. 2024년 FOCS에 발표된 연구(arXiv:2401.14394)가 임계값 미만의 부하율에서 랜덤 워크 방식 d-ary 쿠쿠 해싱의 삽입 기댓값이 O(1)임을 증명했습니다.

해시 함수 수를 늘리면 한 번의 조회가 확인하는 후보 위치도 늘어납니다. 위치가 서로 다른 캐시 라인에 놓이면 높은 부하율의 공간 이득과 추가 메모리 접근 비용을 함께 비교해야 합니다.

flowchart LR
    K["키 k"] --> H1["후보 h1(k)"]
    K --> H2["후보 h2(k)"]
    H1 -->|빈 슬롯| DONE["삽입 완료"]
    H2 -->|빈 슬롯| DONE
    H1 -->|모두 찼음| EVICT["지문 하나 추방"]
    EVICT --> ALT["XOR로 대체 버킷 계산"]
    ALT -->|빈 슬롯| DONE
    ALT -->|이동 한도 초과| FAIL["삽입 실패 또는 리사이즈"]

지문만 남기고 키를 버리는 방법

쿠쿠 필터는 같은 킥아웃 구조를 사용하지만 원본 키 대신 k비트 지문(fingerprint)만 저장합니다. 추방된 원소를 대체 슬롯으로 옮기려면 두 번째 해시값이 필요합니다. 원본 키를 보관하지 않으므로 이 값을 다시 해싱해서 구할 수 없습니다.

부분 키 쿠쿠 해싱(partial-key cuckoo hashing)이 이 문제를 XOR의 대칭성으로 풉니다. 두 후보 버킷을 아래 관계로 묶습니다.

b1 = hash(x) mod B
b2 = b1 XOR hash(fingerprint(x)) mod B
 
b2 XOR hash(f) = b1      XOR 을 두 번 적용하면 원래 값으로 돌아온다

지문 f와 현재 버킷 번호만 있으면 상대 버킷이 바로 나옵니다. 원본 키를 보관하지 않고도 킥아웃 체인을 이어갈 수 있다는 뜻입니다. 대신 XOR과 나머지 연산이 어긋나지 않도록 버킷 개수를 2의 거듭제곱으로 두는 제약이 따라옵니다.

삭제할 때는 해당 지문을 찾아 슬롯에서 지웁니다. 같은 키를 두 번 넣었으면 두 번 지워야 합니다. 넣은 적 없는 원소의 지문을 지우면, 같은 지문을 사용하는 다른 키의 슬롯을 지울 수 있습니다.

후자는 거짓 음성(false negative)을 만들어 필터의 기본 계약을 깨뜨립니다.

지문 충돌은 오탐도 일으킵니다. 조회는 두 후보 버킷의 여러 슬롯을 확인하므로 오탐률이 지문 한 쌍의 충돌 확률 $2^{-k}$보다 높습니다. 버킷당 b개 슬롯을 거의 채운 구성의 오탐률은 대략 $2b/2^k$입니다. 따라서 버킷 크기와 목표 오탐률을 함께 고려해 k를 정합니다.

블룸 필터와 갈리는 지점

블룸 필터는 m비트 배열과 k개 해시 함수로 집합 멤버십을 근사 판정합니다. 삽입은 k개 비트를 1로 세우고, 조회는 그 k개 비트가 모두 1인지 확인합니다. 비트 하나를 0으로 되돌리면 그 비트를 공유하는 다른 원소의 흔적까지 지워지므로 삭제가 불가능합니다.

Fan 외의 CoNEXT 2014 논문은 수십억 개 이하의 원소와 목표 오탐률 3% 미만에서 쿠쿠 필터가 공간 최적화 블룸 필터보다 적은 공간을 쓴다고 보고합니다. 이는 버킷 크기와 점유율을 포함한 논문의 구성에 대한 실험 결과입니다. 지문을 1비트 늘리면 근사 오탐률은 절반이 되고 조회는 두 후보 버킷을 읽습니다.

운영 기준은 구현별 부하율 한계에서 나옵니다. 원 논문의 버킷당 4슬롯 구성은 실험에서 약 95% 점유율까지 사용하지만, 지문 길이와 버킷 크기가 달라지면 실패 지점도 달라집니다. 삽입 실패율과 킥아웃 횟수를 측정해 그 전에 리사이즈해야 합니다.

버킷을 겹쳐서 줄인 1비트

2025년 논문(arXiv:2505.05847)은 버킷 경계 자체를 바꿉니다. 기존 구조는 슬롯을 겹치지 않는 버킷으로 잘라 쓰는데, 지문 10비트 기준 공간 오버헤드가 1.365배였습니다. 이 논문은 겹치는 윈도우(overlapping window)를 도입했습니다.

기존 버킷    [s0 s1 s2 s3] [s4 s5 s6 s7] [s8 s9 ...]     boundary fixed
window l=2   [s0 s1] [s1 s2] [s2 s3] [s3 s4] ...         overlapped, W = S - l + 1

앞 숫자는 해시 함수 수, 뒷 숫자는 버킷 또는 윈도우의 슬롯 수입니다. 여러 윈도우가 슬롯을 공유하므로 같은 슬롯 수로 더 많은 원소를 저장합니다. 키당 저장 공간은 지문 k비트, 선택 비트 1개, 윈도우 오프셋 비트 1개를 합한 k+2비트입니다. 기존 k+3비트보다 1비트 줄어듭니다.

논문은 온라인 삽입을 지원하는 필터 가운데 가장 작은 공간을 쓴다고 주장합니다.

논문 평가에서 조회 속도는 Prefix Filter, VQF와 동등하지만 삽입은 더 느립니다. 삽입 과정에서 윈도우 경계를 계산하는 추가 비용이 들기 때문입니다.

지문이 이미 최적이었다는 증명

지문 기반 필터를 앞으로 얼마나 더 줄일 수 있는지는 두 편의 이론 논문이 답을 냈습니다.

Kuszmaul과 Walzer(STOC 2024)는 동적 필터의 공간 하한을 증명했습니다. 삽입과 삭제를 모두 지원하려면 n log₂(1/ε) + Ω(n) 비트가 필요합니다. n은 원소 수, ε은 목표 오탐률입니다. 정적 필터의 정보이론적 하한은 n log₂(1/ε)이므로 동적 필터는 원소당 상수 비트가 추가로 필요합니다.

Kuszmaul, Liang, Zhou(FOCS 2025, arXiv:2510.18129)는 그 상수를 확정했습니다. ε이 0으로 갈 때 모든 동적 필터는 n log₂(1/ε) + n log₂e − o(n) 비트를 써야 합니다. 1978년 Carter 등이 도입한 지문 기법이 이 하한을 달성합니다. 따라서 반세기 가까이 사용된 이 기법은 정보이론적으로 더 개선할 수 없습니다.

표의 동적 하한은 블룸 필터의 공간 사용량보다 작습니다. 지문 기반 설계는 삭제를 지원하면서도 고전 블룸 필터보다 적은 공간으로 하한에 도달합니다. 이는 삭제 지원에 반드시 더 많은 공간이 필요하다는 통념과 다릅니다.

앞 섹션의 윈도우 쿠쿠 필터는 키당 k+2비트를 쓰고, 동적 하한은 log₂(1/ε) + 1.4427비트입니다. 지문 길이를 log₂(1/ε)에 대응시키면 둘의 차이는 키당 0.6비트 미만입니다.

남은 문제는 크기입니다. 고정 크기 쿠쿠 필터가 용량에 닿으면 오탐률을 올리는 대신 삽입이 실패하므로 리사이즈나 재구축이 필요합니다. 너무 크게 잡으면 비어 있는 슬롯만큼 메모리를 낭비합니다.

Aleph Filter(Dayan, Bercea, Pagh, 2024, arXiv:2404.04703)는 삽입과 조회, 삭제를 모두 O(1)로 유지합니다. 논문은 데이터가 계속 늘어나는 조건에서 메모리와 오탐률을 제어하고, 최종 크기 추정치가 있으면 정적 필터와 같은 공간 효율에 도달한다고 설명합니다.

정리

쿠쿠 해싱은 두 후보 자리와 킥아웃 체인으로 조회 비용을 최악 O(1)로 고정합니다. 쿠쿠 필터는 지문과 XOR 대칭성을 써서 원본 키 없이 대체 버킷을 계산합니다. 삭제는 실제로 삽입한 원소에만 수행해야 거짓 음성을 막을 수 있습니다.

오탐률은 지문 길이뿐 아니라 두 버킷에서 확인하는 슬롯 수의 영향을 받습니다. 고정 용량에 닿으면 삽입이 실패하므로 측정한 부하율 한계 전에 리사이즈해야 합니다. 윈도우 구조와 동적 필터 하한은 이 공간 비용을 더 줄일 수 있는 조건을 보여줍니다.