Distributed-dbms-controlling-concurrency

分散DBMS-同時実行性の制御

同時実行制御技術により、複数のトランザクションが同時に実行され、トランザクションのACIDプロパティとスケジュールのシリアル化が維持されます。

この章では、同時実行制御のさまざまなアプローチについて学習します。

ロックベースの同時実行制御プロトコル

ロックベースの同時実行制御プロトコルは、データ項目のロックの概念を使用します。 *ロック*は、データ項目に関連付けられた変数で、そのデータ項目で読み取り/書き込み操作を実行できるかどうかを決定します。 一般に、データ項目を同時に2つのトランザクションでロックできるかどうかを示すロック互換性マトリックスが使用されます。

ロックベースの同時実行制御システムは、1フェーズまたは2フェーズのロックプロトコルを使用できます。

単相ロッキングプロトコル

この方法では、各トランザクションは使用前にアイテムをロックし、使用が終了するとすぐにロックを解除します。 このロック方式は最大の同時実行性を提供しますが、常にシリアライズ可能性を強制するわけではありません。

二相ロッキングプロトコル

この方法では、すべてのロック操作が最初のロック解除またはロック解除操作に先行します。 トランザクションは2つのフェーズで構成されます。 最初のフェーズでは、トランザクションは必要なすべてのロックのみを取得し、ロックを解放しません。 これは、拡張フェーズまたは「成長フェーズ」と呼ばれます。 2番目のフェーズでは、トランザクションはロックを解除し、新しいロックを要求できません。 これは「収縮フェーズ」と呼ばれます。

2フェーズロックプロトコルに従うすべてのトランザクションは、シリアル化可能であることが保証されています。 ただし、このアプローチでは、2つの競合するトランザクション間の並列性が低くなります。

タイムスタンプ同時実行制御アルゴリズム

タイムスタンプベースの同時実行制御アルゴリズムは、トランザクションのタイムスタンプを使用して、データ項目への同時アクセスを調整し、シリアライズ可能性を確保します。 タイムスタンプは、トランザクションの開始時間を表すDBMSによってトランザクションに与えられる一意の識別子です。

これらのアルゴリズムにより、トランザクションはタイムスタンプで指定された順序でコミットされます。 古いトランザクションは若いトランザクションの前にシステムに入るため、古いトランザクションは若いトランザクションの前にコミットする必要があります。

タイムスタンプベースの同時実行制御技術は、シリアル化可能なスケジュールを生成し、同等のシリアルスケジュールが参加しているトランザクションの年齢順に並べられるようにします。

タイムスタンプベースの同時実行制御アルゴリズムのいくつかは-

• 基本的なタイムスタンプ順序付けアルゴリズム。
• 保守的なタイムスタンプ順序付けアルゴリズム。
• タイムスタンプの順序に基づくマルチバージョンアルゴリズム。

タイムスタンプベースの順序付けは、直列化可能性を強制するために3つの規則に従います-

• アクセスルール-2つのトランザクションが同じデータ項目に同時にアクセスしようとすると、競合する操作のために、古いトランザクションが優先されます。 これにより、若いトランザクションは古いトランザクションが最初にコミットされるのを待ちます。
• 遅延トランザクションルール-若いトランザクションがデータアイテムを書き込んだ場合、古いトランザクションはそのデータアイテムの読み取りまたは書き込みを許可されません。 このルールは、若いトランザクションが既にコミットした後に古いトランザクションがコミットするのを防ぎます。
• 若いトランザクションルール-若いトランザクションは、古いトランザクションによって既に書き込まれたデータ項目を読み書きできます。

楽観的同時実行制御アルゴリズム

競合率の低いシステムでは、すべてのトランザクションのシリアライズ可能性を検証するタスクによりパフォーマンスが低下する場合があります。 これらの場合、シリアライズ可能性のテストはコミットの直前に延期されます。 競合率が低いため、シリアル化できないトランザクションを中止する可能性も低くなります。 このアプローチは、楽観的同時実行制御技術と呼ばれます。

このアプローチでは、トランザクションのライフサイクルは次の3つのフェーズに分割されます-

• 実行フェーズ-トランザクションはデータ項目をメモリにフェッチし、それらに対して操作を実行します。
• 検証フェーズ-トランザクションは、データベースへの変更のコミットがシリアル化可能性テストに合格することを確認するチェックを実行します。
• コミットフェーズ-トランザクションは、メモリ内の変更されたデータ項目をディスクに書き戻します。

このアルゴリズムは、検証フェーズで直列化を強制するために3つのルールを使用します-

• ルール1 *-2つのトランザクションT〜i〜とT〜j〜が与えられ、T〜i〜がT〜j〜が書き込んでいるデータ項目を読み込んでいる場合、T〜i〜の実行フェーズはT〜と重複できませんj〜のコミットフェーズ。 T〜j〜は、T〜i〜の実行が終了した後にのみコミットできます。

• ルール2 *-2つのトランザクションT〜i〜およびT〜j〜が与えられ、T〜i〜がT〜j〜が読み取っているデータ項目を書き込んでいる場合、T〜i〜のコミットフェーズはT〜と重複できませんj〜の実行フェーズ。 T〜j〜は、T〜i〜がすでにコミットした後にのみ実行を開始できます。

• ルール3 *-2つのトランザクションT〜i〜およびT〜j〜が与えられた場合、T〜i〜がT〜j〜も書き込んでいるデータ項目を書き込んでいる場合、T〜i〜のコミットフェーズはTと重複できません〜j〜のコミットフェーズ。 T〜j〜は、T〜i〜がすでにコミットした後にのみコミットを開始できます。

分散システムでの同時実行制御

このセクションでは、上記の手法が分散データベースシステムにどのように実装されるかを説明します。

分散2フェーズロックアルゴリズム

分散型2フェーズロックの基本原理は、基本的な2フェーズロックプロトコルと同じです。 ただし、分散システムには、ロックマネージャーとして指定されたサイトがあります。 ロックマネージャは、トランザクションモニタからのロック取得要求を制御します。 さまざまなサイトのロックマネージャー間の調整を実施するために、少なくとも1つのサイトにすべてのトランザクションを表示し、ロックの競合を検出する権限が与えられます。

ロックの競合を検出できるサイトの数に応じて、分散型の2フェーズロックアプローチには3つのタイプがあります-

• 集中型2フェーズロック-このアプローチでは、1つのサイトが中央ロックマネージャーとして指定されます。 環境内のすべてのサイトは、セントラルロックマネージャーの場所を認識しており、トランザクション中にそこからロックを取得します。
• プライマリコピー2フェーズロック-このアプローチでは、多くのサイトがロックコントロールセンターとして指定されます。 これらの各サイトには、定義された一連のロックを管理する責任があります。 すべてのサイトは、どのロックコントロールセンターがどのデータテーブル/フラグメントアイテムのロックを管理する責任があるかを知っています。
• 分散2フェーズロック-このアプローチには、各ロックマネージャーがローカルサイトに格納されているデータ項目のロックを制御するロックマネージャーがいくつかあります。 ロックマネージャの場所は、データの配布と複製に基づいています。

分散型タイムスタンプの同時実行制御

中央集中型システムでは、トランザクションのタイムスタンプは物理的なクロック読み取り値によって決定されます。 ただし、分散システムでは、サイトのローカルな物理/論理クロックの読み取り値は、グローバルに一意ではないため、グローバルタイムスタンプとして使用できません。 そのため、タイムスタンプはサイトIDとそのサイトの時計の読み取り値の組み合わせで構成されます。

タイムスタンプ順序付けアルゴリズムを実装するために、各サイトには、トランザクションマネージャごとに個別のキューを維持するスケジューラがあります。 トランザクション中に、トランザクションマネージャーはロックリクエストをサイトのスケジューラーに送信します。 スケジューラは、タイムスタンプの昇順で、対応するキューに要求を配置します。 リクエストは、タイムスタンプの順にキューの先頭から処理されます。 最も古いものから。

競合グラフ

別の方法は、競合グラフを作成することです。 このトランザクションクラスが定義されています。 トランザクションクラスには、読み取りセットと書き込みセットと呼ばれる2つのデータ項目セットが含まれています。 トランザクションの読み取りセットがクラスの読み取りセットのサブセットであり、トランザクションの書き込みセットがクラスの書き込みセットのサブセットである場合、トランザクションは特定のクラスに属します。 読み取りフェーズでは、各トランザクションが読み取りセット内のデータ項目に対して読み取り要求を発行します。 書き込みフェーズでは、各トランザクションが書き込み要求を発行します。

アクティブなトランザクションが属するクラスの競合グラフが作成されます。 これには、垂直、水平、および斜めのエッジのセットが含まれます。 垂直エッジは、クラス内の2つのノードを接続し、クラス内の競合を示します。 水平エッジは、2つのクラスにわたって2つのノードを接続し、異なるクラス間の書き込みと書き込みの競合を示します。 対角線のエッジは、2つのクラスにまたがる2つのノードを接続し、2つのクラス間の書き込み/読み取りまたは読み取り/書き込みの競合を示します。

競合グラフを分析して、同じクラス内または2つの異なるクラス間で2つのトランザクションを並行して実行できるかどうかを確認します。

分散オプティミスティック同時実行制御アルゴリズム

分散型楽観的同時実行制御アルゴリズムは、楽観的同時実行制御アルゴリズムを拡張します。 この拡張機能には、2つのルールが適用されます-

• ルール1 *-このルールに従って、トランザクションは実行時にすべてのサイトでローカルに検証する必要があります。 トランザクションがいずれかのサイトで無効であることが判明した場合、トランザクションは中止されます。 ローカル検証により、トランザクションが実行されたサイトでのシリアル化が維持されることが保証されます。 トランザクションがローカル検証テストに合格すると、グローバルに検証されます。

• ルール2 *-このルールによると、トランザクションはローカル検証テストに合格した後、グローバルに検証される必要があります。 グローバル検証により、2つの競合するトランザクションが複数のサイトで同時に実行される場合、それらが一緒に実行されるすべてのサイトで同じ相対順序でコミットする必要があります。 これには、検証の後にコミットする前に、トランザクションが他の競合するトランザクションを待つ必要がある場合があります。 この要件により、トランザクションはサイトで検証されるとすぐにコミットできないため、アルゴリズムの楽観性が低下します。