並行制御モデル
各トランザクションには複数の読み書き操作が含まれており、これらの操作はデータベース内の異なるデータを対象とします。最も単純な並行制御方法は直列（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のうちの最大値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の関係を確定するのを待機します。
