블룸 필터가 '없음'만 확신하는 이유
블룸 필터가 '확실히 없음'과 '있을 수도 있음'으로만 답하는 이유, 거짓 음성이 없다는 보장이 성립하는 조건, 거짓 양성 확률 식, 비트를 지우면 보장이 깨지는 이유를 정리합니다.
블룸 필터는 “확실히 집합에 없다”와 “집합에 있을 수도 있다” 중 하나로 답합니다. Burton Bloom이 1970년에 제안한 구조로, 약간의 오답을 받아들이는 대신 공간을 크게 줄입니다.
구성은 모두 0인 m비트와 해시 함수 k개입니다. 원소를 넣으면 해시 값이 가리키는 k비트를 1로 켭니다. 조회할 때는 같은 k비트를 읽어 하나라도 0이면 “없음”이라고 답합니다.
거짓 음성이 없는 이유
넣은 원소의 k비트는 넣을 때 이미 1이 됐습니다. 표준 블룸 필터는 비트를 0으로 되돌리지 않고, 조회도 같은 방식으로 해시하므로 그 비트를 읽으면 모두 1입니다.
이 보장은 그 원소가 여전히 필터가 나타내는 집합의 구성원이고, 지워진 비트가 없으며, m, k와 해시 값에서 비트 위치로 가는 대응이 그대로일 때만 성립합니다. Python의 hash()는 기본 설정에서 문자열 해시에 실행마다 예측할 수 없는 무작위 값을 섞습니다. 이 값으로 위치를 정한 필터를 저장한 뒤 해시 시드가 다른 프로세스에서 읽으면, 같은 원소가 다른 비트를 가리켜 보장이 깨질 수 있습니다.
거짓 양성이 생기는 이유
넣지 않은 원소도 다른 원소들이 켠 비트 k개에 모두 걸릴 수 있습니다. 해시 값이 균등하고 서로 독립이며 원소가 n개라면 그 확률은 대략 f ≈ (1 − e^(−kn/m))^k이고, k = (ln 2)·m/n일 때 가장 작습니다. m = 8n이면 이 값은 약 5.5입니다. k = 6으로 두면
python3 -c "import math; print((1 - math.exp(-6/8))**6)"의 결과는 약 0.0216입니다.
삭제
한 원소의 비트를 0으로 바꾸면 다른 원소가 쓰던 비트까지 지워질 수 있고, 그러면 그 다른 원소가 “없음”으로 판정됩니다. 카운팅 블룸 필터는 비트 대신 작은 카운터를 두어 넣을 때 올리고 지울 때 내립니다. 넘친 카운터를 최댓값에 고정하는 경우에는 여전히 거짓 음성이 생길 수 있습니다.
세부 동작은 구현마다 다릅니다. Redis는 필터가 용량에 이르면 기본 설정에서 하위 필터를 추가합니다.