DDSketch로 정확한 백

Datadog의 글은 대규모 분산 시스템에서 정확한 백분위수(percentile)를 효율적으로 계산하기 위해 DDSketch를 사용하는 방법을 설명합니다. 평균이나 단순한 히스토그램은 지연 시간처럼 분포가 치우친 데이터의 꼬리 구간을 제대로 표현하지 못하지만, DDSketch는 상대 오차를 일정하게 제한하면서 적은 메모리로 값을 집계합니다. 또한 분산 환경에서 여러 스케치를 병합할 수 있어 p95, p99 같은 지표를 안정적으로 계산할 수 있습니다.

백분위수 계산이 어려운 이유

• 평균은 데이터 분포의 꼬리 부분을 숨길 수 있습니다.
  • 예를 들어 대부분의 요청이 빠르더라도 일부 요청이 매우 느리면 평균만으로는 사용자 경험을 설명하기 어렵습니다.
• p95나 p99는 전체 값을 정렬해야 정확히 계산할 수 있습니다.
  • 대규모 트래픽에서는 모든 원본 값을 저장하고 정렬하는 비용이 매우 큽니다.
• 단순한 고정 폭 히스토그램은 구간 경계에 따라 정확도가 달라집니다.
  • 작은 값에서는 정밀하지만 큰 값에서는 오차가 커지거나, 반대로 큰 값에 맞추면 작은 값의 차이를 구분하지 못합니다.
• 여러 서버에서 수집한 데이터를 중앙에서 합치려면 집계 구조가 병합 가능해야 합니다.

절대 오차보다 상대 오차가 적합한 이유

• DDSketch는 “실제 값과 추정값의 차이가 일정한 절대값 이하”가 아니라 “실제 값 대비 일정 비율 이하”가 되도록 설계됩니다.
• 예를 들어 상대 오차를 1%로 설정하면:
  • 실제 값이 100인 경우 추정값은 대략 99~101 범위입니다.
  • 실제 값이 10,000인 경우에도 약 9,900~10,100 범위입니다.
• 지연 시간이나 처리량처럼 값의 규모가 크게 달라지는 데이터에서는 상대 오차 보장이 더 일관된 품질을 제공합니다.

로그 스케일 기반의 DDSketch

• DDSketch는 값을 로그 스케일의 버킷에 매핑합니다.
• 인접한 버킷의 대표값이 일정한 비율을 갖도록 만들어, 값이 커져도 상대 오차가 일정하게 유지됩니다.
• 양수 값과 음수 값은 별도의 저장소에 기록하고, 0에 가까운 값은 별도의 zero bucket으로 처리합니다.
• 각 원본 값을 저장하는 대신 다음 정보만 유지합니다.
  • 값이 속한 버킷의 인덱스
  • 해당 버킷에 포함된 값의 개수
• 조회 시에는 버킷의 대표값과 누적 개수를 이용해 원하는 순위의 값을 추정합니다.

메모리 사용량과 정확도의 균형

• 상대 오차 설정값을 작게 할수록 더 많은 버킷이 필요하고 메모리 사용량이 증가합니다.
• 반대로 허용 오차를 키우면 더 적은 메모리로 처리할 수 있지만 백분위수의 정밀도가 낮아집니다.
• DDSketch는 원본 데이터 전체가 아니라 분포를 근사하므로, 높은 트래픽에서도 메모리 사용량을 예측하기 쉽습니다.
• 매우 큰 값 범위가 입력되더라도 로그 매핑을 사용하기 때문에 선형 히스토그램보다 효율적으로 다룰 수 있습니다.

분산 환경에서의 병합

• 각 호스트나 애플리케이션 인스턴스가 독립적으로 DDSketch를 생성할 수 있습니다.
• 중앙 집계 단계에서는 각 스케치의 동일한 버킷 개수를 더해 하나의 스케치로 병합합니다.
• 이 방식은 원본 요청 데이터를 네트워크로 전송할 필요가 없어 수집 및 전송 비용을 줄입니다.
• 병합 후에도 설정한 상대 오차 보장이 유지되므로, 분산 시스템 전체의 p95·p99 지연 시간을 계산하는 데 적합합니다.

저장소 구조와 큰 데이터 범위 처리

• DDSketch의 내부 저장소는 버킷 인덱스와 카운트를 관리하는 구조로 구현됩니다.
• 일반적인 범위에서는 밀집 배열을 사용해 빠르게 접근할 수 있습니다.
• 값의 범위가 지나치게 커져 메모리 사용량이 증가할 경우에는 저장소 크기를 제한하고 오래된 범위나 덜 중요한 범위를 압축하는 collapsing store를 사용할 수 있습니다.
• 이로 인해 정확도와 메모리 상한 사이의 트레이드오프를 제어할 수 있습니다.

실무에서는 지연 시간처럼 분포의 꼬리가 중요한 지표에 DDSketch 같은 상대 오차 기반 스케치를 적용하는 것이 유용합니다. 다만 허용 오차와 메모리 제한을 서비스 특성에 맞게 설정하고, p99 등 핵심 백분위수의 정확도를 실제 원본 데이터와 비교해 검증하는 것이 좋습니다.