ロックメカニズム

OceanBaseデータベースは、マルチバージョン2フェーズロックを使用して、その並行制御モデルの正確性を維持します。ロックメカニズムは、正しいデータの並行性と一貫性を保証するために重要な要素です。

OceanBaseデータベースのロックメカニズムは、データ行レベルでロックの粒度を設定します。同一行内の異なる列に対する変更は、同じロックによる排他を引き起こしますが、異なる行に対する変更はそれぞれ異なるロックであり、互いに関係ありません。他のマルチバージョン2フェーズロックを採用するデータベースと同様に、OceanBaseデータベースでは読み取り操作にはロックがかかりません。これにより、読み取りと書き込みの操作が互いに排他的にならないため、ユーザーの読み取りおよび書き込みトランザクションの並行処理能力が向上します。ロックの格納方式として、ロックを行単位（メモリまたはディスクに保存される可能性があります）に格納することを選択しており、メモリ内で大量のロックデータ構造を維持する必要がないようにしています。さらに、メモリ内でロック間の待機関係を維持し、ロックが解放される際にそのロックを待機している他のトランザクションを起動します。

ロックメカニズムの使用

詳しく見る前に、まずOceanBaseデータベースの行ロック機能の使い方を確認してみましょう。以下は、商品情報を更新するための一般的な業務SQLです。

UPDATE GOODS
SET    PRICE = ?, AMOUNT = ?
WHERE  GOOD_ID = ?
AND    LOCATION = ?;

上記のSQLでは、ユーザーが入力した商品IDと住所に基づいて、対応する価格と在庫を更新します。トランザクション内のこのSQLでは、トランザクション終了までに、対応する商品IDと住所のデータ行に行ロックがかけられ、すべての同時実行される更新はブロックされ待機状態になります。これにより、並行する変更によって引き起こされるダーティライト（Dirty Write）を防ぎます。つまり、データを更新する際、ユーザーは変更対象のデータ行に暗黙的にロックをかけており、ロックの範囲などを明示的に指定する必要がなく、OceanBaseデータベースの内部メカニズムによって並行制御が実現されます。

もちろん、ユーザーはロックメカニズムの使用を明示的に指定することもできます。以下は、商品情報を排他的に取得するための一般的な業務SQLです。

SELECT PRICE, AMOUNT
FROM   GOODS
WHERE  GOOD_ID = ?
AND    LOCATION = ?
FOR UPDATE;

上記のSQLでは、ユーザーが入力した商品IDと住所に基づいて、対応する価格と在庫を取得します。トランザクション内のこのSQLでは、トランザクション終了までに、対応する商品IDと住所のデータ行に行ロックがかけられ、すべての同時実行される更新はブロックされ待機状態になります。これにより、ユーザーが指定した明示的なロックがかけられます。異なる業務要件において、これは非常に重要なポイントです。

ロックメカニズムの粒度

OceanBaseデータベースはテーブルロックと行ロックをサポートしており、行ロックは排他的です。

テーブルロックは主に複雑なDDL操作を実現するために使用され、操作中はデータベーステーブル全体への同時アクセスを阻止し、トランザクションの原子性と一貫性を保証します。テーブルロックの粒度は大きいため、行ロックよりも多くのオブジェクトをロックできますが、その代わりに並行性も低下します。これは、テーブルロックが解除されるまで、そのテーブルにアクセスしようとする他のすべての操作がブロックされるためです。テーブルロックは通常、ロックレベル（行ロックやページロックなど）を細分化できないシナリオ、または次の操作がテーブル内の大部分のデータに影響を与えることが予想される場合に使用されます。この種のロックは、通常、テーブル構造の作成や変更などのデータ定義言語（DDL）操作で用いられます。

トランザクション処理において、同一行の異なる列を更新する場合、OceanBaseは行ロックを使用するため、異なるトランザクション間で相互にブロックし合います。これは、行上のデータ構造をロックする際のストレージコストを削減するためです。一方、異なる行のデータを更新する場合、トランザクション間で相互に影響を及ぼすことはなく、トランザクションの並行実行が可能になります。

ロックメカニズムの排他性

OceanBaseデータベースはマルチバージョン2フェーズロックを採用しており、トランザクションによる変更は毎回元の場所で行われるのではなく、新しいバージョンが生成されます。そのため、読み取りは一貫性スナップショットを通じて古いバージョンのデータを取得でき、行ロックがなくても対応する並行制御能力を維持できます。これにより、実行中の読み書きが互斥しないことが可能となり、OceanBaseデータベースの並行処理能力が大幅に向上しています。ただし、SELECT ... FOR UPDATE のような実行は依然として行ロックをかけるため、変更や別の SELECT ... FOR UPDATE と排他されたり待機したりします。また、変更操作は行ロックを必要とするすべての操作と排他的になります。

ロックメカニズムの格納

OceanBaseデータベースでは、ロックは行単位で格納されるため、メモリ内でメンテナンスが必要なロックデータ構造によるオーバヘッドを削減できます。メモリ内では、トランザクションが行ロックを取得すると、対応する行にそのトランザクションのマーカー、すなわち行ロックの保持者を設定します。トランザクションが行ロックを取得しようとすると、対応するトランザクションのマーカーを通じて自分が行ロックの保持者ではないことを認識し、試みを放棄して待機するか、自分が行ロックの保持者であることを認識した場合は行の使用権を取得します。トランザクションが行ロックを解放すると、すべてのトランザクションが関与する行から対応するトランザクションのマーカーが解除され、後続のトランザクションが再度ロックを取得できるようになります。

データがSSTableにダンプされると、マクロブロック内のデータには対応するトランザクションのマーカーが記録されます。他のトランザクションは依然として、トランザクション識別子を用いて対応するデータへのアクセスを許可するかどうかを判断する必要があります。メモリ内のロックメカニズムとは異なり、SSTableは不変である特性を持つため、トランザクションが行ロックを解放した後も、マクロブロック内のデータに記録されたトランザクションのマーカーを即座に削除することはできません。もちろん、トランザクション識別子を用いて対応するトランザクション情報を確認し、トランザクションが既にロックを解除しているかどうかを確認することは可能です。

ロックメカニズムの解放

ほとんどの2段階ロック実装と同様に、OceanBaseデータベースのロックはトランザクション終了時（コミットまたはロールバック）に解放され、データの不整合の影響を回避します。OceanBaseデータベースには他にも解放タイミングがあります。それはSAVEPOINTです。ユーザーがSAVEPOINTまでロールバックすることを選択した場合、トランザクション内部では、そのSAVEPOINT以降にデータに関与するすべての行ロックを、OceanBaseデータベースロックメカニズムの排他性 で説明しているメカニズムに従って解放します。

ロックメカニズムによるトランザクションのウェイクアップ

トランザクションをウェイクアップするために、排他ロックが発生すると、メモリ内で行とトランザクションの待機関係が維持されます。図に示すように、行AはトランザクションBによって保持され、トランザクションCとトランザクションDによって待機されています。この待機関係の維持は、行ロックが解放された際に対応するトランザクションCとDをウェイクアップできるようにするためです。トランザクションBが行Aを解放すると、順序に従ってトランザクションCをウェイクアップし、トランザクションCに依存してトランザクションDをウェイクアップします。

行とトランザクションの待機関係に加えて、OceanBaseデータベースはトランザクション間の待機関係も維持する場合があります。メモリ使用量を削減するため、OceanBaseデータベース内部では行とトランザクションの待機関係をトランザクション間の待機関係に変換することがあります。図に示すように、行AはトランザクションBによって保持され、トランザクションCとトランザクションDによって待機されており、これがトランザクションBがトランザクションCとトランザクションDによって待機されている形に変換されます。トランザクションBが終了すると、行間のロック待機関係が不明なため、トランザクションCとトランザクションDを同時にウェイクアップします。

ロック機構によるデッドロック

ロック機構の実装はデッドロックを引き起こす可能性があります。デッドロックとは、リソースに対する循環的な依存関係を指します。例えば、トランザクションAとトランザクションBが同時にリソースCとDを取得している場合、トランザクションAがリソースCを先に取得し、次にリソースDを取得しようとする一方で、トランザクションBがリソースDを先に取得し、次にリソースCを取得しようとします。このとき、どちらのトランザクションも既に取得しているリソースを放棄する意思がない場合、どのトランザクションも正常に終了できません。

タイムアウトに基づくデッドロックの解決

OceanBase データベース V3.2 より前のバージョンでは、能動的なデッドロック検出機能は含まれていません。そのため、業務ロジック上のデッドロックを解決するためには、主にタイムアウトロールバックメカニズムに依存しています。

対応する問題を解決するために、3 種類のタイムアウトメカニズムが存在します：

• ロックタイムアウトメカニズム：構成パラメータ名は ob_trx_lock_timeout で、デフォルトはステートメントのタイムアウト時間です。ロック待機がロックタイムアウト時間を超えた場合、対応するステートメントをロールバックし、ロックタイムアウトに対応するエラーコードを返します。この時点で、ある循環依存関係内のリソース依存が解消されるため、デッドロックは存在しなくなります。トランザクション B がリソース C の取得に失敗した場合を例にとると、トランザクション B が終了すれば、トランザクション A は対応するリソース D を取得できます。

• ステートメントタイムアウトメカニズム：構成パラメータ名は ob_query_timeout で、デフォルトは 10s です。ロック待機がステートメントのタイムアウト時間を超えた場合、対応するステートメントをロールバックし、ステートメントタイムアウトに対応するエラーコードを返します。この時点で、ある循環依存関係内のリソース依存が解消されるため、デッドロックは存在しなくなります。トランザクション B がリソース C の取得に失敗した場合を例にとると、トランザクション B が終了すれば、トランザクション A は対応するリソース D を取得できます。

• トランザクションタイムアウトメカニズム：構成パラメータ名は ob_trx_timeout で、デフォルトは 86400s です。ロック待機がトランザクションのタイムアウト時間を超えた場合、対応するトランザクションをロールバックし、ステートメント・トランザクションに対応するエラーコードを返します。ある循環依存関係内のリソース依存が解消されるため、デッドロックは存在しなくなります。トランザクション B がタイムアウトした場合を例にとると、トランザクション B が終了するため、トランザクション A は対応するリソース D を取得できます。

主動的なデッドロック検出

OceanBase データベース V3.2 以降では、上記のタイムアウトに基づくデッドロック解決メカニズムに加え、主動的なデッドロック検出メカニズムも実装されています。

現在、OceanBase データベースで実装されているデッドロック検出は、LCL（Lock Chain Length）デッドロック検出方式と呼ばれる、優先度に基づく多出度分散型デッドロック検出方式です。OceanBase データベースのデッドロック検出アルゴリズムは、誤って他のトランザクションを終了させたり、過剰に終了させたりすることがないよう保証します。

優先度に基づくとは、相互にデッドロックを形成している複数のトランザクションの中で、LCL デッドロック検出方式は常に優先度が最も低いトランザクションを終了させることでデッドロックを解除する傾向があることを指します。現在、デッドロック検出におけるトランザクションの優先度指標は主にトランザクションの開始時刻であり、遅くに開始されたトランザクションほど優先度が低くなります。

多出度とは、各トランザクションが同時に 1 つを超える他のトランザクションを待機できることを指します。

分散型デッドロック検出とは、デッドロック検出を行う各ノードが自身の依存情報のみを知っており、グローバルなロックマネージャーを必要とせずにノード間のデッドロックを検出できることを指します。

実装の原理

分散トランザクションは、実行効率を向上させるために通常、複数のパーティションのデータに同時にアクセスする必要があり、複数のロック競合イベントが同時に発生する可能性があります。この場合、デッドロック検出の効率を高めるために、あるトランザクションが複数のトランザクションから一方向に依存して待機している有向エッジを記述することができ、これを多重出力と呼びます。

一般的なデッドロック検出方式は、パスプッシュアルゴリズム（path-pushing algorithm）を採用していますが、このアルゴリズムは多重出力のシナリオで適用されると、多殺や誤殺の問題が多く発生します。LCLデッドロック検出方式は、特別に設計されたエッジ追跡アルゴリズム（edge-chasing algorithm）を採用しています。LCLデッドロック検出方式では、各ノードは深さ値とトークン値と呼ばれる2つの状態を維持します。多殺を防ぐために、ノードが維持するトークン値の数は1つを超えてはならず、トークン値間で比較が可能で、大きなトークン値が小さなトークン値を上書きすることができます。これにより、ループ内では最大トークン値を持つノードのみがデッドロックを検出できるため、多殺の問題を回避できます。

エッジ追跡アルゴリズムにおけるデッドロック検出の基本原理は、トークン値が自分自身から送信されて自分自身に戻ることができるというものです。しかし、多重出力のシナリオで単一トークン値設計を採用すると、デッドロックループ内で最大のトークン値がそのループ内のどのノードにも属さない場合が発生する可能性があります。この場合、デッドロックは検出されません。このシナリオは「環外汚染」と呼ばれます。そのため、LCLデッドロック検出方式は「パス深さ」という概念を導入しました。各ノードはパス深さ値を維持し、ループ内のノードのパス深さ値は時間の経過とともに無限に増加することができますが、ループ外でループ内のノードによって到達されないノードのパス深さ値には増加の上限があります。これにより、ノードは自分自身と同じかそれ以上のパス深さを持つノードからのみトークンを受け取ることが制約され、「環外汚染」を回避します。また、アルゴリズムの初期段階で既に発生した「環外汚染」を定期的にクリーンアップすることで、アルゴリズムが多重出力下で正しく動作することを保証します。

具体的な実装

トランザクションAが行ロックの取得に失敗した場合、トランザクションAは行ロックが解除されるのを待ちながら、行ロックを保持しているトランザクションBのIDを取得し、デッドロック検出ノードa（以下、Detector(a)と呼ぶ）を作成します。そして、Detector(a)にトランザクションBのDetector(b)への一方向依存関係を記録します。

各ノードは以下の状態を維持する必要があります：

Detectorノードが作成されると、2つのトークン状態が生成されます。1つは公開トークン値（public label）、もう1つはプライベートトークン値（private label）です。ノードは自身の優先順位に基づいてグローバルに一意のトークンを生成し（優先順位が高いノードほどトークン値が大きい）、それを使用して2つのトークン値を初期化します。同時に、初期値0の深さ値lclv ((Lock Chain Length)も生成されます。

各Detectorノードは依存リストを維持し、そのリストには依存する他のノードのネットワーク上の位置情報が記録されています。

時間軸で分類すると、1.4秒ごとに1つのLCLサイクルが区切られます。

各サイクルの開始時に、各ノードは自身のpublic labelを自身のprivate labelにリセットします。

LCLサイクルの最初の700msはLCLPサイクル（Lock Chain Length Proliferating）と呼ばれ、各ノードはこのサイクル中に定期的に自身の状態のlclv値を依存リスト内のすべてのダウンストリームノードに送信します。各ノードは、上位ノードから送信されたlclv値を受信すると、自身のlclv値をmax(lclv, received_lclv + 1)に更新します。

LCLサイクルの後半の700msはLCLSサイクル（Lock Chain Length Spreading）と呼ばれ、各ノードはこのサイクル中に定期的に自身の状態の{ lclv, public label }を依存リスト内のすべてのダウンストリームノードに送信します。各ノードは、上位ノードから送信された値を受信した後、自身のlclv値が現在のlclv値以上である場合、自身のpublic labelをmin(public label, received public label)に更新し、自身のlclv値をreceived lclvに更新します。

デッドロックの検出：ノードが受信したpublic labelが自身のprivate labelと一致した場合、デッドロックが検出されたことを意味します。

ビュー

ビューCDB_OB_deadLOCK_EVENT_HISTORYは、過去に発生したすべてのデッドロックイベントおよびこれらのイベントに参加したトランザクションを記録し、デッドロックイベントにおいて最終的にキルされたトランザクションを示します。