一貫性モデル

コンピュータサイエンスにおいて、一貫性モデルはプログラマとシステムの間の契約を指定します。システムは、プログラマがメモリ操作のルールに従えば、メモリの一貫性が保たれ、メモリの読み取り、書き込み、更新の結果が予測可能になることを保証します。一貫性モデルは、分散共有メモリシステムや分散データストア（ファイルシステム、データベース、楽観的レプリケーションシステム、Web キャッシュなど）などの分散システムで使用されます。一貫性は、キャッシュ付きまたはキャッシュなしのシステムで発生するコヒーレンスとは異なり、すべてのプロセッサに関するデータの一貫性です。コヒーレンスは、単一の場所または単一の変数への書き込みがすべてのプロセッサで認識されるグローバルな順序を維持することを扱います。一貫性は、すべてのプロセッサに関する複数の場所への操作の順序を扱います。

C++やJavaなどの高水準言語は、メモリ操作をメモリセマンティクスを保持する方法で低水準操作に変換し、一部のメモリ命令を並べ替え、必要な同期をなどのライブラリ呼び出しでカプセル化することで、一貫性契約を維持しますpthread_mutex_lock()。^[1]

次のようなケースが起こったと仮定する: ^[2]

• 行XはノードMとNに複製される
• クライアントAは行XをノードMに書き込む
• 一定時間tが経過すると、クライアントBはノードNから行Xを読み取ります。

一貫性モデルは、クライアント B がクライアント A によって実行された書き込みを確実に認識するか、確実に認識しないか、または書き込みを認識するかどうかに依存できないかを決定します。

一貫性モデルは、更新の見かけの順序と可視性に関するルールを定義し、トレードオフを伴う連続体上にあります。^[2]一貫性モデルを定義および分類する方法には、問題とビューの2つがあります。

問題

発行方法は、プロセスが操作を発行する方法を定義する制限について説明します。

ビュー

プロセスに表示される操作の順序を定義するビュー メソッド。

たとえば、一貫性モデルでは、以前に発行されたすべての操作が完了するまで、プロセスが操作を発行できないように定義できます。一貫性モデルによって、適用される条件が異なります。一貫性モデルのすべての条件とそれ以上の条件が求められる場合、その一貫性モデルは他のモデルよりも強力であると考えられます。言い換えると、制約が少ないモデルは、より弱い一貫性モデルであると考えられます。

これらのモデルは、ハードウェアのレイアウト方法と、プログラマーがコーディングしなければならない高レベルの方法を定義します。選択したモデルは、コンパイラーが命令を並べ替える方法にも影響します。通常、命令間の制御依存関係があり、同じ場所への書き込みが順序付けられている場合、コンパイラーは必要に応じて並べ替えることができます。ただし、以下に説明するモデルでは、一部のモデルではロード前の書き込みの並べ替えが許可されますが、一部のモデルでは許可されません。

厳密な一貫性は、最も強力な一貫性モデルです。このモデルでは、任意のプロセッサによる変数への書き込みは、すべてのプロセッサで瞬時に認識される必要があります。

厳密なモデル図と非厳密なモデル図は、時間制約（瞬時）を説明します。これは、グローバル クロックが存在し、そのクロック期間の終了までにすべての書き込みがすべてのプロセッサ キャッシュに反映されると考えるとわかりやすいでしょう。次の操作は、次のクロック期間にのみ実行する必要があります。

次の図では、P は「プロセス」を意味し、グローバル クロックの値はシーケンス列に表されます。

これは最も厳格なモデルです。このモデルでは、プログラマーが期待する結果が毎回受信されます。これは決定論的です。瞬時のメッセージ交換は不可能であるため、その実用的な関連性は思考実験と形式主義に限定されます。同時書き込みは不可能であると想定しているため、同じデータ項目への同時書き込みにおける競合解決の質問に答えるのに役立ちません。

シーケンシャル一貫性モデルは、Lamport (1979) によって提案されました。これは、厳密な一貫性モデルよりも弱いメモリ モデルです。^[3]変数への書き込みは、瞬時に確認される必要はありませんが、異なるプロセッサによる変数への書き込みは、すべてのプロセッサで同じ順序で確認される必要があります。シーケンシャル一貫性は、「すべての実行結果が、データ ストアのすべてのプロセスの (読み取りおよび書き込み) 操作が何らかの順序で実行された場合と同じであり、各プロセッサの操作が、そのプログラムで指定された順序でこの順序で表示される」場合に満たされます。^{[3] [4]} Adve と Gharachorloo、1996 ^{[5] は、}シーケンシャル一貫性を実装するための 2 つの要件、プログラム順序と書き込みアトミック性を定義しています。

• プログラム順序: プログラム順序は、各プロセスがプログラムによって順序付けられたメモリ要求を発行することを保証します。
• 書き込みアトミック性: 書き込みアトミック性は、メモリ要求が単一の FIFO キューの順序に基づいて処理されることを定義します。

シーケンシャル一貫性では、時間や最新の書き込み操作の概念はありません。すべてのプロセスで同じインターリーブ操作がいくつかあります。プロセスはすべてのプロセスの書き込み操作を見ることができますが、自分の読み取り操作しか見ることができません。各プロセッサ内のプログラム順序とプロセッサ間の操作の順序は維持される必要があります。プロセッサ間の実行の順序を維持するために、すべての操作は、他のすべてのプロセッサに対して瞬時またはアトミックに実行されるように見える必要があります。

これらの操作は、情報を瞬時に送信することは物理的に不可能であるため、完了したように「見える」だけで十分です。たとえば、単一のグローバル共有バスを使用するシステムでは、バス ラインに情報が送信されると、すべてのプロセッサが同じ瞬間にその情報を見ることが保証されます。したがって、情報をバス ラインに渡すと、すべてのプロセッサに関する実行が完了し、実行されたように見えます。キャッシュレス アーキテクチャまたはキャッシュ アーキテクチャで相互接続ネットワークが瞬時に行われない場合は、プロセッサとメモリの間に低速パスが含まれることがあります。これらの低速パスは、一部のメモリが他のメモリよりも速くブロードキャスト データを受信するため、連続的な不整合を引き起こす可能性があります。

順次一貫性は非決定的な結果を生み出す可能性があります。これは、プロセッサ間の順次操作の順序が、プログラムの実行ごとに異なる可能性があるためです。すべてのメモリ操作は、プログラムの順序で実行する必要があります。

線形化可能性^[6] （アトミック一貫性またはアトミックメモリとも呼ばれる）^[7]は、各操作の開始時間と終了時間を考慮することにより、リアルタイム制約を伴う順次一貫性として定義できます。各操作が開始時間と終了時間の間にポイントを置くことによって線形化可能な順序で実行され、順次一貫性が保証される場合、実行は線形化可能です。

モデル検査による順序一貫性の検証は、有限状態キャッシュコヒーレンスプロトコルの場合でも、一般には決定不可能である。 ^[8]

1990 年に Hutto と Ahamad によって定義された因果的一貫性^[4]は、イベントを因果的に関連しているものとそうでないものに分類することで、シーケンシャル一貫性モデルを弱めたものです。因果的に関連している書き込み操作のみが、すべてのプロセスで同じ順序で確認される必要があると定義されています。たとえば、イベント b が以前のイベント a から発生する場合、因果的一貫性により、すべてのプロセスがイベント a の後にイベント b を確認することが保証されます。Tanenbaum ら (2007) は、データ ストアが因果的に一貫していると見なされる条件を次のように厳格に定義しています。^[4]

• 潜在的に因果関係のある書き込みは、すべてのプロセスで同じ順序で認識される必要があります。
• 同時書き込みは、マシンによって順序が異なる場合があります。

このモデルは、プロセッサによる同時書き込みおよび因果関係のない書き込みの順次一貫性を緩和します。2 回目の書き込みを実行するプロセッサが最初の書き込みを読み取った直後であれば、変数への 1 回目の書き込みが任意の変数への以前の書き込みに依存している場合、2 回目の書き込みは因果関係を持つ可能性があります。2 回の書き込みは、同じプロセッサによって実行された場合も、異なるプロセッサによって実行された場合もあります。

順次一貫性の場合と同様に、読み取りでは変更を瞬時に反映する必要はありませんが、変数に対するすべての変更を順次反映する必要があります。

W(x)2はW(x)2の前にP2によるxの読み取りによりW(x)1の後に発生するため、この例はHuttoとAhamadの定義では因果的に一貫しています（ただし、Tanenbaumらの定義では、W(x)2とW(x)3がすべてのプロセスで同じ順序で発生しないため、因果的に一貫していません）。しかし、R(x)2とR(x)3はP3とP4では異なる順序で発生するため、この例は順序的に矛盾しています。^[10]

データの一貫性を維持し、各プロセッサが独自のメモリを持つスケーラブルなプロセッサシステムを実現するために、プロセッサ一貫性モデルが導き出されました。^[10] すべてのプロセッサは、1つのプロセッサによる書き込みを認識する順序と、異なるプロセッサによる同じ場所への書き込みを認識する方法において一貫性を持っている必要があります（一貫性が維持されます）。ただし、異なるプロセッサによる異なる場所への書き込みの場合は、一貫性は必要ありません。

すべての書き込み操作は、すべてのメモリへの複数のサブ書き込みに分割できます。このようなメモリの 1 つからの読み取りは、このメモリへの書き込みが完了する前に発生する可能性があります。したがって、読み取られたデータは古い可能性があります。したがって、PC のプロセッサは、古いストアを停止する必要がある場合に、新しいロードを実行できます。このモデルでは、書き込み前の読み取り、読み取り後の読み取り、書き込み前の書き込みの順序は保持されます。

プロセッサ一貫性モデル^[11]はPRAM一貫性モデルに似ていますが、同じメモリ位置へのすべての書き込みが他のすべてのプロセスによって同じ順序で認識される必要があるというより強い条件を定義します。プロセッサ一貫性はシーケンシャル一貫性よりも弱いですが、PRAM一貫性モデルよりも強力です。

スタンフォード DASH マルチプロセッサ システムは、グッドマンの定義とは比較にならない (弱くも強くもない) プロセッサ一貫性のバリエーションを実装しています。^[12]すべてのプロセッサは、1 つのプロセッサによる書き込みを認識する順序と、異なるプロセッサによる同じ場所への書き込みを認識する方法で一貫性を持っている必要があります。ただし、異なるプロセッサによる異なる場所への書き込みの場合は、一貫性は必要ありません。

パイプラインRAM一貫性（PRAM一貫性）は、1988年にLiptonとSandbergによって最初に記述された一貫性モデルの1つとして発表されました^[13] 。その非公式な定義のため、実際には少なくとも2つの微妙に異なる実装があり、^[12] 1つはAhamadらによるもので、もう1つはMosbergerによるものです。

PRAM の一貫性では、すべてのプロセスは、単一のプロセスの操作をそのプロセスによって発行されたのと同じ順序で表示しますが、異なるプロセスによって発行された操作は、異なるプロセスから異なる順序で表示できます。PRAM の一貫性は、プロセッサの一貫性よりも弱いです。PRAM は、すべてのプロセッサ間で場所の一貫性を維持する必要性を緩和します。ここでは、プロセッサへの書き込みの前に、任意の変数の読み取りを実行できます。このモデルでは、書き込み前の読み取り、読み取り後の読み取り、書き込み前の書き込みの順序は、引き続き保持されます。

キャッシュの一貫性^{[11] [14]}では、同じメモリ位置へのすべての書き込み操作が一定の順序で実行される必要があります。キャッシュの一貫性はプロセッサの一貫性よりも弱く、PRAMの一貫性とは比較になりません。

^{低速一貫性[14]}では、プロセスがメモリの場所に以前書き込まれた値を読み取った場合、その後その場所から以前の値を読み取ることはできません。プロセスによって実行された書き込みは、そのプロセスにすぐに表示されます。低速一貫性は、PRAMやキャッシュ一貫性よりも弱いモデルです。

例: 低速メモリ図は、低速一貫性の例を示しています。最初のプロセスはメモリ位置 X に 1 を書き込み、次にメモリ位置 Y に 1 を書き込みます。2 番目のプロセスは Y から 1 を読み取り、次に X が Y より前に書き込まれたにもかかわらず、X から 0 を読み取ります。

Hutto、Phillip W.、およびMustaque Ahamad (1990) ^{[9] は、}適切なプログラミングによって、低速メモリ（一貫性）が表現力豊かで効率的になることを示しています。彼らは、低速メモリには、局所性とアトミックメモリからの削減のサポートという2つの貴重な特性があると述べています。彼らは、低速メモリの表現力を表現する2つのアルゴリズムを提案しています。

これら4つの一貫性モデルは1994年の論文で提案されました。これらは、単一のユーザーまたはアプリケーションのみがデータを変更する状況での保証に重点を置いています。^[15]

プロセスがデータ項目xの値を読み取ると、そのプロセスによるxに対する後続の読み取り操作は常に同じ値またはより新しい値を返します。^[4]

あるプロセスによるデータ項目Xへの書き込み操作は、同じプロセスによるXへの後続の書き込み操作よりも先に完了する。^[4]

あるプロセスによってデータ項目Xに書き込まれた値は、同じプロセスによってデータ項目Xに対して実行される後続の読み取り操作で常に利用可能となる。^[4]

あるプロセスによるデータ項目xへの書き込み操作は、同じプロセスによるxの前回の読み取り操作に続いて行われ、読み取られたxの同じ値またはより最近の値に対して実行されることが保証されます。^[4]

次のモデルでは、プログラマーによる特定の同期が必要です。

弱い順序付けは、メモリ操作をデータ操作と同期操作の2 つのカテゴリに分類します。プログラム順序を強制するには、プログラマはプログラム内で少なくとも 1 つの同期操作を見つける必要があります。同期操作は、プロセッサに信号を送り、すべてのプロセッサによって行われたすべての以前の操作が完了し、確認されていることを確認します。プログラム順序とアトミック性は、すべての読み取りと書き込みではなく、同期操作でのみ維持されます。これは、クリティカル セクションで実行されるような特定のメモリ操作は、クリティカル セクションのすべての操作が完了するまで、すべてのプロセッサで確認される必要がないという理解から導き出されました。同期操作間でデータ領域へのメモリ操作を並べ替えても、プログラムの結果には影響しないと想定されています。これは、マルチプロセッサ システムで実行されるように作成されたプログラムには、データ競合が発生しないようにし、常に SC 結果が生成されるようにするために必要な同期が含まれているという事実を利用しています。^[16]

このモデルでは、一貫性は緩和されません。これらの要件が満たされると、他のすべての「データ」操作を並べ替えることができます。これは、カウンターがデータ操作の数を追跡し、このカウンターがゼロになるまで同期操作が発行されないという仕組みです。さらに、以前の同期がすべて完了しない限り、それ以上のデータ操作は発行されません。2 つの同期変数間のメモリ操作は、プログラムの正確性に影響を与えることなく、オーバーラップして並べ替えることができます。このモデルでは、書き込みの原子性が常に維持されるため、弱い順序付けに追加のセーフティ ネットは必要ありません。

弱い順序付けを維持するために、同期操作の前の書き込み操作は、同期操作の前にグローバルに実行する必要があります。同期操作の後にある操作も、同期操作が完了した後にのみ実行する必要があります。したがって、同期変数へのアクセスは連続的に一貫性があり、読み取りまたは書き込みは、前の同期操作が完了した後にのみ実行する必要があります。

プログラムでは明示的な同期に大きく依存しています。弱い順序付けモデルの場合、プログラマーは、テストと設定、フェッチと操作、条件付きストア、リンクされたロードなどのアトミック ロック命令を使用するか、同期変数にラベルを付ける、またはフェンスを使用する必要があります。

リリース一貫性モデルは、入口同期操作と出口同期操作を区別することで、弱い一貫性モデルを緩和します。弱い順序付けでは、同期操作を確認するには、同期操作が完了してプロセッサが処理を進める前に、すべてのプロセッサのすべての操作を確認できる必要があります。ただし、リリース一貫性モデルでは、クリティカル セクションへの入口 (「取得」と呼ばれます) 中に、ローカル メモリ変数に関するすべての操作を完了する必要があります。出口 (「リリース」と呼ばれます) 中に、ローカル プロセッサによって行われたすべての変更が他のすべてのプロセッサに伝播される必要があります。一貫性は維持されます。

取得操作は、クリティカル セクションにアクセスするために実行されるロード/読み取りです。解放操作は、他のプロセッサが共有変数を使用できるようにするために実行されるストア/書き込みです。

同期変数間では、シーケンシャル一貫性またはプロセッサ一貫性を維持できます。SC を使用すると、競合するすべての同期変数を順番に処理する必要があります。ただし、PC では、競合する 2 つの変数はこの順序に従うだけで済みます。新しい取得は、古いリリースの前に実行できます。^{[引用が必要]}

リリース一貫性には、シーケンシャル一貫性を備えたリリース一貫性 (RCsc) とプロセッサ一貫性を備えたリリース一貫性 (RCpc) の 2 種類があります。後者のタイプは、以下で特別として指定されている操作に適用される一貫性のタイプを示します。

特別な（通常の）メモリ操作があり、それ自体がsync操作またはnsync操作という 2 つのクラスの操作から構成されています。後者は同期には使用されない操作です。前者は同期に使用され、取得操作と解放操作から構成されています。取得は、実質的には、特定の共有場所へのアクセスを取得するために使用されるメモリ読み取り操作です。一方、解放は、共有場所へのアクセス許可を付与するために実行される書き込み操作です。

順次一貫性 (RCsc) の場合、制約は次のとおりです。

• 取得する → すべて、
• すべて → 解放、
• 特別な→特別な。

プロセッサの一貫性 (RCpc) のために、書き込みから読み取りへのプログラム順序は緩和され、次の制約があります。

• 取得する → すべて、
• すべて → 解放、
• special → special (ただし、special write の後に special read が続く場合は除く)。

注: 上記の表記 A → B は、プログラム順序で操作 A が B に先行する場合、プログラム順序が強制されることを意味します。

これはリリース一貫性モデルの変形です。また、クリティカル セクションへのエントリまたは終了を明示的に示すために、取得命令とリリース命令を使用する必要があります。ただし、エントリ一貫性では、すべての共有変数に固有の同期変数が割り当てられます。この方法では、変数 x の取得の場合のみ、そのプロセッサに関して x に関連するすべての操作を完了する必要があります。これにより、異なる共有変数の異なるクリティカル セクションの同時操作が可能になります。同じ共有変数のクリティカル操作では、同時実行は確認できません。このような一貫性モデルは、異なるマトリックス要素を同時に処理できる場合に役立ちます。

^{ローカル一貫性[14]}では、各プロセスはプログラムで定義された順序で独自の操作を実行します。他のプロセスの書き込み操作が実行される順序には制約がありません。ローカル一貫性は、共有メモリシステムで最も弱い一貫性モデルです。

一般的な一貫性では、^[17]すべてのプロセスの書き込みが完了すると、メモリ位置のすべてのコピーは最終的に同一になります。

結果的一貫性[ ^4]は、同時更新がないシステムにおける弱い一貫性モデルです。更新に非常に長い時間がかからない場合、すべてのレプリカが最終的に一貫性を持つと定義されます。

ほとんどの共有分散データベースは、結果整合性モデルを採用しています。これは、BASE（基本的に利用可能、ソフトステート、最終的に一貫性がある）またはACIDとBASEの組み合わせ（SALTと呼ばれることもあります）：順次、合意、台帳、改ざん防止、対称、管理者不要、台帳、時間合意のいずれかです。^{[18] [19] [20]}

シーケンシャル一貫性における1つ以上の要件を緩和することで、いくつかの異なる一貫性モデルを定義できます。これを緩和一貫性モデルと呼びます。 ^[7]これらの一貫性モデルは、ハードウェアレベルでメモリの一貫性を提供しません。実際、プログラマは同期技術を適用してメモリの一貫性を実装する責任があります。上記のモデルは4つの基準に基づいて分類され、さらに詳しく説明されています。

緩和された一貫性を定義する比較は 4 つあります。

リラクゼーション

緩和された一貫性を分類する 1 つの方法は、どのシーケンシャル一貫性要件が緩和されるかを定義することです。Adve と Gharachorloo (1996) ^[5]によって定義されたプログラム順序または書き込みアトミック性の要件のいずれかを緩和することで、より緩やかなモデルを作成できます。プログラム順序は、各プロセスがそのプログラムによって順序付けられたメモリ要求を発行することを保証し、書き込みアトミック性は、メモリ要求が単一の FIFO キューの順序に基づいて処理されることを定義します。プログラム順序を緩和すると、書き込み後の書き込み、読み取り後の書き込み、読み取り/書き込み後の読み取りなど、操作ペアの順序のいずれかまたはすべてを緩和できます。緩和された書き込みアトミック性モデルでは、プロセスは他のプロセッサよりも先に自分の書き込みを確認できます。

同期と非同期

同期モデルは、メモリ アクセスを 2 つのグループに分割し、一方のグループには弱い一貫性モデルを適用し、もう一方のグループにはより制限の厳しい一貫性モデルを適用することを考慮して、各グループに異なる一貫性制限を割り当てることによって定義できます。対照的に、非同期モデルでは、メモリ アクセス タイプに同じ一貫性モデルを割り当てます。

問題ベースとビューベース

^[14]発行方式は、プロセスがメモリ操作を発行するための制約を定義することによって、順次一貫性のシミュレーションを提供します。一方、ビュー方式は、プロセスのイベント順序の可視性制約を記述します。

相対的なモデルの強さ

一部の一貫性モデルは、他のモデルよりも制限が厳しいです。言い換えると、厳密な一貫性モデルは、一貫性要件としてより多くの制約を適用します。モデルの強度は、プログラム順序または原子性緩和によって定義でき、モデルの強度を比較することもできます。同じ緩和またはそれ以上の緩和を適用する場合、一部のモデルは直接関連しています。一方、異なる要件を緩和するモデルは直接関連していません。

シーケンシャル コンシステンシーには、プログラム順序と書き込みアトミック性の 2 つの要件があります。これらの要件を緩和することで、さまざまな緩和コンシステンシー モデルを取得できます。これにより、制約が緩和され、パフォーマンスが向上しますが、プログラマーは同期技術を適用してメモリ コンシステンシーを実装する責任があり、ハードウェアについて十分な理解が必要です。

潜在的な緩和策:

• 書き込みから読み取りまでのプログラム順序
• プログラム命令を書き込む
• 読み取るために読む、および書き込むために読むプログラム命令

ハードウェア レベルでパフォーマンスを向上させるアプローチは、書き込みの後に読み取りが続く場合の PO を緩和して、書き込み操作のレイテンシを効果的に隠すことです。このタイプの緩和が依存する最適化は、プロセッサからの以前の書き込みに対して後続の読み取りが緩和された順序になることを可能にすることです。この緩和により、XXX などの一部のプログラムは SC 結果を返すことができない場合があります。一方、YYY などのプログラムは、残りのプログラム順序制約の強制により、一貫した結果を返すことが期待されます。

このカテゴリには 3 つのモデルが該当します。IBM 370 モデルは最も厳格なモデルです。読み取りは、別のアドレスへの以前の書き込みより前に完了できますが、すべてのプロセッサが書き込みを確認していなければ、書き込みの値を返すことは禁止されています。SPARC V8 トータル ストア オーダリング モデル (TSO) は、IBM 370 モデルを部分的に緩和したもので、読み取りでは、同じ場所への他の書き込みに関して、そのプロセッサ自身の書き込みの値を返すことができます。つまり、他のプロセッサがそれを見る前に、そのプロセッサ自身の書き込みの値を返します。前のモデルと同様に、このモデルでは、すべてのプロセッサが書き込みを確認していなければ、書き込みの値を返すことはできません。プロセッサ整合性モデル (PC) は、3 つのモデルの中で最も緩和されており、他のプロセッサに認識される前であっても、以前の書き込みより前に読み取りが完了できるように、両方の制約を緩和しています。

例 A では、read(A) は、そのプロセッサでの write(A) が完了するまで発行されないため、結果は IBM 370 でのみ可能です。一方、TSO と PC では、単一プロセッサでのフラグの書き込みの前にフラグの読み取りが許可されるため、この結果は可能です。

例 B では、書き込みの値が P3 に表示される前であっても P2 が書き込みの値を返すことができるため、結果は PC でのみ可能です。これは他の 2 つのモデルでは不可能です。

上記のモデルで連続的な一貫性を保証するために、セーフティ ネットまたはフェンスを使用して制約を手動で強制します。IBM370 モデルには、操作の間に手動で配置される特殊なシリアル化命令がいくつかあります。これらの命令は、メモリ命令または分岐などの非メモリ命令で構成できます。一方、TSO モデルと PC モデルにはセーフティ ネットはありませんが、プログラマーは読み取り、変更、書き込み操作を使用して、書き込みとそれに続く読み取りの間でプログラム順序が維持されているように見せることができます。TSO の場合、R または W がすでに R 変更 W の一部である場合、PO は維持されるように見えますが、これには、R 変更 W の W が読み取り値を返す「ダミー」である必要があります。同様に、PC の場合、読み取りが書き込みに置き換えられた場合、またはすでに R 変更 W の一部である場合、PO は維持されるように見えます。

ただし、この緩和策のみを実行してもコンパイラの最適化は実行できません。コンパイラの最適化には、PO 内の任意の 2 つの操作を並べ替える完全な柔軟性が求められるため、読み取りに関して書き込みを並べ替える機能は、この場合十分に役立ちません。

一部のモデルでは、異なる場所への書き込み間の順序制約さえも緩和することで、プログラム順序をさらに緩和します。SPARC V8 の部分ストア順序モデル (PSO) は、そのようなモデルの唯一の例です。同じプロセッサから異なる場所への書き込みをパイプライン化してオーバーラップする機能は、PSO によって実現される主要なハードウェア最適化です。PSO は、アトミック性要件の点で TSO に似ており、プロセッサが自身の書き込みの値を読み取ることができ、書き込みが他のすべてのプロセッサに表示される前に他のプロセッサが別のプロセッサの書き込みを読み取ることを防ぎます。2 つの書き込み間のプログラム順序は、明示的な STBAR 命令を使用して PSO によって維持されます。STBAR は、FIFO 書き込みバッファを使用した実装の書き込みバッファに挿入されます。STBAR 命令の前にあるすべての書き込みが完了したかどうかを判断するためにカウンタが使用され、これによりメモリ システムへの書き込みがトリガーされてカウンタが増加します。書き込み確認によってカウンタが減算され、カウンタが 0 になると、以前のすべての書き込みが完了したことを示します。

例 A と B では、PSO はこれらの非連続的な一貫性のある結果の両方を許可します。PSO が提供するセーフティ ネットは TSO のものと似ており、書き込みから読み取りまでのプログラム順序を強制し、書き込みのアトミック性を強制します。

以前のモデルと同様に、PSO によって許可される緩和は、より柔軟な最適化を必要とするコンパイラ最適化に使用できるほど十分に柔軟ではありません。

一部のモデルでは、異なる場所へのすべての操作が緩和されます。読み取りまたは書き込みは、異なる場所の別の読み取りまたは書き込みに応じて並べ替えられる場合があります。弱い順序付けはこのカテゴリに分類され、2 種類のリリース一貫性モデル (RCsc および RCpc) もこのモデルに含まれます。この緩和のカテゴリでは、Digital Alpha、SPARC V9 緩和メモリ順序 (RMO)、および IBM PowerPC モデルの 3 つの商用アーキテクチャも提案されています。

これら 3 つの商用アーキテクチャでは、セーフティ ネットとして明示的なフェンス命令が採用されています。Alpha モデルでは、メモリ バリア(MB) と書き込みメモリ バリア(WMB) の 2 種類のフェンス命令が提供されています。MB 操作は、バリアの後のメモリ操作で MB の前の任意のメモリ操作のプログラム順序を維持するために使用できます。同様に、WMB は書き込み間でのみプログラム順序を維持します。SPARC V9 RMO モデルでは、MEMBAR 命令が提供されており、これをカスタマイズして、将来の読み取りおよび書き込み操作に関して以前の読み取りおよび書き込みを順序付けることができます。この順序を実現するために読み取り、変更、書き込みを使用する必要はありません。MEMBAR 命令は、後続の読み取りに関して書き込みを順序付けするために使用できるためです。PowerPC モデルでは、SYNC 命令と呼ばれる単一のフェンス命令が使用されます。これは MB 命令に似ていますが、同じ場所への 2 つの読み取りの間に SYNC が配置されている場合でも、読み取りがプログラム順序どおりに行われない可能性があるという小さな例外があります。このモデルは、アトミック性の点でも Alpha および RMO とは異なります。これにより、読み取りが完了する前に書き込みを確認できます。書き込みの原子性を疑似的にするには、読み取り、変更、書き込みの各操作の組み合わせが必要になる場合があります。

RMO と PowerPC では、同じ場所への読み取りの順序変更が可能です。これらのモデルは、例 A と B の順序に違反します。これらのモデルで許可されている追加の緩和策は、読み取り操作に続くメモリ操作をオーバーラップし、読み取りに関して順序変更できることです。Alpha と RMO では、読み取りによって別のプロセッサの早期書き込みの値を返すことができます。プログラマーの観点から見ると、これらのモデルは、プロセッサが自身の書き込みを早期に読み取ることができるにもかかわらず、書き込みのアトミック性の錯覚を維持する必要があります。

トランザクションメモリモデル^[7]は、ソフトウェアまたはハードウェアによってサポートされる共有メモリシステムの通信モデルとして、キャッシュ一貫性モデルとメモリ一貫性モデルを組み合わせたものです。トランザクションメモリモデルは、メモリ一貫性とキャッシュ一貫性の両方を提供します。トランザクションとは、データを 1 つの一貫性のある状態から別の一貫性のある状態に変換するプロセスによって実行される一連の操作です。トランザクションは、競合がない場合にコミットするか、中止します。コミットでは、トランザクションが完了すると、すべての変更が他のすべてのプロセスに表示されますが、中止するとすべての変更が破棄されます。緩和一貫性モデルと比較して、トランザクションモデルは使いやすく、順次一貫性モデルよりも高いパフォーマンスを提供できます。

その他の一貫性モデルは次のとおりです。

• 因果関係+一貫性^{[21] [22]}
• クロスクライアント単調性^[23]
• デルタ一貫性
• フォークの一貫性
• 1コピーのシリアル化可能性
• シリアル化可能性
• ベクトル場の一貫性
• 一貫性が弱い
• 強い一貫性

操作の順序や可視性に関する制約を表現したり、特定の障害仮定に対処するために、他のいくつかの一貫性モデルが考案されてきた。^[24]

Tanenbaum ら、2007 ^{[4] は、}レプリケーションの 2 つの主な理由として、信頼性とパフォーマンスを定義しています。信頼性は、現在のレプリカに障害が発生した場合に別のレプリカに切り替えることで、レプリケーションされたファイル システムで実現できます。また、レプリケーションは、異なるレプリカにデータの複数のコピーを提供することで、データが破損するのを防ぎます。また、作業を分割することでパフォーマンスも向上します。レプリケーションはパフォーマンスと信頼性を向上できますが、データの複数のコピー間で一貫性の問題が発生する可能性があります。読み取り操作がすべてのコピーから同じ値を返し、書き込み操作が単一のアトミック操作 (トランザクション) として他の操作が行われる前にすべてのコピーを更新する場合、複数のコピーは一貫性があります。Tanenbaum、Andrew、Maarten Van Steen、2007 ^[4]は、このタイプの一貫性を同期レプリケーションによって提供される緊密な一貫性と呼んでいます。ただし、すべてのコピーの一貫性を保つためにグローバル同期を適用するとコストがかかります。グローバル同期のコストを削減し、パフォーマンスを向上させる 1 つの方法は、一貫性の制限を弱めることです。

Tanenbaum et al., 2007 ^{[4] は、}一貫性モデルをソフトウェア (プロセス) とメモリ実装 (データ ストア) 間の契約として定義しています。このモデルは、ソフトウェアが特定のルールに従う場合、メモリが正しく動作することを保証します。グローバル クロックのないシステムでは、書き込みの最後の操作を定義することが難しいため、読み取り操作によって返される値にいくつかの制限を適用できます。データ中心の一貫性モデルの目標は、プロセスが同時更新を実行する可能性があるデータ ストアに対して一貫したビューを提供することです。

シーケンシャル整合性モデルや因果整合性モデルなどの一部の整合性モデルでは、整合性を提供するために、共有複製データに対する操作の順序を扱います。これらのモデルでは、すべてのレプリカが更新の一貫したグローバル順序に同意する必要があります。

グループ化操作では、同期変数へのアクセスは連続的に一貫しています。プロセスは、以前の書き込みがすべて完了した同期変数にアクセスできます。言い換えると、同期変数に対するすべての操作が完全に実行されるまで、同期変数へのアクセスは許可されません。^[4]

分散システムでは、同時操作を制御するために連続的な一貫性を維持することが不可欠です。同時更新のない特殊なデータストアでは、クライアント中心の一貫性モデルにより、コストのかからない方法で不整合を処理できます。次のモデルは、クライアント中心の一貫性モデルの一部です。^[4]

一貫性モデルの実装は一貫性プロトコルによって定義されます。Tanenbaum et al., 2007 ^{[4] は、}データ中心モデルの一貫性プロトコルをいくつか示しています。

継続的一貫性は、Yu と Vahdat (2000) によって導入されました。^[25]このモデルでは、アプリケーションの一貫性セマンティクスは、アプリケーション内の conits を使用して記述されます。一貫性要件はアプリケーション セマンティクスに基づいて異なる可能性があるため、Yu と Vahdat (2000) ^{[25] は}、定義済みの均一な一貫性モデルは適切なアプローチではない可能性があると考えています。アプリケーションは、アプリケーション セマンティクスを満たす一貫性要件を指定する必要があります。このモデルでは、アプリケーションは各一貫性要件を conit (一貫性ユニットの略語) として指定します。conit は物理的または論理的な一貫性であり、一貫性を測定するために使用されます。Tanenbaum ら、2007 ^{[4] は、}例を挙げて conit の概念を説明しています。

アプリケーションで許容できる不整合は 3 つあります。

数値の偏差

^[25]数値偏差は、conit値と最後の更新の相対値との差を制限します。書き込みに重みを割り当てることで、特定のアプリケーションでの書き込みの重要性を定義できます。conitの未確認書き込みの合計重みは、アプリケーションでの数値偏差として定義できます。数値偏差には、絶対数値偏差と相対数値偏差の2種類があります。

順序の逸脱

^[25]順序偏差とは、レプリカ内の書き込みのローカル順序と最終的な最終イメージ内の相対順序との間の不一致である。

レプリカ間の古さの偏差

^[25]古さ偏差は、現在の時刻と、ローカルでは確認できない conit 上の最も古い書き込みの時刻との差を境界として、最も古い書き込みの有効性を定義します。各サーバーには、実際の順序を決定して conit に適用する必要がある不確実な書き込みのローカル キューがあります。不確実な書き込みキューの最大長が順序偏差の境界です。書き込み数が制限を超えると、サーバーは、新しく送信された書き込みを受け入れる代わりに、書き込みを実行する順序に基づいて他のサーバーと通信して、不確実な書き込みをコミットしようとします。

3 つの偏差境界がすべてゼロに設定されている場合、連続一貫性モデルは強い一貫性になります。

プライマリベースのプロトコル^[4]は、実装がより簡単な一貫性プロトコルの一種と考えることができます。たとえば、操作の一貫した順序を考慮する場合、シーケンシャル順序付けは一般的な一貫性モデルです。シーケンシャル順序付けは、プライマリベースのプロトコルとして決定できます。これらのプロトコルでは、データストア内の各データ項目に関連付けられたプライマリがあり、そのデータ項目への書き込み操作を調整します。

レプリケーションをサポートする最も単純なプライマリベースのプロトコル (プライマリ バックアップ プロトコルとも呼ばれます) では、書き込み操作は単一のサーバーに転送され、読み取り操作はローカルで実行できます。

例: Tanenbaum ら、2007 ^{[4] は}プライマリ バックアップ プロトコルの例を示しています。プライマリ バックアップ プロトコルの図は、このプロトコルの例を示しています。クライアントが書き込みを要求すると、書き込み要求はプライマリ サーバーに転送されます。プライマリ サーバーは、更新を実行するためにバックアップに要求を送信します。次に、サーバーはすべてのバックアップから更新確認を受信し、書き込み完了の確認をクライアントに送信します。どのクライアントも、ローカルで最新の利用可能な更新を読み取ることができます。このプロトコルのトレードオフは、更新要求を送信したクライアントが、続行するために確認を受信するまで長時間待たなければならない可能性があることです。この問題は、更新をローカルで実行し、他のバックアップに更新の実行を依頼することで解決できます。非ブロッキング プライマリ バックアップ プロトコルは、すべてのバックアップ サーバーで更新の一貫性を保証するものではありません。ただし、パフォーマンスは向上します。プライマリ バックアップ プロトコルでは、このプロトコルはグローバルに一意の時間に基づいてすべての着信書き込みを順序付けるため、すべてのプロセスで書き込み操作の順序が同じになります。ブロッキング プロトコルは、プロセスが最後の書き込み操作の結果を表示することを保証します。

プライマリベースのローカル書き込みプロトコルでは、^[4]プライマリコピーは更新を実行するプロセス間を移動します。データ項目を更新するには、プロセスはまずそれをその場所に移動します。結果として、このアプローチでは、各プロセスがデータ項目のローカルコピーを読み取ることができる一方で、連続した書き込み操作をローカルで実行できます。プライマリが更新を完了すると、更新は他のレプリカに転送され、すべてがローカルで更新を実行します。この非ブロッキングアプローチにより、改善が期待できます。ローカル書き込みプロトコルの図は、プライマリベースのプロトコルにおけるローカル書き込みアプローチを示しています。プロセスがデータ項目 x への書き込み操作を要求します。現在のサーバーは、データ項目 x の新しいプライマリと見なされます。書き込み操作が実行され、要求が完了すると、プライマリは他のバックアップサーバーに更新要求を送信します。各バックアップは、更新操作を完了すると、プライマリに確認応答を送信します。

複製書き込みプロトコル^[4]では、プライマリベースのプロトコルとは異なり、すべての更新がすべてのレプリカに対して実行されます。

アクティブレプリケーション^[4]では、書き込み操作を実行するために各レプリカに関連付けられたプロセスがあります。言い換えれば、更新は実行するために操作の形で各レプリカに送信されます。すべての更新は、すべてのレプリカで同じ順序で実行する必要があります。その結果、完全に順序付けられたマルチキャストメカニズムが必要になります。大規模な分散システムでこのようなマルチキャストメカニズムを実装するには、スケーラビリティの問題があります。各操作を中央コーディネータ（シーケンサ）に送信する別のアプローチがあります。コーディネータは最初に各操作にシーケンス番号を割り当て、次に操作をすべてのレプリカに転送します。2番目のアプローチでもスケーラビリティの問題を解決できません。

投票は、複製書き込みプロトコルにおける別のアプローチです。このアプローチでは、クライアントは複製されたデータの読み取りと書き込みを行うために、複数のサーバーに許可を要求して受け取ります。例として、分散ファイルシステムで、ファイルが N 台のサーバーに複製されているとします。ファイルを更新するには、クライアントは少なくともN/2 + 1 台のサーバーに要求を送信して、更新を実行することに同意する必要があります。同意後、ファイルに変更が適用され、更新されたファイルに新しいバージョン番号が割り当てられます。同様に、複製されたファイルを読み取る場合、クライアントはN/2 + 1台のサーバーに要求を送信して、それらのサーバーから関連するバージョン番号を受け取ります。受信したすべてのバージョン番号が最新バージョンであれば、読み取り操作が完了します。^[4]

複製ファイルシステムでは、キャッシュ一貫性プロトコル^[4]がキャッシュの一貫性を提供しますが、キャッシュは通常クライアントによって制御されます。多くのアプローチでは、キャッシュの一貫性は基盤となるハードウェアによって提供されます。ミドルウェアベースの分散システムにおける他のアプローチでは、キャッシュの一貫性を提供するためにソフトウェアベースのソリューションを適用します。

キャッシュ一貫性モデルは、不整合が発生するタイミングを定義する一貫性検出戦略が異なる場合があります。不整合を検出するには、静的ソリューションと動的ソリューションの 2 つの方法があります。静的ソリューションでは、コンパイラがキャッシュの不整合を引き起こす可能性のある変数を特定します。そのため、コンパイラは不整合の問題を回避するための命令を実行します。動的ソリューションでは、サーバーが実行時に不整合をチェックし、キャッシュ後に変更されたキャッシュ データの一貫性を制御します。

一貫性の強制戦略は、別のキャッシュ一貫性プロトコルです。 サーバーにあるコピーを使用して、キャッシュの一貫性を提供する方法を定義します。データの一貫性を保つ 1 つの方法は、共有データをキャッシュしないことです。サーバーはデータを保持し、プライマリ ベースのプロトコルなどの一貫性プロトコルを適用して、共有データの一貫性を確保できます。このソリューションでは、クライアントはプライベート データのみをキャッシュできます。共有データがキャッシュされている場合、キャッシュ一貫性を強制するには 2 つの方法があります。

最初のアプローチでは、共有データが更新されると、サーバーは無効化をすべてのキャッシュに転送します。 2 番目のアプローチでは、更新が伝播されます。 ほとんどのキャッシュ システムは、これら 2 つのアプローチを適用するか、それらを動的に選択します。

• キャッシュコヒーレンス – メモリ位置のキャッシュされたすべてのコピーの等価性
• 分散共有メモリ – 各クラスタノードが大きな共有メモリにアクセスするソフトウェアおよびハードウェア実装フォールバックとしてウィキデータの説明を表示するページ
• 非均一メモリアクセス – マルチプロセッシングで使用されるコンピュータメモリ設計

• Paolo Viotti 、 Marko Vukolic ( 2016 )。「非トランザクション分散ストレージシステムにおける一貫性」。ACM Computing Surveys。49 ( 1 ) : 19:1–19:34。arXiv : 1512.00168。doi :10.1145 / 2926965。S2CID 118557  。
• Sezgin, Ali (2004 年 8 月)。共有メモリの形式化と検証(PDF) (博士論文)。ユタ大学。2024 年6 月 27 日閲覧。（貴重な参考資料が多数含まれています）
• Yelick, Katherine; Bonachea, Dan; Wallace, Charles (2004)、「UPC メモリ一貫性モデルの提案」v1.0 (PDF)、ローレンス バークレー国立研究所技術レポート、doi :10.2172/823757、LBNL-54983、2005年 5 月 20 日のオリジナル(PDF)からアーカイブ
• Mosberger, David (1993). 「メモリ一貫性モデル」.オペレーティングシステムレビュー. 27 (1): 18–26. CiteSeerX  10.1.1.331.2924 . doi :10.1145/160551.160553. S2CID  16123648.
• Sarita V. Adve、Kourosh Gharachorloo (1996 年 12 月)。「共有メモリ一貫性モデル: チュートリアル」(PDF)。IEEE Computer。29 (12): 66–76。CiteSeerX 10.1.1.36.8566。doi :10.1109/2.546611。2008 年 9 月 7日にオリジナル(PDF)からアーカイブ。2008年5 月 28日に取得。 
• Steinke, Robert C.; Gary J. Nutt (2004). 「共有メモリの一貫性の統一理論」Journal of the ACM . 51 (5): 800–849. arXiv : cs.DC/0208027 . doi :10.1145/1017460.1017464. S2CID  3206071.
• テリー、ダグ。「野球を通して説明する複製データの一貫性」Communications of the ACM 56.12 (2013): 82-89。https://www.microsoft.com/en-us/research/wp-content/uploads/2011/10/ConsistencyAndBaseballReport.pdf

• IETFスライド
• 最新マイクロプロセッサのメモリ順序付け、パート I およびパート II、Paul E. McKenney (2005) 著。Linux Journal