구글 크롬 브라우저는 수억 개의 "악성 사이트 URL 목록"을 어떻게 메모리 부족 없이 초고속으로 검사할까요? 정답은 블룸 필터(Bloom Filter)에 있습니다.
블룸 필터는 원본 데이터를 통째로 저장하지 않고, 여러 개의 해시 함수(Hash Function)를 돌려서 아주 작은 '비트 배열(Bit Array)'에 점(1)만 찍어두는 방식입니다. 덕분에 수 기가바이트(GB)의 데이터를 고작 몇 메가바이트(MB)의 메모리만으로 압축하여 "이 데이터가 존재하는가?"를 빛의 속도로 알아낼 수 있습니다.
1. "절대 없음(100%)"과 "있을지도 모름(99%)"의 미학
블룸 필터는 메모리를 극한으로 아끼는 대신, 약간의 타협을 했습니다. 바로 "False Positive (오탐지)"입니다. 여러 데이터가 우연히 같은 비트 자리를 공유할 수 있기 때문입니다.
해시를 돌렸을 때 하나라도 0이 나온다면? 👉 100% 확실하게 없음! (DB를 조회할 필요도 없음)
해시를 돌렸을 때 모두 1이 나온다면? 👉 있을 확률이 매우 높음! (하지만 다른 데이터들이 우연히 찍어놓은 흔적일 수도 있음. 이때만 진짜 DB를 조회해봄)
2. 비트 배열(Bit Array)에 마킹되는 과정
💡 실무 지식: 레디스(Redis) 캐시 폭격(Cache Stampede) 방지
초당 수만 명이 접속하는 서비스에서, 악의적인 해커가 "존재하지도 않는 회원 ID"로 미친듯이 검색을 요청하면 어떻게 될까요?
캐시(Redis)에 데이터가 없으므로 모든 요청이 메인 DB로 직행하여 DB가 뻗어버립니다(Cache Penetration). 이때 메인 DB 앞단에 블룸 필터를 설치해 두면, "없는 회원"이라는 것을 블룸 필터가 0.0001초 만에 걸러내어 DB를 완벽하게 보호해 줍니다!
// 📂 BloomFilter.js (JavaScript)
// 해시 함수를 여러 개 사용하여 비트 배열(Bit Array)에 마킹합니다.
class BloomFilter {
constructor(size = 100) {
this.size = size;
this.bitArray = new Array(size).fill(0); // 0으로 초기화된 비트 배열
}
// 간단한 해시 함수 3개 (실무에서는 MurmurHash 등 빠르고 고른 해시 사용)
hash1(item) {
let hash = 0;
for (let i = 0; i < item.length; i++) hash += item.charCodeAt(i);
return hash % this.size;
}
hash2(item) {
let hash = 0;
for (let i = 0; i < item.length; i++) hash += (item.charCodeAt(i) * 7);
return hash % this.size;
}
hash3(item) {
let hash = 0;
for (let i = 0; i < item.length; i++) hash += (item.charCodeAt(i) * 13);
return hash % this.size;
}
// 🌟 데이터 삽입 (비트를 1로 마킹)
add(item) {
this.bitArray[this.hash1(item)] = 1;
this.bitArray[this.hash2(item)] = 1;
this.bitArray[this.hash3(item)] = 1;
}
// 🌟 데이터 존재 여부 확인
mightContain(item) {
// 세 개의 해시 결과 위치가 모두 1인지 확인합니다.
// 단 하나라도 0이라면 "절대 없음(100%)"을 확신할 수 있습니다.
return this.bitArray[this.hash1(item)] === 1 &&
this.bitArray[this.hash2(item)] === 1 &&
this.bitArray[this.hash3(item)] === 1;
}
}
// 🌐 테스트 실행
const filter = new BloomFilter(100);
filter.add("minstudio");
filter.add("youtube");
console.log("minstudio가 있나요?", filter.mightContain("minstudio")); // true
console.log("netflix가 있나요?", filter.mightContain("netflix")); // false (없음 확실!)