블룸 필터(Bloom filter)

잘난 척을 위한 한 줄 요약

블룸 필터는 “정확히 저장”하는 대신 “아마 있을 수도 있음 / 절대 없음”만 엄청 빠르고 가볍게 판별하는 확률형 자료구조다.

 

블룸 필터, 왜 컴퓨터는 가끔 “있을 수도 있고 없을 수도 있다”는 방식으로 더 똑똑해질까

블룸 필터란 무엇일까?

블룸 필터(Bloom filter)는 어떤 데이터가 집합에 들어 있는지 확인할 때 쓰는 확률적 자료구조다. 1970년 Burton H. Bloom이 제안했고, 핵심 특징은 아주 선명하다. “없다”는 거의 확실하게 말할 수 있지만, “있다”는 100% 확실하게 말하지는 못한다. 다시 말해, 조회 결과가 “있다”면 실제로는 없는데도 있다고 판단하는 거짓 양성(false positive) 은 발생할 수 있지만, “없다”면 진짜 없는 것으로 본다.

 

처음 들으면 좀 이상하다. 자료구조라면 정확해야 할 것 같은데, 왜 일부러 이런 애매한 구조를 쓰는 걸까? 이유는 단순하다. 메모리를 엄청 아끼면서도, 조회 속도가 매우 빠르기 때문이다. Redis 문서도 블룸 필터를 “아주 작은 고정 크기 메모리 공간으로 원소 존재 여부를 확인할 수 있게 해주는 확률적 자료구조”라고 설명한다.

 

---

어떻게 작동할까?

블룸 필터의 핵심은 비트 배열과 여러 개의 해시 함수다. 빈 비트 배열을 하나 준비한 뒤, 어떤 데이터를 넣을 때마다 여러 해시 함수로 위치를 계산하고, 그 위치의 비트를 1로 바꾼다. 나중에 어떤 값이 들어 있는지 확인할 때도 똑같이 해시를 돌려 해당 위치들을 검사한다. 만약 그중 하나라도 0이면 그 값은 절대 들어온 적이 없다고 판단할 수 있다. 반대로 전부 1이면 들어왔을 수도 있다고 본다.

 

왜 “있을 수도 있다”가 되는 걸까?

이유는 간단하다. 서로 다른 값들이 우연히 같은 비트 위치들을 공유할 수 있기 때문이다. 예를 들어 A를 넣어서 1이 된 비트와, B를 넣어서 1이 된 비트가 겹치다 보면, 실제로는 넣지 않은 C를 검사했을 때도 필요한 비트들이 전부 1로 보일 수 있다. 그러면 시스템은 C가 있는 것처럼 착각한다. 이게 바로 거짓 양성이다.

 

대신 “없다”는 강하게 말할 수 있다

반대로 어떤 값을 검사했는데 필요한 비트 중 하나라도 0이라면, 그 값은 애초에 들어온 적이 없다고 바로 결론 낼 수 있다. 이 점 때문에 블룸 필터는 “빠른 1차 필터” 역할에 아주 잘 맞는다. 정확한 데이터 저장소가 따로 있고, 그 앞단에서 “이건 어차피 없으니 굳이 비싼 조회를 하지 말자”는 용도로 쓰기 좋다.

 

---

왜 굳이 이런 애매한 구조를 쓸까?

정확히 저장하는 해시 테이블이나 데이터베이스 인덱스도 있는데, 왜 블룸 필터가 따로 필요할까?
답은 비용 대비 효율이다.

 

메모리를 엄청 적게 쓴다

블룸 필터는 원래 데이터를 저장하지 않는다. 문자열이든 URL이든 사용자 ID든, 그 자체를 보관하지 않고 “해시 결과가 찍은 비트들”만 남긴다. 그래서 많은 양의 데이터를 아주 압축적으로 표현할 수 있다. 위키백과 설명도 블룸 필터의 큰 장점으로 공간 효율성을 강조한다.

 

조회가 매우 빠르다

구조가 단순해서 확인할 때 하는 일도 거의 정해져 있다.
“해시 몇 번 → 비트 몇 개 확인”이면 끝이다. 그래서 블룸 필터는 대규모 시스템에서 빠른 존재 여부 판별기처럼 자주 쓰인다. Redis가 블룸 필터를 별도 데이터 타입으로 제공하는 것도 이 때문이다.

 

---

어디서 많이 쓰일까?

블룸 필터는 생각보다 실무에서 자주 등장한다. 특히 “없는 것을 빨리 걸러내는 일” 에 강하다.

 

데이터베이스나 캐시 앞단

예를 들어 어떤 키가 DB에 없는 경우가 많다고 해보자. 매번 데이터베이스에 직접 물어보면 비용이 크다. 이때 블룸 필터가 앞에 있으면, “이건 애초에 없을 가능성이 높으니 DB까지 가지 말자”는 식으로 불필요한 조회를 줄일 수 있다. 위키백과는 Bigtable, HBase, Cassandra, PostgreSQL 같은 시스템이 존재하지 않는 행이나 컬럼에 대한 디스크 조회를 줄이기 위해 블룸 필터를 사용한다고 설명한다.

 

웹 캐시

어떤 콘텐츠가 한 번만 요청되고 다시는 안 쓰이는 경우가 많다면, 그걸 디스크 캐시에 저장하는 건 낭비일 수 있다. 위키백과는 Akamai가 “원히트 원더(one-hit wonder)” 객체를 캐시에 넣지 않기 위해 블룸 필터를 사용한 사례를 소개한다. 즉, 한 번만 등장한 항목인지 빠르게 거르는 데 유용하다는 뜻이다.

 

대규모 스트리밍/분산 시스템

데이터가 매우 많고, 모든 항목을 무겁게 저장하기 어려운 상황에서는 블룸 필터가 꽤 현실적인 선택지가 된다. Redis 문서도 블룸 필터를 확률형 자료구조의 대표 사례로 소개하며, 적은 메모리로 빠른 존재 여부 판단이 필요한 상황에 적합하다고 설명한다.

 

---

헷갈리기 쉬운 포인트

블룸 필터는 개념 자체는 단순한데, 초보자가 몇 군데에서 자주 헷갈린다.

 

1. 블룸 필터는 “정확한 저장소”가 아니다

블룸 필터는 어떤 값을 다시 꺼내 보여주는 구조가 아니다.
쉽게 말해 “이 값이 있었나?”만 묻는 용도지, “그 값이 무엇이었지?” 를 복원하는 용도는 아니다. 데이터를 실제로 보관하는 저장소와는 역할이 다르다.

 

2. 기본 블룸 필터는 삭제에 약하다

고전적인 블룸 필터는 값을 추가하는 것은 가능하지만, 일반적으로 삭제는 지원하지 않는다. 왜냐하면 어떤 비트 1이 특정 원소 하나만의 흔적인지 알 수 없기 때문이다. 이 문제를 보완하려고 카운팅 블룸 필터(counting Bloom filter) 같은 변형이 등장했다.

 

3. 데이터가 많아질수록 오탐 확률이 올라간다

블룸 필터는 비트 배열이 점점 1로 채워질수록, 넣지 않은 값도 “있을 수도 있음”으로 잘못 판단할 가능성이 커진다. 그래서 블룸 필터는 보통 예상 데이터 수와 허용 가능한 오탐률을 기준으로 크기를 설계한다. Redis의 관련 명령도 필터를 만들 때 false positive rate와 capacity를 지정하도록 되어 있다.

 

---

비유로 보면 더 쉽다

블룸 필터는 약간 이런 느낌이다.

어떤 건물 출입 명단을 정교하게 적어두는 대신,
경비실에 “이 사람이 들어온 흔적이 있는지”만 아주 빠르게 보는 장치를 둔 셈이다.

• 흔적 중 하나라도 없으면 → 이 사람은 분명 안 왔다
• 흔적이 다 있으면 → 왔을 수도 있다. 그런데 동명이인이나 흔적 겹침일 수도 있다

즉, 정확한 신원 조회 시스템은 아니지만, 1차 거르기 장치로는 엄청 유용하다.

 

---

이 개념을 볼 때 같이 체크하면 좋은 것

블룸 필터 관련 설명이나 문서를 볼 때는 아래 세 가지를 같이 보면 이해가 빨라진다.

 

오탐률(false positive rate)을 얼마로 잡는가

오탐을 얼마나 허용할지에 따라 필요한 비트 수와 해시 함수 수가 달라진다.
정확도를 높이고 싶으면 메모리를 더 써야 한다.

 

예상 원소 수(capacity)가 얼마인가

데이터 수가 예상보다 많아지면 필터가 너무 빽빽해져 오탐이 늘어난다.
그래서 블룸 필터는 “얼마나 많은 데이터를 넣을 건지”를 대충이라도 알아야 설계가 된다.

 

진짜 저장소가 따로 있는가

블룸 필터는 보통 단독 주인공이 아니라, 해시 테이블·DB·캐시 같은 시스템과 함께 쓰인다.
즉, “있을 수도 있음”이 나오면 그다음에 어디서 최종 확인할지를 같이 봐야 한다.

 

---

결국 핵심은 이것이다

블룸 필터는 “정확함을 조금 포기하는 대신, 속도와 메모리를 크게 얻는 방식”이다.
그래서 완벽한 판정기가 아니라 대규모 시스템을 효율적으로 굴리기 위한 실용적 도구에 가깝다.

이 개념을 아주 짧게 다시 정리하면 이렇다.

• 있다 → 진짜 있을 수도 있고, 아닐 수도 있다
• 없다 → 거의 확실히 없다

그래서 블룸 필터는 컴퓨터에게 이렇게 말하게 만드는 구조라고 보면 된다.

“정확한 답은 나중에 확인하더라도, 일단 아닌 것부터 엄청 빠르게 쳐내자.”

 

---

참고 자료

• Redis Docs, Bloom filter
  https://redis.io/docs/latest/develop/data-types/probabilistic/bloom-filter/
• Redis Docs, Probabilistic data structures
  https://redis.io/docs/latest/operate/oss_and_stack/stack-with-enterprise/bloom/
• Redis Blog, Bloom Filter Datatype for Redis
  https://redis.io/blog/bloom-filter/
• Wikipedia, Bloom filter
  https://en.wikipedia.org/wiki/Bloom_filter
• 한국어 위키백과, 블룸 필터
  https://ko.wikipedia.org/wiki/%EB%B8%94%EB%A3%B8_%ED%95%84%ED%84%B0

Bloom filter

Probabilistic data structures

Bloom Filter Datatype for Redis | Redis

 

---

참고 영상

• Bloom Filters Explained Simply
  https://www.youtube.com/results?search_query=Bloom+Filters+Explained+Simply
• Bloom Filter Data Structure
  https://www.youtube.com/results?search_query=Bloom+Filter+Data+Structure
• Redis Bloom Filter Tutorial
  https://www.youtube.com/results?search_query=Redis+Bloom+Filter+Tutorial

- YouTube

- YouTube

- YouTube