Data Sketches
“The question isn’t ‘should we use sketches?’ — it’s ‘where is exact precision actually required, and where are we just paying for it out of habit?‘”
핵심 개념
Data Sketch는 대규모 데이터 스트림에서 단일 패스로 근사 통계를 추출하는 확률적 자료구조다. 정확도를 약간 희생하는 대신, 메모리·시간을 수 자릿수 절감하며 수학적으로 보장된 오차 범위를 제공한다.
동작 원리
- 해시 → 균일 분포: 입력값을 0~1 사이 균일 난수로 변환
- 소규모 서브셋 유지: 가장 작은 k개 해시값만 보관 (고정 메모리)
- 추정: k번째 최소 해시값 v로부터 고유 항목 수 ≈ k / v 추정
핵심 속성은 병합 가능성(mergeability): 서로 다른 파티션에서 독립적으로 구축한 스케치를 합집합·교집합·차집합으로 결합해도 오차 범위가 유지된다. 이 덕분에 분산 시스템에서 shuffle 없이 COUNT DISTINCT를 수행할 수 있다.
스케치 패밀리
Cardinality (COUNT DISTINCT)
| 스케치 | 특징 | 사용 시점 |
|---|---|---|
| Theta | 집합 연산(∩, ∪, −) 지원, 동시 업데이트 | 기본 선택지, 교집합 필요 시 |
| HyperLogLog | Theta 대비 2-16x 작음, 교집합 미지원 | 단순 고유 수 카운트 |
| CPC | 바이트당 최고 정확도 | 대량 스케치 저장 시 |
| Tuple | Theta + 임의 payload (예: 매출 합산) | 고유 수 + 추가 메트릭 |
Quantiles (분위수)
| 스케치 | 특징 |
|---|---|
| KLL | 크기 대비 최적 정확도, 대부분의 기본 선택지 |
| REQ | 꼬리 분포(p99.999)에 특화 |
| Classic Quantiles | k=256에서 40억 항목 → ~51KB |
Frequent Items (Heavy Hitters)
- 스트림에서 비율 이상으로 자주 등장하는 항목 탐지
- Frequent Distinct Tuples: 키별 고유 카디널리티 탐지 (예: IP별 고유 사용자 수)
Sampling
- Reservoir Sampling: 분산 환경에서 병합 가능한 대표 샘플 추출
실무 활용 패턴
- 사전 계산 하이퍼큐브: 인제스천 시 스케치를 차원별로 사전 계산 → 쿼리 시 스케치 병합만으로 응답
- Spark
approx_count_distinct(): 내부적으로 HyperLogLog 사용 - Druid/Pinot: Apache DataSketches 네이티브 통합, SQL에서 직접 스케치 쿼리 가능
트레이드오프와 한계
- 되돌릴 수 없음: 스케치 생성 후 더 세밀한 차원 분해 불가 → 차원 스키마를 먼저 설계해야 함
- 집합 연산 누적 오차: 교집합을 10개 이상 스택하면 오차가 크게 누적
- 저장소 곱셈 폭증: 1000페이지 × 100국가 × 365일 × 32KB = 1TB+
- 재무/규제 부적합: 감사인은 근사치를 수용하지 않음
- 소규모 데이터에 불필요: 100만 이벤트 미만이면 정확한 계산이 더 합리적
연관 개념
- Query Optimization — 스케치는 대규모 집계 쿼리 최적화의 핵심 도구
- Real-Time Stream Processing — 스트리밍 알고리즘으로 단일 패스 처리
- Data Engineering FinOps — 정확한 COUNT DISTINCT 대비 컴퓨트 비용 대폭 절감
Source: Data Sketches Guide