DBMのインターフェイスでオンメモリのストレージを実現できる。その設計と実装について考えてみよう。
オンメモリということは永続化されないってことだから、それってデータベースと呼べるのか。永続化しないならデータベースと呼べないと思う。しかし、最終的に帳尻が合えば良いのだ。運用時には完全にオンメモリでデータを保持するにしても、Openした時にファイルから全レコードを読み込んで、Closeした時に全てのレコードをファイルに書き出すようにすればいい。オンメモリデータベースも以下のようなDBMのインターフェイスを実装する立派なデータベースだ。
class DBM {
public:
Status Open(const std::string& path, bool writable);
Status Close();
Status Set(std::string_view key, std::string_view value);
Status Get(std::string_view key, std::string* value);
Status Remove(std::string_view key);
Status Synchronize(bool hard);
};利用するコードは以下のようになるだろう。普通のDBMを使うのと全く変わらない。
StdTreeDBM dbm;
dbm.Open("casket.flat", true);
dbm.Set("北海道", "札幌市");
dbm.Set("岩手県", "盛岡市");
dbm.Set("宮城県", "仙台市");
std::cout << dbm.GetSimple("岩手県") << std::endl;
dbm.Close();実際のところ、このアプローチは結構実用的なのだ。Openの際の読み込みもCloseの際の書き出しもシーケンシャルアクセスなので、意外に高速に実行できる。新しめのマシンで数GB程度のデータベースを扱うなら、起動や終了にかかる時間は1分もかからないだろう。それでいて、オンメモリなので、運用時の性能は圧倒的だ。プロセスが死ねばデータが失われるので、運用時にたまにバックアップを取る場合があるだろうが、それにはSynchronizeメソッドを呼べば良い。Closeと同様にファイルの書き出しを行うが、メモリ上のデータの破棄は行わないというメソッドだ。ファイル上のDBMを運用していたとしても定期的なバックアップは取るだろうから、運用手順は同じだ。Redisとかもそんな感じの位置づけだろう。
オンメモリデータベースのプロトタイプとして、まずは標準ライブラリのハッシュテーブルによる連想配列であるstd::unordered_map
Status StdTreeDBM::Get(std::string_view key, std::string* value) {
std::shared_lock<std::shared_timed_mutex> lock(mutex_);
auto it = map_.find(std::string(key));
if (it == map_.end()) {
return Status(Status::NOT_FOUND_ERROR);
}
*value = it->second;
return Status(Status::SUCCESS);
}constではないstd::mapに対するfindはconstではないバージョンのfindが使われるので、検索操作をしつつも、内部状態が変更されるかもしれない。実装によっては変更操作が行われずに動くかもしれないが、実装によっては動かないかもしれない。赤黒木のリバランスをしているかもしれない。とにかく保証がない。const修飾されていないメソッドをマルチスレッドで読んだ場合の動作は未定義であり、CPUが爆発しても文句は言えないのだ。よって、const参照にキャストしてからfindを呼ぶのが正解だ。同じくbeginやendも潜在的には危ないので、const参照に対してしか呼び出しちゃいけない（C++20からはcbeginやcendを呼ぶという手もあるが、なぜかcfindはない）。
さらに、ハッシュデータベースの設計で詳述したハッシュロックを使ったオンメモリの実装TinyDBMも考えてみた。ハッシュバケット毎に（実際はスロット毎に）排他制御を行うので、ほとんどの場合で、更新操作ですら並列に実行される。また、std::map
同様にして、ツリーデータベースの構造をほぼそのまま流用して、オンメモリでB+木を実現するBabyDBMというのも考えてみた。ツリーデータベースと同じく排他制御はページロックなので、バケットのスロットロックには負けるが、更新処理の並列性もある程度は確保している。TinyDBMと同様にメモリ上でシリアライズしたデータを保持することによって、メモリ使用量をできるだけ減らす努力をする。連結リストではなく配列でレコードを管理する分、空間効率はこちらが上回るはずだ。
試験的な実装をしてみたので、四つの実装の比較をしてみよう。おさらいになるが、StdHashDBMの中身はunordered_mapで、StdTreeDBMの中身はstd::mapで、TinyDBMの中身は独自実装のハッシュテーブルで、BabyDBMは独自実装のB+木だ。まずはシングルスレッドで100万件のSetとGetとRemoveを行う。キーは "00000001" から "00999999" までの8バイトのシーケンシャルな数列で、値は8バイトの "vvvvvvvv" 固定とする。それぞれの実装でスループットとメモリ使用量を測定する。ハッシュテーブルのバケット数はレコード数と同じにする。
| class | Set | Get | Remove | memory usage |
| StdHashDBM | 2,012,894 QPS | 2,920,263 QPS | 2,661,896 QPS | 99.1 MB |
| StdTreeDBM | 1,331,320 QPS | 2,957,670 QPS | 2,751,585 QPS | 104.5 MB |
| TinyDBM | 2,506,691 QPS | 2,929,785 QPS | 2,744,441 QPS | 54.7 MB |
| BabyDBM | 2,080,122 QPS | 2,331,687 QPS | 2,084,949 QPS | 61.1 MB |
同じ実験を10スレッドで行う。
| class | Set | Get | Remove | memory usage |
| StdHashDBM | 804,870 QPS | 8,667,923 QPS | 1,131,562 QPS | 99.3 MB |
| StdTreeDBM | 387,786 QPS | 8,069,927 QPS | 1,128,146 QPS | 106.6 MB |
| TinyDBM | 5,058,370 QPS | 8,370,093 QPS | 6,611,346 QPS | 54.8 MB |
| BabyDBM | 1,136,897 QPS | 7,395,522 QPS | 1,213,289 QPS | 50.5 MB |
どの実装もGetはシングルスレッドで300万QPS近いスループットが出るのは驚異的とも感じるが、単にメモリ上のハッシュテーブルや赤黒木やB+木にアクセスしているだけなのでそりゃそうだろう。予想通り、TinyDBMとBabyDBMのメモリ消費量は標準コンテナよりかなり少ないので、これらは価値がある実装だと言えそうだ。あと面白いのは、シーケンシャルアクセスの場合、赤黒木であるStdTreeDBMの性能がハッシュテーブルである他の二つに肉薄もしくは凌駕しているということだ。マルチスレッドの結果に目を移すと、これも予想通り、ハッシュロックを使っているTinyDBMの更新系のスループットが圧倒的に高いことがわかる。これは良い実装だ。500万QPSで更新できるデータベースなんてのはこんな感じの実装でないと不可能だ。オンメモリのB+木であるところのBabyDBMも見所がある。メモリ使用量が赤黒木であるStdTreeDBMの半分しかないにもかかわらず、ほぼ同じ性能が出せている。
この暗い闇の底で耐え続けた我らには100万レコードぽっちの実験ではもはや足りない！ 一心不乱に1億レコードの実験をしようじゃないか。今回はキーのパターンをランダムに設定して、"00000000" から "99999999" までの数列を生成する。いくつかのレコードはキーの重複で上書きされるので、最終的なレコード数は6300万ほどになる。まずはシングルスレッドから。
| class | Set | Get | Remove | memory usage |
| StdHashDBM | 1,691,914 QPS | 2,131,297 QPS | 2,315,516 QPS | 6409.0 MB |
| StdTreeDBM | 463,928 QPS | 516,673 QPS | 505,744 QPS | 6593.6 MB |
| TinyDBM | 2,267,644 QPS | 2,576,552 QPS | 2,690,487 QPS | 3573.0 MB |
| BabyDBM | 490,861 QPS | 493,863 QPS | 489,624 QPS | 2963.1 MB |
同じ実験を10スレッドで行う。
| class | Set | Get | Remove | memory usage |
| StdHashDBM | 711,054 QPS | 10,794,019 QPS | 1,334,017 QPS | 6409.6 MB |
| StdTreeDBM | 103,929 QPS | 3,944,576 QPS | 121,817 QPS | 6595.6 MB |
| TinyDBM | 7,376,532 QPS | 8,314,453 QPS | 7,596,498 QPS | 3573.0 MB |
| BabyDBM | 687,414 QPS | 3,481,460 QPS | 655,081 QPS | 2960.3 MB |
ハッシュテーブルであるStdHashDBMとTinyDBMの性能はレコード数の増加に全く影響を受けないことがわかる。これがO(1)の威力だ。ランダムアクセスになると、O(log N)である赤黒木のStdTreeDBMと同じくO(log N)であるB+木のBabyDBMは少し劣ってしまう。とはいえ、それでも10スレッドの読み取りで300万QPS以上出るのだから素晴らしい。マルチスレッドの更新操作のスループットではやはりTinyDBMが圧倒的だ。スレッドが占有ロックで互いをブロックしまくる結果、StdHashDBMとStdTreeDBMの更新系スループットはマルチスレッド環境だとかなり落ちてしまう。B+木に並列性を組み込んだBabyDBMでは並列更新時の性能も上がっているので、設計及び実装に成功していると言えそうだ。
この実験で、オンメモリデータベースの性能が把握できた。各種スクリプト言語のバインディングを用意した際には、ビルトインの連想配列クラスの代用として、TinyDBMとBabyDBMが有用になるはずだ。時間効率も空間効率も何倍も良いはずなので。そして、ファイルによるハッシュデータベースやツリーデータベースもこれらに迫るべく最適化していきたい。ストレージ層がオンメモリI/Oであれば、かなり近いところまでとは言わないが、半分くらいの性能まではいける気がする。
ふと思ったのだが、もしかして巷のプログラマの多くはスレッドプログラミングをしてないってことないかな。もしそうだと、スレッド並列性を追求しているのって馬鹿みたいに映るかもしれない。しかし、KTのようにサービス化した暁にはスレッド並列性は強烈に生きてくるので、暖かく見守ってほしい。
