wal.re

= 永続化


一般に、コンピュータ上のプログラムは揮発性のメインメモリ上でプロセスとして動作しますが、
データベースの寿命はプロセスや、それが動いているコンピュータのハードウェアよりも長かったりします。
永続化は、そのような制約を越えてデータベースを永続的に保持するための処理を意味し、
その第一歩はデータベースやその差分をディスクに保存することです。
そのための要素技術が、Write-ahead Logging や Checkpointing です。



== そもそも Log って何でしょうか？

Log はトランザクションによるデータの変更後のもしくは変更前の差分データのことです。
変更後のデータを Redo log、変更前のデータを Undo log といいます。
より厳密にいえば、トランザクション実行前の状態から実行後の状態を作れるだけの情報を持っているものが
Redo log、実行後の状態から実行前の状態を作れるだけの情報を持っているものが Undo log です。
ごく稀に、Read log、すなわちトランザクションが何を読んだかという Log
について考えることがありますが、効率の面からあまり現実的ではありません。
通常、Log はデータベース本体のデータとは別に記録されます。

どのレベルの表現で Log を扱うかという設計の選択肢があり、
Logical logging と Physical logging に大別されます。
Logical logging とは、SQL 文や、ストアドプロシージャの ID とその入力など、抽象度が高い表現を意味します。
Physical logging とは、Record や Record よりももう少し大きな物理構造である Page/block などの表現を意味します。
Log の容量を小さく保つことよりも性能のことを考えると、Record 単位の Physical logging を
用いたくなることが多いのではないかと私は思います。


== 何のために Log はあるの？

Redo log はその名の通り Redo するための Log、トランザクションがあったことにするためのものです。
Undo log は Undo するための Log、トランザクションをなかったことにするためのものです。
Logging は ACID 特性の、A (Atomicity) と D (Durability) を実現するための仕組みです。
我々は Crash が発生し得る世界で、トランザクションを Atomic に実行し、永続化したいです。
しかし、Crash が発生したときは、データベース本体のファイルが中途半端な状態になってしまうことは避けられません。
というのも Atomic にしたい複数操作が実際には Atomic に永続化できないからです。
Log があれば、Crash 直後のデータベース本体ファイルが中途半端な状態から、
全てのトランザクションについて、あった/なかったのどちらかの状態に回復できます。
もちろん、前提として、とある性質を満たす必要があり、詳細は Crash recovery の節で述べます。
Commit しましたよとクライアントに返事をしたトランザクションは必ず Committed 状態でなければならず、
後からそれが覆ったりしてはいけません。


== Write-ahead Logging って何？

トランザクションを後からあったことにする/なかったことに出来るなら
どんな方法を採用しても良いのですが、
「先行」して書く方法が 1991 年の ARIES 論文が発表された前後から主流となっています。
(NVRAM の台頭で変わるかも知れません……)
この「先行」方式を Write-ahead Logging (WAL、ワル) と呼びます。
先に Log を書いておけば、いつ Crash が発生したとしても、
データベース本体の中途半端な状態から回復するために必要な Log が
永続化されている状態を保つことが可能です。

この方式では WAL ファイルに追記していけば良いことから、
シーケンシャルアクセスがランダムアクセスよりも高速であり、永続化にも追加の操作(@<tt>{fsync} 相当)を必要とする
HDD とは相性が良かったのです。
並列に WAL を書く方法も最近は(少なくとも研究レベルでは)当たり前になりました。
(並列じゃない WAL をシングル WAL、並列のものを パラレル WAL と区別して呼ぶことにします。)
似たような方法として、ファイルシステムのジャーナルも WAL の考え方を採用しています。
例えば Linux OS で広く使われている ext4 ファイルシステムは、
メタデータ操作を Atomic 実行の対象として、Crash しても @<tt>{fsck} (という名の全メタデータチェックツール)
の実行が不要な(Crash recovery 相当のジャーナルリプレイ操作のみ必要)仕組みを採用しています。



== Redo/undo log は両方必要？

データベース本体ファイルへの変更の反映についての制約を一番緩いものにしたければ両方必要ですが、
必要な制約を守れば片方だけでも事足ります。
あるトランザクションの時系列による状態の変化に注目して考えてみましょう。

 * (1) トランザクション開始から Commit/abort 命令発行直前まで
 * (2) Commit/abort 処理の実行中
 * (3) Commit/abort 処理完了後

ここでは、話を簡単にするため Redo log、Undo log、Commit/abort log しかないものとしましょう。
Commit/abort log は Log の中で最後に書きます。
これは、Commit log が永続化されていれば、そのトランザクションの全ての Log は永続化されている
という性質を満たすためです。
Commit log が永続化されていないトランザクションは Abort 扱い(なかったこと)になります。
ひとつひとつの Log の適用 (Redo もしくは Undo 操作のこと)は Atomic に実行できるものとします@<fn>{footnote_double_write}。
また、同じ Log を複数回適用しても結果は変わらないものとします(べき等性)。
それぞれの Log を適用する順序には制約があることには意識しておいてください。
同一の Record に対する Redo log 適用の順序は Log を書いた順@<fn>{footnote_log_apply_order}、
Undo log 適用の順序は Log を書いた逆順となります@<fn>{footnote_compensation_log}。

//footnote[footnote_double_write][実際は Atomic に操作できなかったりするので、Double write するなどの工夫が必要です。]
//footnote[footnote_log_apply_order][厳密には Serialization order の順となりますが、S2PL プロトコルを前提とすれば Log を書いた順です。パラレル WAL 方式では何らかの方法で順序を担保する必要があります。]
//footnote[footnote_compensation_log][Undo log の適用そのものをそのままべき等にすることは難しいので、Undo log の適応に際してCompensation log なる Log を出力し、Undo 処理を Redo log として記録します。Undo 実行中の Crash に対しては、Redo phase に Compensation log が適用されることで Undo 途中の状態が再現され、Undo phase でまだ実施していない Undo の続きを実行します。これにより、対象を確実に 1 回だけ Undo することが可能になります。]


=== Redo log しか書かない (Undo log がない) システム

Undo log がないということは Undo できないので、一部でもデータベース本体に変更を反映したトランザクションは、
必ずあったことにしないとけません。
ということは、少なくとも (1) の間にデータべース本体のファイルに変更を反映できないという制約が発生します。
さらに、Commit が確定する(当該トランザクションの Log が全て永続化する、
かつ、それが依存している全てのトランザクションの Commit が完了している)まで、
データベース本体に変更を反映できないという制約も発生します。
つまり、(3) になって始めてデータベース本体のファイルに変更を反映しても良いことになります。
(あくまでディスク上のファイルについての話であって、メインメモリ上では通常もっと前に反映されています。)
すなわち、Commit log の永続化が終わってからデータベース本体に反映を開始することになります。


=== Undo log しか書かない (Redo log がない) システム

Redo log がないということは Redo できないので、データベース本体に変更を反映するまで Commit したことにできません。
Undo はできるので、(1) の間でも Undo log が永続化済みの操作は、どんどんデータベース本体に反映して問題ありません。
(2) において、Commit が確定するためには、当該トランザクションの Log が全て永続化する、かつ、データベース本体への反映が永続化も含めて終わっている、かつ、依存しているトランザクションが Commit 完了している必要があります。
つまり、Commit log はデータベース本体の永続化が完了してから書くことになります。
(3) においてそのトランザクションについてやるべきことはありません。


=== Redo log と Undo log の両方を書くシステム

片方しかない場合に比べて制約が大幅に減ります。
必要な制約は、Redo/undo log を永続化してから対応する操作をデータベース本体ファイルに反映開始することのみです。
Commit に必要な条件は、Commit log まで永続化が完了する、かつ、依存しているトランザクションが Commit 完了していることです。
途中までデータベース本体に反映したところで Crash しても、Undo log は永続化されているので
トランザクションをなかったことにできますし、
Commit log が永続化していれば Redo log は全て永続化しているのでトランザクションをあったことにできます。


図にするとより分かりやすいと思いますが、自分で書いてみてください(えっ)。



== Crash recovery

Crash が発生した直後のデータベース本体ファイルは中途半端な状態になっています。
これを Log を使って各トランザクションがあった/なかったのどちらかに確定させ、
データベースの永続データを一貫性のある状態に修復します。
まず、Log を先頭からなめて、トランザクション毎にあった/なかったのどちらにするか決定します。
あるトランザクションを「あった」ことにする条件は、

 1. トランザクションの全ての Log が永続化済みである(Commit log が記録されている)
 2. トランザクションが依存していた全てのトランザクションが Commit 扱いとなっている

です。

(2) をきちんと考え始めると、込み入った話になります。トランザクションの「依存」とはなにかということです。
トランザクション B が トランザクション A に依存する関係は、
A が書いた Record を B が読んだときに成立します@<fn>{footnote_reads_from}。
A が Abort 扱いになるのであれば、A の書いた Record データはなかったことになるので、
それを読んでしまった B もまた Commit できないということです。
このケースで、B を先に Commit してしまうと、A が Abort してはいけませんが、
実際には Crash によって A が Abort する可能性を排除できないので、破綻します。
破綻を避けるには A を Commit してから B を Commit する必要があります。
この制約を Recoverability といいます。

//footnote[footnote_reads_from][Reads-from 関係ともいいます。B reads from A とか B reads x from A といったりします。]

Recoverability よりも強い制約として Strong recoverability があり、
Serialization order の順に Commit することを意味します。
Strong recoverability を DBMS が満たせば (1) が満たされたとき (2) も自動的に満たされるようになるので、
ここでは Strong recoverability を前提として (1) のみを気にすることにします。これなら簡単ですね。
詳細は@<secref>{memo|sec-recoverability}に書いておきました。

Commit log を永続化した後に Commit 成否はユーザ/アプリケーションに通知されているはずですから、
Commit 成功したと通知されているトランザクションは全て Commit log が永続化されているはずです。
そのようなトランザクションは (1) を満たすわけなので、必ずあったことになります。

トランザクションをあった/なかったのどちらにするかを決定した後は、
あったことにするトランザクションを Redo します(Redo log がないシステムでは不要です)。
最後に、なかったことにするトランザクションを Undo します(Undo log がないシステムでは不要です)。
Log 適用の順番には気をつける必要があります。
シングル WAL であれば、最も単純な方法として、Log の書かれた順番を守って適用すれば問題ありません。
必要とされる性質は、DBMS が並行実行制御で決定したトランザクションの順序(一般に全順序ではなく半順序です)
に矛盾しないように適用順序を制御します。
その制御のために Log に必要な情報を含める必要があります。
どんな情報が必要かは並行実行制御プロトコルや WAL 方式に依存します。
半順序関係を満たせば良いということは、理論上は並列に Log 適用することも可能です。



== Checkpointing

Log はいつまで残しておけば良いでしょうか？
それは、Log に対応するトランザクションが完了していて、
当該トランザクションの全ての Log の操作がデータベース本体ファイルに反映され終わるまでです。
それらの条件が満たされた Log はもう不要なので、消すことができます。
メインメモリが大量にあったり、そもそもインメモリデータベースなどでは、
データベース本体ファイルへの変更の反映をずっとずっと先延ばしにすることが可能です。
先延ばしし続けると Crash recovery 時に適用しなければならない Log が増え、
Crash recovery にかかる時間が長くなってしまうだけでなく、
いつまでも Log を消せないということになります。
それを防ぐために行う操作が Checkpointing です。
Checkpointing とは、先延ばししていたデータベース本体ファイルへの反映を実行して、Log を消す作業です。
プロトタイプを作る場合は実装が後回しになる機能だと思いますが、
長時間 DBMS を動かし続けるためにはなくてはならない機能です。

素朴には、データベースの全データを書き出せば Checkpointing できますが、
書き出しの途中でトランザクションが実行された場合、書き出されたデータは
一貫性のある Snapshot ではなく、中途半端なデータベース状態です。
詳細はここでは述べませんが、この場合はこれを Log と組み合わせて一貫性のある Snapshot を作り出す必要があります。
最近は、一貫性のある差分をうまく非同期的に出力する方法も模索されています。
また、Log を使って古い Snapshot から新しい Snapshot を生成する方法もあります。
新しい Snapshot があれば古い Log は消せますから、Checkpoinitng の目的を達成できるというわけです。
並列 Logging およびデータベースが分割 (Partitioned) されている前提であれば、
Map-reduce のような処理をして、古い Snapshot から新しい Snapshot を作ることになります。
@<secref>{next-step|sec-direction-for-durability}にもう少し詳しく書いておきました。

Checkointing の良さの指標とは、差分を取り出すためのオーバーヘッドが小さいことと、
新しい Snapshot を作るためのコストや時間が小さいことです。
後者は、滞留する Log の量が許容量を越えなければ実用的だと言えます。
追い付けない場合はシステム運用が破綻するので、オンライン処理にバックプレッシャーをかけて遅くする必要さえあり得ます。
Checkpointing の手法を考えたり、設計したりする場合は、これらの指標を意識してください。