블룸 필터

블룸 필터 (Bloom filter)

블룸 필터는 Redis가 제공하는 확률적 데이터 구조 중 하나예요. 아이템이 집합(set) 안에 존재하는지, 아주 작은 고정 크기의 메모리만으로 확인할 수 있게 해주죠. 이번 페이지에서는 블룸 필터가 왜 이렇게 메모리를 아끼면서 빠른지, 실제로 어떻게 쓰는지, 그리고 어떤 한계가 있는지를 하나씩 살펴볼게요.

출처: Redis 공식 문서 — Bloom filter

블룸 필터는 어떻게 동작하나요?

Redis Open Source의 블룸 필터(probabilistic data structure)를 쓰면, 아이템이 집합 안에 존재하는지 아주 작고 고정된 크기의 메모리 공간으로 확인할 수 있어요.

집합의 모든 아이템을 통째로 저장하는 대신, 블룸 필터는 아이템의 해시(Hash)된 표현만 저장해요. 덕분에 정확도(precision)를 조금 희생하는 대신, 매우 공간 효율적이고 빨라지는 거죠.

여기서 중요한 특징이 있어요.

  • 블룸 필터는 "아이템이 집합에 없다"는 것을 보장할 수 있어요.
  • 하지만 "아이템이 집합에 있다"는 것은 **추정(estimation)**만 가능해요.

즉, "없다(negative)"라고 답하면 그건 100% 확실하지만, N번의 "있다(positive)" 응답 중 1번 정도는 틀릴 수 있어요. 처음에는 좀 이상해 보일 수 있는데, 이런 형태의 불확실성은 컴퓨터 과학에서 충분히 유용하게 쓰여요.

  • 높은 비용의 작업을 막아주는 "없다"라는 답: 예를 들어 이미 사용 중인 사용자 이름인지, 신고된 도난 신용카드인지, 사용자가 이미 본 광고인지 등을 확인할 때요.

사용 사례 (Use cases)

금융 사기 탐지 (Financial fraud detection, finance)

"이 사용자가 이전에 이 위치에서 결제한 적이 있나?" 같은 질문에 답하며, 사용자의 비정상적인 쇼핑 패턴을 확인하는 용도로 써요.

  • 사용자마다 블룸 필터 하나를 두고, 모든 거래마다 확인해요.
  • 매우 빠른 응답(로컬 레이턴시)을 제공해요.
  • 사용자가 이동했을 때를 대비해 여러 리전에 복제할 수 있어요.
  • 규모가 커져도 성능 저하를 막아줘요.

이런 애플리케이션에 Redis 블룸 필터를 쓰면 다음과 같은 이점이 있어요.

  • 거래 완료가 빨라져요.
  • 네트워크 파티션이 발생해도 거래가 끊길 가능성이 줄어들어요(연결 유지 시간이 짧아지니까요).
  • 카드 소유자와 판매자 양쪽에 보안 레이어가 하나 더 생겨요.

금융 업계에서 블룸 필터로 답할 수 있는 다른 질문들도 있어요.

  • 사용자가 이 카테고리의 제품/서비스를 구매한 적이 있나요?
  • 검증된 온라인 샵(Amazon, Apple app store 같은 대형 리테일러)에서 구매할 때 보안 단계를 일부 생략해도 되나요?
  • 이 신용카드가 분실/도난 신고된 적이 있나요? 특히 이 경우 블룸 필터를 쓰면, 금융 기관들이 카드 번호 자체를 공개하지 않고도 도난/차단된 카드 번호 목록을 교환할 수 있다는 추가 이점이 있어요.

광고 배치 (Ad placement, retail, advertising)

다음 질문에 답하는 용도로 써요.

  • 사용자가 이미 이 광고를 봤나요?
  • 사용자가 이미 이 제품을 샀나요?

사용자마다 블룸 필터를 하나씩 두고, 구매한 모든 제품을 저장해요. 추천 엔진이 새 제품을 추천하면, 그 제품이 사용자의 블룸 필터에 있는지 확인하죠.

  • 없다면 → 광고를 보여주고 블룸 필터에 추가해요.
  • 있다면 → 없는 제품을 찾을 때까지 과정을 반복해요.

이런 애플리케이션에 Redis 블룸 필터를 쓰면:

  • 거의 실시간에 가까운 맞춤 경험을 비용 효율적으로 제공할 수 있어요.
  • 비싼 인프라에 투자할 필요가 없어요.

사용자 이름 중복 확인 (SaaS, 콘텐츠 게시 플랫폼)

"이 사용자 이름/이메일/도메인 이름/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]

CLI로는 이렇게 해요.

> BF.RESERVE bikes:models 0.01 1000
OK
> BF.ADD bikes:models "Smoky Mountain Striker"
(integer) 1
> BF.EXISTS bikes:models "Smoky Mountain Striker"
(integer) 1
> BF.MADD bikes:models "Rocky Mountain Racer" "Cloudy City Cruiser" "Windy City Wippet"
1) (integer) 1
2) (integer) 1
3) (integer) 1
> BF.MEXISTS bikes:models "Rocky Mountain Racer" "Cloudy City Cruiser" "Windy City Wippet"
1) (integer) 1
2) (integer) 1
3) (integer) 1

BF.RESERVE의 인자는 key, error_rate, capacity 순서예요. 위 예제에서는 오차율 0.01(1%)과 용량 1000을 지정했어요. 각 언어별 클라이언트(redis-py, node-redis, Jedis, go-redis, NRedisStack, Predis, redis-rs 등)에서도 동일한 연산을 제공해요. 자세한 사용법은 각 언어의 Quick-Start 문서를 참고하면 됩니다.

크기 조정과 확장

1. 용량 (Capacity)

필터의 용량은 아이템 개수로 표현돼요. 필터가 가득 차면, 새 아이템을 추가해도 오류는 발생하지 않지만 오차율(error rate)이 커지기 시작해요.

2. 확장 (EXPANSION)

블룸 필터에 아이템을 추가할 때 "가득 찼다"는 이유로 실패하는 일은 없어요. 대신 오차율이 증가하기 시작하죠. 필터 초기화 때 설정한 오차율에 가깝게 유지하기 위해, 블룸 필터는 **자동 확장(auto-scale)**을 해요. 용량에 도달하면 추가 서브 필터(sub-filter)가 생성되는 거예요.

새 서브 필터의 크기는 이전 서브 필터 크기에 EXPANSION을 곱한 값이에요.

  • 필터에 저장할 아이템 수를 모른다면, EXPANSION을 2 이상으로 설정해 서브 필터 개수를 줄이는 걸 권장해요.
  • 반대로 메모리 사용을 줄이고 싶다면 EXPANSION을 1로 설정하는 걸 권장해요.
  • 기본값은 2예요.

새로운 서브 필터가 생길 때마다 원하는 오차율을 유지하기 위해 해시 함수의 개수도 계속 늘어나요.

혹시 "어차피 확장할 거라면 왜 작은 필터에 높은 확장률을 설정하죠?"라고 궁금할 수 있는데, 그 이유는 필터를 많이 유지해야 하는 경우를 위한 거예요. 사용자별 또는 제품별로 필터가 있고, 대부분은 작게 유지되지만 일부는 활동이 많아서 확장해야 하는 상황을 생각해 보면 돼요.

3. NONSCALING

확장할 필요가 없다는 걸 안다면 NONSCALING 플래그를 쓰면 돼요. 이러면 해시 함수를 하나 덜 사용하기 때문이에요. 다만 처음에 할당한 용량에 도달하면 오차율이 커지기 시작한다는 점을 기억해야 해요.

블룸 필터의 총 크기

블룸 필터가 실제로 사용하는 메모리는 선택한 오차율에 따라 결정돼요.

  • 최적 해시 함수 개수는 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% 오탐(false positive) 오차율의 블룸 필터가 쓰는 19.170 비트보다 훨씬 큰 값이죠.

블룸 필터 vs 쿠쿠 필터 (Bloom vs. Cuckoo filters)

  • 블룸 필터는 아이템 삽입에서 일반적으로 더 나은 성능과 확장성을 보여줘요. 데이터셋에 아이템을 자주 추가한다면 블룸 필터가 이상적일 수 있어요.
  • 쿠쿠 필터는 확인 연산이 더 빠르고, 삭제도 가능해요.

성능 (Performance)

  • 블룸 필터에서 삽입(Insertion)은 O(K) 이에요. 여기서 k는 해시 함수 개수예요.
  • 아이템 확인(Checking)은 O(K) 이며, 필터가 쌓여 있는(stacked) 경우에는 O(K*n) 이에요. n은 쌓인 필터 개수예요.

학술 자료 (Academic sources)

더 알아보기 (Learn more)