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

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

前述したように、*レプリケーション*は、分散データベースで使用され、異なるサイトにデータテーブルの複数のコピーを保存する手法です。複数のサイトに複数のコピーを作成する場合の問題は、特に更新操作中にデータの一貫性を維持するオーバーヘッドです。

すべてのサイトで相互に一貫性のあるデータを維持するには、複製制御技術を採用する必要があります。複製制御には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つ以上のレプリカに古い値が格納されている場合があり、トランザクションは異なる値を見ることができます。すべてのレプリカを現在の値にするプロセスは、*同期*と呼ばれます。

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

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

レプリケーション制御アルゴリズムの一部は次のとおりです-

マスタースレーブ複製制御アルゴリズム。
分散投票アルゴリズム。
多数決アルゴリズム。
循環トークンアルゴリズム。

マスタースレーブ複製制御アルゴリズム

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

トランザクションの受け入れ/拒否フェーズ-トランザクションがスレーブサイトのトランザクションモニターに入ると、スレーブサイトはマスターサイトに要求を送信します。マスターサイトは競合をチェックします。競合がない場合、マスターはスレーブサイトに「ACK +」メッセージを送信し、その後、トランザクションアプリケーションフェーズを開始します。そうでない場合、マスターは「ACK-」メッセージをスレーブに送信し、スレーブはトランザクションを拒否します。
トランザクションアプリケーションフェーズ-このフェーズに入ると、トランザクションが入力されたスレーブサイトは、トランザクションを実行するためにすべてのスレーブに要求をブロードキャストします。リクエストを受信すると、ピアスレーブはトランザクションを実行し、完了時にリクエストスレーブに「ACK」を送信します。要求側のスレーブは、すべてのピアから「ACK」メッセージを受信すると、マスターサイトに「DONE」メッセージを送信します。マスターは、トランザクションが完了したことを理解し、保留中のキューから削除します。

分散投票アルゴリズム

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

分散トランザクションの受け入れフェーズ-トランザクションがサイトのトランザクションマネージャーに入ると、トランザクションリクエストが他のすべてのサイトに送信されます。ピアサイトは、リクエストを受信すると、優先度ベースの投票ルールを使用して競合を解決します。すべてのピアサイトがトランザクションで「OK」の場合、要求サイトはアプリケーションフェーズを開始します。ピアサイトのいずれかがトランザクションを「OK」しない場合、要求元サイトはトランザクションを拒否します。
分散トランザクションアプリケーションフェーズ-このフェーズに入ると、トランザクションが開始されたサイトは、トランザクションを実行するためにすべてのスレーブにリクエストをブロードキャストします。要求を受信すると、ピアスレーブはトランザクションを実行し、完了時に要求側スレーブに「ACK」メッセージを送信します。要求側のスレーブは、すべてのピアから「ACK」メッセージを受信した後、トランザクションマネージャーにトランザクションが完了したことを知らせます。

多数決アルゴリズム

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

投票フェーズ-トランザクションがサイトのトランザクションマネージャーに入ると、トランザクションリクエストが他のすべてのサイトに送信されます。ピアサイトは、要求を受信すると、投票ルールを使用して競合をテストし、競合するトランザクションがあれば、保留中のキューに保持します。次に、「OK」または「NOT OK」メッセージを送信します。
トランザクションの受け入れ/拒否フェーズ-要求元のサイトがトランザクションで多数の「OK」を受け取ると、トランザクションを受け入れ、すべてのサイトに「ACCEPT」をブロードキャストします。それ以外の場合は、すべてのサイトに「拒否」をブロードキャストし、トランザクションを拒否します。
トランザクションアプリケーションフェーズ-ピアサイトが「REJECT」メッセージを受信すると、このトランザクションを保留リストから削除し、すべての遅延トランザクションを再検討します。ピアサイトが「ACCEPT」メッセージを受信すると、トランザクションを適用し、このトランザクションと競合している保留中のキュー内のすべての遅延トランザクションを拒否します。完了すると、要求元のスレーブに「ACK」を送信します。

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

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

トランザクションのシリアル化フェーズ-このフェーズでは、すべてのトランザクションがシリアル化の順序で実行されるようにスケジュールされます。各サイトの各トランザクションには、トランザクションの順序を示す一連の連続した一意のチケットが割り当てられます。トランザクションにチケットが割り当てられると、すべてのサイトにブロードキャストされます。
トランザクションアプリケーションフェーズ-サイトがチケットとともにトランザクションを受信すると、サイトはチケットに従ってトランザクションを実行します。トランザクションの実行が完了すると、このサイトは適切なメッセージをブロードキャストします。トランザクションは、すべてのサイトで実行が完了すると終了します。

Distributed-dbms-replication-control

目次