[Golang] 블룸필터(Bloom Filter)의 설명과 구현

블룸필터(Bloom Filter)

 

1. 블룸필터란?

블룸 필터(Bloom Filter)는 매우 효율적인 확률적 자료 구조로, 어떤 원소가 집합에 속하는지 아닌지를 빠르게 확인할 수 있습니다. 이는 일반적으로 많은 양의 데이터 중에서 어떤 원소가 존재하는지 확인하는 데 사용됩니다. 블룸 필터는 확률적인 방법을 사용하기 때문에 100% 정확하지는 않지만, 그럼에도 불구하고 매우 효율적으로 작동하며 고정된 메모리를 사용합니다.

블룸 필터의 주요 특징과 동작 방식에 대한 상세 설명은 다음과 같습니다:

1. 비트 배열 사용: 블룸 필터는 주로 비트 배열을 사용하여 데이터를 저장합니다. 비트 배열은 모든 비트가 0으로 초기화되어 있습니다.
2. 해시 함수 사용: 블룸 필터는 하나 이상의 해시 함수를 사용하여 입력 데이터를 여러 위치로 매핑합니다. 각 해시 함수는 서로 다른 비트의 위치에 대응됩니다. 이 해시 함수들은 일반적으로 서로 독립적이며, 무작위성이 필요합니다.
3. 삽입(Operation - Insertion): 새로운 원소를 블룸 필터에 삽입할 때, 해당 원소를 여러 해시 함수에 적용하여 얻은 위치에 해당하는 비트를 1로 설정합니다.
4. 쿼리(Operation - Query): 어떤 원소가 블룸 필터에 속해 있는지 확인하고자 할 때, 해당 원소를 해시 함수에 적용하여 얻은 위치에 해당하는 비트를 확인합니다. 모든 해당하는 비트가 1이면 "있을 가능성이 있다"고 판단하며, 하나라도 0이면 "없다"고 판단합니다.
5. 확률적 정확성: 블룸 필터는 확률적으로 동작하기 때문에, 어떤 원소가 "있다"고 판단된다고 해도 100% 정확한 정보가 아닙니다. 반면, "없다"고 판단되면 정확한 정보입니다.
6. 메모리 효율성: 블룸 필터는 매우 적은 메모리를 사용하여 많은 양의 데이터를 처리할 수 있습니다. 하지만 그 대신에 일정한 확률로 오검출(false positive)이 발생할 수 있습니다.

블룸 필터는 주로 큰 데이터 집합에서 멤버십 테스트(membership test)를 수행할 때 사용되며, 예를 들어 웹 크롤링, 캐시 관리, 네트워크 라우팅 등 다양한 분야에서 활용됩니다.

 

2. 블룸필터의 간단한 구현

Golang으로 블룸 필터를 구현하려면 hash/fnv 패키지를 사용하여 해시 함수를 만들고, 비트 배열을 조작하는데는 math/big 패키지의 big.Int를 사용할 수 있습니다.

간단한 블룸 필터를 구현하고 사용하는 예제를 만들어보겠습니다.

package main

import (
	"fmt"
	"hash/fnv"
	"math/big"
)

type BloomFilter struct {
	bitArray *big.Int
	size     int
	hashFunc func(data []byte) int
}

func NewBloomFilter(size int, hashFunc func(data []byte) int) *BloomFilter {
	return &BloomFilter{
		bitArray: new(big.Int),
		size:     size,
		hashFunc: hashFunc,
	}
}

func (bf *BloomFilter) Add(data []byte) {
	index := bf.hashFunc(data)
	bf.bitArray.SetBit(bf.bitArray, index, 1)
}

func (bf *BloomFilter) Contains(data []byte) bool {
	index := bf.hashFunc(data)
	return bf.bitArray.Bit(index) == 1
}

- BloomFilter라는 구조체 타입을 정의합니다. 이는 세 가지 필드를 가지고 있습니다:

• bitArray: 비트 배열을 나타내는 big.Int의 포인터입니다.
• size: 비트 배열의 크기를 나타내는 정수입니다.
• hashFunc: 바이트 슬라이스(data)를 입력으로 받아 정수를 반환하는 해시 함수를 가리키는 함수 포인터입니다.

- NewBloomFilter 함수는 새로운 블룸 필터를 생성하는 생성자입니다. 비트 배열의 크기와 해시 함수를 매개변수로 받아 초기화된 BloomFilter 구조체의 포인터를 반환합니다.

- Add 메서드는 블룸 필터에 원소를 추가합니다. 제공된 해시 함수를 사용하여 인덱스를 계산하고, 그에 해당하는 비트를 1로 설정합니다.

- Contains 메서드는 원소가 블룸 필터에 있을 가능성을 확인합니다. 제공된 해시 함수를 사용하여 인덱스를 계산하고, 비트 배열에서 해당하는 비트가 1인지 확인합니다.

위와 같이 만들었다면, 이제 사용해 보도록 하겠습니다.

func main() {
	// 비트 배열 크기와 해시 함수 정의
	bitArraySize := 1024
	hashFunc := func(data []byte) int {
		hash := fnv.New32()
		hash.Write(data)
		return int(hash.Sum32()) % bitArraySize
	}

	// 블룸 필터 생성
	bloomFilter := NewBloomFilter(bitArraySize, hashFunc)

	// 예제 데이터 추가
	data1 := []byte("example1")
	data2 := []byte("example2")

	bloomFilter.Add(data1)

	// 블룸 필터 동작 확인
	fmt.Printf("Contains data1: %v\n", bloomFilter.Contains(data1)) // 예상: true
	fmt.Printf("Contains data2: %v\n", bloomFilter.Contains(data2)) // 예상: false (확률적으로 false positive가 발생할 수 있음)
}

- main 함수에서는 비트 배열의 크기와 해시 함수를 정의합니다. 해시 함수는 입력 데이터에 FNV-1a 해시를 적용하고, 비트 배열 크기로 나누어 나머지를 취하여 인덱스를 얻습니다.

- FNV-1a(Fowler-Noll-Vo)는 짧은 문자열과 작은 정수를 해싱하는 데 빠르고 효율적인 비암호화 해시 함수입니다.

- data1만 Add()메서드를 통해 추가하고, data1과 data2를 각각 검증해 봅니다.