Quorumのソースを表示

'''quorum'''とは[[分散システム]]において、分散トランザクションが処理を実行するために必要な最低限の票の数である。'''quorum'''ベースの技術は分散システムにおいて、処理の整合性をとるために実装される。

== 分散データベースシステムにおけるquorumベースの手法 ==
quorumベースの投票はデータベース[[レプリケーション]]の制御手法として使うことが出来る。<ref name="ozsu">
{{cite book |last1= Ozsu 
|first1= Tamer M 
|last2= Valduriez
|first2= Patrick
|title= Principles of distributed database systems
|edition= 2nd
|isbn = 0-13-691643-0
|year= 1991
|publisher= Prentice-Hall, Inc.
|location= Upper Saddle River, NJ
|chapter= 12
}}</ref>
また、ネットワークパーティショニング下でのデータベース[[トランザクション]][[アトミック性]]を保証するコミット手法としても使用できる。<ref name="ozsu"/>

=== コミットプロトコルにおけるquorumベース投票 ===
分散データベースシステムにおいて、トランザクションは複数サイトにおいて処理を実行している場合がある。アトミック性は全ての分散トランザクションがアトミックであることを要求するため、そのトランザクションも全てのサイトにおいて、[[コミット]]あるいは[[ロールバック|中止]]のいずれかの結末に至らなければならない。ネットワークパーティショニングの場合、サイトはパーティションに区分され、パーティション同士は通信可能ではない可能性がある。ここでquorumベースの技術が用いられる。基本的な考え方は、過半数のサイトがトランザクションの実行に投票した場合、そのトランザクションは実行される、というものである。

システム内の全てのサイトは票V<sub>i</sub>を持つ。システム内の総票数はVであり、中止およびコミットのquorumをそれぞれ、V<sub>a</sub>とV<sub>c</sub>とする。この場合、コミットプロトコルの実装には、次のルールが守らなければならない。
# V<sub>a</sub> + V<sub>c</sub> > V なお、0 <math>\le</math> V<sub>a</sub>, V<sub>c</sub> <math>\le</math> V
# トランザクションがコミットする前にコミットquorum V<sub>c</sub>を獲得しなければならない。
# トランザクションが中止する前にアボートquorum V<sub>a</sub>を獲得しなければならない。

最初のルールによりトランザクションのコミットと中止が同時になされることが無いことが保証される。次の2つのルールはトランザクションがいずれかの方法で終了する前に必要な票数を示している。

=== レプリケーション管理のためのquorumベース投票 ===
レプリケーションを行ったデータベースにおいて、データオブジェクトは複数のサイトにコピーが存在している。[[直列化可能性]]を保証するため、2つのトランザクションが並列に同一のデータアイテムの読み込みおよび書き出しを行うことを許可してはならない。レプリケーションを行ったデータベースの場合、quorumベースのレプリケーション管理プロトコルを使用することにより、あるデータアイテムの2つのコピーが2つのトランザクションによって並列に読み込みおよび書き出しを行わないように保証することが出来る。

レプリケーション管理のためのquorumベース投票は
[Gifford, 1979]<ref>
{{Citation
| first = David K.
| last = Gifford
| contribution = Weighted voting for replicated data
| title = SOSP '79: Proceedings of the seventh ACM symposium on Operating systems principles
| year = 1979
| pages = 150--162
| place = Pacific Grove, California, United States
| url = http://doi.acm.org/10.1145/800215.806583
| publisher = ACM
 }}</ref>による。レプリケーションされたデータアイテムの各コピーは票を割り当てられる。各オペレーションはデータアイテムの読み込みあるいは書き出しを行うためにそれぞれ''read quorum''(V<sub>r</sub>)あるいは''write quorum'' (V<sub>w</sub>)を獲得しなければならない。もしあるデータアイテムがV票持っているとして、quorumは次のルールに従わなければならない。
# V<sub>r</sub> + V<sub>w</sub> > V
# V<sub>w</sub> > V/2

最初のルールはデータアイテムが2つのトランザクションに並列に読み込みあるいは書き出しされないことを保証する。2つ目のルールは2つのトランザクションによる2つの書き込みオペレーションが同じデータアイテムにおいて並列に実行されないことを保証する。2つのルールにより単一コピー直列化可能性が維持されることが保証される。

== 関連項目 ==
* [[トランザクション]]
* [[レプリケーション]]
* [[不可分操作]]

== 脚注 ==
<references/>

[[Category:データベース管理システム]]
[[Category:データベース]]
[[Category:トランザクション処理]]
[[Category:分散コンピューティングアーキテクチャ]]