✍️ 필사 모드: 확률적 자료구조 완전 가이드 2025: Bloom Filter, HyperLogLog, Count-Min Sketch, 실전 활용

TL;DR

• 확률적 자료구조의 본질: 100% 정확도를 포기하고 메모리/속도를 극단적으로 절약
• Bloom Filter: "이 원소가 집합에 있을 수 있다" — false positive O, false negative X. RocksDB, Cassandra, BigTable의 핵심
• HyperLogLog: 12KB로 수십억 원소의 고유 카운트. Redis PFADD/PFCOUNT, BigQuery, Druid 사용
• Count-Min Sketch: 스트림에서 원소 빈도 추정. 핫 키 탐지, DDoS 감지
• 트레이드오프: 정확도 vs 메모리 vs 속도 — 정확한 답이 필요 없을 때 폭발적 효율

1. 확률적 자료구조란?

1.1 핵심 아이디어

"100% 정확한 답이 필요 없다면, 메모리와 속도를 극단적으로 절약할 수 있다."

전통적 자료구조:

• HashMap으로 100만 원소 저장 → 약 50 MB
• "이 원소가 있는가?" → 정확한 답

확률적 자료구조:

• Bloom Filter로 100만 원소 저장 → 약 1 MB (50배 절약!)
• "이 원소가 있는가?" → "있을 수도 있다" 또는 "확실히 없다"

트레이드오프: 메모리 50배 절약 + 약간의 false positive (1%).

1.2 왜 필요한가?

대규모 시스템에서:

• 메모리는 비싸다 — RAM은 디스크의 100배+
• L1/L2 캐시에 들어가야 빠름 → 작을수록 좋음
• 수십억 원소 — HashMap이 불가능
• 분산 시스템 — 작은 데이터가 네트워크 효율적

1.3 정확도가 필요 없는 경우

2. Bloom Filter — 가장 유명한 확률적 자료구조

2.1 원리

비트 배열 + 여러 해시 함수.

삽입:

1. 원소를 K개의 해시 함수에 통과 → K개의 인덱스
2. 각 인덱스의 비트를 1로 설정

조회:

1. 같은 K개 해시 함수
2. 모든 인덱스의 비트가 1이면 → "있을 수도"
3. 하나라도 0이면 → "확실히 없음"

2.2 시각화

비트 배열 (8비트):  [0, 0, 0, 0, 0, 0, 0, 0]

"apple" 삽입 (해시 → [1, 4]):
                  [0, 1, 0, 0, 1, 0, 0, 0]

"banana" 삽입 (해시 → [3, 6]):
                  [0, 1, 0, 1, 1, 0, 1, 0]

"apple" 조회 (해시 → [1, 4]): 둘 다 1 → "있을 수도" ✅
"grape" 조회 (해시 → [2, 5]): 0이 있음 → "확실히 없음" ❌
"cherry" 조회 (해시 → [1, 6]): 우연히 둘 다 1 → "있을 수도" ⚠️ (false positive)

2.3 false positive율 계산

수식:

P(fp) = (1 - e^(-k*n/m))^k

• n: 원소 수
• m: 비트 수
• k: 해시 함수 수

최적 k:

k = (m/n) * ln(2)

1% false positive가 목표라면:

m/n ≈ 9.6 비트
k ≈ 7

100만 원소 = 1.2 MB + 7 해시 함수 = HashMap의 50배 작음.

2.4 Python 구현

import hashlib
import math

class BloomFilter:
    def __init__(self, n, fp_rate):
        self.size = -int(n * math.log(fp_rate) / (math.log(2) ** 2))
        self.hash_count = int(self.size / n * math.log(2))
        self.bits = [0] * self.size

    def _hashes(self, item):
        for i in range(self.hash_count):
            h = hashlib.md5(f"{item}{i}".encode()).hexdigest()
            yield int(h, 16) % self.size

    def add(self, item):
        for h in self._hashes(item):
            self.bits[h] = 1

    def contains(self, item):
        return all(self.bits[h] for h in self._hashes(item))

# 사용
bf = BloomFilter(n=1000000, fp_rate=0.01)
bf.add("alice@example.com")
print(bf.contains("alice@example.com"))  # True
print(bf.contains("bob@example.com"))    # 거의 항상 False

2.5 Bloom Filter의 한계

• 삭제 불가능 — 비트를 0으로 하면 다른 원소에 영향
• resize 어려움 — 새 필터 만들고 모든 원소 재삽입 필요
• count 불가능 — 몇 개 들어있는지 모름

해결책: Counting Bloom Filter, Cuckoo Filter (아래 참조).

2.6 Bloom Filter의 실전 활용

RocksDB / Cassandra / BigTable

LSM 트리 기반 DB에서, SSTable마다 Bloom Filter:

쿼리: "key123"

SSTable 1의 Bloom Filter: "확실히 없음" → 디스크 안 읽음 ✅
SSTable 2의 Bloom Filter: "확실히 없음" → 디스크 안 읽음 ✅
SSTable 3의 Bloom Filter: "있을 수도"  → 디스크 읽음 (실제 검색)

효과: 디스크 I/O 99% 감소. 전체 SSTable을 안 읽음.

CDN 캐시

요청: GET /image/123.jpg

Bloom Filter: "캐시에 없음" → 즉시 origin 요청 (캐시 lookup 생략)
            "있을 수도"   → 캐시 lookup

효과: 캐시 미스 시 시간 절약.

비밀번호 누출 검사

HaveIBeenPwned의 비밀번호 1억+ 데이터베이스 → 클라이언트가 직접 확인 가능 (Bloom Filter 다운로드).

Chrome 악성 URL 검사

Google이 알려진 악성 URL 데이터베이스 → Bloom Filter로 클라이언트에 전송 → 브라우저가 즉시 확인.

3. Counting Bloom Filter

3.1 문제 해결

기본 Bloom Filter는 삭제 불가능. Counting Bloom Filter는 비트 대신 카운터:

배열: [0, 0, 0, 0, 0, 0, 0, 0]  (각 셀이 4비트 카운터)

"apple" 삽입 ([1, 4]):
        [0, 1, 0, 0, 1, 0, 0, 0]

"apple" 또 삽입:
        [0, 2, 0, 0, 2, 0, 0, 0]

"apple" 삭제:
        [0, 1, 0, 0, 1, 0, 0, 0]

3.2 단점

• 메모리 4배 — 1비트 → 4비트 (오버플로 방지 위해)
• 여전히 false positive 있음

3.3 Cuckoo Filter (대안)

Cuckoo Filter는 Bloom Filter보다 우수한 대안:

• 삭제 가능
• false positive율 더 낮음
• 메모리 효율 비슷
• "Cuckoo hashing" 기반

# pycuckoofilter 예시
from cuckoofilter import CuckooFilter

cf = CuckooFilter(capacity=1000000, error_rate=0.01)
cf.insert("alice")
print(cf.contains("alice"))  # True
cf.delete("alice")  # 가능!

언제 Cuckoo > Bloom: 삭제가 필요할 때, 더 낮은 false positive 필요할 때.

4. HyperLogLog — 카디널리티 추정

4.1 문제

"오늘 우리 사이트에 몇 명의 고유 방문자가 왔나?"

전통적 방법: HashSet에 모든 방문자 ID 저장 → 1000만 방문자 = 800 MB.

HyperLogLog: 12 KB로 수십억 원소까지 추정. 1% 오차.

4.2 기본 아이디어

원소를 해시 → 이진수의 선행 0의 개수 추적.

"alice" → hash → 00000010110...  (5개의 선행 0)
"bob"   → hash → 00100110...     (2개의 선행 0)
"carol" → hash → 0001110...      (3개의 선행 0)

관찰: 무작위 해시에서 K개의 선행 0이 나올 확률 = 1/2^K.

→ "최대 5개의 선행 0이 나왔다" → 약 2^5 = 32개의 고유 원소 추정.

현실: 단일 측정은 부정확. 여러 버킷에 나누어 평균 → 정확도 향상. 이게 HyperLogLog.

4.3 정확도

핵심: 메모리는 원소 수에 무관! 1억 원소나 100만 원소나 같은 메모리.

4.4 Redis HyperLogLog

PFADD visitors:2025-04-15 "user1" "user2" "user3"
PFADD visitors:2025-04-15 "user1"  # 중복 무시
PFCOUNT visitors:2025-04-15  # 약 3 (2일 수도, 3일 수도)

# 여러 HLL 병합
PFMERGE visitors:week visitors:2025-04-14 visitors:2025-04-15

4.5 HyperLogLog의 실전 활용

일일 활성 사용자 (DAU)

import redis

r = redis.Redis()

def track_user(user_id):
    today = datetime.now().strftime("%Y-%m-%d")
    r.pfadd(f"dau:{today}", user_id)

def get_dau(date):
    return r.pfcount(f"dau:{date}")

수억 사용자도 12 KB로 처리 가능.

고유 IP 카운트 (DDoS 분석)

PFADD unique_ips:2025-04-15 "1.2.3.4" "5.6.7.8"
PFCOUNT unique_ips:2025-04-15

Big Data — BigQuery, Druid

SELECT APPROX_COUNT_DISTINCT(user_id) FROM events;

내부적으로 HyperLogLog 사용. 정확한 COUNT(DISTINCT) 대비 100배+ 빠름.

5. Count-Min Sketch — 빈도 추정

5.1 문제

스트림에서 "각 원소가 몇 번 나타났나?"

전통적: HashMap → 메모리 폭증.

Count-Min Sketch: 작은 메모리로 빈도 추정.

5.2 원리

2D 배열 (d × w) + d개의 해시 함수.

삽입:

• 각 해시 함수로 인덱스 계산
• 해당 카운터 증가

조회:

• 같은 해시 함수
• 모든 카운터 중 최솟값 반환 (그래서 "Count-Min")

5.3 시각화

배열 (3 x 5):
[0, 0, 0, 0, 0]  ← hash1
[0, 0, 0, 0, 0]  ← hash2
[0, 0, 0, 0, 0]  ← hash3

"apple" 삽입 5번:
hash1("apple") = 1 → 카운터 [0, 5, 0, 0, 0]
hash2("apple") = 3 → 카운터 [0, 0, 0, 5, 0]
hash3("apple") = 0 → 카운터 [5, 0, 0, 0, 0]

"banana" 삽입 2번:
hash1("banana") = 4 → [0, 5, 0, 0, 2]
hash2("banana") = 1 → [0, 2, 0, 5, 0]
hash3("banana") = 2 → [5, 0, 2, 0, 0]

"apple" 조회: min(5, 5, 5) = 5 ✅
"banana" 조회: min(2, 2, 2) = 2 ✅

collision 발생 시: 다른 원소와 충돌하면 카운터가 부풀려질 수 있지만, 최솟값을 취하므로 항상 진짜 카운트보다 ≥ (overestimate).

5.4 정확도

오차 ε, 신뢰도 1-δ
필요 크기:
  w = ⌈e/ε⌉
  d = ⌈ln(1/δ)⌉

예: 1% 오차, 99% 신뢰도 → w=272, d=5 → 1360 카운터 = 5 KB. 수십억 원소 처리 가능.

5.5 실전 활용

핫 키 탐지 (Heavy Hitters)

# 가장 자주 본 키 찾기
sketch = CountMinSketch(width=272, depth=5)

for query in stream:
    sketch.add(query)

# Top-K 찾기 (separate min-heap 사용)

Memcached의 LRU 대안

tinylfu 캐시는 Count-Min Sketch로 빈도 추적 → 자주 쓰이는 키만 캐시에 유지.

DDoS 감지

각 IP의 요청 수를 추정 → 임계값 초과 시 차단.

Apache Spark, Flink

대규모 스트림 처리에서 빈도 분석.

6. MinHash — Jaccard 유사도

6.1 문제

"두 집합이 얼마나 비슷한가?" (Jaccard 유사도)

J(A, B) = |A ∩ B| / |A ∪ B|

전통적 방법: 모든 원소 비교 → O(|A| × |B|).

6.2 MinHash 원리

각 집합의 "최소 해시 값"이 같을 확률 = Jaccard 유사도.

def minhash(set_, num_hashes=128):
    return [min(hash(item, seed=i) for item in set_) for i in range(num_hashes)]

# 두 집합의 MinHash 비교
mh1 = minhash(set1)
mh2 = minhash(set2)

similarity = sum(a == b for a, b in zip(mh1, mh2)) / len(mh1)
# similarity ≈ Jaccard(set1, set2)

6.3 활용

중복 문서 탐지

수십억 웹 페이지에서 거의 같은 페이지 찾기. Google이 사용.

표절 탐지

논문, 코드 비교.

추천 시스템

"비슷한 사용자" 찾기.

클러스터링

LSH (Locality Sensitive Hashing)와 결합하여 비슷한 항목 그룹화.

7. Skip List — 확률적 균형 트리

7.1 정렬된 자료구조

균형 이진 트리(AVL, Red-Black) 대신 확률적 접근.

7.2 원리

다층 연결 리스트. 상위 레벨은 sparse, 하위 레벨은 dense.

Level 3:  1 ───────────────→ 9
Level 2:  1 ────→ 4 ────→ 7 ─→ 9
Level 1:  1 → 3 → 4 → 5 → 7 → 8 → 9

검색: 상위에서 시작, 너무 크면 한 레벨 내려감.

삽입 시 레벨: 동전 던지기로 결정. 50% 확률로 다음 레벨.

7.3 성능

장점: 균형 트리보다 구현 단순, lock-free 동시성 쉬움.

7.4 활용

• Redis Sorted Set: ZADD/ZRANGE의 내부 구조
• LevelDB/RocksDB의 memtable
• Java ConcurrentSkipListMap

8. T-Digest — 분위수 추정

8.1 문제

대규모 스트림에서 p99 latency 같은 분위수를 어떻게 계산하나?

전통적: 모든 값 저장 후 정렬 → 메모리 폭증.

T-Digest: 분포의 "스케치"를 작은 메모리로 유지.

8.2 원리

값을 buckets로 그룹화. 분포의 끝(p99, p99.9)에 더 많은 buckets, 중간(p50)에 적게.

근거: 우리는 보통 **꼬리(tail latency)**에 관심. 중간값은 대략적이어도 OK.

8.3 사용

from tdigest import TDigest

t = TDigest()
for value in stream:
    t.update(value)

p50 = t.percentile(50)
p95 = t.percentile(95)
p99 = t.percentile(99)
p999 = t.percentile(99.9)

8.4 활용

• 모니터링: Prometheus, Datadog, New Relic
• 데이터베이스: Druid, Apache Pinot
• 스트림 처리: Apache Beam, Flink

9. 트레이드오프 비교

9.1 모든 자료구조 비교

9.2 메모리 비교 (1억 고유 사용자)

HyperLogLog가 30만 배 작습니다.

10. 실전 — Kafka의 Heavy Hitter 탐지

10.1 시나리오

Kafka 토픽에 초당 100만 메시지. "어떤 user_id가 가장 활발한가?" (스팸 탐지)

10.2 구현

from countminsketch import CountMinSketch
import heapq

# Count-Min Sketch + Top-K 힙
sketch = CountMinSketch(width=10000, depth=5)
top_k = []  # min-heap of (count, user_id)
TOP_K_SIZE = 100

def process_message(user_id):
    sketch.add(user_id)
    estimated_count = sketch.estimate(user_id)
    
    if len(top_k) < TOP_K_SIZE:
        heapq.heappush(top_k, (estimated_count, user_id))
    elif estimated_count > top_k[0][0]:
        heapq.heapreplace(top_k, (estimated_count, user_id))

# 메모리: ~200 KB로 1억 사용자 처리 가능

10.3 결과

전통적 HashMap = 수 GB → CMS = 200 KB (10,000배 절약).

약간의 부정확성을 받아들이면 메모리 효율이 폭발적입니다.

퀴즈

참고 자료

• Bloom Filter 원논문 — Burton Bloom (1970)
• HyperLogLog 원논문 — Flajolet et al.
• Count-Min Sketch 원논문 — Cormode & Muthukrishnan
• Cuckoo Filter — Fan et al.
• Probabilistic Data Structures and Algorithms — Andrii Gakhov 책
• Redis HyperLogLog
• RocksDB Bloom Filter
• Apache DataSketches — 고품질 구현
• stream-lib — Java 라이브러리
• t-digest — Ted Dunning 구현
• pdsa.gakhov.com — 시각화 + 시뮬레이션