ロックメカニズム

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は、発生したすべてのデッドロックイベントおよびそれらのイベントに関与したトランザクションを記録しており、デッドロックイベントにおいて最終的にキルされたトランザクションも示しています。