[REDIS] HyperLogLog

• 정의

  • 집합의 카디널리티(고유한 요소의 수) 를 추정할 수 있는 확률형 자료구조

• 특징

  • 결과값에 일정 부분 오차가 발생가능함.
  • 카디널리티 계산시 추정 이라는 표현이 사용된다고함.

• 원리

  • 작동
    • 멤버의 값을 해싱 → bucket 단위로 분류한다.
      • 해시 값에 맞게 표시
      • 동일한 아이템이 추가되면 동일한 해시값을 가지기에 카디널리티를 일정하게 계산가능하다.
  • 해시 충돌
    • 해시 충돌이 발생하는 경우, HyperLogLog 는 정확하지 않은 카디널리티를 반환함.

• vs Set

  • Set
    • 중복 검사를 위해 실제 값을 메모리에 모두 저장함.
    • 만개의 아이템이 있으면 O(n) 만큼 저장공간이 증가
  • HyperLogLog
    • 상대적으로 적은 메모리로 카디널리티 계산가능
      • 실제값 저장하지 않아서, 모든 아이템을 전부 출력하는 경우 활용 하면 안된다.
      • 실제로 유실되는 값도 있음.. 해시충돌 떄문에.

• 실습

  

• 대량 insert SET 와 HyperLogLog 비교

  

  

  • SET 의 경우 40296 메모리 사용과 1000 개의 데이터를 가짐

    

    

  • HyperLogLog 의 경우 2608 바이트의 메모리만 사용한다.

    • 다만, 카운트는 부정확하다..