分散正確性

ウィキペディア小見出し辞書

分散正確性

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/12/03 10:02 UTC 版)

「並行性制御」の記事における「分散正確性」の解説

ITの急激な進歩によってコンピュータネットワークの性能が向上し、ローカルな処理と分散処理の違いは曖昧になりつつある。そのためローカルな技法を極めて効率的に分散環境（例えば、コンピュータ・クラスターやマルチコアプロセッサ）に適用するのが一般的となっている。しかし、ローカルな技法には限界があり、分散のスケールが拡大すると対応できない。 分散直列可能性とコミットメント順序付け データベースシステムを分散化したり、分散環境で協調動作する場合（例えば、1990年代初めの連合データベースや最近のグリッド・コンピューティング、クラウドコンピューティング、スマートフォンのネットワークなど）、トランザクションも分散化される。分散トランザクションは複数プロセスにまたがるトランザクションであり、さらにコンピュータ間や地理的に離れたサイト間をまたぐこともある。これを処理するには効率的な分散並行性制御機構を必要とする。分散システムのスケジュールで直列化可能性を効率的に達成するには、ローカルな運用を意図して設計された機構では不可能な工夫を必要とする（グローバル直列化可能性を参照）。これは主に、ネットワークやコンピュータによるレイテンシによって並行性制御情報の分散が高くつくことによる。唯一広く知られている分散技法はコミットメント順序付け (Commit ordering, CO) であり、特許取得後の1991年に公表された。これは、トランザクションのコミットイベントを時系列に順序付けする技法である。COでは並行性制御情報を分散する必要がなく、信頼性/性能/スケーラビリティの観点で効率的な汎用技法となっており、異なる並行性制御機構を採用したシステムから成るヘテロジニアスな環境でも使用可能である。COはコミットイベントの順序を決定するだけで、具体的な機構には関与しない。1991年に公表されるまで、そのような技法は存在しないと言われていたし、発表後も誤解する専門家が多く見られた。COの重要な副作用として、分散デッドロック状態の自動的な解消がある。コミットメント順序付けの結果生成されるスケジュールの属性もCOと呼ばれる。 先述したSS2PLはCOの派生（特殊ケース）と見ることもでき、効率的に分散またはグローバルな直列化可能性を達成することができる。COと同様に分散デッドロックを自動的に解消でき、同時に正確性と直列化可能性を備えている。このような好ましい特徴を持ち、よく知られたロック実装機構であることから、SS2PLは広く採用されている。SS2PLは1980年に登場して以来広く採用され、デファクトスタンダードとなっている。ただしSS2PLはブロックする性質のある悲観的機構であるため、制限がもっと緩いCO（楽観的CO）を使って性能向上を図る場合もある。 分散衝突状態の直列化可能性は、効率的かつ汎用的に対処するのが難しい。「分散CO」では、各ローカルコンポーネントが何らかのCOを持ち、全体を2相コミット (2CP) による投票戦略で制御する。各ローカルコンポーネントがSS2PLであれば、分散COの特殊ケースである「分散SS2PL」となる（この場合、2相コミットによらなくても自動的に投票戦略が実施される）。これはCOが知られていない1980年代から使われていた。 参照とコミットの順序付けについてはCOの公表以前から研究されており、COのスケジュール属性は "dynamic atomicity" と呼ばれていた。COのアルゴリズムの正確な記述は1992年に公表された（等価な概念である "dynamic atomicity" については1988年まで遡ることができる）。最近（2009年）ではCOは4つの主要な並行性制御技法の1つとされており、他の技法の相互運用を可能にするものとされている。 分散回復可能性 分散回復可能性はコミットメント順序付けとよく似た直接的な方法で効率的に達成できる。各データベースはローカルに適用し、2相コミット (2PC) の戦略を採用する。 分散正確性（回復可能性）と分散コミットメント順序付け（直列化可能性）を含む分散SS2PLは自動的に投票戦略を採用し、全てのローカルな並行性制御機構としてSS2PLを採用すれば、全体で分散SS2PLが実現する。