HyperLogLog Introduction

<< Pub/Sub Introduction PFADD >>

소개

HyperLogLog는 집합의 원소의 개수를 추정하는 방법으로 2014년 4월 22일 발표된 Redis 버전 2.8.9에 새로 추가되었습니다.   이 문서는 버전 4.0.9를 기준으로 작성했습니다.
  • 용도: 주로 매우 큰 데이터의 오차가 1% 이하의 근사치를 구할 때 사용합니다. 예를 들어, 어떤 검색 엔진의 하루 검색어 수를 계산할 때 사용할 수 있습니다. 메모리는 매우 적게 사용하고 오차는 적습니다.
  • 메모리 사용량: 가장 큰 장점은 매모리를 매우 적게 사용합니다.   Java HashSet이나 Redis Set을 사용할 경우 원소의 수에 따라 메모리를 사용합니다. 예를 들어, Redis Set에 1백만개의 숫자를 저장하면 4,848kb, 1천만개의 숫자를 저장하면 46,387kb를 사용하지만, Redis HyperLogLog를 사용하면 원소 개수와 상관없이 고정으로 12kb만 사용합니다. 이는 1백만개 숫자의 Set과 비교하면 단지 0.25% 만 사용하는 것입니다.
    Redis HyperLogLog에서는 16384개 레지스터를 사용하고 레지스터 당 6bits를 사용하므로 사용하는 메모리 량은 12kb입니다.   계산식: 16,384 * 6bits = 98,304bits / 8 = 12,288bytes
  • 원소 개수 추정 오차: HyperLogLog 오차는 1.04/SQRT(m)입니다. m은 레지스터(register) 개수로 Redis에서는 16384개를 사용하므로 오차는 0.81%입니다.
  • HyperLogLog는 2007년 Philippe Flajolet 발표한 알고리즘입니다. HyperLogLog라는 이름은 이전 알고리즘인 Loglog Counting을 발전시켰기 때문에 Hyper를 붙친것입니다.
  • 살바토르(Salvatore)는 Philippe Flajolet를 기리기 위해 HyperLogLog 관련 명령에 PF 접두어를 사용했습니다.
  • 저장(add) 속도: HyperLogLog와 Set의 저장 속도를 비교하기 위해 1백만개의 데이터를 PFADD와 SADD로 넣어습니다. PFADD는 5.23초, SADD는 8.64초로 PFADD가 약 1.6배 빨랐습니다.
  • 조회 속도: PFCOUNT와 SCARD 모두 O(1)입니다. Slowlog로 확인해 보았을 때 둘 다 4 microseconds가 걸렸습니다.
  • HyperLogLog 데이터는 별도 data structure를 사용하지 않고 String을 사용합니다. String 내부는 HyperLogLog data structure입니다.
  • 참고 자료
  • Test Data

HyperLogLog 명령어 리스트

CommandsVersionSyntaxDescription
PFADD2.8.9key ele [ele ...]원소(element) 추가
PFCOUNT2.8.9key [key ...]원소 개수 조회
PFMERGE2.8.9destkey sourcekey [sourcekey ...]집합 머지(Merge)

Total : 3


명령을 실습해 보시려면 여기를 클릭해서 Redis Web Client 를 실행하세요.


<< Pub/Sub Introduction HyperLogLog Introduction PFADD >>

질문하거나 댓글을 보려면 클릭하세요.  댓글수 :    조회수 :

Email 답글이 올라오면 이메일로 알려드리겠습니다.