データマネージャ

このステップで、クエリマネージャはクエリを実行するので、テーブルとインデックスからデータを取得する必要があります。そこでデータマネージャに対してデータを取得するよう要求するのですが、ここで次の2つの問題が発生します。

• リレーショナルデータベースはトランザクションモデルを使用しています。この場合、「いつでも・どんなデータも取得できる」というふうにはいきません。どこか別の場所で、ここに格納されているデータを同時に使用したり更新したりしている可能性があるからです。
• データの取得は、データベース内で実行する処理の中で最も時間のかかるもの です。従ってデータマネージャはそれを見越して、メモリバッファにデータを取得しておき、それを保持しなければなりません。

このセクションでは、リレーショナルデータベースがこの2つの問題にどう対処しているかを説明します。なお、データマネージャがデータを取得する方法については、ここでは触れません。さほど重要なことでもないからです（それに、本稿は既にかなり長くなっていますし）。

キャッシュマネージャ

上述の通り、データベースのボトルネックはハードディスクとの間の入出力（I/O）です。そこでパフォーマンスを向上させるために、最近のデータベースではキャッシュマネージャが導入されています。

クエリを実行しているプログラムは、ファイルシステムから直接データを取得するのではなく、キャッシュマネージャに対してデータを要求します。キャッシュマネージャには、インメモリのキャッシュが備えられていて、これを バッファプール と言います。 メモリからデータを取得すると、データベースの処理速度は格段に向上します。 しかし複数の処理間で重要度の順位付けをするのは非常に難しいことです。重要度はそのときに処理しなければならない処理によって左右されるからです。例えば以下のようなことを判断しなければなりません。

• シーケンシャルアクセス（例：フルスキャン）かランダムアクセスか（例：ID列によるアクセス）
• 読み取りか書き込みか

一方データベースに利用するのは、以下のタイプのディスクです。

• 7200/10000/15000 RPMのハードディスクドライブ（HDD）
• SSD
• RAID 1/5/…

ざっと言えば、 メモリの処理速度はHDDの100～10万倍は速い です。

このことが、さらに新たな問題につながっています（データベースに問題は付き物ですが）。キャッシュマネージャは、クエリを実行しているプログラムが使用する 前に 、メモリにデータを読み込んでおく必要があります。そうしないと、クエリマネージャは処理の遅いHDDからデータが届くのを待たなければならなくなります。

プリフェッチ

この問題はプリフェッチと呼ばれるものです。クエリを実行するプログラムは、必要なデータを認識しています。クエリ全体の流れを把握しており、さらに統計のおかげでディスク上のデータについての知識があるからです。以下のような流れになります。

• クエリを実行するプログラムは、先頭にあるデータの一団を処理する
• 続いてキャッシュマネージャに、2番目のデータの一団をあらかじめロードしておくように要求する
• 2番目のデータの一団の処理を開始する
• キャッシュマネージャに対して、3番目のデータの一団をあらかじめロードしておくことと、先頭のデータの一団をキャッシュから消去することを要求する

キャッシュマネージャは一連のデータを全てバッファプールに格納します。データがまだ必要かどうかを確認するために、キャッシュマネージャは一度読み込んだデータに対して、キャッシュされたデータについての別の情報（ ラッチ ）を付加します。

しかし時として、クエリを実行するプログラムが必要なデータを認識していない場合があります。さらに一部のデータベースシステムは、この機能を備えていません。こんな場合は、投機的プリフェッチ（例えば、クエリを実行するプログラムが値「1, 3, 5」を要求してきた時、近い将来「7,9,11」も要求されるだろう、と推測します）またはシーケンシャルプリフェッチ（この場合、キャッシュマネージャはディスク上で、要求されたデータに隣接した位置にあるデータを読み込みます）を実行します。

プリフェッチの効果を監視するために、最近のデータベースは バッファ/キャッシュヒット率 という尺度を使います。ヒット率とは、ディスクアクセスをしない状態で、要求されたデータのうちどれだけがバッファまたはキャッシュに含まれているかを表す数字です。

注： キャッシュヒット率が悪いのは、必ずしもキャッシュが不調だからとは限りません。詳細は、 Oracleドキュメント を参照してください。

ただし、バッファのメモリ容量はごく 限られています 。従って、新しいデータを読み込むには、バッファ内のデータの一部を消去しなければなりません。ディスクとネットワークI/Oの観点から見ると、キャッシュの読み込みと消去は負荷の高い処理です。たびたび実行するクエリがある場合、それを実行するたびにデータを読み込み、また消去するのは効率が良くありません。この問題に対処するため、最近のデータベースはバッファ置換戦略を採用しています。

バッファ置換戦略

最近のデータベースシステム（少なくともSQL Server、MySQL、 Oracle、DB2は該当します）は、LRUアルゴリズムを採用しています。

LRU

LRU とは、「 L east R ecently U sed」の略、つまり最後に使用してから最も長い時間がたったものから削除するということです。このアルゴリズムは、最近使用したデータは再度使われる確率が高いからキャッシュ内に留めておこう、という発想に基づいています。

この概念を視覚化したのが以下の図です。

この図を分かりやすく説明するため、バッファ内のデータがラッチでロックされることはないと仮定しましょう（そのため取り除くことも可能です）。この簡単な例では、バッファに3つの要素を格納できます。

• 1：キャッシュマネージャはデータ1を使う際、空のバッファの中へデータを置きます。
• 2：キャッシュマネージャはデータ4を使う際、一部がすでにロードされているバッファの中へデータを置きます。
• 3：キャッシュマネージャはデータ3を使う際、一部がすでにロードされているバッファの中へデータを置きます。
• 4：キャッシュマネージャがデータ9を使おうとすると、バッファがいっぱいになっています。そのため、 最も前に使用されたデータ1が取り除かれ、 データ9がバッファに追加されます。
• 5：キャッシュマネージャがデータ4を使うと、 既にバッファ内に存在しているデータ4が、再び直近で使用されたデータとなります。
• 6：キャッシュマネージャがデータ1を使おうとすると、バッファがいっぱいになっています。そのため、 最も前に使用されたデータ9が取り除かれ、 データ1がバッファに追加されます。

このアルゴリズムはとても優れていますが、いくつかの限界があります。例えば、大規模なテーブル上でフルスキャンを行うとどうなるでしょうか。言い方を変えると、バッファのサイズを超えた大きさのテーブルやインデックスを扱うと、どうなるのかということです。このアルゴリズムを使用すると、フルスキャンのデータは一度しか使わない可能性が高いにも関わらず、キャッシュに残る全ての値を取り除いてしまうでしょう。

改良

この事象を防ぐために、特有のルールを加えたデータベースもあります。 Oracleのドキュメント で例を見てみましょう。

非常に大規模なテーブルを扱う場合、データベースはダイレクトパスリードを使うのが一般的です。これは、ブロックを直接ロードし、（中略）バッファキャッシュの追加を回避します。中規模のテーブルを扱う場合、データベースはダイレクトリードまたはキャッシュリードを使うでしょう。そして、スキャンがバッファキャッシュを実際に取り除くことを防ぐため、ブロックをLRUリストの最後に置きます。

また、LRU-Kと呼ばれるLRUの上位バージョンを使う場合もあります。例として、SQL ServerがK=2となるLRU-Kを使うことが挙げられます

このアルゴリズムの背景には、使用履歴をもっと配慮するべきだという考えがあります。単純なLRU（これもK=1のLRU-Kです）を使うと、アルゴリズムは最後に使ったデータのみをのみを考慮します。しかし、LRU-Kを使うと以下のようになります。

• 最近からさかのぼってK回のあいだに使われたデータ を考慮します。
• データの使用された回数に 重み付けをします。
• キャッシュ内に新しいデータの一団をロードする場合は、古くても使用頻度の高いデータは取り除かれません（なぜなら、重みが大きいからです）。
• しかし、このアルゴリズムでは、もう使われていない古いデータをキャッシュ内に保持することはできません。
• そのため、 使われていないデータは、時間の経過と共に重みが減少していきます。

重みの計算は負荷が高いため、SQL ServerではK=2のみを使っています。この値は許容できる程度のオーバーヘッドで高いパフォーマンスを見せます。

LRU-Kについて、もう少し詳しく学びたい場合は、初出の論文『The LRU-K page replacement algorithm for database disk buffering（データベースディスクをバッファリングするためのLRU-Kページ置換えアルゴリズム）』（1993年）をお読みください。

その他のアルゴリズム

当然ですが、キャッシュを管理するアルゴリズムは他にもあります。例をご紹介しましょう。

• 2Q（LRU-Kに似たアルゴリズム）
• CLOCK（LRU-Kに似たアルゴリズム）
• MRU（最後に使ったデータを考慮するという、LRUと同じ理論を使用しますが、別のルールも存在します）
• LRFU（最も古く、使用頻度の低いデータから取り除かれる）

また、初期設定ではない別のアルゴリズムを使えるデータベースもあります。

書き込みバッファ

ここまで、読み取りバッファについての「データを使う前にロードするもの」というお話だけしてきました。しかし、データベース内には書き込みバッファもあります。データを1つ1つ書き出しては個別にディスクへアクセスし、それを大量に行う……ということをする代わりに、書き込みバッファにはデータを格納し、ひとまとまりでディスク上に書き出します。

バッファは、列（理論的に、または人間がデータを見る時のデータ）ではなくページ（データの最小ユニット）を格納することを覚えておいてください。修正されて、ディスクに書き込まれていない場合、バッファプール内のページは ダーティ です。このダーティページをディスク上に書き込む最適なタイミングを決めるため、複数のアルゴリズムが存在しています。これは、この記事の次のパートでご紹介するトランザクションの概念と強く結びついています。

トランザクションマネージャ

このパートは最後になりますが、とても大切なことを説明します。それはトランザクションマネージャです。このプロセスが、どのようにトランザクションでクエリを実行するのかを見ていきます。しかし、その前にACIDトランザクションの概念を理解しなければいけません。

ACIDについて

ACIDトランザクションとは、次の4つのことを確実にするための作業単位です。

• Atomicity（原子性、不可分性） ：トランザクションは、10時間かかったとしても、結果は”全てかゼロか”となります。トランザクションがクラッシュした場合は、トランザクション前まで状態が戻ってしまうのです（このトランザクションは ロールバックされます ）。

• Isolation（独立性、隔離性、分離性） ：AとBという2つのトランザクションが同時に実行された場合、トランザクションAがBの前、後、最中のいずれで終わるかには関わらず、トランザクションAとBの結果は必ず同じになります。

• Durability（耐久性、持続性） ：一度、トランザクションがコミットされると（つまり、無事に完了すると）、データは何があってもデータベースに留まります（クラッシュやエラーがあったとしても同じです）。

• Consistency（一貫性、整合性） ：有効なデータのみ（関係的制約と機能的制約に関して）はデータベースに書き込まれます。このConsistency（一貫性）は、Atomicity（原子性、不可分性）やIsolation（独立性、隔離性）と関連しています。

同じトランザクションが行われている間、複数のSQLクエリを実行し、データの読み取り、生成、更新、削除ができます。2つのトランザクションが同じデータを使っていると、混乱が生じます。古典的な例として、口座Aから口座Bへと送金する場合が挙げられます。以下の2つのトランザクションを想像してください。

• トランザクション1（以下T1）では、100ドルが口座Aから口座Bへと送金されます。
• トランザクション2（以下T2）では、50ドルが口座Aから口座Bへと送金されます。

ACID特性に話を戻しましょう。

• Atomicity（原子性、不可分性） は、T1を実行した際、何が（サーバ故障やネットワーク障害などが）起きたとしても、「口座Aから100ドルを送金したが口座Bに入金されていない」という（矛盾した）事態に陥らないことを保証しています。
• Isolation（独立性、隔離性、分離性） は、T1とT2が同時に実行された際、最終的に「口座Aから150ドルが送金され、口座Bに150ドルが入金される」ということを保証しています。これは例えば、「口座Aから150ドルが送金されたが、T2の動作がT1の動作によって消されたため口座Bに50ドルしか入金されていない」という事態に陥らないことを保証しています。
• Durability（耐久性、持続性） は、T1実行後にデータベース障害が起きたとしても、T1でコミットされたトランザクション操作が消えてしまわないことを保証します。
• Consistency（一貫性、整合性） は、トランザクション実行の際、システムがお金を生み出したり失くしたりしないよう保証します。

[このパートについては、もし興味がなければ飛ばして次のパートを読んでください。ここで話す内容は、この後の記事の内容にはあまり関わってきません。]

最近のデータベースの多くでは、デフォルト動作として完全なトランザクションの分離を使用していません。これは、パフォーマンスに大きく影響するからです。SQL標準では、トランザクション分離レベルを次の4段階に定義しています。

• Serializable(直列化可能) (SQLiteではデフォルト動作)は、一番高い分離レベルです。2つのトランザクションが同時に実行されている場合は、それぞれ100％独立しており、独自の「世界」で処理が行われています。

• Repeatable read(反復可能読み取り) (MySQLではデフォルト動作)は、それぞれのトランザクションが独自の「世界」で処理されますが、例外があります。トランザクションが正常に完了した後で新しいデータを追加すると、このデータは別の実行中のトランザクションで見ることができます。しかし、Aがデータの変更を行った上で正常に完了した場合は、この変更されたデータは別の実行中のトランザクションで見ることはできません。トランザクションの分離は新しいデータに関してのみ有効で、既存のデータには当てはまりません。

例えば、トランザクションAが「SELECT count(1) from TABLE_X」を実行した後で、トランザクションBが新しいデータをTABLE_Xに追加し、コミットした場合、トランザクションAが再びcount(1)を実行して返される値は、最初に実行した時に返された値とは異なります。

これは ファントムリード と呼ばれます。

• Read committed (コミット読み取り) (OracleやPostgreSQL、SQL Serverではデフォルト動作)は、反復読み取りと新規の分離を実行します。トランザクションAがデータDを読み取った後に、トランザクションBがデータを変更（あるいは削除）し、コミットすれば、トランザクションAが再び読み取るデータDは、トランザクションBによって変更（あるいは削除）されたデータ内容になります。

これは non-repeatable read(反復不能読み取り) と呼ばれます。

• Read uncommitted (非コミット読み取り) は、一番低い分離レベルです。読み取りコミットと新規の分離を実行します。トランザクションAがデータDを読み取った後で、トランザクションBがデータを変更したが、まだコミットせず実行中の場合でも、トランザクションAが再び読み取るのは変更されたデータになります。しかし、トランザクションBがデータを元に戻した場合には、トランザクションAが2回目に読み取ったデータDはコミットされたデータではないため無効になります。

これは ダーティリード と呼ばれます。

多くのデータベースでは独自のカスタム分離レベルがあります（例えば、PostgreSQLやOracle、SQL Serverで使用されているスナップショット分離）。さらに、多くのデータベースではSQL標準の全ての分離レベル（特にread uncommittedの分離レベル）を導入していません。

デフォルトの分離レベルは、接続の初めに、ユーザや開発者によってオーバーライドすることが可能です（とても簡単なコードを書き足すだけです）。

並行性制御

独立性や一貫性、原子性を確保するための一番の問題は、 同じデータへの書き込み処理 です（データの追加、更新、そして削除など）。

• 全てのトランザクションがデータ読み取り専用の場合、互いのトランザクションの動作を変更することなく、同時に実行することできます。
• 他のトランザクションが読み取ったデータを変更するトランザクションが（最低でも）1つある場合、データベースはこの変更を他のトランザクションから隠す必要があります。さらに、変更データを見ていないトランザクションによって、この変更が消去されないようにしなければなりません。

この問題を並行性制御と呼びます。

この問題を解決する最も簡単な方法は、各トランザクションを1件ずつ実行することです（例えば、順番に）。しかしこれではまったくスケーラビリティはありません。また、1件のトランザクションの処理に対して、マルチプロセッサやコアサーバ上で1つのコアだけを動作させるのは非常に効率が悪いと言えます。

理想的な解決方法は、トランザクションが作成または取り消された場合に、下記を実行することです。

• 全てのトランザクション処理を監視する。
• 複数のトランザクション処理で、同じデータを読み取ったり変更したりすることで矛盾が生じていないか確認する。
• 矛盾するトランザクションがある場合、処理の順番を変更することで矛盾するトランザクションを最小限に抑える。
• 特定の順番で（矛盾しないトランザクションは同時に実行させて）矛盾するトランザクションを実行する。
• トランザクションの取り消しも考慮する。

形式的には、これは重複するスケジューリングの問題です。具体的に言うと、非常に難しく、CPUコストの高い最適化問題なのです。エンタープライズのデータベースでは、新しいトランザクションが生じるたびに、ベストなタイミングを計って実行する余裕はありません。そのため、矛盾するトランザクションへの対応に時間を費やすようなやり方は理想的なアプローチとは言えません。

ロックマネージャ

この問題に対し、多くのデータベースは ロック や、あるいは データのバージョン管理 を行います。重要だと思うので、まず、ロックについて話してから、データのバージョン管理について触れます。

悲観ロック

まず、ロックの概念は次のとおりです。

• トランザクションでデータが必要になった場合、
• データをロックします
• 他のトランザクションでも同じデータが必要になった場合、
• 先に必要になったトランザクションの処理が完了し、データを解放するのを待つしかありません。

これを排他ロックと呼びます。

データ読み取り専用のトランザクションのためだけに排他ロックを使用すると、 同じデータを必要としている別のデータ読み取り専用のトランザクションを待機させるため 、コストがかかってしまいます。このような場合に対応するために、 共有ロック と呼ばれるタイプの異なるロックがあります。

共有ロックでは次のことが可能です。

• あるトランザクションでデータAの読み取りだけが必要な場合、
• 「共有ロック」によって、データの読み取りを実行します。
• 第2のトランザクションでもデータAの読み取りだけが必要になっても、
• 「共有ロック」によって、データの読み取りを実行します。
• 第3のトランザクションがデータAを変更する必要がある場合、
• 先の2つのトランザクションが終了し、データを解放するのを待ってから「排他ロック」をデータAに適応します。

さらに、別のトランザクションでデータの読み取りが必要になっても、排他ロックが解除され、共有ロックに変わるのを待たないと、データの読み取りはできません。

ロックマネージャは、ロックの実行および解除を行います。内部的には、ロックをハッシュテーブルで（ロックするデータの鍵の場所を）保持し、対象のデータを把握します。

• どのトランザクションによってデータがロックされているのか
• どのトランザクションがデータを待っているのか

デッドロック

しかし、ロックを使用すると、2つのトランザクションが永遠にデータを待ち続けてしまう場合があります。

上の図では、

• トランザクションAがデータ1を排他ロックし、データ2を待っています。
• トランザクションBがデータ2を排他ロックし、データ1を待っています。

これを デッドロック と呼びます。

デッドロックの状態を解除するために、どのトランザクションを取り消し（ロールバック）するかは、ロックマネージャが決めます。この判断は簡単ではありません。

• 変更したデータの量が少ない（そのためロールバックのコストがあまりかからない）トランザクションから中止する方が良いのでしょうか。
• 待ち時間の長いトランザクションを優先し、実行された時間の浅いトランザクションから中止した方が良いのでしょうか。
• 処理時間の短いトランザクションから中止した（また飢餓状態を避けた）方が良いのでしょうか。
• ロールバックの際、いくつのトランザクションが影響されるのでしょうか。

これらを決める前に、まずデッドロックが存在するかを確認する必要があります。

ハッシュテーブルを（上の図のように）グラフとして見ることができます。グラフでループが見られる場合はデッドロックが存在すると言うことです。しかし、（全てのロックを確認できるグラフは大きく）ループを確認するのはコストがかかるため、 タイムアウト を使用する方が簡単です。タイムアウト前にロックを獲得できない場合、トランザクションはデッドロック状態に陥ります。

さらにロックマネージャでロックする前に、デッドロック状態の原因にならないかの確認をします。しかし、これも完璧に行うためには、計算コストがかかります。そのため、大抵基本的ルールとして、事前に確認は設定されています。

2フェーズロック

分離を確実なものにする 最も簡単な 方法は、トランザクション実行の開始にロックを取得し、終了にロックを解放することです。つまり、トランザクション実行前に全てのロックを取得するまで待機し、処理後に解放しなければなりません。これは機能こそしますが、全てのロックを待機するために 多くの時間を無駄遣いします

さらに早く実行できる方法は、 2フェーズロックプロトコル （DB2やSQL Serverで使用）で、トランザクションを次の2つのフェーズに分散することです。

• トランザクションがロックを取得できるが、解放できない 成長フェーズ
• トランザクションが（処理済みのデータで、再度処理しないデータを）ロックを解放できるが、取得できない 縮退フェーズ

訳注
2フェーズロックがないと生じる一般的な矛盾
トランザクションA実行前、X=1およびY=2とする。トランザクションA実行後に、AがトランザクションBによって変更されたデータY=1を処理。分離性からAはY=2を処理しなければならない。

2つのフェーズに分ける単純な発想の背景には次のような考えがあります。

• ロックの解除を待つトランザクションの待機時間を短縮するために、必要のないロックを解除する。
• トランザクション実行後に変更されたデータの取得を回避し、トランザクション実行時に取得したデータとの整合性を保つ。

このプロトコルは良く機能しますが、例外があります。それは、データを変更しロックを解除したトランザクションが取り消された（ロールバックされた）場合になります。この時、別のトランザクションによって変更された値が読み取られても、この値はロールバックされてしまいます。このような問題を回避するため、 全ての排他ロックをトランザクション終了後に解放する必要があります。

補足

実際のデータベースでは、もっと高性能なタイプのロック（インテンションロックなど）や粒度の細かいロック（行単位ロック、ページ単位ロック、セグメント単位ロック、テーブル単位ロック、表領域単位ロックなど）を使用していますが、発想は同じです。

私がここまでトランザクションのデータアクセスの際に発生する問題の解決方法として、純粋にロックを基本とする視点で話を進めてきました。 別の方法としては、データのバージョン管理で対応することができます。

この発想の背景には次のような考えがあります。

• 全てのトランザクションによって、同じデータを同じタイミングで変更できる。
• それぞれのトランザクションは、データのコピー（ないしはバージョン）を独自に持っている。
• 2つのトランザクションによって、同じデータが変更された場合、片方の変更のみが承認され、承認されず却下された変更をしたトランザクションはロールバックされる（そして、多分再実行される）。

データのバージョン管理は、次の理由からパフォーマンスを向上できます。

• 読み取りトランザクションが書き込みトランザクションを妨害しない
• 書き込みトランザクションが読み取りトランザクションを妨害しない
• 「太く遅い」ロックマネージャのオーバーヘッドがない

2つのトランザクションによって、同じデータが変更された場合以外では、ロックを使用するよりも良い方法だと思います。さらに、オーバーヘッドのディスクの空き容量が多くなります。

データのバージョン管理とロックの構想は異なります。 楽観ロックと悲観ロックの違い なのです。それぞれ、一長一短ですが、使用目的によっても異なってきます（読み取りが多いのか、書き込みが多いのかなど）。データのバージョン管理について読みたい方は、 この素晴らしいプレゼンテーション をお勧めします。このプレゼンでは、PostgreSQLで複数のバージョンの並行性制御をどのように導入しているか説明しています。

DB2(DB2 9.7まで)やSQL Server(スナップショット分離以外)のようなデータベースではロックを使用しています。しかし、PostgreSQLやMySQL、Oracleはロックとデータのバージョン管理が混在するアプローチを取っています。データのバージョン管理のみを使用するデータベースは知りません（ご存じの方はぜひ教えてください）。

[08/20/2015更新] 記事を読んだ方からいただいたコメントです。

FirebirdとInterbaseはデータロックを使用せず、バージョン管理を使用しています。
バージョン管理はインデックスに面白い効果をもたらします。例えば、固有のインデックスが複製を持つことがあったり、テーブルに存在する列の数よりインデックス登録があったりすることがあります。

複数の分離レベルについて書きましたが、分離性を高めるとロックの数を増やすことになり、結果的にトランザクションを待機させ、無駄に時間を消耗することになります。このことから、多くのデータベースは最も高いトランザクション分離レベル（Serializable）をデフォルトにしていません。

これも、主要なデータベースのドキュメントで内容を確認してください（例えば、 MySQL や PostgreSQL 、 Oracle など）。

ログマネージャ

ここまでに見てきたように、データベースはパフォーマンス向上のためにデータをメモリバッファに保存します。しかし、トランザクションがコミットされている途中にサーバがクラッシュすると、クラッシュ時にメモリに残っているデータが失われ、トランザクションの永続性が壊されます。

ディスクにはトランザクションの全部を書き込むことができますが、サーバがクラッシュすると、ディスクにデータを書き込んでいる途中で終わってしまい、トランザクションの原子性が壊されます。

トランザクションによって書き込まれた修正は、全く実行されないか、完了するかのどちらかでなければならなりません。

この問題に対処するには、２つの方法があります。

• シャドーコピー/シャドーページ ：各トランザクションは処理用に、データベース（またはデータベースの一部）のコピーを作成し、このコピーを使って処理を行います。エラーが発生すると、このコピーは削除されます。処理が正常に終わると、データベースはファイルシステムの早業を使って瞬時にデータをコピーに置き換え、それから「古い」データを削除します。
• トランザクションログ ：トランザクションログはストレージ空間です。ディスクへの書き込みの前に、毎回、データベースはトランザクションログ上に情報を書き込んで、トランザクションがクラッシュまたはキャンセルされた場合にデータベースが未完了のトランザクションを削除（または完了）する方法が分かるようにしておきます。

WAL

多くのトランザクションを伴う大きなデータベースでシャドーコピー／ページを使用すると、巨大なディスクオーバーヘッドが生まれます。これが、最近のデータベースが トランザクションログ を使用する理由です。トランザクションログは、 安定したストレージ に保存しなければなりません。ここではストレージ技術について深くは触れませんが、ディスク故障から保護するには、（少なくとも）RAIDディスクが必須です。

ほとんどのデータベース（少なくともOracle、 SQL Server 、 DB2 、 PostgreSQL 、MySQLおよび SQLite ）は、 ログを先に書き出すプロトコル (WAL)を使用してトランザクションログを処理します。WALプロトコルには、3つの規則があります。

• 1) データベースへの修正のそれぞれにログレコードが生成される。 このログレコードはデータがディスクに書き込まれる前にトランザクションログに書き込まれなければならない。
• 2) ログレコードの書き込み順：ログレコードBより前に発生したログレコードAは、Bより前に書き込まれなければならない。
• 3) トランザクションがコミットされるときは、トランザクションが正常に終了する前にコミット順序がトランザクションログに書き込まれなければならない。

この作業はログマネージャによって行われます。簡単に言うと、ログマネージャはキャッシュマネージャとデータアクセスマネージャ（データをディスクに書き込む）の間にあり、全ての更新／削除／作成／コミット／ロールバックを、それらがディスクに書き込まれる前に毎回トランザクションログに書き込みます。簡単ですね?

いいえ、違います!　これまで見てきたように、データベースに関係することは全て、「データベース効果」に呪われているのです。まじめに言うと、問題は、パフォーマンスを良好に保ちながらログを書く方法を見つけることです。トランザクションログへの書き込みが遅すぎると、何もかもが遅くなってしまいます。

ARIES

1992年に、IBMの研究者たちはARIESと呼ばれるWALの拡張版を「発明」しました。近代のほとんどのデータベースでは多かれ少なかれARIESが使用されています。論理は同じでなくても、ARIESの背景にある概念はどこにでも使われています。「発明」を括弧に入れた理由は、この MITの講義 によれば、IBMの研究者たちは、「トランザクションを復旧するための優れた実践方法を書くこと以上のことはしなかった」からです。ARIESが発表されたのは私が5歳の頃なので、辛口の研究者たちから出た古い噂は気になりません。実は、この情報をここに出すのは、最後の技術解説を始める前に皆さんに一息入れてもらうためです。私は、 ARIEの研究論文 の大部分を読みましたが、とても興味深いものでした。ここではARIESの概要に触れるだけなので、詳細を知りたい方は、この論文をお読みになることを強くお薦めします。

ARIESは、 A lgorithms for R ecovery and I solation E xploiting S emanticsの略語です。

この技法の目的は2つです。

• 1) ログの書き込み時の良好なパフォーマンス
• 2) 高速で 信頼性の高い復旧

データベースがトランザクションをロールバックする理由はいくつかあります。

• ユーザがキャンセルした
• サーバまたはネットワークが故障した
• そのトランザクションによってデータベースの整合性が壊された（例えば、ある列にUNIQUE制約があるのに、トランザクションが複製を追加したなど）
• デッドロック

時には（例えば、ネットワーク故障の場合）、デースベースがトランザクションを復旧することができます。

どうすれば可能なのでしょうか?　この問いに答えるには、ログレコードに保存されている情報について理解する必要があります。

ログ

トランザクション中の各処理（追加／削除／修正）についてログが作成されます。 このログレコードは、次の要素で構成されています。

• LSN ：固有のログ連番。このLSNは、時系列順に与えられる ^(1) 。このことは、処理Aが処理Bより前に発生した場合は、ログAのLSNはログBのLSNより小さくなることを意味します。
• TransID ：その処理を作成したトランザクションのID。
• PageID ：修正されたデータのディスク上の位置。ディスク上のデータの最小量はページなので、データの位置は、そのデータを含むページの位置となる。
• PrevLSN ：同じトランザクションによって生成された直前のログレコードへのリンク。
• UNDO ：処理の効果を削除する方法。
  例えば、処理が更新である場合、UNDOは、更新された要素の更新前の値または状態のどちらかを保存するか（物理的UNDO）、もしくは、処理を直前の状態に戻す（論理的UNDO） ^(2) 。
• REDO ：処理を繰り返す方法。
  同様に、これにも2つの方法がある。処理後の要素の値または状態を保存するか、もしくは、処理自体を繰り返す。
• …：（参考までに、ARIEログには、あと2つ、UndoNxtLSNとTypeというフィールドがある。)

さらに、ディスクの各ページ（ログデータではなくデータを保存している）には、そのデータを修正した最後の処理のログレコードのID（LSN）があります。

1 ：LSNが与えられる方法はログが保存される方法に関連しているので、もっと複雑です。しかし、概念は同じです。

2 ：物理的UNDOの処理は実に厄介なので、ARIESでは論理UNDOだけを使用します。

注：私のわずかな知識によると、UNDOを使用しないのはPostgreSQLだけです。これは、その代わりにガーベジコレクションのデーモンを使用して、古いバージョンのデータを削除します。このことは、PostgreSQLでのデータバージョン管理の実装に関連しています。

イメージしやすいように、クエリ”UPDATE FROM PERSON SET AGE = 18;”で生成されたログレコードの例を、以下にシンプルな形で図示します。このクエリが、例えばトランザクション18で実行されるとしましょう。

それぞれのログには固有のLSNがあります。リンクされているログは同じトランザクションに属しており、その順番は時系列順です（リンクされたリストの最後のログが、最後の処理のログ）。

ログバッファ

ログの書き込みが大きなボトルネックになることを避けるため、ログバッファが使われます。

クエリエグゼキュータが修正を求める時の手順。

• 1) キャッシュマネージャが自身のバッファに修正を保存する。
• 2) ログマネージャが自身のバッファに関連ログを保存する。
• 3) この段階で、クエリエグゼキュータは処理が完了したと判断する（よって、他の修正を要求できる）。
• 4) そして（その後）、ログマネージャはトランザクションログにログを書き込む。ログを書き込むタイミングは、アルゴリズムが決定する。
• 5) そして（その後）、キャッシュマネージャがディスクに修正を書き込む。修正データをディスクに書き込むタイミングは、アルゴリズムが決定する。

トランザクションがコミットされたとは、トランザクション内の全ての処理に対して上記5段階の手順が完了したという意味です。 トランザクションログへの書き込みは、「トランザクションログのどこかにログを追加する」だけなので高速ですが、一方でディスクにデータを書き込むのは、「データを速く読めるように書き込む」ので、より複雑です。

StealとForce

パフォーマンスの観点から、 手順5をコミット後に行うという選択肢があります。 これにより、クラッシュが起こった場合でもREDOログでトランザクションのリカバリが可能です。これを No force と言います。

逆にForceを選択しているデータベース（手順5はコミット前に行われる）では、リカバリ中の作業負荷を軽減できます。

それとは別に、 データを段階的にディスクに書き込むか（Steal） 、あるいはコミット命令が出るまでバッファマネージャが待機し、全データを1度に書き込むか（No steal）という選択の問題があります。書き込みの速さ（代わりにUNDOログを使うリカバリには時間がかかる）を選ぶか、それとも高速なリカバリを選ぶか、いずれを優先するかがその決め手です。

以下に、リカバリにおける上記の方法の効果をまとめました。

• Steal/No forceではUNDOとREDOが必要：パフォーマンスは最も高い 反面、ログやリカバリプロセスが（ARIESのように）より複雑になる。 ほとんどのデータベースはこの方法を選択。 注：このことを複数の論文や講座で目にした記憶があるのですが、（それが明示されている）公式の文書は見つけることができませんでした。
• Steal/ForceはUNDOのみ必要。
• No steal/No forceはREDOのみ必要。
• No steal/Forceはいずれも必要なし。 パフォーマンスが最も低く 、大量のRAMが必要。

リカバリについて

ログについてよく分かりましたよね。どんどん使っていきましょう。

さて、話は変わって新しいインターンがデータベースをクラッシュさせたとします（ルール1：いつだってインターンの失敗）。そうなると、データベースをリスタートしてリカバリしなければなりません。

ARIESでは、以下の3つの手順でクラッシュから回復します。

• 1) 分析 ：このリカバリのプロセスでは、まず全てのトランザクションログ1を読み込んで、クラッシュの間に発生した出来事のタイムラインを再作成します。これにより、どのトランザクションをロールバックし（コミット命令がない全てのトランザクションがロールバックされる）、どのデータがクラッシュ時にディスクに書き込まれる必要があったかを判別します。
• 2) REDO ：このプロセスでは、分析中に判別されたログレコードをベースに、REDOを使ってクラッシュ前の状態にデータベースを更新します。

REDOの段階の間、REDOログは時系列順に処理されます（LSNを使用）。

リカバリプロセスは各ログに関して、ディスク上で修正すべきデータを含むページのLSNを読み込みます。

LSN（ディスクのページ）≧LSN（ログレコード）であれば、データはクラッシュ前に既にディスクに書き込まれたことを意味するので（ただし、値はログの後、クラッシュの前に処理によって上書きされている）、何も行われません。

LSN（ディスクのページ）＜LSN（ログレコード）の場合、ディスクのページが更新されます。

REDOは、リカバリのプロセスを簡略化するという理由から、ロールバックされる見込みのトランザクションでも実行されます（が、最近のデータベースはその限りではないと思います）。

• 3) UNDO ：このプロセスでは、クラッシュ時に不完全だったトランザクションの全てをロールバックします。ロールバックは各トランザクションの最後のログから始められ、最初のログに向かってUNDOログを処理します（ログレコードのPrevLSNを使用）。

リカバリの間は、ディスクのデータがトランザクションログに書き込まれているものと同期されるように、リカバリプロセスによるアクションの通告をトランザクションログは受ける必要があります。その解決策の1つとして考えられるのは、実行されないトランザクションのログレコードを削除することですが、それは非常に困難です。その代わりとしてARIESでは、削除されるトランザクションのログレコードを論理的に削除するトランザクションログに補正ログを書き込みます。

トランザクションが「手動」でキャンセルされるか、ロックマネージャにより（デッドロックを止めるために）キャンセルされるか、あるいは単にネットワークの不具合でキャンセルされた場合、分析のプロセスは必要ありません。何をREDOしてUNDOするかの情報はメモリ内の2つのテーブルで利用できます。

• トランザクションテーブル （現在の全トランザクションの状態を保存）
• ダーティページテーブル （どのデータがディスクに書き込まれる必要があるかを保存）

これらのテーブルは、新規の各イベントに関連してキャッシュマネージャとトランザクションマネージャにより更新されます。どちらもメモリ内に保持されているため、データベースがクラッシュすれば破壊されます。

分析の段階でやることは、クラッシュ後にトランザクションログの情報を参照しながら両方のテーブルを再作成することです。1：分析プロセスをスピードアップするため、ARIESでは チェックポイント という考えを用意しています。その意味するところは、トランザクションテーブルやダーティページテーブルの内容、それから当該の書き込み時点における最終LSNをディスクに書き込むというもので、これによって分析プロセスの際、このLSN以降のログだけを分析すれば済むようになるというわけです。

終わりに

この記事を書く前からテーマの大きさは心得ていましたし、詳しく書こうとすれば時間がかかるだろうことも承知していたつもりです。しかし実際にかかった時間は想定の2倍以上でした。自分の心づもりは多少楽観的に過ぎたようです。ただ、その間に多くを学ぶことはできました。

もしデータベースについて良質な総括資料をお望みの場合は、ぜひとも研究論文「 Architecture of a Database System （データベースシステムの構造）」を読んでみてください。これはデータベースについての優れた入門書（110ページ）で、コンピュータ科学分野以外の人でも読める内容となっています。この記事の計画を練るにあたって私も大いに参考にしました。基本的には私の記事のようにデータ構造やアルゴリズムに主眼を置くのではなく、構造の概念についてより重点的に解説しています。

この記事を注意深く読んでいただいた方々はデータベースの強力さについて十分に理解されたはずですが、長い記事だったので、ここで改めてまとめておきます。

• B+ツリーインデックスの概要
• データベースの全体の概要
• 結合演算子に力点を置いたコストベースの最適化の概要
• バッファプール管理の概要
• トランザクション管理の概要

上記以外にも、データベースには豊富な機能があります。例えば、私は以下のような厄介な問題には触れませんでした。

• クラスタデータベースおよびグローバルトランザクションの管理の方法
• データベース実行中にスナップショットを取る方法
• 効率的にデータを保存（および圧縮）する方法
• メモリ管理の方法

バグの多いNoSQLデータベースと堅実なリレーショナルデータベースのどちらかを選ばなければならない時はよく考えましょう。誤解しないでいただきたいのは、一部のNoSQLデータベースはとても素晴らしいということです。ただ、まだ歴史が浅く、いくつかの用途に関する特定の問題にしか答えられていないのも事実です。

最後に、もし誰かがデータベースの仕組みについて皆さんに質問したとしましょう。ここまで読んでくださった皆さんなら、その質問に背を向けずに答えることができますよね。

答える代わりに、この記事のことを教えていただいてもいいですよ。