DBMSの並行性制御：ロックとタイムスタンプベースのプロトコル

同時実行制御とは何ですか?

同時実行制御 データベース管理システムにおける「同時実行制御」とは、複数の操作が互いに競合することなく同時に実行されるように管理する手順のことです。これにより、データベースのトランザクションが同時かつ正確に実行され、各データベースのデータ整合性を損なうことなく正しい結果が得られることが保証されます。

すべてのユーザーがデータの読み取りのみを行う場合、互いに干渉する可能性がないため、同時アクセスは非常に容易です。しかし、実際のデータベースでは読み取り操作と書き込み操作が混在するため、同時アクセスは課題となります。

DBMSの同時実行制御は、主にマルチユーザーシステムで発生するこのような競合に対処するために使用されます。したがって、同時実行制御は、2つ以上のトランザクションが同時に実行され、同じデータへのアクセスを必要とするデータベースの適切な機能にとって最も重要な要素の1つです。これは、 トランザクション管理これは、並行性制御が安全にインターリーブしなければならない作業単位を定義するものです。

並行処理における潜在的な問題点

適切なDBMS同時実行制御を行わない場合、以下のような問題に直面する可能性があります。

• 失われたアップデート 複数のトランザクションが同じ行を選択し、選択された値に基づいてその行を更新した場合に発生します。
• 未コミットの依存関係 （ダーティリード）は、まだコミットされていない別のトランザクションによって更新された行を、別のトランザクションが選択した場合に発生します。
• 非反復読み取り これは、2番目のトランザクションが同じ行に複数回アクセスし、毎回異なるデータを読み取る場合に発生します。
• 誤った要約 これは、あるトランザクションが繰り返し出現するデータ項目のすべてのインスタンスの値の集計を行い、別のトランザクションがそれらのインスタンスの一部を更新する場合に発生します。結果として得られる集計は、正しい結果を反映しません。

なぜ並行処理手法を用いるのか？

DBMSで並行性制御方式を使用する理由：

• 競合する取引間で相互排他による隔離を適用する。
• 読み書き競合および書き込み競合の問題を解決する。
• 実行制約を常に適用することで、データベースの一貫性を維持する。
• 並行トランザクション間の相互作用を制御するために、並行制御スキームが用いられる。
• シリアル化可能性を確保するため。

例:

2人が同時に電子キオスクに行き、同じ映画の同じ上映時間のチケットを購入すると仮定します。

しかし、その映画館ではその上映回に空席​​は1席しかありません。同時実行制御がなければ、両方の映画鑑賞者がチケットを購入してしまう可能性があります。同時実行制御があれば、このような事態は防げます。両方の映画鑑賞者は映画の座席データベースの情報にアクセスできますが、同時実行制御によってチケットは、先に取引を完了した購入者にのみ発行されます。

同時実行制御プロトコル

異なる並行性制御プロトコルは、許容される並行性の量とそれに伴うオーバーヘッドとの間で異なるトレードオフを提供します。DBMSにおける主な並行性制御技術は次のとおりです。

• ロックベースのプロトコル
• 2相ロックプロトコル
• タイムスタンプベースのプロトコル
• 検証ベースのプロトコル

以下では、最も広く使用されているロックベースのプロトコルから順に、それぞれについて詳しく見ていきます。

ロックベースのプロトコル

ロックベースのプロトコル DBMSにおけるロックとは、トランザクションが適切なロックを取得するまでデータ項目の読み書きができない仕組みのことです。ロックベースのプロトコルは、特定のデータ項目を単一のトランザクションにロックまたは分離することで、並行処理の問題を解消するのに役立ちます。

ロックとは、データ項目に関連付けられたデータ変数であり、そのデータ項目に対して実行可能な操作を示します。ロックは、同時実行トランザクションによるデータベース項目へのアクセスを同期するのに役立ちます。すべてのロック要求は同時実行制御マネージャに対して行われ、トランザクションはロック要求が許可された後にのみ実行されます。

バイナリ ロック: データ項目に対するバイナリロックは、ロック状態またはロック解除状態のいずれかになります。

共有/独占: このロック機構は、ロックをその用途に基づいて分類します。書き込み操作を実行するために取得されたロックは、排他ロックと呼ばれます。

1. 共有ロック (S): 共有ロックは読み取り専用ロックとも呼ばれます。共有ロックを使用すると、データ項目はトランザクション間で共有できます。これは、どのトランザクションも項目を更新する権限を持たないためです。たとえば、2 つのトランザクションが個人の口座残高を読み取っている場合、 データベース 共有ロックをかけることで、読み取りが可能になります。別のトランザクションがその残高を更新しようとしても、読み取りが完了するまで共有ロックによって更新が阻止されます。

2. 排他的ロック (X): 排他ロックを使用すると、データ項目は読み取りと書き込みの両方が可能になります。排他的であり、同じデータ項目に対して同時にロックを保持することはできません。排他ロックは、lock-x命令を使用して要求します。たとえば、トランザクションが口座残高を更新する必要がある場合、排他ロックを設定することで更新が許可されます。これにより、読み取りまたは書き込みを希望する別のトランザクションは阻止されます。

3. シンプルなロックプロトコル： これにより、トランザクションは操作を開始する前にすべてのオブジェクトに対するロックを取得できます。トランザクションは書き込み操作の完了後にデータ項目のロックを解除できます。

4. ロックの事前確保: このプロトコルは操作を評価し、実行開始に必要なデータ項目のリストを作成します。すべてのロックが付与されるとトランザクションが実行され、操作が完了するとすべてのロックが解放されます。

飢餓: 飢餓状態とは、トランザクションがロックを取得するために無期限に待機する状況を指します。その原因としては、ロックされたアイテムの待機スキームの管理が不十分であること、リソースリーク、または同じトランザクションが繰り返し犠牲者として選択されることなどが挙げられます。

デッドロック: デッドロックとは、2つ以上のプロセスが互いにリソースの解放を待ち続け、循環的な連鎖を形成する状況を指します。

2相ロック（2PL）プロトコル

その 2相ロックプロトコル2PLとしても知られるこの方法は、トランザクションデータにロックを適用することで直列化可能性を保証する並行性制御の手法であり、他のトランザクションが同じデータに同時にアクセスすることをブロックします。

2段階ロックプロトコルでは、各トランザクションが2つのステップでロックまたはロック解除の要求を行うことができます。

• 成長段階: この段階では、トランザクションはロックを取得することはできますが、ロックを解放することはできません。
• 縮小段階: この段階では、トランザクションはロックを解放することはできますが、新たなロックを取得することはできません。

確かに2PLは直列化可能性を提供しますが、デッドロックが発生しないことを保証するものではありません。上の図では、ローカルおよびグローバルなデッドロック検出器がデッドロックを検出し、トランザクションを初期状態に戻すことで解決します。

厳密なXNUMX段階ロック方式

厳密2PLは、2PLとほぼ同じです。唯一の違いは、厳密2PLはロックを使用した後にロックを解放しない点です。コミットポイントまで全てのロックを保持し、処理が終了した時点でまとめて解放します。

集中型2PL

集中型2PLでは、単一のサイトがロック管理プロセスを担当します。DBMS全体に対して、ロックマネージャは1つしかありません。

プライマリーコピー 2PL

プライマリコピー2PLメカニズムでは、多数のロックマネージャが異なるサイトに分散配置され、特定のロックマネージャが一連のデータ項目のロック管理を担当します。プライマリコピーが更新されると、その変更はスレーブに伝播されます。

分散型2PL

このメカニズムでは、ロックマネージャがすべてのサイトに分散配置され、各サイトのデータに対するロック管理を担当します。データが複製されない場合は、プライマリコピー2PLと同等になります。分散2PLの通信コストは、プライマリコピー2PLよりもかなり高くなります。

タイムスタンプベースのプロトコル

その タイムスタンプベースのプロトコル DBMSにおけるアルゴリズムの一つに、システム時刻または論理カウンタをタイムスタンプとして使用し、同時実行トランザクションの実行を直列化するものがあります。これにより、競合するすべての読み取りおよび書き込み操作がタイムスタンプ順に実行されることが保証されます。

この方式では、常に古いトランザクションが優先されます。トランザクションのタイムスタンプを決定するためにシステム時刻を使用し、最も一般的に使用されている並行処理プロトコルです。ロックベースのプロトコルは、競合するトランザクションの実行時にそれらの順序を管理しますが、タイムスタンプベースのプロトコルは、操作が作成された直後に競合を管理します。

例：

Suppose there are three transactions T1, T2, and T3.
T1 has entered the system at time 0010
T2 has entered the system at 0020
T3 has entered the system at 0030
Priority will be given to transaction T1, then T2 and lastly T3.

Advantages:

• スケジュールは、2PLプロトコルと同様に、直列化可能です。
• トランザクションの完了を待つ必要がないため、デッドロックが発生する可能性がなくなります。

短所： 同じトランザクションが繰り返し再開され、かつ継続的に中断されると、飢餓状態が発生する可能性があります。

検証ベースのプロトコル

その 検証に基づくプロトコル DBMSにおけるオプティミスティック並行性制御技術としても知られるこの手法は、トランザクションにおける並行性競合を回避するためのものです。このプロトコルでは、トランザクションデータ自体ではなく、トランザクションデータのローカルコピーが更新されるため、実行中の干渉が軽減されます。

検証に基づくプロトコルは、以下の3つの段階で実施されます。

1. 読み取りフェーズ
2. 検証フェーズ
3. 書き込みフェーズ

読み取りフェーズ

読み取りフェーズでは、トランザクションによってデータ値を読み取ることができますが、書き込み操作や更新は実際のデータベースではなく、ローカルのデータコピーにのみ適用されます。

検証フェーズ

検証段階では、更新を適用してもシリアル化可能性が損なわれないことを確認するためにデータがチェックされます。

書き込みフェーズ

書き込みフェーズでは、検証が成功した場合、更新内容がデータベースに適用されます。検証に失敗した場合は、更新内容は破棄され、トランザクションはロールバックされます。

並行性制御プロトコルの比較

これら4つのプロトコルファミリーは、トランザクションが実際にどの程度の頻度で競合するかについて、それぞれ異なる見解を持っています。以下の表は、それぞれのプロトコルファミリーがどの位置づけにあるかをまとめたものです。

要するに、ロックベースおよび2PLプロトコルは、競合が頻繁に発生することを前提として、事前にそれを防止しますが、タイムスタンプおよび検証プロトコルは、競合がまれであることを前提として、発生した場合にのみ解決します。

優れた並行処理プロトコルの特徴

理想的な並行性制御メカニズムは、以下の目的を持つ。

• それは、設置場所や通信障害に対して耐性を持つ必要がある。
• これにより、トランザクションを並列実行して最大の同時実行性を実現できます。
• オーバーヘッドを最小限に抑えるために、その記憶メカニズムと計算方法は控えめにする必要があります。
• それは、トランザクションの原子的な動作の構造に何らかの制約を課す必要がある。

よくあるご質問