HyperLogLog를 사용하여 Redis를 구현하는 방법

1. 개요

Redis는 카디널리티 통계에 사용되는 HyperLogLog 데이터 구조를 버전 2.8.9에 추가했습니다. 장점은 입력 요소 수가 매우 많을 때 카디널리티를 계산하는 데 필요한 공간이 상대적으로 작고 일반적으로 비교적 일정합니다.

Redis에서 각 HyperLogLog 키는 거의 2^64개 요소의 카디널리티를 계산하는 데 12KB의 메모리만 사용합니다. 이는 더 많은 요소가 포함된 컬렉션이 더 많은 메모리를 소비하는 카디널리티 계산과 뚜렷한 대조를 이룹니다. 그러나 HyperLogLog는 입력 요소를 기반으로 카디널리티만 계산하고 입력 요소 자체를 저장하지 않기 때문에 HyperLogLog는 입력의 개별 요소를 컬렉션처럼 반환할 수 없습니다.

2. 카디널리티란 무엇인가요?

예를 들어 데이터 세트가 {1, 3, 5, 7, 5, 7, 8}이면 이 데이터 세트의 카디널리티 세트는 {1, 3, 5,7입니다. , 8}, 카디널리티(반복되지 않는 요소)는 5입니다. 카디널리티 추정은 허용 가능한 오류 범위 내에서 카디널리티를 빠르게 계산하는 것입니다.

3. 명령

현재 HyperLogLog에서는 PFADD, PFCOUNT 및 PFMERGE 세 가지 명령만 지원됩니다. 먼저 하나씩 소개하겠습니다.

3.1 PFADD

가장 빠른 버전: 2.8.9. 시간 복잡도: O(1).

PFADD 명령은 HyperLogLog 데이터 구조에 요소(여러 요소 지정 가능)를 추가하고 첫 번째 매개변수 키로 지정된 키에 저장할 수 있습니다. 카디널리티 추정(평가된 요소 수)이 변경된 경우 1을 반환하고, 그렇지 않으면 0을 반환합니다. 즉, 명령 실행 후 카디널리티 추정이 변경되었는지 확인합니다. 지정된 키가 존재하지 않으면 빈 HyperLogLog 데이터 구조가 생성됩니다(즉, 지정된 문자열 길이와 인코딩을 가진 Redis 문자열). 요소 매개변수를 지정하지 않고 키만 지정하여 명령을 호출하는 것도 가능합니다. 키가 있으면 아무 것도 하지 않고 0을 반환합니다. 키가 없으면 새 HyperLogLog 데이터 노드가 생성되고 1이 반환됩니다. 기본적으로 요소를 저장하지 않고 새로운 HyperLogLog 데이터 구조를 생성합니다.

(1) 구문 형식:

PFADD key element [element ...]

(2) 반환 값:

정수, 하나 이상의 요소가 추가되면 1이 반환되고, 그렇지 않으면 0이 반환됩니다.

(3) 예:

127.0.0.1:6379> PFADD hll a b c d e f g
(integer) 1
127.0.0.1:6379> pfcount hll
(integer) 7

3.2 PFCOUNT

가장 빠른 버전: 2.8.9. 시간 복잡도: O(1) 상대적으로 큰 키가 여러 개인 경우 시간 복잡도는 O(N)입니다.

PFCOUNT 명령을 사용하여 HyperLogLog 예상 카디널리티 값(즉, 요소 ​​수)을 가져옵니다. 이 명령은 키가 없으면 0을 반환하고, 그렇지 않으면 키의 카디널리티 추정치를 반환합니다. 여러 키의 경우 여러 HyperLogLog를 임시 HyperLogLog로 병합하여 계산된 여러 HyperLogLog 통합에 대한 카디널리티 추정치가 반환됩니다. 최소한의 일관된 메모리 양을 사용하여 HyperLogLog는 컬렉션의 고유 요소 수를 계산할 수 있습니다. 각 HyperLogLog는 12K와 몇 바이트의 키 자체만 사용합니다.

(1) 구문 형식:

PFCOUNT key [key ...]

(2) 반환 값:

integer, 지정된 HyperLogLog의 카디널리티 추정치를 반환합니다. HyperLogLog가 여러 개인 경우 공용체의 카디널리티 추정치를 반환합니다.

(3) 예:

127.0.0.1:6379> PFADD hll foo bar zap
(integer) 1
127.0.0.1:6379> PFADD hll zap zap zap
(integer) 0
127.0.0.1:6379> PFADD hll foo bar
(integer) 0
127.0.0.1:6379> PFCOUNT hll
(integer) 3
127.0.0.1:6379> PFADD some-other-hll 1 2 3
(integer) 1
127.0.0.1:6379> PFCOUNT some-other-hll
(integer) 3
127.0.0.1:6379> PFCOUNT hll some-other-hll
(integer) 6

(4) 제한 사항:

HyperLogLog에서 반환된 결과는 정확하지 않으며 오류율은 약 0.81%입니다.

이 명령을 사용하면 HyperLogLog가 변경되고 8바이트를 사용하여 마지막으로 계산된 베이스를 저장합니다. 따라서 기술적으로 말하면 PFCOUNT는 쓰기 명령입니다.

(5) 성능 문제

집약적인 HyperLogLog를 처리하는 데 이론적으로 시간이 더 걸리더라도 PFCOUNT 명령은 키를 하나만 지정하면 여전히 높은 성능을 발휘합니다. 이는 PFCOUNT가 마지막 계산의 기준을 캐시하고 PFADD 명령이 대부분의 경우 레지스터를 업데이트하지 않기 때문에 이 기준이 항상 변경되지 않기 때문입니다. 따라서 초당 수백 건의 요청 효과를 얻을 수 있습니다.

PFCOUNT 명령을 사용하여 여러 키를 처리하면 HyperLogLog가 병합됩니다. 더 중요한 것은 계산된 통합 카디널리티를 캐시할 수 없다는 것입니다. 여러 키를 사용하는 경우 PFCOUNT를 실행하는 데 약간의 시간(보통 밀리초 정도)이 걸릴 수 있으므로 과도하게 사용하지 않는 것이 좋습니다.

이 명령의 단일 키와 다중 키 실행 의미가 다르며 성능도 다르다는 점에 유의해야 합니다. 다중 키 실행 의미 체계를 과도하게 사용하는 것은 권장되지 않습니다.

3.3 PFMERGE

가장 빠른 버전: 2.8.9. 시간 복잡도: O(N), N은 병합할 HyperLogLog의 수입니다.

PFMERGE 명령을 통해 여러 HyperLogLog를 하나의 HyperLogLog로 병합할 수 있습니다. 병합된 HyperLogLog의 카디널리티 추정치는 지정된 모든 HyperLogLog의 합집합을 취하여 계산됩니다. 계산된 결과는 지정된 키에 저장됩니다.

구문 형식:

PFMERGE destkey sourcekey [sourcekey ...]

반환 값:

반환 OK.

예:

127.0.0.1:6379> PFADD hll1 foo bar zap a
(integer) 1
127.0.0.1:6379> PFADD hll2 a b c foo
(integer) 1
127.0.0.1:6379> PFMERGE hll3 hll1 hll2
OK
127.0.0.1:6379> PFCOUNT hll3
(integer) 6

위 내용은 HyperLogLog를 사용하여 Redis를 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!