Redis 블룸 필터 크기에 대한 알고리즘 공식은 무엇입니까?

1. 소개

클라이언트: 이 열쇠가 존재하나요?

서버: 존재하지 않음/모름

블룸 필터는 비교적 영리한 확률적 데이터 구조이며, 그 본질은 데이터 구조입니다. 효율적인 삽입 및 쿼리 기능을 제공합니다. 하지만 특정 구조에 키가 존재하는지 확인하고 싶을 때 Bloom 필터를 사용하면 "이 키는 존재하지 않아야 하거나 존재할 수 있다"는 사실을 빠르게 배울 수 있습니다. List, Set, Map과 같은 전통적인 데이터 구조에 비해 더 효율적이고 공간을 덜 차지하지만 반환되는 결과는 확률적이고 부정확합니다.

Bloom 필터는 컬렉션의 멤버십을 테스트하는 데에만 사용됩니다. 고전적인 Bloom 필터 예는 존재하지 않는 키에 대한 비용이 많이 드는 디스크(또는 네트워크) 조회를 줄여 효율성을 높이는 것입니다. 보시다시피 Bloom 필터는 O(k) 상수 시간에 키를 검색할 수 있습니다. 여기서 k는 해시 함수의 수이며 키가 존재하지 않는지 테스트하는 속도는 매우 빠릅니다.

2. 애플리케이션 시나리오

2.1 캐시 침투

액세스 효율성을 높이기 위해 Redis 캐시에 일부 데이터를 넣습니다. 데이터 쿼리를 수행할 때 데이터베이스를 읽지 않고 먼저 캐시에서 데이터를 가져올 수 있습니다. 이렇게 하면 성능이 효과적으로 향상될 수 있습니다.
데이터를 쿼리할 때는 먼저 캐시에 데이터가 있는지 확인해야 합니다. 데이터가 있으면 캐시에서 직접 데이터를 가져와야 합니다.
하지만 데이터가 없으면 데이터베이스에서 데이터를 가져와서 캐시에 넣어야 합니다. 많은 수의 액세스가 캐시에 도달하지 못하면 데이터베이스에 많은 부담을 주어 데이터베이스가 충돌하게 됩니다. Bloom 필터를 사용하면 존재하지 않는 캐시에 접근 시 빠르게 복귀하여 캐시나 DB 크래시를 피할 수 있습니다.

2.2 대용량 데이터에 특정 데이터가 있는지 확인

HBase에는 매우 많은 양의 데이터가 저장되어 있으며, 특정 ROWKEYS나 특정 컬럼이 존재하는지 확인하려면 Bloom 필터를 사용하면 특정 데이터가 있는지 빠르게 확인할 수 있습니다. . 그러나 특정 오판 비율이 있습니다. 그러나 키가 존재하지 않는 경우에는 정확해야 합니다.

3. HashMap 문제

요소가 존재하는지 확인하려면 HashMap을 사용하는 것이 매우 효율적입니다. HashMap은 값을 HashMap 키에 매핑하여 O(1) 일정한 시간 복잡도를 달성할 수 있습니다.
그러나 저장되는 데이터의 양이 매우 클 경우(예: 수억 개의 데이터) HashMap은 매우 많은 양의 메모리를 소비하게 됩니다. 그리고 한 번에 엄청난 양의 데이터를 메모리로 읽는 것은 불가능합니다.

4. Bloom 필터의 작동 원리 다이어그램 이해하기

:

Bloom 필터는 비트 배열 또는 비트 이진 벡터입니다.
이 배열의 요소는 0 또는 1입니다.
k 해시 함수는 다음과 같습니다. 서로 독립적이며, 각 해시 함수의 계산 결과는 배열의 길이 m의 모듈로이고, 각각의 비트는 1(파란색 셀)로 설정됩니다.
각 키를 설정합니다. 모든 셀은 이렇게 설정됩니다.

5. Bloom 필터에 따른 요소 쿼리

키를 입력한다고 가정하면 이전 k 해시 함수를 사용하여 해시를 찾고 k 값을 얻습니다
k 값이 모두인지 확인 파란색 중 하나라도 파란색이 아니면 키가 존재하지 않는 것입니다.
모두 파란색이면 키가 존재할 수 있습니다. (블룸 필터로 인해 오판이 발생할 수 있습니다.)
입력 개체가 많고 상대적으로 컬렉션이 많은 경우 작으면 컬렉션의 대부분의 위치가 파란색으로 그려집니다. 그러면 특정 키가 파란색으로 확인되면 특정 위치가 파란색으로 설정되는 경우가 발생합니다. set
예:

6. 삭제할 수 있나요?

기존 Bloom 필터는 삭제 작업을 지원하지 않습니다. 그러나 Counting Bloom 필터라는 변형을 사용하여 요소 개수가 특정 임계값보다 절대적으로 작은지 여부를 테스트할 수 있으며 요소 삭제를 지원합니다. Counting Bloom Filter 기사의 원리와 구현은 매우 자세하게 작성되어 있으므로 자세히 읽을 수 있습니다.

7. 해시 함수 수와 블룸 필터 길이를 선택하는 방법

분명히 블룸 필터가 너무 작으면 모든 비트가 곧 1이 되며, 어떤 값이든 쿼리하면 "존재할 수 있음"이 반환됩니다. 필터링의 목적을 상실합니다. Bloom 필터의 길이가 길어질수록 거짓양성률은 감소합니다.

또한 해시 함수의 개수도 측정해야 합니다. 개수가 많을수록 블룸 필터 비트 위치가 1로 설정되는 속도가 빨라지고 블룸 필터의 효율성이 낮아지지만 너무 적으면 그러면 우리는 오경보율이 더 높아질 것입니다.

위 그림에서 알 수 있듯이 해시 함수 k의 개수를 늘리면 오류율 p가 크게 줄어듭니다.

걱정하지 마세요. 실제로 m과 k의 값을 확인해야 합니다. 내결함성 p와 요소 수 n을 지정하면 이러한 매개변수는 다음 공식을 사용하여 계산할 수 있습니다.

필터 크기 m, 해시 함수 k 수 및 삽입된 요소 수 n 비율 p에 대한 공식은 다음과 같습니다. 위의 내용을 바탕으로 비즈니스에 적합한 k 및 m 값을 선택하는 방법은 무엇입니까?
공식:

k는 해시 함수 수, m은 블룸 필터 길이, n은 삽입된 요소 수, p는 거짓양성률입니다.
이 공식을 도출하는 방법은 제가 Zhihu에 게시한 기사에 나와 있습니다. 관심이 없으시면 위의 공식만 기억하시면 됩니다.

여기서 또 다른 중요한 점을 언급하고 싶습니다. Bloom 필터를 사용하는 유일한 목적은 더 빠른 검색이므로 느린 해시 함수를 사용할 수는 없겠죠? 암호화 해시 함수(예: Sha-1, MD5)는 약간 느리기 때문에 블룸 필터에 적합하지 않습니다. 따라서 더 빠른 해시 함수 구현 중에서 더 나은 선택은 murmur, fnv 계열 해싱, Jenkins 해싱 및 HashMix입니다.

추가 애플리케이션 시나리오

주어진 예에서 이를 사용하여 사용자에게 취약한 비밀번호를 입력하면 경고할 수 있다는 것을 확인했습니다.
블룸 필터를 사용하면 사용자가 악성 웹사이트를 방문하는 것을 방지할 수 있습니다.
특정 이메일을 가진 사용자가 존재하는지 확인하기 위해 SQL 데이터베이스를 쿼리하는 대신 먼저 Bloom Bloom 필터를 사용하여 저렴한 조회 확인을 수행할 수 있습니다. 이메일이 존재하지 않는다면 괜찮습니다! 존재하는 경우 데이터베이스에 추가 쿼리를 수행해야 할 수도 있습니다. "이미 사용 중인 사용자 이름"을 검색하기 위해 동일한 작업을 수행할 수도 있습니다.
웹사이트 방문자의 IP 주소를 기반으로 Bloom 필터를 유지하여 웹사이트 사용자가 "재사용자"인지 "신규 사용자"인지 확인할 수 있습니다. "재사용자"의 몇 가지 오탐은 당신에게 해를 끼칠 수 없습니다. 그렇죠?
블룸 필터를 사용하여 사전 단어를 추적하여 맞춤법 검사를 할 수도 있습니다.

위 내용은 Redis 블룸 필터 크기에 대한 알고리즘 공식은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!