t-digest

개요

t-digest는 실수 값으로 이루어진 데이터에서 분위수(percentile), 백분위, 중위수(median), Value-at-Risk 등을 빠르고 정확하게 추정하기 위한 자료구조입니다. Ted Dunning이 고안한 이 구조는 대규모 데이터 스트림 환경에서도 고정된 메모리로 높은 정밀도를 유지하며, 특히 tail(꼬리) 영역에서의 정확도에 강점을 갖습니다.

---

1. 개념 및 정의

항목	설명
정의	분위수 계산을 위한 확률 밀도 추정용 데이터 요약 구조
목적	중위수, 분위수 계산을 메모리 효율적으로 수행
필요성	전체 데이터를 저장하지 않고 정확한 분위수 추정 필요

t-digest는 평균값이 아닌 분포 형태를 요약해 통계적으로 의미 있는 추정을 가능하게 함

---

2. 특징

특징	설명	비교
메모리 효율성	수백만 건도 수백 KB 이내 메모리 사용	히스토그램보다 메모리 적음
정밀한 tail 추정	극단값(1%, 99%)에서 높은 정확도	Q-digest보다 유리함
병합 가능성	여러 t-digest를 쉽게 병합	분산 환경에서 통계 집계 가능

tail 추정 정확도를 높이기 위한 가중 중심(cluster centroid) 전략 사용

---

3. 구성 요소

구성 요소	설명	예시
Centroid	데이터 군집의 평균과 가중치	(mean=43.2, count=12)
Compression Factor	요약 압축률을 조정하는 파라미터	값이 클수록 정확, 느림
Cumulative Distribution Function (CDF)	분위수 계산에 사용	quantile(x) 계산 가능

Centroid의 정렬된 구조 덕분에 분위수 계산이 logN 수준으로 빠름

---

4. 기술 요소

기술	설명	사용 예
AVL 트리 / 리스트	Centroid 정렬 관리	빠른 삽입/검색을 위한 자료구조
Merge 알고리즘	여러 t-digest 병합	Spark, Flink 등에서 분산 계산
Quantile 추정	분위수 위치 계산	P99 응답 시간, SLA 모니터링 등

t-digest는 단순한 평균이나 분산보다 통계적으로 더 풍부한 정보를 제공

---

5. 장점 및 이점

장점	설명	효과
실시간 분위수 계산	전체 데이터 불필요	스트리밍 처리에 적합
높은 정밀도	특히 상위/하위 분위수에서 우수	SLA 모니터링 지표 적합
분산 시스템 호환	t-digest 객체 병합 가능	데이터 레이크, 로그 분석 적합

A/B 테스트, 사용자 행동 분석, 금융 리스크 모델 등에서 유용함

---

6. 주요 활용 사례 및 고려사항

사례	설명	참고사항
API 응답 시간 분석	P50, P95, P99 응답 시간 측정	Prometheus + t-digest 사용 가능
로그 기반 사용자 분석	이상값 탐지 및 사용자 분포 분석	Flink, Spark와 통합 활용
금융 모델링	Value-at-Risk, Tail Risk 분석	백테스트와 조합하여 사용

압축률(compression) 조절에 따라 정밀도와 성능 균형 필요

---

7. 결론

t-digest는 정확한 분위수 계산이 중요한 다양한 분석 환경에서 필수적인 데이터 요약 도구로 자리잡고 있습니다. 특히 분산 처리 시스템에서의 효율성과 극단값에 대한 정밀도는 성능과 정확도 모두를 만족시키는 뛰어난 특성을 갖추고 있습니다. 실시간 대시보드, SLA 모니터링, 대규모 로그 분석 등에 광범위하게 활용됩니다.