홍라이프 계산기하이퍼로그로그 오차·메모리 계산기 쉽게 이해하기 — 개념과 원리
하이퍼로그로그(HyperLogLog, HLL)는 순 방문자 수나 서로 다른 검색어 수처럼 데이터 흐름에 들어 있는 고유 항목의 개수를 아주 작은 고정 메모리로 추정하는 알고리즘입니다. 이 계산기는 정밀도 p로 레지스터 수를 정하면 메모리 사용량과 추정의 표준 오차가 함께 결정되는 관계를 보여 줍니다.
계산 방법
- 레지스터 수: m = 2ᵖ
- 표준 오차: σ ≈ 1.04 ÷ √m(백분율로 표시)
- 메모리: m × 레지스터당 비트 ÷ 8 ÷ 1,024 KiB
레지스터에는 앞쪽 0의 개수를 저장하는데, 64비트 해시에서는 63을 넘지 않으므로 보통 6비트를 씁니다.
원리
모든 항목을 무작위처럼 보이는 비트열로 해시합니다. 0이 r개 연속으로 시작할 확률은 2⁻ʳ이므로, 무작위 비트열 n개 중 가장 긴 선행 0의 길이는 약 log₂ n입니다. 이 최댓값 하나만으로는 오차가 너무 크기 때문에, HLL은 해시의 앞 p비트로 레지스터 m개 중 하나를 고르고 레지스터마다 최댓값을 따로 기록합니다. 그다음 조화평균과 보정 상수로 결과를 합칩니다. 독립적인 추정 m개를 평균하면 오차가 1 ÷ √m에 비례해 줄고, 플라졸레 등의 분석에서 상수 1.04가 나옵니다. 중복 항목은 같은 해시값을 가지므로 결과를 바꾸지 않습니다.
예제 풀이
- 입력값: p = 14, 레지스터당 6비트입니다.
- 레지스터 수는 2¹⁴ = 16,384개이고 √16,384 = 128입니다.
- 표준 오차: 1.04 ÷ 128 = 0.008125이므로 0.81%입니다.
- 메모리: 16,384 × 6 ÷ 8 ÷ 1,024 = 12 KiB입니다.
이는 Redis의 PFCOUNT가 쓰는 설정으로, Redis 문서에도 12 KB, 표준 오차 0.81%로 나와 있습니다.
| 정밀도 p (레지스터 = 2^p) | 표준오차 |
|---|---|
| 3.5 | 30.92% |
| 7 | 9.19% |
| 10.5 | 2.73% |
| 14 | 0.81% |
| 17.5 | 0.24% |
| 21 | 0.07% |
| 28 | 0.01% |
결과 해석
표준 오차는 상대 오차이므로 실제 고유 항목이 1,000만 개라면 0.81%는 약 ±81,000개입니다. 추정값의 약 68%가 표준 오차 1배 안에, 약 95%가 2배 안에 들어옵니다. p를 1 올릴 때마다 메모리는 2배가 되고 오차는 √2로 나뉘어 약 0.71배가 되므로, 12 KiB를 48 KiB로 늘려도 오차는 절반으로 줄 뿐입니다.
흔한 실수
- 정확한 개수를 기대하는 경우입니다. 하나하나가 중요하면 정확한 집합을 써야 합니다.
- 표준 오차를 최대 오차로 오해하는 경우입니다. 이보다 큰 편차도 가끔 생깁니다.
- 정밀도나 해시 함수가 다른 스케치를 합치는 경우입니다.
자주 묻는 질문
두 HLL 스케치를 합칠 수 있나요?
p와 해시 함수가 같다면 레지스터마다 최댓값을 취해 합집합의 스케치를 얻을 수 있습니다.
그냥 해시 집합을 쓰면 안 되나요?
집합은 고유 항목 수에 비례하는 메모리가 들어 수 GB가 될 수 있지만 HLL은 수 KB면 됩니다.
얼마나 많은 항목까지 셀 수 있나요?
64비트 해시를 쓰면 현실의 어떤 데이터보다도 많이 셀 수 있고, 메모리는 그대로입니다.
출처: P. Flajolet, É. Fusy, O. Gandouet, F. Meunier, "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm", AofA 2007 · Redis 공식 문서, HyperLogLog(PFADD, PFCOUNT)