블룸 필터

소개

블룸 필터는 특정 엘리먼트가 집합에 포함되어 있는지 여부를 알려주는 공간 효율적인 데이터 구조다.

이 데이터 구조는 확률적이다. 블룸 필터에 대한 쿼리는 false 또는 true를 반환한다. false는 엘리먼트가 집합에 확실히 포함되지 않음을 의미하고, true는 엘리먼트가 집합에 있을 수도 있음을 의미한다.

블룸 필터는 작은 확률로 거짓 양성(false positive)을 발생시킬 수 있다. 즉, 쿼리가 true를 반환했지만 실제로 엘리먼트가 집합에 포함되지 않는 경우가 있다. 하지만 거짓 음성(false negative)은 절대 발생하지 않는다. 쿼리가 false를 반환하면 엘리먼트가 집합에 포함되지 않음을 보장한다.

따라서 블룸 필터는 "확실히 아니다" 또는 "아마도 있다"라고 알려준다.

처음에는 이 기능이 그다지 유용해 보이지 않을 수 있다. 하지만 캐시 필터링이나 데이터 동기화 같은 애플리케이션에서는 매우 중요한 역할을 한다.

블룸 필터는 해시 테이블과 비교해 일정한 메모리 사용량과 일정한 시간 복잡도의 삽입 및 검색을 유지한다는 장점이 있다. 엘리먼트 수가 많은 집합에서는 해시 테이블과 블룸 필터 간의 성능 차이가 크다. 거짓 양성이 발생하지 않음을 보장할 필요가 없다면 블룸 필터는 유용한 선택지다.

참고: 해시 테이블과 달리 블룸 필터는 실제 객체를 저장하지 않는다. 단지 어떤 객체를 본 적이 있는지(약간의 불확실성을 포함해) 그리고 어떤 객체를 본 적이 없는지만 기억한다.

셋에 객체 삽입하기

블룸 필터는 기본적으로 고정 길이의 비트 벡터이다. 이는 비트로 이루어진 배열이다. 객체를 삽입할 때 일부 비트를 1로 설정하고, 객체를 쿼리할 때 특정 비트가 0인지 1인지 확인한다. 두 작업 모두 해시 함수를 사용한다.

필터에 요소를 삽입하려면, 요소를 여러 다른 해시 함수로 해싱한다. 각 해시 함수는 배열의 인덱스에 매핑할 값을 반환한다. 그런 다음 이 인덱스에 해당하는 비트를 1 또는 true로 설정한다.

예를 들어, 다음과 같은 비트 배열이 있다고 가정하자. 총 17개의 비트가 있고, 처음에는 모두 0 또는 false이다:

[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]

이제 "Hello world!"라는 문자열을 블룸 필터에 삽입하려고 한다. 이 문자열에 두 개의 해시 함수를 적용한다. 첫 번째 해시 함수는 값 1999532104120917762를 반환한다. 이 해시 값을 배열 길이로 나눈 나머지를 구해 배열의 인덱스에 매핑한다: 1999532104120917762 % 17 = 4. 이는 인덱스 4의 비트를 1 또는 true로 설정한다는 의미이다:

[ 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]

그런 다음 원래 문자열을 다시 해싱하지만 이번에는 다른 해시 함수를 사용한다. 이 해시 함수는 값 9211818684948223801을 반환한다. 이를 17로 나눈 나머지는 12이므로, 인덱스 12의 비트도 1로 설정한다:

[ 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 ]

이 두 개의 1 비트는 블룸 필터가 이제 "Hello world!" 문자열을 포함하고 있다는 것을 알려준다. 물론 실제 문자열은 포함하지 않으므로, 블룸 필터에게 "포함하고 있는 모든 객체 목록을 보여줘"라고 요청할 수 없다. 블룸 필터가 가지고 있는 것은 단순히 1과 0의 집합일 뿐이다.

집합 조회하기

조회 작업은 삽입과 마찬가지로, 먼저 예상 값을 해싱하여 여러 배열 인덱스를 얻은 후, 해당 인덱스의 비트가 모두 1인지 확인한다. 하나라도 1이 아닌 비트가 있으면 해당 요소는 삽입되지 않았음을 의미하므로 조회 결과는 false가 된다. 모든 비트가 1이면 조회 결과는 true를 반환한다.

예를 들어, 문자열 "Hello WORLD"를 조회한다고 가정해보자. 첫 번째 해시 함수는 5383892684077141175를 반환하고, 이를 17로 나눈 나머지는 12다. 이 비트는 1이다. 그러나 두 번째 해시 함수는 5625257205398334446을 반환하고, 이는 배열 인덱스 9에 매핑된다. 이 비트는 0이다. 따라서 문자열 "Hello WORLD"는 필터에 존재하지 않으며, 조회 결과는 false가 된다.

첫 번째 해시 함수가 1 비트에 매핑된 것은 단순한 우연이다(두 문자열이 모두 "Hello "로 시작한다는 사실과는 무관하다). 이러한 우연이 너무 많이 발생하면 "충돌"이 생길 수 있다. 충돌이 발생하면 실제로 삽입되지 않은 요소에 대해 조회가 true를 잘못 반환할 수 있으며, 이는 앞서 언급한 거짓 양성 문제를 일으킨다.

다른 요소 "Bloom Filterz"를 삽입하면 비트 7과 9가 설정된다. 이제 배열은 다음과 같이 보인다:

[ 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0 ]

이 상태에서 다시 "Hello WORLD"를 조회하면, 필터는 비트 12와 9가 모두 1임을 확인한다. 필터는 "Hello WORLD"가 집합에 존재한다고 보고하지만, 실제로는 그렇지 않다. 해당 문자열은 삽입된 적이 없기 때문이다. 이는 거짓 양성의 예시다. 이 예제는 Bloom Filter가 "확실히 있다"고 말하지 않고 "아마도 있다"고만 말하는 이유를 보여준다.

이러한 문제는 더 많은 비트를 가진 배열과 추가적인 해시 함수를 사용해 해결할 수 있다. 물론 해시 함수를 더 많이 사용할수록 Bloom Filter의 성능은 느려진다. 따라서 적절한 균형을 찾아야 한다.

Bloom Filter에서는 삭제가 불가능하다. 하나의 비트가 여러 요소에 속할 수 있기 때문이다. 한 번 추가된 요소는 영원히 남는다.

Bloom Filter의 성능은 **O(k)**이며, 여기서 k는 해시 함수의 개수다.

코드 분석

코드는 상당히 직관적이다. 내부 비트 배열은 초기화 시 고정된 길이로 설정되며, 한번 초기화되면 변경할 수 없다.

public init(size: Int = 1024, hashFunctions: [(T) -> Int]) {
  self.array = [Bool](repeating: false, count: size)
  self.hashFunctions = hashFunctions
}

초기화 시 여러 해시 함수를 지정해야 한다. 어떤 해시 함수를 사용할지는 집합에 추가할 요소의 데이터 타입에 따라 달라진다. 플레이그라운드와 테스트에서 몇 가지 예제를 확인할 수 있다. 문자열을 위한 djb2와 sdbm 해시 함수가 대표적이다.

삽입 연산은 필요한 비트를 true로 설정한다:

public func insert(_ element: T) {
  for hashValue in computeHashes(element) {
    array[hashValue] = true
  }
}

이 코드는 computeHashes() 함수를 사용한다. 이 함수는 지정된 hashFunctions를 순회하며 인덱스 배열을 반환한다:

private func computeHashes(_ value: T) -> [Int] {
  return hashFunctions.map() { hashFunc in abs(hashFunc(value) % array.count) }
}

쿼리 연산은 해시된 값에 해당하는 비트가 모두 true인지 확인한다:

public func query(_ value: T) -> Bool {
  let hashValues = computeHashes(value)
  let results = hashValues.map() { hashValue in array[hashValue] }
  let exists = results.reduce(true, { $0 && $1 })
  return exists
}

다른 명령형 언어에서 온 개발자라면 exists 할당 부분의 특이한 문법을 눈치챌 수 있다. Swift는 코드를 더 간결하고 가독성 있게 만들기 위해 함수형 패러다임을 활용한다. 이 경우 reduce를 사용하면 for 루프보다 모든 비트가 true인지 확인하는 코드를 더 간결하게 작성할 수 있다.

다른 접근 방식

이전 섹션에서는 여러 개의 해시 함수를 사용해 블룸 필터에서 충돌 가능성을 줄이는 방법을 배웠다. 하지만 좋은 해시 함수를 설계하는 것은 쉽지 않다. 여러 해시 함수 대신 사용할 수 있는 간단한 대안은 무작위 숫자 집합을 활용하는 것이다.

예를 들어, 블룸 필터가 삽입 과정에서 각 엘리먼트를 15번 해싱한다고 가정해보자. 15개의 서로 다른 해시 함수를 사용하는 대신, 단 하나의 해시 함수만 사용할 수 있다. 이 해시 값은 15개의 다른 값과 결합해 비트를 뒤집을 인덱스를 생성한다. 이 블룸 필터는 15개의 무작위 숫자를 미리 초기화하고, 각 삽입 과정에서 이 값을 사용한다.

hash("Hello world!") >> hash(987654321) // 비트 8을 뒤집음
hash("Hello world!") >> hash(123456789) // 비트 2를 뒤집음

Swift 4.2부터 Hasher가 표준 라이브러리에 포함됐다. 이는 여러 해시를 효율적으로 단일 해시로 줄이도록 설계됐다. 이를 통해 해시를 결합하는 작업이 간단해졌다.

private func computeHashes(_ value: T) -> [Int] {
  return randomSeeds.map() { seed in
    let hasher = Hasher()
    hasher.combine(seed)
    hasher.combine(value)
    let hashValue = hasher.finalize()
    return abs(hashValue % array.count)
  }
}

이 접근 방식에 대해 더 자세히 알고 싶다면, Hasher 문서나 Soroush Khanlou의 Swift 4.2 Bloom filter 구현을 참고할 수 있다.

Swift Algorithm Club을 위해 Jamil Dhanani가 작성. Matthijs Hollemans가 편집. Bruno Scheele가 업데이트.