[Redis] HyperLogLog

[HyperLogLog란]

HyperLogLog(hll)은 간단히 말하면 중복제거된 값을 매우 적은비용과 매우 빠른 속도로 계산하는데 사용하는 확률적 자료구조이다.

대용량의 데이터에서 중복제거된 unique value을 계산하는데 의미가 있으며 적은 메모리로 정확하지는 않지만 최소한의 오차율을 통해 unique value를 계산한다.

예를들어 포털 사이트에 방문한 사람의 수를 구하는데 또는 포털 사이트에서 하루에 검색한 검색어의 수를 구하는데 사용된다.

물론 집합이나 다른 자료구조를 통해 구할 수 있겠지만 데이터의 크기가 커질수록 엄청난 시간복잡도가 요구될것이다.

 

메모리 기반의 Redis에서 unique value를 찾으려고 하면 용량이 커질수록 메모리는 한정적이기 때문에 한계가 있었다.

 

hll은 이러한 문제를 아주 적은 메모리와 아주 적은 오차율을 통해 해결한다고한다.

참고로 1.5KB의 메모리에는 실제 키를 저장하는데 사용된 메모리는 포함되지 않는다.

 

redis에서 hll은 별도의 자료구조를 사용하지 않으며 raw한 스트링을 사용하며 스트링은 hll자료구조로 이루어져있다고 한다.

또한 unique value를 저장하고있지 않으며 때문에 unique value들을 추가하면 value를 확인할 수 없다.

대용량의 디스크가 또한 필요하지 않다.

 

[HyperLogLog 사용법]

- PFADD 

시간복잡도 O(1)

IP라는 Key에 ip 원소들을 추가한다.

Key에 unique한 원소가 추가되었다면 1이 반환되고 unique하지 않다면 0이 반환된다.

unique하지 않을경우 아무일도 일어나지 않는다.

 

 

- PFCOUNT

시간복잡도 O(1)

IP라는 Key에 있는 원소의 수를 출력한다.

 

 

-PFMERGE

시간복잡도 O(N)

두개 이상의 Key를 하나로 병합한다.