[redis] 데이터 타입 - HLL

HyperLogLog(HLL)

- 큰 데이터 집합의 항목 개수를 매우 효율적으로 추정할 수 있는 확률적 데이터 구조(PF : Probalistic Fuction)

- Bloom Filter, Cuckoo Filter 등을 사용하는데 False Positive 발생을 허용하는 데이터 타입이다.

- 데이터가 존재하는지 확인하기 위해 사용되는 자료구조로 고정된 소량의 크기(12KB)를 갖음

 

1. 내부 동작 방식

1) 해싱: 입력된 요소는 해시 함수에 의해 해싱. 해시 함수는 요소를 균등하게 분포된 비트 스트링으로 변환

- "foo" -> 11010010101101000101010100111001...

2) 최대 앞자리 0의 개수 계산: 해시된 결과에서 최대 앞자리 0의 개수를 계산. 이를 통해 해당 해시 값이 얼마나 희귀한지를 측정. 매우 드문 값일수록 해시 값의 앞부분에 더 많은 0이 존재

- 예를 들어, 해시 값이 00001011...인 경우, 앞자리 0의 개수는 4

3) 해시 값을 여러 개의 레지스터로 분할

- 이 레지스터는 해시 값의 일부 비트를 사용하여 결정

- 예를 들어, 16개의 레지스터가 있다면 해시 값의 상위 4비트를 사용하여 어느 레지스터에 값을 기록할지 결정합니다.

: 해시 값: 11010010101101000101010100111001...
-> 레지스터 인덱스 (상위 4비트): 1101 (13번 레지스터 : 십진법으로 변환하면 13)

4) 레지스터에 최대 앞자리 0의 개수 기록

해시 값이 변경되면 레지스터는 해당 범위 내에서 최대 앞자리 0의 개수를 다시 기록.

예를 들어, 13번 레지스터의 현재 값이 5인데 새로운 해시 값의 앞자리 0의 개수가 6이면, 13번 레지스터는 6으로 업데이트

5) 로그-로그 카운팅

레지스터 값이 업데이트된 후, 전체 레지스터의 값을 기반으로 고유 항목 수를 추정. 이때 로그-로그 카운팅 기법을 사용

• 각 레지스터의 값은 해당 해시 값 범위 내에서 최대 앞자리 0의 개수
• 이 값들을 평균화하고 특정 수학적 변환(로그-로그 변환)을 통해 최종 카디널리티를 추정

 

2. 명령어 

PFADD key element [element ...]

HyperLogLog 데이터 구조에 하나 이상의 요소를 추가

• 사용 형식: PFADD key element [element ...]
  • key: HyperLogLog 데이터 구조의 키.
  • element: 추가할 요소(하나 이상).

PFADD myhll "foo" "bar" "zap"  # myhll에 "foo", "bar", "zap" 요소를 추가
PFADD myhll "zap" "zap" "zap"  # "zap" 요소를 여러 번 추가해도 고유 개수는 변화 없음

 

PFCOUNT key [key ...]

HyperLogLog 데이터 구조의 추정된 고유 요소의 개수를 반환

• 사용 형식: PFCOUNT key [key ...]
  • key: HyperLogLog 데이터 구조의 키(하나 이상).

 

PFADD myhll "foo" "bar" "zap"  # myhll에 요소 추가
PFCOUNT myhll                  # 결과: 3 (고유 요소의 개수)

 

PFMERGE destkey sourcekey [sourcekey ...]

여러 HyperLogLog 데이터 구조를 병합하여 하나의 HyperLogLog 데이터 구조로 생성

• 사용 형식: PFMERGE destkey sourcekey [sourcekey ...]
  • destkey: 병합된 결과를 저장할 키.
  • sourcekey: 병합할 HyperLogLog 데이터 구조의 키(하나 이상).

PFADD hll1 "foo" "bar"
PFADD hll2 "baz" "qux"
PFMERGE hll3 hll1 hll2 # hll1과 hll2를 병합하여 hll3에 저장
PFCOUNT hll3 # 결과: 4 (hll1과 hll2의 고유 요소 합계)

- PF는 데이터 스트림 처리(대용량 로그, 백업), 빅데이터 분석에서 활용 가능. 데이터 무결성이 보장되어야 하는 도메인에서는 신중한 고려가 필요.