データベースの歴史は古い。
データベースの黎明期ではメモリの価格は今とは桁違いで、1バイトあたり1円を切るかとかそういうレベルの世界だった。1バイトが1円ということは1MBのメモリが100万円以上するという事である。
また、単純にメモリのサイズも小さく、ハイエンドのメモリフレームでRAMを8MB積んでいるとかそんな世界であった。ちょっと大きな事をやろうとすると8MBを溢れる事は当然想定しなくてはならない。
ページ
HDDのランダムIOは非常に遅い。なので1バイト単位でデータを書き換えるよりはメモリで可能な限り書き換えをバッファして、ある程度の大きさでまとめて書き込みを行う事で高速化できる。
PostgreSQLではデータベースの内容をページという(デフォルトでは)8KByteの大きさに切り分けて管理している。
1ページの中にテーブルの中の数行分のデータを入れる事でRDBMSはリレーションを保存している。
HDDの中にDB全体がページの配列の形で保存され、そのページを適宜メモリに読み出してトランザクションを行うのが伝統的なDBのアーキテクチャである。
メモリはDBのディスクのキャッシュであり、キャッシュの中でもライトバック式のキャッシュである。
つまり可能な限りディスクとのIOを引き起こさずにメモリ内で更新を受け止め、他のページを参照する際に容量が足りなくなったら更新をディスクに書き戻して手放す。
メモリ内に置いているディスクページの写しを「バッファ」や「キャッシュ」などと呼ぶ事が多い。
1件以上の書き込みを一括にまとめるという意味でのバッファ（もっと言うとWrite Combining Buffer)と、ディスクからの読み出しを高速化するキャッシュの両方の目的を兼ねている事が多い。
ページの書き込みはAtomicに行われるとは限らず、ページの更新途中で電源が抜かれる可能性もあるのでそれに合わせた障害リカバリをする必要がある。
ログ
これまでの記事では意図的に「ディスクに書く」「ログを書く」などの文脈でも具体的にどのようなフォーマットのログを書くかに関しては言及しなかった。
それは、ログのフォーマット1つ取ってもそれなりにややこしい問題があるからである。
物理ログと論理ログと物理論理ログ
ログにはUndo情報とRedo情報のどちらか、もしくは両方が入っている。どういう場合にどういう使い分けがされるかは後日の記事により詳細を説明する。
Undo情報は「その操作を取り消す為に必要な操作」が入っており、Redo情報には「その操作を行う為に必要な操作」が入っている。
そもそも個々のページの中身は書き換えの途中でマシンの電源断で消失している可能性すらあるので、ここで非常に大事になってくるのが操作が冪等であるという事である。
冪等とは何度適用しても同じ結果になるという性質を表している。数学的にかっこ良く書くなら f(f(x)) = f(x) である。例えば
x = 10; // xに10を代入する
この操作は何度実行してもxに10という数値が代入されるので冪等だが
// std::vector<int> y; とする
y.push_back(10); // 配列yの末尾に新たに10を繋げる
この操作は実行するほどに配列yが長くなっていき冪等ではない。
冪等な操作でログを構成することで、ページの一部が中途半端に更新された状態からのリカバリであっても完全なページを復旧できる。
物理ログ
物理ログとはまさにその目的を果たすフォーマットのログであり、愚直にはUndo情報として「更新操作前のページ全体」、Redo情報として「更新操作語のページ全体」、そして「対象となるページID」を保存する事で目的を満たせる。
ページがどのような状態になっていてもまるっと全体を上書きすればそれは冪等な操作である、ページが論理レベルでどういう構造をなしていようと関係なくリカバリできる。
だが、単純な問題としてログ1件あたりページ全体の情報を含むのはログの巨大化を招く。Undo/Redo両方を持ったら1ページ8KBとして16KBもの大きさのログになる。
全体ではなくて一部のバイナリデータとオフセットのペアで持てばいくらか小さくできるが、ページの中の特定の場所に値を挿入する場合など、論理的には小さな更新だが物理的には変更範囲がページ全体に行き届く場合もあり結局ログデータが肥大化する事は避けられない。
論理ログ
データベースにどのような操作を行ったか、という論理的な情報を保存するフォーマットである。例えば「Usersテーブルにid=5 かつ name='kumagi'というエントリを挿入する」という形をしている。このログは簡潔で目的を適切に表現していてコンパクトである一方で冪等でないという致命的な欠点がある。
そのためこの操作を何度も繰り返すとUsersテーブルがどんどん膨れ上がっていく事になる。
単純に冪等でないだけであれば、いくつかの工夫（ユニークなIDを入れるとか）で対応できる。しかし、ページのSplitやMergeやインデックスの更新が絡んだりなど、1つの更新が複数のページに跨る動作となった場合に全てのページが一斉に永続化されていないと一貫性が破られる。複数のページを論理的に一斉に永続化させる方法はシャドーページング（詳細は後日の記事に）などがあるがオーバーヘッドが大きいのであまり実用的とは呼べない。
物理論理ログ
Physiological Logと呼ばれる物で、物理ログと論理ログの両方の特性を併せ持ったログのフォーマットである。
物理的な情報としてページの情報を持ち、論理的な情報としてページに対する更新動作をログする。例えば1つの論理操作が3つのページに影響を与えた場合、論理ログであれば1エントリのログだが、物理論理ログではそれぞれのページごとに1エントリ、合計で3エントリのログが生成される。これであれば3のページそれぞれでディスクに書き戻さずに電源が落ちても、3ページのそれぞれに対してUndoもしくはRedoが可能になる。ページ内に対しては論理的ログであり、個々のページごとにヒモ付けされているという意味で物理ログなので、物理論理ログと呼ばれる。
なお、今後の記事においては特に但し書きをしない限り物理論理ログを指していると考えて欲しい。
明日はバッファ管理とWALの話について書く。