중복집합에 들어 있는 서로 다른 값의 개수를 추정하는 알고리즘 시리즈를 이어, 이번에는 state of the art 알고리즘인 HyperLogLog를 다룬다. 이 알고리즘의 아이디어는 모두 앞에서 설명한 LogLog에서 나왔으므로, 이 글을 읽기 전에 LogLog를 잘 알아 두는 것이 좋다.

LogLog 알고리즘에는 두 가지 큰 문제가 있었다.

이상값

LogLog의 최종 추정값은 이상값, 즉 다른 값들과 매우 동떨어진 값에 아주 민감하다. 그룹마다 구한 0 접미사의 최대 길이는 대부분 비슷해서, 예를 들어 12에서 15 사이에 있는 경우가 많다. 그런데 갑자기 쾅 하고 0 접미사 하나의 길이가 27이 된다. 이 큰 차이가 서로 다른 값의 개수에 대한 최종 추정값을 흐트러뜨린다. 보통의 산술평균은 이런 값을 잘 다루지 못하기 때문이다. 고액 연봉을 받는 소수의 최고 경영자와 임원이 나라 전체의 평균 임금을 끌어올리는 것과 같은 원리이다.

알고리즘의 저자들은 처음에 이상값을 없애는 방법, 즉 가장 큰 최댓값 몇 개를 평균에 넣지 않는 방법으로 이 문제를 해결하려 했지만, 그다지 좋은 해결책은 아니었다. 나중에는 다른 방법을 시도했다. 산술평균 대신 조화평균을 쓴 것이다. 조화평균은 평균에서 멀리 떨어진 값이 있을 때 훨씬 좋은 성질을 보인다.

작은 카디널리티에서 매우 나쁜 결과

LogLog는 작은 중복집합의 카디널리티를 추정할 때 결과가 형편없다. 중복집합에 서로 다른 원소가 몇 개뿐이면 LogLog는 터무니없이 큰 추정값을 돌려준다. 저자들은 이 문제를 영리하게 해결했다. 입력이 카디널리티가 작은 중복집합이면 LogLog 알고리즘 대신 전혀 다른 알고리즘, 이미 익숙한 Linear counting을 쓴다. 그런데 카디널리티를 모르는데 입력의 카디널리티가 작다는 것을 어떻게 알 수 있을까?

먼저 LogLog로 서로 다른 원소의 개수를 추정하고, 이 추정값이 비교적 작으면 그 추정값을 버리고 Linear counting 알고리즘으로 다시 구한다. Linear counting이 어떻게 동작하는지 빠르게 되짚어 보자. 처음에 미리 정한 크기(보통 2의 거듭제곱)의 (비트) 배열을 0으로 채워 할당한다. 중복집합의 모든 원소를 훑으면서 해시값을 계산하고, 이를 0부터 배열의 길이 빼기 1까지의 정수 i로 바꾼다. 그리고 배열의 인덱스 i에 1을 저장한다. 마지막으로 배열에 있는 0과 1의 개수를 세고 간단한 식으로 카디널리티를 추정한다.

그런데 LogLog 알고리즘은 계산한 해시값을 “저장”하는 비트 배열을 쓰지 않는다. 그 대신 접미사의 최대 길이를 저장하는 배열을 쓴다. 이 배열은 예를 들어 다음과 같다.

[2, 5, 9, 0, 5, 4, 4, 0]

여기서 각 수는 계산한 해시값의 해당 그룹에서 0 접미사의 최대 길이를 나타낸다. 그런데 i번째 위치의 값이 0이 아니라면, 중복집합의 값 가운데 (3비트) 해시값이 i인 원소가 반드시 있다는 뜻이다. 다시 말해 0은 그대로 두고 양수는 모두 1로 바꾸면 이 배열을 Linear counting용 비트 배열로 바꿀 수 있다. 앞의 배열에서는 다음 비트 배열을 얻는다.

[1, 1, 1, 0, 1, 1, 1, 0]

이제 Linear counting 알고리즘을 적용하여 카디널리티를 추정할 수 있다.

그런데 한 가지 함정이 있다. 배열에는 0 접미사의 최대 길이를 저장하는데, 어떤 그룹에서 모든 해시값이 1로 끝나면 어떻게 될까? 예를 들어 마지막 세 비트를 해시값이 속한 그룹의 식별자로 쓰면, 해시값 “01001100”의 0 접미사의 길이는 0이다. 벡터 “01001”이 1로 끝나기 때문이다. 그러면 최댓값 배열의 인덱스 4(100₂=4₁₀)에 0을 저장한다. 그런데 Linear counting 알고리즘에서는 이것이 해시값이 4인 값을 찾지 못했다는 뜻이 되는데, 이는 사실이 아니다.

그래서 최댓값 배열에 가장 긴 0 접미사의 길이 대신 “오른쪽에서 첫 번째 1”의 인덱스(인덱스는 1부터 센다)를 저장하도록 알고리즘을 고친다. 이 인덱스는 0 접미사의 길이에 1을 더한 것과 같다. 그러면 인덱스 i의 값이 0이라는 것은 해시값이 i인 값이 하나도 없다는 뜻이 되므로, 이 배열을 Linear counting에 쓸 수 있다.

HyperLogLog의 구현

차근차근 살펴보자.

def alpha(num_buckets):
    return (0.7213 / (1 + 1.079 / num_buckets))

함수 alpha는 계산한 추정값을 보정하는 값을 돌려준다. 지난 글에서 본 것과 같은데, HyperLogLog에서는 그룹의 개수에 따라 alpha의 값이 달라진다.

def trailing_zeroes(number):
    if number == 0: 
        return 0
    zeroes = 0
    while (number & 1) == 0:
        zeroes += 1
        number = number >> 1
    return zeroes

수의 끝에 있는 0 비트의 개수를 돌려주는 함수이다.

def count_maxims(values, k):
    num_buckets = 2 ** k  
    max_zeroes = [0] * num_buckets

    for value in values:
        h = hash(value)
        bucket_index = h & (num_buckets - 1)
        bucket_hash = h >> k
        num_zeros = trailing_zeroes(bucket_hash) + 1
        max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)

    return max_zeroes

모든 값을 훑으면서 num_buckets개의 그룹으로 나누고, 그룹마다 오른쪽에서 첫 번째 1의 인덱스(0 접미사의 최대 길이 더하기 1)를 구하는 함수이다.

def linear_counting(number_of_ones, num_buckets):
    number_of_zeros = num_buckets - number_of_ones
    Z = float(number_of_zeros) / num_buckets
    p = (-num_buckets) * log(Z)
    return p

Linear counting 알고리즘을 계산하는 함수를 조금 고친 것이다.

def estimate_cardinality(values, k): 
    num_buckets = 2 ** k   
    max_zeroes = count_maxims(values, k)
    estimate = float(alpha(num_buckets) * (num_buckets**2)) / sum(2**(-r) for r in max_zeroes)
    number_of_ones = sum(1 if x > 0 else 0 for x in max_zeroes)

    if (estimate <= 2.5 * num_buckets) and (number_of_ones < num_buckets):
        return linear_counting(number_of_ones, num_buckets)
    else:
        return estimate

이 모든 것을 하나로 묶는 주 함수이다. 먼저 고친 LogLog로 추정값을 구하는데, 네 번째 줄에서 산술평균 대신 조화평균을 쓴다. 마지막으로 계산한 추정값이 그룹 개수의 2.5배보다 작고(이때는 LogLog의 보통 추정값이 Linear counting을 쓸 때보다 나쁠 것으로 예상한다) 최댓값 배열에 0이 적어도 하나 있으면(1로만 이루어진 배열은 Linear counting에 쓸 수 없다. 앞의 글 참고) Linear counting으로 보정한다. HyperLogLog의 결과는 어떨까?

카디널리티가 차례로 10, 100, …, 1,000,000인 집합의 카디널리티를 추정하는 시험 코드를 실행해 보자.

for x in range(1, 7):
    num_values = 10**x
    values = (str(uuid4()) for _ in xrange(num_values))
    cardinality = estimate_cardinality(values, 14)
    print "Cardinality: %s, relative error: %s" % (cardinality, num_values / cardinality)

결과는 다음과 같다.

Cardinality: 10.0030530001, relative error: 0.999694793165
Cardinality: 100.306423257, relative error: 0.996945128268
Cardinality: 1003.0892434, relative error: 0.99692027063
Cardinality: 10013.1348931, relative error: 0.998688233677
Cardinality: 100520.045562, relative error: 0.994826449206
Cardinality: 998088.420332, relative error: 1.0019152408

결과가 언제나 정답에서 1% 미만으로 벗어난다. 아주 좋다!

HyperLogLog의 또 다른 개선

HyperLogLog는 그 뒤로도 몇 가지 흥미로운 개선을 거쳤다. 남은 문제 가운데 하나는 메모리 사용량이 크다는 점이다. 지난 글에서 메모리 사용량을 극찬하고 최댓값 배열을 저장하는 데 768바이트면 충분하다고 계산했으니 이상하게 들릴 것이다. 그런데 거대한 중복집합 하나가 아니라 작은 중복집합 수백만 개의 카디널리티를 동시에 구하거나, 계산한 최댓값 배열을 나중에 이리저리 쓰려고 데이터베이스에 저장하려고 하면 문제가 생긴다.

예를 들어 중복집합 10억 개의 카디널리티를 동시에 구한다면, 지금의 구현으로는 1,000,000,000 곱하기 768바이트, 즉 768 GB가 필요하다. 한편으로는 나쁘지 않지만… 다른 한편으로는 HyperLogLog를 더 잘 구현할 수 있다.

희소 표현

k=12로 설정한다고 하자. 즉 그룹을 식별하는 데 12비트를 쓰므로 해시값의 그룹은 2¹²개가 된다. 알고리즘을 시작할 때 길이가 4096인 배열을 할당해야 한다(함수 count_maxims의 세 번째 줄 참고). 그리고 중복집합에 서로 다른 원소가 3개 있다고 하자. 그러면 배열의 서로 다른 세 자리에 값을 넣고, 나머지 4093개 값은 0으로 남는다. 나머지 4093개는 전혀 쓰지 않은 것이다. 그다지 효율적이지 않다.

대부분이 0이고 쓰이지 않으면서도 귀중한 메모리를 차지하는 배열을 피하려면, 처음에는 값을 [인덱스, 값] 쌍으로 저장하면 된다. 예를 들어 다음 배열은

[7, 0, 0, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

훨씬 메모리 효율적으로 다음 두 쌍으로 나타낼 수 있다.

[0, 7], [4, 12]

쓰지 않는 공간을 잔뜩 할당해 두는 대신 정말 필요한 공간만 차례로 할당할 수 있다. 이런 표현을 희소(sparse) 표현이라고 한다. 하지만 어느 순간에는 이 표현이 그냥 배열에 저장하는 것보다 메모리를 더 많이 쓰게 된다. 그때는 정보를 잃지 않고 희소 표현을 보통의 배열로 바꾸면 된다.

오프셋

실제로 써 보면 배열의 값은 모두 대략 비슷하다. 최댓값 배열은 보통 예를 들어 다음과 같다.

[12, 13, 11, 13, 15, 12, 14, 11, 12, ...,  13, 14, 11]

모든 값이 13 근처에 있다. 이런 배열의 크기를 줄이는 또 다른 방법은 모든 원소에서 어떤 고정된 값을 빼고 그 값을 기억해 두는 것이다. 예를 들어 8을 뺄 수 있다.

[4, 5, 3, 5, 7, 4, 6, 3, 4, ..., 5, 6, 3]

이제 배열의 각 값이 메모리를 덜 쓴다. 첫 번째 배열에는 0부터 15까지의 수를 저장해야 하므로 4비트가 필요하지만, 두 번째 배열에는 0부터 7까지의 수만 저장하므로 3비트면 충분하다. 물론 배열을 비트 단위로 구현한다고 가정한 것이다. 배열의 값을 읽을 때는 기억해 둔 값을 다시 더해야 한다.

…그 밖에도 개선 방법이 많다. 이 분야의 연구는 아직 진행 중이므로 앞으로도 흥미로운 아이디어가 나올 것이다. 다음 글에서는 HyperLogLog 벡터의 합집합과 교집합을 다루고, 머지않아 HyperLogLog 벡터를 수십억 개 저장하는 것이 왜 쓸모 있는지도 이야기하려 한다.

링크와 참고 자료

• 전체 구현은 GitHub에서 볼 수 있다.
• HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm [PDF]: HyperLogLog를 처음 소개한 원래 논문.
• HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm [PDF]: 앞에서 말한 희소 표현 등을 더해 원래 HyperLogLog를 개선한 버전.