🖖

データベースのリカバリプロトコル: ARIES

2024/02/03に公開

Database

データベースシステムがクラッシュしたとき、我々は DB を復旧しようとします。では DB を復旧するとは具体的に何を意味しているのでしょうか？答えは、次の2つです。

DB のスナップショットをログ (WAL) の状態に合わせること。
クラッシュ時に走っていたトランザクションの変更をロールバックすること。

本記事ではスナップショットとは、ログを上から順に実行して得られたオブジェクトを指すこととします。インメモリのデータベースではスナップショットはメモリ上にすべて展開されており、ディスクベースのデータベースでは、スナップショットの一部がメモリ上にロードされています。本記事の内容は、ディスクベースのデータベースを前提とします。

1.はクラッシュ時に（ディスクにある）スナップショットが（ディスクにある）ログを実行した結果と異なる可能性があり、それを一致させることを意味します。1.を実行したあと、WAL とスナップショットが示す DB の状態が一致します。その後、2.でトランザクションをロールバックします。ロールバック時には、WAL にロールバックしたことを示す Compensation Log Record (CLR) を追記し、スナップショットを巻き戻すので、最終的にスナップショットとログの状態は揃っています。

では、一番簡単な復旧方法は何でしょうか？答えは、ログを時系列順に実行して DB のスナップショットを1から作り上げ、ディスクにあるスナップショットを上書きし、最後に COMMIT と書かれていないトランザクションの変更分をスナップショットから巻き戻せば良いでしょう。先程述べたように WAL とスナップショットが一致した状態を維持するために CLR を WAL に追記する必要が有ります。

この復旧方法の問題点は何でしょうか？答えは、復旧にとてつもない時間がかかることです。ログを時系列順に再実行するとは、データベースのすべてのログを走破することになります。また UNCOMMITTED なトランザクションを探すのも、すべてのログを走破することになります。これでは、復旧している間データベースに対してクエリを投げられず、可用性という観点でよろしくありません。

ではどうやって復旧時間を短くできるでしょうか？一番簡単な答えは、定期的にある時点でのスナップショットをとりディスクに書き出すことでしょう。ある時点でのスナップショットを取ってさえいれば、そのスナップショットに対応したログから再実行すれば良いので見るべきログの数が減り、復旧の時間を減らせます。しかし注意しなければならないのは、すべてのトランザクションが COMMIT するのを待ってからスナップショットを取らない限り見るべきログの数は変わらないということです。もし書き出すスナップショット内に UNCOMMITTED な変更が含まれていたらなら、その UNCOMMITTED なトランザクションを見つけ出すためにはすべてのログを走破する必要が有ります。

ここで問題を一旦整理しておきましょう。

[問題]
DB を復旧するにはログを走破して

WAL とスナップショットの実態を一致させる。
UNCOMMITTED なトランザクションを見つけ出し、その変更を Undo する。

この2つを行う必要があるが、ログの走破は時間がかかる。

[解決法]
定期的にスナップショットを取る。スナップショットのとり方には 2 種類ある。
[A] 現在動いているすべてのトランザクションが終了するのを待ってからスナップショットを取る。
[B] トランザクションをまたずにUNCOMMITTED なデータを含んだ状態でスナップショットを取る。

[A] を選択した場合、1., 2. ともに見なければいけないログが減るが、すべてのトランザクションが終了するのを待たないといけない。
[B] を選択した場合、1. で見なければいけないログは減るが、2. では依然としてすべてのログを走破しなければならない。

この問題にデータベースはどのようにアプローチしているのでしょうか？結論から言いますと、[B] を選択しつつ、走破しなければいけないログを減らすことに成功しています。以下にその方法を書きます。

まずディスクベースのデータベースで、クエリがスナップショットへの読み書きをどのように行われているのか軽く説明します。ディスクベースのデータベースとは、スナップショットがすべてメモリ上に乗らないという仮定のもと作られたデータベースです。そのため、スナップショットの一部をメモリに乗せるために Buffer Pool というコンポーネントが存在します。Buffer Pool は、固定サイズ（4KB とか）のページを決められた数だけメモリ上にもちます。Buffer Pool はディスク IO を軽減するキャッシュの役割と、DB がメモリを使いすぎて OS に OOM-killed されるのを防ぐ役割をもっています。では実際に Buffer Pool がどのように使われるのか見てみましょう。クエリがテーブル T の行 R を Read するとします。まず Buffer Pool に T の R が書かれたページが存在するか確認し、なければ T のファイルから R が書かれているページを Buffer Pool の1つのフレームにコピーして、アクセスします。Write するときも同様です。ただし、同時に複数のトランザクションが Buffer Pool の同一ページに変更を加えるのを防ぐため、フレームのロックを取り、WAL を書いて、ページに変更を加え、フレームに DIRTY マークをつけます。このフレームのロックはトランザクションが COMMIT するまで保持しておくこととします。Buffer Pool にページをロードしたいのに、すべてのフレームにすでにページがロードされている場合は、どれかのページを退避する必要が有ります。ページが DIRTY でなければそのまま新しいページで上書きすればよいのですが、ページが DIRTY な場合、まずそのページに変更を加えたログをすべてディスクに flush し、次にそのページをディスクに書き戻します。そして、空いたフレームに新たなページをロードします。注目すべき点は、DIRTY なページをディスクに書き戻すところです。これは、いわゆるキャッシュの Write-back の操作で、ディスクにあるスナップショットの一部分を最新状態に更新していることにもなります。各ページは、ディスクに書かれるときに UNCOMMITTED なデータを含むことが有ります。

では、具体的にディスクベースのデータベースシステムではどのように 1. と 2. を実行しているのでしょうか？まず 1. について考えてみます。ある時点でクラッシュしたとき、ディスク上のスナップショットと WAL はどのような関係があるでしょうか？先程ページの Eviction のところで述べたように、ページがディスクに書き戻される前に、そのページに変更を加えたすべてのログは永続化されています。そのため、ログがスナップショットを先行することはあってもスナップショットがログを先行することはありません。つまりディスクにある各ページについて、そのページに変更を加えた最後の操作のログは必ず永続化されています。 WAL とスナップショットの状態を一致させるには、各ページについて、そのページに変更を加えた最後のログから最新のログまで見て、そのページに関わる操作を再実行してやればよいです。この操作はそれぞれのページで独立しているので並列に実行できます。では 2. はどうでしょう？依然としてログをすべて走破して COMMIT されていないトランザクションを割り出し、そのトランザクションの操作を巻き戻す必要が有ります。上で述べたようにトランザクションはページに書き込む際にフレームのロックを取り COMMIT するまでロックを放さないと仮定したため、ログの中で2つ以上の UNCOMMITTED なトランザクションが同一のページに変更を加えている可能性はありません。そのため、ログを巻き戻す操作は各トランザクション独立しており、ページ同様並列に実行できます。

これが一番簡単なデータベースシステムの復旧方法です。ですが見てわかるとおり、ディスクベースなデータベースシステムもこの方法だと大量のログを走破する必要が有り、ログ走破の問題解決できていません。

まず 1. のステップは、すべてのページに対してそのページを最後に変更したログから最新のログを見る必要が有ります。これは全く変更が加えられていないページに対してもそのページが作られた一番最初のログから最新のログまでを見て、そのページに変更が加えられていないか確認する必要が有ることを意味します。例えば、1000年前に作ってそれ以降一回も触っていないページがデータベースに紛れ込んでいた場合、1000年前のログからそのページに対してなにか変更が起こってないか遡る必要が有ります。2. に関しても すべてのトランザクション に関して、データベースが誕生した一番最初のログから最新のログを確認し、それが COMMIT されたか確認する必要が有ります。

ではどうすれば大量のログを見なくても良いでしょうか？我々が今知りたいことは、ディスク上のスナップショットのうち、どのページはすでに最新版をもっているかです。例えば 1000年前に作られたページでもそれ以降変更は全くなく最新版を持っているということがわかれば、そのページに対して復旧作業を一切行わなくて良いことになります。これはどのように達成すればよいでしょうか？ Buffer Pool は、DIRTY なページが全てわかっています。なぜなら Buffer Pool に無いページは DIRTY ではないからです。つまり Buffer Pool の中で DIRTY であるページ以外のすべてのページについてはディスクにあるのが最新版です。DIRTY なページの ID をすべてログに書いてみてはどうでしょうか？DB 復旧作業のとき、まずこのログを見ます。このログから最新のログまで実行していけば、最新のログまでの間に DIRTY になったすべてのページを判明させることができます。DIRTY なページが判明するということは、どのページを復旧させればよいかわかるということです。復旧対象のページに対して、そのページを最後に変更したログから最新のログを見れば、それらのページを復旧することができます。

次に 2. についてはどうでしょうか？我々が今知りたいことは、WAL内のすべてのトランザクションのうち、どのトランザクションが UNCOMMITED かです。ではある時点での UNCOMITTED なトランザクションをログに書き出してみたらどうでしょうか？そこから最新のログまで実行していけば、最新のログの状態で UNCOMMITED なトランザクションは容易にわかります。それらのトランザクションによる変更を巻き戻す作業をしていきます。巻き戻す際に、各ページに巻き戻し対象の変更が永続化されているのかを確認する必要が有ります。それは各ページを最後に変更した操作のログを見てわかります。

これら2つの操作をまとめて行うことを Checkpoint といいます。DB 復旧の際は、この Checkpoint がかかれたログを見て、そこから最新のログまでを読むことで、復旧対象のページとトランザクションを割り出します。

以上をまとめるとDBの復旧は以下のように行えることがわかります。

DIRTY Page ID がかかれたログを探して、そこからログを再実行して、最新のログまでの間に DIRTY になるすべてのページを判明させる。
UNCOMMITTED Transaction が書かれたログを探して、そこから最新のログのときに Uncommitted なすべてのトランザクションを判明させる。
各 DIRTY Page ID に対して、ディスクから実際のページを取り出して、そのページが最後に変更されたログ（より正しくは、DIRTY Page ID に紐付けられた、一番最初に DIRTY にしたログ）から最新のログまでの間にあるログのうち、そのページにかかわるログを実行する。これにより、ディスクにあるすべてのページが WAL の状態と一致する。各ページはそれぞれ独立に復旧できる。
各 UNCOMMITTED なトランザクションに対して、そのログを割り出し、ディスクから実際のページを取り出して、その変更がページに変更されていれば Undo する。各トランザクションはそれぞれ独立に復旧できる。

これは ARIES というプロトコルに匹敵します。とくに 1, 2 は Analysis と呼ばれ、3 は Redo, 4 は Undo と呼ばれます。

以上は、データベースシステムのログをリプレイするためのアルゴリズムである ARIES がなぜうまくいくのかの説明を異なる角度で行うことを試みました。ARIES ついてより詳しく知りたい方は以下の参考文献をあたってください。原著論文を読まなくても下2つの文献で大方理解はできると思います。

Discussion