Redis 의 부 릉 필터 구현

"부 릉 필터"가 무엇 입 니까?
부 릉 필 터 는 하나의 요소 가 집합 에 있 는 지 여 부 를 판단 할 수 있 는 신기 한 데이터 구조 이다.자주 사용 하 는 기능 중 하 나 는 무 거 운 것 을 없 애 는 것 이다.파충류 에서 흔히 볼 수 있 는 수요:목표 사이트 URL 천만,어떤 URL 파충류 가 총애 한 적 이 있 는 지 어떻게 판단 합 니까?간단하게 파충류 가 URL 을 채집 할 때마다 이 URL 을 데이터베이스 에 저장 하고 새로운 URL 이 올 때마다 데이터베이스 에 방문 한 적 이 있 는 지 확인 할 수 있다.

select id from table where url = 'https://jaychen.cc'

그러나 파충류 가 지나 가 는 URL 이 많아 지면 서 요청 할 때마다 데이터 베 이 스 를 한 번 씩 방문 해 야 하 며 이 문자열 에 대한 SQL 조회 효율 은 높 지 않다.데이터 베 이 스 를 제외 하고 Redis 의 set 구 조 를 사용 하면 이 수 요 를 만족 시 킬 수 있 고 성능 이 데이터베이스 보다 우수 하 다.그러나 레 디 스 도 메모리 소모 가 너무 많다 는 문제 가 있다.이때 부 릉 필 터 는 가로로 등장 했다.이 문 제 는 내 가 할 게.
데이터베이스 와 Redis 에 비해 부 릉 필 터 를 사용 하면 성능 과 메모리 점용 문 제 를 잘 피 할 수 있 습 니 다.
부 릉 필 터 는 본질 적 으로 하나의 비트 배열 이 고 비트 그룹 은 배열 의 모든 요소 가 1 bit 만 차지한다.모든 원 소 는 0 이나 1 만 있 을 수 있다.이렇게 10000 개의 요 소 를 신청 하 는 자릿수 그룹 은 10000/8=1250 B 의 공간 만 차지한다.부 릉 필 터 는 한 개의 배열 을 제외 하고 K 개의 해시 함수 도 있다.하나의 요소 가 부 릉 필터 에 들 어 갈 때 다음 과 같은 작업 을 합 니 다.

은 K 개의 해시 함 수 를 사용 하여 원소 값 을 K 회 계산 하여 K 개의 해시 값 을 얻 었 다.

에서 얻 은 해시 값 에 따라 재위 배열 에서 아래 표 시 된 값 을 1 로 설정 합 니 다.

...을 들다🌰，부 릉 필터 에 3 개의 해시 함수 가 있다 고 가정 합 니 다.f1,f2,f3 와 한 비트 배열 arr.현재 https://jaychen.cc 을 부 릉 필터 에 삽입 하려 고 합 니 다.

의 값 을 세 번 해시 계산 하여 세 개의 값 n1,n2,n3 를 얻 었 다.

은 자릿수 그룹 에서 세 개의 요소 인 arr[n1],arr[n2],arr[3]를 1 로 설정 합 니 다.

하나의 값 이 부 릉 필터 에 있 는 지 여 부 를 판단 하려 면 요 소 를 다시 해시 로 계산 하고 값 을 얻 은 후에 자릿수 그룹의 모든 요소 가 1 인지 여 부 를 판단 합 니 다.만약 값 이 1 이 라면 이 값 이 부 릉 필터 에 있 음 을 설명 합 니 다.만약 에 하나의 값 이 1 이 아니라면 이 요 소 는 부 릉 필터 에 없 음 을 설명 합 니 다.
글 자 를 못 읽 겠 어 요.아래 영혼 을 보고 손 그림 을 그 려 서 설명 하 세 요.👇👇👇

위의 설명 을 보면 반드시 문 제 를 제기 할 것 이다.삽 입 된 요소 가 원래 많 을 수록 비트 그룹 에서 1 로 설 치 된 위치 가 많아 지고 부 릉 필터 에 없 는 요소 가 해시 계산 을 거 친 후에 얻 은 값 은 비트 그룹 에서 조회 하면 이런 위치 도 모두 1 로 설 치 될 수 있다.부 릉 필터 가 존재 하지 않 는 것 도 부 릉 필터 로 오 판 될 수 있다.그러나 부 릉 필터 가 부 릉 필터 에 요소 가 없다 고 판단 하면 이 값 은 부 릉 필터 에 있 지 않 을 것 이다.쉽게 말 하면:

부 릉 필 터 는 어떤 요소 가 있 으 면 오심 을 받 을 수 있다 고 말 했다.

부 릉 필 터 는 어떤 요소 가 없다 면 반드시 없다 고 말 했다.

이 부 릉 필터 의 결함 을 파충류 의 요구 에 넣 으 면 방문 하지 않 은 URL 이 방문 한 것 으로 오 판 될 수 있 지만 방문 한 URL 이 라면 방문 하지 않 은 것 으로 오 판 되 지 않 을 것 이다.
Redis 의 부 릉 필터
redis 는 4.0 버 전에 module 기능 을 추 가 했 습 니 다.부 릉 필 터 는 module 형식 으로 redis 에 추가 할 수 있 기 때문에 redis 4.0 이상 의 버 전 을 사용 하면 module 을 불 러 와 redis 의 부 릉 필 터 를 사용 할 수 있 습 니 다.그러나 이것 은 가장 쉬 운 방법 이 아니다.docker 를 사용 하면 redis 에서 부 릉 필 터 를 직접 체험 할 수 있다.

> docker run -d -p 6379:6379 --name bloomfilter redislabs/rebloom
> docker exec -it bloomfilter redis-cli

redis 부 릉 필 터 는 주로 두 명령 에 있 습 니 다.

bf.add 부 릉 필터 에 요 소 를 추가 합 니 다:bf.add urls https://jaychen.cc.

bf.exists 은 특정한 요소 가 필터 에 있 는 지 여 부 를 판단 합 니 다.bf.exists urls https://jaychen.cc.

위 에서 말 했 듯 이 부 릉 필터 에 오심 이 있 는 경우 redis 에서 두 개의 값 이 부 릉 필터 의 정확 도 를 결정 합 니 다.

error_rate :부 릉 필터 의 오류 율 을 허용 합 니 다.이 값 은 낮 을 수록 필터 의 자릿수 그룹의 크기 가 클 수록 사용 공간 도 큽 니 다.

initial_size :부 릉 필터 가 저장 할 수 있 는 요소 의 갯 수 는 실제 저 장 된 요소 의 갯 수가 이 값 을 초과 하면 필터 의 정확도 가 떨어진다.

redis 에서 이 두 값 을 설정 할 수 있 는 명령 이 있 습 니 다:

bf.reserve urls 0.01 100

세 개의 매개 변수의 의미:

첫 번 째 값 은 필터 의 이름 입 니 다.

두 번 째 값 은 error_rate 의 값 이다.

세 번 째 값 은 initial_size 의 값 이다.

이 명령 을 사용 하려 면 주의해 야 합 니 다.이 명령 을 실행 하기 전에 필터 의 이름 이 존재 하지 않 을 것 입 니 다.실행 하기 전에 오류 가 발생 할 수 있 습 니 다:(error) ERR item exists 이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.