한양과기고 에듀테크 수업도구 대시보드

HyperLogLog — "서로 다른 개수(cardinality)" 어림잡기

사이트의 순 방문자 수, 검색어의 고유 사용자 수처럼 "중복을 뺀 개수"를 세려면 보통 본 값을 전부 Set에 담아야 한다. 1억 명이면 메모리도 1억 개. HyperLogLog는 값을 하나도 저장하지 않고, 해시값 앞에 0이 몇 개 연속으로 나왔는지만 기록해서 몇 KB로 수십억 개의 서로 다른 개수를 ±2% 오차로 추정한다.

핵심 직관 — "앞면이 연속으로 몇 번?"

동전을 계속 던지다 보면, 시도를 많이 할수록 "앞면 연속" 최고 기록도 길어진다. 누가 "앞면 10번 연속 봤다"고 하면, 대략 2¹⁰ ≈ 1024번은 던졌겠구나 짐작할 수 있다. HyperLogLog는 이걸 뒤집어서 쓴다:

각 아이템을 해시하면 예측 불가능한 0/1 비트열이 된다 (동전 던지기와 같음).
비트열 맨 앞의 0 개수 + 1 = 그 아이템의 순위(rank). (0이 3개면 rank 4)
서로 다른 아이템이 n개 들어오면, 그중 최고 rank는 대략 log₂(n).
같은 아이템은 해시가 같아 rank도 같음 → 중복은 최고 기록을 못 바꾼다. 그래서 "서로 다른 개수"만 반영됨.

최고 rank가 R이면 서로 다른 개수 n ≈ 2^R. 단, 딱 한 번의 운(레지스터 1개)으로 추정하면 편차가 크다 → 아래처럼 여러 통(bucket)으로 쪼개 평균 낸다.

직접 해보기 — 값을 흘려보내고 추정치를 확인

마지막으로 넣은 값의 32비트 해시 — 보라 4비트 = 몇 번 통에 넣을지, 나머지 28비트에서 앞쪽 0을 세어 rank 계산:

—

값을 넣으면 해시와 rank가 여기에 표시됩니다.

m = 16개 레지스터 (각 통이 지금까지 본 최고 rank 저장):

실제 서로 다른 개수

HyperLogLog 추정치

오차

—

사용 메모리 (레지스터 16 × 1바이트)

16 B

"중복 재입력"을 아무리 눌러도 추정치와 레지스터가 거의 그대로인 걸 확인해 보자 — 이미 본 값은 같은 통의 같은 rank라 최고 기록을 못 넘긴다. 반대로 고유값 +100을 계속 누르면 추정치가 실제 개수를 따라 커진다.

추정 공식 — 조화 평균으로 편차 줄이기

왜 조화 평균?

어쩌다 한 통이 아주 큰 rank를 찍으면 산술 평균은 크게 튄다.
조화 평균은 큰 값의 영향을 눌러줘서 이런 "행운의 튐"에 강하다.
통이 많을수록(m↑) 오차 ≈ 1.04 / √m 로 작아진다.

전체 식

E = α_m · m² / Σ_j 2^−M[j]

M[j] = j번 통의 최고 rank, α₁₆ ≈ 0.673 (편향 보정 상수). 개수가 아주 작을 때는 선형 계수(linear counting)로, 아주 클 때는 32비트 해시 충돌 보정으로 갈아탄다.

정밀도 vs 메모리 — 통 개수(p비트)를 조절해 보자

통 개수 지수 p (m = 2^p) 14

레지스터 개수 m

—

표준 오차 ≈ 1.04 / √m

—

메모리 (레지스터당 6비트)

—

Redis의 HyperLogLog는 p=14 → m=16,384개, 약 12KB 고정으로 표준 오차 0.81%. 값이 1개든 20억 개든 메모리는 12KB 그대로다.

정확한 Set과 비교

항목	HashSet (정확)	HyperLogLog
메모리	고유값 수에 비례 (수십 byte × n)	고정 (예: 12KB)
결과	정확한 개수	추정치 (±0.8~2%)
원소 조회 / 나열	가능	불가 (값을 안 가짐)
합집합 개수	두 Set 합쳐야 함	레지스터별 `max` → 병합 O(m)
교집합 개수	직접 계산	포함·배제로 간접 추정 (오차 큼)

병합이 강점: 요일별 HLL을 max로 합치면 곧바로 "이번 주 순 방문자"가 나온다. Set이라면 7일치를 전부 메모리에 올려 합쳐야 한다.

파이썬 미니 구현 (p=14, 32비트 해시)

import hashlib, math

class HyperLogLog:
    def __init__(self, p=14):
        self.p = p
        self.m = 1 << p
        self.reg = [0] * self.m
        self.alpha = 0.7213 / (1 + 1.079 / self.m)

    def add(self, item):
        h = int.from_bytes(hashlib.sha1(str(item).encode()).digest()[:4], "big")
        idx = h >> (32 - self.p)                # 앞 p비트 = 통 번호
        w = (h << self.p) & 0xFFFFFFFF          # 나머지 비트
        rank = 32 - self.p - w.bit_length() + 1   # 앞쪽 0 개수 + 1
        self.reg[idx] = max(self.reg[idx], rank)

    def count(self):
        z = sum(2.0 ** -r for r in self.reg)
        e = self.alpha * self.m * self.m / z
        if e <= 2.5 * self.m:                   # 작은 범위: 선형 계수
            v = self.reg.count(0)
            if v: e = self.m * math.log(self.m / v)
        return round(e)

    def merge(self, other):                     # 합집합 개수
        self.reg = [max(a, b) for a, b in zip(self.reg, other.reg)]

실제로 어디에 쓰일까

Redis — PFADD / PFCOUNT / PFMERGE 로 순 방문자(UV) 집계.
Google BigQuery / Presto — APPROX_COUNT_DISTINCT 가 내부적으로 HLL.
Redshift·Druid·Elasticsearch(cardinality agg) — 대시보드의 "고유 사용자" 카드.
네트워크 모니터링 — 스캔 탐지를 위해 출발지 IP가 접속한 고유 목적지 포트 수 추적.

친척들: 원소 존재 여부만 → 블룸 필터, 상위 빈발 원소 → Count-Min Sketch, 스트림에서 균일 표본 → 저수지 샘플링. 모두 "다 저장하지 않고 요약만 남기는" 확률적 자료구조다.