DDSketch로 정확한 백분위수 계산하기 (새 탭에서 열림)
Datadog은 대규모 분산 환경에서 발생하는 모니터링 데이터를 효율적으로 처리하기 위해 새로운 확률적 자료구조인 **DDSketch**를 개발했습니다. 기존의 백분위수 계산 알고리즘은 분산된 데이터를 병합할 때 정확도가 떨어지거나 시각화 시 실제와 다른 노이즈를 생성하는 한계가 있었습니다. DDSketch는 빠른 연산 속도와 완전한 병합 가능성을 제공하며, 특히 '상대 오차 보장'을 통해 고성능 모니터링 시스템에서 정밀한 지표 산출을 가능하게 합니다. ### 분산 시스템에서의 데이터 집계와 백분위수 계산의 난제 * 웹 애플리케이션의 지연 시간(Latency) 모니터링 시, 평균값은 이상 수치를 가리기 때문에 P99와 같은 백분위수(Percentile)를 확인하는 것이 사용자 경험 파악에 필수적입니다. * 정확한 백분위수를 계산하려면 모든 데이터를 저장하고 정렬해야 하지만, 초당 수백만 개의 데이터가 발생하는 분산 환경에서는 메모리와 네트워크 비용 문제로 인해 사실상 불가능합니다. * 최대값이나 합계와 달리 백분위수는 각 노드에서 계산된 중간 결과값을 단순히 합치는 것만으로는 전체 데이터의 정확한 백분위수를 구할 수 없다는 기술적 어려움이 존재합니다. ### 스케치(Sketch) 알고리즘의 역할과 병합 가능성 * 스케치는 방대한 데이터를 요약하여 압축된 형태로 저장하는 '손실 압축' 알고리즘으로, 메모리 사용량을 대폭 줄이는 대신 약간의 정확도를 희생합니다. * 모니터링 시스템에서는 여러 소스에서 생성된 요약된 데이터(스케치)를 하나로 합쳐도 정확도가 유지되는 '병합 가능성(Mergeability)'이 매우 중요한 요소입니다. * 잘 설계된 분위수 스케치(Quantile Sketch)를 사용하면 전체 데이터를 전송하지 않고도 분산된 노드들의 지표를 효율적으로 통합할 수 있습니다. ### 기존 GK 스케치의 한계와 시각화 오류 * 기존에 사용되던 GK(Greenwald-Khanna) 알고리즘은 데이터 요약 과정에서 발생하는 오차로 인해 그래프상에 실제 데이터에는 없는 가공의 스파이크(Spike)나 노이즈를 생성하는 문제가 있었습니다. * 이러한 현상은 특히 P99와 같은 높은 백분위수에서 두드러지게 나타나며, 이는 시스템의 실제 상태를 오판하게 만드는 원인이 됩니다. * 기존 알고리즘의 대부분은 '순위 오차(Rank-error)'를 제어하는 데 집중하지만, 이는 값의 범위가 넓은 모니터링 데이터에서는 충분한 정확도를 보장하지 못합니다. ### DDSketch의 혁신: 상대 오차 보장 * DDSketch는 '상대 오차(Relative-error)'를 보장하도록 설계되어, 측정값이 크든 작든 설정된 오차 범위 내에서 일관된 정확도를 제공합니다. * 매우 빠른 입력 속도와 낮은 메모리 점유율을 기록하여 Datadog 에이전트와 같은 리소스 제한적인 환경에서도 원활하게 동작합니다. * 이 알고리즘은 학술적 검증(PVLDB 발표)을 마쳤으며, 실제 Datadog 서비스에서 대규모 분포 메트릭을 계산하는 핵심 기술로 활용되고 있습니다. **결론** 대규모 분산 시스템을 운영하는 엔지니어라면 데이터 집계 시 단순히 평균에 의존하기보다 DDSketch와 같은 상대 오차 보장형 스케치 알고리즘을 도입하는 것이 좋습니다. 이를 통해 리소스 비용을 최소화하면서도 사용자 경험을 결정짓는 핵심 지표인 상위 백분위수를 왜곡 없이 정확하게 모니터링할 수 있습니다.