Bloom Filter·Skip List·Treap·Cuckoo Hashing으로 검색 경로 최적화하기
Bloom Filter, Skip List, Treap, Cuckoo Hashing의 특성과 트레이드오프를 비교하고 저지연 검색과 메모리 효율을 위한 설계 기준을 정리한다.
2026-08-14 · 최초 발행 2024-04-29
검색 경로에서 데이터 구조가 맡는 역할
대규모 트래픽과 데이터가 함께 늘어나는 시스템에서는 데이터 구조 선택이 성능의 상한을 좌우한다. Bloom Filter는 존재하지 않는 키의 탐색을 앞단에서 걸러내고, Skip List와 Treap은 순서가 필요한 데이터를 다루며, Cuckoo Hashing은 짧은 조회 경로가 필요한 핫셋에 적합하다.
각 구조는 정확성 모델, 메모리 배치, 동시성 제어 방식이 다르다. 하나를 일괄 적용하기보다 워크로드별로 검색 경로를 나누는 편이 현실적이다.
부재 키, 순서 데이터, 핫셋을 다루는 방식
Bloom Filter는 비트 배열과 k개의 해시 함수를 이용하는 확률적 멤버십 질의 구조다. 오탐(False Positive)은 가능하지만 미탐(False Negative)은 없다. 비트 배열 크기 m과 해시 함수 수 k를 조절해 오탐률을 제어한다.
Skip List는 레벨별 다중 포인터를 둔 확률적 균형 검색 구조다. 탐색·삽입·삭제는 평균 O(log n)이며, 구현이 비교적 간결하고 동시성 제어와도 잘 맞는다.
Treap은 이진 탐색 트리에 힙(priority) 속성을 결합한 랜덤화 균형 트리다. 난수 priority를 통해 평균 균형을 유지하고, 회전을 이용해 구조를 관리한다. 연산은 평균 O(log n)이다.
Cuckoo Hashing은 두 개 이상의 해시 위치 사이에서 항목 재배치(relocation)를 허용한다. 조회는 O(1) 기대값을 가지며 높은 부하율을 노릴 수 있다. 대신 삽입 중 재배치가 길어지거나 실패할 경우 재해시(rehash) 처리가 필요하다.
성능뿐 아니라 정확성과 메모리 배치를 함께 본다
Bloom Filter의 조회와 삽입은 O(k)이며, k는 보통 4~10이다. 연속된 비트 배열을 사용하므로 캐시 지역성이 좋다. 삭제는 기본적으로 불가능하며 Counting형이 필요하다.
Skip List와 Treap은 평균 O(log n) 연산을 제공하지만 노드와 포인터 중심의 구조라 캐시 미스가 발생할 수 있다. Skip List는 락-프리 또는 옵티미스틱 락 구현에 적합하고 RCU도 적용할 수 있다. Treap은 회전 구간 잠금이나 STM/RCU 조합을 설계 대상으로 둔다.
Cuckoo Hashing은 테이블 또는 버킷을 연속 배치해 캐시 효율을 높일 수 있다. 버킷 단위의 미세 잠금이 가능하지만, 재배치 구간의 원자성과 재배치 경로 잠금 순서를 보장해야 한다.
| 구조 | 평균 검색 | 평균 삽입 | 평균 삭제 | 공간 효율 | 일관성/정확성 | 확장성(부하율) | 운영 관점 |
|---|---|---|---|---|---|---|---|
| Bloom Filter | O(k) | O(k) | 기본 불가(Counting형 필요) | 매우 높음(≈ 9.6 bits/key @1% FPR) | 오탐 있음, 미탐 없음 | 확장 어려움(Scalable BF로 완화) | 파라미터 튜닝 필요 |
| Skip List | O(log n) | O(log n) | O(log n) | 중간(포인터 오버헤드) | 정확 | 높음(Sharding/Lock-free) | 구현/디버깅 용이 |
| Treap | O(log n) | O(log n) | O(log n) | 중간 | 정확(난수 의존 평균 보장) | 높음 | 코드 간결, 재현성 관리 필요 |
| Cuckoo Hashing | O(1) | O(1)* | O(1) | 높음(부하율 0.8~0.95) | 정확 | 재해시 필요 시 비용 발생 | 재배치/스태시 운용 필요 |
*평균 삽입은 재배치 실패 시 재해시 비용 발생 가능
Bloom Filter부터 인덱스까지 이어지는 조회 흐름
조회 경로는 Bloom Filter로 먼저 부재 후보를 분리한 뒤 메모리 인덱스와 디스크 인덱스로 이어진다. Cuckoo Hashing에서는 재배치 한도를 넘었을 때 스태시 저장 또는 재해시를 처리한다. Skip List의 읽기 경로에는 RCU나 락-프리 탐색을, 쓰기 경로에는 옵티미스틱 잠금과 검증 단계를 적용할 수 있다.
스토리지와 네트워크 경로에서의 조합
LSM-Tree 계열에서는 MemTable에 Skip List를 두어 로그구조 병합(Compaction) 전의 정렬 상태를 유지할 수 있다. SSTable 앞에는 Bloom Filter를 배치해 부재 키의 디스크 탐색을 피한다. RocksDB의 CuckooTable은 읽기 편향 워크로드와 고정 길이 키/값에 선택적으로 적용할 수 있다.
대규모 캐시나 키-밸류 저장소에서는 Bloom Filter가 부재 요청을 앞단에서 차단해 백엔드 I/O를 줄인다. 핫셋은 Cuckoo Hashing으로 O(1) 조회와 높은 부하율을 목표로 두고, NUMA 노드별 샤딩을 구성할 수 있다.
패킷 필터와 블랙리스트는 Bloom Filter의 실시간 판별과 오탐 허용 정책을 활용할 수 있다. DPDK나 로드밸런서의 세션 테이블에는 Cuckoo Hashing을 적용해 고정 지연을 관리한다.
순서 통계나 범위 질의가 필요한 경우에는 Treap에 order-statistics(서브트리 크기)를 확장해 랭크와 셀렉트를 지원할 수 있다. Skip List에는 레벨 힌트와 prefetch를 적용해 범위 스캔을 최적화한다.
메모리 예산과 지연 효과를 계산하는 기준
키 1억개(n=1e8), 목표 오탐률 p=1%를 가정하면 최적 m/n은 -ln p / (ln2)^2 ≈ 4.6052 / 0.48045 ≈ 9.59 bits/key다. 총 메모리 m ≈ 9.59 × 1e8 bits ≈ 959 Mb ≈ 120 MB이고, 해시 함수는 k ≈ ln2 × m/n ≈ 0.693 × 9.59 ≈ 6.64 → 7개가 된다. 조회의 90%가 미스라면 Bloom Filter 없이 디스크 탐색은 90% 발생한다. Bloom Filter를 적용하면 0.01 × 90% = 0.9%만 디스크에 접근하므로 전체 조회 대비 디스크 I/O는 약 89.1% 절감된다.
Cuckoo Hashing은 버킷 크기 4, 2-해시 구성에서 안정 부하율 0.90.95를 달성할 수 있다. 동일 키 수를 기준으로 체이닝 해시의 부하율 0.50.75와 비교하면 메모리를 20~80% 절감할 수 있다.
Skip List와 RCU는 읽기 다중화 환경에서 coarse-grained 락 트리 대비 1.5~3배 처리량 향상을 기대할 수 있다. 이 값은 워크로드·CPU·NUMA에 의존한다. Treap은 AVL이나 Red-Black보다 회전 규칙이 단순해 코드 복잡도를 줄일 수 있으며, Bloom Filter와 Cuckoo Hashing은 파라미터와 재해시 정책을 명확히 할수록 장애 시나리오의 예측 가능성이 높아진다.
구조별 운영 기준과 감수할 비용
Bloom Filter는 목표 오탐률에서 m과 k를 산출한 뒤 k를 4~8 범위로 제한하고, SIMD 해시와 비트셋 사용을 검토한다. 데이터 증가에는 Scalable/Partitioned BF를 적용하고 레벨별 FPR을 다르게 둘 수 있다. 극소 메모리 비용과 오탐으로 발생하는 불필요 I/O 사이의 균형이 핵심이다.
Skip List는 레벨 하향식 옵티미스틱 락, ABA 방지, RCU 또는 epoch GC 기반 메모리 재활용을 함께 설계한다. 노드 풀링과 연속 메모리 청크는 포인터 구조의 캐시 미스를 완화한다. 간결성과 동시성에는 유리하지만 포인터 비용과 캐시 비효율을 감수해야 한다.
Treap은 고정 시드 난수나 deterministic priority 전략으로 재현성을 관리한다. order-statistics와 interval treap으로 확장할 수 있지만, 난수 품질에 따라 최악 케이스가 가능하다는 점은 남는다.
Cuckoo Hashing은 재배치 한도, 스태시 크기, 백오프, 재해시 트리거를 사전에 정한다. 버킷 잠금과 이중 해시의 원자적 스왑, 재배치 경로 잠금 순서도 함께 규약화해야 한다. 높은 부하율과 짧은 조회 경로의 대가로 삽입 변동성과 재해시 비용을 관리하게 된다.
선택 전에 확인할 조건
- 읽기/쓰기 비율, 미스율, 범위 질의 여부를 먼저 파악한다.
- 오탐 허용 여부와 재현성·감사 요구를 확인한다.
- bits/key와 부하율 목표에 맞춰 메모리·스토리지 예산을 잡는다.
- 락 전략, 재해시 정책, metrics·재배치율·FPR 관측 방식을 운영 설계에 포함한다.
Bloom Filter로 부재 탐색을 차단하고, 메모리 인덱스에 Cuckoo Hashing이나 Skip List를 배치하며, 순서성과 확장성 요구에는 Treap과 LSM 구조를 결합할 수 있다. 구조 자체보다 파라미터, 동시성, 재해시 정책을 어떤 경로에 적용하는지가 운영 안정성을 결정한다.