블룸 필터(Bloom Filter)는 “이 값을 본 적이 있는가”라는 질문에 아주 적은 메모리로 답하는 확률적 자료구조다. 대용량 저장소 앞단에서 불필요한 디스크 조회를 걸러내는 데 쓰이기 때문에 분산 시스템과 데이터베이스 영역에서 자주 거론되며, 정보관리기술사 같은 서술형 시험에서 해시, 확률, 공간 효율의 트레이드오프를 한 번에 묻기 좋은 소재다.
블룸 필터는 “없음”은 확정하고 “있음”은 확률로만 답한다
블룸 필터는 m비트짜리 배열과 k개의 서로 독립적인 해시 함수로 구성된다. 원소를 넣을 때는 k개 해시값이 가리키는 비트를 모두 1로 만들고, 질의할 때는 그 k개 비트를 읽어 하나라도 0이면 “확실히 없음”, 전부 1이면 “있을 수도 있음”으로 판정한다. 핵심 키워드는 거짓 음성(false negative) 없음, 거짓 양성(false positive) 존재, 원소 삭제 불가(기본형)이다.
삽입과 질의는 같은 k개 비트 위치를 오간다
- 비트 배열 m개를 모두 0으로 초기화하고 해시 함수 k개를 정한다.
- 삽입: 원소 x에 대해 h1(x), …, hk(x) 위치의 비트를 1로 설정한다.
- 질의: 같은 k개 위치를 읽는다. 하나라도 0이면 미포함, 모두 1이면 포함 가능성이 있다.
- 모두 1이어도 다른 원소들이 우연히 그 비트를 채웠을 수 있어, 이때 거짓 양성이 생긴다.
거짓 양성률은 m, n, k 세 값이 함께 결정한다
| 구성요소 | 의미 | 값을 키우면 |
|---|---|---|
| m (비트 수) | 배열 크기 | 비트가 덜 겹쳐 거짓 양성 감소, 메모리 증가 |
| n (원소 수) | 삽입된 원소 개수 | 1인 비트 비율이 올라 거짓 양성 증가 |
| k (해시 수) | 원소당 설정 비트 수 | 처음엔 감소, 너무 크면 배열이 빨리 차 오히려 증가 |
거짓 양성률은 근사식 p ≈ (1 − e^(−kn/m))^k 로 표현한다. 이 식을 k에 대해 최소화하면 최적 해시 수 k = (m/n)·ln 2 가 나오고, 이때 배열의 약 절반이 1이 된다. 목표 확률 p에서 필요한 크기는 m/n = −ln p / (ln 2)^2, 즉 원소당 비트 수로 환산된다.
예시 계산: 원소 1,000개를 1만 비트에 넣으면 오탐은 약 0.8%다
n = 1,000, m = 10,000(원소당 10비트)이면 최적 k = 10 × 0.693 ≈ 6.93이므로 k = 7을 쓴다. 근사식에 대입하면 p ≈ (1 − e^(−0.7))^7 ≈ 0.0082, 약 0.82%다. 같은 m에서 k = 1이면 약 9.5%, k = 3이면 약 1.7%로 k를 늘릴수록 좋아지다가 k = 10에서는 약 1.0%로 다시 나빠진다(파이썬으로 검산). 정확식 (1 − (1 − 1/m)^(kn))^k 로 계산해도 0.0082로 같다. 거짓 양성률 1%를 목표로 하면 원소당 약 9.6비트(약 1.2바이트)가 필요하므로, 1억 개 키라면 약 120MB 수준이다. 키 자체를 저장하는 해시 집합과 비교하면 훨씬 작다.
변형 기법은 삭제, 확장, 공간 효율 중 무엇을 개선하느냐로 갈린다
| 기법 | 원리 | 장점 | 한계 |
|---|---|---|---|
| 표준 블룸 필터 | 비트 배열과 k개 해시 | 단순하고 매우 작음 | 삭제 불가, 원소 수 증가 시 오탐 증가 |
| 카운팅 블룸 필터 | 비트 대신 작은 카운터 사용 | 삭제 가능 | 메모리가 카운터 폭만큼 증가, 카운터 오버플로 주의 |
| 스케일러블 블룸 필터 | 가득 차면 더 엄격한 필터를 추가 | 원소 수를 몰라도 사용 가능 | 질의 시 여러 필터 확인, 구현 복잡 |
| 쿠쿠 필터 | 지문(fingerprint)을 버킷에 저장 | 삭제 지원, 낮은 오탐률 목표에서 공간 유리 | 삽입 실패(재배치 한계) 처리 필요 |
답안에서는 “어디에 쓰고 어디에 못 쓰는가”를 함께 적어야 한다
실무에서는 LSM 트리 기반 저장소(Bigtable 계열, Cassandra, HBase 등)가 SSTable 파일에 키가 없음을 먼저 확인해 디스크 읽기를 줄이는 데 블룸 필터를 쓴다. 크롤러의 중복 URL 검사, 캐시 앞단의 없는 키 조회 차단도 같은 발상이다. 반대로 거짓 양성을 허용할 수 없는 용도(결제, 권한 판정의 최종 근거)나 원소를 나열해야 하는 용도에는 맞지 않는다. 답안에는 정의, 동작 흐름, 오탐률 식과 최적 k, 변형 비교, 적용 사례와 한계를 순서대로 담고 그림 하나를 곁들이면 구성이 갖춰진다.
시험 직전 한 줄 요약
블룸 필터 = m비트 + k해시, “없음”은 확정, “있음”은 확률, 최적 k = (m/n)·ln 2, 오탐 1%에 원소당 약 9.6비트.
이 글은 학습용 정리이며 실제 시험 문항과 다를 수 있다. 출제 기준은 큐넷·KISA·한국데이터산업진흥원 등 공식 공지를 확인하라. 그림은 개념도 및 계산값 그래프로 실측 데이터가 아니다.