Quorum
quorumとは分散システムにおいて、分散トランザクションが処理を実行するために必要な最低限の票の数である。quorumベースの技術は分散システムにおいて、処理の整合性をとるために実装される。
分散データベースシステムにおけるquorumベースの手法
[編集]quorumベースの投票はデータベースレプリケーションの制御手法として使うことが出来る。[1] また、ネットワークパーティショニング下でのデータベーストランザクションアトミック性を保証するコミット手法としても使用できる。[1]
コミットプロトコルにおけるquorumベース投票
[編集]分散データベースシステムにおいて、トランザクションは複数サイトにおいて処理を実行している場合がある。アトミック性は全ての分散トランザクションがアトミックであることを要求するため、そのトランザクションも全てのサイトにおいて、コミットあるいは中止のいずれかの結末に至らなければならない。ネットワークパーティショニングの場合、サイトはパーティションに区分され、パーティション同士は通信可能ではない可能性がある。ここでquorumベースの技術が用いられる。基本的な考え方は、過半数のサイトがトランザクションの実行に投票した場合、そのトランザクションは実行される、というものである。
システム内の全てのサイトは票Viを持つ。システム内の総票数はVであり、中止およびコミットのquorumをそれぞれ、VaとVcとする。この場合、コミットプロトコルの実装には、次のルールが守らなければならない。
- Va + Vc > V なお、0 Va, Vc V
- トランザクションがコミットする前にコミットquorum Vcを獲得しなければならない。
- トランザクションが中止する前にアボートquorum Vaを獲得しなければならない。
最初のルールによりトランザクションのコミットと中止が同時になされることが無いことが保証される。次の2つのルールはトランザクションがいずれかの方法で終了する前に必要な票数を示している。
レプリケーション管理のためのquorumベース投票
[編集]レプリケーションを行ったデータベースにおいて、データオブジェクトは複数のサイトにコピーが存在している。直列化可能性を保証するため、2つのトランザクションが並列に同一のデータアイテムの読み込みおよび書き出しを行うことを許可してはならない。レプリケーションを行ったデータベースの場合、quorumベースのレプリケーション管理プロトコルを使用することにより、あるデータアイテムの2つのコピーが2つのトランザクションによって並列に読み込みおよび書き出しを行わないように保証することが出来る。
レプリケーション管理のためのquorumベース投票は [Gifford, 1979][2]による。レプリケーションされたデータアイテムの各コピーは票を割り当てられる。各オペレーションはデータアイテムの読み込みあるいは書き出しを行うためにそれぞれread quorum(Vr)あるいはwrite quorum (Vw)を獲得しなければならない。もしあるデータアイテムがV票持っているとして、quorumは次のルールに従わなければならない。
- Vr + Vw > V
- Vw > V/2
最初のルールはデータアイテムが2つのトランザクションに並列に読み込みあるいは書き出しされないことを保証する。2つ目のルールは2つのトランザクションによる2つの書き込みオペレーションが同じデータアイテムにおいて並列に実行されないことを保証する。2つのルールにより単一コピー直列化可能性が維持されることが保証される。
関連項目
[編集]脚注
[編集]- ^ a b Ozsu, Tamer M; Valduriez, Patrick (1991). “12”. Principles of distributed database systems (2nd ed.). Upper Saddle River, NJ: Prentice-Hall, Inc.. ISBN 0-13-691643-0
- ^ Gifford, David K. (1979), “Weighted voting for replicated data”, SOSP '79: Proceedings of the seventh ACM symposium on Operating systems principles, Pacific Grove, California, United States: ACM, pp. 150--162