Source: Dev.to

Bloom 필터는 크기를 조절할 수 없습니다 – 대신 할 수 있는 일

Bloom 필터는 고정된 크기와 고정된 false‑positive 비율을 갖는 확률적 자료구조입니다.
필터를 한 번 생성하면, 그 크기와 비율은 변경할 수 없습니다.
이 제한 때문에 “필터가 가득 차서 더 이상 아이템을 삽입할 수 없다”는 상황에 직면하게 됩니다.

아래에서는 Bloom 필터를 크기 조절할 수 없는 이유를 간단히 살펴보고, 실제 프로젝트에서 사용할 수 있는 대체 전략들을 소개합니다.

---

왜 Bloom 필터는 리사이징이 불가능한가?

1. 비트 배열이 고정되어 있다
   Bloom 필터는 m개의 비트 배열과 k개의 해시 함수를 사용합니다.
   새로운 비트를 추가하면 기존에 설정된 비트와 해시값이 모두 달라져야 하므로, 기존에 삽입된 모든 원소를 다시 해시해야 합니다.

2. False‑positive 확률이 비트 수에 의존한다
   m과 k가 바뀌면 false‑positive 확률도 바뀝니다.
   기존 원소를 그대로 두고 비트 수만 늘리면, 기존 원소에 대한 false‑positive 확률이 보장되지 않습니다.

3. 재해싱 비용이 너무 크다
   전체 데이터를 다시 해시하는 작업은 O(n) 시간 복잡도를 가지며, 대규모 시스템에서는 실용적이지 않습니다.

---

실전에서 사용할 수 있는 대안

1. 처음부터 충분히 큰 필터를 만든다

가장 간단한 방법은 예상되는 최대 원소 수와 허용 가능한 false‑positive 비율을 기준으로 여유 있게 큰 필터를 설계하는 것입니다.

// Go 예시: 1백만 개의 아이템, 0.01 (1%) false‑positive 목표
n := 1_000_000
p := 0.01
m := int(math.Ceil(-float64(n) * math.Log(p) / (math.Ln2 * math.Ln2)))
k := int(math.Round((float64(m) / float64(n)) * math.Ln2))
bf := bloom.New(uint(m), uint(k))

Tip: m과 k를 계산할 때는 위와 같은 수학 공식을 사용하면 정확합니다.

2. Scalable Bloom Filter 사용

Scalable Bloom Filter(SBF)는 필터가 가득 차면 자동으로 새로운 레이어를 추가하는 방식으로 동작합니다.
각 레이어는 점점 더 작은 false‑positive 비율을 갖도록 설계됩니다.

from pybloom_live import ScalableBloomFilter

# 초기 레이어는 0.01 false‑positive, 이후 레이어는 0.5배씩 감소
sbf = ScalableBloomFilter(initial_capacity=100000, error_rate=0.01, mode=ScalableBloomFilter.LARGE_SET_GROWTH)
sbf.add("some-element")

• 장점: 기존 데이터를 재해싱할 필요가 없습니다.
• 단점: 메모리 사용량이 레이어가 추가될수록 증가합니다.

3. Counting Bloom Filter 로 대체

Counting Bloom Filter는 각 비트를 카운터(보통 4~8비트)로 바꾸어, 원소를 삭제하거나 재삽입할 수 있게 합니다.
필터가 포화 상태에 가까워지면, 카운터가 가득 찬 비트를 기준으로 새로운 필터를 생성하고 기존 데이터를 복사합니다.

// C 예시 (libbloom 사용)
struct counting_bloom *cbf = cbloom_create(1000000, 0.01);
cbloom_add(cbf, "example");
cbloom_check(cbf, "example");

• 장점: 삭제가 가능하고, 포화 시점에 새로운 필터를 만들 수 있습니다.
• 단점: 카운터를 저장하므로 메모리 사용량이 일반 Bloom Filter보다 2~4배 높습니다.

4. Partitioned Bloom Filter (또는 “Bloom Filter of Bloom Filters”)

전체 데이터를 여러 개의 작은 Bloom Filter로 분할합니다.
예를 들어, 시간 기반 파티셔닝을 하면 “지난 1시간”, “지난 2시간” 등으로 각각 별도 필터를 유지할 수 있습니다.

// Java 예시 (Guava 사용)
BloomFilter<String> hour1 = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), 100_000, 0.01);
BloomFilter<String> hour2 = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), 100_000, 0.01);

• 장점: 오래된 파티션을 삭제하면 메모리를 회수할 수 있습니다.
• 단점: 파티션 수가 많아지면 조회 비용이 증가합니다.

5. Cuckoo Filter 로 전환

Cuckoo Filter는 삭제가 가능한 Bloom Filter의 대안이며, 일반적으로 비슷한 false‑positive 비율을 유지하면서도 동적 크기 조절이 가능합니다.

// Rust 예시 (cuckoofilter crate)
use cuckoofilter::CuckooFilter;

let mut cf = CuckooFilter::with_capacity(1_000_000);
cf.add(&"item".as_bytes());
assert!(cf.contains(&"item".as_bytes()));

• 장점: 삽입/삭제가 O(1)이며, 필터가 포화될 경우 자동으로 리사이징됩니다.
• 단점: 구현이 복잡하고, 메모리 사용량이 약간 더 높을 수 있습니다.

---

언제 어떤 방법을 선택해야 할까?

---

마무리

Bloom 필터는 고정된 구조 때문에 직접적인 리사이징이 불가능합니다.
하지만 위에서 소개한 여러 전략을 활용하면, 필터가 포화되는 상황을 효과적으로 회피하면서도 원하는 false‑positive 비율을 유지할 수 있습니다.

프로젝트의 특성과 요구사항에 맞는 방식을 선택하고, 필요에 따라 테스트를 통해 실제 메모리 사용량과 false‑positive 비율을 검증하는 것이 중요합니다.

“필터를 리사이즈하려고 애쓰기보다, 올바른 자료구조와 설계를 선택하는 것이 장기적으로 더 큰 가치를 제공합니다.”

블룸 필터란?

Bloom filters are a probabilistic data structure that use a bit array and hash functions to reduce the load on main databases.
You might wonder why not just use a caching system like Redis. The answer comes down to a trade‑off between accuracy and memory efficiency:

블룸 필터 설계

Before using a bloom filter you must decide:

1. Size of the bit array (m) – once set, it cannot be changed.
2. Number of hash functions (k) – also fixed after creation.

Both parameters depend on:

• n – expected number of items to store.
• p – acceptable false‑positive probability.

해시 함수 개수 선택

The number of hash functions cannot be too low (causing many collisions) nor too high (filling the array quickly and also causing collisions).
The optimal value is given by the formula:

[ k = \frac{m}{n},\ln 2 ]

Go에서 최적 파라미터 계산

package main

import (
	"math"
)

// CalculateOptimalParams returns the optimal bit‑array size (m) and
// number of hash functions (k) for a given item count (n) and false‑positive
// rate (p).
func CalculateOptimalParams(n int, p float64) (uint, uint) {
	// 1. Ideal bit‑array size (m)
	//    m = - (n * ln(p)) / (ln(2))²
	m := -float64(n) * math.Log(p) / math.Pow(math.Log(2), 2)

	// 2. Ideal number of hash functions (k)
	//    k = (m / n) * ln(2)
	k := (m / float64(n)) * math.Log(2)

	return uint(math.Ceil(m)), uint(math.Ceil(k))
}

func main() {
	n := 1000          // Expected number of items
	p := 0.01          // Desired false‑positive rate (1%)
	m, k := CalculateOptimalParams(n, p)

	// Print the recommended parameters
	println("Recommended Bit Array Size (m):", m)
	println("Recommended Hash Functions (k):", k)
}

Bloom Filter의 핵심 로직

Bloom filter는 “이 항목이 집합에 존재할 가능성이 있나요?” 라는 질문에 답합니다.

답이 확실히 NO라면, 데이터베이스 조회를 건너뛸 수 있습니다.
답이 maybe라면, 실제 데이터 소스와 확인해야 합니다.

예시 시나리오: 사용자 이름 사용 가능 여부

1. 전통적인 접근법 – SQL 쿼리를 실행합니다:

   SELECT 1 FROM users WHERE username = 'ayush' LIMIT 1;

   인덱스가 있더라도, 쿼리 비용은 대략 O(log n) 입니다.

2. Bloom‑filter 접근법 –
   먼저 필터를 확인합니다.
   NO라고 하면, 즉시 사용자 이름을 허용합니다.
   maybe라고 하면, 데이터베이스 쿼리로 돌아갑니다.

이는 데이터베이스 부하를 크게 줄일 수 있습니다.

블룸 필터 작동 방식

블룸 필터는 두 가지 구성 요소로 이루어집니다:

1. Bit Array – 0과 1로 이루어진 배열 (예: [0,0,0,0,0]).
2. Hash Functions – 값을 비트 배열의 인덱스로 매핑하는 결정적 함수.

단계별 진행

비트 배열을 10비트로 가정하고, 처음에는 모두 0입니다.

Go 구현 간단한 블룸 필터

package main

import (
	"fmt"
	"hash/fnv"
)

// BloomFilter holds the bit array and its size.
type BloomFilter struct {
	bitset []bool // 0/1 array
	size   int    // length of the array
}

// NewBloomFilter creates a filter with the given size.
func NewBloomFilter(size int) *BloomFilter {
	return &BloomFilter{
		bitset: make([]bool, size),
		size:   size,
	}
}

// hash1 – first hash function (FNV‑1a).
func (bf *BloomFilter) hash1(s string) int {
	h := fnv.New32a()
	h.Write([]byte(s))
	return int(h.Sum32()) % bf.size
}

// hash2 – second hash function (FNV‑1a with a salt).
func (bf *BloomFilter) hash2(s string) int {
	h := fnv.New32a()
	h.Write([]byte(s + "salt")) // simple salt to get a different hash
	return int(h.Sum32()) % bf.size
}

// Add inserts an item into the filter.
func (bf *BloomFilter) Add(item string) {
	i1 := bf.hash1(item)
	i2 := bf.hash2(item)
	bf.bitset[i1] = true
	bf.bitset[i2] = true
	fmt.Printf("Added: %s (indices %d, %d)\n", item, i1, i2)
}

// Exists checks whether an item *might* be in the set.
func (bf *BloomFilter) Exists(item string) bool {
	i1 := bf.hash1(item)
	i2 := bf.hash2(item)

	// Both bits must be true for a "maybe" answer.
	if bf.bitset[i1] && bf.bitset[i2] {
		return true // maybe
	}
	return false // definitely not
}

func main() {
	filter := NewBloomFilter(100)

	// 1. Add "Ayush"
	filter.Add("Ayush")

	// 2. Query "Ayush"
	fmt.Println("Does Ayush exist?", filter.Exists("Ayush")) // true (maybe)

	// 3. Query "Kumar"
	fmt.Println("Does Kumar exist?", filter.Exists("Kumar")) // false (definitely not)
}

실제 사용 사례

요점

• Bloom Filter는 작은, 제어 가능한 오탐률을 대가로 엄청난 메모리 절감과 빠른 멤버십 검사를 제공합니다.
• 필터는 쓰기 전용이며 (삭제 불가) 생성 후 크기가 고정됩니다.
• 위의 식을 사용해 m과 k를 적절히 설정하는 것이 원하는 오류율을 달성하는 데 핵심입니다.

Go 코드를 여러분의 프로젝트에 맞게 자유롭게 적용하고, 해시 함수 개수를 조정하거나 단순 FNV 해시 대신 MurmurHash, SipHash와 같은 더 강력한 해시를 사용해 분포를 개선해 보세요. 즐거운 필터링 되세요!

실무에서의 블룸 필터

• 웹 브라우저 – URL이 너무 길거나 의심스러울 경우, Chrome은 이를 블룸 필터에 저장합니다.

  • 방문 시 Chrome은 필터를 확인합니다.
  • 필터가 *“아마 위험함”*을 반환하면, Chrome은 확인을 위해 Google 서버에 연락합니다.

• 데이터베이스 (Cassandra / PostgreSQL) – 행을 찾기 위해 하드 디스크 블록을 스캔하기 전에 엔진은 블룸 필터를 확인합니다.

  • 필터가 해당 행이 없다고 판단하면, 비용이 많이 드는 디스크 I/O를 피할 수 있습니다.

Bloom 필터 확장

Bloom 필터의 크기(배열 길이 m와 해시 함수 개수 k)는 일반적으로 가정된 최대 아이템 수 n와 목표 위양성률 p를 기준으로 선택됩니다.
실제 데이터 세트가 원래 가정보다 커지면 필터를 확장해야 합니다.

확장 가능한 Bloom 필터 (SBF)

Redis Stack은 stacked Bloom filters(또는 Scalable Bloom Filters라고도 함)를 구현합니다.
스택에 추가되는 각 새로운 필터는 이전 필터보다 크고 엄격히 더 정확합니다.

스태킹 알고리즘 작동 방식

A. 쓰기 규칙 – 데이터 추가

왜? 동결된 필터는 원래의 오탐 보장을 유지하며, 최신 필터만 새로운 삽입을 처리합니다.

B. 읽기 규칙 – 데이터 확인

쿼리 **“Ayush가 존재합니까?”**에 답하려면:

1. 필터 3 확인 – 결과: 아니오 (Ayush는 최신 필터에 없음)
2. 필터 2 확인 – 결과: 아니오
3. 필터 1 확인 – 결과: 예 (Ayush는 두 달 전에 추가됨)

최종 답은 모든 확인의 논리적 OR입니다:

Result = F3.Exists() || F2.Exists() || F1.Exists()

Naïve Stacking의 문제점

• 추가되는 각 필터는 자체적인 false‑positive 확률을 도입한다.
• 각 필터의 오류율이 1 %라면, 두 개의 필터는 ≈ 2 % 전체 오류, 열 개의 필터는 ≈ 10 % 오류를 초래한다 – 이는 받아들일 수 없는 증가이다.

Redis가 문제를 해결하는 방법

Redis는 각 연속 필터를 더 엄격하게(거짓 양성 비율 감소) 만들며 이전 필터보다 더 낮은 오류율을 제공합니다:

후속 필터는 훨씬 더 정밀하기 때문에, 20개의 필터를 쌓아도 전체 거짓 양성 비율이 1 % 이하로 유지됩니다.

요약

• 블룸 필터는 비용이 많이 드는 조회를 피하기 위해 널리 사용됩니다.
• 데이터 세트가 커질 때, 스케일러블 블룸 필터(쌓아 올린, 점점 더 엄격한 필터)를 사용하면 전체 구조를 재구성하지 않고도 낮은 전체 오류율을 유지할 수 있습니다.
• Redis 구현은 점진적으로 더 엄격해지는 필터가 실용적이고 낮은 오류율을 갖는 확장의 핵심임을 보여줍니다.