Bloom Filter 핵심 정리, 작동 원리부터 수학 이론과 Java 구현까지

데이터베이스나 캐시 시스템에서 특정 키가 존재하는지 확인할 때, 매번 디스크 I/O를 발생시키는 대신 메모리에서 빠르게 판별할 수 있다면 성능이 크게 향상된다. Bloom Filter는 이 목적에 특화된 확률형 자료구조로, false positive를 일정 수준 허용하는 대신 극히 적은 메모리로 집합 멤버십을 검사한다. 이 글에서는 Bloom Filter의 작동 원리, 수학적 오류율 계산, Java 구현 예, 그리고 Cassandra·HBase 등 실제 시스템에서의 활용까지 다룬다.

개요

블룸필터(Bloom filter)는 1970년도에 Burton H. Bloom이 고안한 것으로 공간 효율적인 probabilistic data structure이며 구성요소가 집합의 구성원인지 점검하는데 사용된다. False positive들이 가능하며, false negative들은 불가능하다. 요소들은 집합에 추가될 수 있으나 제거는 되지 않는다. 그리고 블룸 필터는 메모리를 좀 더 사용함으로써 자주 호출되는 비싼 함수들의 성능을 크게 향상시키는 방법 중에 하나이다.

구성 요소들과 작동 방식

1. 구성 요소

• 해시(hash) 함수: 해시 알고리즘 구현체
• Bloom Filter Key: 해시 알고리즘이 반환한 키
• Bloom Filter Index: Bloom Filter Key를 임의 크기의 비트 블록으로 나눈 하나하나의 조각
• 블룸 필터는 추가하는 add()와 존재 여부를 확인하는 isExist(), 이렇게 두 가지 연산을 제공한다.
• false positive: 없는데 있다고 판단하는 경우, false negative: 있는데 없다고 판단하는 경우

2. 작동 방식

예를 들어, m(bloom filter의 bit 사이즈) = 10, k(hashing functions의 수) = 2로 하자. 2개의 해시 함수를 h1, h2 하고 Bloom Filter 배열은 아래와 같다.

+-+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|0|
+-+-+-+-+-+-+-+-+-+-+
 0 1 2 3 4 5 6 7 8 9

데이터 A를 삽입한다고 가정하면, 데이터 A를 두 해시 함수 h1, h2를 거쳐 해시 값을 계산한다. 만일 3=h1(A), 7=h2(A) 였다고 하자. 이 해시 값 3, 7에 해당하는 곳에 1을 셋팅한다. 이제 배열은 아래와 같아진다.

+-+-+-+-+-+-+-+-+-+-+
|0|0|0|1|0|0|0|1|0|0|
+-+-+-+-+-+-+-+-+-+-+
 0 1 2 3 4 5 6 7 8 9

그 다음 데이터 A를 검색한다면, 해시 함수를 거치면 3=h1(A), 7=h2(A)이다. 3, 7에 대응하는 배열을 보면 양쪽 모두 1로 되어 있어서 리턴은 true로 던져질 것이다.

+-+-+-+-+-+-+-+-+-+-+
|0|0|1|1|0|0|0|1|0|0|
+-+-+-+-+-+-+-+-+-+-+
 0 1 2 3 4 5 6 7 8 9
       *       *

그 다음 데이터 C를 검사한다면, 해시 함수를 거치면 3=h1(C), 6=h2(C)이다. 그런데 3은 1이나 6이 0이므로 false가 리턴되어 없는 것으로 간주하게 된다.

+-+-+-+-+-+-+-+-+-+-+
|0|0|1|1|0|0|0|1|0|0|
+-+-+-+-+-+-+-+-+-+-+
 0 1 2 3 4 5 6 7 8 9
       *     *

이런 형태로 동작하는 방식이다.

Bloom Filter는 기존 hash table의 key-value의 쌍으로 저장하지 않고 hash table상에 키가 존재하는지 안하는지 true, false 정보의 조각(Bit의 Set)이 저장된다고 보면 된다. 즉, 각 Value를 저장하는 대신에 Bloom Filter는 Key가 존재하는 지점(해시 함수에 의해)을 가리키는 Bits의 배열이라고 봐도 된다. 찾는 비트의 조합이 모두 1일 경우 제대로 찾을 확률이 높아진다. Space와 Time을 적절하게 배합하고 고른 분포도를 가지며 Collision을 대처한다면 좋은 이득을 얻을 수 있다. 많은 비트를 할당할수록 성능은 좋을 수 있으나 많은 메모리가 필요하고 해싱 함수를 늘리게 되면 연산이 많아지게 되어 성능은 느리나 메모리를 덜 차지하게 되는 trade-off 관계가 존재한다. Optimizing하는게 관건이다.

수학적 이론

k는 해시 함수의 수, n은 집합에 삽입된 원소의 수, m은 비트 배열의 크기다. false positive 확률 p는 아래 공식으로 계산된다.

비트를 많이 쓸수록(m↑) p가 낮아지고, 원소가 늘어날수록(n↑) p가 높아진다. 해시 함수 수(k)를 최적값으로 설정하면 동일한 m·n에서 p를 최소화할 수 있다. 아래는 10,000단어 사전에서 1% error rate를 목표로 할 때 m = 10,000 × 10 = 100,000, n = 10,000으로 계산한 예다.

10,000단어의 사전에서 0.1%의 에러율을 희망할 경우 18KB의 메모리가 필요하다. 실용적인 수준이다.

구현 예

다음은 Google Guava의 BloomFilter 클래스를 사용한 예이다. 소스는 여기에 있다.

public class GuavaBloomFilterDemo {  
   public static void main(String[] args) {  
      final int maxInt = 500;  
      final Funnel<Integer> funnel = (Integer x, PrimitiveSink into) -> into.putInt(x);  
      final BloomFilter<Integer> bloomFilter = BloomFilter.create(funnel, maxInt);  
  
      // 0에서 998까지의 짝수를 Bloom Filter 에 추가  
      for (int i = 0; i < maxInt * 2; i += 2) {  
         bloomFilter.put(i);  
      }  
  
      // 998까지 모든 짝수가 positive 임  
      for (int i = 0; i < maxInt * 2; i += 2) {  
         if (!bloomFilter.mightContain(i)) {  
            System.out.printf("%d should be contained.\n", i);  
         }  
      }  
  
      // 1에서 999까지의 홀수로 false positive가 되는 값 추출  
      final Set<Integer> falsePositives = new HashSet<>();  
      for (int i = 1; i < maxInt * 2; i += 2) {  
         if (bloomFilter.mightContain(i)) {  
            falsePositives.add(i);  
         }  
      }  
  
      System.out.printf("예상 false positive 확률: %f\n", bloomFilter.expectedFpp());  
      System.out.printf("실제 false positive 확률: %f\n", (double) falsePositives.size() / maxInt);  
      System.out.printf("false-positive 값: %s", falsePositives);  
   }  
}

실행 결과로부터 false negative는 발생하지 않고 2.2%의 확률로 false positive가 발생하고 있는 것을 알 수 있다.

예상 false positive 확률: 0.026961
실제 false positive 확률: 0.022000
false-positive 값: [609, 131, 197, 405, 951, 41, 169, 649, 877, 175, 255]

활용되는 곳

• 스펠링체크, 사전, 웹 검색, IP Filtering, Router 등에 쓰이고 Squid Web, Venti Storage System, SPIN model checker, Google Chrome Browser 등에도 쓰이고 있다.
• Cassandra: SSTable 생성 시 인덱스 용도로 사용해 Read 성능을 향상시킨다(디스크 I/O 감소)
  • SMHasher & MurmurHash hash 함수 사용
• HBase: HFile 안에 로우와 컬럼이 존재하는지 검사하기 위해 사용한다
• Bigtable: 불필요한 디스크 접근을 피하기 위해 사용한다
• Oracle
  • Parallel Join 시 Slave 간의 communication 데이터량을 줄이기 위해(10gR2)
  • Join-Filter Pruning 사용 시(11gR1)
  • Result Cache 지원(11gR1)
• Guava Bloom Filter
• pyreBloom = Python + Redis + Bloom Filter
• bloomfilter-rb = Ruby + Redis + Bloom Filter 서버에 설정이 없다면 클라이언트 모듈에 직접 구현해서 사용하는 경우도 많다. 그만큼 성능 이슈가 크기 때문이다.

Hash Functions

• murmur
• fnv
• HashMix.
• Jenkins hash function
• MD5
• SHA1

참조 사이트

• Bloom filter
• BloomFilters Paper
• Scalable Datasets: Bloom Filters in Ruby
• Bloom Filters by Example