블룸 필터의 기본 개념부터 해시 함수 선택, 거짓 양성 확률의 수학, 삭제 가능한 변형(카운팅/Deletable Bloom Filter), 벤치마크 관점과 데이터베이스·캐시·스파크 조인 등 실전 활용까지 한 번에 정리한다.
BlogsPapershelfBookshelfCoursesTalks
호기심 많은 사람, 뚝딱이, 탐험가
블룸 필터(Bloom filter)는 **“이걸 전에 본 적이 있나?”**라는 매우 특정한 질문에 답하기 위해, 거의 메모리를 쓰지 않으면서 동작하는 확률적 자료구조다.
다만 트레이드오프가 있다. 블룸 필터는 ‘틀릴’ 수 있다. 블룸 필터는 실제로 존재하는 것을 없다고 말하는 일은 절대 없지만(거짓 음성 없음), 존재하지 않는 것을 있다고 말하는 경우(거짓 양성)가 가끔 발생할 수 있다.
이 글에서는 블룸 필터를 기초 개념부터 카운팅/삭제 가능 블룸 필터 같은 고급 변형, 해시 함수의 미묘한 포인트, 그리고 실제 벤치마크와 사용 사례까지 끝까지 훑어본다.
수백만 사용자가 있는 콘텐츠 플랫폼에서 추천 엔진을 만든다고 해보자. 각 사용자는 수천 개의 글을 이미 읽었다. 추천을 생성할 때는 사용자가 이미 본 글을 걸러야 한다.
사용자별로 모든 글 ID를 해시 셋에 저장하면 메모리를 엄청나게 잡아먹는다. 숫자로 계산해보자…
가정:
해시 셋에 글 ID를 직접 저장:
Per user storage:
5,000 article IDs * 8 bytes = 40,000 bytes = 40 KB
Hash set overhead (typical 2x for load factor + pointers):
40 KB * 2 = 80 KB per user
Total for all users:
80 KB * 10,000,000 users = 800 GB
사용자가 본 글을 추적하는 데만 RAM이 800GB가 든다. 오버헤드를 더 낙관적으로 1.5배로 잡아도 600GB다.
블룸 필터는 실제 글 ID를 저장하지 않고, “존재 여부”를 아주 조밀한 비트 배열에 저장함으로써 공간을 약 ~60GB(10분의 1) 정도로 줄일 수 있다. 그리고 다음 질문에 답한다.
이 사용자는 이 글을 아마 봤을까?
답이 아니오면 자신 있게 추천할 수 있다. 답이 예면 추천에서 빼거나, 더 비싼 조회로 실제로 봤는지 확인하면 된다. 실무에서는 추천 생성 속도를 떨어뜨리지 않으면서도 메모리 사용량을 90% 이상 줄일 수 있다.
이 아이디어의 변형은 대규모 시스템에서 흔히 보인다. Medium은 추천에, Chrome은 위험한 URL 표시에, 데이터베이스는 불필요한 디스크 읽기를 피하기 위해 블룸 필터를 활용한다.
블룸 필터는 두 가지 구성요소로 이루어진다.
m비트의 비트 배열(bit array): 초기값은 모두 0k개의 해시 함수: 임의 입력을 m개 위치 중 하나로 매핑원소를 필터에 추가하려면:
def add(element):
for i in 1 to k:
position = hash_i(element) mod m
bit_array[position] = 1
원소가 존재할 수도 있는지 확인하려면:
def contains(element):
for i in 1 to k:
position = hash_i(element) mod m
if bit_array[position] == 0:
return false
return true
계산된 위치 중 어떤 비트라도 0이면, 그 원소는 확실히 추가된 적이 없다. 삽입 시 해당 위치 비트가 1로 세팅되었어야 하기 때문이다. 하지만 모든 비트가 1이면, 그 원소가 실제로 추가되었을 수도 있고, 다른 원소들이 그 비트들을 1로 만들어 놓았을 수도 있다. 이것이 **거짓 양성(false positive)**의 근원이다.
구체적인 예를 보자. 10비트 배열과 해시 함수 2개가 있다고 하자. 문자열 “apple”, “banana”를 넣는다.
이후 비트 2, 3, 5, 7이 1이 된다. 이제 “cherry”를 확인해보면:
두 위치 모두 이미 1이므로(이전 삽입으로 세팅됨), 필터는 “cherry”가 있을 수도 있다고 잘못 보고한다. 이것이 거짓 양성이다.
m비트 필터에 k개의 해시 함수를 사용해 n개 원소를 삽입한 뒤, 특정 비트가 0으로 남아 있을 확률은:
p0 = (1 - 1/m)^(kn)
배열에 m비트가 있고 해시가 무작위 위치를 출력한다고 하면, 특정 비트를 맞출 확률은 1/m이다. 따라서 한 번 해시에서 특정 비트를 맞추지 않을 확률은 1 - 1/m. n번 삽입에서 매번 k비트를 세팅하므로, 그 비트가 0으로 남을 확률은 (1 - 1/m)^(kn)가 된다.
m이 충분히 크면 다음으로 근사된다.
p0 ≈ e^(-kn/m)
거짓 양성 확률은, 집합에 없는 임의 원소에 대해 k개 비트가 모두 1일 확률이다.
p_fp = (1 - e^(-kn/m))^k
여기에는 중요한 트레이드오프가 있다. m(비트 수)를 늘리면 거짓 양성이 줄지만 메모리를 더 쓴다. k(해시 함수 개수)를 늘리는 것은 k와 m/n의 관계에 따라 도움이 될 수도, 오히려 악화시킬 수도 있다.
거짓 양성률을 최소화하는 최적 해시 함수 개수는(간단한 미분으로):
k_optimal = (m/n) * ln(2) ≈ 0.693 * (m/n)
이 최적 k에서 거짓 양성률은:
p_fp ≈ (0.6185)^(m/n)
거꾸로 계산하면, 특정 거짓 양성률 p를 원할 때 필요한 대략적인 비트/원소 비율은:
m/n = -ln(p) / (ln(2))^2 ≈ -1.44 * ln(p)
거짓 양성률이 1%라면 원소당 약 9.6비트가 필요하고, 0.1%라면 약 14.4비트가 필요하다.
이를 64비트 정수 100만 개를 직접 저장하는 것(8MB 필요)과 비교해보자. 블룸 필터는 확률적 멤버십 테스트를 제공하면서도 대략 7배의 공간 절감을 이룬다.
블룸 필터에는 다음 조건의 해시 함수가 필요하다.
SHA-1이나 MD5 같은 암호학적 해시는 분포 특성과 보안 보장이 좋지만, 계산 비용이 크다. 블룸 필터는 암호학적 보안이 필요 없으므로 이런 해시는 CPU를 낭비한다.
비암호학적 해시가 표준 선택이다.
Kirsch와 Mitzenmacher의 중요한 논문은 실제로 k개의 독립 해시 함수가 필요 없음을 보였다. 대신 해시 함수 2개만 계산하고 선형 결합으로 k개 위치를 만들 수 있다.
g_i(x) = h1(x) + i * h2(x) for i = 0, 1, ..., k-1
이를 더블 해싱(double hashing) 또는 Kirsch–Mitzenmacher 최적화라고 하며, 계산 오버헤드를 크게 줄이면서도 점근적 거짓 양성률은 동일하게 유지한다. 실서비스용 블룸 필터 구현 대부분이 이 방식을 쓴다.
def compute_positions(element, k, m, hash1, hash2):
"""
Compute k bit positions using double hashing.
"""
h1 = hash1(element)
h2 = hash2(element)
positions = []
for i in range(k):
pos = (h1 + i * h2) % m
positions.append(pos)
return positions
여기에는 미묘하지만 중요한 구현 디테일이 있다. h2가 0이 되거나 m과 공약수를 공유하면, 여러 위치가 서로 겹치는 퇴화(degenerate) 케이스가 발생할 수 있다. 향상된 더블 해싱은 h2가 항상 홀수(특히 m이 2의 거듭제곱일 때)거나, m과 서로소가 되도록 보장해 이를 해결한다.
def compute_positions_enhanced(element, k, m, hash_func):
"""
Enhanced double hashing that avoids degenerate cases.
"""
h = hash_func(element)
h1 = h & 0xFFFFFFFF # Lower 32 bits
h2 = (h >> 32) | 1 # Upper 32 bits, ensure odd
positions = []
for i in range(k):
pos = (h1 + i * h2) % m
positions.append(pos)
return positions
RocksDB는 블룸 필터 구현에서 이 문제를 발견했고, delta 값이 항상 홀수가 되도록 고쳐 m이 2의 거듭제곱일 때 서로 다른 위치가 보장되게 했다.
표준 블룸 필터의 큰 한계는 원소를 제거할 수 없다는 점이다. 한 비트가 1로 세팅되면, 그 비트가 하나의 원소 때문에 세팅된 것인지 여러 원소 때문에 세팅된 것인지 알 수 없다. 이를 0으로 내리면 같은 위치를 공유하는 다른 원소에 대해 거짓 음성이 생길 수 있다.
이를 해결하는 여러 변형이 있다.
가장 직관적인 방법은 각 비트를 작은 카운터(보통 4비트)로 바꾸는 것이다. 비트를 1로 세팅하는 대신 카운터를 증가시키고, 삭제 시에는 해당 위치 카운터를 감소시킨다.
class CountingBloomFilter:
def __init__(self, m, k, counter_bits=4):
self.m = m
self.k = k
self.max_count = (1 << counter_bits) - 1
self.counters = [0] * m
def add(self, element):
for pos in self._get_positions(element):
if self.counters[pos] < self.max_count:
self.counters[pos] += 1
def remove(self, element):
for pos in self._get_positions(element):
if self.counters[pos] > 0:
self.counters[pos] -= 1
def contains(self, element):
return all(self.counters[pos] > 0
for pos in self._get_positions(element))
트레이드오프는 크다. 4비트 카운터를 쓰면 표준 블룸 필터 대비 메모리를 4배 사용한다. 카운터 오버플로도 문제다. 너무 많은 원소가 같은 위치로 해시되면 카운터가 포화(saturate)된다. 대부분의 구현은 포화 카운터를 최대값에 고정하고 더 이상 감소시키지 않는 방식으로 처리하며, 거짓 양성이 약간 늘어나는 것을 감수한다.
Deletable Bloom filter는 다른 접근을 취한다. 카운팅 대신 블룸 필터 배열 전체를 r개의 논리적 영역(region)으로 나누고, (최소 한 비트에서) 충돌이 발생한 영역을 추적하며 별도의 충돌 비트맵(collision bitmap)을 유지한다.
원소 삽입 시:
k개 비트 위치 계산원소 삭제 시:
DlBF는 확률적 삭제 가능성을 제공한다. 대부분 원소는 삭제할 수 있지만, 일부는 삭제할 수 없다. 장점은 카운팅 필터에 비해 메모리 오버헤드가 훨씬 낮다는 점이다.
블룸 필터 구현을 평가할 때는 여러 지표가 중요하며, 이런 벤치마크 대부분은 내 GitHub 저장소 abloom에서 확인할 수 있다.
초당 몇 개 원소를 필터에 추가할 수 있는지 측정한다. 주로 다음에 좌우된다.
블룸 필터는 초당 수십만~수백만 건 삽입을 달성해야 한다. Redis 벤치마크는 파이프라이닝으로 초당 약 250,000건 삽입을 보여준다.
보통 삽입과 비슷하거나 더 빠르다. 조회는 첫 0비트를 발견하면 즉시 종료할 수 있기 때문이다. 더블 해싱 최적화는 해시 계산을 줄여 조회에 특히 이득이다.
이론적 거짓 양성률은 완벽한 해시 함수를 가정한다. 실제 구현은 벤치마크로 검증할 수 있다.
def benchmark_fp_rate(bf, test_size=100000):
"""
Benchmark actual false positive rate.
"""
# Add known elements
known_elements = [f"element_{i}" for i in range(test_size)]
for elem in known_elements:
bf.add(elem)
# Test with elements definitely not in the set
false_positives = 0
test_elements = [f"test_{i}" for i in range(test_size)]
for elem in test_elements:
if bf.contains(elem):
false_positives += 1
return false_positives / test_size
블룸 필터는 현대 데이터베이스에서 꽤 흔하며, 특히 LSM(Log-Structured Merge) 트리를 사용하는 DB에서 많이 쓴다.
RocksDB, Cassandra, LevelDB, HBase 같은 DB는 읽기 경로 최적화를 위해 블룸 필터를 쓴다. LSM 트리에서는:
블룸 필터가 없으면, 키 조회마다 여러 SSTable을 디스크에서 읽어야 할 수도 있다. 각 SSTable에 블룸 필터를 붙이면, 해당 키가 확실히 없다는 것을 빠르게 판단해 비싼 디스크 읽기를 피할 수 있다.
Cassandra는 이를 튜닝 가능한 파라미터로 노출한다. bloom_filter_fp_chance 설정은 SSTable당 거짓 양성률을 제어한다.
CREATE TABLE my_table (
...
) WITH bloom_filter_fp_chance = 0.01;
값을 낮추면(예: 0.01) 메모리를 더 쓰지만 불필요한 디스크 읽기를 줄인다. 값을 높이면(예: 0.1) 메모리를 아끼는 대신 거짓 양성으로 인한 디스크 접근이 늘어난다.
콘텐츠를 이전에 본 적이 있는지 확인하는 것은 블룸 필터의 고전적인 적용 사례다. 예:
핵심 인사이트는 거짓 양성(가끔 이미 처리한 것을 다시 확인)은 허용되지만, 거짓 음성(새로운 것을 놓침)은 허용되지 않는다는 점이다.
CDN은 엣지 노드에서 어떤 오브젝트가 캐시되어 있는지 추적하기 위해 블룸 필터를 사용한다. Akamai는 “원히트 원더(one hit wonders)”(한 번만 접근되는 오브젝트)를 캐싱하지 않기 위해 블룸 필터를 쓰는 기법을 선도적으로 도입했다. 최소 두 번 이상 본 오브젝트만 캐싱함으로써 캐시 효율을 크게 개선했다.
패턴:
PostgreSQL Bloom 인덱스
10개 컬럼이 있고 다양한 조합으로 필터링하는 쿼리가 있다고 해보자.
SELECT * FROM products WHERE color = 'red' AND size = 'large' AND brand = 'nike';
SELECT * FROM products WHERE category = 'shoes' AND price_range = 'mid';
SELECT * FROM products WHERE color = 'blue' AND category = 'shirts' AND material = 'cotton';
전통적인 방법은 B-tree 인덱스를 만드는 것이다. 하지만 어떤 조합을 인덱싱할 것인가?
CREATE INDEX idx1 ON products(color, size, brand);
CREATE INDEX idx2 ON products(category, price_range);
CREATE INDEX idx3 ON products(color, category, material);
-- And so on for every possible combination...
이는 금방 폭발한다. 10개 컬럼에 임의의 쿼리 패턴이 있으면 수십 개 인덱스가 필요할 수 있고, 각각 디스크를 크게 잡아먹으며 쓰기도 느려진다.
PostgreSQL의 Bloom 인덱스는 지정한 모든 컬럼을 각 행(또는 페이지)당 하나의 블룸 필터로 인코딩해, 하나의 조밀한 인덱스를 만든다.
CREATE EXTENSION bloom;
CREATE INDEX products_bloom ON products USING bloom (color, size, brand, category, price_range, material);
쿼리 시점에:
SELECT * FROM products WHERE color = 'red' AND size = 'large';
큰 테이블(10억 행, 500GB)과 작은 테이블(10만 행, 10MB)을 조인한다고 하자.
large_df = spark.read.parquet("events") # 1B rows across 1000 partitions
small_df = spark.read.parquet("users") # 100K rows
result = large_df.join(small_df, "user_id")
최적화가 없으면 Spark는 작은 테이블을 모든 노드로 브로드캐스트한다.
하지만 큰 테이블에서 실제로 매칭되는 user_id가 5%뿐이라면? 여전히 10억 행을 읽고 처리한다.
블룸 필터 최적화:
from pyspark.sql.functions import broadcast
# Spark builds a Bloom filter from small_df's user_id column
# and broadcasts it (just a few KB) to all executors
result = large_df.join(broadcast(small_df), "user_id")
일어나는 일:
1970년 Burton Howard Bloom이 고안한 블룸 필터는 오늘날까지 가장 널리 배포된 확률적 자료구조 중 하나다. 단순함, 효율, 잘 이해된 수학적 성질 덕분에 데이터베이스 내부부터 분산 시스템, 네트워크 보안까지 현대 시스템 설계의 핵심에 자리 잡았다.
빠르고 공간 효율적인 멤버십 테스트가 필요하고, 가끔의 거짓 양성을 감수할 수 있다면 블룸 필터가 최적의 선택인 경우가 많다.
도움이 되었고 흥미로웠다면,
GCP Memorystore의 Staff Engg, DiceDB 제작자, 전 Google Ads 및 GCP Dataproc Staff Engg, 전 Amazon Fast Data, 전 Unacademy의 Director of Engg. SRE 및 데이터 엔지니어링. 군더더기 없는 엔지니어링 영상으로 YouTube와 내 코스로 엔지니어링 호기심을 불러일으킨다.
Writings and Learnings
Courses
Legal and Contact
Everything Else
Arpit의 뉴스레터(엔지니어 145,000명이 읽음)
현실 세계의 시스템 설계, 분산 시스템, 또는 매우 영리한 알고리즘에 대한 딥다이브를 다루는 주간 에세이.
이 웹사이트에 나열된 코스는 다음에서 제공한다.
Relog Deeptech Pvt. Ltd.
203, Sagar Apartment, Camp Road, Mangilal Plot, Amravati, Maharashtra, 444602
GSTIN: 27AALCR5165R1ZF
YouTube (180k)Twitter (100k)LinkedIn (250k)GitHub (6k)