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 데이터 유형도 제공한다는 사실을 발견했습니다.

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을 반환할 수 있습니다.

주어진 요소가 모든 요소에 포함된 경우 계산되면 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!