목차 LIST
HyperLogLog는 집합의 카디널리티를 추정하는 확률적 데이터 구조(probabilistic data structure)이다.
즉, 정확한 값을 제공하지 않고 확률적인 방법을 사용하여 집합의 카디널리티를 추정하는 것이다.
HyperLogLog는 확률적 데이터 구조의 특성을 가지기 때문에 완벽한 정확도를 포기하고 대신 공간을 효율적으로 사용한다.
(HyperLogLog trades perfect accuracy for efficient space utilization.)
대용량 데이터셋에서 유니크한 값, 즉 카디널리티를 어떻게 구할 것인가? 에 대한 문제를 Cardinality Estimation Problem 또는 Count-distinct problem 이라고 한다.
HyperLogLog가 어떻게 카디널리티 추정 문제를 해결하는지를 보기 전에, 우리는 왜 이 문제를 해결하기 위해 HyperLogLog가 필요한지 생각해봐야 한다.
전시회에 방문한 유니크한 사용자 수를 구하려고 할 때, 방문자의 풀네임을 기록해서 카운트하는 방법이 있을것이다. 하지만 이름 대신 방문자들의 휴대폰번호 뒤 6자리만 적을수도 있다.
그럼에도 불구하고, 여전히 쉽지 않은 작업이다. 이 상황에서 준실시간으로 유니크한 사용자 수를 구할 수 있을까?
Flajolet-Martin Algorithm
수천명의 유니크 방문자 수를 실시간으로 그리고 손가락 숫자세기로로 구할 수 있을까?
해결법 : 당신이 본 휴대폰 번호 6자리 중에 leading zeros 가 가장 긴 수열을 손가락으로 계속 추적하면 된다.
참고로, leading zero는 숫자가 0으로 시작하는 것을 의미한다. 예를 들면 070은 leading zero를 가지고 있지만, 707은 leading zero가 없으므로 수열의 길이는 0이다.
예를 들어보자. 만약 532885 라면 가장 긴 연속된 0의 수열(longest sequence of zeroes)는 0이다.
042311 이라면 1이 된다.
10명 이상의 사람들을 봤을 때, 가장 긴 수열은 1일 가능성이 높으며 100명 이상의 사람들을 봤을 때는 2일 가능성이 높다.
무작위 데이터에서 k개의 0으로 이루어진 수열은 평균적으로 10ᴷ개의 요소마다 한 번씩 발생하는 것을 알 수 있다.
확률에 기반하여, 모든 숫자 중에서 찾은 leading zero의 가장 긴 수열이 L 일 때, 유니크 방문자의 추정 수는 대략 10ᴸ에 가까울 것이다.
1984년 논문에서는 원소들을 먼저 해시하여 더 균일하게 분포된 이진 결과를 얻었다.
예를 들면, 원소 x1을 010001로 해시하고 다른 x2를 101000으로 해시할 수 있다. 그러므로, 지역코드 같은 패턴으로 균일하게 분포되지 않는 전화번호도 정확하게 추정될 수 있다. 또한, 출력을 이진 비트 배열로 바꿨기 때문에 현재 카디널리티의 추정치는 2ᴸ이다.
즉, Flajolet-Martin Algorithm의 핵심은 원소를 해시하고 그 결과를 이진 비트배열로 변환한 뒤, 그 배열에서의 leading zeroes의 수(L)을 확인하는 것이다. 그런 다음 이 L 값을 사용하여 집합의 카디널리티를 추정한다. 이때 사용되는 공식이 2ᴸ이다.
이렇게 2ᴸ 공식이 나오는 이유는 이진로그의 특성화 해시 함수의 균등한 분포 특성 때문이다. 해시 함수는 데이터를 균등하게 분포시키는 특성이 있어, leading zero의 길이가 L일 경우 실제 원소 수는 대략 2ᴸ 정도라는 것을 추정할 수 있게 된다.
하지만, 2ᴸ 공식이 어떤 편향을 가지고 있음을 통계 분석을 통해 확인되었다. 2ᴸ 공식만으로는 집합의 카디널리티는 정확하게 추정하기는 어렵다는 것이다.
Flajolet-Martin 알고리즘의 개발자들은 이런 편향을 보정하기 위해 ϕ값을 도입했으며, ( ≈ 0.77351) 최종적으로 집합의 카디널리티를 추정하는 공식은 2ᴸ / ϕ 가 된다.
How to improve: LogLog
우리는 위에서 확인한 추정법이 충분히 신뢰할만하다고 생각하지 않을 수 있다. 가장 처음 원소로부터 얻은 해시 값이 0000010 이라면 어떤가? 이렇게 실생활에서는 데이터의 이상치(outlier)들이 추정을 왜곡시킬 수 있다.
어떻게 하면 우리의 추정법이 이상치(outlier)의 영향을 덜 받을 수 있을까?
한 가지 해결책은 여러 독립적인 해시 함수들로 Flajolet-Martin Algorithm 알고리즘을 반복적으로 수행하고 그 결과들의 평균을 내는 것이다. 예를 들어, 우리가 m 개의 다른 해시 알고리즘을 사용해서 leading zeroes의 가장 긴 수열을 얻는다면, 여기에서 leading zero의 가장 긴 수열의 값을 L₁, L₂, …, Lₘ 으로 표현하고 최종 추정값은 m * 2^((L₁+…+Lₘ)/m) 이 된다.
그러나, 여러 해싱 함수들로 하나의 값을 해싱하는 것은 계산적으로 비용이 많이 든다. 그래서 Flajolet와 새로운 친구 Marianne Durand는 대안을 제시하는데, 단 하나의 해시 함수를 사용하고 그 결과의 일부를 사용하여 값을 여러 개의 다른 버킷으로 나누는 것이다. 값을 버킷으로 나누기 위해 해시 값의 처음 몇 비트를 버킷의 인덱스로 사용하고 나머지를 기반으로 leading zero의 가장 긴 수열을 계산한다.
즉, 여러 해시 함수를 사용하는 대신에 하나의 해시 함수를 사용하되 그 결과를 분리하여 여러 '버킷'에 할당하는 방식을 제안한다. 이 방식은 계산 비용을 절감하면서 여러 번의 추정을 수행하는 효과를 얻을 수 있다.
예를 들어, 4개의 버킷을 원한다면, 해시의 처음 두 비트를 버킷의 인덱스로 사용할 수 있다.
Hash(x1) = 100101 -> bucket(10)=2 , longest sequence of leading zeroes = (0101) = 1
Hash(x2) = 010011 -> bucket(01)=1 , longest sequence of leading zeroes = (0011) = 2
Hash(x3) = 001111 -> bucket(00)=0, longest sequence of leading zeroes = (1111) = 0
Hash(x4) = 110101 -> bucket(11)=3, longest sequence of leading zeroes = (0101) = 1
모든 버킷의 longest leading zeros의 평균은 1(1+2+0+1/4)이다. 그러므로 추정값은 4 * 2^1 이 된다. 여기서는 매우 적은 샘플만 사용했기 때문에 실제 값에 가깝지 않지만, 우리는 아이디어만 이해하고 넘어갈 수 있다.
LogLog에 대한 수정계수(correction factor) ϕ에 대한 내용은 2003년 논문 "Loglog Counting of Large Cardinalities" 에서 찾을 수 있다. 지금까지 말한 내용이 LogLog이다. 추정치를 평균화하여 분산을 줄이며 LogLog의 표준 오차는 1.3/√m 이다. (m:버킷 수)
결과적으로 LogLog에서는 해시 함수에 버킷을 사용하여 정확도를 높이려고 한다.
LogLog보다 뛰어난 성능: SuperLogLog
Flajolet-Martin algorithm과 LogLog를 제안한 후에도, Flajolet은 계속해서 카디널리티 추정 문제를 고민했다.
LogLog를 소개한 논문에서, Flajolet과 Durand는 버킷에서 얻은 값들을 평균화하기 전에 가장 큰 값들을 제외하면 정확도가 크게 향상될 수 있음을 발견했다.
커밋으로부터 값들을 수집할 때, 70퍼센트의 가장 작은 값들만 보존하고 나머지는 평균을 위해 버린다. 이렇게 하면 정확도가 1.3/√m 에서 1.05/√m 로 향상된다! 놀라운 결과에 그들은 LogLog보다 우수한 이름을 주기 위해 SuperLogLog라고 이름을 붙인다.
The Ultimate Solution: HyperLogLog
2007년에 Flajolet은 카디널리티 추정 문제에 대한 최종 해결책을 찾아냈다. 그 솔루션은 HyperLogLog라고 불리며, 그는 이것을 "거의 최적의 카디널리티 추정 알고리즘"이라고 언급했다. 기본 아이디어는 매우 간단하다. LogLog로 부터 얻은 결과의 평균을 구하기 위해 기하평균(geometric mean)을 사용하는 대신, 조화 평균(harmonic mean)을 사용하는 것이다.
조화평균은 상호의 평균의 역수이다. (The harmonic mean is the reciprocal of the average of the reciprocals.)
상호는 1/value 를 의미한다. 그러므로 조화평균의 공식은 n / (1/a + 1/b + 1/c + ...)이다.
예를 들면, 1,2,4의 조화평균은 3 / (1/1 + 1/2 + 1/4) = 3 / (1.75) = 1.714 이다.
조화평균을 사용하는 이유가 뭘까?
조화평균은 큰 이상치(outlier)를 처리하는데 좋기 때문이다. 예를 들어, 2,4,6,100 에 대한 조화 평균을 구해보자.
4 / (1/2 + 4/1 + 6/1 + 100/1) = 4.32
큰 이상치 100은 우리가 역수만 사용하기 때문에 무시된다. 그러므로, 우리는 큰 이상치에 영향을 덜 받는 평균 계산 방법을 얻게 되었다.
* 조화평균은 일반적으로 극단적인 값을 갖는 이상치에 덜 민감한 평균값을 제공하므로 데이터에 큰 이상치가 있을 때 유용하게 사용된다.
2007년 논문 "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm" 에는 HyperLogLog의 수정계수(correction factor) ϕ 에 대한 내용을 확인할 수 있다.
LogLog에서 사용된 기하평균 대신 조화평균을 사용하고 SuperLogLog에서 가장 작은 70퍼센트의 값만 사용함으로써, HyperLogLog는 모든 알고리즘 중에서 가장 낮은 오차율인 1.04/√m를 달성했다.
HyperLogLog는 실제로 어떻게 쓰이고 있을까
HyperLogLog 알고리즘은 작은 메모리와 시간을 사용해서 큰 데이터셋의 유니크한 값의 개수를 추정할 수 있다. 이 알고리즘은 1.5kb의 메모리만 사용하여 10^9 이상의 카디널리티를 2%의 표준 오차로 추정할 수 있다. 실제로는 어디에서 쓰이고 있을까?
페타바이트 규모의 데이터를 처리해야 하는 데이터베이스와 데이터 웨어하우스에서 사용하는 경우가 있다. 데이터 쿼리의 효율적인 유니크 카운트 기능을 지원하기 위해 HyperLogLog를 사용한다. Redis, Amazon Redshift, Facebook Presto(Trino), BigQuery, Apache Druid 등이 있다.
마무리
원래 논문에서는 가장 긴 연속되는 0의 수열을 세지 않는다. Flajolet-Martin 알고리즘은 이진수에서 가장 낮은 중요도를 가지는 비트(least-significant bit (LSB))의 위치를 계산한다. 참고로, LSB는 컴퓨터에서 숫자를 이진 형태로 표현할 때, 가장 오른쪽에 위치한 비트를 말한다.
LogLog, SuperLogLog 및 HyperLogLog는 사실 왼쪽에서 가장 처음 나타나는 1의 위치를 계산한다. (즉, 선행하는 0의 개수 + 1).
개념을 이해하는 것이 주 목적이었기 때문에 이러한 세부 사항들을 단순화했지만, 모든 개념들은 꽤 유사하다.
References
https://chengweihu.com/hyperloglog/
'데이터 엔지니어링' 카테고리의 다른 글
| Apache Spark : Spark 소개 및 구조 (0) | 2024.02.06 |
|---|---|
| SingleStore DB에 대해 알아보자 (0) | 2024.01.13 |
| [Druid] indexing service / Overlord (0) | 2023.07.16 |
| Druid flatten spec 공식 문서 (0) | 2023.03.26 |
| Druid segment retention rules | 세그먼트 보존 규칙 (0) | 2023.03.26 |
댓글