HyperLogLog — 대규모 카디널리티 추정의 원리

방법 1: Set 사용
  1억 개의 고유 ID를 Set에 저장
  → 메모리: ~6.4GB (ID당 ~64바이트)

방법 2: 비트맵 사용 (정수 ID일 때)
  → 메모리: ~12.5MB (1억 비트)

방법 3: HyperLogLog
  → 메모리: 12KB (고정)
  → 오차: ±0.81%

# 원소 추가
PFADD visitors "user:1" "user:2" "user:3"
PFADD visitors "user:1" "user:4"    # user:1은 이미 있으므로 카디널리티 변화 없음

# 카디널리티 추정
PFCOUNT visitors
# (integer) 4

# 여러 HLL의 합집합 카디널리티
PFADD visitors:page1 "user:1" "user:2" "user:3"
PFADD visitors:page2 "user:2" "user:4" "user:5"
PFCOUNT visitors:page1 visitors:page2
# (integer) 5  (합집합의 카디널리티)

# HLL 합치기 (결과를 새 키에 저장)
PFMERGE visitors:total visitors:page1 visitors:page2
PFCOUNT visitors:total
# (integer) 5

1회 시행: 앞 → 최대 연속 1회 → 약 2^1 = 2번 정도 던진 것으로 추정
4회 시행: 앞앞 → 최대 연속 2회 → 약 2^2 = 4번 정도 던진 것으로 추정
8회 시행: 앞앞앞 → 최대 연속 3회 → 약 2^3 = 8번 정도 던진 것으로 추정

입력: "user:1" → hash → 0001011010... → leading zeros = 3
입력: "user:2" → hash → 0000001101... → leading zeros = 6
입력: "user:3" → hash → 0100110100... → leading zeros = 1
입력: "user:4" → hash → 0000000010... → leading zeros = 8

최대 leading zeros = 8 → 추정 카디널리티 ≈ 2^8 = 256

해시값 64비트:
[14비트: 레지스터 인덱스][50비트: leading zeros 관찰 대상]

레지스터 수: 2^14 = 16384개
각 레지스터: leading zeros의 최댓값을 저장 (6비트 = 최대 63)
총 메모리: 16384 × 6비트 = 12,288바이트 ≈ 12KB

원소: "user:1"
hash = 00101100001110...
       ^^^^^^
       레지스터 인덱스 = 0b001011 = 11 (실제로는 14비트)
              ^^^^^^^^^
              나머지에서 leading zeros 관찰

register[11] = max(register[11], leading_zeros)

E = α_m × m² × (Σ 2^(-register[j]))^(-1)

α_m: 보정 상수 (m=16384일 때 약 0.7213)
m: 레지스터 수 (16384)
register[j]: j번째 레지스터의 값

표준 오차 = 1.04 / sqrt(m)
m = 16384일 때: 1.04 / sqrt(16384) = 1.04 / 128 ≈ 0.0081 = 0.81%

# 원소가 적으면 sparse 표현 사용
PFADD test "a" "b" "c"
OBJECT ENCODING test    # 실제로는 string 타입

# hll-sparse-max-bytes (기본: 3000바이트)
# sparse 표현이 이 크기를 초과하면 dense로 전환
CONFIG GET hll-sparse-max-bytes

┌──────────────┬──────────────────────────┐
│ 헤더 (16B)   │ 레지스터 데이터 (12KB)    │
└──────────────┴──────────────────────────┘

import redis
from datetime import date

r = redis.Redis()

def track_user(user_id):
    """사용자 활동 기록"""
    today = date.today().isoformat()
    r.pfadd(f"dau:{today}", user_id)

def get_dau(target_date=None):
    """일일 활성 사용자 수"""
    if target_date is None:
        target_date = date.today().isoformat()
    return r.pfcount(f"dau:{target_date}")

def get_wau():
    """주간 활성 사용자 수 (7일 합집합)"""
    keys = [f"dau:{date.today() - timedelta(days=i)}"
            for i in range(7)]
    # PFCOUNT에 여러 키를 전달하면 합집합 카디널리티 반환
    return r.pfcount(*keys)

def get_mau():
    """월간 활성 사용자 수"""
    # 30일치를 합쳐서 계산
    keys = [f"dau:{date.today() - timedelta(days=i)}"
            for i in range(30)]
    # 성능을 위해 PFMERGE 후 PFCOUNT
    r.pfmerge("mau:current", *keys)
    return r.pfcount("mau:current")

def track_page_view(page_id, user_id):
    """페이지별 고유 조회자 추적"""
    r.pfadd(f"pageview:{page_id}", user_id)

def get_unique_viewers(page_id):
    return r.pfcount(f"pageview:{page_id}")

def get_site_unique_visitors():
    """전체 사이트 고유 방문자"""
    keys = r.keys("pageview:*")  # SCAN 사용 권장
    if keys:
        return r.pfcount(*keys)
    return 0

def track_search(query):
    today = date.today().isoformat()
    r.pfadd(f"search:unique:{today}", query.lower().strip())

def get_unique_searches(target_date):
    return r.pfcount(f"search:unique:{target_date}")

PFADD hll "new_element"
# (integer) 1  → 내부 레지스터가 변경됨 (새 원소일 가능성 높음)
# (integer) 0  → 레지스터 변경 없음 (이미 본 원소이거나 영향 없음)

# 주의: 반환값 1이 "새 원소가 추가됨"을 의미하지는 않음
# 레지스터가 변경되었다는 것이며, 확률적 판단임

실제 카디널리티가 매우 작을 때 (< 100) 오차가 상대적으로 클 수 있음
예: 실제 10개 → HLL 추정 9~11개 (10% 오차)
    실제 1,000,000개 → HLL 추정 991,900~1,008,100 (0.81% 오차)

→ 소규모에서는 Set, 대규모에서는 HLL이 적합

# PFMERGE는 O(N) — N은 합치는 HLL의 수
# 레지스터별로 max를 취하므로 12KB씩 읽어야 함
PFMERGE result hll1 hll2 hll3 ... hll365

# 365일치를 합치면 365 × 12KB ≈ 4.3MB 데이터 처리
# 주기적으로 미리 합쳐두는 것이 좋음