95%, 99% (통계) 빠르게 계산하기

IMQA는 자체 모니터링 시스템을 구축하여 모바일 어플리케이션 사용자의 사용 환경, 자원 리소스 사용 패턴, 사용 시 발생되는 문제점에 대한 판단과 분석은 물론 의사결정을 위한 통계 및 보고서까지 지원해 드립니다.‌

IMQA 통계가 궁금하다면? 클릭!

다양하게 제공되는 지원 서비스 중 통계에 대해서 이야기해볼까 합니다.

지금보다 더 좋은 성능과 정확한 통계를 위한 방법이 있을까?라는 의문에서 이번 편이 나오게 되었던 것 같아요.‌
‌항상 IMQA 서비스 고도화를 위해 고민하는 개발팀!‌

먼저 백분위수(Percentile)를 생각해 보았어요.

백분위수는 크기가 있는 값들로 이루어진 자료를 순서대로 나열했을 때 백분율로 나타낸 특정 위치의 값인데요. (From Wikipedia)

자주 쓰이는 백분위 수에는 무엇이 있을까요?‌
‌1. P50(중앙값) : 데이터의 정 중앙에 있는 값 (평균값과는 달라요!)‌
‌2. P95 : 상위 또는 하위 5% 위치한 값‌
‌3. P99 : 상위 또는 하위 1%에 위치한 값

들어보셨나요? :)‌
‌바로 예시를 들어 확인해보아요. 아래 자료들에서 각 백분위 수의 값을 찾아볼까요?‌

P50 : 1233 | P95 : 999997 | P99 : 999997

어떻게 구했을까요?‌
‌1. 우선 모든 데이터들을 받아요.‌
‌2. 그리고 이 데이터들을 정렬하죠!‌
‌3. "배열의 크기 * 백분위수(50||95||99) * 0.01" 로 나타낸 인덱스를 가리킵니다.

참 쉽죠?‌
‌좋아요... 하지만 문제점이 보이시나요?

모든 데이터를 들고 있어야 해요! 위 예시에서 보이는 데이터양으로는 괜찮죠.‌
‌‌
‌하지만 데이터의 양이 많아진다면요?‌
‌많은 양의 데이터를 쌓고, 정렬하면 어떤 일이 일어나게 될까요?

알고리즘에 따라 달라지겠지만 시간 복잡도가 올라가는 것은 물론이며 공간 복잡도(메모리 사용량)도 엄청 늘어나게 됩니다!

이건 아니야..😂
‌좀 더 좋은 방법이 없을까 고민하는 IMQA 개발팀!

자, 이 자료구조를 소개하기 위해 구구절절 이야기가 길어졌네요.‌

‌DD-Sketch

DD-Sketch는 VLDB19(데이터베이스 학회)에서 소개된 자료구조라고 해요.
"모든 값을 가지고 있지 않아도" 위에서 설명한 P95, P50 등과 같은 백분위수를 계산할 수 있죠!

위 백분위 수를 알기 위해서는 '모든 값을 들고 있어야 한다'라고 말씀드렸는데,‌
‌이는 곧 데이터양과 비례한 메모리 자원이 필요하다는 것을 일컫기도 해요.

하지만 DD-Sketch는 값을 가지고 있지 않아도 백분위수를 구할 수 있기 때문에 저장 공간(메모리)에 대한 활용도가 높은 거죠.‌ 처리시간도 당연히 빨라지겠고요.

DD-Sketch는 모든 값을 가지고 있지 않으면서 통계 값으로 쓸 수 있는 백분위수를 어떻게 구하는 걸까요?

핵심은 버킷! 일종의 바구니라고 생각하시면 돼요.‌
‌각 바구니는 값의 범위를 가지고 있어요. 해당하는 범위에 포함하는 데이터의 수를 누적합니다.

이번에도 예를 들어보아요.‌
‌들어온 데이터(숫자)가 다음과 같을 때,‌
‌[5633, 4522, 4999, 1328, 3322, 6678, 9999]

각 버킷(바구니)에 저장되는 결과는 다음과 같아요.‌

물론 DD Sketch와 같은 경우에는 위와 같이 균일하게 버킷 범위를 잡지 않고, 뒤의 버킷 범위가 앞의 버킷의 제곱 정도 되는 범위로 버킷 범위를 잡게 됩니다.

예를 들어 0번 버킷은 0~2, 1번 버킷은 2~4, 2번 버킷은 4~8, 3번 버킷은 8~16 이런 식으로 말이죠. (여담으로 이러한 형태로 버킷의 범위를 잡는 경우, 입력값이 파레토 분포를 따른다고 합니다)

그다음으로 인접한 버킷들을 합치면 데이터 범위가 유동적일 경우에 더 효과적으로 메모리 공간을 절약할 수 있습니다.

두 개의 버킷이 합쳐질 때, 더 적은 카운트를 가진 버킷을 삭제함으로써 가능한 일이죠! 이 작업이 반복될수록 정확도는 더 올라간답니다!

‌사실 이와 유사한 구조를 가진 알고리즘이 있어요!

구글에서 개발한 GKArray, 히스트릭스(Hystrix)에서도 사용하고 있는 HDRHistogram,  그 외 T-digest 등...

그렇다면 DD-Sketch와의 성능 비교 결과는 어떨까요?

아래 이미지와 같이 각 버킷에 값을 추가할 때뿐만 아니라 합치는 과정에서도 DD-Sketch가 가장 좋은 성능을 보여주고 있습니다.

‌[출처;성능 분석 그래프 및 자세한 정보는 다음 문서에서 확인해주세요] https://blog.acolyer.org/2019/09/06/ddsketch/‌
‌http://www.vldb.org/pvldb/vol12/p2195-masson.pdf

더불어, IMQA 개발팀에서도 관련 코드를 확인하고 실제로 작성해보는 시간을 가져보았답니다.‌

‌[실행결과]‌

이번 연구를 통해,  IMQA 통계 서비스에도 녹여낼 수 있을지 검토해 볼 예정이니 앞으로의 IMQA 통계 서비스, 기대해주셔도 좋습니다!

더불어 IMQA에서는 현재 백엔드 프로그래머를 채용 중입니다! 각자의 분야에서 전문적인 사람들이 능력 있는 분들과 함께 일하기를 기대하고 있습니다. 채용 정보를 확인해주세요!