[20250417] 블룸 필터
Table of Contents
1 블룸 필터란?
블룸 필터(Bloom Filter)는 1970년 Burton Howard Bloom에 의해 소개된 확률적 데이터 구조로, 집합에 특정 요소가 속해 있는지 여부를 빠르게 확인할 수 있는 도구.
이 구조는 메모리 효율성이 뛰어나며, 대규모 데이터셋에서 중복을 방지하거나 캐시를 관리하는 데 유용하게 사용됨.
블룸 필터의 주요 특징:
- 공간 효율성: 적은 메모리로 대량의 데이터를 처리할 수 있다.
- 빠른 조회: 해시 함수를 사용해 상수 시간(O(1)) 내에 조회가 가능하다.
- 거짓 양성 허용: 요소가 집합에 없음에도 "있을 수 있다"고 잘못 판단할 수 있지만(거짓 양성, False Positive), "없다"고 판단한 경우는 절대 틀리지 않는다(거짓 음성, False Negative 없음).
블룸 필터는 이러한 특성 덕분에 웹 캐시, 네트워크 라우팅, 데이터베이스 시스템 등 다양한 분야에서 활용됨. 특히 대규모 분산 시스템에서 불필요한 디스크 조회를 줄이는 데 중요한 역할을 하며, 이는 시스템 성능 최적화에 크게 기여함.
2 소스코드
(ns core
(:require [clojure.core.reducers :as r]
[clojure.repl.deps]))
;; clojure 1.12.0 version necessary
(comment
(clojure.repl.deps/add-lib 'org.clojure/math.combinatorics {:mvn/version "0.3.0"})
(require '[clojure.math.combinatorics :as combo])
;;
)
(def default-size 100)
(defn hash-functions [k size]
"k개의 해시 함수를 생성. 여기서는 간단히 hash 함수를 사용"
(map (fn [i]
;; x를 받아 x와 i를 문자열로 결합 후 hash 로 계산 후 mod 100 으로 0~99 사이 값으로 반환
(fn [x] (mod (hash (str x i)) size))) (range k)))
;; k=3 일때, 아래처럼 3개의 해시함수가 리턴댐
;; (fn [x] (mod (hash (str x 0)) 100))
;; (fn [x] (mod (hash (str x 1)) 100))
;; (fn [x] (mod (hash (str x 2)) 100))
;; "hello" 를 입력하면
;; (mod (hash "hello0") 100) -> 45
;; (mod (hash "hello1") 100) -> 72
;; (mod (hash "hello2") 100) -> 19
(defn create-bloom-filter [size hash-count]
"블룸 필터 초기화
args:
size: 비트 배열의 크기
hash-count: 사용할 해시 함수의 개수
returns:
맵으로 표현된 블룸 필터"
{:size size
:hash-count hash-count
:bit-array (vec (repeat size 0))
:hash-fns (hash-functions hash-count size)})
(defn add-to-filter [bloom-filter item]
"항목을 블룸 필터에 추가
args:
bloom-filter: 블룸 필터 맵
item: 추가할 항목
returns:
업데이트된 블룸 필터"
(let [{:keys [size hash-fns bit-array]} bloom-filter
;; indices 는 hash-fns의 각 함수를 적용한 결과(데이터가 있는지 확인할 수 있는 0~99)
;; k의 숫자만큼 index 가 생성될 것. ex) [45 72 19]
indices (map (fn [h] (h item)) hash-fns)]
(assoc bloom-filter
:bit-array
;; "hello" 가 추가되면 indices [45 72 19] 인덱스가 1로 바뀜.
(reduce (fn [arr idx] (assoc arr idx 1))
bit-array
indices))))
(defn check-in-filter [bloom-filter item]
(let [{:keys [hash-fns bit-array]} bloom-filter
indices (map (fn [h] (h item)) hash-fns)]
;; "hello" indices -> [45 72 19] 안에 모든 인덱스에 1이 존재해야한다.
(every? #(= 1 (get bit-array %)) indices)))
(defn run []
(let [bf (create-bloom-filter default-size 3)]
(let [bf-added (add-to-filter bf "hello")]
(println (check-in-filter bf-added "hello"))
(println (check-in-filter bf-added "world")))))
(run)
deps.edn
{:paths ["src"]
:deps {org.clojure/clojure {:mvn/version "1.12.0"}}}
3 블룸 필터 사용 사례
블룸 필터는 대규모 데이터 처리와 시스템 최적화가 필요한 환경에서 널리 사용됨. (특히 IO 비용이 높은 데이터 처리에서) 특히 빅테크 기업들은 이를 활용해 성능과 효율성을 극대화함.
아래는 몇 가지 대표적인 사례:
- Google BigTable: Google의 분산 데이터베이스 시스템인 BigTable은 SSTable에 저장된 행-열 쌍의 존재 여부를 빠르게 확인하기 위해 블룸 필터를 사용. 이를 통해 디스크 I/O를 줄이고, 쿼리 응답 속도를 크게 향상시킨다.
- Apache Cassandra: 오픈소스 분산 데이터베이스인 Cassandra는 블룸 필터를 활용해 SSTable에서 특정 파티션 키가 존재하는지 확인. 이는 불필요한 디스크 읽기를 방지해 성능을 최적화한다.
- Squid Web Proxy Cache: Squid는 캐시된 URL의 존재 여부를 빠르게 확인하기 위해 블룸 필터를 사용. 이를 통해 캐시 히트율을 높이고 네트워크 트래픽을 줄인다.
이처럼 블룸 필터는 메모리 효율성과 빠른 조회 속도를 바탕으로, 대규모 시스템에서 핵심적인 역할을 수행한다.
4 블룸 필터의 한계
블룸 필터는 거짓 양성(False Positive)을 허용하기 때문에, 존재하지 않는 요소를 확인할 때 오류가 발생할 수 있다. 이는 데이터 처리 시스템에서 중요한 문제가 될 수 있음. 이 한계는 인지만 하고 있으면, 블룸 필터를 사용해서 존재하는 데이터를 못 찾을 확률은 매우 낮다.