豪鬼メモ

一瞬千撃

I/Oのバッチ化によるDBの性能改善

前回までの一連の実験で、ダイレクトI/Oを使ってデータベースを運用する際の性能特性が見えてきた。そこで洗い出された課題を解決し、おそらくは最善の効率に到達した。性能評価の結果としては、ダイレクトI/Oを使ったデータベースの性能を、書き込みが9.3倍、読み込みが6.3倍も高速化することが確かめられた。まるで某コンピュータメーカーの広告のようではないか。Tkrzw-0.9.20から有効なので、ぜひお手元でお試しいただきたい。
f:id:fridaynight:20210525024040p:plain


一定の単位にアラインメントされたオフセットおよびサイズを持つページを単位としたキャッシュがページキャッシュである。ダイレクトI/Oを前提とする場合、ページのアラインメントは下層のデバイスのブロックサイズと同じかその倍数である必要がある。

f:id:fridaynight:20210523204942p:plain
上の図を見ていただこう。ブロックサイズが512として、400バイトのオフセットから300バイトを書き込むとしよう。その場合、0バイトで始まるブロック0と512バイトで始まるブロック1の二つを読み出してから、ブロック0のページの400バイトから終わりまでの112バイトと、ブロック1のページの始めから187バイトまでの188バイトを書き換えて、両方のページを該当のブロックに書き戻す。一見非効率のようだが、下層のブロックデバイスがそういう風にできているのだから仕方がない。なお、読み出したブロックの全体を更新するということが予め分かっている場合、そもそもブロックを読み出す必要はない。その際には、読み出しを省略してバッファの割り当てだけしてページを作成できる。その状態を頻出させるには、データベース側でもアラインメントを実装する必要があるが、それは設計当初から念頭においていたので問題ない。

今までの実装では、Nページの読み書きを行う際に、N回のシステムコールを発行していた。動作させるだけならそれでもよいのだが、性能を考えるとそれは最適ではない。隣接するブロックの読み書きはまとめて一気に呼び出した方がよい。上述の例だと、ブロック0とブロック1は隣接しているので、0バイトから1023バイトの読み出しをまとめて行ってから、バッファ上の400バイトから699バイトまでの書き換えをして、それを一気に書き出した方が効率的だ。

しかし、キャッシュの寿命管理を考えると、複雑な問題が生じる。ブロック0のページはキャッシュされていないで、ブロック1のページはキャッシュされている場合、ブロック0のページだけ操作すればよい。逆もしかりだ。ではブロック0,1,2を操作するとして、ブロック1のみがキャッシュされている場合、0と2だけを個別に操作すべきか、それともページ1のキャッシュを無視してブロック0,1,2を一気に操作すべきか。どちらが最適かは、ハードウェアの実装に依存する。個別に操作するブロックが物理的に別々の領域(セクタ)に割り当てられている場合、一気に操作してもそれほど利点がないので、個別に操作して転送量を抑える方がよいかもしれない。そうでない場合、一気に操作した方が得だ。

もうちょっと意地悪な例を考えよう。ブロック0,1,2,3,4,5を操作するとして、1,3,4だけがキャッシュされているとする。0,1,2,3は同じセクタにあるが、4,5は別のセクタにあると考えられるとする。こうなると、何が最適なのかもうよく分からない。複雑な条件を考えれば切りがないし、読み込みと書き込みで性能特性は違うし、HDDなのかSSDなのかでも違うし、ストレージの製品やデバイスドライバの実装によっても変わってくる。

純化して考えよう。まず、歯抜けにキャッシュされたページがあるというケースは稀であると想定する。そのようなケースが起っても適切に動作はするが、性能上は最適である必要はないと割り切る。そして、歯抜けでないケースに最適化する。

まず、読み出しの対象となるブロックの先頭から検査を進めて、キャッシュされたページがあればそれを再利用して、実際の入出力の操作対象を狭めていく。キャッシュされていないブロックを発見したら検査を終える。末尾からも同じことが可能だが、それはやらないでおく。バッファのアドレスの計算が多少面倒なのと、先頭がキャッシュされていないのに末尾がキャッシュされている確率は高くないからだ。

キャッシュされていない最初のブロックから読み出し対象の最後のブロックまでは、一気に操作する。一気に操作する対象の区間には、既にキャッシュされているブロックがあるかもしれない。更新済みのダーティなページがある場合、ファイルから読み出したデータよりも優先してページのデータを見る必要がある。また、各ページとそれに対応するブロックの操作はアトミックでなければならないので、操作対象に該当する全てのスロットをロックする必要がある。デッドロックを防ぐためには、該当する全てのスロットをインデックスでソートしてから、昇順にロックする必要がある。アンロックは降順にする必要がある。

キャッシュ内のダーティページを書き込む際にも、隣接したブロックをバッチにまとめて書き込む余地がある。前回までに論じたが、並列性のために、ページキャッシュは複数のスロットで管理している。スロット内のページ数が一定を超えたら、古いページは捨てて、その際に更新済みのものはファイルに書き出すという実装である。今までの実装では、ブロック番号をスロット数で割った値でスロットを割り当てていたが、それだと隣接するブロックは決して同じスロットに割り当てられない。排他制御の都合でキャッシュの操作は必ずスロット単位で行わねばならないため、同じスロットにないブロックはバッチ化できない。なので、ブロック番号を32で割った値を更にスロット数で割った値でスロットを決めるように変更した。それなら、32個の隣接するブロック毎にスロットに割り当てられるので、スロットが異なることを理由にバッチ化が妨げられる確率を抑えつつ、十分な並列性が得られる。

あるページがLRUに該当して捨てられるとする。そのページが読み出されてから一度以上更新されてダーティフラグがついていた場合、ファイルに書き戻さねばならない。その際に、今まではそのページだけを書き込んでから破棄していた。そこを変更して、隣接するページが同じスロットにある場合には結合したバッファを作ってから書き込みを行うようにする。その後、最初にLRUに合致したページは破棄するが、バッチに巻き込まれただけのページは破棄せずにダーティフラグをクリアしたクリーンなページに戻して維持する。こうすると、LRU削除の効率性を損なうすることなく、バッチ書き込みが実現できる。隣接したページを探すには、該当のページのオフセットをページサイズでずらしたキーでハッシュ表を検索すればよい。

以上のことを実装すると、どれくらい性能が向上するかを見てみたい。複数の隣接する領域を読み出す場合に性能向上するので、4000バイトの値を持つレコードを4096バイトにアラインメントして扱い、それを10万個SetしてからGetするというユースケースを再現する。ブロックサイズは512バイトで、ダイレクトI/Oとパディングとキャッシュを有効にする。以下のコマンドになる。

$ ./tkrzw_dbm_perf sequence --path casket.tkh --file pos-para --random_key --random_seed -1 --iter 100000 --size 4000 --align_pow 12 --cache_buckets --block_size 512 --direct_io --padding --pagecache

その結果を、連続読み書きありとなしで比較してみよう。単位はQPS(クエリ毎秒)である。

Set Get
連続読み込みなし 1786 1876
連続読み込みあり 16691 12585

ということで、SetもGetも、あからさまに高速化した。この実験だとレコードは8ブロックからなる。連続読み込みなしだと、1個のレコードを読むのに8回のダイレクトI/Oの呼び出しが発生するが、連続読み込みありだとそれが1回で済む。レコードの書き込みも、8回に分けて書き込まれていたのが、1回か2回で済むようになった。結論として、ブロックサイズが小さい場合、転送量を抑えるよりも呼び出し回数を抑える方が性能に寄与するらしいということがわかった。

マルチスレッドの場合のスループットも測ってみた。上記の実験の投機的読み込みあり設定と同じ条件でスレッド数を2にして動かしたところ、Setが10011、Getが22416だった。4スレッドだと、Setが8470、Getが46057だった。並列化しても書き込みのスループットは上がらないか、むしろ下がる。読み込みのスループットは線形に近い勢いで上がる。これは下層のハードウェアの特性だろう。


話題を変える。ファイル内から可変長レコードを読み出すことを考えよう。レコードのサイズは最初の4バイトにビッグエンディアンな数値として書いてあり、その後にレコードの実データが並べられるものとする。率直な実装では、まず最初の4バイトを読み込んでレコードのサイズを認知してから、それに応じたバッファを確保して、そして4バイト目以降を読み出す。ページキャッシュがある場合、最初の4バイトを読み込んだ時点で、それが属するブロックがキャッシュに乗るため、後続の実データを読み込む処理では実際のファイルアクセスが発生しないようにできる。

しかし、それでもまだ最適ではない。レコードが2つ以上のブロックにまたがる場合、理想的には全てを一気に読み出したいのに、サイズを調べるためだけに最初の1ブロックだけを先に読み出さねばならない。そうすると、ファイルアクセスが2回になってしまう。これを1回にすることはできないか。

レコード全体のデータを一気に読むには、予めサイズがわかっていないといけない。しかし、サイズを知るためにはデータの一部を読み出さねばならない。ジレンマだ。しかし、実際には、間違ってもいいのだ。多めに読んだデータは捨てればいいし、少なめに読んだならまた読み直せばよい。つまり、投機的に読み出す長さを決定するという選択肢がある。

今までの実装では、レコードのアラインメントと48バイトの大きい方を投機的に読み込む長さとしていた。ハッシュデータベースのアラインメントのデフォルトは8バイトなので、デフォルトでは48バイトを投機的に読み込む。レコード毎のヘッダが9バイトなので、キーと値の合計サイズが39バイトまでのレコードは一撃で読み出される。アラインメントを設定していない場合には小さいレコードが多いことを想定してのチューニングである。

アラインメントが設定された場合でも、レコードの典型的なサイズがアラインメントよりも大きい場合には、読み込みが2回になる確率が増すことになる。例えばB+木の場合、アラインメントは1024バイトだが、典型的なページサイズは6000バイトくらいであり、そうするとほぼ確実に2回の読み込みが必要になる。B+木ではファイル内ページキャッシュは使わないことが前提であるため、2回の読み込みは2回のデバイスアクセスを意味する。1回と2回は2倍の差なので、これはなんとかしたい。

典型的なサイズをパラメータとして与えてそれに基づいて投機的な読み込みを行えばいいじゃないかと。min_read_size なるチューニングパラメータをユーザが指定できるようにすればいい。デフォルトは48とアラインメントの大きい方ということにして、ユースケースによって1024とか8192とかを指定すればよい。B+木とダイレクトI/Oの組み合わせで運用する場合、B+木のページ分割の閾値をmin_read_sizeのデフォルトにすればよい。B+木とメモリマップI/Oか通常I/Oの組み合わせの場合、再読み込みのコストは高くないので、むしろ初回の読み込みのコストを下げるべく、デフォルトは48で良い。

以上のことを実装すると、どれくらい性能が向上するかを見てみたい。B+木で、ファイル内キャッシュを指定せずに、4060バイトでページ分割するユースケースを、投機的読み込みありとなしで比較してみる。ブロックサイズは1024バイトで、ダイレクトI/Oとパディングとキャッシュを有効にする。以下のコマンドになる。

$ ./tkrzw_dbm_perf sequence --path casket.tkt --file pos-para --random_seed -1 --random_key --size 100 --max_page_size 4060 --max_cached_pages 1000 --iter 1000000 --cache_buckets --block_size 1024 --direct_io --padding

その結果を、連続読み書きありとなしで比較してみよう。単位はQPS(クエリ毎秒)である。

Set Get
投機的読み込みなし 1882 4231
投機的読み込みあり 2996 7058

ということで、SetもGetも、あからさまに高速化した。ここでも同じ結論だ。ダイレクトI/Oを呼び出す回数が半減したのだから当然だ。ブロックサイズが小さい場合、転送量を抑えるよりも呼び出し回数を抑える方が性能に寄与する。

マルチスレッドの場合のスループットも測ってみた。上記の実験の投機的読み込みあり設定と同じ条件でスレッド数を2にして動かしたところ、Setが4653、Getが14439だった。4スレッドだと、Setが4025、Getが29608だった。これはハッシュデータベースと似た傾向だが、こちらは書き込みのスループットも若干上がるっぽい。読み書きするブロックの位置のばらつきや長さが並列処理性能に関係するとは思うが、具体的な理由はよくわからない。

ファイル内キャッシュの実装をここまで最適化した今なら、B+木と併用しても実は得があるんじゃないかと、ふと思い立った。上述の実験に「--pagecache」とつけて実行するだけなのだから、試してみて損はない。その結果、Setが2965、Getが4913と出た。つまり、ほぼ同じ性能にはなるが、取り立てて得もないということになる。まあ、予想通りと言えば予想通りか。データベース内キャッシュが効かなかったからファイル内キャッシュを引いているわけで、より局所性が低いキャッシュの層を設けても意味はない。やはり、B+木にはファイル内キャッシュは不要だ。


その他、最新バージョンでは、細かい最適化も入れた。バッチ化などの処理でページやレコードの集合をvectorやsetなどに入れたくなるが、そこをぐっとこらえてスタック上のポインタ配列で頑張った。バッファやエラーメッセージなどもstringに入れたくなるが、そこをぐっとこらえてスタック上のchar配列で頑張った。I/Oの最適化をやり切った次に来るのはメモリ確保の最適化なのだ。つまり、newやmallocを呼ぶ回数をいかに減らすか。プロファイルを取ったら意外にコスト上位に来ていたStatusオブジェクトもムーブ機構を活用して最適化した。

I/Oをバッチ化する場合、元々のページのバッファをそのまま利用して入出力を行うわけにはいかない。連続したバッファに詰め直す必要があるからだ。その際にも、ダイレクトI/Oを念頭におくと、バッファのアドレスがブロックサイズの倍数にアラインメントされている必要がある。そのようなバッファを毎回割り当てるのは効率が悪いが、ダイレクトI/Oのコストよりは遥かにマシなので、現状ではそのままにしている。バッチ化しなかった際には、つまりバッチの中に一つしかページがなかった場合には、ページのバッファそのものを使うような分岐を入れている。


まとめ。ファイル内キャッシュの読み書きにおいて、隣接したブロックをファイル内キャッシュでまとめてバッチ処理することによって、ファイル入出力の回数を減らすことができる。これは特に応答の遅いダイレクトI/Oの際に高速化に寄与する。一方、ファイル内キャッシュを使わない場合でも、レコードを読み込みむ際のデータサイズを投機的に決定することで、ファイル入出力の回数を減らすことができる。これは特にB+木とダイレクトI/Oを組み合わせて使う際に高速化に寄与する。実際に性能を測定したところ、ダイレクトI/Oの呼び出し回数に反比例してスループットが上がることが確認できた。

動作が遅いパターンに対策を打って、 「最大xx倍の高速化」と謳うことで、あたかも性能が全般的に上がっているかのような印象を持たせる商法はよくあることだ。もちろん、この記事の書き方はそのパロディだ。しかし、実際のところ、実験のために想定したシナリオはそんなに特殊なものではない。レコードサイズがKB単位のハッシュデータベースを構築することは普通にあるし、B+木データベースではページサイズが KB単位になるのはほぼ確実だ。よって、ダイレクトI/Oを使う規模ならば、今回の高速化は実際の運用に寄与すると言える。

ダイレクトI/Oに関しても、これで全てやり切った感がある。私が思いつく限りの無駄は全て省いた。従来、Tkrzwは実メモリに乗り切る規模での性能に最適化していた。この1ヶ月の努力のおかげで、実メモリよりも遙かに大きく、ファイルシステムのキャッシュすら非効率になる規模のデータベースにおいても、おそらく最善に近い効率で操作ができるようになった。ちゃんとチューニングすれば、毎回のレコード操作でほぼ1回のハードウェアアクセスをするだけになった。もう、これ以上の効率はあり得ないのだ。これで遅いなら、ハードウェアが遅いからだと断言できる。