일반적으로 나는 무작위 알고리즘을 좋아하지만, 그중에서도 특히 좋아하는 것이 하나 있다. 어떻게 동작하는지 이해하고 나서도 프로그래머의 관점에서는 여전히 마법처럼 느껴지기 때문이다. 이 알고리즘은 시간이나 공간 측면에서 요구하는 것이 매우 적음에도 거의 비논리적으로 보이는 일을 해낸다. 이 알고리즘의 이름은 HyperLogLog이며, 오늘 Redis의 새로운 자료구조로 소개된다.

고유한 것 세기
===

보통 고유한 것들을 세는 일, 예를 들어 오늘 웹사이트에 접속한 고유 IP 수나 사용자들이 수행한 고유 검색어 수 등을 세려면 지금까지 마주한 모든 고유 요소를 기억해야 한다. 다음 요소가 이미 본 요소들의 집합과 일치하는지 확인하고, 한 번도 본 적 없는 새로운 요소일 때만 카운터를 증가시키기 위해서다.

이를 위해서는 우리가 세고 있는 집합의 카디널리티(원소 수)에 비례하는 메모리가 필요하며, 이는 종종 감당할 수 없을 정도로 크다.

무작위성을 이용해 상수 수준의 적은 메모리만으로 집합 내 고유 원소 수의 근사치를 제공하는 알고리즘 부류가 있다. 현재 알려진 이러한 알고리즘 중 가장 뛰어난 것이 HyperLogLog이며, Philippe Flajolet가 고안한 것이다.

HyperLogLog는 매우 적은 메모리로도 집합의 카디널리티에 대해 매우 우수한 근사치를 제공한다는 점에서 놀랍다. Redis 구현에서는 키당 12kbytes만으로 표준 오차 0.81%로 개수를 셀 수 있으며, 셀 수 있는 항목 수에는 사실상 제한이 없다. 2^64개에 가까워지지 않는 한 말이다(그럴 가능성은 매우 낮아 보인다).

이 알고리즘은 원 논문 [1]에 문서화되어 있으며, 실제 구현과 변형들은 Google의 2013년 논문 [2]에서 심도 있게 다뤄졌다.

[1] http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
[2] http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/40671.pdf

어떻게 동작하는가?
===

HyperLogLog에 대해 더 배울 수 있는 훌륭한 자료는 [3]을 비롯해 많이 있다.

[3] http://blog.aggregateknowledge.com/2012/10/25/sketch-of-the-day-hyperloglog-cornerstone-of-a-big-data-infrastructure/

여기서는 [3]에서 찾은 아주 영리한 예시를 이용해 기본 아이디어만 다루겠다. 당신이 하루 종일 동전을 던지며 끊기지 않고 연속으로 앞면이 나온 횟수를 세었다고 내게 말한다고 상상해보자. 최대 연속 앞면이 3번이었다고 말한다면, 당신이 동전을 그리 많이 던지지 않았다고 짐작할 수 있다. 반대로 가장 긴 연속이 13번이었다면, 아마 동전을 던지는 데 꽤 오랜 시간을 보냈을 것이다.

하지만 운이 좋아 처음부터 10번 연속으로 앞면이 나오는, 가능성은 낮지만 일어날 수 있는 일이 생기고 바로 동전 던지기를 멈춘다면, 나는 당신이 동전을 던지는 데 쓴 시간에 대해 매우 잘못된 추정을 하게 될 것이다. 그래서 나는 실험을 반복해 달라고 부탁할 수 있다. 이번에는 동전 10개와 종이 10장을 사용해, 동전 하나당 종이 한 장씩 가장 긴 앞면 연속을 기록하는 것이다. 이번에는 관찰할 데이터가 더 많아지므로 추정이 더 정확해진다.

요컨대 HyperLogLog가 하는 일이 바로 이것이다. 관찰하는 모든 새로운 요소를 해시한다. 해시의 일부는 레지스터를 인덱싱하는 데 사용된다(앞선 예시의 동전+종이 쌍에 해당한다. 기본적으로 원래 집합을 m개의 부분 집합으로 나누는 것이다). 해시의 나머지 부분은 해시에서 선행 0이 연속으로 나타나는 가장 긴 길이를 세는 데 사용된다(우리의 앞면 연속에 해당한다). N+1개의 0이 연속될 확률은 N개의 0이 연속될 확률의 절반이므로, 각 부분 집합마다 지금까지 관찰된 최대 0 연속 길이에 맞춰 설정된 서로 다른 레지스터들의 값을 관찰함으로써 HyperLogLog는 매우 우수한 카디널리티 근사치를 제공할 수 있다.

Redis 구현
===

HyperLogLog의 표준 오차는 1.04/sqrt(m)이며, 여기서 “m”은 사용된 레지스터 수다. Redis는 16384개의 레지스터를 사용하므로 표준 오차는 0.81%이다.

Redis 구현에서 사용하는 해시 함수의 출력은 64비트이며, 그중 14비트를 사용해 16k개의 레지스터에 주소를 지정하므로 50비트가 남는다. 따라서 우리가 마주할 수 있는 가장 긴 0 연속은 6비트 레지스터에 들어간다. 이것이 Redis HyperLogLog 값이 16k개의 레지스터에 대해 12k bytes만 사용하는 이유다.

Google이 [2]에서 제시한 알고리즘 수정 사항 중 하나인 64비트 출력 함수를 사용하기 때문에, 셀 수 있는 집합의 카디널리티에는 실질적인 제한이 없다. 게다가 매우 작은 카디널리티에서는 오차가 매우 작게 나타나는 경향이 있다는 점도 주목할 만하다. 다음 그래프는 서로 다른 두 개의 큰 집합에 대해 알고리즘을 실행한 결과를 보여준다. x축은 집합의 카디널리티를, y축은 상대 오차(퍼센트)를 나타낸다.



빨간색과 녹색 선은 전혀 관련 없는 두 집합에 대한 서로 다른 두 실행 결과다. 카디널리티가 증가해도 오차가 일관되게 유지됨을 보여준다. 하지만 훨씬 더 작은 카디널리티에서는 훨씬 더 작은 오차를 기대할 수 있다:



녹색 선은 카디널리티 100까지의 단일 실행 오차를, 빨간색 선은 100번 실행에서 발견된 최대 오차를 보여준다. 수백 정도의 카디널리티까지는 알고리즘이 매우 작은 오차를 내거나 정확한 답을 제공할 가능성이 매우 높다. 이는 계산된 값이 사용자에게 표시되어 정답 여부를 시각적으로 확인할 수 있을 때 매우 유용하다.

Redis 구현의 소스 코드는 Github에서 볼 수 있다:

https://github.com/antirez/redis/blob/unstable/src/hyperloglog.c

API
===

Redis의 관점에서 HyperLogLog는 단지 문자열일 뿐이며, 길이가 정확히 12k + 8 bytes인 문자열이다(정확히는 12296 bytes다). 모든 HyperLogLog 명령은 정확히 이 크기의 String 값에 대해 호출되면 정상적으로 실행되고, 그렇지 않으면 오류를 보고한다. 하지만 문자열에 무엇이 저장되어 있든 모든 호출은 안전하다. 쓰레기 값을 저장하고도 카디널리티 추정을 요청할 수 있으며, 어떤 경우에도 서버가 충돌하지 않는다.

또한 표현의 모든 것은 엔디안에 중립적이며 프로세서 워드 크기의 영향을 받지 않으므로, 32비트 빅 엔디안 프로세서가 64비트 리틀 엔디안 프로세서의 HLL을 읽을 수 있다.

HyperLogLog가 문자열이라는 점 덕분에 RDB 레벨에서 실제 타입을 새로 도입할 필요가 없었다. 덕분에 이 작업을 향후 며칠 안에 Redis 2.8로 백포트할 수 있게 되었고, 여러분은 곧바로 HyperLogLog를 사용할 수 있게 될 것이다. 게다가 포맷은 자동으로 직렬화되며 쉽게 가져오고 복원할 수 있다.

API는 세 개의 새로운 명령으로 구성된다:

PFADD var element element … element
PFCOUNT var
PFMERGE dst src src src … src

명령어 접두사 “PF”는 Philippe Flajolet를 기리기 위한 것이다 [4].

[4] http://en.wikipedia.org/wiki/Philippe_Flajolet

PFADD는 “var”에 저장된 HLL에 요소를 추가한다. 변수가 존재하지 않으면 Redis API 호출에서 늘 그렇듯 빈 HLL이 자동으로 생성된다. 이 명령은 가변 인자를 받으므로 매우 적극적인 파이프라이닝과 대량 삽입이 가능하다.

이 명령은 내부 HyperLogLog가 수정되면 1을, 그렇지 않으면 0을 반환한다. 요소를 추가할수록 실제로 어떤 레지스터를 수정할 확률이 감소하므로 이는 사용자에게 흥미로운 점이다. 새로운 카디널리티를 사용할 수 있다는 힌트를 API가 제공할 수 있다는 사실 덕분에, 계속해서 요소를 추가하면서 새로운 값이 생겼을 때만 근사 카디널리티를 가져오는 프로그램을 만들 수 있다.

PFCOUNT는 추정된 카디널리티를 반환하며, 키가 존재하지 않으면 0을 반환한다.

마지막으로 PFMERGE는 N개의 서로 다른 HLL 값을 하나로 병합할 수 있다. 결과 HLL은 서로 다른 HLL 값들로 셌던 여러 집합들의 합집합 카디널리티에 대한 추정치를 보고한다. 마법처럼 보이지만, HLL은 무작위적이면서도 완전히 결정적이기 때문에 동작한다. 그래서 PFMERGE는 각 레지스터마다 N개의 HLL 값들에 걸쳐 존재하는 최대값을 취하기만 하면 된다. 특정 요소는 항상 같은 레지스터에 같은 0 연속 길이로 해시되므로, 이런 방식으로 수행된 병합은 서로 다른 HLL들에 공통되지 않은 요소들의 개수만 더하게 된다.

볼 수 있듯이 HyperLogLog는 완전히 병렬화할 수 있다. 집합을 N개의 부분 집합으로 나누어 독립적으로 센 뒤 나중에 값을 병합해 전체 카디널리티 근사치를 얻을 수 있기 때문이다. Redis에서 HLL이 단지 문자열이라는 점은 인스턴스 간에 HLL 값을 이동시키는 데 도움이 된다.

먼저 정확하게 만들고, 그 다음 빠르게 만들자
===

Redis HLL은 6비트 정수에 패킹된 16k개의 레지스터로 구성된다. 이는 깊게 고민하지 않고도 호출할 수 있는 명령어 API를 제공하기 위해 해결해야 할 여러 성능 문제를 야기한다.

한 가지 문제는 레지스터에 접근하려면 올바른 6비트 값을 가져오기 위해 여러 바이트에 접근하고 시프트와 마스킹을 해야 한다는 점이다. 이는 요소마다 하나의 레지스터에만 접근하는 PFADD에는 큰 문제가 되지 않지만, PFCOUNT는 16k개의 레지스터 전체를 이용해 계산을 수행해야 하므로 각 레지스터에 접근하는 데 적지 않은 고정 시간이 든다면 명령이 느려질 위험이 있다. 게다가 레지스터에 접근하는 동안 부동소수점 연산이 필요한 pow(2,-register)의 합을 계산해야 한다.

계산을 빠르게 하기 위해 6비트 정수 대신 전체 바이트를 사용하고 싶은 유혹을 느낄 수도 있지만, 그렇게 하면 HLL 하나당 12k 대신 16k를 사용하게 되어 차이가 적지 않으므로 이 방법은 처음부터 배제되었다. 명령은 초기 구현에 비해 약 3배의 속도 향상을 위해 다음과 같은 변경을 통해 최적화되었다:

* m=16k인 경우, 즉 Redis 기본값인 경우(구현은 더 범용적이며 이론적으로는 다른 값으로도 동작할 수 있다) 구현은 매번 16개의 레지스터에 접근하는 루프를 풀어낸 fast-path를 선택한다. 레지스터는 고정된 오프셋/시프트/마스크를 이용해 접근한다(다음 반복에서 12바이트씩 증가하는 포인터를 통해).
* 부동소수점 계산은 가능한 경우 여러 연산이 병렬로 수행될 수 있도록 수정되었다. 이는 단지 괄호를 추가하는 문제였다. 부동소수점 연산은 교환 법칙이 성립하지 않지만, 이 경우에는 정밀도 손실이 없었다.
* pow(2,-register) 항은 룩업 테이블에 미리 계산해 두었다.

위 변경으로 3배의 속도 향상을 달성한 뒤, 해당 명령은 빠른 하드웨어에서 초당 약 60k회 호출을 수행할 수 있었다. 하지만 이는 사용자 관점에서 개념적으로 유사한 SCARD 같은 명령으로 가능한 수십만 회 호출에는 여전히 한참 못 미친다.

근사 카디널리티 계산을 더 최적화하는 대신, 더 간단한 해결책이 있었다. 기본적으로 알고리즘의 출력은 어떤 레지스터가 변경될 때만 바뀐다. 하지만 위에서 이미 관찰했듯이 대부분의 PFADD 호출은 어떤 레지스터도 변경하지 않는다. 이는 기본적으로 마지막 출력을 캐시해 두고 레지스터가 변경될 때만 다시 계산하는 것이 가능하다는 의미다.

그래서 우리 자료구조는 리틀 엔디안 형식의 64비트 부호 없는 정수를 나타내는 8바이트 꼬리를 추가로 갖는다. 최상위 비트가 설정되어 있으면 미리 계산된 값이 오래된 것이므로 다시 계산해야 하고, 그렇지 않으면 PFCOUNT는 그대로 사용할 수 있다. PFADD는 어떤 레지스터가 수정될 때 “invalid cache” 비트를 켜기만 하면 된다.

이 변경 후에는 50개의 동시 클라이언트로 32개 요소의 파이프라인을 이용해 최대 속도로 요소를 추가하려고 시도하는 경우에도 PFCOUNT는 매우 작은 상수 시간을 갖는 다른 O(1) 명령만큼 잘 수행할 수 있었다.

다항 회귀를 이용한 편향 보정
===

실용적이기 위해 HLL 알고리즘은 어떤 카디널리티 범위에서든 동일하게 잘 동작해야 한다. 안타깝게도 알고리즘이 수행하는 원시 추정은 m*2.5 미만(약 m=16384일 때 40000개 요소)의 카디널리티에서는 그다지 좋지 않다. 이 범위에서는 알고리즘의 출력이 편향되거나 정확한 범위에 따라 더 큰 오차를 갖는 결과를 내기 때문이다.

원래 HLL 논문 [1]은 HLL 알고리즘 전반부에서 추정된 원시 카디널리티가 m*2.5보다 작을 때 Linear Counting [5]으로 전환할 것을 제안한다.

[5] http://dblab.kaist.ac.kr/Publication/pdf/ACM90_TODS_v15n2.pdf

Linear counting은 간단한 개념을 사용하는 다른 카디널리티 추정기다. N비트짜리 비트맵이 있다. 새로운 요소를 셀 때마다 해시하고, 그 해시를 이용해 비트맵 내부의 무작위 비트를 인덱싱해 1로 바꾼다. 비트맵에서 설정되지 않은 비트의 수는 다음 공식을 이용해 지금까지 몇 개의 요소를 추가했는지에 대한 아이디어를 제공한다:

    cardinality = m*log(m/ez);

여기서 ‘ez’는 0인 비트의 수이고 m은 비트맵의 전체 비트 수다.

Linear counting은 HyperLogLog에 비해 큰 카디널리티에서는 잘 동작하지 않지만 작은 카디널리티에서는 매우 잘 동작한다. HLL 레지스터는 부수 효과로 linear counting 비트맵으로도 동작하므로, 0인 레지스터 수를 세어 HLL이 잘 동작하지 않는 범위에 linear counting을 적용할 수 있다. 이는 레지스터를 업데이트할 때 실제로 가장 긴 0 연속 자체가 아니라 가장 긴 0 연속에 1을 더한 값을 사용하기 때문에 가능하다. 즉, 요소가 추가되어 한 번도 접근된 적 없는 레지스터를 가리키면 레지스터는 0에서 다른 값(최소 1)으로 바뀐다는 뜻이다.

Linear counting의 문제는 카디널리티가 커질수록 출력 오차가 커지므로 가능한 빨리 HLL로 전환해야 한다는 점이다. 하지만 2.5m에서 전환하면 HLL은 여전히 편향되어 있다. 다음 이미지에서는 동일한 카디널리티를 1000개의 서로 다른 집합으로 테스트했으며, 각 실행의 오차를 점으로 표시했다:



파란색 선은 오차의 평균이다. 볼 수 있듯이 linear counting이 사용되는 카디널리티 40k 이전까지는, 카디널리티가 커질수록 점들의 “빔”이 더 넓어진다(오차가 커진다). HLL 원시 추정치로 전환하면 오차는 더 작아지지만 편향이 존재한다. 알고리즘은 40k-80k 범위에서 카디널리티를 과대 추정한다.

Google 엔지니어들은 이 문제를 광범위하게 연구하여 편향을 보정했다 [2]. 그들의 해결책은 카디널리티 값과 그에 대응하는 편향에 대한 경험적 테이블을 만드는 것이었다. 수정된 알고리즘은 테이블과 보간을 사용해 주어진 범위에서 편향을 구하고 그에 따라 보정한다.

나는 다른 접근법을 사용했다. 편향이 무작위적인 것이 아니라 매우 매끄러운 곡선처럼 보인다는 것을 알 수 있으므로, 몇 개의 카디널리티-편향 샘플을 계산하고 다항 회귀를 수행해 곡선을 근사하는 다항식을 찾았다.

현재 나는 40960-72000 범위에서 보정하기 위해 4차 다항식을 사용하고 있으며, 편향 보정 후 결과는 다음과 같다:



두 알고리즘 사이의 전환 지점에서는 여전히 약간의 편향이 남아 있지만, 결과는 기본 HLL 알고리즘과 비교하면 꽤 만족스럽다. 다만 편향 곡선에 더 잘 맞는 곡선을 사용하는 것이 가능할 수도 있다. 나는 이를 더 깊이 조사할 시간이 없었다.

조사 과정에서 알아낸 점 하나를 언급할 가치가 있다. 편향 보정을 사용하지 않을 때, 적어도 m=16384인 경우 linear counting에서 원시 HLL 추정치로 전환하는 최적값은 [1]에서 언급된 2.5가 아니라 실제로는 3 근처라는 것이다. 3이라는 값은 편향과 오차를 모두 개선하기 때문이다. 3보다 큰 값은 편향을 개선할 것이고(값이 4이면 완전히 보정된다) 오차에는 나쁜 영향을 미친다.

원래 HLL 알고리즘은 2^32에 가까운 값에 대해서도 보정한다 [1][2]. 매우 큰 값에 접근하면 해시 함수의 충돌이 문제가 되기 시작하기 때문이다. 우리는 Google 엔지니어들이 제안하고 Redis 구현이 채택한 수정 사항 중 하나인 64비트 해시 함수와 6비트 카운터를 사용하므로 이러한 보정이 필요하지 않다.

향후 과제
===

직관적으로, 우리가 가진 추가 정보를 활용하면 linear counting을 사용할 때 알고리즘 출력의 오차를 개선할 수 있을 것 같다. 표준 linear counting 알고리즘에서 레지스터는 단지 1비트 폭이므로, 지금까지 요소가 이 비트에 해시되었는지 여부에 대한 두 가지 정보만 갖는다. 그럼에도 불구하고 처음 제안된 HLL 알고리즘 [1]과 Google에서 수정한 알고리즘 [2]은 linear counting으로 되돌아갈 때 여전히 0인 레지스터 수만을 알고리즘 입력으로 사용한다. 레지스터에 저장된 정보를 함께 사용하는 것이 출력을 개선할 수 있을지도 모른다.

예를 들어 표준 linear counting에서 10비트가 있다고 가정하면, 5개의 요소를 추가했는데 모두 우연히 같은 비트를 가리킬 수 있다. 이는 알고리즘이 바로잡을 방법이 없는 특수한 경우이며, 제공된 추정치는 실제 카디널리티보다 작을 가능성이 높다. 하지만 HLL에서 사용되는 linear counting 알고리즘에서는 유사한 상황에서 설정된 유일한 레지스터의 값이 여러 요소가 그곳에서 충돌했다는 힌트가 될 수 있어 출력 보정이 가능할 수도 있다.

결론
===

HyperLogLog는 놀라운 자료구조다. 며칠 안에 안정 버전으로 제공될 Redis 구현(Redis 2.8.9에 포함될 예정이다)이 이 도구를 많은 프로그래머에게 바로 사용할 수 있는 형태로 제공하기를 바란다.

HN 게시물은 여기에 있다: https://news.ycombinator.com/item?id=7506774