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

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

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

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

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

一元化されたシステムでのデッドロック処理

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

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

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

デッドロック防止

デッドロック防止アプローチでは、デッドロックにつながるロックをトランザクションが取得することはできません。慣例では、複数のトランザクションが同じデータアイテムのロックを要求すると、そのうちの1つだけにロックが付与されます。

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

デッドロックの回避

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

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

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

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

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

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

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

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

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

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

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

トランザクションの場所

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

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

トランザクション制御

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

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

分散デッドロック防止

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

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

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

ロックの事前取得には、通信の遅延に長い時間がかかります。これにより、トランザクションに必要な時間が長くなります。
サイトまたはリンクに障害が発生した場合、サイトが回復するためにトランザクションは長時間待機する必要があります。その間、実行中のサイトでは、アイテムはロックされています。これにより、他のトランザクションが実行されなくなる可能性があります。
制御サイトに障害が発生すると、他のサイトと通信できなくなります。これらのサイトは、ロックされたデータアイテムを引き続きロックされた状態に保つため、ブロックされます。

分散デッドロックの回避

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

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

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

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

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

分散デッドロック検出

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

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

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

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