1. BloomFilterの説明と例
1-1. 前提のユースケース
ちょっと小難しいので例をあげる。
適切なユースケースでもないし現実味もないが。
- スマホで相手の口座番号を入力して送金できるアプリを作る
- 存在しない口座番号には送金できない
このケースだと
- 相手の口座番号をサーバのデータベースに問い合わせる
- 存在しなければエラーを返し、存在すればそこに入金処理を行う
となる。
ここで、以下のように
その口座番号が存在するかしないかの一覧をアプリが持っていれば
わざわざネットワークを介してデータベースに口座番号の存在を問い合わせる必要はなくなる。
| 口座番号 |
|---|
| 111-111-111 |
| 222-222-222 |
| 333-333-333 |
| ......... |
ただし、口座番号が膨大である場合、スマホアプリでそれだけの情報を保持するのは難しい。
そういう時にBloomFilterを用いると、口座番号の存在有無が「ほぼ」分かる情報を非常にコンパクトに持てる。
1-2. 仕組み
くわしい説明はWikiで。
- ０と１のビット情報を持てるような一定長のレコードを用意する
- 口座番号にハッシュ関数をかけ、結果のハッシュをレコード長の０１のビット列に変換する
- レコードの該当する位置にビットを立てる
この際、１が立つ位置は複数あるイメージになる。
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
|---|
これを全ての口座番号分繰り返すと１が立つ位置は増えていく。
上記のアプリで口座番号を入力した場合にこのレコードさえあれば
全く同じハッシュ⇒０１ビット列変換を掛けて、１が立っている部分をレコードと突合し
全て１が立っていれば、その口座番号が存在している確率が極めて高いことが分かる。
- 上段：全ての口座番号の情報を持つレコード
- 下段：口座番号「111-111-111」をハッシュ⇒０１変換した結果
| 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
⇒ 対象の位置すべてに1が立っているため、そのレコードは存在する可能性が極めて高い。
「極めて高い」というのは絶対ではないからだ。
なぜなら１が立つ位置は他の口座番号と衝突するので
他の口座番号情報のビット列によってその位置に１を立てられている可能性がある。
- １行目：以下の口座番号の情報を持つレコード
- ２行目：存在する口座番号「111-111-111」のビット情報
- ３行目：存在する口座番号「222-222-222」のビット情報
| 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
ここで、存在しない口座番号「999-999-999」を
ハッシュ⇒０１ビット変換かけた結果が以下のようになったら、誤ってデータは存在すると判定される。
- １行目：以下の口座番号の情報を持つレコード（前と同じ）
- ２行目：存在しない口座番号「999-999-999」の変換結果
| 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
１が立つ位置に一つでも０があればデータがないと１００％確定的に断定できるが
全ての１が立つ位置に１があっても、データがあるとは１００％確定できない。
このような特徴を偽陰性はないが、偽陽性はある、と言う。
レコード長を十分長く取ることで偽陽性は低下するが、
あまりに長いレコードに取ると容量が圧迫されてしまう。
もっとも、１００万件の口座番号（何桁でもいい）に対し
概ね １．２ＭＢ程度の領域さえあれば偽陽性は１％程度に収束する。
仮に、１．８ＭＢ程度の領域が用意できれば、偽陽性は０．１％程度にまで収束する。
なので、上記のようなアプリでは僅かなレコードを保持するだけで
大幅にネットワークアクセス、データベースアクセスを抑制できることになる。
なお、この場合だと新規に口座が追加されるたびに
更新されたレコードをダウンロードするのかというツッコミどころはある。
複数のストレージやセグメントにデータが格納されている場合に
データの格納場所を効率的に探したりということにも使えるのだがそれだと伝わりづらいし
他に簡単に説明できる良いユースケースが直ぐ思い浮かばなかったので勘弁いただきたい。
2. BloomFilterの実装サンプル
Javaでの実装そのまま載せます。
MyBloomFilter.java
import java.io.Serializable;
import java.nio.charset.Charset;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.BitSet;
/**
* BloomFilterの最も基本的な機能のみを備える
* @author owl
* @param <E>
*/
public class MyBasicBloomFilter<E> implements Serializable {
private final BitSet bitFilter; // Filter本体
private final int bitFilterSize; // Filterのサイズ
private int numberOfAddedElements; // 現在の要素数
private final int countOfHashNumCreatePerOneElement; // 要素あたりのTrueビット数（ハッシュ化⇒数値変換の回数）
static final Charset DEFAULT_CHARSET = Charset.forName("UTF-8");
/**
* 偽陽性レベル
* High: 偽陽性は高いが、フィルタサイズはコンパクトで、パフォーマンスも良好
* Middle： 偽陽性とフィルタサイズと、パフォーマンスのバランスを取る
* Low: フィルタサイズの増大や、処理時間の長さを招いても偽陽性を極力低く抑える
*/
public static enum FalsePositiveProbability{ High, Middle, Low }
/**
* メッセージダイジェストの実行
*/
static final MessageDigest digestFunction;
static final String hashName = "MD5";
static {
MessageDigest tmp;
try { tmp = java.security.MessageDigest.getInstance(hashName); } catch (NoSuchAlgorithmException e) { tmp = null; }
digestFunction = tmp;
}
/**
* コンストラクタ
* @param c １要素あたりで利用するビット数
* @param n （想定する最大の）要素数
* @param k 要素あたりのTrueビット数（ハッシュ化⇒数値変換の回数）
*/
public MyBasicBloomFilter(double c, int n, int k) {
this.countOfHashNumCreatePerOneElement = k;
// 要素数 * 要素あたり利用ビット数でFilterのビットサイズを決定する
this.bitFilterSize = (int)Math.ceil(c * n);
numberOfAddedElements = 0;
this.bitFilter = new BitSet(bitFilterSize);
}
/**
*
* @param expectedItemCount
* @param fpp
*/
public MyBasicBloomFilter(int expectedItemCount, FalsePositiveProbability fpp) {
switch(fpp){
case High : {
this.bitFilterSize = (int)Math.ceil(expectedItemCount * 4.8);
break;
}
case Low : {
this.bitFilterSize = (int)Math.ceil(expectedItemCount * (9.6 + 4.8));
break;
}
default : {
this.bitFilterSize = (int)Math.ceil(expectedItemCount * 9.6);
}
}
this.countOfHashNumCreatePerOneElement
= (int) Math.round((this.bitFilterSize / (double)expectedItemCount) * Math.log(2.0));
numberOfAddedElements = 0;
this.bitFilter = new BitSet(bitFilterSize);
}
public MyBasicBloomFilter(int expectedItemCount) {
this(expectedItemCount, FalsePositiveProbability.Middle);
}
/**
* ハッシュ化
* @param data 入力データ
* @param hashCount 回数
* @return ハッシュ化して求められた数値（ビット立て位置）
*/
public static int[] createHashes(byte[] data, int hashCount) {
int[] result = new int[hashCount];
int k = 0;
byte seed = 0;
while (k < hashCount) {
// ハッシュ化
byte[] digest;
synchronized (digestFunction) {
digestFunction.update(++seed);
digest = digestFunction.digest(data);
}
// 4Byte区切りでint化して配列に詰める
for (int i = 0; i < digest.length/4 && k < hashCount; i++) {
int h = 0;
for (int j = (i*4); j < (i*4)+4; j++) {
h <<= 8;
h |= ((int) digest[j]) & 0xFF;
}
result[k] = h;
k++;
}
}
return result;
}
/**
* 要素の追加
* @param element
*/
public void add(E element) {
add(element.toString().getBytes(DEFAULT_CHARSET));
}
/**
* 要素の追加
* @param bytes
*/
public void add(byte[] bytes) {
int[] hashes = createHashes(bytes, countOfHashNumCreatePerOneElement);
for (int hash : hashes) bitFilter.set(Math.abs(hash % bitFilterSize), true);
numberOfAddedElements ++;
}
/**
* 判定
* @param element 要素
* @return
*/
public boolean contains(E element) {
return contains(element.toString().getBytes(DEFAULT_CHARSET));
}
/**
* 判定
* @param bytes 要素のバイト配列
* @return
*/
public boolean contains(byte[] bytes) {
int[] hashes = createHashes(bytes, countOfHashNumCreatePerOneElement);
for (int hash : hashes) {
if (!bitFilter.get(Math.abs(hash % bitFilterSize))) {
return false;
}
}
return true;
}
/**
* フィルタの取得
* @return フィルタ
*/
public BitSet getBitSet() {
return bitFilter;
}
/**
* 追加された項目数を取得
* @return 項目数
*/
public int getAddItemCount(){
return this.numberOfAddedElements;
}
public double getFalsePositiveProbability() {
// (1 - e^(-k * n / m)) ^ k
return
Math.pow((1 - Math.exp(-countOfHashNumCreatePerOneElement * (double) this.numberOfAddedElements
/ (double) bitFilterSize)), countOfHashNumCreatePerOneElement);
}
}
呼び出しサンプル
import java.util.ArrayList;
import java.util.List;
import org.apache.commons.lang.RandomStringUtils;
/**
* BloomFilterを試す
* @author owl
*/
public class ExecBloomFilterSample {
public static void main(String argv[]){
MyBasicBloomFilter<String> bf = new MyBasicBloomFilter<>(1000000, MyBasicBloomFilter.FalsePositiveProbability.Low);
List<String> addList = new ArrayList<>(); // BloomFilterに追加するデータ
List<String> notAddList = new ArrayList<>(); // BloomFilterに追加しないデータ
// １万件のデータをBloomFilterに追加
// 同時にBloomFilterに追加しない１万件の検証データも生成
for(int i=0;i<2000000;i++){
if(i % 2 == 0) {
String s = RandomStringUtils.randomAlphabetic(24);
bf.add(s);
addList.add(s);
} else {
notAddList.add(RandomStringUtils.randomAlphabetic(24));
}
}
// BloomFilterの状態を出力
for(int i=0; i < bf.getBitSet().size(); i++ ){
System.out.print(bf.getBitSet().get(i) ? "1" : "0");
if(i>1000) break;
}
// BloomFilterのデータサイズと計算された偽陽性確率を出力
System.out.println();
System.out.println("データサイズ --> " + bf.getBitSet().size() + " | K-Byteバイト数" + (double)((double)(bf.getBitSet().size())/8/1024));
System.out.println("偽陽性確率 --> " + String.format("%.5f", bf.getFalsePositiveProbability()));
// BloomFilterに追加したデータが全て陽性判定されるか確認
// （問題なければ何も表示されない）
System.out.println();
System.out.println("■■■■■ 追加データが全て陽性判定されるかチェックを開始 ■■■■■");
addList
.stream()
.sequential()
.filter(e -> !bf.contains(e))
.forEach(e-> System.out.println("はずれ判定：" + e));
// BloomFilterに追加していないデータが誤って陽性判定されたカウントを出力
System.out.println("■■■■■ 非追加データが偽陽性判定されるかチェックを開始 ■■■■■");
System.out.println("1000000データ中..." +
notAddList
.stream()
.sequential()
.filter(e -> bf.contains(e))
.count() + "件の偽陽性を検出しました。");
}
}
実行結果
000011100100001110011011100010101001100110111000100011001(省略)
データサイズ --> 14400000 | K-Byteバイト数1757.8125
偽陽性確率 --> 0.00099
■■■■■ 追加データが全て陽性判定されるかチェックを開始 ■■■■■
■■■■■ 非追加データが偽陽性判定されるかチェックを開始 ■■■■■
1000000データ中...994件の偽陽性を検出しました。