1,000억 개를 12KB로 세는 방법 — HyperLogLog의 원리

본문

면접에서 '오늘 사이트의 유니크 방문자 수는?'이라는 질문을 받으면 대부분 HashSet에 요청 ID를 넣는 답을 떠올립니다. 하지만 요청이 1,000억 건이라면 이 접근은 약 1TB의 RAM을 요구하게 되고, 샤딩으로 해결하자니 '몇 명이 왔는가'라는 질문 하나를 위해 분산 시스템 전체를 운영하는 셈이 됩니다. 이 글은 정확성을 의도적으로 포기하는 대신 CPU L2 캐시에 들어갈 크기의 자료구조로 답하는 HyperLogLog의 원리를 단계별로 풀어냅니다.

정확한 집계가 비싼 이유

HashSet은 본 적 있는 모든 ID의 슬롯을 영구히 유지하기 때문에 정확합니다. 바로 그 점이 확장을 막는 이유이기도 합니다. 키를 압축하거나 샤딩해도 메모리는 유니크 항목 수에 선형으로 증가합니다. 일일 유니크가 수십만 건 수준이라면 문제가 아니지만, 수십억 건을 넘어가면 '전부 기억하기'는 엔지니어링 선택이 아니라 클라우드 비용과의 승부가 됩니다.

선행 0비트로 추정하기

핵심 아이디어는 단순합니다. 모든 ID를 균일한 비트 문자열로 해시한 뒤, 첫 1비트가 나오기 전까지의 선행 0비트 개수를 셉니다. 각 비트가 동전 던지기이므로 해시의 50%는 0이 하나 이상, 25%는 둘 이상, 12.5%는 셋 이상의 선행 0을 가집니다. 이를 뒤집으면, 선행 0이 6개인 해시는 1/64 확률의 사건이므로 그런 해시를 관찰했다는 것은 대략 64개 안팎의 항목을 해시했다는 증거가 됩니다. 즉 '지금까지 본 가장 긴 연속 0의 길이' 하나만 추적하면 2^streak으로 유니크 수를 추정할 수 있습니다. 이 아이디어는 Flajolet과 Martin의 1985년 확률적 카운팅 논문으로 거슬러 올라가며, 현대적 형태는 Flajolet, Fusy, Gandouet, Meunier의 2007년 논문에서 제안된 HyperLogLog입니다.

단일 카운터는 너무 노이즈가 큽니다. 글은 약 10줄짜리 Python 코드로 같은 n_items=10,000에 대해 추정치가 실행마다 2~4배 이상 출렁이는 것을 보여줍니다. 운 좋게 긴 스트릭이 한 번 나오거나, 반대로 나오지 않으면 추정 전체가 흔들립니다.

버킷과 조화평균 — HyperLogLog의 완성

HyperLogLog는 카운터를 하나 쓰지 않고 수천 개를 씁니다. 해시의 앞쪽 p비트로 m개의 버킷 중 하나를 선택하고(예: m=16,384), 나머지 비트에서 선행 0을 세어 해당 버킷의 최댓값을 갱신합니다. 각 버킷은 ID 공간의 서로 다른 조각을 보는 독립 추정기이므로, 한 버킷의 행운·불운이 다른 16,383개 버킷에 의해 상쇄됩니다.

평균 방식도 중요합니다. 2^streak이 지수적으로 커지기 때문에 단순 산술평균은 비정상적으로 긴 스트릭을 기록한 버킷 하나에 의해 전체가 지배됩니다. HyperLogLog는 큰 이상치를 강하게 벌주는 조화평균(harmonic mean)을 사용해 바로 이 실패 모드를 방어합니다. 버킷이 m개일 때 표준오차는 약 1.04/√m이며, m=16,384이면 약 0.8%가 나옵니다. Redis 구현이 위치한 지점입니다. 이 오차는 백만 건을 세든 1,000억 건을 세든 동일하고 오직 m에만 의존하므로, 설계 시점에 허용 오차를 한 번 정하면 메모리 비용은 영원히 고정됩니다. 또한 소수 버킷만 채워졌을 때 과대추정을 막는 선형 카운팅(linear counting)과, 2^32 개에 가까워질 때 해시 충돌을 보정하는 대역 보정이 양 끝단을 처리합니다.

병합이 공짜인 이유와 생태계

각 버킷이 '본 적 있는 최대 스트릭'일 뿐이므로 두 HyperLogLog의 병합은 버킷별 최댓값을 취하는 것으로 끝납니다. 원본 ID 접근도 재계산도 필요 없어, 일별 유니크를 주별 유니크로 롤업하는 데 이상적입니다. Redis는 이를 PFADD(추가), PFCOUNT(추정치 조회, 키당 약 12KB), PFMERGE(일별 카운터 병합) 세 명령으로 제공하며, 문서상 표준오차는 0.81%이고 소수·대규모 구간 보정에는 Google의 HyperLogLog++ 논문을 적용했습니다. Redis만이 아니라 BigQuery의 APPROX_COUNT_DISTINCT, Presto·Trino의 approx_distinct, Spark의 approx_count_distinct도 같은 알고리즘이며, 분석 대시보드의 '유니크 방문자' 위젯 대부분이 이 방식으로 돌아가고 있을 가능성이 큽니다.

언제 쓰고 언제 쓰지 말 것인가

저자는 정확한 카운팅을 버리라는 것이 아니라 어떤 질문에 답하는지 알라고 강조합니다. API 호출당 과금, 결제 중복 제거, 쿠폰 사용 여부 판단처럼 정확성이 필요하거나 특정 ID의 존재 여부를 물어야 한다면 HyperLogLog는 맞지 않습니다. 유니크 수가 수천~수십만 수준이면 메모리에 여유롭게 들어가는 HashSet이 공짜로 정확한 답을 줍니다. HyperLogLog가 빛나는 경우는 '유니크 수가 곧 제품'이면서 규모가 충분히 클 때, 즉 유니크 방문자·고유 IP·고유 검색어 수 같은 지표입니다. 필요하지도 않은 정확성 보장을, 미리 선택한 오차 범위 안의 감당 가능한 메모리 비용과 맞바꾸는 것이 이 알고리즘의 전부입니다.

원문: dev.to / 번역·요약: Trawling