구글에서 회원가입을 할 때, 본인이 원하는 이메일을 입력하라고 할 때가 있다.
어떤 이메일이 좋을지 궁리하다, 비장의 한 수로 이메일을 입력해도 '이미 있는 이메일이라고 한다'
그러면 또 본인이 후순위로 둔 비장의 이메일 주소를 쓰고, 반복해서 마침내 내가 원하는 이메일을 찾아낸다.
근데 한번씩 궁금하다. 구글에서는 엄청나게 많은 데이터베이스를 가지고 있을텐데 어떻게 이렇게 빨리 아닌지 판별하는지
해답은 바로 '블룸 필터'에 있다.
이 블룸필터는 해시 함수를 이용한다
(해시 함수에 대해 간단히 말하면, 나눗셈이나 기타 정한 방법을 통해 숫자를 구하고 나온 숫자를 DB에 넣는 방식이 바로 해시 함수다)
위의 그림에서 {x,y,z}가 있는데 이 x,y,z를 해시함수에 넣어 나온 값을 인덱스에 넣는다
이 과정에 어떤 인덱스에는 값이 중복이 될 수 있어도 신경쓰지 않는다.
이후에 내가 A를 넣는다고 가정하고, 해시 함수로 넣어서 이런 값이 나온다고 치자
0 1 0 1 1 0 0 0 0 0 0 0 ~
컴퓨터는 이후에 이걸 넣을 수 있을지 확신할 수가 없다. 이미 블룸필터를 통해서 앞에 1인 인덱스 위치가 동일하다고 보기 때문이다.
이런 구조의 장점은
1. 매우 빠르다
2. 데이터가 1억건, 2억건이 넘어도 빠르게 조회해 확인할 수 있기 때문에 메모리의 소모가 극단적으로 낮아진다.
3. 데이터 처리가 쉽다.
단점은
1. 데이터가 중복되기 때문에 값의 삽입만 가능하고, 값의 삭제는 불가능하다. 왜냐면 다른 중복된 데이터가 같은 위치의 인덱스가 없는 지 확신할 수 없다. 그렇기에 지웠다가 해시테이블이 망가질 수 있다.
2. 내가 찾는 게 정확하게 있을지 확신할 수 없다.
사실 정확하지 않는 건 시스템이건 프로그램이건 매우 큰 단점이지만
구글의 이메일을 설정하는데, 매우 정확할 필요는 없다. 어차피 사용자 입장에선 이게 있는지 없는지 확인하고, 이미 있다면 다른 아이디를 검색하는 게 싸게 먹힌다.
속도를 위해서 이런 구조를 생각할 수 있다는 게 대단하다.