• HyperLogLogs 타입은 관계형 DB의 테이블 구조에서 Check 제약조건과 유사한 개념의 데이터 구조이다. 관계형 DB에서 Check 제약조건을 사용하는 이유는 해당 컬럼에 반드시 저장되어야 할 데이터 값 만을 저장할 수 있도록 제한을 가하는 것이다. Redis 에서도 동일하게 특정 필드 또는 엘리먼트에 저장되어야 할 데이터 값을 미리 생성하여 저장한 후 필요에 따라 연결(Link)하여 사용할 수 있는 데이터 타입이다.
• 데이터를 처리할 때는 pfadd, pfcount, pfmerge 명령어를 사용한다.

pfadd credit_type "Cash" "Credit Card" "Point" "Check" "Cash"
pfadd domestic_city "Seoul" "Busan" "Daejeon" "Gwangju" "Daegu" "Busan"
pfadd foreign_city "Los Angeles" "San Diego" "New York" "Washington"

pfcount credit_type
(integer) 4
pfcount domestic_city
(integer) 5
pfcount foreign_city
(integer) 4

pfmerge international_city domestic_city foreign_city
"OK"

pfcount international_city
(integer) 9

HyperLogLog는 2007년 Philippe Flajolet가 발표한 알고리즘입니다. HyperLogLog라는 이름은 이전 알고리즘인 Loglog Counting을 발전시켰기 때문에 Hyper를 붙친것입니다. (출처: redisgate http://redisgate.kr/redis/command/hyperloglog.php)

하루에 접속하는 사용자 수가 100만명이라고 하면, 100만명을 추려내기 위해 엄청난 크기의 데이터를 분석해서 정확히 100만명을 얻을 수도 있습니다. 정확한 값이 필요한 계산이라면 시간과 비용이 많이 들더라도 중복된 값을 제거하고 모두 카운팅을 해야 합니다.

하지만 저는 101만명인지 99만300명인지 이 정도 정확한 숫자는 필요없고, 어느정도 신뢰할 만한 범위의 100만이라는 숫자를 알고 싶습니다. 이렇게 어느정도 오차를 허용하는 카운팅을 할 때 메모리와 시간 비용을 획기적으로 줄일 수 있는 알고리즘이 HyperLogLog입니다. 카운팅에 필요한 리소스를 몇 천분의 일 정도로 줄이는 건 일도 아닙니다.

이 알고리즘의 핵심은 비트 패턴 분석을 기반으로 확률을 추정한다는 겁니다. 예를들어 8자리 2진수 00000000 ~ 11111111 중에 하나를 랜덤으로 받는다고 해보죠. 첫 숫자로 00110100을 받았습니다. 이렇게 반복해서 계속 숫자를 받습니다. 앞자리 1~2개 비트가 연속으로 0일 확률은 높지만 5개 이상 연속일 확률은 낮습니다. 5개 이상 연속된 0를 받았다는 건 그 희귀한 비트 패턴이 나올만큼 많은 수를 받았을 확률이 높습니다.

다른 예로 로또복권을 매주 사는 사람들에게 로또 5등에 당첨된 적이 몇 번이나 있는지 설문조사를 한다고 가정해 봅니다. 누군가의 계산에 의하면 5등 당첨확률은 약 1/44 라고 합니다.

당첨 횟수로 구매횟수를 추정할 수 있지 않을까요? 그런데 엄청나게 운좋은 사람들을 처음에 많이 만나서 실제로 사람들이 50개 밖에 안 샀는데 2000개 쯤 샀다고 잘못 추정할 수도 있습니다. 이런 문제점을 해결을 위해 사람들을 그룹으로 나눠서 평균을 분산시켜 계산합니다.

보다 자세한 내용은 https://d2.naver.com/helloworld/711301 를 참고하시면 많은 도움을 받으실 수 있습니다.

Redis에서 이 알고리즘을 사용하면 숫자가 백만이든 천만이든 상관없이 12kb의 용량만 사용하고 약 0.81% 오차로 근사값을 얻을 수 있습니다. 조회 속도는 물론 빠르고요. 하지만 데이터를 저장하지 않고 카운트하기만 합니다.