Bloom Filter: 원리, 사용법, 장단점 및 Python 구현

I. 사용법 및 응용 시나리오

Bloom Filter는 요소가 집합에 속하는지 여부를 결정하는 데 사용되는 매우 공간 효율적인 확률적 데이터 구조입니다. 많은 분야에서 광범위하게 응용됩니다.

1. 워드 프로세싱 소프트웨어의 철자 검사: 워드 프로세싱 소프트웨어에서 영어 단어의 철자가 올바른지 빠르게 확인할 수 있습니다. 예를 들어, 사용자가 단어를 입력하면 Bloom Filter는 해당 단어가 올바른 단어 집합에 있을 가능성이 있는지 신속하게 판단할 수 있습니다. 그렇지 않은 경우 철자 오류를 알려줍니다.
2. FBI 용의자 목록 쿼리: FBI와 같은 기관에서 용의자의 이름이 이미 용의자 목록에 있는지 신속하게 판단하는 데 사용할 수 있습니다. 새로운 용의자 정보를 사용할 수 있을 때 초기 스크리닝을 통해 효율성을 빠르게 향상시킬 수 있습니다.
3. 웹 크롤러 URL 액세스 판단: 웹 크롤러에서 URL을 방문했는지 효율적으로 판단할 수 있습니다. 이는 동일한 URL에 대한 반복적인 액세스를 방지하고 리소스를 절약합니다.
4. 이메일 스팸 필터링: Yahoo 및 Gmail과 같은 이메일 서비스의 이메일 스팸 필터링 기능은 Bloom Filter를 사용하여 이메일이 스팸인지 판단할 수 있습니다. 먼저 일부 기능을 사용하여 이메일이 스팸일 가능성이 있는지 판단합니다. 그렇다면 추가 처리를 수행합니다.
5. 캐시 침투 방지: 캐시 시스템에서 Bloom Filter는 캐시 침투 문제를 방지할 수 있습니다. 많은 수의 요청이 동시에 캐시에 존재하지 않는 데이터에 액세스하면 데이터베이스에 과도한 부담을 줄 수 있습니다. Bloom Filter는 먼저 데이터가 존재할 가능성이 있는지 판단할 수 있습니다. 그렇지 않은 경우 유효하지 않은 데이터베이스 쿼리를 방지하면서 직접 반환합니다.

II. 알고리즘의 장단점

(I) 장점

1. 작은 데이터 공간: Bloom Filter는 데이터 자체를 저장할 필요가 없습니다. 대신 비트 배열과 해시 함수를 사용하여 데이터의 존재를 표시하므로 저장 공간을 크게 절약할 수 있습니다. 모든 요소를 저장하는 기존 방식과 비교할 때 많은 양의 데이터를 저장할 때 분명한 이점이 있습니다.

(II) 단점

1. 오판의 존재: 일치에 실패하면 요소가 "세트에 확실히 없음"을 결정할 수 있지만, 일치가 성공하더라도 값이 세트에 확실히 있다고 보장하지 않습니다. 일정한 오탐지 확률이 있습니다. 이는 해시 함수에 의해 매핑된 후 다른 요소가 비트 배열에서 동일한 비트 위치를 차지할 수 있기 때문입니다.
2. 요소를 삭제할 수 없음: 요소가 세트에 추가되면 삭제할 수 없습니다. 특정 요소를 삭제하면 Bloom Filter를 재구축하지 않는 한 다른 요소의 판단 결과에 영향을 줄 수 있습니다.
3. 용량에 따른 오탐지율 변화: 세트가 거의 꽉 찼을 때, 즉 예상 최대 용량에 가까워지면 오탐지 확률이 증가합니다. 이는 비트 배열에서 1로 설정된 비트 수가 증가하여 오판의 가능성이 높아지기 때문입니다.
4. 확대된 공간 점유율: 일반적으로 1%의 오탐지 확률의 경우 각 요소는 10비트 미만이 필요하며 이는 세트의 크기 또는 요소 수와 무관합니다. 공간 절약적이지만 대규모 데이터의 경우 전체 공간 점유율은 여전히 클 수 있습니다.
5. 느린 쿼리 프로세스: 여러 해시 함수를 사용하기 때문에 각 일치 프로세스는 존재를 확인하기 위해 여러 비트(해시 수)를 확인해야 하므로 쿼리 프로세스가 느려집니다.

III. 원리 소개

(I) 알고리즘 원리

Bloom Filter는 세트에 특정 요소가 포함되어 있는지 판단하는 알고리즘입니다. 데이터 자체를 저장할 필요는 없지만 매우 큰 비트 배열과 몇 가지 해시 함수를 통해 구현됩니다.

비트 배열의 길이가 (m)이고 해시 함수의 수가 (k)라고 가정합니다. 먼저 각 비트를 0으로 설정하여 비트 배열을 초기화합니다.

요소가 세트에 추가되면 입력 문자열은 해시 함수를 통해 비트 배열의 하위 스크립트로 매핑된 다음 하위 스크립트에 해당하는 값이 1로 설정됩니다. 예를 들어, 문자열의 경우 (k) 해시 함수로 계산한 후 (k) 하위 스크립트 위치가 획득되고 이러한 (k) 위치의 비트가 모두 1로 설정됩니다. 동일한 문자열을 두 번째로 계산하면 해시 함수에 의해 동일한 하위 스크립트 위치로 매핑됩니다.

요소가 존재하는지 쿼리할 때 요소는 동일한 (k) 해시 함수를 통해 비트 배열의 (k) 포인트로 매핑됩니다. 이러한 (k) 포인트 중 하나가 1이 아니면 요소가 세트에 존재하지 않는다고 판단할 수 있습니다. 반대로 (k) 포인트가 모두 1이면 요소가 세트에 존재할 수 있습니다. 요소가 세트에 반드시 존재한다고 판단할 수 없으며, 일정한 오탐지율이 있습니다.

예를 들어, 세트에 3개의 요소 ({x, y, z})가 있고 해시 함수 수가 3이라고 가정합니다. 세트의 각 요소에 대해 3개의 해시 함수를 통해 요소를 연속적으로 매핑합니다. 각 매핑은 비트 배열의 점에 해당하는 해시 값을 생성한 다음 비트 배열의 해당 위치를 1로 표시합니다. 요소 (W)가 세트에 존재하는지 쿼리할 때 (W)는 동일한 방법을 통해 비트 배열의 3개의 포인트로 매핑됩니다. 3개의 포인트 중 하나가 1이 아니면 요소가 세트에 존재하지 않는다고 판단할 수 있습니다. 반대로 3개의 포인트가 모두 1이면 요소가 세트에 존재할 수 있습니다. 그림에서 볼 수 있듯이 특정 요소가 매핑을 통해 하위 스크립트 4, 5, 6으로 매핑된다고 가정합니다. 이러한 3개의 포인트가 모두 1이지만 이러한 3개의 포인트는 해싱을 통해 다른 요소가 획득한 위치입니다. 따라서 이 상황은 요소가 세트에 없지만 해당 비트가 모두 1일 수 있음을 보여주며, 이는 오탐지율이 존재하는 이유입니다.

(II) 간단한 Python 구현

다음은 BloomFilter의 Python 코드 구현 예일 뿐입니다. 실제 BloomFilter 구현은 초기화된 비트 배열의 길이에 따라 해시 함수 수를 결정해야 하며 복잡한 해싱 프로세스도 수행해야 합니다.

#_*_coding:utf_8_
import BitVector
import os
import sys


class SimpleHash():
    def __init__(self, cap, seed):
        self.cap = cap
        self.seed = seed

    def hash(self, value):
        ret = 0
        for i in range(len(value)):
            # weighted sum
            ret += self.seed * ret + ord(value[i])
        # bit operation to ensure the final value is between 0 and self.cap
        return (self.cap - 1) & ret


class BloomFilter():
    def __init__(self, BIT_SIZE=1 << 25):
        self.BIT_SIZE = 1 << 25
        self.seeds = [5, 7, 11, 13, 31, 37, 61]
        self.bitset = BitVector.BitVector(size=self.BIT_SIZE)
        self.hashFunc = []

        for i in range(len(self.seeds)):
            self.hashFunc.append(SimpleHash(self.BIT_SIZE, self.seeds[i]))
        print(self.hashFunc)

    def insert(self, value):
        for f in self.hashFunc:
            loc = f.hash(value)
            self.bitset[loc] = 1
        print(self.bitset)

    def is_contaions(self, value):
        if value == None:
            return False
        ret = True
        for f in self.hashFunc:
            loc = f.hash(value)
            ret = ret & self.bitset[loc]
        return ret

위의 코드에서 SimpleHash 클래스는 간단한 해시 함수를 구현하고 BloomFilter 클래스는 비트 배열과 여러 해시 함수를 초기화하여 요소 삽입 및 존재 판단 기능을 구현합니다. insert 메서드는 요소를 Bloom Filter에 삽입하는 데 사용되고 is_contaions 메서드는 요소가 Bloom Filter에 존재하는지 판단하는 데 사용됩니다.

Leapcell: Python 웹 호스팅을 위한 최고의 서버리스 플랫폼

마지막으로 Python 서비스를 배포하기 위한 최고의 플랫폼인 Leapcell을 소개합니다.

1. 다국어 지원

• JavaScript, Python, Go 또는 Rust로 개발합니다.

2. 무제한 프로젝트를 무료로 배포

• 사용량에 따라서만 지불하고 요청이나 요금은 없습니다.

3. 최고의 비용 효율성

• 유휴 요금 없이 사용량에 따라 지불합니다.
• 예: $25는 평균 응답 시간 60ms에서 694만 건의 요청을 지원합니다.

4. 간소화된 개발자 경험

• 간편한 설정을 위한 직관적인 UI.
• 완전 자동화된 CI/CD 파이프라인 및 GitOps 통합.
• 실행 가능한 통찰력을 위한 실시간 지표 및 로깅.

5. 간편한 확장성 및 고성능

• 고도의 동시성을 쉽게 처리할 수 있도록 자동 확장.
• 운영 오버헤드가 없으므로 구축에만 집중하면 됩니다.

설명서에서 더 자세히 알아보세요!

Leapcell Twitter: https://x.com/LeapcellHQ