블룸 필터
블룸 필터 (Bloom Filter)
블룸 필터(Bloom filter)는 집합 안에 항목이 존재하는지 확인하는 확률적 데이터 구조(probabilistic data structure)예요. Redis Open Source 안에서 고정된 크기의 매우 작은 메모리 공간으로 요소가 집합에 존재하는지 확인할 수 있게 해주죠. 이 페이지에서는 블룸 필터의 원리와 사용 사례, 크기 조정 방법을 설명해 드릴게요.
블룸 필터란 (What is a Bloom filter)
집합의 모든 항목을 저장하는 대신, 블룸 필터는 항목들의 해시 표현(hash representation)만 저장해요. 그래서 일부 정밀도를 희생하죠. 트레이드오프는 블룸 필터가 매우 공간 효율적이고 빠르다는 점이에요.
블룸 필터는 집합에서 항목의 부재를 보장할 수 있지만, 존재에 대해서는 추정(estimation)만 제공해요. 즉, 항목이 집합에 없다고 응답하면(부정 답변) 확실히 그렇다는 뜻이에요. 하지만 N개의 긍정 답변 중 1개는 틀릴 수 있어요. 언뜻 이상해 보이지만 이런 종류의 불확실성도 컴퓨터 과학에서 자리 잡을 데가 있어요. 부정 답변이 더 비싼 연산을 막아주는 경우가 많은데, 예를 들어 사용자 이름이 이미 사용 중인지, 신용카드가 도난 신고됐는지, 사용자가 이미 광고를 봤는지 등을 확인할 때죠.
사용 사례 (Use cases)
금융 사기 탐지 (Financial fraud detection)
"이 사용자가 이전에 이 위치에서 결제한 적이 있나?"라는 질문에 답하며, 사용자의 쇼핑 습관에서 의심스러운 활동을 확인해요.
사용자마다 블룸 필터 하나를 두고 모든 거래에 대해 확인해요. 매우 빠른 응답(로컬 지연 시간)을 제공하고, 사용자가 이동할 경우를 대비해 다른 지역에 복제해요. 규모가 커져도 성능 저하를 막을 수 있죠.
Redis 블룸 필터를 이 애플리케이션에 사용하면 다음과 같은 이점이 있어요:
- 빠른 거래 완료
- 네트워크 분할 시 거래가 중단될 가능성 감소(연결을 더 짧은 시간 동안 열어두면 되므로)
- 카드 소유자와 판매자 모두에게 추가 보안 계층 제공
금융 업계에서 블룸 필터가 도와줄 수 있는 다른 질문들:
- 사용자가 이 제품/서비스 카테고리에서 구매한 적이 있는가?
- 사용자가 검증된 온라인 상점(Amazon, Apple 앱 스토어 같은 대형 소매점)에서 구매할 때 일부 보안 단계를 건너뛰어도 되는가?
- 이 신용카드가 분실/도난 신고됐는가? 마지막 사례에서 블룸 필터를 쓰는 추가 이점은 금융 기관이 카드 번호 자체를 노출하지 않고 도난/차단된 신용카드 번호 목록을 교환할 수 있다는 점이에요.
광고 배치 (Ad placement)
다음 질문에 답해요:
- 사용자가 이미 이 광고를 봤는가?
- 사용자가 이미 이 제품을 샀는가?
사용자마다 블룸 필터를 두고 구매한 모든 제품을 저장해요. 추천 엔진이 새 제품을 제안하고 그 제품이 사용자의 블룸 필터에 있는지 확인해요.
- 없다면 광고가 사용자에게 표시되고 블룸 필터에 추가돼요.
- 있다면 프로세스가 다시 시작되어 필터에 없는 제품을 찾을 때까지 반복해요.
이점: 맞춤형 근실시간(near real-time) 경험을 위한 비용 효율적인 방법, 비싼 인프라에 투자할 필요 없음.
사용자 이름 중복 확인 (Check if a username is taken)
"이 사용자 이름/이메일/도메인 이름/slug이 이미 사용됐는가?"라는 질문에 답해요.
가입한 모든 사용자 이름마다 블룸 필터를 사용해요. 새 사용자가 원하는 사용자 이름을 입력하면 앱이 블룸 필터에 그 사용자 이름이 존재하는지 확인해요.
- 없다면 사용자가 생성되고 사용자 이름이 블룸 필터에 추가돼요.
- 있다면 앱은 메인 데이터베이스를 확인하거나 사용자 이름을 거부할 수 있어요.
쿼리 시간은 규모가 커져도 동일하게 유지돼요. 이점: 일반적인 작업을 위한 매우 빠르고 효율적인 방법, 비싼 인프라에 투자할 필요 없음.
예시 (Example)
백만 가지의 다른 자전거 종류를 만드는 자전거 제조사를 생각해 보세요. 새 모델에서 중복 모델명을 피하고 싶다면 블룸 필터로 중복을 감지할 수 있어요. 아래 예시에서는 백만 개 항목을 위한 공간과 0.1% 오류율을 가진 필터를 만들게요. 모델명 하나를 추가하고 존재하는지 확인한 다음, 여러 모델명을 추가하고 존재하는지 확인해요.
블룸 필터 연산: BF.RESERVE로 필터를 만들고, BF.ADD와 BF.MADD로 항목을 추가하며, BF.EXISTS와 BF.MEXISTS로 멤버십을 확인해요 — 공간 효율적인 확률적 집합 멤버십 테스트가 필요할 때 쓰죠.
res1 = r.bf().reserve("bikes:models", 0.01, 1000)
print(res1) # >>> True
res2 = r.bf().add("bikes:models", "Smoky Mountain Striker")
print(res2) # >>> True
res3 = r.bf().exists("bikes:models", "Smoky Mountain Striker")
print(res3) # >>> True
res4 = r.bf().madd("bikes:models", "Rocky Mountain Racer", "Cloudy City Cruiser", "Windy City Wippet")
print(res4) # >>> [True, True, True]
res5 = r.bf().mexists("bikes:models", "Rocky Mountain Racer", "Cloudy City Cruiser", "Windy City Wippet")
print(res5) # >>> [True, True, True]
const res1 = await client.bf.reserve('bikes:models', 0.01, 1000);
console.log(res1); // >>> OK
const res2 = await client.bf.add('bikes:models', 'Smoky Mountain Striker');
console.log(res2); // >>> true
const res3 = await client.bf.exists('bikes:models', 'Smoky Mountain Striker');
console.log(res3); // >>> true
const res4 = await client.bf.mAdd('bikes:models', ['Rocky Mountain Racer', 'Cloudy City Cruiser', 'Windy City Wippet']);
console.log(res4); // >>> [true, true, true]
const res5 = await client.bf.mExists('bikes:models', ['Rocky Mountain Racer', 'Cloudy City Cruiser', 'Windy City Wippet']);
console.log(res5); // >>> [true, true, true]
String res1 = jedis.bfReserve("bikes:models", 0.01, 1000);
System.out.println(res1); // >>> OK
boolean res2 = jedis.bfAdd("bikes:models", "Smoky Mountain Striker");
System.out.println(res2); // >>> True
boolean res3 = jedis.bfExists("bikes:models", "Smoky Mountain Striker");
System.out.println(res3); // >>> True
List<Boolean> res4 = jedis.bfMAdd("bikes:models", "Rocky Mountain Racer", "Cloudy City Cruiser", "Windy City Wippet");
System.out.println(res4); // >>> [True, True, True]
List<Boolean> res5 = jedis.bfMExists("bikes:models", "Rocky Mountain Racer", "Cloudy City Cruiser", "Windy City Wippet");
System.out.println(res5); // >>> [True, True, True]
res1, err := rdb.BFReserve(ctx, "bikes:models", 0.01, 1000).Result()
if err != nil {
panic(err)
}
fmt.Println(res1) // >>> OK
res2, err := rdb.BFAdd(ctx, "bikes:models", "Smoky Mountain Striker").Result()
if err != nil {
panic(err)
}
fmt.Println(res2) // >>> true
res3, err := rdb.BFExists(ctx, "bikes:models", "Smoky Mountain Striker").Result()
if err != nil {
panic(err)
}
fmt.Println(res3) // >>> true
res4, err := rdb.BFMAdd(ctx, "bikes:models", "Rocky Mountain Racer", "Cloudy City Cruiser", "Windy City Wippet").Result()
if err != nil {
panic(err)
}
fmt.Println(res4) // >>> [true true true]
res5, err := rdb.BFMExists(ctx, "bikes:models", "Rocky Mountain Racer", "Cloudy City Cruiser", "Windy City Wippet").Result()
if err != nil {
panic(err)
}
fmt.Println(res5) // >>> [true true true]
bool res1 = db.BF().Reserve("bikes:models", 0.01, 1000);
Console.WriteLine(res1); // >>> True
bool res2 = db.BF().Add("bikes:models", "Smoky Mountain Striker");
Console.WriteLine(res2); // >>> True
bool res3 = db.BF().Exists("bikes:models", "Smoky Mountain Striker");
Console.WriteLine(res3); // >>> True
bool[] res4 = db.BF().MAdd("bikes:models", new RedisValue[]{"Rocky Mountain Racer", "Cloudy City Cruiser", "Windy City Wippet"});
Console.WriteLine(string.Join(", ", res4)); // >>> True, True, True
bool[] res5 = db.BF().MExists("bikes:models", ["Rocky Mountain Racer", "Cloudy City Cruiser", "Windy City Wippet"]);
Console.WriteLine(string.Join(", ", res5)); // >>> True, True, True
C#-Sync (NRedisStack) Quick-Start
$res1 = $r->bfreserve('bikes:models', 0.01, 1000);
echo $res1 . PHP_EOL; // >>> OK
$res2 = $r->bfadd('bikes:models', 'Smoky Mountain Striker');
echo $res2 . PHP_EOL; // >>> 1
$res3 = $r->bfexists('bikes:models', 'Smoky Mountain Striker');
echo $res3 . PHP_EOL; // >>> 1
$res4 = $r->bfmadd('bikes:models', 'Rocky Mountain Racer', 'Cloudy City Cruiser', 'Windy City Wippet');
echo json_encode($res4) . PHP_EOL; // >>> [1,1,1]
$res5 = $r->bfmexists('bikes:models', 'Rocky Mountain Racer', 'Cloudy City Cruiser', 'Windy City Wippet');
echo json_encode($res5) . PHP_EOL; // >>> [1,1,1]
let _ : () = r.bf_reserve("bikes:models", 0.001, 1_000_000).expect("Failed to reserve Bloom filter");
println!("OK"); // >>> OK
let res1: bool = r.bf_add("bikes:models", "Smoky Mountain Striker").expect("Failed to add item to Bloom filter");
println!("{res1}"); // >>> true
let res2: bool = r.bf_exists("bikes:models", "Smoky Mountain Striker").expect("Failed to check item in Bloom filter");
println!("{res2}"); // >>> true
let res3: Vec<bool> = r.bf_madd("bikes:models", &["Rocky Mountain Racer", "Cloudy City Cruiser", "Windy City Wippet"]).expect("Failed to add items to Bloom filter");
println!("{res3:?}"); // >>> [true, true, true]
let res4: Vec<bool> = r.bf_mexists("bikes:models", &["Rocky Mountain Racer", "Cloudy City Cruiser", "Windy City Wippet"]).expect("Failed to check items in Bloom filter");
println!("{res4:?}"); // >>> [true, true, true]
let _ : () = r.bf_reserve("bikes:models", 0.001, 1_000_000).await.expect("Failed to reserve Bloom filter");
println!("OK"); // >>> OK
let res1: bool = r.bf_add("bikes:models", "Smoky Mountain Striker").await.expect("Failed to add item to Bloom filter");
println!("{res1}"); // >>> true
let res2: bool = r.bf_exists("bikes:models", "Smoky Mountain Striker").await.expect("Failed to check item in Bloom filter");
println!("{res2}"); // >>> true
let res3: Vec<bool> = r.bf_madd("bikes:models", &["Rocky Mountain Racer", "Cloudy City Cruiser", "Windy City Wippet"]).await.expect("Failed to add items to Bloom filter");
println!("{res3:?}"); // >>> [true, true, true]
let res4: Vec<bool> = r.bf_mexists("bikes:models", &["Rocky Mountain Racer", "Cloudy City Cruiser", "Windy City Wippet"]).await.expect("Failed to check items in Bloom filter");
println!("{res4:?}"); // >>> [true, true, true]
참고: 항목이 몇 개뿐이더라도 false positive(거짓 긍정)가 발생할 가능성은 항상 있어요. 즉, 명시적으로 추가되지 않았는데도 항목이 "존재"할 수 있죠. 블룸 필터의 확률적 특성을 더 깊이 이해하려면 이 페이지 하단에 링크된 블로그 글을 참고하세요.
블룸 필터 예약하기 (Reserving Bloom filters)
Redis 블룸 필터를 사용하면 크기 조정 작업의 대부분이 자동으로 처리돼요.
BF.RESERVE {key} {error_rate} {capacity} [EXPANSION expansion] [NONSCALING]
1. 거짓 긍정률 (error_rate)
이 비율은 0과 1 사이의 십진수 값이에요. 예를 들어 원하는 거짓 긍정률이 0.1%(1000분의 1)라면 error_rate는 0.001로 설정해야 해요.
2. 예상 용량 (capacity)
이는 필터에 총 몇 개의 항목이 들어갈 것으로 예상하는지에 대한 숫자예요. 정적 집합이라면 쉬운데, 집합이 시간이 지나며 커지면 더 어려워져요. **초과 크기(oversize)**로 잡으면 메모리를 낭비하고, **부족 크기(undersize)**로 잡으면 필터가 가득 차서 그 위에 새 필터를 쌓아야 해요(서브필터 스태킹). 필터가 여러 서브필터로 구성된 경우 추가(add) 지연 시간은 동일하게 유지되지만 존재 확인(checks) 지연 시간은 증가해요. 확인이 먼저 최상위(가장 최근) 필터에서 수행되고, 부정 답변이 반환되면 다음 필터를 확인하는 방식이라 그렇죠. 여기서 추가 지연 시간이 발생해요.
3. 스케일링 (EXPANSION)
블룸 필터에 항목을 추가하는 것은 데이터 구조가 "가득 차는" 것 때문에 실패하지 않아요. 대신 오류율이 증가하기 시작하죠. 오류를 필터 초기화 시 설정한 값에 가깝게 유지하기 위해 블룸 필터는 자동으로 스케일링돼요. 즉, 용량에 도달하면 추가 서브필터가 생성돼요.
새 서브필터의 크기는 마지막 서브필터 크기에 EXPANSION을 곱한 값이에요. 필터에 저장될 항목 수를 모른다면, 서브필터 수를 줄이기 위해 expansion을 2 이상 사용하는 걸 권장해요. 그렇지 않으면 메모리 소비를 줄이기 위해 expansion을 1로 사용하는 걸 권장해요. 기본 expansion 값은 2예요.
필터는 원하는 오류율을 유지하기 위해 새 서브필터마다 해시 함수를 더 추가해요.
"어차피 스케일할 거면 왜 높은 expansion으로 작은 필터를 만드는 거지?"라고 궁금할 수 있어요. 답은: 많은 필터를 유지해야 하는 경우(예: 사용자당 또는 제품당 필터)이고, 대부분은 작게 유지되지만 활동이 많은 일부는 스케일해야 하기 때문이에요.
4. NONSCALING
스케일할 계획이 없다면 NONSCALING 플래그를 쓰세요. 그러면 필터가 해시 함수를 하나 덜 사용해요. 다만 처음에 할당된 용량에 도달하면 오류율이 증가하기 시작한다는 것을 기억하세요.
블룸 필터의 총 크기 (Total size of a Bloom filter)
블룸 필터가 실제로 사용하는 메모리는 선택한 오류율의 함수예요.
최적의 해시 함수 수는 ceil(-ln(error_rate) / ln(2))예요.
원하는 error_rate와 최적의 해시 함수 수가 주어졌을 때 항목당 필요한 비트 수는 -ln(error_rate) / ln(2)^2예요. 따라서 필터에 필요한 비트 수는 capacity * -ln(error_rate) / ln(2)^2이에요.
- 1% 오류율은 해시 함수 7개와 항목당 9.585비트가 필요해요.
- 0.1% 오류율은 해시 함수 10개와 항목당 14.378비트가 필요해요.
- 0.01% 오류율은 해시 함수 14개와 항목당 19.170비트가 필요해요.
비교를 위해, Redis set을 멤버십 테스트에 사용할 때 필요한 메모리는:
memory_with_sets = capacity*(192b + value)
예를 들어 IP 주소 집합이라면 항목당 약 40바이트(320비트)가 되는데, 이는 0.01% 거짓 긍정률의 블룸 필터에 필요한 19.170비트보다 훨씬 높아요.
블룸 vs 쿠쿠 필터 (Bloom vs. Cuckoo filters)
블룸 필터는 일반적으로 항목 삽입 시 더 나은 성능과 확장성을 보여줘요(데이터셋에 자주 항목을 추가한다면 블룸 필터가 이상적일 수 있어요). 쿠쿠 필터는 확인(check) 연산이 더 빠르고 삭제도 허용해요.
성능 (Performance)
블룸 필터에서 삽입은 O(K)이며, 여기서 k는 해시 함수 수예요. 항목 확인은 O(K) 또는 스택된 필터의 경우 O(K*n)이며, 여기서 n은 스택된 필터 수예요.
학술 자료 (Academic sources)
참고 자료 (References)
웨비나 (Webinars)
블로그 글 (Blog posts)
- RedisBloom Quick Start Tutorial
- Developing with Bloom Filters
- RedisBloom on Redis Software
- Probably and No: Redis, RedisBloom, and Bloom Filters