Bloom Filters¶
문제: "이 username이 존재하는가?"¶
방법 1: 직접 DB 조회¶
- 매번 데이터베이스에 쿼리를 보내야 함
- 느리다 (Slow)
방법 2: 캐시 (Cache) 사용¶
- 모든 username을 캐시에 저장
- 비효율적이고 메모리 소모가 큼 (Inefficient, memory)
방법 3: Bloom Filter 사용¶
- 해시 함수를 사용하여 비트 배열(bit array) 에서 빠르게 존재 여부 확인
- 메모리 효율이 매우 높음
Bloom Filter 동작 원리¶
구조¶
- 고정 크기의 비트 배열 (예: 64비트)
- 모든 비트가 0으로 초기화됨
사용자 생성 (쓰기)¶
사용자가 생성될 때 해시 함수를 적용하여 비트를 설정한다:
1단계: jack 등록
2단계: paul 등록
3단계: Tim 등록
4단계: Ali 등록
존재 여부 확인 (읽기)¶
"paul"이 존재하는가?
- 비트가 0이면: 확실히 존재하지 않음 (DB 조회 불필요) - 비트가 1이면: 아마도 존재함 → DB에서 확인 필요"jack"이 존재하는가?
- 하지만 63번 비트는 jack과 Tim 둘 다 사용 → False Positive 가능핵심 특성¶
False Positive (거짓 양성)¶
- Bloom Filter가 "존재할 수 있음"이라고 답했지만 실제로는 존재하지 않는 경우
- 해시 충돌 때문에 발생
- 예: Tim과 jack이 같은 해시값(63)을 가짐
False Negative 없음¶
- Bloom Filter가 "존재하지 않음"이라고 답하면 확실히 존재하지 않음
- 비트가 0이면 해당 값이 추가된 적이 없다는 것을 보장
정리¶
| 결과 | 의미 |
|---|---|
| 비트가 0 | 확실히 존재하지 않음 (DB 조회 불필요) |
| 비트가 1 | 아마도 존재함 (DB에서 확인 필요) |
장점과 단점¶
장점¶
- 매우 적은 메모리 사용 (비트 배열만 필요)
- O(1) 시간 복잡도로 조회
- 존재하지 않는 항목에 대한 불필요한 DB 조회를 제거
단점¶
- False Positive 발생 가능 (비트 배열이 클수록 확률 감소)
- 삭제 불가 (비트를 0으로 되돌리면 다른 항목에 영향)
- 비트 배열 크기와 해시 함수 수를 적절히 조정해야 함