Bloom Filterについて

こんにちは、プロダクト開発部のちょうです。最近だいぶ寒くなってきて、こたつからなかなか出られません。こたつとみかんがあれば一日いきれると思いつつ、普段自分が学んでいる内容をすこし紹介したいと思います。

今回の内容はBloom Filterです。Bloom Filterは一言でいうと、空間効率のいい確率的データ構造です。要素が集合のメンバーであるかどうかのテストに使われます（wikipediaより）。確率ですので、使えるものではないと思う人が多いかもしれないが、Bloom Filterの特徴を理解すれば問題なく利用できます。

要素が集合のメンバーであるかどうかを確認するには、一番普通の方法はHash関数を元にするHashSetというデータ構造を使います。HashSetは基本 O(1) の速さで判断できます。もちろん、Hash関数による衝突の可能性があります。最悪の場合、HashSetの内部tableのサイズを倍にする必要があります。それに、要素数が非常に多い領域では、普通のHashSetだと空間効率が悪いと予想できます。ここで、Bloom Filterの登場です。

Bloom Filterは空間効率のいいデータ構造です。なぜなら、利用するメモリー領域を倍にする必要がありません。最初から固定してもいいです。それと、Bloom Filterの要素の単位は bit です。32bitマシンでinteger型だと最大32個の要素が入れます。

Bloom Filterは複数のHash関数を利用します。一つのHash関数だと衝突による実際集合のメンバーではないのにメンバーですという結果になる可能性が高いので、複数Hash関数で可能性を減らします。

サイズは8のBloom Filterを例にします。

| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

最初すべてのbitが0です。要素 foo を入れます。Hash関数を3つにしましょう。Hash1、Hash2とHash3。3つのHash関数の結果は2, 4と7とします。

| 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |

foo を入れたBloom Filterです。indexが2、4と7の位置を1にセットします。次は要素 bar を入れます。３つのHash関数の結果は1, 2と3とします。

| 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |

同じく、indexが1、2と3の位置にセットします。

では要素をテストしましょう。要素 foo でテストすると、３つのHash関数の結果で、場所2、4と7にすべて1にセットされ、メンバーであるということになります。同じく要素 bar でテストしてもメンバーであることもわかります。

続いてメンバーではない要素をテストします。 要素 aaa にたいして、Hash関数の結果を2, 5, 7とします。index 2と7に1がセットされましたが、5がセットされないです。ゆえ、 aaa がメンバーではありません。要素 bbb にたいして、Hash関数の結果は2、3と4とします。すべての位置に1がセットされ、メンバーであるという結果になりますが、実際はメンバーではありません！

ここでわかったことは、Bloom Filterはメンバーではない要素でもメンバーであるという結果になる可能性があります。これはfalse positiveということです。こういう問題があって、Bloom Filterは使えものにならないと思う人がいるかもしれないが、Bloom Filterはメンバーではない要素をメンバーであるという結果にならない（つまり、メンバーではない結果でしたら絶対メンバーではない）です。まとめてみると、

要素	事実	テスト
foo	メンバー	メンバー
bar	メンバー	メンバー
aaa	メンバーではない	メンバーではない
bbb	メンバーではない	メンバー

要素 aaa はメンバーではないの結果なので、メンバーではないということが断言できます。逆に、メンバーであるという結果になったら、メンバーではない可能性があります。

こういう特徴を受け、Bloom Filter + DBの使い例を考えみましょう。

DBに100万のレコードがあり、サイズ200万（メモリーやく244KB）のBloom FilterをDBの前にします。毎回レコードを取得するとき、まずBloom Filterを通して、もし存在しないなら、レコードはかならず存在しないので、存在するレコードだけDBと問い合わせします。

こうすることで、Bloom Filterでいらない問い合わせを減らすことができます。Bloom Filterの確率的という特徴もカバーできます。実際、Bloom Filterを利用するシーンはほとんど、レコードは非常に多く、例えばメールボックスのSpam Filter、Bloom Filterなしだと裏側のデータソースへものすごく負荷をかかることが予想できます。

Bloom Filterの特徴を理解できると、以下のような簡単なBloom Filterが書けます。

import java.util.*

interface Hasher<K> {
    fun apply(key: K): Int
}

class SimpleStringHasher(
        private val seed: Int, 
        private val max: Int
) : Hasher<String> {
    override fun apply(key: String): Int {
        return key.fold(seed) { acc, c -> acc * seed + c.toInt() } and (max - 1)
    }
}

class SimpleBloomFilter<K>(
        private val bitSet: BitSet, 
        private val hashers: Collection<Hasher<K>>
) {
    fun mightContains(key: K): Boolean {
        return hashers.all { bitSet.get(it.apply(key)) }
    }

    fun put(key: K) {
        hashers.forEach { bitSet.set(it.apply(key)) }
    }
}

fun main() {
    val size = 2048
    val bloomFilter = SimpleBloomFilter(BitSet(size), listOf(
            SimpleStringHasher(1, size),
            SimpleStringHasher(7, size),
            SimpleStringHasher(23, size)
    ))
    for (i in 1..1000) {
        bloomFilter.put(i.toString())
    }
    println((1..2000).count { bloomFilter.mightContains(it.toString()) })
    // 1024 -> 1582
    // 2048 -> 1000
}

SimpleBloomFilterのソースコードをすこしみてみましょう。mightContainsはすべてのHash関数が計算した位置に1がセットされればtrueを返します。putはすべてのHash関数が計算した位置に1をセットします。

main関数では、サイズ2048のBloom Filterを作ってました。それと1から1000までという要素をBloom Filterに入れます。最後は1から2000までの要素でテストします。サイズは2048だと、最後はきれいに1000とカウントされますが、サイズ1024の場合は1582の結果になります。ぜひ試してください。

最後に、false positiveつまり誤判断を減らすにはサイズどれぐらいにすればいいでしょうか。その質問にたいして、Bloom Filterの論文に答えがありますが、ここで結論を出します。

Pfpをfalse positiveの確率とします。nは入れようとする要素の数です。mはBloom Filterのサイズです。

m = - (n * ln Pfp) / (ln 2) ^ 2

おまけに、Hash関数の数kも

k = (m / n) * ln 2

いかがでしょうか。すこしBloom Filterに理解していましたでしょうか。普段の開発に使わないかもしれないが、こういうものがあると覚えていただければ幸いです。