クォーラム（分散コンピューティング）

クォーラムとは、分散システムにおいて分散トランザクションが操作を実行するために取得しなければならない最小の投票数です。クォーラムベースの技術は、分散システムにおける一貫した操作を強制するために実装されます。

分散データベースシステムにおけるクォーラムベースの技術

クォーラムベースの投票は、レプリカ制御方法[ 1 ]としてだけでなく、ネットワーク分割が存在する場合にトランザクションの原子性 を保証するコミット方法としても使用できます。[ 1 ]

コミットプロトコルにおけるクォーラムベースの投票

分散データベースシステムでは、トランザクションは複数のサイトで操作を実行する可能性があります。アトミック性を保つためには、すべての分散トランザクションがアトミックであることが求められるため、トランザクションはすべてのサイトで同じ結果（コミットまたはアボート）を辿る必要があります。ネットワーク分割が発生すると、サイトが分割され、パーティション間で通信できなくなる可能性があります。このような状況で、クォーラムベースの手法が役立ちます。基本的な考え方は、多数のサイトがトランザクションの実行に投票した場合、トランザクションが実行されるというものです。

システム内のすべてのサイトには投票権V iが割り当てられます。システム全体の投票数をV、アボートクォーラムとコミットクォーラムをそれぞれV aとV cと仮定します。コミットプロトコルの実装では、以下の規則に従う必要があります。

  1. V a + V c > V、ただし 0 < V c、V a V。≤{\displaystyle \leq }
  2. トランザクションがコミットする前に、コミットクォーラムV cを取得する必要があります。これは、コミットの準備ができている少なくとも1つのサイトと、コミットを待機している0以上のサイトの合計です。[ 2 ]≥{\displaystyle \geq }
  3. トランザクションが中止される前に、中止クォーラム V aを取得する必要があります。中止の準備ができている 0 個以上のサイト、またはV a を待機しているサイトの合計です。≥{\displaystyle \geq }

最初のルールは、トランザクションが同時にコミットと中止されないことを保証します。次の2つのルールは、トランザクションが何らかの方法で終了する前に獲得しなければならない投票数を示します。

レプリカ制御のためのクォーラムベースの投票

複製データベースでは、データオブジェクトのコピーが複数のサイトに存在します。直列化可能性を確保するため、2つのトランザクションが同時に同じデータ項目を読み書きすることは許可されません。複製データベースの場合、クォーラムベースのレプリカ制御プロトコルを使用することで、2つのトランザクションが同時に同じデータ項目の2つのコピーを読み書きすることがないようにすることができます。

レプリカ制御のためのクォーラムベースの投票は、[Gifford, 1979] [ 3 ]に由来する。複製されたデータ項目の各コピーには投票が割り当てられる。各操作は、データ項目の読み取りまたは書き込みを行うために、それぞれ読み取りクォーラム（V r）または書き込みクォーラム（V w ） を獲得する必要がある。あるデータ項目に合計Vの投票がある場合、クォーラムは以下の規則に従う必要がある。

  1. V r + V w > V
  2. V w > V/2

最初のルールは、データ項目が2つのトランザクションによって同時に読み書きされないことを保証します。さらに、読み取りクォーラムには、データ項目の最新バージョンを保持するサイトが少なくとも1つ含まれていることを保証します。2番目のルールは、2つのトランザクションからの2つの書き込み操作が、同じデータ項目に対して同時に発生しないことを保証します。これらの2つのルールにより、1コピーのシリアル化可能性が維持されます。

参照

参考文献

  1. ^ a b Ozsu, Tamer M; Valduriez, Patrick (1991). "12".分散データベースシステムの原則（第2版）. Upper Saddle River, NJ: Prentice-Hall, Inc. ISBN 978-0-13-691643-7。
  2. ^ Skeen, Dale. 「クォーラムベースのコミットプロトコル」(PDF) . コーネル大学ECommonsライブラリ. 2013年2月10日閲覧。
  3. ^ Gifford, David K. (1979).複製データに対する加重投票. SOSP '79: Proceedings of the seventh ACM symposium on Operating systems practices. Pacific Grove, California, United States: ACM. pp.  150– 162. CiteSeerX 10.1.1.12.6256 . doi : 10.1145/800215.806583 . 
「 https://en.wikipedia.org/w/index.php?title=Quorum_(distributed_computing)&oldid=1333797497」より取得