市販されているハードディスクは大半が7200rpmである。
これは毎分7200回転、つまり毎秒120回転する事を意味しており、ハードディスクのヘッドを目的の場所に合わせるランダムアクセスに1/120秒ほど掛かる見込みがあるとも言える。実際HDDのカタログスペックを見てもヘッドシークは10ms程度掛かると見て間違いない。
ざっくり言うと普通のハードディスクは1秒に120箇所以上に書き込む事はできない。(探せば15000rpmのハードディスクもあるけれど倍速くなるわけでもなさそう）
ログを書くという事
毎秒120箇所を書き換えれないのに1つのトランザクションが120箇所を更新する内容をすべてそのままディスク上のデータに反映させていたら毎秒1トランザクションしか走らない。それではパフォーマンスが致命的に落ちるので、データベースは可能な限りHDDのヘッドシークを減らす方向に進化してきた。それがログである。
データベースの複数の箇所を書き換えたい時に、それぞれの箇所を直接書き換えるのではなく「このキーにこの値を保存する」というような情報(ログ)の羅列を直列に書き出す事で代用する。そうすれば一度に何百箇所を編集するトランザクションであっても1トランザクションあたりヘッドのシークは1回に収まる。ログを書き込んでもディスク上のデータベースは物理的に書き換わらないため、いずれデータベース内のデータそのものも書き換える必要があるが、ページ単位で更新を取りまとめて書きだす事でトランザクション数に対して書き出すページ数も抑える事ができる。そうやってスループットを稼いできたのがトランザクションの歴史である。ログの形にまとめる事で1秒あたりにコミットできるトランザクションの数はトランザクションの大きさにおよそ関わらず秒間100トランザクション程が見えてくる。
ディスクの遅延とトランザクション
HDDの遅延は約10msと書いたが、例えば3GhzのCPUから見ると10msの待機とは30,000,000クロックの待ちを表している。1クロックを仮に1秒のタイムスケールに直すと30,000,000秒とは347日、ほぼ一年に近い待ち時間になる。先にS2PLで述べたようにDurabilityの為にはトランザクションのロック期間の中で永続化を行わなくてはならないが、ロックを10msも保持し続けるのは正気の沙汰ではないので何とかしてロック期間を短くするアルゴリズムはいくつか提案されている。どれも面白いので詳細は後日の記事にする。
グループコミット
ハードディスクのヘッドは、動かすまでは10msかかるが、目的の所にシークした後は100MB/秒ほどの読み書き性能がでる、これをシーケンシャルリード・シーケンシャルライトと言う。ログを書く場合、次にログを書くべき場所は追記故に確定しておりシーケンシャルライト性能を存分に活かしきるためには複数のトランザクションのログを一度に書き出せるのが好ましい。
しかしながら、各トランザクションはいつ始まっていつ終わるのか予めはわからない。
そこで発明されたのがグループコミットである。IO命令の発行数を最小化するため、ログを書く専用のスレッド（ロガー）を用意して、トランザクションを行うスレッドはみんなそこにログの書き出しを依頼(エンキュー)し、ロガーが複数の依頼を一度のディスク書き込みで一括で完了させる。そして各トランザクションはログの書き込みが完了するまで待機する。という方法でスループットを改善する。ロガーは
- 書かれたログ量が一定の閾値を超えた場合
- 前回の書き出しから一定の時間が経過した場合
のどちらかの条件が満たされた場合に、エンキューされたログをまとめてHDDに書き出してトランザクションを発行したスレッドに完了を報告する。これらの閾値や時間に関してはシステムの要件によって最適値が変わる。
この機能が最初に搭載された商用DBは1976年のIBMのIMS FastPathだと言われている。だが当時に論文の形とししては登場せず、1985年にVarieties of Concurrency Control in IMS/VS Fast Path.の中で紹介された。これとは独立してGroup commit timers and high volume transaction systemsが1984年に発明され登場した。この当時のDBは技術の核心は現代ほどおおっぴらに公開されない傾向があったと言えるかも知れない。
このグループコミットの面白い所は、個々のトランザクションがそれぞれでロックを取ってHDDのヘッドを握りしめて丁寧にS2PLした場合と完全に状況が一致することである。つまり並行性にも永続性にも機能レベルでは何の悪影響も出さずに性能だけを向上させることに成功している。
このアルゴリズムによってトランザクションのスループットはチューニング次第で1000トランザクション/秒を超えることも可能になった。
さらにこれを改良するアルゴリズムも提案されているが、そのうち1つは明日の記事にする。