LRU削除キャッシュDBM

キーと値の連想配列であるDBMのインターフェイスでLRUレコード削除機能付きのキャッシュ機構を実装してみた話。

情報技術の文脈において、キャッシュ（cache）とは、生成あるいは取得するためのコストが高いデータを一時的に保存しておいて、それを再利用することによって性能の向上を図る機構である。キャッシュのレコードはオンメモリで保持するのが一般的であり、その容量に限りがある。キャッシュ上に所望のレコードがない場合には、コストのかかる「本番」の処理を再試行することで同じデータを生成できるので、あまり使われないレコードは消しても問題ない。限られた容量のキャッシュ上に、よく使われる（ヒット率の高い）レコードを残し、そうでないレコードを破棄するというのが性能上重要になる。

いずれ、Tkrzwをベースにしたデータベースサービスを実装するかもしれない。その際には、要求される機能要件と非機能要件に応じて、ストレージ（ファイルかオンメモリか）とデータ構造（ハッシュテーブルとB+木とスキップリスト）が選べるのは大きな強みである。それらとは別に、キャッシュサービスとしての需要も考えられる。アプリケーション側から不要なレコードを削除する命令を出し続ける仕組みにすると煩雑になるため、不要なデータはサーバ側で判断して暗黙的に削除してくれる方が望ましい。キャッシュサービスという場合には最低限、メモリ使用量を一定に保つための仕組みを備えなければならない。

不要なレコードを機械的に判断するために、各レコードに生存期間（TTL = Time To Live）のメタデータを設定し、それを過ぎたものを削除するという方法がある。具体的なTTL値の設定はレコードを追加する際にアプリケーション側で行う。この方法の利点は、古すぎて利用価値のなくなったレコードがキャッシュ上に蓄積されたり再利用されたりするのを防げることになる。欠点は、メモリ使用量を一定にする保証がないことである。別のアプローチとして、キャッシュ上のレコード数やそのサイズの合計に上限を設け、それを過ぎたら、古いレコードから消すという方法がある。この方式の利点はメモリ使用量を一定にすることが保証されることである。欠点は、古い情報がいつまでも残る可能性があることである。みんな大好きmemcachedはその二つともをサポートしているので、使い勝手がとてもよい。

今回実装するキャッシュDBMでは、TTL方式は採用せず、レコード数に上限を設けるだけにする。メモリ使用量を保証する機能だけはサーバ側が担っていないと、安心して運用することができない。必要であれば、アプリケーション側の責任で各レコードにTTLを付与し、古いレコードは無視するようにしてもらう。それが煩雑に感じる場合、TTLを暗黙的に付与するラッパーを書けばよい。TTL方式を使いたくないもう一つの理由は、性能の問題である。各レコードにTTLを付与することによる空間効率の悪化は所詮4バイトか5バイトで済むので大した問題ではない。TTLが過ぎたレコードを削除するためにデータベース全体にイテレータを回すか、削除予定時刻が近い順にレコードを並べることが必要になるのが問題である。どちらの方法も実装は簡単だが、CPU負荷かメモリ使用量を増やしてしまう欠点がある。

さて、タイムスタンプを使わずにレコードの要不要を判断するための典型的な方法として、LRU削除という方式が挙げられる。B+木のキャッシュの記事でも説明したが、最近使われたレコードはまた使われる可能性が高いという仮定に基づく方法である。全てのレコードを連結リストで繋いで、個々のレコードがアクセスされる度に、その位置を連結リストの末尾に移動させる。そうすると、連結リストの前方には最も古く利用された（Least Recent Usedな）レコードが集まる。キャッシュの容量が上限を超えた際には、LRUなレコードから消していけばよい。

ところで、レコード数とメモリ使用量が比例するのは確かだが、メモリ使用量をレコード数の上限だけで制御するのは面倒だ。レコードの平均的なサイズが事前に把握した上で、利用可能メモリ量を平均レコードサイズで割るといった作業が必要になる。しかし、推定が実際と異なることは多いし、運用してみないとまともな推定ができないことも多いだろう。それよりは、キャッシュ内でメモリ使用量を把握しておいて、それを過ぎたら不要レコードを消すという方式の方が管理しやすい。したがって、最大メモリ使用量というパラメータも設定できるようにしよう。コンストラクタで最大レコード数と最大メモリ使用量を設定できるようにする。1000万レコード以下かつメモリ使用量4GB以下という設定にするには、以下のようにDBMを構築する。

constexpr int64_t max_num_records = 10000000;  // 10 million
constexpr int64_t max_memory_usage = 4LL << 30;  // 4GiB
CacheDBM dbm(max_num_records, max_memory_usage);

dbm.Set("1234", "I love you.");
dbm.Set("5678", "You love me.");
...

最大メモリ使用量だけ設定すれば最大レコード数の指定はいらないと思うかもしれない。しかし、レコードを効率的に検索するためにハッシュテーブルを使っていて、ハッシュテーブルのバケット数を最大レコード数から算出したいので、最大レコード数の指定は必須とする。ただし、この値は正確でなくても構わない。最大メモリ使用量の方はオプションで、デフォルト値は無限ということにする。最大メモリ使用量を設定せずに最大レコード数に大きすぎる設定をした場合、仮想メモリのスワップが発生して、性能がガタ落ちになってしまう。逆に最大レコード数が小さすぎると、せっかく搭載されているメモリが遊んでしまうことになり、コスパが悪くなる。最大メモリ使用量を設定する場合は、それが保険となるので、最大レコード数を大きめに設定することができる。真面目なユースケースでは最大メモリ使用量は実質必須と言ってよいだろう。

DBM内でメモリ使用量を把握するにはどうすればよいか。各レコードに対して、そのキーのサイズと値のサイズとフットプリントのサイズを合計した値を算出し、それを総計したものがレコードのメモリ使用量となる。フットプリントは典型的には26バイトで、以下の内訳になる。

• ハッシュバケットから全レコードを繋ぐ連結リストのポインタ8バイト
• 最初のレコードから最後のレコードまでを繋ぐ連結リストのポインタ8バイト
• 最後のレコードから最初のレコードまでを繋ぐ連結リストのポインタ8バイト
• キーのサイズのメタデータ1（から6）バイト
• 値のサイズのメタデータ1（から6）バイト

レコードのメモリ使用量に加えて、データベース全体で使うメモリの使用量も考える必要がある。主なものはハッシュテーブルであり、バケット数に8バイトを賭けたメモリ使用量になる。バケット数は最大レコードサイズの1.5倍を取るということにしよう。そうすると、キーが平均8バイトで値が平均100バイトのレコードを1000万個入れるとすると、(8 + 100 + 26) * 10000000 + 8 * 10000000 * 1.5 で、およそ1.4GBの使用メモリということになろうか。この計算ができていれば最大メモリ使用量を設定する必要はないのだが、念のため、4GBとかいった上限値を設定しておくことは有用であろう。なお、実際のメモリ使用量（RSS = Resident Set Size）にはプログラムのコードやアロケータ（malloc）が使うメモリも含まれるのだが、それに関してはライブラリ側からは制御できない。よって、キャッシュサービスにマシンの全リソースを捧げるにしても、安心のためには、搭載する物理メモリ量の7割くらいを上限値に設定することになるだろう。

LRU削除機能のためには全レコードを双方向連結リストで繋ぐ必要があるのだが、連結リストの更新処理は並列に行えないという欠点がある。順序関係があるものは並列に更新できないのだ。しかし、キャッシュサービスは性能が命なので、並列化は必須だ。よって、内部でシャーディングを施して並列化を実現する。個々のシャードを管理する内部的な連想配列をスロットと呼ぼう。すなわち、内部的に32個のスロットに分けて管理して、その各々でハッシュテーブルと連結リストを持たせる。排他制御はスロット毎に持つmutexで行う。最近のマシンだ6コア12スレッドとかが普通に実装されるようになってきたが、スロット数としては32個もあれば十分だろう。個々のレコードに対しては、キーのハッシュ値によって、どのスロットに所属させるか決める。ハッシュ値の下位8ビットはスロットのインデックスの算定に用いて、残りをハッシュバケットのインデックス算定に使えばよいだろう。レコードの追加操作は以下のようなコードで実装される。

uint64_t hash = PrimaryHash(key);
int32_t slot_index = hash & 0xFF;
int64_t bucket_index = (hash >> 8) % num_buckets_;
slots_[slot_index].Set(bucket_index, key, value);

スロット化によって、完全なLRU削除は実現されなくなる。レコード数の上限を1000万と設定したなら、個々のスロットのレコード数の上限として31万くらいが設定される。よって、理論的な最悪のケースでは全レコードが特定のスロットに集中して、31万個より古いレコードが消される可能性がある。とはいえ、そのようなことが実際に起こる確率はほぼゼロであり、たとえ起きたとしてもキャッシュデータなので問題ない。理論的な保証よりは実際の性能の方が重要であろう。

性能テストをしてみた。キーと値がそれぞれ8バイトでランダムなパターンを持つレコードを1億件登録する。LRU削除なしでスロット化しない実装であるTinyDBMと、LRU削除ありでスロット化した実装であるCacheDBMを比較する。

class	Set	Get	Remove	RAM usage
TinyDBM (1 thread)	2,267,644 QPS	2,576,552 QPS	2,690,487 QPS	3573.0 MB
CacheDBM (1 thread)	2,263,022 QPS	2,257,323 QPS	2,745,666 QPS	4999.2 MB
TinyDBM (10 threads)	7,376,532 QPS	8,314,453 QPS	7,596,498 QPS	3573.0 MB
CacheDBM (10 threads)	6,871,719 QPS	7,358,504 QPS	8,325,958 QPS	4999.5 MB

上記で確認できるように、マルチスレッドによる並列処理は十分に機能していて、10スレッドを使うと700万QPS程度で検索も更新もできる。データベースサーバの内部で使うと仮定した場合、この性能であればボトルネックになることはないだろう。スループットが大きければ、安価なCPUを採用して、その分の金をRAMの増設やマシン自体の増設に回せるので、結果的にスケールアップやスケールアウトに繋がる。スループットはTinyDBMとCacheDBMでほぼ同等だが、メモリ使用量はTinyDBMの方が少ない。これはCacheDBMは連結リストのためのフットプリントが大きいためである。ただし、実際のユースケースではレコードの値のサイズがもっと大きいのが典型的であろうから、フットプリントが占める割合はもっと低くなることだろう。

これらオンメモリDBMは、データベースサーバに組み込む以外でも、JavaやPythonやRubyのプロセスに組み込んで使っても有用であろう。DBMには文字列しか格納できないのでオブジェクトをシリアライズして扱うことになるのだが、各言語のネイティブなオブジェクトを大量に保持し続けるよりは、大幅なメモリ節約になる。1億レコードをマシン1台でこねくり回せるのだ。