일반적으로 말하자면 저는 무작위 알고리즘을 좋아합니다. 그중에서도 특히 좋아하는 알고리즘이 하나 있는데, 그 작동 방식을 이해한 후에도 프로그래머의 관점에서 여전히 마법처럼 느껴지기 때문입니다. 이 알고리즘은 시간이나 공간 측면에서 요구하는 것이 너무 적은데도 거의 비논리적으로 보이는 일을 해냅니다. 이 알고리즘은 HyperLogLog라고 하며, 오늘 Redis의 새로운 데이터 구조로 소개됩니다.

고유 항목 세기
===

일반적으로 고유한 항목을 센다는 것은, 예를 들어 오늘 웹사이트에 접속한 고유 IP 수나 사용자가 수행한 고유 검색 수를 센다는 것은 지금까지 만난 모든 고유 요소를 기억해야 합니다. 그래야 다음 요소가 이미 본 요소들의 집합에 있는지 확인하고, 새 요소가 이전에 본 적이 없는 경우에만 카운터를 증가시킬 수 있기 때문입니다.

이렇게 하면 세고 있는 집합의 카디널리티(항목 수)에 비례하는 메모리가 필요하며, 이는 흔히 완전히 감당할 수 없는 규모입니다.

무작위화를 사용하여 일정하고 작은 메모리만으로 집합의 고유 요소 수에 대한 근삿값을 제공하는 알고리즘 부류가 있습니다. 현재 알려진 최고의 알고리즘은 HyperLogLog로, Philippe Flajolet이 고안했습니다.

HyperLogLog는 아주 적은 메모리만으로도 집합의 카디널리티를 매우 잘 근사한다는 점에서 놀랍습니다. Redis 구현에서는 키당 12kbytes만 사용하여 0.81%의 표준 오차로 셀 수 있으며, 2^64개에 가까워지지 않는 한 셀 수 있는 항목 수에는 제한이 없습니다(이는 꽤 일어나기 어려운 일입니다).

이 알고리즘은 원래 논문 [1]에 문서화되어 있으며, 실용적인 구현과 변형은 2013년 Google의 논문 [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의 연속 길이로 설정된 각기 다른 레지스터 값을 관찰함으로써 HyperLogLog는 매우 좋은 근사 카디널리티를 제공할 수 있습니다.

Redis 구현
===

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

Redis 구현에서 사용하는 해시 함수는 64비트 출력을 가지며, 16k 레지스터를 주소 지정하기 위해 해시 출력의 14비트를 사용하므로 50비트가 남습니다. 따라서 마주칠 수 있는 최대 0의 연속 길이는 6비트 레지스터에 들어갑니다. 이 때문에 Redis HyperLogLog 값은 16k 레지스터에 단지 12k 바이트만 사용합니다.

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



빨간색과 초록색 선은 완전히 무관한 두 집합에 대한 서로 다른 두 실행입니다. 카디널리티가 증가함에 따라 오차가 어떻게 일관되는지 보여줍니다. 그러나 훨씬 더 작은 카디널리티에서는 훨씬 더 작은 오차를 얻을 수 있습니다.



초록색 선은 카디널리티 100까지의 단일 실행 오차를 보여주고, 빨간색 선은 100회 실행에서 발견된 최대 오차를 보여줍니다. 카디널리티가 수백까지인 경우 알고리즘은 오차가 매우 작거나 정확한 답을 제공할 가능성이 매우 높습니다. 이는 계산된 값을 사용자에게 보여줄 때 답이 올바른지 육안으로 확인할 수 있으므로 매우 유용합니다.

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

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

API
===

Redis 관점에서 HyperLogLog는 문자열일 뿐이며, 정확히 12k + 8바이트 길이입니다(정확히는 12296바이트). 모든 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

명령 접두사는 Philippe Flajolet을 기리기 위해 “PF”입니다 [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은 16k개의 레지스터로 구성되며, 각각 6비트 정수로 압축되어 있습니다. 이는 명령 API를 너무 생각하지 않고 호출할 수 있게 하려면 해결해야 할 몇 가지 성능 문제를 만듭니다.

한 가지 문제는 레지스터에 접근하려면 올바른 6비트 값을 얻기 위해 여러 바이트에 접근하고, 시프트하고, 마스킹해야 한다는 것입니다. 이는 요소마다 레지스터 하나만 건드리는 PFADD에게는 큰 문제가 아니지만, PFCOUNT는 16k 레지스터를 모두 사용하여 계산을 수행해야 하므로, 개별 레지스터 접근에 무시할 수 없는 상수 시간이 걸린다면 명령이 느려질 위험이 있습니다. 게다가 레지스터에 접근하면서 부동소수점 연산이 포함된 pow(2,-register)의 합을 계산해야 합니다.

계산 속도를 높이기 위해 6비트 정수 대신 전체 바이트를 사용하고 싶은 유혹이 들 수도 있습니다. 그러나 그러면 모든 HLL이 12k 대신 16k를 사용하게 되므로 무시할 수 없는 차이이며, 그래서 이 방법은 처음부터 폐기되었습니다. 다음 변경을 통해 초기 구현보다 약 3배 빨라지도록 명령을 최적화했습니다.

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

위 변경으로 얻은 3배 속도 향상으로 이 명령은 빠른 하드웨어에서 초당 약 6만 건의 호출을 수행할 수 있었습니다. 그러나 이는 사용자 관점에서 개념적으로 유사한 SCARD 같은 명령에서 가능한 수십만 건의 호출과는 아직 거리가 있습니다.

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

따라서 데이터 구조에는 리틀 엔디언 형식의 64비트 부호 없는 정수를 나타내는 8바이트의 추가 꼬리가 있습니다. 가장 중요한 비트가 설정되어 있으면 미리 계산된 값이 오래된 것이므로 다시 계산해야 하고, 그렇지 않으면 PFCOUNT는 그 값을 그대로 사용할 수 있습니다. PFADD는 일부 레지스터가 수정될 때 “잘못된 캐시” 비트를 켜기만 하면 됩니다.

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

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

HLL 알고리즘은 실용적이려면 어떤 카디널리티 범위에서도 동일하게 잘 작동해야 합니다. 불행히도 이 알고리즘이 수행하는 원시 추정은 m*2.5 미만(약 40000개 요소, m=16384일 때)의 카디널리티에 대해서는 그리 좋지 않습니다. 이 범위에서는 정확한 범위에 따라 편향된 결과 또는 더 큰 오차가 있는 결과를 출력하기 때문입니다.

원래 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]. 매우 큰 값에 가까워지면 해시 함수의 충돌이 문제가 되기 시작하기 때문입니다. 우리는 64비트 해시 함수와 6비트 카운터를 사용하므로 그러한 보정이 필요하지 않습니다. 이는 Google 엔지니어들이 제안하고 Redis 구현이 채택한 수정 사항 중 하나입니다.

향후 작업
===

직관적으로 볼 때, 우리가 가진 추가 정보를 활용하면 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