LRU は最近を信じ、ブルームフィルタは「ない」だけを確信する

一言でいうと

キャッシュは「もうすぐ再び使うもの」を当てる賭けであり、LRUは「今使ったものはすぐまた使う」に賭けます。ブルームフィルタは逆に、「確実にない」ことだけを約束する代わりに、ごく少ないビットで集合を持ち歩きます。どちらも、何を信じる構造なのかを知って使わないと、数字が期待どおりに出ません。

なぜ必要なのか

遅いストレージの前に速いストレージを置いた途端に、質問が2つ生まれます。場所が足りなくなったら何を捨てるのか。そして、そもそも存在しないものを探しに、遅いほうまで行く必要があるのか。

最初の質問の教科書的な答えがLRU(least recently used)です。functools.lru_cacheのドキュメントは、LRUキャッシュは「直近の呼び出しが、これから来る呼び出しをもっともよく予測するとき」にもっともよく動作すると述べ、毎日変わるニュースサーバーの人気記事を例に挙げます。逆に言えば、その仮定が崩れるアクセス(全キーを1回走査するバッチやバックフィル)では、LRUは二度と来ないキーを「最新」として扱うために、肝心のよく使うキーを追い出してしまいます。Cache replacement policiesの項目は、これをcache pollutionと呼びます。

2つ目の質問が、ブルームフィルタの出番です。加入の有無の確認、すでに見たURLの除外、存在しないキーで叩いてくるボットのリクエストのように、答えがほとんど「ない」である問い合わせは、否定の結果までキャッシュに入れても、キー空間が広いとすぐに押し出されます。BroderとMitzenmacherのサーベイNetwork Applications of Bloom Filters: A Survey(Internet Mathematics 1巻4号)は、これを「ブルームフィルタの原則」としてまとめています。リストや集合を使う場面で、空間が貴重であり、偽陽性の影響を減らせるなら、ブルームフィルタを検討してみる、という原則です。

どう動くのか

LRUをO(1)で: 必要な操作は3つです。キーで探すこと、「今使った」と印を付けること、もっとも長く使っていないものを捨てること。ハッシュテーブルが1つ目を、二重連結リストが残り2つを、定数時間で行います(ノードを外して末尾に付け、先頭を外します)。Pythonでは、OrderedDictがこの組み合わせをすでに持っています。ドキュメントは、OrderedDictは並べ替えの操作に強いように設計されており、さまざまな種類のLRUキャッシュを作るのに適していると述べ、move_to_end(key)(存在しないキーならKeyError)とpopitem(last=False)(FIFOの順序で取り出す)を提供しています。

操作	LRU	FIFO
getでヒット	末尾(最新)へ移します	そのままにします
存在するキーへのput	値の更新 + 末尾へ移します	値だけ更新します
あふれたとき	先頭(もっとも長く使っていないもの)を削除します	先頭(もっとも先に入ったもの)を削除します

表の最初の1行が、2つのポリシーの違いのほぼすべてです。そのため、getで最近性の更新を忘れたLRUは、名前だけがLRUのFIFOになり、ヒット数が静かに減ります。リスト(list)で順序を管理すると、removeがO(n)なので、容量が大きくなるほど遅くなりますが、小さなテストでは表に出ません。

現実のキャッシュが正確なLRUであるとも限りません。Redisのevictionのドキュメントは、Redisはキーをいくつかランダムに選び、その中でもっとも長く使っていないものを捨てる近似を使っており、本物のLRUはメモリがより多く必要だからだと説明しています(サンプル数はmaxmemory-samples)。

ブルームフィルタ: mビットの配列と、k個のハッシュでできています。入れるときはk個の位置を1にし、問い合わせるときは、k個の位置がすべて1なら「あるかもしれない」、1つでも0なら「確実にない」です。立てたビットは下ろさないので、入れたキーについて偽陰性は生じません。サーベイ2.1節の計算によれば、n個を入れた後の偽陽性率はおよそ(1 − e^(−kn/m))^kで、mとnが決まるとk = (m/n)·ln 2で最小になります。2.2節は、目標の偽陽性率pに必要なビット数を、m ≈ n·log2(1/p) / ln 2と記しています。例として、n = 1,000、p = 1%なら、mは約9,586ビット(1.2KB強)、kは7です。

k個の独立したハッシュを別々に求める必要もありません。KirschとMitzenmacherのLess Hashing, Same Performance(2008)は、2つのハッシュh1、h2から、g_i(x) = h1(x) + i·h2(x)を作って使っても、漸近的な偽陽性率が悪化しないことを示しました。このラボは、hashlibのsha256ダイジェスト(32バイト)からh1、h2を取り出します。組み込みのhash()を使わない理由は、PYTHONHASHSEEDのドキュメントにあるとおり、文字列ハッシュのシードがデフォルトでランダムであり、別のプロセスが作ったフィルタを、同じルールで読めないからです。

偽陽性率を測るとき、分母は本当に存在しないキーへのクエリ数です。全クエリで割ると、存在するキーの割合だけ値が小さくなり、フィルタが実際よりよく見えます。

現場での姿

ClickHouseのスキップインデックスのうちbloom_filterは、許容する偽陽性率を1つ引数に取り(デフォルトは0.025)、ドキュメントは、偽陽性は不要なブロックをいくつか余分に読むだけなので大きな問題ではないと記しています。「ClickHouse — 列指向分析 DB を中身から」コースが、実際のグラニュール数でその場面を見せてくれます。有効期限とevictionのポリシーの選択やcache-asideは「Redisとキャッシュ」コースが、同じ局所性の論理がCPUキャッシュ階層でどのように現れるかは「コンピュータ構成」コースが扱います。このモジュールは、その下にあるデータ構造を自分で作り、数字で確認する場所です。

次のラボですること

偏ったアクセス記録で、LRUとFIFOのヒット数を容量別に測り、1回走査するスキャンがホットなキーをいくつ押し出すかを数えます。続いて、式でmとkを選び、固定されたハッシュのルールでブルームフィルタを作って偽陽性率を測ったあと、フィルタをLRUの前に置くとDB問い合わせが何回減るかを計算します。