블룸 필터 — 램이 비쌀 때 쓰는 자료구조
이 토픽을 마치면
블룸 필터의 원리를 설명할 수 있고, "없다"는 확실하지만 "있다"는 가끔 틀리는 이유를 이해하게 됩니다.
문제: 사용자가 1억 명인데 아이디 중복 체크를 해야 합니다
회원가입할 때 아이디 중복 체크를 합니다. 사용자가 100명이면 DB에서 SELECT 한 번이면 됩니다. 근데 사용자가 1억 명이면?
매번 DB를 뒤지면 느립니다. 그렇다고 1억 개 아이디를 전부 메모리에 올려놓자니 램이 부족합니다. 아이디 하나당 평균 10바이트라 해도 1GB입니다.
블룸 필터는 이 1GB를 12MB로 줄여줍니다. 대신 조건이 하나 붙습니다.
원리: 해시 함수 + 비트 배열
블룸 필터는 0과 1만 저장하는 비트 배열입니다. 처음에는 전부 0입니다.
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]아이디 "alice"을 등록하면, 해시 함수 3개를 돌려서 위치 3개를 얻습니다:
hash_A("alice") → 2번
hash_B("alice") → 5번
hash_C("alice") → 8번
[0, 0, 1, 0, 0, 1, 0, 0, 1, 0]
↑ ↑ ↑아이디 "bob"도 등록합니다:
hash_A("bob") → 1번
hash_B("bob") → 5번 ← alice이랑 겹침
hash_C("bob") → 7번
[0, 1, 1, 0, 0, 1, 0, 1, 1, 0]이제 "charlie"가 가입하려고 합니다. 중복 체크:
hash_A("charlie") → 3번 → 0 → "없음 확정!"해시 결과 중 하나라도 0이면 절대 등록된 적 없습니다. DB를 볼 필요도 없이 즉시 "사용 가능"이라고 답할 수 있습니다.
함정: "있다"는 가끔 거짓말합니다
문제는 반대 경우입니다. "dave"를 체크했더니 세 위치가 전부 1이었습니다. "이미 있네!" 라고 판단했는데, 실제로는 alice과 bob이 등록되면서 우연히 같은 위치를 1로 만든 것일 수 있습니다.
이걸 False Positive(거짓 양성)이라고 합니다.
- "없다"고 하면 → 진짜 없음 (100% 확실)
- "있다"고 하면 → 아마 있는데 가끔 틀림 (확률적)
비트 배열이 클수록, 해시 함수가 많을수록 False Positive 확률이 낮아집니다. 실무에서는 1% 이하로 유지합니다.
어디서 쓰이나
"가끔 틀리는" 자료구조가 쓸모가 있을까요? 놀랍게도 아주 많이 쓰입니다:
크롬 브라우저의 악성 URL 필터링 — 악성 사이트 목록을 블룸 필터로 저장합니다. 방문하려는 URL이 "없다"면 바로 통과, "있을 수도 있다"면 그때 서버에 진짜 확인합니다.
데이터베이스 쿼리 최적화 — SELECT 전에 "이 테이블에 이 값이 있을 가능성이 있나?"를 블룸 필터로 먼저 확인합니다. 없다고 확정되면 디스크를 읽지 않아도 됩니다.
회원가입 아이디 중복 체크 — 블룸 필터에서 "없음"이면 즉시 OK, "있을 수도"면 그때 DB를 조회합니다. DB 부하를 대폭 줄입니다.
핵심 패턴은 항상 같습니다: "없다"를 빠르게 확정해서 비싼 작업을 생략하는 것.
블룸 필터에 없는 기능
한 가지 주의할 점 — 블룸 필터는 삭제가 안 됩니다. 비트를 0으로 돌려놓으면 다른 항목이 같은 위치를 쓰고 있을 수 있어서 데이터가 깨집니다.
삭제가 필요한 경우에는 Counting Bloom Filter라는 변형을 씁니다. 비트 대신 카운터를 저장해서 "1 추가/1 감소"로 삭제를 구현합니다. 대신 메모리를 더 씁니다.
그리고 한번 넣은 데이터를 꺼낼 수도 없습니다. 블룸 필터는 "있냐 없냐"만 대답합니다. "뭐가 들어있냐"는 대답 못 합니다. 해시 함수를 거치면서 원래 데이터 정보가 사라지기 때문입니다.
정리하면 블룸 필터는 "이게 있나?"만 물어볼 수 있고, "뭐가 있나?"나 "이거 빼줘"는 못 하는 구조입니다. 이 제약을 알고 쓰면 메모리를 극적으로 아끼는 도구가 되고, 모르고 쓰면 버그의 원인이 됩니다.
핵심
블룸 필터는 "없다"는 확실하고 "있다"는 가끔 틀리는 확률적 자료구조입니다. 해시 함수로 비트 배열에 표시하는 원리이며, 메모리를 극적으로 아낍니다. 용도는 항상 같습니다 — 빠르게 "없음"을 확정해서 비싼 작업을 건너뛰기.