사용자 가입 페이지에서 사용자 이름이 주어지면 이미 등록되었는지 어떻게 알 수 있습니까?

인덱싱된 데이터베이스를 쿼리하면 도움이 되지만 속도가 느리고 네트워크 호출이 발생합니다.

작업 속도를 높이기 위해 Redis와 같은 키-값 저장소에 등록된 사용자 이름 목록을 캐시할 수 있습니다.

그러나 이는 수백만 개의 레코드를 캐싱하고 메모리 공간을 두 배로 늘리는 것을 의미합니다.

사소해 보이는 이 문제에서 우리는 어떻게 더 잘할 수 있습니까?

블룸 필터가 답일 수 있습니다. 확인해 봅시다!

블룸 필터란 무엇입니까?

블룸 필터는 하나의 간단한 질문에 답합니다.

주어진 세트에 요소가 존재합니까?

블룸 필터는 확률적 데이터 구조입니다. 위의 질문이 주어지면 다음 답변 중 하나를 출력합니다.

• 아마 예
• 100% 아니요

그리고 가장 큰 장점은 일정한 시간과 공간에서 이를 수행한다는 것 입니다 .

어떻게 작동합니까?

블룸 필터는 두 가지 구성 요소로 구성됩니다.

• N 크기 비트 배열
• 여러 해싱 함수

먼저 모든 비트가 0으로 설정된 N 크기 비트 배열로 초기화됩니다. 지금은 배열의 길이가 10이라고 가정해 봅시다.

항목 추가

항목 추가는 간단합니다.

• "호랑이"라는 항목은 해싱 함수를 사용하여 해싱됩니다.
• 생성된 해시는 제한된 인덱스를 얻기 위해 배열 길이로 변경됩니다.
• 그러면 비트 배열의 인덱스가 1로 설정됩니다.

항목을 추가하는 것과 유사하게 해싱 함수를 사용하여 요소를 해시하고 제한된 인덱스를 얻기 위해 수정합니다.

출력은 다음과 같이 평가됩니다.

• 비트 배열의 인덱스 값이 0이면 항목이 집합에 없습니다 .
• 그렇지 않으면 항목이 아마도 세트에 있을 것입니다.

블룸 필터 저장

블룸 필터를 배열로 저장하는 대신 비트 표현을 십진수로 변환할 수 있습니다.

예를 들어, 1001119를 포함하는 배열을 변환하여 캐시에 저장할 수 있습니다.

목록이 자주 변경되지 않는 경우 서버는 클라이언트 측에서 유효성 검사를 수행할 수 있도록 클라이언트에 10진수를 보낼 수 있습니다.

더 잘할 수 있을까요?

해싱 함수가 "tiger"와 "cow" 모두에 대해 인덱스 1을 출력하는 경우 집합에 "cow"가 있는지 확인하면 그렇지 않은 경우에도 Yes가 반환됩니다 .

다음 솔루션을 통해 오탐 가능성을 줄일 수 있습니다.

• 배열 길이 늘리기
• 해싱 함수의 수를 늘립니다.

하나의 인덱스 대신 여러 해시를 사용하여 여러 인덱스를 얻을 수 있습니다.

아이템 추가 시 획득한 인덱스는 모두 1로 설정됩니다.

모든 인덱스가 1로 설정된 경우에만 항목이 아마도 세트에 있다고 주장됩니다 .

이러한 방법을 활용하면 오탐 가능성을 크게 낮출 수 있습니다.

애플리케이션

몇 가지 실제 사례를 살펴보겠습니다.

사용자 가입 절차에 사용자 이름이 있는지 확인

• 사용자 이름이 생성되면 키-값 저장소에 저장된 블룸 필터에 사용자 이름이 추가됩니다.
• 사용자가 사용자 가입 페이지에서 사용자 이름을 입력하면 서버는 먼저 블룸 필터를 쿼리합니다.
• 사용자 이름이 블룸 필터에 없으면 서버는 즉시 클라이언트에 오류를 반환합니다.
• 그렇지 않으면 서버가 데이터베이스에서 쿼리하고 교차 확인합니다.

• 매체는 각 사용자에 대한 블룸 필터를 유지합니다.
• 기사를 추천하기 전에 미디엄은 사용자의 블룸 필터에 기사 ID가 있는지 확인합니다.
• 확실히 블룸 필터에 없는 기사는 사용자에게 권장됩니다.

• URL에 액세스할 때 Chrome은 먼저 URL이 악성 목록의 일부인지 확인합니다.
• 구글은 매번 구글 서버에 질의하는 대신 미리 정해진 악성 목록을 이용해 블룸 필터를 구축해 브라우저에 보낸다.
• 브라우저는 웹 사이트에 액세스하기 전에 URL을 해시하고 블룸 필터와 교차 확인합니다.

가양성 이 있을 수 있지만 블룸 필터는 항목이 확실히 목록에 없는지 알려줄 때 유용 합니다.

시간과 공간 모두에서 효율성으로 인해 필터링의 첫 번째 레이어로 사용할 수 있습니다.

도움이 되셨기를 바라며 다음 글에서 뵙겠습니다!