블룸 필터 (Bloom Filter)

어떤 값이 집합에 "있을 수도 있음 / 없음은 확실함"을 매우 빠르고 메모리 효율적으로 판단하기 위한 확률적 자료 구조이다.

1. 목적

• 존재 여부 검사를 빠르게 하기 위함
• 정확성보다 속도와 메모리 효율을 우선

대표적인 사용 목적

1. 캐시 Penetration 방지

• 존재 가능한 키만 Bloom Filter에 미리 등록
• 요청 키가 Bloom Filter에서 없음이면 Cache / DB 접근 자체를 차단
• 존재하지 않는 ID에 대한 반복 DB 조회 방지 및 봇·악성 트래픽 방어

2. 중복 요청 차단

• 이미 처리된 요청 ID를 Bloom Filter에 기록하여 요청이 다시 들어올 경우 "이미 처리됨"으로 간주
• 멱등성 보조 수단 및 결제, 메세지 발송 중복 방지 (정확성이 중요한 경우 단독 사용은 부적합)

3. 크롤러의 URL 중복 방문 방지

• 방문한 URL을 Bloom Filter에 저장
• 이미 방문했을 가능성이 있으면 스킵
• 메모리 절약 및 대규모 URL 집합 관리 가능

2. 핵심 특징

항목	설명
False Positive	있다고 나올 수 있음
False Negative	절대 발생하지 않음
삭제	기본 Bloom Filter는 삭제 불가
메모리	매우 적게 사용
시간복잡도	O(k) (k = 해시 함수 개수)

False Positive (거짓 양성) : 없는데 있다고 판단

False Negative (거짓 음성) : 있는데 없다고 판단

3. 구조

• 비트 배열 (bit array): 크기 m
• 해시 함수 k개: 서로 독립적인 해시 함수

4. 동작 방식

값 추가 (insert)

1. 값을 k개의 해시 함수에 넣음
2. 각각의 해시 결과는 비트 배열의 인덱스를 의미
3. 해당 인덱스의 비트를 1로 설정

값 조회 (lookup)

1. 값을 동일하게 k개의 해시 함수에 넣음
2. 나온 인덱스들의 비트 확인
3. 결과
   • 하나라도 0 → 없음을 의미 (절대 없음)
   • 전부 1 → 있을 수도 있음

5. 왜 False Positive가 생기는가

• 서로 다른 값들이 같은 비트 인덱스를 공유할 수 있음.
• 비트 배열이 점점 1로 채워질수록 새로운 값도 "있는 것처럼" 보일 확률 증가

하지만

• 한 번이라도 0이면 바로 "없음" 판단 가능
• 그래서 False Negative는 발생하지 않음

6. 장단점

장점

• 메모리 사용량이 매우 작음
• 속도가 빠름 (CPU 캐시 친화적)
• 대규모 트래픽에 적합

단점

• 100% 정확하지 않음
• 삭제 불가 (→ Counting Bloom Filter로 보완, 비트를 카운터로 바꿔 삭제 가능)
• 데이터가 많아질수록 정확도 저하

7. 무엇을 우선?

• n (들어갈 원소 수) 을 먼저 추정
• 목표 false positive (p) 를 결정
• 그에 맞춰 비트 배열 (m) 과 해시 함수 개수 (k) 를 설계

대략적으로:

• 최적 해시 개수는 k ≈ (m/n) * ln 2
• false positive는 대략 p ≈ (1 - e^{-kn/m})^k

8. 다른 효율화 방안

1. Counting Bloom Filter

• 비트를 카운터로 바꾸므로 삭제 가능
• 단점은 메모리를 더 사용

2. Scalable Bloom Filter

• n이 예상보다 커졌을 때 성능이 망가지는 문제 해결
• Bloom Filter를 하나 더 붙여가며 확장 (계층 구조)
• 과소설계 리스트를 완화시킴

3. Partitioned Bloom Filter

• 비트 배열을 k개의 구간으로 나누고 해시마다 구간을 고정
• 비트 분포가 더 균등해져 성능이 안정적일 수 있음

4. 해시 함수 최적화 (더블 해싱)

• 해시 2개로 k개를 파싱
• 빠르고 구현이 단순