Bloom Filter, 제대로 이해하기 - Java

Bloom Filter의 개념과 특징, 그리고 Java에서의 사용법을 알아보는 것이 본 포스팅의 목표입니다.

 

 

Bloom Filter

Bloom filters는 집합 내에 특정 원소가 존재하는지를 확인할 때 사용되는 자료구조입니다.

Hash Table을 사용해서 원소가 있는지 없는지를 판단하는 것과 비슷합니다.

 

Burton H. Bloom 저의 "Space/Time Trade-offs in Hash Coding with Allowable Errors (1970)" 논문에서 소개되었습니다.

여기서 논문 제목만으로도 아래의 Bloom Filter의 특징을 직접 알 수 있습니다.

 

# 1. 공간/시간의 트레이드 오프

# 2. 해시

# 3. 일부 에러를 허용

 

Bloom Filter는 공간과 시간의 효율성을 위해 일부 에러를 허용하는 해시 함수를 통한 원소의 존재 여부를 확인합니다.

즉 정확성을 희생해서 해시 함수를 사용하여 빠르지만, 해시 함수 특징인 중복을 받아들이는 방식입니다.

 

 

How to work

Bloom Filter는 굉장히 간단한 원리로 동작하는데요,

어떻게 작동하는지 살펴볼게요.

 

먼저, Bloom Filter는 N size의 bit array와 한 개 이상의 Hash Function를 사용합니다.

아래의 그림에서 볼 수 있습니다.

 

https://meetup.toast.com/posts/192



 

하나의 데이터를 여러 개의 Hash Functions을 통해 도출된 값의 bit를 N 사이즈의 bit array에 표시하고,

후에 해당 데이터가 존재하는지를 해당 bit 위치의 표시 유무로 판단합니다.

 

예시를 보면 아주 쉽게 이해할 수 있을거에요.

black IP 집합을 마련하고, 접근하는 IP가 black IP 집합 내에 포함되는 지를 확인해봅시다.

 

 

Example

N을 24로 설정해서 24 사이즈의 bit array와 2개의 Hash Function을 사용해서 Black IP를 사용한다고 가정해봅시다.

 

- bit array of size 24

- 2 hash functions

 

 

 

먼저, black IP 를 Bloom Filter에 추가해야합니다. 

 

hashFunction_1("192.170.0.1") : 2 
hashFunction_2("192.170.0.1") : 6

 

첫 번째 IP가 두 개의 hash function을 통과하면서 2와 6의 숫자를 반환했습니다.

그럼 인덱스 2와 6에 bit를 binary 값 1로 설정합니다.

 

 

다시 한번, 다른 숫자들을 추가해볼게요.

 

hashFunction_1("75.245.10.1") : 4 
hashFunction_2("75.245.10.1") : 10

 

 

hashFunction_1("10.125.22.20") : 10 
hashFunction_2("10.125.22.20") : 19

 

 

자, 이제 인입되는 IP가 black IP인지를 판단해보겠습니다.

IP가 75.245.10.1 일 때를 테스트해볼게요.

 

hashFunction_1("75.245.10.1") : 4 
hashFunction_2("75.245.10.1") : 10

 

bit array를 확인해보면, 아래와 같이 인덱스 4와 10에는 이미 binary 1 로 표시 되어있는 것을 확인할 수 있습니다.

즉, 리스트에 존재한다는 의미입니다.

 

 

이 번엔 75.245.20.30 일 때를 테스트 해볼게요.

 

hashFunction_1("75.245.20.30") : 19 
hashFunction_2("75.245.20.30") : 23

 

리스트에는 19는 binary 1 로 표시되어있지만, 23은 표시되어 있지 않습니다.

등장하지 않았던 IP라는 의미입니다.

 

이 번엔 마지막으로 문제가 되는 상황을 테스트 해볼게요.

만약, IP가 101.125.20.22 일 때, hash functions에서 아래와 같은 값이 나왔다고 해볼게요.

 

hashFunction_1("101.125.20.22") : 19 
hashFunction_2("101.125.20.22") : 2

 

 

 

 

두 인덱스에서 1을 표시하고 있지만, 실제로 한 번도 등장한 적 없던 IP입니다.

이렇게 Bloom Filter는 False Positice을 발생시킬 수 있지만,

위와 같이 Hash-coding을 사용해서 빠르고 공간 효율적이라는 Trade-off를 감안합니다.

 

 

 

False positive

Bloom Filter는 위의 예시와 같이, 존재하지 않는 원소를 존재한다고 판단하는 False Positive의 가능성이 있습니다.

False positive probability(FPP)는 수학적으로 계산이 가능합니다.

 

아래 사이트에서 아이템과 확률 사이 관계를 계산해볼 수 있습니다.

 

 

n : filter에 등록된 아이템

p : false positive의 확률. 0과 1사이의 숫자

m : filter의 bit 수

k : hash function 수

 

 

Hash Function Problems

해시 함수의 중복 문제는 해시 함수의 결과 값 길이를 짧게 지정함에 따라 해시 결과 값이 중복이 될 수 있습니다.

 

가령 이름을 해시 키로 해시 함수를 사용해서 unique한 값을 얻어내려고 할 때를 생각해볼게요.

이 때, 해시 함수의 결과 값의 길이를 2자로 지정했다고 해봅시다.

위 그림의 네 가지 경우에서 John Smith, Sandra Dee 를 해시 함수에 돌렸을 때,

아주 우연히 02 라는 해시 값을 얻었다고 한다면, 해시한 후에 이 둘을 구별할 수 있는 방법이 없습니다.

 

만약 키 값이 10,000개일 때, 혹은 500만개라고 해볼 때,

해시 값의 결과값의 중복이 얼마나 일어날지는 모르지만 적어도 발생한다는 것은 예상할 수 있겠죠?

 

그래서, 보통 충분한 길이로 설정해주곤 합니다.

 

 

 

Hash Table vs Bloom Filter

Hashtable은 주어지는 데이터를 특정한 키로 빠르게 접근하기 위해 Hash function을 사용합니다.

평균 조회 시간이 O(1)이기 때문에, 아주 빠른 탐색이 필요할 때 사용합니다.

가령 Python의 Dictionary와 Java에서 HashTables Class가 바로 HashTables을 구현한 것입니다.

 

Bloom Filter는 한 요소가 주어진 집합에 포함되는지를 테스트하는 공간 효율성을 위한 확률적 자료구조입니다.

단순히 0과 1의 bit set을 통해 존재 여부의 테스트를 위한 데이터 구조입니다.

 

 

✔️ Store Object

Hash table은 해시 함수를 통해 매핑되는 key 값 (인덱스)에 객체를 저장하지만,

Bloom Filter는 객체를 저장하지 않습니다. 

단순히 존재 여부만을 판단하는 목적이기 때문입니다.

 

✔️ Space efficiency

Hash table는 공간 효율이 적고,

Bloom Filter는 실제 객체보다 더 크기가 작기 때문에 공간 효율적입니다.

 

✔️ Deletion

Hash table는 삭제가 가능하지만, 

Bloom Filter는 삭제할 수 없습니다.

 

✔️ Accuracy

Hash table는 정확한 결과를 제공하고, 

Bloom Filter는 존재하지 않은데 존재한다고 판단하는 false positive의 가능성을 가집니다. 

 

✔️ Collision

Hash table는 충돌을 최소화해야하기 때문에 다중 해시 함수를 구현하거나 강한 hash function을 가져야 하지만,

Bloom Filter는 많은 hash functions를 사용하며 따로 충돌을 처리하지 않습니다.

 

✔️ Application

Hash table는 컴파일러 연산, 프로그래밍 언어(hash table 기반 데이터 구조), 비밀번호 검증 등에 사용되며,

Bloom Filter는 네트워크 라우터, 웹 브라우저(악성 URL 검증), 비밀번호 확인(약하거나 추측가능하거나, 금지된 암호 목록을 설정하지 않도록 체크) 등에서 사용될 수 있습니다.

 

 

 

BloomFilter in Java

dependency

<dependency>
	<groupId>com.google.guava</groupId>
	<artifactId>guava</artifactId>
	<version>19.0</version>
</dependency>

 

black Listed IP

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.nio.charset.Charset;

public class BloomFilterTests {

    @Test
    public void stringTest() {
        BloomFilter<String> blackListedIps = BloomFilter.create(
            Funnels.stringFunnel(Charset.forName("UTF-8")), 10000, 0.005);

        blackListedIps.put("192.170.0.1");
        blackListedIps.put("75.245.10.1");
        blackListedIps.put("10.125.22.20");

        Assertions.assertTrue(blackListedIps.mightContain("75.245.10.1"));
    }
}

 

혹은 정수 형의 테스트도 가능합니다.

 

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

public class BloomFilterTests {

    @Test
    public void integerTest() {
        BloomFilter<Integer> filter = BloomFilter.create(
            Funnels.integerFunnel(), 500, 0.01);
            
        filter.put(1);
        filter.put(2);
        filter.put(3);

        Assertions.assertTrue(filter.mightContain(2));
        Assertions.assertTrue(filter.mightContain(1));
        Assertions.assertTrue(filter.mightContain(3));

        Assertions.assertFalse(filter.mightContain(100));
    }
}

 

 

 

 

그럼 지금까지 Bloom Filter의 개념과 사용법에 대해 알아보았습니다.

오타나 잘못된 내용을 댓글로 남겨주세요!

감사합니다 ☺️ 

 

 

| Refer |

https://www.geeksforgeeks.org/bloom-filter-in-java-with-examples/

https://www.geeksforgeeks.org/difference-between-bloom-filters-and-hashtable/