HyperLogLog - 대량 데이터 분석시 유용한 확률적 자료구조

목적

퍼널 분석을 하기 위해 로그 데이터에 직접 접근을 하고자 할 때가 있다. 하지만 보통 로그 데이터의 사이즈는 매우 커서 조회 작업 자체가 어려운 경우가 있다. 이로 인해서 액션(서비스 기능 개선 또는 마케팅)에 대한 의사결정 자체를 하기가 어려운 경우가 많다. 그리고 어떻게든 데이터를 잘게 쪼개서 데이터를 분석했다 해도, 그 데이터의 샘플링 사이즈가 너무 작아(분, 시간 단위) 일단위의 의사결정을 진행하기에는 한계가 있을 때도 있다.

이럴 때 우리는 HyperLogLog를 이용해 대략적인 수치를 추정해봄으로써 의사결정을 위한 데이터 분석을 진행할 수 있다.

HyperLogLog는 매우 적은 메모리로 집합의 원소 개수를 추정할 수 있는 방법입니다. 집합의 원소 개수를 정확하게 계산하기 위해 아주 많은 메모리가 필요할 때나 하나의 메모리에 모두 담을 수 없을 정도로 원소의 개수가 많을 때, 정확하지 않지만 최대한 정확한 값을 상대적으로 적은 메모리만 사용해 얻고 싶을 때 사용할 수 있는 방법입니다. (출처: 네이버 D2 )

특징

• 적은 메모리를 차지하는 자료구조
• 이 자료 구조로부터 유일한 원소의 수를 추정할 수 있다(원소가 담긴 집합의 크기 근사값 = cardinality)
• 많은 HyperLogLog 구현에서 merge 연산을 지원한다(합집합)
• Hash를 사용하는 방식이기 때문에 추정치에는 오차가 있을 수 있으며, 자료구조의 크기를 조정하여 오차 범위를 조정할 수 있다.
• 스트림 데이터에서의 유일 원소 수 추정에 사용되는 경우가 많음

활용 방식 예(presto)

예) 매달 활동 유저에 대한 HyperLogLog를 만들어둔다

2019년 1월과 2019년 2월에 한 번이라도 서비스에 들어온 유저의 유니크한 수를 추정하기

• 1월과 2월의 HyperLogLog를 merge한 뒤 merge된 HyperLogLog에서 cardinality를 측정한다

2019년 1월과 2019년 2월, 두 달에 모두 서비스에 들어온 유저의 유니크한 수 추정하기

• (1월 HyperLogLog의 cardinality) + (2월 HyperLogLog의 cardinality) – (merge된 HyperLogLog의 cardinality)

2019년 1월부터 6월까지의 유입 유저 유니크 수 추정하기

• 1월부터 6월까지의 HyperLogLog를 모두 merge한 뒤 cardinality 측정

참고자료

• 네이버 D2 페이지에 올라온 HyperLogLog에 대한 설명글(꼭 읽어보세요) : https://d2.naver.com/helloworld/711301
• Facebook Code 페이지의 presto HyperLogLog 설명 : https://code.fb.com/data-infrastructure/hyperloglog/
• 프레스토의 HyperLogLog 설명 : https://prestodb.github.io/docs/current/functions/hyperloglog.html
• 위키피디아 : https://en.wikipedia.org/wiki/HyperLogLog
• https://okky.kr/article/404747
• https://blog.devartis.com/hyperloglogs-a-probabilistic-way-of-obtaining-a-sets-cardinality-3b5e6a982a12