分散DBMS-並行性の制御
同時実行制御技術により、トランザクションのACIDプロパティとスケジュールの直列化可能性を維持しながら、複数のトランザクションが同時に実行されます。
この章では、並行性制御のさまざまなアプローチについて学習します。
ロックベースの同時実行制御プロトコル
ロックベースの同時実行制御プロトコルは、データ項目をロックするという概念を使用します。Alockデータ項目に関連付けられた変数であり、そのデータ項目に対して読み取り/書き込み操作を実行できるかどうかを決定します。一般に、データ項目を2つのトランザクションで同時にロックできるかどうかを示すロック互換性マトリックスが使用されます。
ロックベースの同時実行制御システムは、1フェーズまたは2フェーズのロックプロトコルを使用できます。
単相ロックプロトコル
この方法では、各トランザクションは使用前にアイテムをロックし、使用が終了するとすぐにロックを解除します。このロック方法は最大の同時実行性を提供しますが、常に直列化可能性を強制するわけではありません。
二相ロックプロトコル
この方法では、すべてのロック操作が最初のロック解除またはロック解除操作の前に行われます。トランザクションは2つのフェーズで構成されます。最初のフェーズでは、トランザクションは必要なすべてのロックのみを取得し、ロックを解放しません。これは、拡張またはgrowing phase。2番目のフェーズでは、トランザクションはロックを解放し、新しいロックを要求できません。これは、shrinking phase。
2フェーズロックプロトコルに従うすべてのトランザクションは、シリアル化可能であることが保証されています。ただし、このアプローチでは、競合する2つのトランザクション間の並列処理が低くなります。
タイムスタンプ同時実行制御アルゴリズム
タイムスタンプベースの同時実行制御アルゴリズムは、トランザクションのタイムスタンプを使用してデータ項目への同時アクセスを調整し、直列化可能性を確保します。タイムスタンプは、トランザクションの開始時刻を表す、DBMSによってトランザクションに与えられる一意の識別子です。
これらのアルゴリズムにより、トランザクションはタイムスタンプで指定された順序でコミットされます。古いトランザクションは若いトランザクションの前にシステムに入るので、古いトランザクションは若いトランザクションの前にコミットする必要があります。
タイムスタンプベースの同時実行制御技術は、同等のシリアルスケジュールが参加トランザクションの経過時間の順に並べられるように、シリアル化可能なスケジュールを生成します。
タイムスタンプベースの同時実行制御アルゴリズムのいくつかは次のとおりです。
- 基本的なタイムスタンプの並べ替えアルゴリズム。
- 保守的なタイムスタンプの並べ替えアルゴリズム。
- タイムスタンプの順序に基づくマルチバージョンアルゴリズム。
タイムスタンプベースの順序付けは、直列化可能性を適用するために3つのルールに従います-
Access Rule− 2つのトランザクションが同じデータ項目に同時にアクセスしようとすると、操作が競合するため、古いトランザクションが優先されます。これにより、若いトランザクションは古いトランザクションが最初にコミットするのを待ちます。
Late Transaction Rule−若いトランザクションがデータ項目を書き込んだ場合、古いトランザクションはそのデータ項目の読み取りまたは書き込みを許可されません。このルールは、若いトランザクションがすでにコミットされた後、古いトランザクションがコミットされないようにします。
Younger Transaction Rule −若いトランザクションは、古いトランザクションによってすでに書き込まれているデータ項目を読み書きできます。
楽観的同時実行制御アルゴリズム
競合率が低いシステムでは、すべてのトランザクションの直列化可能性を検証するタスクによってパフォーマンスが低下する可能性があります。このような場合、直列化可能性のテストはコミット直前に延期されます。競合率が低いため、シリアル化できないトランザクションを中止する可能性も低くなります。このアプローチは、楽観的同時実行制御手法と呼ばれます。
このアプローチでは、トランザクションのライフサイクルは次の3つのフェーズに分けられます-
Execution Phase −トランザクションはデータ項目をメモリにフェッチし、それらに対して操作を実行します。
Validation Phase −トランザクションは、データベースへの変更のコミットが直列化可能性テストに合格することを確認するためのチェックを実行します。
Commit Phase −トランザクションは、メモリ内の変更されたデータ項目をディスクに書き戻します。
このアルゴリズムは、3つのルールを使用して、検証フェーズで直列化可能性を適用します。
Rule 1-二つのトランザクションTを考えると、私とTのJ Tがあれば、私はTデータ項目読んでいるjが書いているが、その後、T Iの実行フェーズでは、オーバーラップTとすることはできませんJさんフェーズコミット。T jは、Tiが実行を終了した後にのみコミットできます。
Rule 2-二つのトランザクションTを考えると、私とTのjがT場合、私はTのことをデータ項目書き込んでいるjが読んでいるが、その後、T IさんがTではない重複相はできるコミットJの実行フェーズ」。T jは、Tiがすでにコミットした後にのみ実行を開始できます。
Rule 3- Tが与えられた二つのトランザクションIおよびTのjはTがあれば、私はTデータ項目書き込んでいるjがも書いているが、その後、T Iさんは相コミットは、オーバーラップTとすることはできませんJさんフェーズコミット。T jは、Tiがすでにコミットした後でのみコミットを開始できます。
分散システムにおける並行性制御
このセクションでは、上記の手法が分散データベースシステムにどのように実装されているかを見ていきます。
分散型ツーフェーズロックアルゴリズム
分散型2フェーズロックの基本原理は、基本的な2フェーズロックプロトコルと同じです。ただし、分散システムには、ロックマネージャーとして指定されたサイトがあります。ロックマネージャーは、トランザクションモニターからのロック取得要求を制御します。さまざまなサイトのロックマネージャ間の調整を実施するために、少なくとも1つのサイトに、すべてのトランザクションを表示し、ロックの競合を検出する権限が与えられます。
ロックの競合を検出できるサイトの数に応じて、分散型2フェーズロックアプローチには3つのタイプがあります。
Centralized two-phase locking−このアプローチでは、1つのサイトが中央ロックマネージャーとして指定されます。環境内のすべてのサイトは、中央ロックマネージャーの場所を認識しており、トランザクション中に中央ロックマネージャーからロックを取得します。
Primary copy two-phase locking−このアプローチでは、いくつかのサイトがロック管理センターとして指定されます。これらの各サイトには、定義された一連のロックを管理する責任があります。すべてのサイトは、どのロックコントロールセンターがどのデータテーブル/フラグメントアイテムのロックを管理する責任があるかを知っています。
Distributed two-phase locking−このアプローチでは、多数のロックマネージャーがあり、各ロックマネージャーがローカルサイトに格納されているデータ項目のロックを制御します。ロックマネージャの場所は、データの分散とレプリケーションに基づいています。
分散タイムスタンプ同時実行制御
集中型システムでは、トランザクションのタイムスタンプは物理的な時計の読み取り値によって決定されます。ただし、分散システムでは、サイトのローカルの物理的/論理クロックの読み取り値は、グローバルに一意ではないため、グローバルタイムスタンプとして使用できません。したがって、タイムスタンプは、サイトIDとそのサイトの時計の読み取り値の組み合わせで構成されます。
タイムスタンプの順序付けアルゴリズムを実装するために、各サイトには、トランザクションマネージャーごとに個別のキューを維持するスケジューラーがあります。トランザクション中に、トランザクションマネージャーはサイトのスケジューラーにロック要求を送信します。スケジューラーは、タイムスタンプの昇順で対応するキューに要求を置きます。リクエストは、タイムスタンプの順に、つまり最も古いものから順にキューの先頭から処理されます。
競合グラフ
もう1つの方法は、競合グラフを作成することです。このトランザクションでは、クラスが定義されています。トランザクションクラスには、読み取りセットと書き込みセットと呼ばれる2セットのデータ項目が含まれています。トランザクションの読み取りセットがクラスの読み取りセットのサブセットであり、トランザクションの書き込みセットがクラスの書き込みセットのサブセットである場合、トランザクションは特定のクラスに属します。読み取りフェーズでは、各トランザクションは、読み取りセット内のデータ項目に対して読み取り要求を発行します。書き込みフェーズでは、各トランザクションが書き込み要求を発行します。
アクティブなトランザクションが属するクラスの競合グラフが作成されます。これには、垂直、水平、および斜めのエッジのセットが含まれています。垂直エッジは、クラス内の2つのノードを接続し、クラス内の競合を示します。水平エッジは、2つのクラスにまたがる2つのノードを接続し、異なるクラス間の書き込みと書き込みの競合を示します。対角エッジは、2つのクラスにまたがる2つのノードを接続し、2つのクラス間の書き込み/読み取りまたは読み取り/書き込みの競合を示します。
競合グラフを分析して、同じクラス内または2つの異なるクラス間で2つのトランザクションを並行して実行できるかどうかを確認します。
分散楽観的同時実行制御アルゴリズム
分散された楽観的同時実行制御アルゴリズムは、楽観的同時実行制御アルゴリズムを拡張します。この拡張機能には、2つのルールが適用されます-
Rule 1−このルールに従って、トランザクションは実行時にすべてのサイトでローカルに検証する必要があります。トランザクションがいずれかのサイトで無効であることが判明した場合、そのトランザクションは中止されます。ローカル検証により、トランザクションが実行されたサイトで直列化可能性が維持されることが保証されます。トランザクションがローカル検証テストに合格すると、グローバルに検証されます。
Rule 2−このルールによれば、トランザクションがローカル検証テストに合格した後、グローバルに検証する必要があります。グローバル検証により、2つの競合するトランザクションが複数のサイトで一緒に実行される場合、それらが一緒に実行されるすべてのサイトで同じ相対順序でコミットする必要があります。これには、検証後、コミットする前に、トランザクションが他の競合するトランザクションを待機する必要がある場合があります。この要件により、サイトで検証されるとすぐにトランザクションをコミットできない可能性があるため、アルゴリズムの楽観性が低下します。