t-digest

t-digest (t-digest)

이번엔 대용량 데이터에서 백분위수(percentile)를 추정할 때 쓰는 자료구조, t-digest를 배워볼게요. 데이터가 수백만 건이라도 전부 저장하지 않고 작은 "스케치(sketch)"만으로 근사치를 얻을 수 있어요. 메모리를 아끼면서 대략적인 분포 정보를 얻고 싶을 때 딱인 도구예요.

출처: Redis 공식 문서 — t-digest

t-digest란?

t-digest는 데이터 스트림이나 큰 데이터셋에서 백분위수를 추정하기 위한 확률적(probabilistic) 데이터 구조예요. Redis Open Source의 스케치 자료구조로서, 컴팩트한 스케치를 이용해 백분위수를 계산해요.

다음 같은 질문에 답할 수 있어요.

데이터 스트림의 값 중 주어진 값보다 작은 값의 비율은 얼마인가?
데이터 스트림의 값 중 주어진 값보다 작은 값이 몇 개인가?
데이터 스트림의 값 중 p퍼센트보다 작은 값 중 가장 큰 값은 무엇인가? (즉 p-백분위수 값은?)

이런 질문에 근사치로 답하기 때문에, 정확한 순서 통계가 필요한 곳보다는 큰 흐름을 봐야 하는 곳에 어울려요.

사용 사례 (Use cases)

하드웨어/소프트웨어 모니터링 온라인 서버의 응답 지연시간(response latency)을 측정하면서 이런 질문을 하고 싶을 때 쓰여요.

온라인 게임 플레이어 경험 분석 수백만 명이 게임을 즐기는 온라인 게임 플랫폼에서, 각 플레이어에게 다음과 같은 정보를 주고 싶을 때도 유용해요.

네트워크 보안 매초 네트워크를 지나는 IP 패킷을 측정하면서 서비스 거부(DoS) 공격을 탐지하려고 이런 질문을 던질 때도 써요.

예제 (Examples)

t-digest 스케치를 만들고 데이터를 추가하는 기본 흐름을 볼게요.

스케치 만들기와 값 추가

import redis
r = redis.Redis(decode_responses=True)
res1 = r.tdigest().create("bikes:sales", 100)
print(res1)  # >>> True
res2 = r.tdigest().add("bikes:sales", [21])
print(res2)  # >>> OK

create로 스케치를 만들 때는 두 번째 인자로 압축(compression) 값(예: 100)을 지정해요. 압축 값이 클수록 정확도가 높아지지만 메모리를 더 써요.

자바(Java) 예시도 볼게요.

UnifiedJedis jedis = new UnifiedJedis("redis://127.0.0.1:6379");
String res1 = jedis.tdigestCreate("bikes:sales", 100);
System.out.println(res1);  // >>> True
String res2 = jedis.tdigestAdd("bikes:sales", 21);

값으로 분수/순위 추정하기 (Estimating fractions or ranks by values)

추가한 값들로 분수(fraction)나 순위(rank)를 추정할 수 있고, 순위/분수로 값을 추정할 수도 있어요. 스케치의 정보를 조회하는 명령들도 있어요.