HyperLogLog Introduction

Redis Developer Course	Redis Technical Support	Redis Enterprise Server

소개

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입니다.
참고 자료

Philippe Flajolet가 2007년 발표한 논문 원본: HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm
Marianne Durand와 Philippe Flajolet가 2003년 발표한 논문 원본: Loglog Counting of Large Cardinalities
2013년 구글에서 HyperLogLog 실제 구현을 담은 논문 원본: HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm
살바토르(Salvatore)의 HyperLogLog 소개 글: Redis new data structure: the HyperLogLog
NEVER D2에 소개된 자료: 확률적 자료구조를 이용한 추정 - 유일한 원소 개수(Cardinality) 추정과 HyperLogLog
흥미로운 자료: Sketch of the Day: HyperLogLog — Cornerstone of a Big Data Infrastructure
Hacker News

Test Data

./redis-benchmark -p 6001 -r 100000 -n 1000000 pfadd hll __rand_int__
	-> 1000000 requests completed in 5.23 seconds
info memory -> used_memory: 583,520
memory usage hll 	-> 12,357

./redis-benchmark -p 6002 -r 100000 -n 1000000 sadd myset __rand_int__
	-> 1000000 requests completed in 8.64 seconds
info memory	-> used_memory: 6,068,480
memory usage myset samples 0	-> 4,848,493

./redis-benchmark -p 6001 -r 1000000 -n 10000000 pfadd hll __rand_int__
	-> 10000000 requests completed in 51.77 seconds
info memory -> used_memory: 583,520
memory usage hll 	-> 12,357

./redis-benchmark -p 6002 -r 1000000 -n 10000000 sadd myset __rand_int__
	-> 10000000 requests completed in 84.47 seconds
info memory	-> used_memory: 49,407,112
memory usage myset samples 0	-> 46,387,195

HyperLogLog 명령어 리스트
Commands	Version	Syntax	Description
PFADD	2.8.9	key ele [ele ...]	원소(element) 추가
PFCOUNT	2.8.9	key [key ...]	원소 개수 조회
PFMERGE	2.8.9	destkey sourcekey [sourcekey ...]	집합 머지(Merge)

Total : 3

<< SCRIPT DEBUG	HyperLogLog	PFADD >>

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

HyperLogLog Introduction

소개

HyperLogLog 명령어 리스트