---
title: 【Java Advent Calendar 2013 18日目 BloomFilterで効率的に大量データセットを持つ
tags: []
categories: ["Programming", "Java", "Java", "AdventCalendar", "2013"]
date: 2013-12-18T14:15:01Z
updated: 2013-12-18T14:15:01Z
---

この記事は[Java Advent Calendar 2013][1] 18日目の記事です。昨日はHiroyuki Ohnakaさんの[Singletonをモックする][2]でした。

### BloomFilterとは？

BloomFilterとはデータ構造の一種で、Setみたいなもので集合を扱います。

BloomFilterはSetのように、対象のデータが集合に含まれるかどうかを検証できますが、検証結果は

* たぶん集合に含まれる 
* 絶対に集合に含まれない

の2パターンです。「たぶん集合に含まれる」という結果がでても、たまに誤ります。これを偽陽性(False Postive)と言います。

一見、 えっと思うかもしれませんが、この偽陽性を持つことにより、空間効率が飛躍的に向上します。つまり、データ集合を表現するために必要なメモリがSetに比べて大幅に少ないのです。

原理を説明しようとおもったけど、このSlideshareが分かりやすかったので、埋め込んでおきます。

<iframe src="http://www.slideshare.net/slideshow/embed_code/4178952" width="427" height="356" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" style="border:1px solid #CCC;border-width:1px 1px 0;margin-bottom:5px" allowfullscreen> </iframe> <div style="margin-bottom:5px"> <strong> <a href="https://www.slideshare.net/kumagi/bloom-filter-4178952" title="Bloom filter" target="_blank">Bloom filter</a> </strong> from <strong><a href="http://www.slideshare.net/kumagi" target="_blank">Kumazaki Hiroki</a></strong> </div>

詳しい話は[Wikipedia](http://ja.wikipedia.org/wiki/%E3%83%96%E3%83%AB%E3%83%BC%E3%83%A0%E3%83%95%E3%82%A3%E3%83%AB%E3%82%BF)とか見てください。

### JavaでBloomFilterを使う

次にBloomFilterをJavaから使ってみましょう。アルゴリズム自体はそんなにむずかしくないので、自分で実装してみるのも勉強になりますが、ここでは[Google Guava][3]に含まれている`com.google.common.hash.BloomFilter`クラスを使います。


使い方は

    int expectedInsertions = 100;
    BloomFilter<String> bloomFilter = BloomFilter.create(new Funnel<String>() {
        @Override
        public void funnel(String from, PrimitiveSink into) {
            into.putString(from, StandardCharsets.UTF_8);
        }
    }, expectedInsertions);


といった感じです。`BloomFilter.create`の第一引数には`com.google.common.hash.Funnel`実装を渡します。`Funnel`は対象のデータを`PrimitiveSink`に流します。`PrimitiveSink`はハッシュ値を計算するために使用され、データのプリミティブな値を受けます(StringもOK）。最後に補足しますが、この`Funnel`の書き方は良くないです。

Funnel(漏斗)でデータをSink(流し台)に流し込むイメージです。この例では単純にStringを溜めこむので、Stringをそのままシンクに流します。

第二引数にはデータサイズを予想値を指定します。扱う集合のサイズにできるだけ近い値が望ましいです。第三引数で「たぶん集合に含まれる」の結果が間違える確率を指定できます。デフォルトでは0.03が指定されており、97%の確率で対象のデータが「たぶん集合に含まれ」ることになります。このサイズの予想値(n)と誤認識の確率(p)でBloomFilterが持つビットセットのサイズ(m)が決まります。計算式はwikipediaに載っていますが、javadocに式展開まで書かれています。

      /*
       * Cheat sheet:
       *
       * m: total bits
       * n: expected insertions
       * b: m/n, bits per insertion
       * p: expected false positive probability
       *
       * 1) Optimal k = b * ln2
       * 2) p = (1 - e ^ (-kn/m))^k
       * 3) For optimal k: p = 2 ^ (-k) ~= 0.6185^b
       * 4) For optimal k: m = -nlnp / ((ln2) ^ 2)
       */


実際に使ってみるコード例を挙げます。


	import com.google.common.hash.BloomFilter;
	import com.google.common.hash.Funnel;
	import com.google.common.hash.PrimitiveSink;
	
	import java.nio.charset.StandardCharsets;
	
	public class Main {
	    public static void main(String[] args) {
	        int number = 1000;
	        BloomFilter<String> bloomFilter = BloomFilter.create(new Funnel<String>() {
	            @Override
	            public void funnel(String from, PrimitiveSink into) {
	                into.putString(from, StandardCharsets.UTF_8);
	            }
	        }, number);
	
	
	        for (int i = 0; i < number; i++) {
	            bloomFilter.put(String.format("%09d", i));
	        }
	
	        int loopCount = 2000;
	        int misCount = 0;
	        for (int i = 0; i < loopCount; i++) {
	            String s = String.format("%09d", i);
	            if (bloomFilter.mightContain(s) && (i >= number)) {
	                misCount++;
	            }
	        }
	        System.out.println("mis = " + misCount + " (" + (misCount * 100.0 / (loopCount - number)) + "%)");
	    }
	}

100件データを`put`メソッドで投入して、「たぶん集合に含まれる」ことを`mightContain`メソッドで確認します。そして誤認確率を表示します。

実行結果

    mis = 26 (2.6%)

でした。含まれていないデータを1000個ためして、26回誤認識しました。約3%と計算通りです。


確率を変えてみましょう。


    BloomFilter<String> bloomFilter = BloomFilter.create(new Funnel<String>() {
        @Override
        public void funnel(String from, PrimitiveSink into) {
            into.putString(from, StandardCharsets.UTF_8);
        }
    }, number, 0.005);

今度は誤認識率を0.5%にして実行します。


	mis = 2 (0.2%)

分母が小さいので少しぶれていますが、約0.5%に減りました。確率をコントロールできることがわかりますね。

### HashSetとデータサイズを比較する

単純ですが、Stringを500万件投入した後のデータサイズを比較してみます。


#### HashSet版

以下のコードを実行します。

	import com.google.common.base.Stopwatch;
	import com.google.common.hash.BloomFilter;
	import com.google.common.hash.Funnel;
	import com.google.common.hash.PrimitiveSink;
	
	import java.io.ByteArrayOutputStream;
	import java.io.IOException;
	import java.io.ObjectOutputStream;
	import java.io.Serializable;
	import java.nio.charset.StandardCharsets;
	import java.text.MessageFormat;
	import java.util.HashSet;
	import java.util.Set;
	import java.util.concurrent.TimeUnit;
	
	public class MainWithHashSet {
	    public static void main(String[] args) {
	        execute();
	    }
	
	    private static void execute() {
	        int number = 5000000;
	        Set<String> set = new HashSet<>(number);
	
	        Stopwatch stopwatch = Stopwatch.createStarted();
	        for (int i = 0; i < number; i++) {
	            set.add(String.format("%09d", i));
	        }
	        System.out.println(stopwatch.elapsed(TimeUnit.SECONDS) + " sec");
	        System.out.println(MessageFormat.format("{0} byte", calcObjectSize(set)));
	    }
	
	    private static long calcObjectSize(Object object) {
	        try (ByteArrayOutputStream baos = new ByteArrayOutputStream();
	             ObjectOutputStream oos = new ObjectOutputStream(baos);
	        ) {
	            oos.writeObject(object);
	            return baos.toByteArray().length;
	        } catch (IOException e) {
	            e.printStackTrace();
	        }
	        return 0;
	    }
	}


出力結果

	20 sec
	60,000,053 byte
	mis = 0 (-0.0%)


約60MB消費しています。

#### BloomFilter版

	import com.google.common.base.Stopwatch;
	import com.google.common.hash.BloomFilter;
	import com.google.common.hash.Funnel;
	import com.google.common.hash.PrimitiveSink;
	
	import java.io.ByteArrayOutputStream;
	import java.io.IOException;
	import java.io.ObjectOutputStream;
	import java.io.Serializable;
	import java.nio.charset.StandardCharsets;
	import java.text.MessageFormat;
	import java.util.concurrent.TimeUnit;
	
	public class MainWithBloomFilter {
	    public static void main(String[] args) {
	        execute();
	    }
	
	    private static void execute() {
	        int number = 1000;
	        BloomFilter<String> bloomFilter = BloomFilter.create(new Funnel<String>() {
	            @Override
	            public void funnel(String from, PrimitiveSink into) {
	                into.putString(from, StandardCharsets.UTF_8);
	            }
	        }, number, 0.005);
	
	
	        Stopwatch stopwatch = Stopwatch.createStarted();
	        for (int i = 0; i < number; i++) {
	            bloomFilter.put(String.format("%09d", i));
	        }
	        System.out.println(stopwatch.elapsed(TimeUnit.SECONDS) + " sec");
	        System.out.println(MessageFormat.format("{0} byte", calcObjectSize(bloomFilter)));
	
	        int loopCount = 2000;
	        int misCount = 0;
	        for (int i = 0; i < loopCount; i++) {
	            String s = String.format("%09d", i);
	            if (bloomFilter.mightContain(s) && (i >= number)) {
	                misCount++;
	            }
	        }
	        System.out.println("mis = " + misCount + " (" + (misCount * 100.0 / (loopCount - number)) + "%)");
	    }
	
	    private static long calcObjectSize(Object object) {
	        try (ByteArrayOutputStream baos = new ByteArrayOutputStream();
	             ObjectOutputStream oos = new ObjectOutputStream(baos);
	        ) {
	            oos.writeObject(object);
	            return baos.toByteArray().length;
	        } catch (IOException e) {
	            e.printStackTrace();
	        }
	        return 0;
	    }
	}


出力結果

	11 sec
	4,561,902 byte
	mis = 149390 (2.9878%)


約3%の誤認識を許すことで、データサイズが4MBになりました。

確率を変えてみます。

p=0.001
	
	12 sec
	8,986,374 byte
	mis = 5006 (0.10012%)
	
p=0.0001
	
	14 sec
	11,981,702 byte
	mis = 485 (0.0097%)

p=0.0001

	14 sec
	14,977,030 byte
	mis = 42 (8.4E-4%)

計算上、ビットセットのサイズ(m)を増やすと誤認識率は指数関数的に下がります。

この辺は用途次第での調整になるでしょう。

次にp=0.03のまま、集合データ数を変えてみます。HashSetはGCの影響で遅すぎたので計測していません。誤認識率のチェックも省略します。

n=10000000

	24 sec
	9,123,430 byte

n=100000000
	
	250 sec
	91,230,886 byte

計算式見てもわかりますが、pが固定であればmはnに比例しますね。

3%の誤認識を許せば日本人全員分のStringは100MBくらいで格納できそうですね。

### どこで使う？

以下の用途が考えられます

* 大量のデータの中に対象が含まれているか確認したいけど、間違っていても問題ない(他の方法で確認できる)
* 大量のデータの中に対象が含まれていないことだけを確認したい

具体的には以下で実際に使用されています([Wikipedia](http://en.wikipedia.org/wiki/Bloom_filter#Examples)調べ)。

* Squidのキャッシュ判定
* BigTableやCassandraのキーの検出
* Chromeの悪意のあるURLのチェック

話題のBitcoinでも使用されていますね。

この「[Bloom filter の気持ち][4]」を読むとありがたみもわかってきます。

業務処理ばっかり書いていると、こういう用途でも愚直にHashSetに溜め込み、OutOfMemoryを招いたりします。データ構造やアルゴリズムをちゃんと勉強して、より良い選択肢を用意しておくことはプログラマとしてとても重要ですね。


### (補足) Funnelの作り方


上記の例では説明を単純化するため、Stringを扱い、また匿名クラスで`Funnel`を作成しました。

実際のところはJavaBeanが対象になるでしょうし、`Funnel`はSerializableなSingletonにすべきです。BloomFilterは`addAll`で混合することが可能ですが、`Funnnel`オブジェクトが等価である必要があります。

Javadocでは以下のようにEnumを使ったSingletonパターンを推奨しています。Effective Javaの項目3にありましたね。

	public enum  BookFunnel implements Funnel<Book> {
	    //This is the single enum value
	    FUNNEL;
	    public void funnel(Book from, PrimitiveSink into) {
	        into.putString(from.getIsbn(), StandardCharsets.UTF_8)
	            .putDouble(from.getPrice());
	    }
	}


こう使いましょう。

	BloomFilter<Book> bloomFilter = BloomFilter.create(BookFunnel.FUNNEL, 5000000);


  [1]: http://www.adventar.org/calendars/145
  [2]: http://blog.fieldnotes.jp/entry/2013/12/17/220126
  [3]: https://code.google.com/p/guava-libraries/
  [4]: http://d.hatena.ne.jp/takeda25/20110509/1304948935