Distributed-dbms-deadlock-handling

分散DBMS-デッドロック処理

この章では、データベースシステムのデッドロック処理メカニズムの概要を説明します。 集中型データベースシステムと分散型データベースシステムの両方で、デッドロック処理メカニズムを調査します。

デッドロックとは何ですか？

デッドロックは、各トランザクションが他のトランザクションによってロックされているデータ項目を待機しているときに、2つ以上のトランザクションを持つデータベースシステムの状態です。 デッドロックは、グラフ待機のサイクルで示されます。 これは、頂点がトランザクションを示し、エッジがデータ項目の待機を示す有向グラフです。

たとえば、次のグラフ待機では、トランザクションT1は、T3によってロックされているデータ項目Xを待機しています。 T3はT2によってロックされているYを待機しており、T2はT1によってロックされているZを待機しています。 したがって、待機サイクルが形成され、どのトランザクションも実行を続行できません。

Wait-For-Graph

集中システムでのデッドロック処理

デッドロック処理には3つの古典的なアプローチがあります。

• デッドロック防止。
• デッドロック回避。
• デッドロックの検出と削除。

3つのアプローチはすべて、集中データベースシステムと分散データベースシステムの両方に組み込むことができます。

デッドロック防止

デッドロック防止アプローチでは、どのトランザクションもデッドロックにつながるロックを取得できません。 規則では、複数のトランザクションが同じデータ項目のロックを要求すると、そのうちの1つだけがロックを許可されます。

最も一般的なデッドロック防止方法の1つは、すべてのロックの事前取得です。 この方法では、トランザクションは実行を開始する前にすべてのロックを取得し、トランザクションの期間全体にわたってロックを保持します。 別のトランザクションがすでに取得したロックのいずれかを必要とする場合、必要なすべてのロックが使用可能になるまで待機する必要があります。 このアプローチを使用すると、待機中のトランザクションのいずれもロックを保持していないため、システムのデッドロックが防止されます。

デッドロック回避

デッドロック回避アプローチは、デッドロックが発生する前に処理します。 トランザクションとロックを分析して、待機がデッドロックにつながるかどうかを判断します。

この方法は、次のように簡単に説明できます。 トランザクションは実行を開始し、ロックする必要があるデータ項目を要求します。 ロックマネージャは、ロックが使用可能かどうかを確認します。 使用可能な場合、ロックマネージャーはデータ項目を割り当て、トランザクションはロックを取得します。 ただし、互換性のないモードの他のトランザクションによってアイテムがロックされている場合、ロックマネージャーはアルゴリズムを実行して、トランザクションを待機状態にするとデッドロックが発生するかどうかをテストします。 したがって、アルゴリズムは、トランザクションを待機できるか、トランザクションの1つを中止する必要があるかを決定します。

この目的には、 wait-die と wound-wait の2つのアルゴリズムがあります。 T1とT2の2つのトランザクションがあり、T1がすでにT2によってロックされているデータ項目をロックしようとすると仮定します。 アルゴリズムは次のとおりです-

• Wait-Die -T1がT2よりも古い場合、T1は待機できます。 それ以外の場合、T1がT2よりも若い場合、T1は中止され、後で再起動されます。
• Wound-Wait -T1がT2よりも古い場合、T2は中止され、後で再起動されます。 それ以外の場合、T1がT2よりも若い場合、T1は待機できます。

デッドロックの検出と削除

デッドロックの検出と削除のアプローチは、デッドロック検出アルゴリズムを定期的に実行し、デッドロックが発生した場合にデッドロックを削除します。 トランザクションがロックの要求を出すとき、デッドロックをチェックしません。 トランザクションがロックを要求すると、ロックマネージャはそれが利用可能かどうかを確認します。 使用可能な場合、トランザクションはデータ項目をロックできます。それ以外の場合、トランザクションは待機できます。

ロック要求を許可している間は予防策がないため、一部のトランザクションはデッドロックされる可能性があります。 デッドロックを検出するために、ロックマネージャーはwait-forgraphにサイクルがあるかどうかを定期的にチェックします。 システムがデッドロック状態の場合、ロックマネージャーは各サイクルから被害者のトランザクションを選択します。 犠牲者は中止され、ロールバックされます。後で再起動します。 被害者の選択に使用される方法のいくつかは-

• 最も若いトランザクションを選択します。
• データ項目が最も少ないトランザクションを選択します。
• 更新の回数が最も少ないトランザクションを選択します。
• 再起動のオーバーヘッドが最も少ないトランザクションを選択します。
• 2つ以上のサイクルに共通するトランザクションを選択します。

このアプローチは、トランザクションが少なく、ロック要求への高速応答が必要なシステムに主に適しています。

分散システムでのデッドロック処理

分散データベースシステムでのトランザクション処理も分散されています。 同じトランザクションが複数のサイトで処理されている可能性があります。 集中型システムには存在しない分散データベースシステムの2つの主なデッドロック処理の懸念は、*トランザクションの場所*と*トランザクション制御*です。 これらの懸念に対処すると、デッドロックは、デッドロック防止、デッドロック回避、またはデッドロックの検出と削除のいずれかによって処理されます。

取引場所

分散データベースシステムのトランザクションは複数のサイトで処理され、複数のサイトのデータ項目を使用します。 データ処理の量は、これらのサイト間で均一に分散されていません。 処理の期間も異なります。 したがって、同じトランザクションが一部のサイトでアクティブになり、他のサイトでは非アクティブになる場合があります。 2つの競合するトランザクションがサイトにある場合、そのうちの1つが非アクティブな状態になることがあります。 この状態は、集中システムでは発生しません。 この懸念は、トランザクションロケーションの問題と呼ばれます。

この懸念は、デイジーチェーンモデルで対処できます。 このモデルでは、トランザクションは、あるサイトから別のサイトに移動するときに特定の詳細を運びます。 詳細の一部は、必要なテーブルのリスト、必要なサイトのリスト、訪問したテーブルとサイトのリスト、まだ訪問していないテーブルとサイトのリスト、および取得したロックとタイプのリストです。 トランザクションがコミットまたはアボートによって終了した後、情報は関係するすべてのサイトに送信される必要があります。

トランザクション制御

トランザクション制御は、分散データベースシステムでトランザクションを処理するために必要なサイトの指定と制御に関係しています。 次のように、トランザクションを処理する場所の選択と制御の中心を指定する方法に関する多くのオプションがあります-

• 1つのサーバーを制御の中心として選択できます。
• 制御の中心は、あるサーバーから別のサーバーに移動できます。
• 制御の責任は、複数のサーバーで共有できます。

分散デッドロック防止

集中型デッドロック防止と同様に、分散デッドロック防止アプローチでは、トランザクションは実行を開始する前にすべてのロックを取得する必要があります。 これにより、デッドロックが防止されます。

トランザクションが入るサイトは、制御サイトとして指定されます。 制御サイトは、データアイテムが存在するサイトにメッセージを送信して、アイテムをロックします。 その後、確認を待ちます。 すべてのサイトがデータ項目をロックしたことを確認すると、トランザクションが開始されます。 サイトまたは通信リンクに障害が発生した場合、トランザクションは修復されるまで待機する必要があります。

実装は簡単ですが、このアプローチにはいくつかの欠点があります-

• ロックの事前取得には、通信遅延のために長い時間が必要です。 これにより、トランザクションに必要な時間が長くなります。
• サイトまたはリンクに障害が発生した場合、トランザクションはサイトが回復するまで長時間待機する必要があります。 一方、実行中のサイトでは、アイテムはロックされています。 これにより、他のトランザクションの実行が妨げられる場合があります。
• 制御サイトに障害が発生すると、他のサイトと通信できなくなります。 これらのサイトは、ロックされたデータ項目をロックされた状態に維持し続けるため、結果としてブロックされます。

分散デッドロック回避

集中システムの場合と同様に、分散デッドロック回避は、発生する前にデッドロックを処理します。 さらに、分散システムでは、トランザクションの場所とトランザクション制御の問題に対処する必要があります。 トランザクションの分散性により、次の競合が発生する場合があります-

• 同じサイト内の2つのトランザクション間の競合。
• 異なるサイトの2つのトランザクション間の競合。

競合が発生した場合、分散待機ダイまたは分散創傷待機アルゴリズムに従って、トランザクションの1つが中止されるか、待機が許可される場合があります。

T1とT2の2つのトランザクションがあると仮定します。 T1はサイトPに到着し、そのサイトでT2によってすでにロックされているデータ項目をロックしようとします。 したがって、サイトPで競合が発生しています。 アルゴリズムは次のとおりです-

• 分散創傷ダイ
• T1がT2よりも古い場合、T1は待機できます。 T1は、T2がすべてのサイトで正常にコミットまたはアボートしたというメッセージをサイトPが受信した後、実行を再開できます。
• T1がT2よりも若い場合、T1は中止されます。 サイトPの同時実行制御は、T1を中止するためにT1が訪問したすべてのサイトにメッセージを送信します。 T1がすべてのサイトで正常に中止された場合、制御サイトはユーザーに通知します。
• 分散待機待機
• T1がT2より古い場合、T2を中止する必要があります。 T2がサイトPでアクティブな場合、サイトPは中断し、T2をロールバックしてから、このメッセージを他の関連サイトにブロードキャストします。 T2がサイトPを離れたがサイトQでアクティブな場合、サイトPはT2が中止されたことをブロードキャストします。次に、サイトLはT2を中止してロールバックし、このメッセージをすべてのサイトに送信します。
• T1がT1よりも若い場合、T1は待機できます。 T2が処理を完了したというメッセージをサイトPが受信した後、T1は実行を再開できます。

分散デッドロック検出

集中化されたデッドロック検出アプローチと同様に、デッドロックは発生が許可され、検出されると削除されます。 トランザクションがロック要求を出すとき、システムはチェックを実行しません。 実装のために、グローバルなグラフ待機が作成されます。 グローバルなグラフ待ちのサイクルの存在は、デッドロックを示します。 ただし、トランザクションはネットワーク全体でリソースを待機するため、デッドロックを見つけることは困難です。

あるいは、デッドロック検出アルゴリズムはタイマーを使用できます。 各トランザクションは、トランザクションが終了すると予想される期間に設定されるタイマーに関連付けられます。 トランザクションがこの時間内に終了しない場合、タイマーはオフになり、デッドロックの可能性があることを示します。

デッドロック処理に使用される別のツールは、デッドロック検出器です。 集中システムでは、1つのデッドロック検出器があります。 分散システムでは、複数のデッドロック検出器が存在する場合があります。 デッドロック検出器は、その制御下にあるサイトのデッドロックを見つけることができます。 つまり、分散システムでのデッドロック検出には3つの選択肢があります。

• 集中型デッドロック検出器-1つのサイトが中央デッドロック検出器として指定されています。
• 階層的デッドロック検出器-多数のデッドロック検出器が階層的に配置されています。
• Distributed Deadlock Detector -すべてのサイトがデッドロックの検出と削除に参加しています。