HyperLogLog

HyperLogLog (HyperLogLog) (hyperloglogs)

Redis 공식 문서의 hyperloglogs 페이지를 한국어로 풀어드릴게요. 옆에서 하나씩 설명해 드리는 느낌으로 읽으시면 돼요.

출처: Redis 공식 문서 — hyperloglogs

HyperLogLog는 집합의 cardinality(고유 원소 수)를 추정하는 확률적(probabilistic) 데이터 구조예요. 완벽한 정확도를 포기하는 대신 공간을 아주 효율적으로 쓰는 게 핵심이에요. Redis 구현은 최대 12 KB의 메모리를 쓰면서 **표준 오차율 0.81%**를 제공해요.

왜 HyperLogLog가 필요한가요?

고유한 항목을 세려면 보통 셀 항목 수에 비례하는 메모리가 필요해요. 왜냐하면 이전에 본 요소를 다시 세지 않으려고 그 요소들을 기억해 둬야 하기 때문이죠. 그런데 메모리를 정밀도와 맞바꾸는 알고리즘 계열이 있어요. 표준 오차가 있는 추정값을 돌려주는데, Redis의 HyperLogLog 구현 기준으로는 그 오차가 1% 미만이에요.

이 알고리즘의 마법은 셈한 항목 수에 비례하는 메모리가 아니라 일정한 메모리만 쓰면 된다는 거예요. 최악의 경우 12k 바이트, 그리고 HyperLogLog(앞으로 HLL이라고 부를게요)가 본 요소가 아주 적다면 훨씬 덜 쓰죠.

Redis의 HLL은 기술적으로는 별개의 데이터 구조지만 Redis string으로 인코딩돼요. 그래서 GET으로 HLL을 직렬화할 수 있고, SET으로 서버에 다시 역직렬화할 수 있죠.

HLL API 사용법

개념적으로 HLL API는 같은 작업을 Set으로 하는 것과 비슷해요. Set에서는 SADD로 본 요소를 넣고, SCARD로 집합 안의 요소 수를 확인하죠. SADD는 이미 있는 요소를 다시 추가하지 않으니 고유한 요소만 세어져요.

HLL에는 실제 요소를 담지 않기 때문에 항목을 추가하지는 않지만, API는 같아요.

  • 새 요소를 볼 때마다 PFADD로 개수에 더해요.
  • PFADD로 추가된 고유 요소들의 현재 근사치를 가져오려면 PFCOUNT를 써요. 서로 다른 두 HLL을 병합해야 한다면 PFMERGE를 써요. HLL은 고유 요소의 개수를 근사치로 제공하므로, 병합 결과는 두 HLL 전체에 걸친 고유 요소 수의 근사치가 돼요.

예시 (Python)

res1 = r.pfadd("bikes", "Hyperion", "Deimos", "Phoebe", "Quaoar")
print(res1)  # >>> 1
res2 = r.pfcount("bikes")
print(res2)  # >>> 4
res3 = r.pfadd("commuter_bikes", "Salacia", "Mimas", "Quaoar")
print(res3)  # >>> 1
res4 = r.pfmerge("all_bikes", "bikes", "commuter_bikes")
print(res4)  # >>> True
res5 = r.pfcount("all_bikes")
print(res5)  # >>> 6

각 언어별 예시는 공식 문서의 Python / Node.js / Java / Go / C# / PHP / Ruby / Rust Quick-Start를 참고하세요. PFADD로 자전거 이름들을 넣고 PFCOUNT로 개수를 세고, PFMERGE로 두 HLL을 합친 뒤 PFCOUNT로 전체 6개가 나오는 걸 확인할 수 있어요.

대표적인 사용 사례

이 데이터 구조의 전형적인 예시로는 검색 폼에서 사용자가 수행한 고유 쿼리를 매일 세거나, 웹 페이지의 고유 방문자 수를 세는 경우가 있어요. 그 외에도 비슷한 유형의 중복 없는 카운팅에 두루 쓰이죠.

사용 사례 (Use cases)

웹 페이지의 익명 고유 방문 (SaaS, 분석 도구)

이 애플리케이션은 이런 질문에 답해요.

  • 이 페이지는 오늘 고유 방문이 몇 번 있었나요?
  • 이 노래를 고유 사용자가 몇 명이나 들었나요?
  • 이 영상을 고유 사용자가 몇 명이나 봤나요?

참고: 일부 국가에서는 IP 주소나 그 밖의 개인 식별자를 저장하는 것이 법적으로 금지되어 있어서, 웹사이트의 고유 방문자 통계를 얻을 수 없는 경우가 있어요.

페이지(비디오/노래)마다 기간마다 HyperLogLog 하나를 만들고, 매 방문마다 각 IP/식별자를 그 안에 추가해요.

성능 (Performance)

PFADD로 쓰고 PFCOUNT로 읽는 것은 상수 시간·상수 공간으로 이뤄져요. HLL 병합(merging)은 O(n)인데, 여기서 n은 스케치(sketch)의 수예요.

한계 (Limits)

HyperLogLog는 최대 18,446,744,073,709,551,616 (2^64) 개의 원소를 가진 집합의 cardinality를 추정할 수 있어요.

더 배우기

더 알아보기 (Learn more)

HyperLogLog를 더 깊이 배우고 싶다면 아래 링크를 추천해요.