並行制御モデル
各トランザクションは複数の読み書き操作を含み、これらの操作はデータベース内の異なるデータに対して行われます。最も単純な並行制御方法は直列実行（serial）です。つまり、あるプロセスが別のプロセスが操作を完了し、応答を受信するまで、次の操作をトリガーしません。しかし、この方法は明らかに高並行性の要求には適していません。そのため、学者たちは直列化可能（serializable）な方法を提案しました。これは、トランザクション内の複数の操作を並列（非直列）に実行できるものの、最終的な結果は直列実行と同じであることを保証します。
トランザクション内の読み書き操作を通じて、トランザクション間の依存関係（トランザクションが直列化された後の実行順序を表す関係）を確立できます。主な依存関係は以下の3種類です：
- 書き込み依存（Write Dependency）：トランザクションAがデータXを変更した後、トランザクションBが同一のデータXを変更する場合、トランザクションBはトランザクションAに依存します。
- 書き込み読み取り依存（Read Dependency）：トランザクションAがデータXを読み取った後、そのデータXがトランザクションBによって変更された場合、トランザクションAはトランザクションBに依存します。
- 読み取り書き込み依存（Anti Dependency）：トランザクションAがデータXを読み取った後、トランザクションBが同一のデータXを変更する場合、トランザクションBはトランザクションAに依存します。
これらの依存関係によって定義される直列化可能性は、競合直列化可能（conflict serializable）と呼ばれます。トランザクション間の競合関係が環を形成しない場合、競合直列化可能性が保証されます。一般的な実装メカニズムには、2段階ロックとオプティミストック機構があります。2段階ロックは排他的ロックによって競合する変更を制限し、デッドロック検出機構によって循環を生じさせるトランザクションをロールバックすることで、環の不存在を保証します。一方、オプティミストックはコミット時に検出を行い、環を引き起こす可能性のあるすべてのトランザクションをロールバックします。
しかし、直列化可能分離レベルの導入は、実際の商用データベースではあまり用いられていません。主な理由は、そのパフォーマンスコストが高いためです。そのため、通常はトランザクションのパフォーマンスと拡張性を向上させるために、許容可能な一部の例外を許容します。一般的な分離レベルには、スナップショット読み取りと既コミット読み取りが含まれます。スナップショット読み取りはマルチバージョンデータの維持に依存し、固定の読み取りバージョン番号で対応するバージョンのデータを読み取ることで、読み書き依存による環状構造を生じさせます。例えば、トランザクションAがバージョン1のデータXを読み取りデータYを変更し、トランザクションBがバージョン1のデータYを読み取りデータXを変更すると、最終的に書き込みスキュー（Write Skew）が発生します。既コミット読み取り分離レベルでは、再現不能読み取り（トランザクション内部での2回の読み取り結果が異なる）が露呈します。分離レベルを定義する抽象化を設計し、パフォーマンスと使いやすさのバランスを取ることが、トランザクション分離レベル設計の鍵の一つです。
OceanBaseデータベースの並行制御モデル
OceanBaseデータベースは、スナップショット読み取りとコミット済み読み取りの2種類の分離レベルをサポートし、分散環境において外部整合性を保証します。
マルチバージョンデータとトランザクションテーブル
読み書き操作の相互排他を避けるため、OceanBaseデータベースは設計段階からマルチバージョンストレージを採用し、読み取りバージョン番号とコミットバージョン番号という2つのグローバルバージョン番号を維持しています。これらは図中の ローカル最大読み取りタイムスタンプ と 最大コミットタイムスタンプ に相当します。更新のたびにメモリ内に新しいバージョンが記録され、これにより読み書きの非排他性が実現されます。
図に示すように、メモリ内にはデータA、B、Cの3行があります。各データはバージョン（ts）、値（val）、トランザクションID（txn）で管理・更新され、複数回の更新が同時に管理されることでマルチバージョンが維持されます。また、メモリ内にはトランザクションテーブルが存在し、各トランザクションのID、状態、バージョンが記録されています。トランザクションの開始時およびコミット時には、グローバルタイムスタンプキャッシュサービス（Global Timestamp Cache）からタイムスタンプを取得し、読み取りタイムスタンプおよびコミットタイムスタンプの参照に使用します。
図からわかるように、グローバルタイムスタンプ取得サービスは、最大で遭遇したトランザクションの読み取りタイムスタンプと、既にコミット済みのトランザクションのコミットタイムスタンプをそれぞれ120と100として維持しています（後ほどこの2つのタイムスタンプの役割について説明します）。メモリ内では、データAにはバージョン100のコミット済みデータaが含まれており、対応するトランザクションはトランザクション10です。同様に、データBには未決定バージョンのデータjと対応するトランザクション12が含まれ、データCには未決定バージョンのデータxと対応するトランザクション15が含まれています。トランザクションテーブルには、対応するトランザクションとその状態が含まれており、例えばトランザクション15はバージョン130で2フェーズコミット状態に入っています。
コミットリクエスト処理
OceanBaseデータベースの分散トランザクションには、RUNNING、PREPARE、COMMITの3つの状態があります。トランザクションの状態は分散環境では原子的に確認できないため、PREPARE段階では2フェーズコミットが導入されています。そのため、ローカルコミットバージョン番号（local commit version、別名prepare version）を維持し、トランザクションの グローバルコミットバージョン番号（global commit version、別名commit version）は、すべてのパーティションのローカルコミットバージョン番号の最大値によって決定されます。各パーティションは、トランザクションの グローバルコミットバージョン番号 がローカルパーティションの ローカルコミットバージョン番号 以上であることを保証します。これは、読み書きリクエストの並行制御を実現する鍵の一つです。
トランザクションのコミット時には2フェーズコミットが実行されます。各パーティションはローカルの 最大読み取りタイムスタンプ をローカルコミットタイムスタンプとして取得し、最初の参加者はグローバルタイムスタンプ取得サービスからグローバルタイムスタンプを取得して、最大値をローカルコミットタイムスタンプとして設定します。これにより、更新の欠落を防ぎます。下図のように、トランザクション12はコミット段階に入り、状態をPREPAREに設定し、ローカルトランザクションバージョン番号を最大読み取りタイムスタンプ（120）とグローバルタイムスタンプ（150）の最大値（150）に設定します。
トランザクションがコミットされると、対応する2フェーズコミットが実行されます。参加者の各パーティションについて、ローカルの 最大読み取りタイムスタンプ をローカルコミットタイムスタンプとして取得し、最初の参加者についてはグローバルタイムスタンプ取得サービスからグローバルタイムスタンプを取得して、最大値をローカルコミットタイムスタンプとして設定します。この保証は、単一値の読み書き競合（anti dependency）を防ぐためです。前述の保証により、コミットタイムスタンプは以前のすべての読み取りよりも大きいことが保証されるため、直列実行ではこれらの先行する読み取りの後に続けて実行できます。したがって、先行するトランザクションが本トランザクションを読み取っていないことは当然です。図に示すように、トランザクション12はコミット段階に入り、状態をPREPAREに設定し、ローカルトランザクションバージョン番号をローカルの 最大読み取りタイムスタンプ 120 と、(仮に最初のパーティションとする) グローバルタイムスタンプ が150の最大値である150に設定します。
2フェーズコミットが終了するまで、グローバルコミットタイムスタンプ がローカルコミットタイムスタンプ以上であることを保証します。コミットメッセージを受信すると、グローバルコミットタイムスタンプ が確定し、図に示すように、状態はコミットに戻り、タイムスタンプは160に設定され、更新データに非同期で反映されます。その後はトランザクションテーブルをクエリする必要はありません。さらに、最大コミットトランザクションタイムスタンプを更新して後続の読み取りリクエストを最適化し、ロックキュー内のトランザクションを覚醒させます。
書き込みリクエスト処理
データを書き込む際、書き込み依存性（write dependency）を保証するために、変更には2フェーズロックプロトコルが使用されます。書き込みリクエストがトリガーされたとき、その行のマルチバージョンで実行中のトランザクションが検出された場合、そのリクエストはロックマネージャーに投入され待機状態になります。OceanBaseデータベースでは、ロックマネージャー内に待機キューを実装しており、ロックまたはタイムアウトによってこの書き込みリクエストを起動します。図に示すように、データBを更新しようとしたとき、アクティブなトランザクション12がデータBを変更しているため、この書き込みリクエストはロックキューに投入され、トランザクション12の起動を待機します。
読み書き競合（anti dependency）や書き込み読み取り競合（read dependency）による環状構造の発生、および更新損失（lost update）を防ぐために、スナップショット読み取り分離レベルでは、書き込み操作がロックを取得した後、読み取りタイムスタンプをその行の最大コミットトランザクションタイムスタンプと比較します。読み取りタイムスタンプが行の最大コミットトランザクションタイムより小さい場合、そのトランザクションはロールバックされます。例えば、書き込み操作の読み取りタイムスタンプが100で、トランザクション12がタイムスタンプ160でコミットした場合、書き込み操作トランザクションのロールバックがトリガーされ、エラー(TRANSACTION_SET_VIOLATION)が報告されます。
分離レベルによって、書き込み操作の読み取りタイムスタンプの処理方法は異なります。
- 読み取りコミット済み（RC）分離レベルでは、書き込み操作の読み取りタイムスタンプはステートメント開始時に取得したタイムスタンプです。
TRANSACTION_SET_VIOLATIONエラーが発生した場合、トランザクション全体をロールバックする必要はなく、ステートメントをやり直して新しい読み取りタイムスタンプを取得するだけで済みます。 - スナップショット分離（SI）レベルでは、書き込み操作の読み取りタイムスタンプはトランザクション開始時に取得したタイムスタンプです。
TRANSACTION_SET_VIOLATIONエラーが発生した場合、「更新損失」を避けるためにトランザクション全体をロールバックする必要があります。
読み取りリクエスト処理
読み取り時には、読み取りバージョン番号を使用して対応するデータを読み取り、ローカルの最大読み取りタイムスタンプを更新します。前述の保証により、分散環境においてもスムーズに読み取りリクエストを処理できます。
実際の読み取り時には、いくつかのケースに分けて考えることができます。コミットまたはロールバックされたトランザクションを読み取る場合、グローバルコミットタイムスタンプとステータスに基づいて、対応するデータを読み取る必要があるかどうかを簡単に判断します。図に示すように、読み取りリクエストr1は読み取りバージョン番号90で読み取りを行いますが、スナップショット読み取りポリシーに基づき、読み取りバージョン番号80、データはbとなります。
RUNNING状態のトランザクションを読み取る場合、ローカル最大読み取りタイムスタンプが引き上げられ、その後のRUNNING状態のトランザクションがより大きなローカルタイムスタンプで2フェーズコミットに入ることを保証し、そのデータを安全にスキップします。図に示すように、読み取りリクエストr2は読み取りバージョン番号130で読み取りを行い、最大読み取りトランザクションタイムスタンプを引き上げた後、2フェーズコミットに入っていないトランザクション12をスキップし、読み取りバージョン番号100のデータbを読み取ります。
PREPARE状態のトランザクションを読み取る場合、ローカルタイムスタンプが読み取りタイムスタンプより大きい場合は安全にスキップできます。ローカルタイムスタンプが読み取りタイムスタンプより小さい場合は、グローバルコミットタイムスタンプと読み取りタイムスタンプの関係が確定できません。解決策は、優雅に待機することです（ロック読み取り）。図に示すように、読み取りリクエストr3は読み取りバージョン番号140で読み取りを行い、最大読み取りトランザクションタイムスタンプを引き上げた後、2フェーズコミット状態でローカルコミットタイムスタンプが130のトランザクションがグローバルコミットタイムスタンプと読み取りタイムスタンプ140の関係を確定するのを待ちます。
