Redis 데이터 유형 학습을 위한 HyperLogLog에 대한 간략한 분석

이 기사에서는 일반적으로 컬렉션의 고유 요소 수를 계산하는 데 사용되는 Redis 데이터 유형의 HyperLogLog를 이해하는 데 도움이 되기를 바랍니다.

오늘은 금요일입니다. 즐겁게 낚시를 하고 계시는데, 제품 관리자가 이메일로 요구사항 문서를 보내드립니다. 요구 사항은 아마도 다음과 같습니다. 회사는 웹 사이트의 일일 방문자 IP를 계산해야 하며 이 통계는 몇 달에서 몇 년에 이르는 장기적인 동작입니다.

요구 사항을 읽고 나면 이 기능을 Redis의 수집 유형을 사용하여 쉽게 구현할 수 있습니다. 매일 수집 유형 키를 생성하고 SADD를 사용하여 일일 방문자 IP를 저장하고 SCARD 명령을 사용하십시오. 일일 방문자 IP 수량을 쉽게 얻을 수 있습니다.

빠르게 코드 입력을 마치고 테스트를 통과하여 이 기능이 실행되었습니다. 온라인 상태로 잠시 실행한 후 Redis가 위치한 서버에서 알람이 울리기 시작하는 것을 발견할 수 있습니다. 그 이유는 일부 키의 메모리 사용량이 너무 크기 때문입니다. 살펴보니 이 키들은 모두 설정된 키입니다. 방문자 IP를 저장하는 것입니다. 그제서야 당신은 자신이 큰 구멍을 팠다는 것을 알고 머리를 쓰다듬었습니다.

IPv4 형식으로 IP 주소를 저장하려면 최대 15바이트가 필요하고 웹사이트의 일일 방문자 수는 최대 100만 명에 달한다고 가정해 보겠습니다. 이러한 설정된 키는 월별 0.45GB, 연간 5.4GB의 메모리를 사용합니다. 이는 IPv6 형식이 더 많은 메모리를 차지할 경우의 추정치일 뿐입니다. SADD 및 SCARD의 시간 복잡도는 O(1)이지만 메모리 소비는 허용되지 않습니다.

Redis의 공식 웹사이트를 검색한 결과 Redis가 제품 요구 사항을 충족할 뿐만 아니라 메모리를 덜 차지하는 HyperLogLog 데이터 유형도 제공한다는 사실을 발견했습니다. [관련 권장 사항: Redis 동영상 튜토리얼]

HyperLogLog 알고리즘

HyperLogLog은 집합의 카디널리티를 계산하기 위해 특별히 만들어진 확률적 알고리즘으로, 주어진 집합의 대략적인 카디널리티를 계산할 수 있습니다.

대략적인 카디널리티는 집합의 실제 카디널리티가 아니며 실제 카디널리티보다 약간 작을 수도 있고 클 수도 있지만, 그렇지 않은 통계의 경우 추정 카디널리티와 실제 카디널리티 사이의 오차는 합리적인 범위 내에 있습니다. 매우 정확해야 합니다. HyperLogLog 알고리즘을 사용할 수 있습니다.

HyperLogLog의 장점은 대략적인 카디널리티를 계산하는 데 필요한 메모리가 세트의 크기로 인해 변경되지 않는다는 것입니다. 세트에 포함된 요소 수에 관계없이 HyperLogLog가 계산하는 데 필요한 메모리는 항상 고정되어 있으며 매우 작습니다. .

Redis는 거의 2⁶⁴ 요소를 계산하는 데 HyperLogLog 유형당 12KB의 메모리 공간만 필요하며 알고리즘의 표준 오류는 0.81%에 불과합니다.

HyperLogLog 유형을 사용하여 위 기능을 구현하면 하루 방문자가 100만 명이라면 한 달에 360KB의 메모리만 차지하게 됩니다.

PFADD

PFADD 명령은 하나 이상의 지정된 집합 요소를 계산할 수 있습니다.

PFADD 키 요소 [요소...]PFADD key element [element...]

根据给定的元素是否已经进行过计数，PFADD 命令可能返回 0，也可能返回 1：

• 如果给定的所有元素都已经进行过计数，那么 PFADD 命令将返回 0，表示 HyperLogLog 计算出的近似基数没有发生变化。
• 如果给定的元素中出现了至少一个之前没有进行过计数的元素，导致 HyperLogLog 计算出的近似基数发生了变化，那么 PFADD 命令将返回 1。

例如：

redis> PFADD letters a b c -- 第一次添加
(integer) 1
redis> PFADD letters a     -- 第二次添加
(integer) 0

如果在调用该命令时仅指定 key 而不指定元素也是可以的，如果 key 存在，则不会有任何操作，如果不存在，则会创建一个数据结构（返回 1）。

PFCOUNT

通过 PFCOUNT 命令可以获取 HyperLogLog 为集合计算出的近似基数。若给定的 key 不存在将返回 0。

PFCOUNT key [key...]

例如：

redis> PFCOUNT letters
(integer) 3

当向 PFCOUNT 传入多个 HyperLogLog 时，PFCOUNT 命令将先对所有的 HyperLogLog 求并集，然后返回近似基数。

redis> PFADD letters1 a b c
(integer) 1
redis> PFADD letters2 c d e
(integer) 1
redis> PFCOUNT letters1 letters2
(integer) 5

PFMERGE

PFMERGE 命令可以对多个 HyperLogLog 执行并集计算，然后把计算得出的并集 HyperLogLog 保存到指定的键中。

PFMERGE destKey sourceKey [sourceKey...]

주어진 요소가 계산되었는지 여부에 따라 PFADD 명령은 0 또는 1을 반환할 수 있습니다.

주어진 경우 have의 모든 요소 계산되면 PFADD 명령은 0을 반환하며 이는 HyperLogLog에서 계산된 대략적인 카디널리티가 변경되지 않았음을 나타냅니다.
이전에 계산되지 않은 특정 요소에 하나 이상의 요소가 존재하여 HyperLogLog에서 계산한 대략적인 카디널리티가 변경되는 경우 PFADD 명령은 1을 반환합니다.
• 예:

  redis> PFADD letters1 a b c
  (integer) 1
  redis> PFADD letters2 c d e
  (integer) 1
  redis> PFMERGE res letters1 letters2
  OK
  redis> PFCOUNT res
  (integer) 5

  이 명령을 호출할 때 요소를 지정하지 않고 키만 지정할 수도 있습니다. 키가 존재하지 않으면 데이터 구조가 수행되지 않습니다. 생성됩니다(반환 1).

• PFCOUNT

PFCOUNT 명령을 사용하여 해당 세트에 대해 HyperLogLog에서 계산한 대략적인 카디널리티를 가져옵니다. 주어진 키가 존재하지 않으면 0이 반환됩니다.

• PFCOUNT 키 [key...]

예:
• rrreee

  여러 HyperLogLog가 PFCOUNT에 전달되면 PFCOUNT 명령은 먼저 모든 HyperLogLog의 결합을 찾은 다음 대략적인 값을 반환합니다. 베이스 .

  rrreee

  🎜PFMERGE🎜🎜🎜PFMERGE 명령은 여러 HyperLogLog에 대해 통합 계산을 수행한 다음 계산된 통합 HyperLogLog를 지정된 키에 저장할 수 있습니다. 🎜🎜PFMERGE destKey sourceKey [sourceKey...]🎜🎜지정된 키가 이미 존재하는 경우 PFMERGE 명령은 기존 키를 덮어씁니다. 🎜rrreee🎜PFMERGE와 PFCOUNT 명령이 매우 유사하다는 것을 알 수 있습니다. 실제로 PFCOUNT 명령은 여러 HyperLogLog의 대략적인 카디널리티를 계산할 때 다음 작업을 수행합니다. 🎜🎜🎜🎜PFMERGE 명령은 내부적으로 호출되어 합집합을 계산합니다. 모두 주어진 HyperLogLogs를 사용하고 이 조합을 임시 HyperLogLog에 저장합니다. 🎜🎜🎜🎜임시 HyperLogLog에서 PFCOUNT 명령을 실행하여 대략적인 카디널리티를 가져옵니다. 🎜🎜🎜🎜임시 HyperLogLog를 삭제하세요. 🎜🎜🎜🎜 결과 근사값을 반환합니다. 🎜

프로그램이 여러 HyperLogLog에서 PFCOUNT 명령을 호출해야 하고 이 호출이 여러 번 반복될 수 있는 경우 이 호출을 해당 PFMERGE 명령 호출로 대체하는 것을 고려할 수 있습니다. HyperLogLog에서 매번 Union을 생성하면 프로그램은 불필요한 Union 계산을 최소화할 수 있습니다.

비즈니스 시나리오

HyperLogLog의 기능은 계산(월별, 연간 통계), 중복 제거(스팸 SMS 감지) 및 기타 시나리오에 매우 적합합니다.

더 많은 프로그래밍 관련 지식을 보려면 프로그래밍 소개를 방문하세요! !

위 내용은 Redis 데이터 유형 학습을 위한 HyperLogLog에 대한 간략한 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!