확률적 자료구조 — 정확함을 메모리와 맞바꾸는 기술 (Bloom·HyperLogLog·Count-Min)
Bloom 필터·HyperLogLog·Count-Min 스케치 — 정확도를 메모리와 바꾸는 확률적 자료구조. 거짓 양성률, 카디널리티 추정, Redis·Cassandra 응용을 그림으로.
“정확한 답”을 포기하면 메모리가 천 배 줄어든다
10억 개의 URL 중에 이 URL을 전에 본 적 있나? 방문자 1억 명 중 유니크 방문자는 몇 명인가? 검색어 스트림에서 이 단어가 몇 번 나왔나? 정직하게 풀면 전부 모든 원소를 저장해야 합니다 — HashSet에 10억 개를 담으면 수십 GB입니다.
확률적 자료구조는 다른 거래를 제안합니다. “틀릴 확률을 아주 작게 통제하는 대신, 메모리를 수백~수천 배 줄인다.” 답이 가끔 틀리지만 어떻게 틀리는지가 명확하고(한 방향으로만 틀림), 그 오차율을 수식으로 조절할 수 있다는 게 핵심입니다. 이 글은 그중 가장 널리 쓰이는 셋 — Bloom filter(존재 여부), HyperLogLog(유니크 개수), Count-Min Sketch(빈도) — 를 다룹니다.
Bloom Filter — “확실히 없음” 또는 “아마 있음”
블룸 필터는 m비트짜리 배열과 k개의 독립적인 해시 함수로 만듭니다. 원소를 추가할 땐 k개 해시가 가리키는 k개의 비트를 모두 1로 켭니다. 조회할 땐 그 k개 비트를 봅니다 — 하나라도 0이면 확실히 없음(추가됐다면 반드시 켜졌을 테니까), 전부 1이면 아마 있음(우연히 다 켜졌을 수도 있으니 거짓 양성 가능).
비대칭이 포인트입니다. 거짓 음성(false negative)은 절대 없습니다 — 넣은 원소는 비트가 반드시 켜져 있으니까요. 대신 거짓 양성(false positive) 은 존재합니다. 다른 원소들이 우연히 같은 비트들을 다 켜놨을 수 있죠. 거짓 양성 확률은 비트 수 m, 원소 수 n, 해시 수 k로 결정됩니다.
이를 최소화하는 최적 해시 개수는 $k = \frac{m}{n}\ln 2$이고, 이때 원소당 약 9.6비트면 거짓 양성 1%를 얻습니다. HashSet이 원소당 수십 바이트임을 생각하면 수십 배 절약입니다.
1
2
3
4
5
6
// 원소당 약 10비트, 거짓 양성률 1%로 1000만 개를 약 12MB에
BloomFilter<String> filter =
BloomFilter.create(Funnels.stringFunnel(UTF_8), 10_000_000, 0.01);
filter.put(url);
if (filter.mightContain(url)) { /* 아마 있음 → 진짜 저장소 확인 */ }
else { /* 확실히 없음 → 디스크 조회 자체를 건너뜀 */ }
마지막 줄이 블룸 필터의 진짜 가치입니다. Cassandra·HBase·LevelDB의 SSTable은 디스크를 읽기 전에 블룸 필터로 “이 키는 확실히 이 파일에 없음”을 걸러, 헛디스크 I/O를 없앱니다. 단점은 삭제 불가 — 비트를 0으로 되돌리면 그 비트를 공유하는 다른 원소까지 지워버립니다. 삭제가 필요하면 비트 대신 카운터를 쓰는 Counting Bloom Filter를 씁니다.
HyperLogLog — 1.5KB로 10억 개의 유니크를 센다
“유니크 방문자 수”를 정확히 세려면 본 적 있는 ID를 전부 기억해야 합니다. HyperLogLog는 이걸 확률로 우회합니다. 핵심 직관: 균등하게 해시된 값들에서 선두 0이 연속 p개 나오는 사건의 확률은 $2^{-(p+1)}$입니다. 그러니 스트림에서 관찰한 최대 선두 0 개수가 p라면, 대략 $2^{p}$개쯤은 봤다고 역추정할 수 있습니다 — 동전을 계속 던지다 “앞면 10번 연속”을 봤다면 어림잡아 $2^{10}$번쯤 던졌겠다고 추정하는 것과 같습니다.
선두 0 하나만 보면 분산이 큽니다(운 나쁘게 한 번 크게 나오면 과대추정). 그래서 HLL은 해시의 앞 비트로 원소를 m개의 버킷에 나눠 각 버킷의 최대 선두 0을 따로 기록하고, 그 값들의 조화평균으로 합칩니다. 표준오차는 $\frac{1.04}{\sqrt{m}}$ — m=16384(2¹⁴)이면 오차 약 0.8%로, 고작 12~16KB에 수십억 카디널리티를 추정합니다. Redis의 PFADD/PFCOUNT가 바로 이것입니다.
1
2
3
4
5
redis> PFADD visitors:2025-08-19 user:42 user:99 user:42
(integer) 1
redis> PFCOUNT visitors:2025-08-19 # 유니크만 카운트 (user:42 중복 무시)
(integer) 2
# 키 하나당 최대 12KB 고정. 1억 유니크든 10억이든 메모리 동일.
여러 날짜의 유니크 합집합도 PFMERGE로 즉시 구합니다 — 정확한 집합 연산이라면 불가능한 일입니다.
Count-Min Sketch — 빈도를 작은 표로
블룸이 “있나/없나”라면, Count-Min Sketch는 “몇 번 나왔나“입니다. d개의 해시와 d × w 카운터 표를 두고, 원소가 올 때마다 각 행에서 해시가 가리킨 칸을 +1 합니다. 빈도를 물으면 그 원소가 가리키는 d개 칸 중 최솟값을 답합니다 — 해시 충돌은 카운트를 부풀리기만 하므로, 최솟값이 가장 덜 오염된 추정이기 때문입니다.
flowchart LR
K["원소 x"] --> H1["행1 해시 → +1"]
K --> H2["행2 해시 → +1"]
K --> H3["행3 해시 → +1"]
H1 --> Q["조회: 세 칸의 min<br/>(충돌은 과대추정만)"]
H2 --> Q
H3 --> Q
블룸 필터처럼 한 방향으로만 틀립니다(과소추정은 없고 과대추정만). 헤비 히터(가장 빈번한 검색어·핫키) 탐지, 네트워크 트래픽 통계에 쓰입니다. AWS Kinesis·실시간 분석 파이프라인에서 무한 스트림의 상위 빈도를 상수 메모리로 잡을 때 이 계열을 씁니다.
| 구조 | 답하는 질문 | 틀리는 방향 | 메모리 |
|---|---|---|---|
| Bloom filter | 있나/없나 | 거짓 양성만 | 원소당 ~10비트 |
| HyperLogLog | 유니크 몇 개 | ±표준오차 | 키당 ~12KB 고정 |
| Count-Min Sketch | 몇 번 나왔나 | 과대추정만 | d×w 카운터 |
프로덕션 함정
| 함정 | 증상 | 해법 |
|---|---|---|
블룸 n 과소예측 | 원소가 예상보다 많아 비트 포화 → 거짓 양성률 폭등 | 용량 여유 있게, 포화 시 재구축/스케일러블 블룸 |
| 블룸에서 삭제 시도 | 비트 0으로 끄자 다른 원소가 거짓 음성 | Counting Bloom 또는 재구축 |
| HLL을 소량 카디널리티에 | 작은 n에서 상대오차 큼 | HLL++ 선형카운팅 보정(작은 범위 별도 추정) |
| Count-Min 폭 부족 | 핫키 충돌로 과대추정 심함 | w를 ε 기준으로 산정, conservative update |
| 해시 품질 불량 | 비균등 분포로 추정 붕괴 | MurmurHash/xxHash 등 균등 해시 사용 |
면접/리뷰 단골 질문
- Q. 블룸 필터가 거짓 음성이 없는 이유? → 추가 시 해당 비트들을 반드시 켜므로, 넣은 원소의 비트는 항상 1. 0이 보이면 추가된 적 없다는 확정. 거짓 양성만 가능.
- Q. 블룸 필터에서 삭제가 안 되는 이유와 대안? → 비트를 공유하므로 끄면 다른 원소를 거짓 음성으로 만듦. 대안은 카운터를 쓰는 Counting Bloom.
- Q. HyperLogLog는 어떻게 메모리가 고정인가? → 원소를 저장하지 않고 버킷별 “최대 선두 0”만 기록. 카디널리티가 아무리 커도 레지스터 개수(m)는 그대로 → 12KB 고정.
- Q. Count-Min에서 왜 min을 답하나? → 충돌은 카운트를 더하기만(과대추정) 하므로, 여러 행 중 최솟값이 충돌 오염이 가장 적은 추정.
- Q. 이런 구조를 언제 쓰나? → 정확한 답이 불필요하고 메모리/속도가 결정적일 때. SSTable 사전필터(블룸), 유니크 방문자(HLL), 헤비히터(CMS).
정리
- 확률적 자료구조는 통제된 오차를 받아들이는 대신 메모리를 수백~수천 배 줄인다 — 그리고 한 방향으로만 틀린다.
- Bloom: 거짓 음성 0, 거짓 양성만. SSTable·캐시 사전필터. 삭제는 Counting Bloom.
- HyperLogLog: 선두 0 관찰로 카디널리티를 추정, 키당 ~12KB 고정. Redis
PFADD/PFCOUNT. - Count-Min Sketch: 빈도를 작은 표로 과대추정만 하며 추정. 스트림 헤비히터 탐지.
「알고리즘 A-Z」는 복잡도 분석의 “정확함의 비용”에서 출발해, 여기서 그 비용을 확률로 흥정하는 데까지 왔습니다. 다음 글은 같은 해시를 분산 시스템의 데이터 배치에 쓰는 일관된 해싱입니다.
</content>