pixivでBloomFilterを使うためにやったこと

こんにちは。最近はAndroidアプリ開発に入門しました、@edvakfです。

pixivではキャッシュ兼汎用KVSとしてKyotoTycoon (KT)を使用しており、頻繁にアクセスされるキーはアプリケーションサーバー内のAPC（PHPのshared memory cacheです）にもキャッシュすることで多段化しています。

このような構成の弱点として、「ほとんどの場合は値が無いけど毎回存在確認が必要なキー」の場合に前段にキャッシュが無くて毎回後段にまで問い合わせなければいけないという問題があります。ネガティブキャッシュ（値がないことをキャッシュする）を使うという手もありますが、問い合わせるキーの数が膨大になってくると現実的ではありません。

pixivでは、作品に付いている最大10個のタグについて、ピクシブ百科事典に記事があるかどうかを判定する必要がありました。これに加え、最近ではBOOTHに商品がある場合にもアイコンを出しています。ここのために最大20個のキーをKTに問い合わせるのはかなり効率が悪いです。

そこで、こういう時によく使われるBloomFilterを使ってみようということになりました。BloomFilterの導入にあたって考慮したことなどを書いていきたいと思います。

BloomFilterがどういうものかはググれば色々出てきますが、社内勉強会で@nanikakaさんがやったスライドがあるので貼っておきます。

すべてのタグを含むことができるBloomFilterはそれなりのサイズになる

BloomFilterの特徴の1つとして、格納するキー数が増えても記憶容量が増えないことがありますが、あらかじめ十分な数のキーを格納しておける容量のBloomFilterを作っておく必要はあります。

例えばBOOTHに商品が存在するタグは3万程度ですので、誤判定確率を1%に抑えたいとすると、30万ビット程度(=37kB)は確保しておく必要があります（計算は後述します）。将来その数が10万ぐらいになるまで耐えられるようにすると、100kB以上の長さのBloomFilterになります。

pixivでの使い方として、BloomFilterはKTに保存しておき、APCにもキャッシュしておくことを考えていましたが、APCから100kBを取り出すのは5ms以上かかってしまいます。毎リクエストにこれだけかかるのはpixivとしては許容できる時間ではありません。

これだけの容量をメモリに展開した上で、キーの存在確認のためにアクセスされるビット数は、使用するハッシュ関数の数だけです。ハッシュ関数の数が10個だとすると、1つのキーの存在確認のために100kBのうち10ビットしか使われないことになります。メモリアクセスを局所化することで最適化が図れそうです。

BloomFilterの分割

そこで、すべてのキーを格納するBloomFilterを1本持つのではなく、一部のキーだけを格納するBloomFilterを何本も用意することにしました。まずキーのハッシュ値を計算し、そのキーを格納するBloomFilterを選ぶことになります。

APCから取り出すのに現実的なサイズを1kB(=8192ビット)と決めると、誤判定率が1%を超えないキー数は800ぐらいになります。ということは、BloomFilterを100本用意しておけば、BOOTHに登録されているタグが8万になるまでは大丈夫という計算になります。

これでも100本*1kBのデータを持つだけ良いですし、APCに前段キャッシュさせることができるので、効率ははるかに良いです。APCから1kBのデータを取得してハッシュ関数を10回適用しても、所要時間は0.1ms以下で済みました。

BloomFilterの分割についてはKyotoCabinetの内部でも使われているそうです。分割したいモチベーションは違いますが、やっていることは同じです。

• http://fallabs.com/blog-ja/promenade.cgi?id=70

パラメータ調整

WikipediaのBloomFilterの記事の誤検出の可能性という項に計算式があります。

これによると、ブルームフィルタの誤検出率は、フィルターのビット数(m)、ハッシュ関数の数(k)、フィルターに格納されているキーの数(n)で表すことができます。

p = ( 1 - (1-1/m)^(k*n) )^k

mは8192ビットにすると決めたので、kとnの平面にpの等高線を引いてみましょう。

x軸がハッシュ関数の数、y軸が格納するキーの数で、青、緑、黄色、赤の線がそれぞれ誤検出率 0.5%, 1.0%, 1.5%, 2.0% の線になります。

これを見ると、1kBのブルームフィルタに格納して誤検出率が1%ぐらいに収まるキー数は、最適なハッシュ関数の数を選択しても800キーぐらいであることがわかります。ハッシュ関数は少なすぎても多すぎても誤検出率が上がり、だいたい6個ぐらいが最適です（何%まで許容するかによって若干変わります）。

将来的に格納するキーが増えてきて、誤検出率1%を超えると、それ以上は急激に誤検出率が上がっていく傾向もわかるかと思います 。

BloomFilter生成バッチ

BOOTHや百科事典に存在するタグにリンクを貼るという用途においては、あまりリアルタイム性が必要ではありませんので1日数回の更新で十分です。逆に、BOOTHや百科事典で更新がある度にBloomFilterを更新するということをすると密結合度が高くなりそうだったので避けました。（しかも、今回の要件がBloomFilterにぴったりな点として、間違ってアイコンが出てしまっていても少々なら問題が無いということです。もし実際に商品が無いタグにBOOTHアイコンが出ているのを見つけたら、ラッキーと思ってください。）

BloomFilterの更新は、最近追加されたものについてだけKTから引っ張ってきて追加することもできますし、すべてのキーを空のBloomFilterに再登録して全更新することもできます。いずれにせよ、BloomFilterのビット列のうち、現在埋まっているビットの割合を求めることができるため、ここから現在の誤検出率を計算できます。

p = (埋まっているビットの割合)^k

BloomFilter更新バッチで誤検出率を計算しておいて、一定以上になったら失敗するようにしています。

実装

実装は自前のものを使いました。分割関係の処理は入れずに100行程度です。以下に公開しておきました。特に権利は主張しませんのでパブリックドメインと思ってお使いください。

• https://gist.github.com/edvakf/ec98cd4ff184b8222520

まとめ

• BloomFilterをウェブアプリケーションのアプリケーションサーバー内キャッシュとして使用する場合、BloomFilterの分割が効果的である
• 1kBのBloomFilterで誤判定率を1%に抑えたい場合、最適なハッシュ関数の数は6ぐらいで、800キー程度まで格納できる
• BloomFilterの誤検出率は埋まっているビットの割合から求められるので、これを監視してパラメータの再調整の時期を見計らうと良い

2014/8/11 追記: フィルター長について

この記事を書いた時点ではフィルター長を1kBと適当に決めていましたが、その後検証したところ、APCから取り出すデータの容量は約8kBまではパフォーマンスに大きな違いが見られなかったため、8kBに変更しました。

8kBにしても上記の考察はそのままあてはまり、誤判定率を1%に抑えたければ6500キー程度まで格納でき、最適なハッシュ関数の数は6程度です。1つのBloomFilterに格納できるキーを増やすことで、APCのキャッシュヒット率の向上が期待できます。

確率と計算 ―乱択アルゴリズムと確率的解析―