Implementation and Acquisition Mechanism of MDL Lock

背景

MySQL は、同時実行リクエスト下でのデータベースのトランザクション分離性および整合性の要件を満たし、複数の MySQL プラグインストレージエンジンに対応するため、Server レイヤーで Metadata Locking（MDL）機構を実装しています。その効果として、たとえば、あるトランザクションがデータベースの特定のリソースにアクセスしている際、他の同時実行トランザクションによるそのリソースの削除を制限します。これは論理的な意味でのロックです。オペレーティングシステムカーネルが提供する限定的なタイプのミューテックスとは異なり、MDL はロック対象、ロックタイプ、および異なるロックタイプの優先度を柔軟にカスタマイズできます。異なるロックタイプの互換性を動的に調整することで、データベースによる各種クエリリクエストの適切な同時実行制御を大きく促進します。

本稿では、MDL システムでよく使用されるデータ構造とその意味について紹介し、実装の観点から MDL の獲得機構とデッドロック検出について議論し、最後に実運用における MDL 状態の監視方法について共有します。

二つの基本概念

1 MDL_key

MDL オブジェクトはキーと値のペア（キーバリュー）の形式で記述され、各キー値はロック対象を一意に表します（値はデータベースの特定のリソースを表します）。キーは MDL_key で表現され、オブジェクトの名前を文字列の形式で表します。

完全な文字列は名前空間、階層構造の各レベルの名前で構成され、複数の名前空間により同じ名前を持つ異なるタイプのオブジェクトを区別できます。名前空間は、データベース内で作成可能な異なるオブジェクトタイプである GLOBAL、SCHEMA、TABLE、FUNCTION、PROCEDURE などから構成されます。

タイプに応じて、オブジェクトの名前は複数の階層で構成される場合があります。たとえば、テーブルオブジェクトはデータベース名とテーブル名で一意に記述されます。SCHEMA オブジェクトの場合は、データベース名の 1 レベルのみです。名前は文字列終端子で区切られます。したがって、これらの部分で構成される文字列をキーとして使用し、データベース内の特定のオブジェクトを一意に表すことができます。

2 enum_mdl_type

同じデータベースオブジェクトに対して、異なるクエリは異なるアクセスモードを持ちます。たとえば、SELECT 文はオブジェクトの内容を読み取ろうとし、INSERT / UPDATE 文はオブジェクトの内容を変更しようとし、DDL 文はオブジェクトの構造と定義を変更しようとします。これらの文はオブジェクトに異なる影響を与え、同時実行分離に対する要件も異なるため、MySQL は異なるタイプの MDL とその互換性を定義して、これらの文の同時アクセスを制御しています。

異なるタイプの MDL の互換性

MySQL はロックタイプを範囲ロックとオブジェクトロックに分類します。

1) 範囲ロック

範囲ロックのタイプは比較的少なく（IX、S、X）、主に GLOBAL、COMMIT、TABLESPACE、BACKUP_LOCK、SCHEMA 名前空間のオブジェクトに使用されます。これらのタイプの互換性はシンプルで、主に全体としての同時実行操作を制限することを目的としています。たとえば、グローバル読み取りロックはトランザクションのコミットをブロックし、DDL は SCHEMA レベルの意図排他ロック（IX）を要求することで SCHEMA レベルの変更操作をブロックします。

これらのタイプの MDL 互換性関係は 2 つのマトリックスで定義されます。同じオブジェクトに対して、1 つは獲得済み MDL タイプと新規要求タイプの互換性、もう 1 つは待機中の MDL 要求タイプと未獲得の新規要求タイプの互換性です。IS（INTENTION_SHARE）はすべてのケースで他のロックと互換性があるため、MDL システムでは無視できます。

2) オブジェクトロック

オブジェクトロックは豊富な MDL タイプを含み、データベースの基本的なオブジェクトの大部分に適用されます。その互換性マトリックスは以下の通りです。

MDL の獲得プロセスにおいて、これら 2 つの互換性マトリックスを通じて、許可済み/待機状態の MDL が要求された MDL と互換性がないかを判断し、要求を満たせるかどうかを決定します。満たせない場合は待機状態に入ります。

MDL システムは互換性マトリックスを通じてロックタイプの強度も判断します。以下に示します。

表現の仕方が少し回りくどいです。あるタイプ type が m_type タイプと互換性のある MDL と互換性がない場合、type タイプの方が強いと理解できます。そうでない場合、m_type タイプは同等かそれ以上です。つまり、弱いタイプは互換性のない MDL タイプであり、強い MDL は互換性がないということです。

三つの重要なデータ構造

1 関係図

2 MDL_request
文の MDL に対する要求を表し、MDL_key、enum_mdl_type、enum_mdl_duration で構成されます。MDL_key と enum_mdl_type が MDL オブジェクトとロックタイプを決定します。

enum_mdl_duration には 3 種類あり、MDL の保持期間を表します。単一文レベル期間、トランザクションレベル期間、明示的期間があります。

MDL_request のライフサイクルは MDL システムの外部にあり、ユーザーによって制御され、一時的な変数となり得ます。ただし、この要求を通じて獲得された MDL のライフサイクルは永続的で、MDL システムによって制御され、MDL_request の破棄とともに解放されることはありません。

3 MDL_lock

データベース内のオブジェクトに対して、その名前（MDL_key）に対応する単一のロックオブジェクト MDL_lock が存在します。データベースオブジェクトへの初回アクセス時に、ロックフリーの HASH によってメモリ内に MDL_lock が作成・管理されます。以降のアクセスでは、同じオブジェクトへのアクセスは同じ MDL_lock を参照します。

MDL_lock 内には、現在ロックオブジェクトの待機中キュー m_waiting と、オブジェクトに許可済みのキュー m_granted の両方が存在します。キュー内の要素は MDL_ticket で表現されます。

静的ビットマップオブジェクトで構成される MDL_lock_strategy は、前述の範囲ロックとオブジェクトロックの互換性マトリックスを格納するために使用され、MDL_lock の名前空間に基づいてロックの互換性を取得できます。

4 MDL_ticket

MDL_lock と enum_mdl_type が MDL_ticket を形成し、現在のスレッドのデータベースオブジェクトへのアクセス権を表します。MDL_ticket は各クエリが MDL ロックを要求する際に作成され、MDL システムによってメモリが割り当てられ、トランザクション終了時に破棄されます。

MDL_ticket には 2 組のポインターが含まれ、それぞれそのスレッドが獲得したすべてのチケットと、そのチケットが関与するロックオブジェクトの待機状態または許可状態のチケットを連結します。

5 MDL_context
スレッドが MDL ロックを獲得するためのコンテキストで、各接続に 1 つずつ存在し、その接続が獲得したすべての MDL_ticket を含みます。これらは異なるライフサイクルに応じてそれぞれの連結リストに格納され、MDL_ticket_store によって管理されます。

接続が獲得するすべてのロックはライフサイクルに基づいて 3 種類に分類できます。文レベル、トランザクションレベル、および明示的ロックです。文レベルとトランザクションレベルのロックは自動的なライフサイクルとスコープを持ち、トランザクション中に累積されます。文レベルロックは最も外側の文終了後に自動解放され、トランザクションレベルロックは COMMIT、ROLLBACK、ROLLBACK TO SAVEPOINT の後に解放され、手動では解放されません。明示的ライフサイクルを持つチケットは、トランザクションとチェックポイントをまたぐロック用に獲得され、HANDLER SQL ロック、LOCK TABLES ロック、ユーザーレベルロック GET_LOCK() / RELEASE_LOCK() が含まれます。文レベルとトランザクションレベルのロックは時系列の逆順で対応する連結リストの先頭に追加されます。あるチェックポイントまでロールバックする際、対応するチケットは連結リストの先頭からスタック方式で解放され、チェックポイント作成前に最後に獲得されたチケットまで続きます。

スレッドが MDL ロックを獲得しようとする際、まず自身の MDL_ticket_store 内で、トランザクション内に同じロックオブジェクトに対して既に強いタイプの MDL_ticket を獲得しているか確認します。したがって、MDL_ticket_store は MDL_request に基づいて MDL_ticket を検索するインターフェースを提供します。1 つは異なるライフサイクルの MDL_ticket 連結リスト内を検索することです。現在のスレッドが獲得した MDL_ticket の数がしきい値（デフォルト 256）を超えると、すべての MDL_ticket が追加的に管理されます。

四 MDL の獲得プロセス

DML や DDL の第 1 段階を含むほぼすべてのクエリ文は、解析段階にあります。LEX と YACC が文のタイプに応じてアクセス対象テーブルの MDL ロック要求を初期化します。たとえば、SELECT 文は SR、INSERT 文は SW、ALTER TABLE 文は SU です。このプロセスは以下の呼び出しスタックにあります。

文の実行前に、open_tables_for_query 関数を通じてアクセスが必要なすべてのテーブルが開かれ、TABLE テーブルオブジェクトが獲得されます。このプロセスでは、まず MDL ロックが獲得され、その後にテーブルリソースが獲得されます。これにより、同じテーブルのメタ情報への同時読み書きを防止します。MDL ロックの要求はすべて、現在のスレッドのコンテキスト MDL_context から MDL_context::acquire_lock を呼び出すことで行われます。呼び出しスタックは以下の通りです。

次に、MDL_context::try_acquire_lock_impl のプロセスに注目します。この関数はさまざまなタイプのロック獲得（互換性の高いもの、低いもの）とロック競合検出を含みます。入力パラメーターは現在の MDL_request で、出力パラメーターは獲得された MDL_ticket です。

まず MDL_request に基づいて、現在のスレッドが既に保持している同じオブジェクトの MDL_ticket の中から、より強いタイプで同じまたは異なるライフサイクルのチケットを検索します。同じライフサイクルのチケットが既に存在する場合はそのまま返します。異なるライフサイクルの場合は、そのライフサイクルのチケットをクローンして返します。

前述の通り、ロックタイプの互換性に基づいて、非介入ロックと介入ロックに分類できます。ロック獲得プロセスにおいては、それぞれファストパスとスローパスに対応し、獲得の難しさが異なります。

一部の弱いタイプの MDL 要求（非介入、SR / SW など）については、この部分の要求が大多数を占め、互換性も良いため、獲得後に具体的な MDL_ticket を記録する必要はなく、獲得数だけを記録すればよいです。そのため、MDL_lock 内で整数の原子変数 std::atomic m_fast_path_state を使用して、そのロックが許可したすべての非介入ロックタイプの数をカウントします。各非介入ロックは異なる数値表現を持ち、固定ビット範囲を確保してこのロックタイプの累積値を格納します。最終的な結果は、long long 型を使用して許可されたすべての非介入ロックの数をカウントするのと同等であり、同時に CAS を通じてロックフリーで修正できます。さらに、m_fast_path_state の上位ビットには、IS_DESTROYED / HAS_OBTRUSIVE / HAS_SLOW_PATH の 3 つの状態表示ビットがあります。

MDL_request の要求タイプに基づいて、対応するタイプの非介入整数増分値を取得します。増分値が 0 の場合は介入ロックであることを意味し、スローパスを経由する必要があります。

0 でない場合は非介入ロックであることを意味し、ファストパスを経由して、MDL_lock::m_fast_path_state に対応する整数値を CAS で直接加算できます。ただし、1 つの条件を確認する必要があります。それは、そのオブジェクトが他のスレッドによって介入的にロックされていないことです。一部の非介入ロックと介入ロックは相互排他であり、介入ロックが存在しない場合にのみ他の非介入ロックが互いに互換性があるため、他のスレッドのロック保持状態を判断する必要なく直接獲得できます。

CAS 完了後、関連するデータ構造の状態と参照を設定し、現在の MDL_ticket をスレッドの MDL_ticket_store に追加して返します。

一部の比較的強いタイプの MDL 要求（介入、SU / SRO / X など）については、対応する MDL_ticket が MDL_lock の m_granted 連結リストに格納されます。したがって、この連結リストとその他のビットマップを走査して、他のスレッドが獲得または待機中の MDL_ticket との間にロック競合が存在するかどうかを判断する必要があります。

スローパスでロックを獲得する前に、現在のスレッドはファストパスで獲得したロックを MDL_lock::m_fast_path_state から実体化し、ビットマップから削除して MDL_lock::m_granted に追加する必要があります。MDL_lock::m_fast_path_state に含まれるビットマップはスレッドを区別できず、現在のスレッド自身が獲得した複数のロックはロック競合を構成しないため、ビットマップを通じて判断する前に、MDL_lock::m_fast_path_state のチケットがすべて他のスレッドに属していることを確認する必要があります。

実体化完了後、現在の要求は、待機中のチケットタイプ（m_waiting）、許可済みチケットタイプ（m_granted）、および非介入ロックタイプ状態（MDL_lock::m_fast_path_state）と前述の互換性マトリックスを組み合わせて、ロックタイプが獲得可能かどうかを判断できます。このプロセスは主に MDL_lock::can_grant_lock にあります。

m_waiting と m_granted には、チケットを連結する連結リストに加え、ビットマップを使用して連結リスト内のすべてのチケットのタイプを集め、直接比較できるようにしています。m_granted で互換性のないタイプが見つかった後、連結リストを走査して、その互換性のないタイプのチケットが現在のスレッドによって獲得されたものかどうかを判断する必要があります。現在のスレッド以外のスレッドによって獲得された場合にのみロック競合が発生します。非介入ロックが獲得可能な場合は、直接 MDL_lock::m_granted リストに追加されます。

2 ロック待機と通知

上記のプロセスで、MDL_ticket が正常に取得できれば MDL の獲得が完了し、クエリプロセスを続行できます。取得できない場合（非介入ロックが介入ロックのためにスローパスを強制された場合でも、介入ロック自体が取得できない場合でも）、ロック待機に入る必要があります。ロック待機のプロセスでは非介入か介入かを区別せず、一元的に処理されます。

各スレッドの MDL_context には MDL_wait メンバーが含まれています。ロック待機とデッドロック検出はスレッド単位のオブジェクトであり、対応する要求された MDL_ticket をロックの待機キューに追加することで通知登録が行われます。mutex、条件変数、列挙状態からなる一組のスレッド間の待機と通知を実現する仕組みがあります。5 つの待機状態があります。

WS_EMPTY が初期状態で、その他は待機の結果状態です。コマンドから分かるように、待機結果は以下のようになります。

GRANTED：スレッドが待機中の MDL ロックを獲得した
VICTIM：スレッドがデッドロックの犠牲者となり、トランザクションの再実行が必要
TIMEOUT：待機タイムアウト
KILLED：待機中にスレッドが強制終了された
待機スレッドはまず獲得しようとするチケットを MDL_lock の m_waiting キューに追加し、設定された待機時間に応じて MDL_wait の関数を呼び出してタイムアウト待機を行います。

互換性のないタイプロックを保持する他のスレッドがクエリを完了するかトランザクションが終了すると、保持していたすべてのロックが一斉に解放されます。同時に、ファストパスで獲得されたかスローパスで獲得されたかに応じて、MDL_lock::m_fast_path_state と MDL_lock::m_granted 連結リストの状態が復元されます。さらに、MDL_lock::m_waiting に待機中のチケットがある場合、MDL_lock::reschedule_waiters() を呼び出してロックを獲得できるスレッドを起動し、待機状態を GRANTED に設定します。

起動された待機スレッドがチケットの状態を GRANTED だと判断した場合、実行を継続します。そうでない場合は、状況に応じてエラーを報告します。

3 デッドロック検出
各スレッドがロック待機に入る前に、デッドロック検出を実行して、現在のスレッドがデッドロックに陥ることを防止します。デッドロック検出の前に、まず現在のスレッドが獲得した非介入ロックを実体化し、これらのロックが MDL_lock::m_granted リストに表示されるようにすることで、デッドロック検出が検出可能にします。そして現在のスレッドの待機ロック MDL_context::m_waiting_for を現在のチケットとして設定します。待機に入る各スレッドが待機オブジェクトを設定し、この待機チェーンに沿ってデッドロックを検出できます。

待機グラフのエッジを表す抽象クラスがあり、デッドロック検出アルゴリズムによって走査されます。MDL_ticket は MDL_wait_for_subgraph から派生しており、accept_visitor() 関数を実装することで、補助検出クラスがエッジに沿って待機リングを探すことができます。

待機グラフ内の待機リングを検出するための補助クラスで、検出プロセス中の状態情報を含みます。たとえば、デッドロック検出の開始スレッド m_start_node、検索プロセス中にデッドロックが発生した後、重みに基づいて選択された犠牲スレッド m_victim、検索スレッドの深さなどです。スレッドの待機チェーンが長すぎてしきい値（デフォルト 32）を超えた場合、デッドロックが検出されなくてもデッドロックとして扱われます。

検出プロセス

デッドロック検出の考え方は以下の通りです。まず、幅優先で、現在のスレッドが待機しているロックから開始して、MDL_lock の待機キューと許可キューを走査し、現在のスレッドによって獲得されておらず、待機中のロックと互換性のないロックが存在するか確認します。保持スレッドがアルゴリズム走査の開始スレッドと一致する場合、ロック待機チェーンにデッドロックが存在します。次に、深さ優先で、互換性のないロックの保持スレッドまたは待機スレッドから開始して、そのスレッドも待機状態にある場合、上記のプロセスを再帰的に繰り返し、開始点のスレッドを待機しているスレッドが見つかるまで探索します。見つからない場合はデッドロックなしと判定します。コードロジックは以下の通りです。

犠牲者の重み

デッドロック検出後、スレッド待機チェーンに沿って退出する際に、各スレッドの待機チケットの重みに基づいて最小重みの犠牲者を選択し、待機を放棄させ、保持しているロックを解放させます。Deadlock_detection_visitor::opt_change_victim_to 関数です。

重みは依然として比較的粗く、トランザクションの段階や実行された文の内容に関係なく、ロックリソースのタイプとロックタイプに従って事前に設定された重みが適用されます。MDL_ticket::get_deadlock_weight() 関数に定義されています。

デッドロック発生時、DML 文にエラーを発生させてロールバックし、DDL 文を継続実行する傾向があることが分かります。同じタイプの文がデッドロックを形成した場合、待機チェーンに後から入ったスレッドを犠牲者にして、長く待機しているスレッドを待機継続させる傾向があります。

現在のスレッドがデッドロックリング上の犠牲スレッドの状態を VICTIM に設定して起動した後、現在のスレッドは待機状態に入ることができます。

五 MDL の監視
MySQL の performance_schema を通じて、現在の MDL ロックの獲得状況を明確に監視できます。performance_schema は読み取り専用変数で、設定には再起動が必要です。設定ファイルに追加します。

六 PolarDB の MDL に関する最適化
MySQL Community Edition では、パーティションテーブルデータのアクセス操作（DML）とパーティションメンテナンス操作（DDL）が相互にブロックされます。主な原因は、DDL がパーティションテーブルの MDL_EXCLUSIVE ロックを獲得する必要があることです。これにより、パーティションメンテナンス操作はビジネスのオフピーク時にしか実行できず、パーティションテーブルに対するパーティションの作成/削除の必要性は比較的高頻度であるため、パーティションテーブルの利用が大幅に制限されます。

PolarDB では、パーティションレベルの MDL ロックを導入し、DML と DDL が獲得するロックの粒度をパーティションレベルまで低減し、同時実行性を向上させ、「オンライン」のパーティションメンテナンス機能を実現しました。パーティションテーブルのデータアクセスとパーティションメンテナンスは互いに影響せず、ユーザーはパーティションテーブルの業務フローに影響を与えることなく、より自由にパーティションメンテナンスを実行でき、パーティションテーブルの利用の柔軟性が大幅に向上しました。