HyperLogLog는 방대한 데이터에서 "서로 다른 값이 몇 개인가"(카디널리티, cardinality)를 아주 적은 메모리로 추정하는 확률적 알고리즘입니다. 정확한 개수 대신 약 1~2%의 오차를 허용하는 대가로, 수억 개의 유니크 값을 세는 데 고작 12KB 안팎이면 충분합니다.
일 단위 순 방문자(UV)를 세야 했던 적이 있습니다. 처음엔 Redis Set에 방문자 ID를 다 넣고 SCARD로 셌죠. 방문자가 수천만이 되자 Set 하나가 수 GB를 먹었습니다. 날짜별, 페이지별로 쪼개니 메모리가 폭발했고요. 정확히 셀 필요가 있었을까요? "어제 UV 3,120만 vs 3,118만"의 2만 차이가 의사결정을 바꾸지 않는다면, 그 정밀도를 위해 GB를 태우는 건 낭비였습니다.
정확히 세려면 왜 이렇게 비싼가
중복 없이 유니크를 세려면, 원리적으로 "이미 본 값"을 어딘가 기억해야 합니다. 해시 셋이든 정렬이든, 결국 서로 다른 원소 수 n에 비례하는 메모리가 듭니다. n이 1억이면 1억 개를 기억해야 하죠. HyperLogLog는 이 전제를 깹니다. 원소를 저장하지 않고, 해시 값의 통계적 성질만 관찰합니다.
핵심 직관 — 앞자리 0의 개수
비유가 하나 있습니다. 동전을 여러 번 던져 "앞면이 연속으로 나온 최대 횟수"를 기록한다고 합시다. 누군가 "앞면 10연속을 봤다"고 하면, 그 사람은 대략 2^10, 즉 1000번쯤 던졌으리라 짐작할 수 있죠. 드문 사건을 봤다는 것 자체가 시도 횟수가 많았다는 증거입니다.
HyperLogLog는 각 값을 해시해서 그 이진수의 앞쪽 연속된 0의 개수를 봅니다. 유니크 값이 많을수록 "앞에 0이 아주 많이 붙은 희귀한 해시"를 만날 확률이 커집니다. 이 관찰만으로 유니크 개수를 역산하는 거죠. 다만 관찰 하나로는 편차가 크니, 해시의 일부 비트로 값을 수천 개의 버킷(레지스터)에 나눠 담고, 버킷별 최댓값들을 조화평균으로 합쳐 오차를 줄입니다.
# 개념 뼈대 (실제 구현은 보정항이 더 붙습니다)
import math
class HLL:
def __init__(self, p=14): # 2^14 = 16384개 버킷
self.p = p
self.m = 1 << p
self.reg = [0] * self.m
def add(self, x):
h = hash64(x)
idx = h >> (64 - self.p) # 앞 p비트로 버킷 선택
rest = (h << self.p) | (1 << (self.p - 1))
rank = 64 - self.p - rest.bit_length() + 1 # 앞자리 0 개수+1
self.reg[idx] = max(self.reg[idx], rank)
def count(self):
alpha = 0.7213 / (1 + 1.079 / self.m)
z = sum(2.0 ** -r for r in self.reg)
return int(alpha * self.m * self.m / z)메모리와 오차의 맞교환
| 방식 | 1억 유니크 메모리 | 정확도 |
|---|---|---|
| 해시 Set(정확) | 수 GB | 정확 |
| HLL (p=14) | 약 12 KB | 오차 약 0.8% |
| HLL (p=16) | 약 48 KB | 오차 약 0.4% |
표준오차는 대략 1.04/√m입니다. 버킷을 4배 늘리면 오차는 절반이 되죠. Redis의 PFADD/PFCOUNT가 바로 이 HyperLogLog 구현이고, 키 하나가 최대 12KB로 고정입니다. 유니크가 1개든 10억 개든 메모리가 그대로라는 게 핵심 매력입니다.
가장 강력한 성질 — 병합(union)
제가 가장 아끼는 기능은 합집합입니다. HLL은 버킷별 최댓값 배열이라, 두 HLL을 원소별 max로 합치면 두 집합의 합집합에 대한 카디널리티가 나옵니다. 오차 누적 없이요. 덕분에 "일별 UV"들을 그냥 병합해 "주간 UV"를 얻을 수 있습니다. 정확한 Set이라면 매번 원본을 다시 합쳐야 하지만, HLL은 요약본끼리 더하면 끝입니다. Redis PFMERGE가 이걸 해줍니다.
주의할 점
- 교집합은 직접 안 됩니다. 포함-배제(A + B − A∪B)로 근사할 수 있지만 오차가 크게 증폭되니 신뢰하지 마세요.
- 작은 카디널리티 구간은 별도 보정이 필요합니다. 그래서 실제 구현은 값이 적을 때 선형 계수(linear counting)로 전환하는 등의 보정을 넣습니다.
- 정확한 값이 필요한 정산·과금에는 부적합합니다. 대시보드·트렌드처럼 근사로 충분한 곳에 쓰세요.
자주 묻는 질문
오차 1%면 실무에서 괜찮은가요?
UV, 순 검색어 수, 고유 IP 수처럼 "규모와 추세"를 보는 지표라면 대개 충분합니다. 반대로 청구 금액, 정확한 재고, 법적 집계처럼 한 건도 틀리면 안 되는 곳에는 쓰지 마세요.
Redis HLL은 정말 12KB 고정인가요?
기본 정밀도에서 조밀 표현(dense)일 때 약 12KB가 상한입니다. 카디널리티가 아주 작을 땐 희소 표현(sparse)으로 더 작게 유지하다가, 커지면 조밀 표현으로 전환합니다.
버킷 수(정밀도 p)는 어떻게 정하나요?
필요한 오차에서 역산합니다. 표준오차 1.04/√(2^p)를 목표치 이하로 만드는 p를 고르면 됩니다. 대부분 p=14(오차 약 0.8%)가 무난한 기본값입니다.
HyperLogLog와 Count-Min Sketch는 뭐가 다른가요?
HLL은 "서로 다른 값의 개수"를 셉니다. Count-Min Sketch는 "각 값이 몇 번 나왔는가"(빈도)를 추정합니다. 질문 자체가 다르니 용도에 맞게 고르세요.
댓글 0