分散DBMS-レプリケーション制御

この章では、すべてのサイトで一貫性のあるデータを維持するために必要なレプリケーション制御について説明します。レプリケーション制御技術とレプリケーション制御に必要なアルゴリズムについて学習します。

前に説明したように、 replicationは、分散データベースで使用される手法で、データテーブルの複数のコピーをさまざまなサイトに格納します。複数のサイトに複数のコピーがある場合の問題は、特に更新操作中にデータの整合性を維持するためのオーバーヘッドです。

すべてのサイトで相互に整合性のあるデータを維持するには、レプリケーション制御技術を採用する必要があります。レプリケーション制御には2つのアプローチがあります。

  • 同期レプリケーション制御
  • 非同期レプリケーション制御

同期レプリケーション制御

同期レプリケーションアプローチでは、すべてのレプリケーションが常に同じ値になるようにデータベースが同期されます。データ項目を要求するトランザクションは、すべてのサイトで同じ値にアクセスできます。この均一性を確保するために、データアイテムを更新するトランザクションが拡張され、データアイテムのすべてのコピーが更新されます。通常、この目的には2フェーズコミットプロトコルが使用されます。

たとえば、データテーブルPROJECT(PId、PName、PLocation)について考えてみましょう。PLocationが「Bombay」の場合、PLocationを「Mumbai」に更新するトランザクションT1を実行する必要があります。レプリケーションが存在しない場合、トランザクションT1の操作は次のようになります。

Begin T1: 
   Update PROJECT Set PLocation = 'Mumbai' 
   Where PLocation = 'Bombay'; 
End T1;

データテーブルのサイトAとサイトBに2つのレプリカがある場合、T1は2つのサイトに対応する2つの子T1AとT1Bを生成する必要があります。展開されたトランザクションT1は次のようになります-

Begin T1: 
   Begin T1A : 
      Update PROJECT Set PLocation = 'Mumbai' 
      Where PLocation = 'Bombay'; 
   End T1A;  
	
   Begin T2A : 
      Update PROJECT Set PLocation = 'Mumbai'
      Where PLocation = 'Bombay'; 
   End T2A; 
	
End T1;

非同期レプリケーション制御

非同期レプリケーションアプローチでは、レプリカが常に同じ値を維持するとは限りません。1つ以上のレプリカが古い値を格納している可能性があり、トランザクションは異なる値を見ることができます。すべてのレプリカを現在の値にするプロセスは、synchronization

同期の一般的な方法は、ストアアンドフォワード方式です。この方法では、1つのサイトがプライマリサイトとして指定され、他のサイトがセカンダリサイトとして指定されます。プライマリサイトには常に更新された値が含まれています。すべてのトランザクションは最初にプライマリサイトに入ります。これらのトランザクションは、セカンダリサイトでのアプリケーションのためにキューに入れられます。セカンダリサイトは、トランザクションの実行がスケジュールされている場合にのみ、ロールアウト方式を使用して更新されます。

レプリケーション制御アルゴリズム

レプリケーション制御アルゴリズムのいくつかは次のとおりです。

  • マスタースレーブレプリケーション制御アルゴリズム。
  • 分散投票アルゴリズム。
  • マジョリティコンセンサスアルゴリズム。
  • 循環トークンアルゴリズム。

マスタースレーブレプリケーション制御アルゴリズム

1つのマスターサイトと「N」スレーブサイトがあります。マスターアルゴリズムがマスターサイトで実行され、競合が検出されます。スレーブアルゴリズムのコピーは、各スレーブサイトで実行されます。全体的なアルゴリズムは、次の2つのフェーズで実行されます-

  • Transaction acceptance/rejection phase−トランザクションがスレーブサイトのトランザクションモニターに入ると、スレーブサイトはマスターサイトに要求を送信します。マスターサイトは競合をチェックします。競合がない場合、マスターは「ACK +」メッセージをスレーブサイトに送信し、スレーブサイトはトランザクションアプリケーションフェーズを開始します。それ以外の場合、マスターは「ACK-」メッセージをスレーブに送信し、スレーブはトランザクションを拒否します。

  • Transaction application phase−このフェーズに入ると、トランザクションが開始されたスレーブサイトは、トランザクションを実行するための要求をすべてのスレーブにブロードキャストします。要求を受信すると、ピアスレーブはトランザクションを実行し、完了時に要求側スレーブに「ACK」を送信します。要求しているスレーブは、すべてのピアから「ACK」メッセージを受信した後、「DONE」メッセージをマスターサイトに送信します。マスターは、トランザクションが完了したことを理解し、保留中のキューからトランザクションを削除します。

分散投票アルゴリズム

これは「N」個のピアサイトで構成され、トランザクションの実行を開始する前に、すべてのサイトでトランザクションを「OK」する必要があります。以下は、このアルゴリズムの2つのフェーズです。

  • Distributed transaction acceptance phase−トランザクションがサイトのトランザクションマネージャーに入ると、他のすべてのサイトにトランザクション要求を送信します。リクエストを受信すると、ピアサイトは優先度ベースの投票ルールを使用して競合を解決します。すべてのピアサイトがトランザクションで「OK」の場合、要求元のサイトはアプリケーションフェーズを開始します。ピアサイトのいずれかがトランザクションを「OK」しない場合、要求元のサイトはトランザクションを拒否します。

  • Distributed transaction application phase−このフェーズに入ると、トランザクションが開始されたサイトは、トランザクションを実行するための要求をすべてのスレーブにブロードキャストします。要求を受信すると、ピアスレーブはトランザクションを実行し、完了時に要求しているスレーブに「ACK」メッセージを送信します。要求元のスレーブは、すべてのピアから「ACK」メッセージを受信した後、トランザクションマネージャーにトランザクションが完了したことを通知します。

マジョリティコンセンサスアルゴリズム

これは、ピアの過半数がトランザクションを「OK」したときにトランザクションの実行が許可される分散投票アルゴリズムとは異なります。これは3つのフェーズに分けられます-

  • Voting phase−トランザクションがサイトのトランザクションマネージャーに入ると、他のすべてのサイトにトランザクション要求を送信します。要求を受信すると、ピアサイトは投票ルールを使用して競合をテストし、競合するトランザクションがある場合は保留キューに保持します。次に、「OK」または「NOTOK」メッセージを送信します。

  • Transaction acceptance/rejection phase−要求側サイトがトランザクションで過半数の「OK」を受信すると、トランザクションを受け入れ、すべてのサイトに「ACCEPT」をブロードキャストします。それ以外の場合は、「REJECT」をすべてのサイトにブロードキャストし、トランザクションを拒否します。

  • Transaction application phase−ピアサイトが「REJECT」メッセージを受信すると、このトランザクションを保留リストから削除し、すべての延期されたトランザクションを再検討します。ピアサイトが「ACCEPT」メッセージを受信すると、トランザクションを適用し、このトランザクションと競合する保留中のキュー内のすべての遅延トランザクションを拒否します。完了時に、要求元のスレーブに「ACK」を送信します。

循環トークンアルゴリズム

このアプローチでは、システム内のトランザクションは循環トークンを使用してシリアル化され、それに応じてデータベースのすべてのレプリカに対して実行されます。したがって、すべてのトランザクションが受け入れられます。つまり、拒否されるトランザクションはありません。これには2つのフェーズがあります-

  • Transaction serialization phase−このフェーズでは、すべてのトランザクションがシリアル化順に実行されるようにスケジュールされます。各サイトの各トランザクションには、トランザクションの順序を示す一連の一意のチケットが割り当てられます。トランザクションにチケットが割り当てられると、それはすべてのサイトにブロードキャストされます。

  • Transaction application phase−サイトがチケットと一緒にトランザクションを受信すると、そのチケットに従ってトランザクションを実行します。トランザクションの実行が終了すると、このサイトは適切なメッセージをブロードキャストします。トランザクションは、すべてのサイトで実行が完了すると終了します。