並行制御の概要

並行制御モデル

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