Linear Counting: 서로 다른 값의 개수를 추정하는 방법

데이터가 정말 많을 때, 데이터에 들어 있는 서로 다른 값의 개수는 어떻게 셀 수 있을까? 예를 들어 어떤 큰 웹사이트, 아니면 .kr/.com/.whatever 도메인 전체의 순 방문자 수를 측정하는 서비스가 있다고 하자.

단순한 방법

별로 고민할 것도 없다. 데이터를 훑으면서 각 값을 알맞은 자료 구조에 한 번씩만 저장하면 된다. 파이썬으로는 대략 다음과 같이 쓸 수 있다(코드는 일부러 장황하게 썼다).

nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]

def count_unique(values):
    found = set()
    for item in values:
        if item not in found:
            found.add(item)
    return len(found)

print count_unique(nonunique_values) # 5

잘 동작한다. 그런데 데이터가 36자짜리 고유한 v4 식별자이고, 서로 다른 ID가 예를 들어 1,000만 개라면 어떨까? 음… 프로그램은 여전히 올바른 값을 구하지만, 메모리는 얼마나 차지할까? 직접 계산해 보자. 간단히 하기 위해 uuid를 정말로 36자짜리 문자열로 저장한다고 가정한다. 그러면 uuid 하나가 36바이트를 차지하므로 ID 1,000만 개는 360 MB를 차지한다.

솔직히 적은 양은 아니다. 서로 다른 ID가 1억 개라면 차지하는 메모리가 기가바이트 단위로 넘어간다. 그것도 데이터 자체가 차지하는 양만 센 것이다. 여기에 파이썬이나 자바스크립트가 차지하는 오버헤드를 더하면 ID가 1,000만 개만 되어도 기가바이트 단위에 이를 수 있다.

이런 상황은 피하고 싶다. 어떻게 해야 할까?

ID 자체를 더 효율적으로 저장하거나, 파이썬 대신 C를 써서 메모리 사용량을 크게 줄일 수도 있다. 하지만 여전히 만족스럽지 않고, 이런 프로그램은 여전히 엄청난 메모리를 차지한다. 그러면 이런 질문을 던져 볼 수 있다. 서로 다른 값이 9,563,618개인지 한 치의 오차도 없이 알아야 할까? 9,547,666개로 계산하면 무슨 문제가 생길까? 문제가 생기고 정확한 값이 꼭 필요하다면 그렇게 하면 된다. 그렇지 않다면, 데이터에 들어 있는 서로 다른 값의 개수를 될 수 있는 대로 정확하고 빠르게, 그리고 메모리를 최소한으로 써서 추정하는 방법을 알아보자.

해시 함수가 구원해 준다

문자열을 입력으로 받아 어떤 n비트 수를 출력하는 해시 함수를 생각한다. “문자열을 돌려주는” 해시 함수에 더 익숙하다면, 그 문자열을 다시 수로 바꾼다고 생각하면 된다. 어려울 것은 없다. 비트 수는 그 수가 얼마나 큰지를 나타낸다. 8비트 함수는 8비트를 차지하는 수를 돌려주고, 8비트에는 2⁸가지 값, 보통 0부터 255까지의 정수를 저장할 수 있다. 앞으로는 24비트 해시 함수를 쓴다. 이런 함수는 2²⁴가지, 즉 16,777,216가지 값을 돌려준다.

값 자체를 저장하는 대신 그 24비트 해시값을 저장한다. 24비트 해시값 1,000만 개를 저장하는 데는 30 MB가 필요하다. 앞의 360 MB보다 한 자릿수 적다. 코드는 다음과 같이 쓸 수 있다.

def nhash(item, n):
    return hash(item) % (2 ** n)

nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]

def count_unique_using_nhash(values):
    found = set()
    for item in values:
        checksum = nhash(item, 24)
        if checksum not in found:
            found.add(checksum)
    return len(found)

print count_unique_using_nhash(nonunique_values) # 5

함수 hash는 파이썬의 내장 함수로 정수를 돌려준다. 함수 nhash는 n비트 해시 함수를 단순하게 구현한 것이다. 어떻게 동작하는지 이해할 필요는 없다. 어차피 제대로 동작하지 않기 때문이다. 이 함수의 결과는 24비트를 차지하지 않지만, 지금은 원리가 중요하므로 상관없다.

그다음 함수 count_unique_using_nhash가 서로 다른 값을 센다. 모든 값을 훑으면서 해시값을 계산하고, 그 해시값이 변수 found에 아직 없으면 저장한다.

이 방법의 문제는 해시 함수가 서로 다른 문자열에 대해 같은 체크섬을 돌려줄 수 있다는 점, 즉 충돌이 생길 수 있다는 점이다. 충돌이 많이 생길수록 결과가 부정확해진다. 함수 count_unique_using_nhash는 거의 언제나 실제보다 적은 개수를 돌려준다.

어떤 해시 함수를 고르면 될까? 그리 중요하지 않지만, 보통은 MurmurHash의 한 변형을 권한다.

비트맵

C 언어 프로그래밍 기초 수업을 열심히 들었다면 비트맵을 알고 있을 것이다. 비트맵은 어떻게 쓸 수 있을까?

아이디어를 배열로 설명해 보자. 계산한 체크섬을 저장할 필요 없이, 길이가 2²⁴인 배열을 만들고 모든 원소를 0으로 초기화하면 된다. 그리고 어떤 체크섬을 만나면(체크섬은 수이다!) 배열의 인덱스 checksum에 1을 적어 이 체크섬을 이미 찾았다고 표시한다. 그러면 서로 다른 원소의 개수는 이 배열에 있는 1의 개수와 거의 같다. 코드는 다음과 같이 쓸 수 있다.

def count_unique_using_array(values):
    # 길이가 2^24이고 모두 0으로 초기화된 리스트
    array = [0] * (2 ** 24) 
    for item in values:
        array[nhash(item, 24)] = 1
    return sum(array)

print count_unique_using_array(nonunique_values)

하지만 이 경우 배열을 쓰면 메모리가 매우 많이 든다. 칸마다 1이나 0 하나만 저장하면 되는데도 그렇다. 그 대신 비트 배열을 쓸 수 있다. 예를 들어 정수(integer)는 32비트에 저장할 수 있다. 수 354를 이진법으로 나타내면 101100010이다. 따라서 수 354는 컴퓨터에 32비트 정수로 다음과 같이 저장된다(자세한 부분은 넘어가자).

00000000 00000000 00000001 01100010

꽤 쓸 만한 형식이지 않은가? 함수에서는 0과 1만 저장하면 되는데, 방금 본 것처럼 보통의 수도 결국 0과 1의 덩어리일 뿐이다(컴퓨터 안의 모든 것이 그렇듯이…). 요컨대 비트 연산자를 쓰면 1 하나가 정말로 1비트만 차지하도록 저장할 수 있다.

배열을 쓴 함수로 돌아가 보자. 이를 비트 배열로 바꾸면 24비트 해시 함수에는 크기가 2²⁴비트, 즉 2 MiB인 비트 배열이면 충분하다. 상당한 개선이다!

출력값이 2³²가지, 즉 4,294,967,296가지인 32비트 해시 함수를 쓰면 크기가 0.5기가바이트인 비트 배열이 필요하다. 수십억 개 단위의 서로 다른 값까지 셀 수 있다는 점을 생각하면 나쁘지 않다.

Linear Counting

앞에서 말했듯이 해시 함수를 쓰면 서로 다른 값의 개수를 추정할 수 있을 뿐이다. 서로 다른 값의 개수가 해시 함수의 서로 다른 출력값의 개수에 가까워질수록 이 추정은 부정확해진다. 서로 다른 값이 50억 개인 데이터를 24비트 해시 함수로 셀 수 없는 것은 당연하다.

하지만 해시 함수로 구한 추정값은 더 정확하게 다듬을 수 있다. 여기에 쓰는 아이디어는 간단하다. 데이터에 서로 다른 값이 많을수록 시간이 지나면서 충돌이 생길 가능성이 커진다. (충돌 = 서로 다른 두 입력에 대해 해시 함수의 출력, 즉 체크섬이 같은 것.) 이제 계산을 조금 할 것이므로 변수 몇 개를 정하자.

• n비트 해시 함수 h를 쓴다.
• 함수 h의 가능한 출력은 모두 2n가지이다. 이 개수를 문자 m으로 나타낸다. 즉 m=2n이다.
• 찾은 체크섬을 저장할 비트 배열을 대문자 A로 나타낸다. 배열 A의 길이는 m이다.
• 알고리즘으로 데이터 전체를 훑고 나면 비트 배열의 값 중 일부는 0이고 일부는 1이다. 여기서 관심 있는 것은 “0의 개수를 배열의 길이로 나눈 값”, 즉 비트 배열에서 0이 차지하는 비율이다. 처음에는 배열이 모두 0으로 초기화되어 있으므로 이 비율은 1이다. 0과 1이 반반이면 비율은 2분의 1이다. 이 값을 Z로 나타내고 Z = 0의 개수 / m으로 계산한다.

이때 Z의 값이 클수록 서로 다른 값의 개수에 대한 추정이 정확하다고 더 확신할 수 있다. 예를 들어 빈 데이터를 훑으면 비트 배열에는 0만 남고 Z의 값은 1이 된다. 따라서 데이터에 들어 있는 서로 다른 원소의 개수가 비트 배열에 있는 1의 개수, 즉 0과 같다고 완전히 확신할 수 있다.

Z의 값이 0.99이면 비트 배열의 100분의 1이 1로 채워져 있다는 뜻이다. 배열의 99%에는 0이 들어 있다. 이 정도면 아직 괜찮다. 계산하는 동안 충돌이 별로 생기지 않았을 가능성이 높으므로 보정이 전혀 필요 없거나 아주 조금만 필요하다. 하지만 Z의 값이 0.05이면 배열의 5%만 0으로 남아 있으므로, 계산하는 동안 충돌이 아주 많이 생겼을 것이다. 보정을 크게 해야 한다.

그러면 이 보정은 어떻게 계산할까? 로그를 이용한다. 로그함수의 그래프는 다음과 같다.

여기서 관심 있는 것은 구간 (0, 1]의 빨간 부분이다. x축에 Z의 값을 놓으면, Z가 클수록 y의 값이 0에 가까워진다. 반대로 Z가 작을수록 y의 값은 작아진다. 이 수에 -m을 곱하면 최종 추정값이 나온다. Z의 값이 충분히 작으면 -1보다 작은 수가 나오고, 이 값에 -m을 곱하면 m보다 큰 추정값을 얻는다는 점에 주목하자. 즉 서로 다른 값의 개수가 해시 함수 h가 내놓을 수 있는 체크섬의 개수보다 많다고 추정한 것이다.

서로 다른 값의 개수 p를 구하는 식 전체는 다음과 같다.

$$p=-m\cdot \ln Z$$

(비트 배열 없이 보통의 배열만으로) 구현하면 다음과 같다.

from uuid import uuid4
from math import log

number_of_unique_values = 10000
nonunique_values = [uuid4() for _ in xrange(number_of_unique_values)]
nonunique_values += nonunique_values

def nhash(item, n):
    return hash(item) % (2 ** n)

def count_unique_using_array(values, n):
    array = [0] * (2 ** n)
    for item in values:
        array[nhash(item, n)] = 1
    return sum(array)

def linear_counting(values, n):
    estimate = count_unique_using_array(values, n)
    m = 2 ** n
    number_of_zeros = m - estimate
    Z = float(number_of_zeros) / m
    # 여기서 log는 밑이 e인 자연로그이다
    p = (-m) * log(Z)      
    p = int(round(p))
    print "Debug info: estimate=%s, m=%s, number_of_zeros=%s, Z=%s, p=%s" % \
          (estimate, m, number_of_zeros, Z, p)
    return p

print "Cardinality: %s" % linear_counting(nonunique_values, 16)

함수 linear_counting에서는 먼저 n비트 해시 함수를 쓰는 앞의 알고리즘으로 첫 추정값을 구한다. 그다음 배열에서 0이 차지하는 비율을 구하고 식에 따라 보정한다. 코드의 로그는 자연로그이다. 변수 nonunique_values에는 서로 다른 문자열이 number_of_unique_values개 들어 있으므로, 이 예에서는 리스트 nonunique_values에 서로 다른 값이 1만 개 있다. 여섯 번째 줄의 이상한 코드는 배열에 같은 값이 여러 번 들어가게 한다. 리스트 끝에 같은 리스트를 이어 붙이므로 각 값이 배열에 두 번씩 들어간다. 그다음 계산을 한다. 이상적으로는 함수가 리스트에 서로 다른 값이 1만 개 있다고 돌려주어야 한다. 출력은 다음과 같다.

Debug info: estimate=9289, m=65536, number_of_zeros=56247, 
Z=0.858261108398, p=10017
Cardinality: 10017

리스트 nonunique_values는 매번 새로 만들어지므로 호출할 때마다 결과가 다르다. 여기서는 16비트 해시 함수를 썼다. 함수 count_unique_using_array의 첫 추정값은 리스트에 서로 다른 값이 9,289개 있다는 것이었다. 보정으로 이 추정값을 10,017로 다듬었는데, 꽤 괜찮은 결과이다. 보정한 추정값은 실제보다 0.17%만 크지만, 보정 전에는 7.11%나 작았다.

“더 큰” 해시 함수, 예를 들어 24비트 해시 함수를 쓰면 더 정확한 결과를 얻는다.

Debug info: estimate=9997, m=16777216, number_of_zeros=16767219, 
Z=0.999404132366, p=10000
Cardinality: 10000

처음 추정값부터 괜찮았고, 보정한 값은 정확히 1만이 되었다. 예로 서로 다른 ID 100만 개, 즉 number_of_unique_values = 1000000으로 시험해 볼 수도 있다. 24비트 해시 함수로는 다음 결과를 얻는다.

Debug info: estimate=971033, m=16777216, number_of_zeros=15806183, 
Z=0.94212192297, p=1000267
Cardinality: 1000267

나쁘지 않다. 게다가 비트 배열로 구현하면 배열은 앞에서 말한 2메가바이트(+ 언어가 쓰는 메모리)만 차지한다. 꽤 좋은 결과이다. But we can do better! Much better. 하지만 그 이야기는 다음 글에서 한다.

그동안 논문 A Linear-Time Probabilistic Counting Algorithm for Database Applications [PDF]를 읽어 보아도 좋다. 아니면 시리즈의 다음 글인 min-value 알고리즘으로 넘어가도 된다.