홍라이프 계산기블룸 필터 계산기 쉽게 이해하기 — 개념과 원리
블룸 필터는 어떤 항목을 본 적이 있는지 묻는 질문에 '확실히 없음' 또는 '아마 있음'으로 답하는 작은 비트 배열입니다. 거짓 음성은 절대 없지만 거짓 양성은 생길 수 있습니다. 이 계산기는 예상 항목 수와 허용할 거짓 양성률을 넣으면 필요한 비트 수, 메모리, 최적 해시 함수 개수, 항목당 비트 수를 알려 줍니다.
계산 방법
- 비트 수: m = −n · ln p ÷ (ln 2)²(올림)
- 해시 함수 개수: k = (m ÷ n) · ln 2(반올림)
- 메모리: m ÷ 8 ÷ 1,048,576 MiB
- 항목당 비트: m ÷ n
n은 예상 항목 수, p는 목표 거짓 양성률을 소수로 나타낸 값(1% = 0.01)입니다.
원리
항목을 넣을 때 해시 함수 k개가 고른 비트 k개를 1로 만듭니다. 조회할 때 같은 k개 비트 중 하나라도 0이면 넣은 적이 없는 항목입니다. 항목 n개를 넣은 뒤 특정 비트가 여전히 0일 확률은 약 e^(−kn/m)이므로 거짓 양성률은 p ≈ (1 − e^(−kn/m))ᵏ입니다. 이 값은 비트의 절반쯤이 1일 때 가장 작아지며, 그 조건이 k = (m/n) ln 2입니다. 이를 대입하면 p = (1/2)ᵏ와 위의 크기 공식이 나옵니다. 항목 자체의 크기와 상관없이, 거짓 양성률을 10분의 1로 줄일 때마다 항목당 약 4.8비트가 더 필요합니다.
예제 풀이
- 입력값: n = 1,000,000개, p = 1% = 0.01입니다.
- m = −1,000,000 × ln 0.01 ÷ (ln 2)² = 1,000,000 × 4.6052 ÷ 0.48045 ≈ 9,585,058.4이므로 올려서 9,585,059비트입니다.
- 메모리: 9,585,059 ÷ 8 ÷ 1,048,576 ≈ 1.142628074 MiB입니다.
- k = 9.585059 × 0.6931 ≈ 6.64이므로 반올림해 7개입니다.
- 항목당 비트는 9.585059입니다.
| 예상 항목 수 n | 필요한 비트 수 m |
|---|---|
| 250,000 | 2,396,265 |
| 500,000 | 4,792,530 |
| 750,000 | 7,188,794 |
| 1e+06 | 9,585,059 |
| 1.25e+06 | 11,981,323 |
| 1.5e+06 | 14,377,588 |
| 2e+06 | 19,170,117 |
결과 해석
항목당 약 9.6비트면 1%, 14.4비트면 0.1%, 19.2비트면 0.01%의 거짓 양성률을 얻습니다. 계획보다 많은 항목을 넣으면 거짓 양성률이 빠르게 오르므로 최대 항목 수 기준으로 잡아야 합니다. 데이터베이스나 저장 엔진은 확실히 없는 키에 대해 디스크 읽기를 건너뛰는 데 블룸 필터를 쓰며, 1%라면 없는 키 100번 조회에 쓸데없는 읽기가 약 한 번 생긴다는 뜻입니다.
흔한 실수
- 백분율 칸에 0.01을 넣는 경우입니다. 1%는 1로 입력합니다.
- 항목을 삭제할 수 있다고 기대하는 경우입니다. 일반 블룸 필터는 삭제하면 거짓 음성이 생길 수 있습니다.
- 느린 해시 함수를 k개 따로 쓰는 경우입니다. 좋은 해시 두 개를 h₁ + i·h₂로 조합하면 대개 충분합니다.
자주 묻는 질문
항목 크기가 메모리에 영향을 주나요?
아닙니다. 항목당 비트 수만 중요하므로 긴 URL이든 짧은 ID든 필터 크기는 같습니다.
해시 함수 개수를 왜 정수로 반올림하나요?
해시 함수를 소수 개만큼 쓸 수 없고, 최적값 근처에서는 오차율이 거의 변하지 않기 때문입니다.
없는 항목을 있다고 할 수도 있나요?
네, 그것이 거짓 양성입니다. 넣은 항목을 없다고 하는 일은 없습니다.
출처: B. H. Bloom, "Space/time trade-offs in hash coding with allowable errors", Communications of the ACM 13(7), 1970 · A. Broder, M. Mitzenmacher, "Network applications of Bloom filters: a survey", Internet Mathematics 1(4), 2004