コミットメント発注

コミットメント順序付け( CO ) は、データベース、トランザクション処理、および関連アプリケーションの同時実行制御における相互運用可能な直列化可能性技術の一種です。楽観的(非ブロッキング) 実装が可能です。マルチコア プロセッサの普及に伴い、 CO は同時プログラミング、トランザクショナル メモリ、ソフトウェア トランザクショナル メモリ(STM)でも楽観的に直列化可能性を実現するためにますます利用されるようになりました。 CO は、結果として得られるトランザクション スケジュール(履歴) プロパティの名前でもあり、1988 年に動的原子性という名前で定義されました。^{[ 1 ]} CO 準拠のスケジュールでは、トランザクションのコミットメント イベントの発生順序は、各トランザクションの優先順位と互換性があります。 CO は、競合直列化可能性の幅広い特殊なケースであり、異なる同時実行制御メカニズムを使用する可能性のあるデータベース システムのコレクション全体でグローバル直列化可能性 (モジュール直列化可能性) を実現するための効果的な手段 (信頼性、高性能、分散性、スケーラビリティ) です (CO は、各システムの直列化可能性を、まだ準拠していない場合は準拠させます)

CO に準拠していない各データベース システムには、データ アクセスやその他のトランザクション操作の干渉なしに、CO 準拠のコミットメント イベントを順序付ける CO コンポーネント (コミットメント オーダー コーディネータ、COCO) が追加されています。このように、CO は、グローバル直列化可能性 (および分散直列化可能性) のためのオーバーヘッドの低い汎用ソリューションを提供し、マルチデータベース システムやその他のトランザクション オブジェクト(クラウド コンピューティング、グリッド コンピューティング、スマートフォンネットワーク内など) のグローバル同時実行制御(および分散同時実行制御) に役立ちます。アトミック コミットメント プロトコル(ACP、任意のタイプ) は、ソリューションの基本的な部分であり、競合 (優先順位、直列化可能性) グラフ内のグローバル サイクルを切断するために使用されます。CO は、関連するデータベース システムがアトミック コミットメント プロトコル (未変更) メッセージ以外の同時実行制御情報を共有せず、トランザクションがグローバルかローカルかを認識していない場合 (データベース システムが自律的) 、グローバル直列化可能性を保証する最も一般的なプロパティ (必要条件) ですしたがって、CO（およびその派生）は、一般的にコストのかかるローカルな同時実行制御情報（ローカルな優先順位関係、ロック、タイムスタンプ、チケットなど）の配布を必要としない唯一の汎用的な手法です。COは、広く普及している強力な厳密な2相ロック（SS2PL）特性を一般化しており、 2相コミットプロトコル（2PC）と組み合わせることで、（SS2PLベースの）データベースシステム全体にわたってグローバルな直列化可能性を実現するための事実上の標準となっています。その結果、CO準拠のデータベースシステム（どのような種類の同時実行制御であっても）は、グローバルな直列化可能性を実現するSS2PLベースのソリューションに透過的に統合できます。

さらに、ロック ベースのグローバル デッドロックは、CO ベースのマルチデータベース環境では自動的に解決されます。これは、重要な副次的な利点です (完全に SS2PL ベースの環境の特殊なケースを含む。これは、SS2PL ではこれまで注目されていなかった事実です)。

さらに、厳密性とCOの融合である厳密なコミットメント順序付け（SCO; Raz 1991c ）は、読み取り/書き込み競合が発生する場合（書き込み/読み取り競合と書き込み/書き込み競合のブロッキング動作は同一、ロックオーバーヘッドは同程度） 、SS2PLよりも優れたパフォーマンス（平均トランザクション完了時間が短縮され、結果としてトランザクションスループットが向上する）を実現します（書き込み/読み取り競合と書き込み/書き込み競合のブロッキング動作は同一、ロックオーバーヘッドは同程度）。SCOの利点は、特にロック競合時に顕著です。厳密性により、SS2PLとSCOはどちらも同じ効果的なデータベース復旧メカニズムを使用できます。

CO には、拡張 CO (ECO; Raz 1993a ) とマルチバージョン CO (MVCO; Raz 1993b ) という 2 つの主要な一般化バリアントが存在します。これらのバリアントも、ローカルな同時実行制御情報の配布なしでグローバルな直列化可能性を提供し、任意の関連する同時実行制御と組み合わせることができ、楽観的 (非ブロッキング) 実装が可能です。どちらも、CO 制約を緩和し、より優れた同時実行性とパフォーマンスを実現するために追加情報を使用します。投票順序付け(VO または一般化 CO (GCO); Raz 2009 ) は、CO とそのすべてのバリアント用のコンテナ スケジュール セット (プロパティ) および手法です。アトミック コミットメント プロトコル (ACP) 参加者が同時実行制御情報を共有しない場合 (一般化された自律性プロパティを持つ場合)、グローバルな直列化可能性を保証するためにローカル VO が必要です。CO とそのバリアントは透過的に相互運用し、

概要

コミットメント順序（CO; Raz 1990 , 1992 , 1994 , 2009）スケジュール特性は、動的原子性（1988年以降^{[ 1 ]}）、コミット順序、コミット順序の直列化可能性、そして強力な回復可能性（1991年以降）とも呼ばれてきました。後者は誤解を招く名称です。なぜなら、COは回復可能性とは比較できず、「強力な」という用語は特別な場合を意味するからです。つまり、実質的な回復可能性特性が必ずしもCO特性を持つとは限らず、その逆も同様です。

2009年、COは、1980年代から知られていた3つの主要な方法、すなわちロック、タイムスタンプ順序付け、シリアル化グラフテストとともに、主要な並行性制御方法として特徴づけられ、異なる並行性制御メカニズムを使用するシステムの相互運用性を実現するものとして特徴づけられました。^{[ 2 ]}

連合データベース システムや、より緩く定義された他のマルチデータベース システム (通常は通信ネットワークに分散)では、トランザクションは複数の、場合によっては分散データベースにまたがります。このようなシステムでグローバル直列化可能性を強制することは問題があります。単一データベースのすべてのローカル スケジュールが直列化可能であるとしても、システム全体のグローバル スケジュールが必ずしも直列化可能であるとは限りません。競合の直列化可能性を実現するためにデータベース間で必要となる競合情報の膨大な通信交換は、主にコンピュータと通信の待ち時間のために、許容できないパフォーマンスにつながります。グローバル直列化可能性を効果的に実現する問題は、 1991 年に発明者のYoav Raz ( Raz 1991a 、グローバル直列化可能性も参照)によって CO が公開されるまでは未解決の問題でした。

CO の強制は、分散システムでグローバルに競合の直列化可能性を強制する効果的な方法です。各データベース (または他のトランザクション オブジェクト) でローカルに CO を強制すると、グローバルにもそれが強制されるためです。各データベースは、任意の (場合によっては異なる) 種類の同時実行制御メカニズムを使用できます。競合の直列化可能性を既に提供しているローカル メカニズムでは、CO をローカルに強制しても他のアボートは発生しません。これは、CO をローカルに強制しても、メカニズムのデータ アクセス スケジューリング戦略に影響しないためです (このスケジューリングによって直列化可能性に関連するアボートが決定されます。このようなメカニズムでは通常、コミットメント イベントやその順序は考慮されません)。CO ソリューションでは、各分散トランザクションがアトミック性を達成するために既に必要としている (変更されていない)アトミック コミットメントプロトコル メッセージのみを使用するため、通信オーバーヘッドは発生しません。アトミック コミットメント プロトコルは、グローバル競合グラフ内のグローバル サイクル (2 つ以上のデータベースにまたがるサイクル) を切断することによって、グローバルに CO を強制する分散 CO アルゴリズムで中心的な役割を果たします。 CO とその特殊ケース、およびその一般化は相互運用可能であり、グローバルな直列化可能性を実現すると同時に、同時実行制御メカニズムが異なる可能性のあるオブジェクトで構成される単一の異種分散環境で透過的に併用されます。 そのため、コミットメント順序付けは、その特殊ケースも含め、その一般化 (以下の CO バリアントを参照) とともに、マルチデータベース システムと他の複数のトランザクション オブジェクト (トランザクションによってのみ状態がアクセスおよび変更されるオブジェクト。たとえば、トランザクション プロセスのフレームワーク内、クラウド コンピューティング、グリッド コンピューティング内) の異種環境でグローバルな直列化可能性を保証するための汎用的で高性能な完全分散ソリューション (中央処理コンポーネントや中央データ構造は不要) を提供します。 CO ソリューションは、パフォーマンスに悪影響を与えることなく、ネットワーク サイズとデータベースの数に合わせて拡張できます (単一の分散トランザクションの統計、たとえば単一のトランザクションに関連するデータベースの平均数は変更されないと仮定)。

マルチコアプロセッサの普及に伴い、ソフトウェアトランザクションメモリのシリアル化を実現するために楽観的CO（OCO）の利用も増えており、「コミット順序」を活用したSTM論文や特許も多数公開されている（例えば、Zhang et al. 2006 ^{[ 3 ]}）。

グローバル直列化可能性のためのコミットメント順序付けソリューション

COの一般的な特性

コミットメント順序(CO) は、競合直列化可能性の特殊なケースです。CO は、非ブロッキングメカニズムで強制できます(各トランザクションは、データ アクセスがブロックされることなくタスクを完了できるため、楽観的同時実行制御が可能です。ただし、コミットメントはブロックされる可能性があります)。CO スケジュールでは、トランザクションのコミットメント イベントの (部分的な) 優先順位は、競合するアクセス操作 (通常は読み取りおよび書き込み (挿入/変更/削除) 操作。CO は、非可換な場合は競合する高レベルの操作や、複数バージョンのデータに対する操作間の競合にも適用されます) によって生じる、(有向) 競合グラフ (優先順位グラフ、直列化可能性グラフ) 内の各トランザクションの優先順位 (部分的) に対応します。

定義: コミットメント順序

スケジュールにおいて、 が （ が に先行）と競合する2つのコミット済みトランザクションがあるとします。このようなトランザクション2つのうち、がより前にコミットされる場合、スケジュールはコミットメント順序付け（CO）特性を持ちます。${\displaystyle T_{1},T_{2}}$ ${\displaystyle T_{2}}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$

異なるプロセスがコミットするか中止するかについて合意に達する必要がある場合、コミットメント決定イベントは、ローカル コミットメント メカニズムまたはアトミック コミットメント プロトコルによって生成されます。プロトコルは分散型または集中型の場合があります。コミット部分順序が許せば (競合する操作がない場合)、トランザクションは同時にコミットできます。異なる競合操作が同じトランザクションの異なる部分順序を誘導するとします。その場合、競合グラフにはサイクルがあり、サイクル上のすべてのトランザクションがコミットされると、スケジュールは直列化可能性に違反します。この場合、コミットメント イベントの部分順序は見つかりません。したがって、競合グラフのサイクルは、トランザクションを中止することによって壊す必要があります。ただし、トランザクションの優先順位の部分順序に従ってコミット イベントを適切に遅延させることにより、競合直列化可能スケジュールをトランザクションを中止せずに CO にすることができます。

CO には回復可能性のプロパティがないため、CO の強制だけでは同時実行制御メカニズムとしては不十分であり、この回復可能性もサポートされる必要があります。

分散COアルゴリズム

参加している各データベースのローカル CO を使用する、完全に分散されたグローバル コミットメント順序付け強制アルゴリズムが存在し、これは (変更されていない) アトミック コミットメント プロトコル メッセージのみを必要とし、それ以上の通信は不要です。分散アルゴリズムは、ローカル (各データベースに対して) CO アルゴリズム プロセスと (完全に分散可能な) アトミック コミットメント プロトコルを組み合わせたものです。アトミック コミットメント プロトコルは、各分散トランザクションのアトミック性 (コミットするか中止するかを決定するため。この手順は、同時実行制御や CO とは関係なく、分散トランザクションで常に実行されます) を強制するために不可欠です。アトミック コミットメント プロトコルの一般的な例は、多くの種類のシステム障害に耐性のある2 フェーズ コミット プロトコルです。信頼性の高い環境、またはプロセスが通常同時に失敗する (同じ集積回路内など) 場合、より単純なアトミック コミットメント プロトコルを使用できます (たとえば、分散トランザクションの参加プロセスと、任意の既知の特別な参加者 (トランザクションのコーディネーター) との単純なハンドシェイク、つまり、 1 フェーズ コミットプロトコルの一種)アトミック コミットメント プロトコルは、参加者にまたがる分散 (グローバル) トランザクションをコミットするか中止するかについて、参加者間で合意に達します。このようなプロトコルの重要な段階は、各参加者によるYES 票(明示的または暗黙的) です。これは、投票する参加者がプロトコルの決定 (コミットまたは中止) に従う義務があることを意味します。それ以外の場合、参加者は明示的な NO 票によって一方的にトランザクションを中止できます。プロトコルは、すべての参加者から YES 票を受け取った場合にのみトランザクションをコミットします (したがって、欠落票は通常 NO と見なされます)。それ以外の場合、プロトコルはトランザクションを中止します。さまざまなアトミック コミット プロトコルは、さまざまなコンピューティング環境の障害状況を処理する能力と、さまざまな状況で必要な作業量およびその他のコンピューティング リソースが異なるだけです。

グローバル直列化可能性の CO ソリューション全体は、分散トランザクションの投票が欠落している場合に、アトミック コミットメント プロトコルが最終的にこのトランザクションを中止するという事実に基づいています。

グローバルCO2の施行

各データベースシステムでは、ローカルCOアルゴリズムがそのデータベースに必要なコミットメント順序を決定します。上記のCOの特性から、この順序は、ローカルデータアクセススケジューリングメカニズムによって決定されるトランザクションのローカルな優先順位に依存します。したがって、アトミックコミットメントプロトコルにおけるYES投票は、各（中止されていない）分散トランザクションに対してスケジュールされます（以下、「投票」はYES投票を意味します）。2つのトランザクション間に優先順位関係（衝突）が存在するとします。この場合、アトミックコミットメントプロトコルによるコミット順序違反を防ぐため、最初のトランザクションが完了（コミットまたは中止）するまで、2番目のトランザクションへの投票は行われません。これは、プロトコルによるコミット順序が投票順序と必ずしも一致しないためです。優先順位関係が存在しない場合は、両方のトランザクションに同時に投票が行われる可能性があります。この投票順序決定戦略は、アトミックコミットメントプロトコルがコミットメント順序を維持することを保証し、グローバルCO（およびデータベースのローカルCO。これがなければ、グローバルCOとローカルCO（各データベースがCO準拠であることを意味する特性）の両方に違反する可能性があります）を保証するための必要条件です。

しかし、データベースシステムはトランザクションを独立してスケジュールするため、2つ以上のデータベースにおけるトランザクションの優先順位が互換性を持たない可能性があります（それぞれのローカルな優先順位を組み込むことができるグローバルな優先順位は存在しません）。COでは、優先順位がコミットメント順序でもあります。同じ分散トランザクションに参加しているデータベースが、そのトランザクションに対して互換性のあるローカルな優先順位を持たない場合（「認識」していないにもかかわらず、通常はデータベースシステム間で競合に関する調整が行われません。必要な通信が膨大で、パフォーマンスが許容できないほど低下するためです）、そのトランザクションはグローバル競合グラフ内のグローバルサイクル（2つ以上のデータベースが関与する）上にあることを意味します。この場合、アトミックコミットメントプロトコルは、そのトランザクションをコミットするために必要なすべての投票を収集できません。上記の投票順序付け戦略により、少なくとも1つのデータベースは、自身のコミットメント（優先順位）順序に従うために、そのトランザクションへの投票を無期限に延期します。これは、そのグローバルサイクル上の別の先行トランザクションが、異なる順序を持つ別のデータベースによって無期限に延期されるのを待つことになるためです。これは、そのサイクル上のデータベース間で投票によるデッドロックが発生することを意味します。その結果、プロトコルは最終的に、このグローバルサイクル上のデッドロックしたトランザクションの一部を中止します。なぜなら、各トランザクションには少なくとも1人の参加者の投票が欠けているからです。サイクル上で中止する特定のトランザクションの選択は、アトミックコミットメントプロトコルの中止ポリシーに依存します（タイムアウトメカニズムが一般的ですが、サイクルごとに複数の中止が必要になる可能性があります。不要な中止の防止と中止時間の短縮は、CO専用の中止メカニズムによって実現できます）。このような中止は、その分散トランザクションを含むグローバルサイクルを中断します。デッドロックしたトランザクションと、デッドロックしたトランザクションと競合する可能性のある他のトランザクション（したがってブロックされているトランザクション）の両方に、自由に投票できます。投票デッドロックに関与する各データベースは、デッドロックしたトランザクションと競合しないトランザクション（通常はほぼすべての未処理トランザクション）に対して定期的に投票を継続することに注意してください。したがって、ローカル（部分的）コミットメント順序に互換性がない場合、アトミックコミットメントプロトコルは、互換性の問題の原因となっているトランザクションを中止することで自動的に解決するため、アクションは必要ありません。これは、上記の投票順序付け戦略がGlobal CO を保証するための十分な条件でもあることを意味します。

結論は以下のとおりです。

• グローバルCO強制定理のための投票順序戦略

ローカルトランザクションにCOを強制するデータベースシステムにおいて、未決定（コミットもアボートもされていない）トランザクションが であるとします。この場合、 はグローバルであり、と競合します（が先行します）。このとき、がコミットに投票される前に（コミットまたはアボートのいずれかで）終了していること（投票順序付け戦略）は、マルチデータベース環境における各データベースシステムにおいて、グローバルCOを保証するための必要十分条件です（ はグローバルCOを保証しますが、この条件がなければ違反する可能性があります）。${\displaystyle T_{1},T_{2}}$ ${\displaystyle T_{2}}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$

コメント:

1. グローバルCOを強制する投票順序付け戦略は、（Raz 1992）で言及されています。${\displaystyle CD^{3}C}$
2. グローバルスケジュールのローカルCOプロパティは、各データベースがCO準拠であることを意味します。必要性に関する議論から、上記の部分は、グローバルトランザクションが存在する場合に「グローバルCO」を「ローカルCO」に置き換えても定理が成り立つことを直接的に示しています。これらを合わせると、ローカルCOが保証される場合にのみ、グローバルCOが保証されることを意味します（これは、グローバル競合直列化可能性とローカル競合直列化可能性については当てはまりません。グローバルはローカルを意味しますが、その逆は当てはまりません）。

グローバル CO はグローバル直列化可能性を意味します。

グローバルCO アルゴリズムは、ローカル トランザクションのコミットを順序付けすることによって各参加データベース システムで (ローカル) CO を強制すること (以下の「ローカルでの CO の強制」を参照) と、上記の定理の投票順序付け戦略を強制すること(グローバル トランザクションの場合) で構成されます。

投票デッドロックの地球規模のサイクルによる正確な特徴づけ

上記の投票デッドロックによるグローバルサイクル排除プロセスは、次の観察によって詳細に説明できます。

まず、単純化のため、すべてのトランザクションがコミット準備完了状態に達し、少なくとも1つのデータベースによって投票されると仮定します（これは、ロックによるブロッキングが発生しないことを意味します）。「コミット投票待ち」グラフを、トランザクションをノードとし、任意の最初のトランザクションから2番目のトランザクションへの有向辺（最初のトランザクションが2番目のトランザクションのコミット投票をブロックする場合）を持つ有向グラフとして定義します（待機グラフにおける従来の辺の方向とは逆）。このようなブロッキングは、2番目のトランザクションが最初のトランザクションと競合する場合にのみ発生します（上記参照）。したがって、この「コミット投票待ち」グラフは、グローバル競合グラフと同一です。「コミット投票待ち」グラフのサイクルは、投票におけるデッドロックを意味します。したがって、競合グラフにサイクルがある場合、投票においてデッドロックが発生します。ローカル直列化メカニズムは、ローカルサイクル（単一のデータベースに限定）を排除します。その結果、グローバルサイクルのみが残り、アトミックコミットメントプロトコルが、それぞれの投票が欠落している（ブロックされている）デッドロック状態のトランザクションをアボートする際に、グローバルサイクルが排除されます。

次に、ローカル コミットも処理されます。CO を強制する場合、ローカル トランザクションの通常のローカル コミットを待機すると、競合時に他のトランザクションのローカル コミットと投票がブロックされる可能性があり、上記の単純化された仮定がなければグローバル トランザクションの状況も変化しないことに注意してください。最終結果は、ローカル トランザクションのローカル コミットメントでも同じであり、それらのアトミック コミットメントに投票する必要はありません。

最後に、これまで除外してきたロックによるブロッキングについて検討する必要があります。ロックは競合する操作をブロックし、競合の発生を防ぎます。トランザクション終了後にのみロックが解除されると仮定します。この場合、投票またはローカルコミットを直接ブロックした場合と同じ効果で、別のトランザクション（準備完了状態に移行できないトランザクション）の投票またはローカルコミットが間接的にブロックされる可能性があります。競合グラフにサイクルが生成されるのは、このようなロックによるブロッキングがエッジでも表現されている場合のみです。ロックによるブロッキングのイベントを表すエッジが追加されることで、競合グラフは拡張競合グラフになります。

• 定義: 拡張対立グラフ

拡張競合グラフは、エッジが追加された競合グラフです。元のエッジに加えて、次の 2 つの条件が満たされる場合、トランザクションからトランザクションへの有向エッジが存在します。${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$

1. ${\displaystyle T_{2}}$ によって適用されたデータアクセスロックによってブロックされている（ブロックにより、との競合が具体化され、通常の競合グラフにエッジを持つことが防止される）。${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$ ${\displaystyle T_{1}}$
2. このブロッキングは終了（コミットまたは中止）まで停止しません。これはロックベースの CO に当てはまります。${\displaystyle T_{1}}$

このグラフは、（通常の）衝突グラフと（反転エッジ、通常の）待機グラフの和集合として定義することもできる。

コメント:

1. ここでは、具体化された競合に対してのみエッジを持つ通常の競合グラフとは異なり、具体化された競合と非具体化された競合のすべてがエッジによって表されます。
2. 全ての新しいエッジは、wait-forグラフの（従来のものとは逆の）エッジであることに注意してください。wait -forグラフは、非実体化競合のグラフとしても定義できます。一般的な慣例により、競合グラフにおけるエッジの方向は、競合する操作間の時間順序を定義します。これは、wait-forグラフにおけるエッジによって定義される時間順序とは逆になります。
3. このようなグローバルグラフには、（逆エッジの）通常のローカル待機グラフがすべて含まれ（埋め込まれ）、さらにロックベースのグローバルサイクル（ローカルグラフには存在し得ない）も含まれる場合があることに注意してください。例えば、グローバルサイクル上のすべてのデータベースがSS2PLベースである場合、関連する投票ブロック状況はすべてロックによって引き起こされます（これは、データベース研究文献で扱われる古典的かつおそらく唯一のグローバルデッドロック状況です）。これは、関連する各データベースがサイクルの一部を作成するものの、完全なサイクルがどのローカル待機グラフにも存在しないグローバルデッドロックのケースです。

CO が存在する場合、拡張競合グラフは、実際には（反転エッジの）ローカルコミットおよび投票待機グラフとなります。つまり、2 番目のトランザクションが最初のトランザクションの終了を待機し、投票（グローバルの場合）またはローカルコミット（ローカルの場合）が行われるまで待機している場合、最初のトランザクション（ローカルまたはグローバル）から 2 番目のトランザクションへのエッジが存在します。このグラフ内の（2 つ以上のデータベースにまたがる）すべてのグローバルサイクルは、投票デッドロックを生成します。グラフのグローバルサイクルは、投票デッドロックの完全な特性を提供し、マテリアライズド競合と非マテリアライズド競合の任意の組み合わせを含むことができます。マテリアライズド競合のサイクルのみが、通常の競合グラフのサイクルでもあり、直列化可能性に影響を与えます。サイクル上の 1 つ以上の（ロック関連の）非マテリアライズド競合は、通常の競合グラフのサイクルになることを妨げ、ロック関連のデッドロックになります。グローバル直列化可能性を維持し、データアクセスロックを含むグローバルデッドロックを解決するには、すべてのグローバルサイクル（投票デッドロック）を解消する必要があります。実際、投票デッドロックによる投票の欠落により、それらはすべてアトミック コミットメント プロトコルによって破壊されます。

コメント：この観察は、以下の拡張CO（ECO）の正しさも説明しています。2つのグローバルトランザクション間に順序関係（グラフパス）が存在する場合、グローバルトランザクションの投票順序は、投票ブロックを伴う競合グラフ順序に従う必要があります。ローカルトランザクションは投票されず、競合時にローカルコミットがブロックされることもありません。これにより、ECOと同様の投票デッドロック状況が発生し、結果としてグローバルサイクルの排除プロセスが実現されます。

投票の行き詰まり状況は次のように要約できます。

• CO投票デッドロック定理

マルチデータベース環境が、各グローバル CO を強制する(上記の定理の条件を使用) CO 準拠の (ローカル サイクルを排除する) データベース システムで構成されているとします。投票デッドロックは、グローバル サイクル(2 つ以上のデータベースにまたがる) がグローバル拡張競合グラフ(データ アクセス ロックによるブロックもエッジで表されます) に存在する場合にのみ発生します。サイクルがアボートによって中断されないものとします。その場合、そのサイクル上のすべてのグローバルトランザクションが、それぞれの投票デッドロックに関係します。最終的には、それぞれの投票がブロックされます (データ アクセス ロックによって直接的または間接的に)。ローカル トランザクションがサイクルに存在する場合、最終的には、その (ローカル) コミットがブロックされます。

コメント:稀に、投票デッドロック（ブロックされた投票の欠落による）が発生することがあります。この状況では、関連するサイクルにおいて、これらのトランザクションに関与するデータベースシステムのいずれかが、どのトランザクションに対しても投票を行いません。これは、ローカルサブトランザクションがマルチスレッド化されている場合に発生する可能性があります。このような稀なイベントが発生する可能性が最も高いのは、2つのトランザクションが同時に2つの反対のサイクルで実行されている場合です。このようなグローバルサイクル（デッドロック）は、ローカルサイクルと重なり合います。ローカルサイクルはローカルに解決され、通常はアトミックコミットメントを伴わずにローカルメカニズムによって解決されます。形式的にはこれはグローバル サイクルでもありますが、実際にはローカル サイクルです (ローカル サイクルの一部がグローバル サイクルを生成します。これを確認するには、各グローバル トランザクション (ノード) をローカル サブトランザクション (それぞれが単一のデータベースに限定される部分) に分割します。各ローカル サブトランザクション間にエッジが存在する場合、トランザクション間には有向エッジが存在します。サイクルのすべてのエッジが同じデータベースのサブトランザクション間のサイクルから発生している場合、そのサイクルはローカルであり、そうでない場合はグローバルです。グローバルとローカルは重複できます。トランザクション間の同じサイクルが、サブトランザクション間の複数の異なるサイクルから発生する場合があり、ローカルとグローバルの両方になることがあります)。

また、次のロック ベースの特殊なケースが結論付けられます。

• COロックベースのグローバルデッドロック定理

CO準拠のマルチデータベースシステムにおいて、少なくとも1つのデータアクセスロック（非マテリアライズド競合）と2つ以上のデータベースシステムが関与するロックベースのグローバルデッドロックは、グローバル拡張競合グラフにおけるグローバルサイクルの反映であり、投票デッドロックを引き起こします。このようなサイクルは、（通常の）グローバル競合グラフ（マテリアライズド競合のみを反映するため、直列化可能性には影響しません）におけるサイクルではありません。

コメント:

1. サイクル内のデータアクセスロック以外のブロッキング（エッジ）は、投票またはローカルコミットのいずれかを直接ブロックします。このロックベースのタイプも含め、すべての投票デッドロックは解決されます（ほぼすべてアトミックコミットメントによって解決されます。上記のコメントを参照）。
2. ロックベースのグローバルデッドロックは、SS2PLベースの完全な分散環境（COベースの特殊なケース）でも発生する可能性があります。投票ブロッキング（および投票デッドロック）はすべて、データアクセスロックによって引き起こされます。長年にわたり、このようなグローバルデッドロックの解決方法について多くの研究論文が取り上げられてきましたが、アトミックコミットメントによって自動的に解決されることに注目した論文は（CO論文を除いて）2009年時点では存在しません。このような自動解決は、既存のSS2PLベースのマルチデータベースシステムにおいて、気づかれることなく定期的に発生しており、専用の解決メカニズムをバイパスしていることがよくあります。

投票デッドロックは分散 CO の動作の鍵となります。

グローバル サイクルの排除 (ここでは、アトミック コミットメントによる投票デッドロックの解決) と、その結果として中止されたトランザクションの再実行は、使用される同時実行制御に関係なく、時間がかかります。データベースがトランザクションを独立してスケジュールする場合、グローバル サイクルは避けられません (ローカル SS2PL で生成されるサイクル/デッドロックと完全に類似しています。分散では、トランザクションまたは操作のスケジュール調整によって自律性が侵害され、通常はパフォーマンスが大幅に低下します)。ただし、グローバル トランザクションに関連する競合の数を減らすデータベースおよびトランザクション設計ガイドラインを実装することで、多くの場合、その可能性を非常に低くすることができます。これは主に、ホット スポット (頻繁にアクセスされるデータベース オブジェクト) を適切に処理し、可能な場合は可換性を使用して競合を回避することによって行われます (たとえば、財務などのカウンターを多用する場合、特にマルチトランザクション累積カウンターは一般的にホット スポットになります)。

アトミックコミットメントプロトコルは、データベースの同時実行制御を考慮せずにアトミック性を実現することを目的として設計されています。これらのプロトコルは、欠落投票を検出またはヒューリスティックに発見（例えばタイムアウトによって、時には誤って、不必要に）すると中止しますが、通常はグローバルサイクルには気づきません。これらのプロトコルは、特にCO（以下のCOの派生版を含む）向けに拡張することで、不要な中止を防ぎ、グローバル拡張競合グラフにおけるグローバルサイクルの解消に使用される中止を加速できます（トランザクション終了時にコンピューティングリソースと通常はロックされているデータを早期に解放することで、パフォーマンスが向上します）。例えば、タイムアウト以外の既存のロックベースのグローバルデッドロック検出手法は、データアクセスブロッキングに加えて、ローカルコミットと投票による直接ブロッキングも考慮するように一般化できます。このようなメカニズムにおける妥協案としては、最も頻度が高く、比較的扱いやすい長さ2のグローバルサイクルを効果的に検出して解消し、検出されない頻度がはるかに低い長いサイクルにはタイムアウトを使用するというものがあります。

地域におけるCOの施行

コミットメント順序は、専用の CO アルゴリズム、または CO の特別なケースを提供する任意のアルゴリズム/プロトコルによって、ローカル（単一のデータベース内）で強制できます。データベース システムで広く利用され、CO スケジュールを生成する重要なプロトコルとして、強力で厳密な2 フェーズ ロックプロトコル (SS2PL: 「トランザクションがコミットまたは中止された後にのみトランザクションのロックを解除する」、以下を参照) があります。SS2PL は、2PLと厳密性の共通部分の適切なサブセットです。

汎用ローカルCOアルゴリズム

汎用ローカル CO アルゴリズム( Raz 1992、アルゴリズム 4.1) は、実装の詳細に依存しない、まさに CO プロパティを適用するアルゴリズムです。データ アクセスをブロックせず (非ブロッキング)、トランザクションのコミット時に特定のトランザクション セットを (必要な場合のみ) アボートします。ローカルで実行され、将来直列化違反を引き起こす可能性のある (競合グラフでコミット済みトランザクションのサイクルが後で生成される可能性がある、任意の時点で一意に決定される) その他の未決定の (コミット済みでもアボート済みでもない) トランザクションの最小セットをアボートします (これはコミット済みトランザクション T の ABORT セットです。T をコミットした後は、コミット時に ABORT 状態にあるトランザクションはコミットできず、すべてがアボートされる運命にあります)。このセットは、競合グラフ内でコミット済みトランザクションへの有向エッジを持つすべての未決定トランザクションで構成されます。したがって、そのトランザクションを完了するためのリアルタイム制約が存在しない限り、そのトランザクションのコミットを待機し、このセットのサイズが減少するのを待つことが望ましい。別の直列化メカニズムがローカルに存在する場合（ローカル競合グラフ内のサイクルが排除される）、またはそのトランザクションを含むサイクルが存在しない場合、セットは最終的に空になり、セットメンバーのアボートは不要になる。そうでない場合、セットはローカルサイクル上のトランザクションで安定し、サイクルを解消するためにセットメンバーのアボートが発生する。CO競合の場合、コミット時にブロッキングが発生するため、拡張競合グラフ（上記参照）内のローカルサイクルはローカルコミットデッドロックを示し、SS2PLのようなデッドロック解決手法（タイムアウトや待機グラフなど）を使用できる。拡張競合グラフ内のローカルサイクルに少なくとも1つの非マテリアライズド競合がある場合、ロックベースのデッドロックが反映される。上記のローカルアルゴリズムは、通常のローカル競合グラフではなくローカル拡張競合グラフに適用され、汎用的な拡張ローカルCOアルゴリズムを構成する。、単一のローカルサイクル排除メカニズム、ローカル直列化可能性の保証とロックベースのローカルデッドロックの処理の両方を行います。実際には、回復可能性を強化するためだけの場合でも、追加の並行性制御メカニズムが常に使用されます。汎用 CO アルゴリズムは、他のローカル並行性制御メカニズムと一緒に実行する場合、ローカルデータアクセススケジューリング戦略に影響を与えません。コミット順序にのみ影響するため、組み合わせたローカル並行性制御メカニズムによって直列性違反の防止のために中止する必要があるトランザクションよりも多くのトランザクションを中止する必要はありません。CO の正味の効果は、最大でも、必要なコミット順序に準拠するためのコミットイベント (または分散環境での投票) の遅延です (ただし、SS2PL などの特殊なケースよりも遅延は大きくなく、平均して大幅に少なくなります)。

次の定理が導き出される。

• 汎用ローカルCOアルゴリズム定理

データベースシステムで単独または並行制御メカニズムと併用して実行する場合、

1. 汎用ローカル CO アルゴリズムは、(ローカル) CO (CO 準拠スケジュール) を保証します。
2. 汎用拡張ローカルCOアルゴリズムは、（ローカル）COと（ローカル）ロックベースのデッドロック解決の両方を保証します。また、タイムアウトを使用せず、リアルタイムトランザクション完了制約が適用されていない場合、どちらのアルゴリズムも、必要最小限（トランザクション操作のスケジューリングによって決定されますが、アルゴリズムの範囲外です）を超えるトランザクションを中止することはありません。

例: 並行プログラミングとトランザクショナルメモリ

並行プログラミングとトランザクション メモリも参照してください。

マルチコアプロセッサの普及に伴い、汎用ローカルCOアルゴリズムの派生型は、並行プログラミング、トランザクショナルメモリ、特にソフトウェアトランザクショナルメモリにおいて、「コミット順序」による楽観的な直列化可能性の実現にますます利用されるようになっている（例えば、Ramadan et al. 2009、^{[ 4 ]} Zhang et al. 2006、^{[ 3 ]} von Parun et al. 2007 ^{[ 5 ]}）。COを利用した関連論文や特許は既に多数公開されている。

実装上の考慮事項: コミットメントオーダーコーディネーター (COCO)

マルチデータベース環境のデータベース システムを想定しています。ソフトウェア アーキテクチャの観点から、汎用 CO アルゴリズムをローカルに実装する CO コンポーネントであるコミットメント オーダー コーディネータ(COCO) は、(単一の) データベース システムとアトミック コミットメント プロトコル コンポーネント ( Raz 1991b )間の仲介者として簡単に設計できます。ただし、COCO は通常、データベース システムの不可欠な部分です。COCO の機能は、ローカル コミットメント オーダーに従って、準備完了のグローバル トランザクション (処理は終了しています) に対してコミットに投票すること、データベース システムがアボートを開始したトランザクションに対してアボートに投票すること (データベース システムはさまざまな理由でどのトランザクションに対してもアボートを開始できます)、およびアトミック コミットメントの決定をデータベース システムに渡すことです。ローカル トランザクション (識別できる場合) の場合、投票は必要ありません。コミットメント順序を決定するために、COCOは、未決定（コミットもアボートもしていない）トランザクションのローカル競合グラフ（またはロックデッドロックも捕捉するためのローカル拡張競合グラフ）の更新された表現をデータ構造として保持します（例えば、競合を捕捉するためにロックに類似したメカニズムを利用しますが、データアクセスのブロックは行いません）。COCOコンポーネントは、データベースシステムとのインターフェースを備えており、データベースシステムから「競合」、「準備完了」（処理終了。グローバルトランザクションへの投票またはローカルトランザクションのコミットの準備完了）、および「アボート」通知を受け取ります。また、アトミックコミットメントプロトコルとのインターフェースを備えており、各グローバルトランザクションに対するアトミックコミットメントプロトコルの決定を投票し、受け取ります。決定は、ローカルトランザクションのコミット通知と同様に、インターフェースを介して適切なコミット順序でCOCOからデータベースシステムに配信されます。インターフェースを含むCOCOは、COの別のバリエーション（後述）を実装したり、アトミックコミットメントにおける投票以外のデータベースの同時実行制御メカニズムで役割を果たしたりすることで、拡張可能です。

COCO は、アトミック コミットメント プロトコルとのインターフェイスを持たない単一の分離されたデータベース システムで、ローカルに CO を保証します。

CO は、自律型データベース システム全体にわたるグローバルなシリアル化可能性の必要条件です。

分散トランザクション (つまり、複数のデータベースにまたがるトランザクション) に参加するデータベースが、共有の同時実行制御情報を一切使用せず、変更されていないアトミック コミットメント プロトコル メッセージ (アトミック性を達成するために) を使用するとします。その場合、 (ローカル)コミットメント順序またはその一般化バリアントの 1 つ (以下を参照)を維持することは、グローバル シリアル化可能性を保証するための必要条件です (証明手法については ( Raz 1992 ) に、これに対する別の証明方法については ( Raz 1993a ) に記載されています)。また、十分条件でもあります。これは、シリアル化可能性とトランザクションの定義から導かれる数学的な事実です。つまり、CO に準拠していない場合、この条件 (アトミック コミット プロトコル メッセージ以外にデータベース間でローカルな同時実行制御情報が共有されない条件) では、グローバル シリアル化可能性は保証できません。アトミック コミットメントは、分散トランザクションの定義によって暗示されるように常に必要なため、分散トランザクションの最小要件です。

（Raz 1992）は、データベースの自律性と独立性を、追加のローカル知識を使用せずにこの要件に準拠することと定義しています。

• 定義: (同時実行制御ベースの)自律型データベースシステム

データベースシステムが自律的であるとは、変更されていないアトミックコミットメントプロトコルメッセージ以外の並行制御情報を他のエンティティと共有しないことを指します。また、並行制御において、競合以外のローカルな情報も使用しません（最後の文は明示的には示されていませんが、Raz 1992でのさらなる議論によって暗示されています）。

この定義を使用すると、次のことが結論付けられます。

• COと大域直列化可能性定理

1. マルチデータベース環境におけるすべての自律型データベース システム (またはトランザクション オブジェクト)の CO 準拠は、グローバル シリアル化可能性を保証するための必要条件です(CO がないと、グローバル シリアル化可能性に違反する可能性があります)。
2. すべてのデータベース システムにおける CO 準拠は、グローバル直列化可能性を保証するための十分な条件です。

しかし、上記の自律性の定義は、例えば、自律型データベースシステムがローカルトランザクション（単一のデータベースに限定される）をローカルトランザクションとして識別できないようにトランザクションがスケジュールされることを意味します。これは一部のトランザクションオブジェクトには現実的ですが、汎用データベースシステムには制限が厳しすぎて現実的ではありません。自律性にローカルトランザクションを識別する能力が加われば、より一般的な特性である拡張コミットメント順序（ECO、後述）への準拠がECOの必要条件となります。

( Raz 2009 )においてのみ、一般化された自律性の概念が意図された自律性の概念を捉えています。

• 定義: 一般化された自律性

データベース システムが、(変更されていない) アトミック コミット プロトコル メッセージ以外のローカル同時実行情報を他のデータベース システムと共有しない場合、そのデータベース システムは一般化された自律性プロパティを持ちます (ただし、ローカル情報はいずれも利用できます)。

この定義は、データベース同時実行制御のコンテキストで可能な最も広範な定義であると考えられます。また、CO とその一般化バリアント (投票順序付け (VO)。以下の CO バリアントを参照) のいずれか (有用:同時実行制御情報の配布なし) を合わせて、グローバル直列化可能性の必要条件となります (つまり、CO とその一般化バリアントの和集合は必要なセット VO であり、これには新しい未知の有用な一般化バリアントも含まれる可能性があります)。

まとめ

グローバルシリアル化可能性のコミットメント順序付け(CO) ソリューション (テクニック) は、次のように要約できます。

マルチデータベース環境内の各データベース(またはその他のトランザクション オブジェクト) が CO に準拠している場合、つまり、それぞれのトランザクションのローカル競合グラフ (直列化可能性グラフ) によって誘導されるローカル (データベースに対して)な部分順序に従って、ローカル トランザクションのコミットメントと (グローバル、分散) トランザクションへの投票をアトミック コミットメントプロトコルに配置すれば、グローバル COとグローバル直列化可能性が保証されます。データベースの CO 準拠は、ローカル競合直列化可能性に基づく同時実行制御メカニズムによって効果的に達成でき、トランザクションの実行プロセスやスケジュールには影響せず、中止することもありません。また、データベースの自律性も侵害されません。発生する唯一の低いオーバーヘッドは、競合の検出 (たとえば、ロックを使用するが、データ アクセスはブロックしない。他の目的でまだ検出されていない場合) と、競合に応じた投票とローカル トランザクションのコミットの順序付けです。

スケジュールクラスの包含：クラスAからクラスBへの矢印は、クラスAがクラスBを厳密に包含することを示します。クラス間に有向パスがない場合、クラスは比較不可能です。あるプロパティが、他のトランザクションで特定のイベントが発生するまでトランザクションのデータアクセス操作をブロックすることによってのみ強制できる場合、それは本質的にブロッキングです。( Raz 1992 )

2つ以上のデータベースの部分順序に互換性がない場合（グローバル部分順序がそれぞれのローカル部分順序を組み込むことができない場合）、グローバル競合グラフにグローバルサイクル（2つ以上のデータベースにまたがる）が生成されます。これはCOと相まって、投票がブロックされるサイクルを引き起こします。そのサイクル上のデータベースで投票デッドロックが発生します（ただし、各データベースで許可されている同時投票（通常は未処理の投票のほぼすべて）は引き続き実行されます）。この場合、アトミックコミットメントプロトコルは、そのグローバルサイクル上のブロックされたトランザクションに必要なすべての投票を収集できません。その結果、プロトコルは投票が不足している一部のトランザクションを中止します。これによりグローバルサイクルが中断され、投票デッドロックが解消され、関連するブロックされた投票が自由に実行できるようになります。グローバル競合グラフのグローバルサイクルが中断されることで、グローバルCOとグローバル直列化可能性が維持されます。したがって、ローカル（部分）コミットメント順序に互換性がない場合、アトミックコミットメントプロトコルは、非互換性の原因となっているトランザクションを中止することで自動的に解決するため、特別な措置は必要ありません。さらに、ロックによるグローバル デッドロック (少なくとも 1 つのデータ アクセスがブロックされている 拡張競合グラフ内のグローバル サイクル) により投票デッドロックが発生し、同じメカニズムによって自動的に解決されます。

関連するデータベースが（変更されていない）アトミックコミットメントプロトコルメッセージ以外の同時実行制御情報を共有していない場合、つまり、同時実行制御のコンテキストにおいてデータベースが自律的である場合、ローカルCOはグローバル直列化可能性を保証するための必要条件です。これは、自律型データベースにおけるすべてのグローバル直列化可能性ソリューションがCOに準拠する必要があることを意味します。そうでない場合、グローバル直列化可能性が侵害される可能性があります（したがって、高パフォーマンス環境では非常に急速に侵害される可能性があります）。

CO ソリューションは、共通の分散型アトミック コミットメント アーキテクチャを利用することで、パフォーマンスを低下させることなく、ネットワーク サイズとデータベースの数に合わせて拡張できます。

分散直列化可能性とCO

分散型CO

分散直列化可能性に対するCOソリューションが他の手法と大きく異なる点は、競合情報（例えば、ローカルな優先順位関係、ロック、タイムスタンプ、チケット）を分散して必要としない点です。これがCOソリューションの優れた効果を生み出しています。COソリューションでは、（既に使用されている）アトミックコミットメントプロトコルメッセージを（変更せずに）利用します。

（分散）システムで分散直列化可能性を実現する一般的な方法は、分散ロック マネージャ（DLM）を使用することです。分散環境でロック（非マテリアライズド競合）情報を通信する DLM は、通常、コンピュータと通信の遅延の影響を受け、システムのパフォーマンスが低下します。CO を使用すると、分散ロック マネージャを使用せずに、非常に一般的な条件下で分散直列化可能性を実現でき、マルチデータベース環境ですでに説明した利点が得られます。具体的には、信頼性、高パフォーマンス、スケーラビリティ、必要に応じて楽観的同時実行制御を使用できる、ネットワーク経由の競合情報関連通信がない（オーバーヘッドと遅延が発生する）、および分散デッドロックの自動解決などです。

すべての分散トランザクション システムは、分散トランザクション内のプロセス間の原子性 (コミットするか中止するか) を調整するために、何らかのアトミック コミットメント プロトコルに依存しています。また、通常、回復可能データ(トランザクションの制御下にあるデータ、例: データベース データ。スケジュールの回復可能性プロパティと混同しないでください) は、ローカル サブトランザクション (単一の場所、例:ネットワーク ノードにある分散トランザクションの部分) を処理する単一のトランザクション データ マネージャコンポーネント (リソース マネージャとも呼ばれます) によって直接アクセスされます。これは、これらのデータがトランザクション中に分散システム内の他のエンティティによって間接的にアクセスされる場合でも同様です (間接アクセスには、ローカル サブトランザクションを介した直接アクセスが必要です)。したがって、分散トランザクション システム内の回復可能データは通常、トランザクション データ マネージャ間で分割されます。このようなシステムでは、通常、これらのトランザクション データ マネージャは、システムのアトミック コミットメント プロトコルの参加者を構成します。各参加者がCOに準拠している場合（例えば、SS2PL、COCO、またはそれらの組み合わせを使用。上記参照）、分散システム全体がCO（上記の定理により、各参加者は個別のトランザクションオブジェクトと見なすことができます）を提供し、それによって（分散）直列化可能性を実現します。さらに、COをアトミックコミットメントプロトコルと併用すると、データアクセスロックによって引き起こされる分散デッドロック（つまり、複数のデータマネージャにまたがるデッドロック）も自動的に解決されます。したがって、以下の系が導き出されます。

• COベースの分散直列化可能性定理

分散トランザクションシステム（例えば、分散データベースシステム）が、システムの回復可能なデータすべてを管理するトランザクションデータマネージャ（リソースマネージャとも呼ばれる）で構成されているとします。データマネージャは、以下の3つの条件を満たします。

1. データ パーティション:回復可能なデータはデータ マネージャー間で分割されます。つまり、回復可能な各データ (データ項目) は単一のデータ マネージャーによって制御されます (たとえば、Shared Nothing アーキテクチャで一般的です。異なるデータ マネージャーの下にある同じデータのコピーであっても、物理的に区別され、複製されます)。
2. アトミック コミットメント プロトコルの参加者:これらのデータ マネージャーは、分散トランザクションのアトミック性を調整するためのシステムのアトミック コミットメント プロトコルの参加者です。
3. CO 準拠:このような各データ マネージャーは CO に準拠しています (または一部の CO バリアントに準拠しています。以下を参照)。

それから

1. 分散システム全体は（分散COと）直列化可能性を保証し、
2. データ アクセス ベースの分散デッドロック(少なくとも 1 つの非マテリアライズド競合を伴う 2 つ以上のデータ マネージャーが関与するデッドロック) は自動的に解決されます。

さらに、データ マネージャーが CO 準拠であることは、データ マネージャーが自律的である場合、つまり、アトミック コミットメント プロトコルの変更されていないメッセージを超えて同時実行制御情報を共有しない場合、上記の条件1、2 を満たすシステムで (分散)直列化可能性を実現するための必要条件です。

この定理はまた、SS2PL（またはその他のCOバリアント）が各トランザクションデータマネージャでローカルに使用され、各データマネージャがデータの排他制御権を持つ場合、分散SS2PLと直列化可能性のために分散ロックマネージャ（分散SS2PLを強制するためによく利用される）が不要であることを意味します。これは幅広い分散トランザクションアプリケーションに関連しており、定理の条件を満たすように容易に設計できます。

分散型楽観的CO（DOCO）

分散楽観的CO（DOCO）を実装するために、システム内のすべてのアトミックコミットメントプロトコル参加者において、汎用的なローカルCOアルゴリズムが利用されます。これにより、データアクセスのブロッキングは発生せず、ローカルデッドロックも発生しません。前述の定理には以下の系が成り立ちます。

• 分散楽観的CO（DOCO）定理

DOCO が利用される場合、次のようになります。

1. ローカルデッドロックは発生せず、
2. グローバル (投票) デッドロックは自動的に解決されます (すべては、ロック関連 (ブロッキング競合および場合によっては非ブロッキング競合) ではなく、シリアル化関連 (非ブロッキング競合) です)。

したがって、デッドロック処理は必要ありません。

例

分散SS2PL

SS2PLを利用する分散データベースシステムは、2 つのリモートノード A と B 上に存在します。データベースシステムには、各ノードに 1 つずつ、合計 2 つのトランザクションデータマネージャ（リソースマネージャ）が存在します。データベースデータは、2 つのデータマネージャ間で分割され、各マネージャが自身の（ノードにローカルな）データ部分を排他的に制御します。つまり、各マネージャは、他のマネージャのデータとロックについて一切認識することなく、独自のデータとロックを処理します。分散トランザクションごとに、これらのデータマネージャは利用可能なアトミックコミットメントプロトコルを実行する必要があります。

2 つの分散トランザクションとが同時に実行されており、両方ともデータ x と y にアクセスします。x は A のデータ マネージャーの排他的制御下にあり (B のマネージャーは x にアクセスできません)、y は B のデータ マネージャーの排他的制御下にあります。 ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$

${\displaystyle T_{1}}$ A で x を読み取り、B で y を書き込みます。つまり、同時実行制御に共通する表記法を使用する場合です。${\displaystyle T_{1}=R_{\text{1A}}(x)}$ ${\displaystyle W_{\text{1B}}(y)}$

${\displaystyle T_{2}}$ Bでyを読み取り、Aにxを書き込む、つまり、${\displaystyle T_{2}=R_{\text{2B}}(y)}$ ${\displaystyle W_{\text{2A}}(x)}$

A と B のそれぞれのローカルサブトランザクション(各ノード のとの部分) は次のとおりです。${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$

ローカルサブトランザクション

ノード 取引	あ	B
${\displaystyle T_{1}}$	${\displaystyle T_{\text{1A}}=R_{\text{1A}}(x)}$	${\displaystyle T_{\text{1B}}=W_{\text{1B}}(y)}$
${\displaystyle T_{2}}$	${\displaystyle T_{\text{2A}}=W_{\text{2A}}(x)}$	${\displaystyle T_{\text{2B}}=R_{\text{2B}}(y)}$

ある時点での データベース システムのスケジュールは次のとおりです。

${\displaystyle R_{\text{1A}}(x)}$ ${\displaystyle R_{\text{2B}}(y)}$

（も可能です）${\displaystyle R_{\text{2B}}(y)}$ ${\displaystyle R_{\text{1A}}(x)}$

${\displaystyle T_{1}}$ はxに読み取りロックを保持し、yにも読み取りロックを保持しています。したがって、とSS2PLのロック互換性規則によってブロックされ、実行できません。これは分散デッドロック状況であり、長さ2（エッジ数、競合数。2は最も頻繁に発生する長さ）の分散（グローバル）サイクルを持つ投票デッドロック（下記参照）でもあります。ローカルサブトランザクションは以下の状態にあります。 ${\displaystyle T_{2}}$ ${\displaystyle W_{\text{1B}}(y)}$ ${\displaystyle W_{\text{2A}}(x)}$

${\displaystyle T_{\text{1A}}}$ 準備完了（実行終了）かつ投票済み（アトミックコミットメント）

${\displaystyle T_{\text{1B}}}$ 実行中であり、ブロックされています（非具体化された競合状況であり、投票は発生しません）

${\displaystyle T_{\text{2B}}}$ 準備が整い、投票済み

${\displaystyle T_{\text{2A}}}$ 実行中であり、ブロックされています (非具体化された競合、投票なし)。

アトミックコミットメントプロトコルは、ブロックされたサブトランザクションへの投票を受け付けることができないため（投票デッドロック）、投票が不足しているトランザクションは、タイムアウト、 、 のいずれか（タイムアウトが非常に近い場合は両方）によって最終的に中止されます。これにより、グローバルデッドロックは解消されます。残りのトランザクションは実行を完了し、投票が行われ、コミットされます。中止されたトランザクションは直ちに再開され、再実行されます。 ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$

コメント

1. データパーティション（A上のx、B上のy）は重要です。なぜなら、これがないと、例えばBからxに直接アクセスできてしまうからです。あるトランザクションがB上で、およびと同時に実行されており、xに直接書き込みを行う場合、分散ロックマネージャがなければ、A上で保持されているxの読み取りロックはB上では参照できず、書き込みをブロックすることもできません（または、非ブロッキングCOバリアントの場合は、マテリアライズドコンフリクトを通知します。後述）。したがって、直列化可能性が侵害される可能性があります。${\displaystyle T_{3}}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{3}}$
2. データパーティションのため、Bからxに直接アクセスすることはできません。ただし、機能に制限はなく、Bで実行されているトランザクションはxへの書き込みまたは読み取りリクエストを発行できます（ただし、これは一般的ではありません）。このリクエストは、A上のトランザクションのローカルサブトランザクション（まだ存在しない場合は生成されます）に伝達され、A上のローカルデータマネージャにリクエストが発行されます。

バリエーション

上記のシナリオでは、両方の競合が非マテリアライズドであり、グローバル投票デッドロックがグローバル待機グラフ内のサイクルとして反映されています(ただし、グローバル競合グラフには反映されていません。上記の「グローバルサイクルによる投票デッドロックの正確な特徴付け」を参照してください)。ただし、データベース システムは、まったく同じ競合と投票デッドロックの状況、および同じ解決策で任意の CO バリアントを利用できます。競合は、使用する CO バリアントによって、マテリアライズドまたは非マテリアライズド になります。たとえば、分散データベース システムで SS2PL の代わりにSCO (下記) を使用する場合、例の 2 つの競合はマテリアライズドになり、すべてのローカル サブトランザクションは準備完了状態になり、2 つのトランザクション (各ノードで 1 つ) で投票ブロックが発生します。これは、A と B の両方に独立して適用される CO 投票ルールが原因です。競合が原因で は終了前に投票されず、 は終了前に投票されないため、投票デッドロックになります。これで、衝突グラフにグローバルサイクル（すべての衝突がマテリアライズド化される）が形成され、再びアトミックコミットメントプロトコルによって解決され、分散直列化可能性が維持されます。分散データベースシステムではあり得ませんが、原理的には可能であり（マルチデータベースでは実際に発生します）、AはSS2PLを使用し、BはSCOを使用できます。この場合、グローバルサイクルは待機グラフにも直列化可能性グラフにも存在しませんが、拡張衝突グラフ（両者の結合）に存在します。様々な組み合わせを以下の表にまとめます。 ${\displaystyle T_{\text{2A}}=W_{\text{2A}}(x)}$ ${\displaystyle T_{\text{1A}}=R_{\text{1A}}(x)}$ ${\displaystyle T_{\text{1B}}=W_{\text{1B}}(y)}$ ${\displaystyle T_{\text{2B}}=R_{\text{2B}}(y)}$

投票の膠着状態

場合	ノードA	ノードB	可能なスケジュール	サイクル上の衝突の具体化	非物質的紛争	${\displaystyle T_{\text{1A}}=R_{\text{1A}}(x)}$	${\displaystyle T_{\text{1B}}=W_{\text{1B}}(y)}$	${\displaystyle T_{\text{2A}}=W_{\text{2A}}(x)}$	${\displaystyle T_{\text{2B}}=R_{\text{2B}}(y)}$
1	SS2PL	SS2PL	${\displaystyle R_{\text{1A}}(x)R_{\text{2B}}(y)}$	0	2	投票済み	実行中（ブロック）	実行中（ブロック）	投票 済み
2	SS2PL	SCO	${\displaystyle R_{\text{1A}}(x)R_{\text{2B}}(y)W_{\text{1B}}(y)}$	1	1	投票済み	準備完了投票がブロックされました	実行中（ブロック）	投票 済み
3	SCO	SS2PL	${\displaystyle R_{\text{1A}}(x)R_{\text{2B}}(y)W_{\text{2A}}(x)}$	1	1	投票済み	実行中（ブロック）	準備完了投票がブロックされました	投票 済み
4	SCO	SCO	${\displaystyle R_{\text{1A}}(x)R_{\text{2B}}(y)W_{\text{1B}}(y)W_{\text{2A}}(x)}$	2	0	投票済み	準備完了投票がブロックされました	準備完了投票がブロックされました	投票 済み

コメント:

1. 拡張競合グラフにおける競合、ひいてはサイクルは、使用される同時実行制御とは無関係に、トランザクションとその初期スケジュール設定によってのみ決定されます。COのどのバリアントでも、グローバルサイクル（つまり、2つ以上のデータベースにまたがるサイクル）は投票デッドロックを引き起こします。COのバリアントによって、特定の競合がマテリアライズドかノンマテリアライズドかが異なる場合があります。
2. 上記のスケジュールでは、トランザクション内の順序によって制約され、一部の限定的な操作順序の変更が可能ですが、このような変更によってテーブルの残りの部分は変更されません。
3. 前述の通り、ケース4のみが（通常の）競合グラフにおけるサイクルを記述しており、直列化可能性に影響を与えます。ケース1～3は、ロックに基づくグローバルデッドロックのサイクル（少なくとも1つのロックブロッキングが存在）を記述しています。すべてのサイクルタイプは、アトミックコミットメントプロトコルによって同様に解決されます。ケース1は、1980年代から利用されている一般的な分散SS2PLです。しかし、2009年現在、CO論文を除いて、このロックによるグローバルデッドロックの自動解決に注目した研究論文は知られていません。このようなグローバルデッドロックは通常、専用のメカニズムによって処理されてきました。
4. 上記のケース 4 は、分散楽観的 CO (DOCO)が使用される場合の一般的な投票デッドロックの例でもあります(つまり、楽観的 CO (OCO、下記参照) が A と B の両方で SCO に置き換わってもケース 4 は変わりません)。データ アクセスのブロックは発生せず、具体化された競合のみが存在します。

仮想マルチシングルスレッドコア（MuSiC）環境

コメント:上記の例は CO の実際の推奨利用方法を説明していますが、この例はデモンストレーションのみを目的とした仮説的なものです。

いくつかの実験的な分散メモリ常駐データベースは、マルチシングルスレッドコア（MuSiC）トランザクション環境を推奨しています。「シングルスレッド」とは、トランザクションスレッドのみ、およびトランザクションのシリアル実行を指します。その目的は、同一コア上の複数スレッドによる従来のトランザクション実行と比較して、桁違いの性能向上（例えば、H-Store ^{[ 6 ]}やVoltDB）を実現することです。以下で説明するMuSiCは、コアの分散方法に依存しません。コアは1つの集積回路（チップ）内に存在する場合もあれば、複数のコンピュータに地理的に分散された複数のチップに存在する場合もあります。このような環境では、回復可能な（トランザクション）データがスレッド（コア）間で分割され、前のセクションで説明した分散COの従来の方法で実装されていれば、DOCOと厳密性が自動的に実現されます。しかし、このような環境の単純な実装には欠点があり、汎用ソリューションとしての実用性には疑問が残ります。一方で、ほとんどの状況でこれらの欠点を回避できるアプリケーションでは、驚異的な性能向上を実現できます。

コメント:ここで説明する MuSiC の簡単な実装 (たとえば、分散 CO で通常どおり、必要に応じてアトミック コミットメント プロトコルで投票 (およびトランザクション スレッド) ブロックを使用する) はデモンストレーションのみを目的としており、H-Store や他のプロジェクトの実装とは 関係ありません。

MuSiC環境では、ローカルスケジュールはシリアルです。したがって、ローカル楽観的CO（OCO、下記参照）と、アトミックコミットメントプロトコルにおけるグローバルCO強制投票順序戦略条件の両方が自動的に満たされます。これにより、分散CO準拠（したがって分散シリアル化可能性）と、自動的なグローバル（投票）デッドロック解決の両方が実現されます。

さらに、直列スケジュールでは局所的な厳密性も自動的に保証されます。Raz 1992 ; 307ページの定理5.2によれば、CO投票順序付け戦略を適用すると、大域的な厳密性も保証されます。なお、局所的な直列スケジュールは、厳密性と「楽観的」（データアクセスのブロッキングがない）を同時に実現できる唯一のモードです。

結論は以下のとおりです。

• MuSiC定理

MuSiC環境では、回復可能な（トランザクション）データがコア（スレッド）間で分割されている場合、

1. OCO（および暗黙の直列化可能性、つまりDOCOと分散直列化可能性）
2. 厳格さ（効果的な回復を可能にする；1と2は厳密なCOを意味する—下記のSCOを参照）および
3. （投票による）デッドロック解決

使用されるコアの数に無制限のスケーラビリティを備え、自動的にグローバルに存在します。

コメント:ただし、特別な処理が必要となる 2 つの大きな欠点が存在する可能性があります。

1. グローバルトランザクションのローカルサブトランザクションはコミットまでブロックされ、それぞれのコアがアイドル状態になります。これにより、ローカルサブトランザクションのスケジューリングにおいて、すべてのサブトランザクションをほぼ同時に、かつ近い時間で実行しようとしたとしても、コアの使用率が大幅に低下します。この問題は、グローバルトランザクションの実行をコミットから切り離すこと（何らかのアトミックコミットメントプロトコルを使用）によって回避できますが、連鎖的なアボートが発生する可能性があります。
2. 回復可能なデータの量（データベース サイズ）に応じてコア数を増やすと、コアあたりの（パーティション化された）データの平均量が減少します。これにより、データ使用率の分布によっては、一部のコアがアイドル状態になり、他のコアが非常にビジー状態になる可能性があります。また、ローカル（コア単位）トランザクションが必要なデータに到達するためにグローバル（マルチコア）になる場合があり、追加のオーバーヘッドが発生します。したがって、コア数が増加するにつれて、各コアに割り当てられるデータの量とタイプは、データ使用量に応じてバランスをとる必要があります。そうすることで、コアが過負荷になってボトルネックになることも、ビジー状態のシステムで頻繁にアイドル状態になって十分に活用されないこともありません。もう 1 つの考慮事項は、通常同じトランザクションによってアクセスされるすべてのデータを同じコア パーティションに配置することです（可能な場合）。これにより、ローカル トランザクションの数を最大化し（グローバルな分散トランザクションの数を最小化します）。これは、負荷分散（データ アクセス分散）とトランザクションによるデータ使用パターンに基づいて、コア間で時折データを再パーティション化することで実現できます。この欠点を大幅に軽減するもう 1 つの方法は、読み取り専用のグローバル トランザクションが (使用パターンに応じて) 完全に回避され、レプリケーションの変更が専用のコミット メカニズムによって同期されるように、いくつかのコア パーティション間で適切な物理データ レプリケーションを行うことです。

COバリアント：特殊なケースと一般化

特殊なケースのスケジュール プロパティ クラス (たとえば、以下の SS2PL および SCO) は、CO クラスに厳密に含まれています。一般化クラス (ECO および MVCO) は、CO クラスを厳密に含みます (つまり、CO 準拠でないスケジュールも含みます)。一般化バリアントは、ローカル同時実行制御情報を配布することなくグローバルな直列化可能性も保証します (各データベースには、一般化された自律性プロパティがあり、ローカル情報のみを使用します)。その一方で、CO 制約を緩和し、追加の (ローカル) 情報を使用することで同時実行性とパフォーマンスを向上させます。ECO はトランザクションがローカルである (つまり、単一のデータベースに限定されている) という知識を使用し、MVCO はデータ バージョン値の可用性を使用します。CO と同様に、両方の一般化バリアントは非ブロッキングであり、どのトランザクションの操作スケジュールにも干渉せず、関連する同時実行制御メカニズムとシームレスに組み合わせることができます。

COバリアントという用語は、一般的にCO、ECO、MVCO、またはそれらと関連する同時実行制御メカニズムやプロパティ（マルチバージョンベースのECO、MVECOを含む）を組み合わせたものを指します。これ以外の汎用バリアント（ローカル同時実行制御情報の分散なしにグローバルな直列化可能性を保証するもの）は知られていませんが、発見される可能性があります。

強力な厳密な2相ロック（SS2PL）

強力厳密二相ロック（SS2PL、厳密性または厳密スケジューリングとも呼ばれる）とは、トランザクションの読み取りロックと書き込みロックの両方が、トランザクションが終了（コミットまたはアボート）した後にのみ解除されることを意味します。SS2PLスケジュールの集合は、 COスケジュールの集合の適切なサブセットです。この特性はデータベースシステムで広く利用されており、COを暗黙的に含んでいるため、SS2PLを使用しグローバルトランザクションに参加するデータベースは、シリアル化可能なグローバルスケジュールをまとめて生成します（マルチデータベース環境におけるアトミック性に必要なアトミックコミットメントプロトコルを使用する場合）。この場合、CO分散ソリューションに参加するためにデータベースの変更や追加は必要ありません。上記のローカル汎用COアルゴリズムにおいてコミット前にアボートされる未決定トランザクションの集合は、ロックが存在するため空であり、したがってこの場合はそのようなアルゴリズムは不要です。トランザクションは、「準備完了」状態、つまりローカルでタスクの実行を完了した直後に、データベースシステムによって投票できます。そのロックは、アトミック コミットメント プロトコルによって決定された後にのみデータベース システムによって解放されるため、上記のグローバル CO 強制定理の条件は自動的に維持されます。データベース システムがローカル タイムアウト メカニズムを使用して (ローカル) SS2PL デッドロックを解決する場合、ブロックされたトランザクションを中止すると、グローバル競合グラフ内の潜在的なローカル サイクル (拡張競合グラフ内の実際のサイクル) が破壊されるだけでなく、アトミック コミットメントプロトコルの中止メカニズムが比較的遅い場合は、副作用としてデータベース システムの潜在的なグローバル サイクルも破壊されます。複数のエンティティによるこのような独立した中止は通常、グローバル サイクルごとに複数のトランザクションで不要な中止が発生する可能性があります。ローカルの待機グラフベースのメカニズムの場合は状況が異なります。このようなメカニズムではグローバル サイクルを識別できず、結果として生じる投票デッドロックが別のデータベースで以前に解決されない場合、アトミック コミットメント プロトコルはグローバル サイクルを破壊します。

ローカルSS2PLとアトミックコミットメント（グローバル直列化可能性を示唆）の組み合わせは、直接的に推論することもできます。分散トランザクションを含むすべてのトランザクションは、2PL（SS2PL）ルールに従います。アトミックコミットメントプロトコルメカニズムは、ここではコミット時のコンセンサスではなく、フェーズ2の同期ポイントの終了時に必要です。おそらくこのため、アトミックコミットメント投票メカニズムを考慮せずに、自動グローバルデッドロック解決がCO以前には注目されていませんでした。

厳格なCO（SCO）

読み取り書き込み競合：SCO vs. SS2PL。トランザクションT2の所要時間は、SS2PLの方がSCOよりも長くなります。SS2PLは、読み取り操作r1[x]に続いてT1がxをロックするため、T1がコミットするまでT2の書き込み操作w2[x]を遅延させます。トランザクションT2が書き込み操作w2[x]を開始してから準備完了状態に達するまでにt時間単位かかる場合、T2はT1のコミットからt時間単位後にコミットします。しかし、SCOはw2[x]をブロックしないため、T2はT1のコミット直後にコミットできます。( Raz 1991c )

ストリクト・コミットメント・オーダリング（SCO; ( Raz 1991c )）は、厳密性（回復可能性の特殊なケース）とCOの交点であり、両方の特性が共存する場合にスケジュールの同時実行性の上限を提供します。SCOは、一般的なSS2PLで使用されるブロッキング機構（ロック）と同様のオーバーヘッドで実装できます。

SS2PL とは異なり、SCO は読み取り/書き込み競合ではブロックしませんが、代わりにコミット時にブロックする可能性があります。SCO と SS2PL は、書き込み/読み取り、および書き込み/書き込みという他の 2 つの競合タイプでは同一のブロッキング動作を行います。その結果、SCO は平均ブロッキング期間が短く、同時実行性が高くなっています (たとえば、順序付き共有を使用したロックの最も重要なバリアント( SCO と同一) の単一データベースのパフォーマンス シミュレーションはこれを明確に示しており、一部のトランザクション負荷で約 100% の向上が見られます。また、同一のトランザクション負荷では、ロックスラッシングが発生するまで、SCO は SS2PL よりも高いトランザクション レートを達成できます)。同時実行性が高いということは、与えられたコンピューティング リソースで、単位時間あたりに完了するトランザクションが多くなり (トランザクション レート、スループットが高くなる)、トランザクションの平均期間が短くなる (完了が速くなる、グラフを参照) ことを意味します。SCO の利点は、ロック競合時に特に顕著になります。

• SCO対SS2PLパフォーマンス定理

読み取り/書き込み競合が存在する場合、SCO は SS2PL よりも平均トランザクション完了時間が短くなります。それ以外の点では、SCO と SS2PL は同じです (書き込み/読み取り競合および書き込み/書き込み競合でのブロッキング動作は同じです)。

SCOはSS2PLと同様に実用的です。SS2PLと同様に、SCOは直列化可能性に加えて厳密性も備えており、これはデータベース障害からの効率的な復旧の基盤として広く利用されています。SS2PLのメカニズムは、復旧方法を変更することなく、簡単にSCOのメカニズムに変換してパフォーマンスを向上させることができます。SCOの実装については、(Perrizo and Tatarinov 1998)を参照してください。^{[ 7 ]}半楽観的データベーススケジューラも参照してください 。

SS2PL は SCO の適切なサブセットです (これが、SCO が SS2PL よりも制約が少なく、より多くの同時実行性を提供するもう 1 つの理由です)。

楽観的CO（OCO）

楽観的コミットメント順序付け（OCO）を実装するために、データアクセスのブロッキング、つまりローカルデッドロックなしで汎用的なローカルCOアルゴリズムが利用されます。トランザクションや操作のスケジュール制約のないOCOは、COクラス全体をカバーしており、COクラスの特殊なケースではなく、むしろCOの有用なバリアントであり、メカニズムの特性評価です。

拡張CO（ECO）

ECOの一般的な特徴

拡張コミットメント順序（ECO; ( Raz 1993a )）はCOを一般化します。ローカルトランザクション（単一のデータベースに限定されたトランザクション）とグローバル（分散）トランザクション（2つ以上のデータベースにまたがるトランザクション）を区別できる場合、コミットメント順序はグローバルトランザクションにのみ適用されます。したがって、ローカル（データベース）スケジュールがECO特性を持つためには、グローバルトランザクション（ローカルトランザクションには重要ではない）のコミットイベントの時系列（部分的）順序が、それぞれのローカル競合グラフ上の順序と一致している必要があります。

• 定義: 拡張コミットメント発注

スケジュールにおいて、コミット済みのグローバルトランザクションが2つあるとします。この場合、競合グラフ（優先順位グラフ）において、中止されていないトランザクションの有向パスが からまで（が に先行し、推移的に 、間接的に が先行する可能性があります）存在します。このようなトランザクション2つごとに がより前にコミットされる場合、スケジュールは拡張コミットメント順序付け（ECO）プロパティを持ちます。${\displaystyle T_{1},T_{2}}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$

グローバルECOを保証する分散アルゴリズムが存在します。COの場合と同様に、このアルゴリズムは（変更されていない）アトミックコミットメントプロトコルメッセージのみを必要とします。グローバルな直列化可能性を保証するためには、各データベースは、任意の（ローカルな）同時実行制御メカニズムによって、自身のトランザクションの競合直列化可能性も保証する必要があります。

• ECOと大域直列化可能性定理

1. (ローカル、つまりグローバルを意味する) ECO は、ローカル競合の直列化可能性と組み合わせることで、グローバル競合の直列化可能性を保証するための十分な条件となります。
2. アトミックコミットメントメッセージ以外の同時実行制御情報がデータベース外部で共有されず（自律性）、ローカルトランザクションを識別できる場合も、必要な条件です。

必然性の証明については（Raz 1993a）を参照。

この条件 (ローカル直列化可能性を備えた ECO) は CO よりも弱く、少し複雑なローカル アルゴリズムを犠牲にして、より多くの同時実行が可能になります (ただし、CO との実質的なオーバーヘッドの違いは存在しません)。

すべてのトランザクションがグローバルであると想定される場合 (たとえば、トランザクションがローカルであるかどうかに関する情報がない場合)、ECO は CO に縮小されます。

ECOアルゴリズム

グローバル トランザクションがコミットされる前に、汎用ローカル (データベースに対して) ECO アルゴリズムが、最小の未決定トランザクション セット (コミットも中止もされていない、ローカル トランザクションまたはローカルで実行されるグローバル トランザクション) を中止します。この未決定トランザクション セットは、後で競合グラフでサイクルを引き起こす可能性があります。この中止されたトランザクション セット (CO とは異なり、一意ではありません) は、各トランザクションに重み (トランザクションの重要性と、実行中のトランザクションにすでに費やされているコンピューティング リソースによって決定できます。最適化は、たとえば、ネットワークの最大フロー問題 ( Raz 1993a ) からの削減によって実行できます) が割り当てられている場合は最適化できます。CO と同様に、このようなセットは時間に依存し、最終的には空になります。実際には、必要な実装のほぼすべてにおいて、セットが空の場合にのみトランザクションをコミットする必要があります (セットの最適化は適用できません)。ローカル（データベースに対して）同時実行制御メカニズム（ECO アルゴリズムとは別）は、ローカル サイクルが確実に排除されるようにします（CO とは異なり、CO はそれ自体で直列化可能性を意味しますが、実際には CO でも、少なくとも回復可能性を確保するためにローカル同時実行メカニズムが利用されます）。ローカル トランザクションは常に同時にコミットできます（CO とは異なり、優先順位が存在する場合でも）。トランザクション全体のローカル部分順序（これはローカル競合グラフによって決定されますが、ローカル直列化可能性メカニズムによってサイクルが排除されるため、一時的なローカル サイクルのみが可能です）が許せば、グローバル トランザクションも同時にコミットされるように投票できます（推移的に（間接的に）先行する（競合を介して）グローバルトランザクションがすべてコミットされる場合、一方、推移的に先行するローカル トランザクションはどの状態であってもかまいません。これは、推移的に先行するトランザクションがすべてコミットされる必要がある、分散 CO アルゴリズムのより強力な同時投票条件に似ています）。

グローバル ECOを保証するための条件は、CO と同様に要約できます。

• グローバルECO強制投票順序戦略定理

ローカルに直列化可能性を保証するデータベース システムで、未決定（コミットも中止もされていない）のグローバル トランザクションがあるとします。この場合、ローカル競合グラフ（データベース自体のグラフ）に、 から まで、中止されていないトランザクションの有向パスが存在します。このとき、マルチデータベース環境のこのようなすべてのデータベース システムにおいて、 がコミット対象として投票される前に が終了（コミットまたは中止のいずれか）していることは、グローバル ECO を保証するための必要十分条件です（この条件はグローバル ECO を保証しますが、この条件がないと違反する可能性があります）。${\displaystyle T_{1},T_{2}}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$

グローバルECO（グローバル競合グラフ内のすべてのグローバルサイクルがアトミックコミットメントによって排除される）とローカル直列化可能性（つまり、各データベースシステムがローカルに直列化可能性を維持し、すべてのローカルサイクルが排除される）を組み合わせると、グローバル直列化可能性（すべてのサイクルが排除される）が実現されます。つまり、マルチデータベース環境内の各データベースシステムが（任意のメカニズムによって）ローカル直列化可能性を提供し、上記の定理（COの投票順序付け戦略の一般化）の投票順序付け戦略を強制する場合、グローバル直列化可能性が保証されます（ローカルCOは不要になります）。

CO と同様に、ECO の投票デッドロック状況は次のように要約できます。

• ECO投票デッドロック定理

マルチデータベース環境が、それぞれがグローバル ECO (上記の定理の条件を使用) とローカル競合直列化可能性(グローバル競合グラフ内のローカルサイクルを排除) の両方を実施するデータベースシステムで構成されているとします。すると、投票デッドロックは、グローバル拡張競合グラフ(データアクセス ロックによるブロックもエッジで表されます) にグローバルサイクル(2 つ以上のデータベースにまたがる) が存在する場合にのみ発生します。サイクルがアボートによって中断されない場合、そのサイクル上のすべてのグローバルトランザクションがそれぞれの投票デッドロックに関係し、最終的にそれぞれの投票がブロックされます (直接的、またはデータアクセス ロックによって間接的に)。ローカルトランザクションがサイクルに存在する場合、そのトランザクションはアボートされていない任意の状態 (実行中、準備完了、コミット済み。CO とは異なり、ローカルコミットのブロックは不要) になります。

CO と同様に、これは、データ アクセス ロック (少なくとも 1 つのロックがブロックされている) によるグローバル デッドロックも投票デッドロックであり、アトミック コミットメントによって自動的に解決されることを意味します。

マルチバージョン CO (MVCO)

マルチバージョンコミットメントオーダリング（MVCO; ( Raz 1993b )）は、マルチバージョンリソースを持つデータベース向けに CO を一般化したものです。このようなリソースでは、読み取り専用トランザクションはブロックされないか、またはブロックされてパフォーマンスが向上します。このようなリソースを利用することは、オブジェクトが書き込まれるたびにデータベースオブジェクトの新しいバージョンを生成し、トランザクションによる各オブジェクトのいくつかの最後の関連バージョンの読み取り操作を許可することにより、同時実行性とパフォーマンスを向上させる今日では一般的な方法です。MVCO は、マルチバージョンリソースの直列化可能性を一般化した 1SER または 1SR を意味します。COと同様に、MVCO は非ブロッキングであり、関連するマルチバージョン同時実行制御メカニズムと干渉することなく組み合わせることができます。導入された MVCO の基礎理論では、競合は同じリソースの異なるバージョンに対して一般化されています（以前のマルチバージョン理論とは異なります）。異なるバージョンの競合では、時系列順がバージョン順に置き換えられ、場合によっては逆順に置き換えられますが、競合する操作の通常の定義は維持されます。通常の競合グラフと拡張競合グラフの結果は変更されず、COと同様に、単一バージョンと複数バージョンのリソースが混在する環境に対応する分散MVCO強制アルゴリズムが存在します（単一バージョンは複数バージョンの特殊なケースです）。COと同様に、MVCOアルゴリズムは追加の通信オーバーヘッドなしで、（変更されていない）アトミックコミットメントプロトコルメッセージのみを必要とします。ロックベースのグローバルデッドロックは投票デッドロックに変換され、自動的に解決されます。COと同様に、以下が当てはまります。

• MVCOとグローバルワンコピー直列化可能性定理

1. 単一バージョンと複数バージョンのデータベースが混在するマルチデータベース環境におけるすべての自律データベース システム (またはトランザクション オブジェクト)の MVCO 準拠は、グローバル ワン コピー シリアル化可能性 (1SER) を保証するための必要条件です。
2. すべてのデータベース システムの MVCO 準拠は、グローバル 1SER を保証するための十分な条件です。
3. ロックベースのグローバルデッドロックは自動的に解決されます。

コメント: CO 準拠の単一バージョン データベース システムは、自動的に MVCO 準拠にもなります。

MVCO は、ECO の一般化 (MVECO) を採用することでさらに一般化できます。

例: CO ベースのスナップショット分離 (COSI)

CO ベースのスナップショット分離(COSI) は、スナップショット分離(SI) と MVCO の共通部分です。SI は、優れたパフォーマンスといくつかの点で直列化可能性 (1SER) に類似しているため、広く利用されている多版型同時実行制御方式です。上で説明した MVCO の理論 (Raz 1993b) は、後に (Fekete et al. 2005) や SI に関するその他の論文 (Cahill et al. 2008) で利用されています。^{[ 8 ]}また、「スナップショット分離を直列化可能にする」およびそこに記載されている参考文献も参照して、SI 内の競合を分析し、直列化可能にしています。(Cahill et al. 2008) で紹介されている方法、直列化可能スナップショット分離(SerializableSI) は、SI の低オーバーヘッド修正であり、直列化可能性を強制するためのペナルティがわずかで、SI に比べて優れたパフォーマンス結果をもたらします。 SIとMVCO（COSI）を組み合わせた別の方法では、汎用COアルゴリズムとシングルバージョンメカニズムを組み合わせた場合と同様に、比較的低いオーバーヘッドでSIもシリアル化可能になります。さらに、結果として得られるCOSIはMVCO準拠であるため、COSI準拠のデータベースシステムは相互運用でき、分散/グローバルシリアル化のためのCOソリューションに透過的に参加できます（下記参照）。オーバーヘッドに加えて、プロトコルの動作も定量的に比較する必要があります。一方で、すべてのシリアル化可能なSIスケジュールは、トランザクションを中止することなく、COSI（必要に応じてコミットを遅延させることにより）によってMVCO化できます。一方、SerializableSIは、シリアル化可能なSIスケジュールにおいても、一定の割合のトランザクションを不必要に中止して再開することが知られています。

COとその派生品は、グローバルなシリアル化可能性のために透過的に相互運用可能である。

CO とその変種 (上記の SS2PL、SCO、OCO、ECO、MVCO など) では、分散アルゴリズムに基づくアトミック コミットメントプロトコルによってグローバル直列化可能性が実現されます。CO とそのすべての変種では、アトミック コミットメント プロトコルは、グローバル拡張(したがって通常の)競合グラフ内のグローバル サイクル (2 つ以上のデータベースにまたがるサイクル) を(暗黙的に、グローバル データ構造の実装は不要) 削除するための手段です。2 つ以上のデータベースでローカル コミットメント 順序に互換性がない場合 (それぞれのローカル部分順序を一緒に埋め込むことができるグローバル部分順序がない場合)、またはデータ アクセス ロックに関連する投票デッドロックが発生した場合 (どちらもグローバル拡張競合グラフ内のグローバル サイクルを意味し、投票がありません)、アトミック コミットメント プロトコルは、未決定のトランザクションを中止することでそのようなサイクルを中断します (上記の「分散 CO アルゴリズム」を参照)。さまざまな変種間の違いは、ローカル レベル (参加データベース システム内) にのみ存在します。どのバリアントでも、各ローカル CO インスタンスは同じ役割を持ち、すべてのグローバル トランザクション (2 つ以上のデータベースにまたがるトランザクション) のローカル コミットメント順序内での位置を決定します。つまり、アトミック コミットメント プロトコルでトランザクションがローカルに投票される順番を決定します。したがって、すべての CO バリアントは、アトミック コミットメントに関して同じ動作を示します。つまり、それらはすべて、アトミック コミットメント (通常はサービスとして提供され、その一部はアトミック コミットメント用にすでに標準化されており、主に2 フェーズ コミットプロトコル用です (例: X/Open XA )) を介して相互運用可能であり、透過的に任意の分散環境で一緒に使用できます (各 CO バリアント インスタンスは、関連する任意のローカル同時実行制御メカニズム タイプに関連付けられる可能性があります)。

要約すると、任意の単一のグローバル トランザクションは、異なる可能性のある任意の CO バリアントを採用している可能性のあるデータベースに同時に参加できます (各データベースでプロセスが同時に実行され、各データベースでローカル トランザクションおよびその他のグローバル トランザクションが同時に実行されます)。アトミック コミットメント プロトコルは CO に無関係であり、さまざまな CO バリアントを区別しません。拡張グローバル競合グラフで生成されたグローバル サイクルは、異なる CO バリアントのデータベースにまたがる可能性があり、(ローカル アボートによって解除されない限り) 単一の CO バリアント環境とまったく同じようにアトミック コミットメントによって解決される投票デッドロックを生成します。ローカル サイクル(マテリアライズド競合と非マテリアライズド競合が混在する可能性があり、直列化可能性とデータ アクセス ロック デッドロック (例 : SCO) の両方が関連) はローカルで解決されます (それぞれ対応するバリアント インスタンスのローカル メカニズムによって)。

投票順序付け（VOまたは一般化CO（GCO）；Raz 2009）は、COとそのすべての派生形を統合した有用な概念であり、グローバル直列化可能性を実現する技術です。VOに準拠するには、ローカル直列化可能性（最も一般的な形式で、可換性に基づき、マルチバージョン化を含む）と投票順序戦略（ローカルな優先順位による投票）が必要です。

CO とその変異体の結果を組み合わせると、次の結論が導き出されます。

• COバリアント相互運用性定理

1. 各データベース システム (トランザクション オブジェクト) が何らかの CO バリアント プロパティ (VO 準拠) に準拠しているマルチ データベース環境では、任意のグローバル トランザクションが、場合によっては異なる CO バリアントのデータベースに同時に参加でき、グローバル シリアル化可能性が保証されます (グローバル シリアル化可能性の十分な条件、および複数バージョンのデータベースが存在する場合のグローバル ワン コピー シリアル化可能性 (1SER))。
2. 各データベース システムでローカルな（データベース システムに対して）同時実行制御情報のみが利用される場合（各データベース システムは、一般化された自律性プロパティ、つまり自律性の一般化を備えています）、各システムが何らかの（任意の）CO バリアント プロパティ（VO 準拠）に準拠していることは、グローバル直列化可能性（およびグローバル 1SER。そうでない場合は違反する可能性があります）を保証するための必要条件です。
3. さらに、このような環境では、データ アクセス ロックに関連するグローバル デッドロックは自動的に解決されます (このようなデッドロックはそれぞれ、拡張競合グラフのグローバル サイクル(つまり、投票デッドロック。上記を参照) によって生成され、少なくとも 1 つのデータ アクセス ロック (非マテリアライズド競合) と 2 つのデータベース システムが関係します。したがって、通常の競合グラフのサイクルではなく、シリアル化可能性には影響しません)。

参考文献

• Raz, Yoav (1992年8月)、「コミットメント順序の原理、またはアトミックコミットメントを用いた複数の自律リソースマネージャの異機種環境における直列化可能性の保証」(PDF)、第18回国際大規模データベース会議議事録、カナダ、バンクーバー、pp.  292– 312（DEC-TR 841、Digital Equipment Corporation、1990年11月）
• ラズ、ヨアブ（1994年9月）、「コミットメント順序による直列化可能性」、情報処理レター、51（5）：257-264、doi：10.1016/0020-0190（94）90005-1
• ラズ、ヨアブ（2009年6月）、コミットメント・オーダー理論：要約、 2011年11月11日閲覧
• Raz, Yoav (1990年11月)、「コミットメント順序付けの重要性について」 (PDF)、Digital Equipment Corporation
• ヨアヴ・ラズ（1991a）：米国特許5,504,899（ECO）5,504,900（CO）5,701,480（MVCO）
• Yoav Raz (1991b)：「リソース マネージャーのコミットメント オーダー コーディネータ (COCO)、または分散コミットメント オーダー ベースの同時実行制御のアーキテクチャ」、DEC-TR 843、Digital Equipment Corporation、1991 年 12 月。
• Yoav Raz (1991c)：「ロック ベースの厳密なコミットメント順序、またはロック ベースのリソース マネージャーでの並行性の向上方法」、DEC-TR 844、1991 年 12 月。
• Yoav Raz (1993a): 「拡張コミットメント順序、またはグローバルトランザクションへのコミットメント順序選択性適用によるグローバル直列化可能性の保証」第12回ACMデータベースシステム原理シンポジウム(PODS)議事録、ワシントンD.C.、pp. 83-96、1993年5月。(DEC-TR 842、1991年11月)
• Yoav Raz (1993b): 「単一バージョンと複数バージョンのリソースをブリッジするためのコミットメント順序に基づく分散同時実行制御」第3回IEEE国際ワークショップ「データエンジニアリングの研究課題：マルチデータベースシステムにおける相互運用性(RIDE-IMS)」議事録、オーストリア、ウィーン、1993年4月、189-198ページ。(DEC-TR 853、1992年7月)

脚注

1. Alan Fekete、Nancy Lynch、Michael Merritt、William Weihl (1988):ネストされたトランザクションの可換性ベースのロック(PDF) MIT、LCS ラボ、技術レポート MIT/LCS/TM-370、1988 年 8 月。
2. Philip A. Bernstein、Eric Newcomer (2009): Principles of Transaction Processing、第2版、Wayback Machineで2010年8月7日にアーカイブ、Morgan Kaufmann (Elsevier)、2009年6月、 ISBN 978-1-55860-623-4（145ページ、360ページ）
3. Lingli Zhang、Vinod K.Grover、Michael M. Magruder、David Detlefs、John Joseph Duffy、Goetz Graefe (2006):ソフトウェアトランザクションのコミット順序と競合管理、米国特許7711678、2010年5月4日付与。
4. Hany E. Ramadan、Indrajit Roy、Maurice Herlihy、Emmett Witchel (2009)：「STMにおける競合トランザクションのコミット」（ PDF）並列プログラミングの原理と実践に関する第14回ACM SIGPLANシンポジウム（PPoPP '09）の議事録、 ISBN 978-1-60558-397-6
5. Christoph von Praun、Luis Ceze、Calin Cascaval (2007)「順序付きトランザクションによる暗黙の並列処理」（ PDF）、第12回ACM SIGPLANシンポジウム「並列プログラミングの原理と実践」（PPoPP '07）の議事録、ACM New York ©2007、 ISBN 978-1-59593-602-8doi 10.1145/1229428.1229443
6. Robert Kallman、Hideaki Kimura、Jonathan Natkins、Andrew Pavlo、Alex Rasin、 Stanley Zdonik、Evan Jones、Yang Zhang、Samuel Madden、 Michael Stonebraker、John Hugg、Daniel Abadi (2008)：「H-Store: 高性能分散メインメモリトランザクション処理システム」、 2008 VLDB 会議録、1496 - 1499 ページ、ニュージーランド、オークランド、2008 年 8 月。
7. Perrizo, William; Tatarinov, Igor (1998年11月11日).コミット順序に基づく半楽観的データベーススケジューラ. 1998 Int'l Conference on Computer Applications in Industry and Engineering. ラスベガス. pp.  75– 79. CiteSeerX 10.1.1.53.7318 . 
8. Michael J. Cahill、Uwe Röhm、Alan D. Fekete (2008)：「スナップショットデータベースのシリアル化可能な分離」、 2008 ACM SIGMOD国際データ管理会議議事録、pp. 729-738、バンクーバー、カナダ、2008年6月、 ISBN 978-1-60558-102-6（SIGMOD 2008 最優秀論文賞

外部リンク

• ヨアヴ・ラズのコミットメント注文ページ