一貫性モデル (ソフトウェア)
 | この項目「一貫性モデル (ソフトウェア)」は翻訳されたばかりのものです。不自然あるいは曖昧な表現などが含まれる可能性があり、このままでは読みづらいかもしれません。（原文：en:Consistency model） 修正、加筆に協力し、現在の表現をより自然な表現にして下さる方を求めています。ノートページや履歴も参照してください。（2023年1月） |
 | この記事は別の言語から大ざっぱに翻訳されたものであり、場合によっては不慣れな翻訳者や機械翻訳によって翻訳されたものかもしれません。 |
 |
一貫性モデル（いっかんせいモデル、英: consistency model）または整合性モデル（せいごうせいモデル）は、分散共有メモリシステムや分散データストア（ファイルシステム、データベース、楽観的レプリケーションシステム、ウェブキャッシングなど）のような分散システムで使用される。システムは、メモリ上の操作が特定のルールに従っている場合、あるモデルをサポートしていると言う。データ一貫性モデルは、プログラマーとシステムの間の契約を規定するもので、プログラマーがルールに従えば、メモリは一貫しており、メモリの読み書きや更新の結果は予測可能であることをシステムが保証する。これは、キャッシュやキャッシュレスのシステムで発生するコヒーレンスとは異なり、すべてのプロセッサに対するデータの一貫性を意味する。コヒーレンスは、1つの場所や1つの変数への書き込みをすべてのプロセッサが見ることができるようなグローバルな秩序を維持することを意味する。一貫性とは、複数の場所への操作の順序を、すべてのプロセッサに対して維持することである。
C++ や Java などの高レベル言語では、メモリ操作を低レベルの操作に変換することで、メモリセマンティクスを維持しながら契約を部分的に維持している。契約を守るために、コンパイラは一部のメモリ命令を並べ替えたり、pthread_mutex_lock()などのライブラリコールは必要な同期をカプセル化したりする[1]。
モデル検査による逐次的な整合性の検証は、有限状態のキャッシュコヒーレンスプロトコルであっても、一般的には決定不可能である[2]。
一貫性モデルは、更新の見かけ上の順序と可視性に関するルールを定義しており、トレードオフの連続性を持っている[3]。
事例
[編集]次のようなケースが想定できる[3]。
- 行XはノードMとNに複製される
- クライアントAがノードMに行Xを書き込む
- 一定時間t後、クライアントBがノードNから行Xを読み出す
一貫性モデルは、クライアントAが行った書き込みをクライアントBが見ているかどうかを判断しなければならない。
類型
[編集]一貫性モデルの定義と分類には、発行と観測の2つの方法がある。
- 発行方式では、プロセスがオペレーションを発行する方法を定義する制限を記述する。
- プロセスから見える操作の順序を定義する観測方式。
例えば、一貫性モデルでは、以前に発行された操作がすべて完了するまで、プロセスが操作を発行することはできないと定義することができる。一貫性モデルによって、適用される条件は異なる。ある一貫性モデルは、そのモデルのすべての条件とそれ以上の条件を必要とする場合、他のモデルよりも強いと考えることができる。言い換えれば、制約条件が少ないモデルは、弱い一貫性モデルと考えられうる。
これらのモデルは、ハードウェアがどのように配置されるべきかを定義し、プログラマがどのようにコーディングするべきかを高いレベルで定義する。選択されたモデルは、コンパイラがどのように命令を並べ替えるかにも影響してくる。一般的には、命令間の制御依存関係や同じ場所への書き込みが順序づけられていれば、コンパイラは必要に応じて命令を並べ替えることができる。しかし、以下に説明するモデルでは、ロード前の書き込みを順序変更できるものとできないものがある。
厳密な一貫性
[編集]厳密な一貫性は、最も強力な一貫性モデルである。このモデルでは、任意のプロセッサによる変数への書き込みは、すべてのプロセッサによって瞬時に確認される必要がある。
厳密モデルの図と非厳密モデルの図は、時間の制約である「瞬間」を表している。これは、あたかもグローバルクロックが存在し、すべての書き込みがそのクロック期間の終わりまでにすべてのプロセッサのキャッシュに反映されなければならないように理解することができる。次の操作は、次のクロック期間にのみ行われなければならない。
| シーケンス | 厳密なモデル | 非厳密なモデル | ||
|---|---|---|---|---|
| P1 | P2 | P1 | P2 | |
| 1 | W(x)1 | W(x)1 | ||
| 2 | R(x)1 | R(x)0 | ||
| 3 | R(x)1 | |||
これは最も厳格なモデルである。このモデルでは、プログラマーが期待した結果が毎回返ってくる。よって決定論的なモデルである。瞬間的なメッセージ交換は不可能なので、実用的な関連性は思考実験と形式論に限られる。また、同時書き込みが不可能であることを前提としているため、同じデータアイテムへの同時書き込みにおける衝突解決の問題にも役立たない。
逐次一貫性
[編集]逐次一貫性（整合性）モデルは、ランポート(1979)によって提唱された。厳密な一貫性モデルよりも弱いメモリモデルである。変数への書き込みは瞬時に確認される必要はないが、異なるプロセッサによる変数への書き込みは、すべてのプロセッサで同じ順序で確認されなければならない。ランポート(1979)の定義によると、「任意の実行結果が、すべてのプロセッサの操作が何らかの順序で実行された場合と同じであり、個々のプロセッサの操作が、そのプログラムで指定された順序でこの順序に現れる」場合に、逐次整合性が満たされる[4]。
各プロセッサ内のプログラムの順序と、プロセッサ間の操作の順序は維持されるべきである。プロセッサ間の実行の順序を維持するためには、すべての操作が他のすべてのプロセッサに対して瞬間的または不可分的に実行されているように見えなければならない。情報を瞬時に送信することは物理的に不可能なので、これらの操作は完了したように見えればよい。例えば、単一のグローバル共有バスを利用したシステムでは、バスラインに情報がポストされると、すべてのプロセッサが同じ瞬間にその情報を見ることが保証される。そのため、バスラインに情報を渡すことで、すべてのプロセッサに対して実行が完了し、実行されたように見える。キャッシュレス・アーキテクチャや、インターコネクト・ネットワークが瞬間的ではないキャッシュ・アーキテクチャでは、プロセッサとメモリの間にスロー・パスが含まれることがある。このような遅い経路では、あるメモリが他のメモリよりも早くブロードキャストデータを受け取るため、シーケンシャルな不整合が生じる可能性がある。
逐次一貫性は、非決定的な結果をもたらすことがある。これは、プロセッサ間の逐次操作の順序が、プログラムの異なる実行時に異なる可能性があるためである。すべてのメモリ操作は、プログラムの順番通りに行われる必要がある。
線形化可能性（不可分整合性とも呼ばれる）は、逐次一貫性にリアルタイム制約を加えたものと定義できる。
因果一貫性
[編集]因果一貫性（因果整合性）とは、イベントを因果関係のあるものとないものに分類することで、順序の整合性を弱めるモデルである。このモデルでは、因果関係のある書き込み操作だけが、すべてのプロセスから同じ順序で見られる必要があると定義している。
このモデルでは、プロセッサによる同時書き込みと、因果関係のない書き込みについて、逐次整合性（逐次一貫性）を緩和している。2つの書き込みが因果関係を持つのは、1つの変数への書き込みが、任意の変数への以前の書き込みに依存している場合、2つ目の書き込みを行うプロセッサが1つ目の書き込みを読んだばかりの場合である。2つの書き込みは、同じプロセッサで行われた場合もあれば、異なるプロセッサで行われた場合もある。
逐次整合性（逐次一貫性）と同様に、読み取りは変更を瞬時に反映させる必要はないが、変数へのすべての変更を逐次反映させる必要がある。
| シーケンス | P1 | P2 |
|---|---|---|
| 1 | W1(x)3 | |
| 2 | W2(x)5 | |
| 3 | R1(x)3 |
W1はW2とは因果関係がない。
| シーケンス | P1 | P2 | P3 | P4 |
|---|---|---|---|---|
| 1 | W(x)1 | R(x)1 | R(x)1 | R(x)1 |
| 2 | W(x)2 | |||
| 3 | W(x)3 | R(x)3 | R(x)2 | |
| 4 | R(x)2 | R(x)3 |
W(x)1とW(x)2は、W(x)2の前にP2がxに対して行った読み取りにより、因果関係がある[5]。
プロセッサ一貫性
[編集]データの一貫性を保ち、各プロセッサが独自のメモリを持つスケーラブルなプロセッサシステムを実現するために、プロセッサの一貫性モデルが考案された[5]。すべてのプロセッサは、あるプロセッサが行った書き込みを見る順序と、異なるプロセッサが同じ場所に書き込んだ書き込みを見る順序が一致している必要がある（コヒーレンスの維持）。しかし、異なるプロセッサが異なる場所に書き込んだ場合には、一貫性を保つ必要はない。
すべての書き込み操作は、すべてのメモリに対するいくつかのサブ書き込みに分割することができる。このようなメモリからの読み出しは、このメモリへの書き込みが完了する前に起こる可能性がある。そのため、読み込まれたデータが古くなってしまうことがある。したがってプロセッサ一貫性下のプロセッサは、古いストアをストールする必要があるときに、より新しいロードを実行することができる。このモデルでも、Read before write、Read after read、Write before writeの順序は守られている。
プロセッサ一貫性モデルは、PRAM一貫性モデルに似ているが、同じメモリ位置へのすべての書き込みが、他のすべてのプロセスから同じ順序で見えるようにしなければならないという、より強い条件を備えている。プロセッサ整合性は、逐次整合性よりは弱いが、PRAM整合性モデルよりは強い[6]。
Stanford DASHマルチプロセッサシステムでは、Goodmanの定義と比較できない（弱くもなく強くもない）プロセッサ一貫性のバリエーションを実装している[7]。すべてのプロセッサは、あるプロセッサによる書き込みを見る順序と、異なるプロセッサによる同じ場所への書き込みを見る方法が一貫している必要がある。しかし、異なるプロセッサによる異なる場所への書き込みについては、一貫性を保つ必要はない。
パイプラインRAM一貫性 (またはFIFO一貫性)
[編集]パイプラインRAM整合性（PRAM整合性）は、1988年にLiptonとSandberg[8]によって最初に記述された一貫性（整合性）モデルの1つとして発表された。非公式な定義のため、実際には少なくとも2つの微妙に異なる実装があり、1つはAhamadらによるもの、もう1つはMosbergerによる[7]。
PRAM一貫性では、すべてのプロセスが、あるプロセスの操作を、そのプロセスが発行したのと同じ順序で見るが、異なるプロセスが発行した操作は、異なるプロセスから異なる順序で見ることができる。PRAMの一貫性は、プロセッサの一貫性よりも弱い。PRAMでは、ある場所へのコヒーレンスをそのプロセッサ全体で維持する必要性が緩和されている。ここでは、任意の変数への読み出しは、プロセッサ内で書き込みの前に実行することができる。このモデルでは、書き込み前の読み取り、読み取り後の読み取り、書き込み前の書き込みの順序は維持される。
| Sequence | P1 | P2 | P3 | P4 |
|---|---|---|---|---|
| 1 | W(x)1 | |||
| 2 | R(x)1 | |||
| 3 | W(x)2 | |||
| 4 | R(x)1 | R(x)2 | ||
| 5 | R(x)2 | R(x)1 |
キャッシュ一貫性
[編集]キャッシュ整合性 (一貫性) [6][9]は、同じメモリ位置へのすべての書き込み操作が、ある順序で実行されることを必要とする。キャッシュの整合性は、プロセッサの整合性よりも弱く、PRAMの整合性とは比較にならない。
遅い一貫性
[編集]
遅い一貫性[9] では、あるプロセスがメモリの場所に以前に書き込まれた値を読み取ると、その後その場所から以前の値を読み取ることはできない。また、あるプロセスが行った書き込みは、そのプロセスがすぐに見ることができる。遅い一貫性は、PRAMやキャッシュコンシステンシーよりも弱いモデルである。
例: 遅いメモリーの図は、遅い一貫性の例を描いている。最初のプロセスがメモリロケーションXに1を書き込み、次にメモリロケーションYに1を書き込む。2番目のプロセスがYから1を読み込み、XがYより先に書き込まれたにもかかわらず、Xから0を読み込む。
Hutto, Phillip W., and Mustaque Ahamad (1990)[10]は、適切なプログラミングによって、スローメモリ（一貫性）が表現力と効率性を持つことを説明している。彼らは、スローメモリには2つの価値ある特性があると述べている。それは、局所性と不可分的メモリからの削減をサポートすることである。彼らはスローメモリの表現力を示すために2つのアルゴリズムを提案している。
以下のモデルでは、プログラマーによる特定の同期を必要とする。
弱い順序 (ウィークオーダリング)
[編集]プログラムの順序やアトミック性（不可分性）は、すべての読み取りと書き込みではなく、特定の操作に対してのみ維持される。これは、クリティカルセクションで行われるようなある種のメモリ操作は、クリティカルセクション内のすべての操作が完了するまで、すべてのプロセッサには見えないようにする必要があるという理解に基づいている。また、マルチプロセッサシステムで実行されるプログラムには、データレースが起こらないように必要な同期が含まれており、常に逐次一貫性の結果が得られるようになっていることを利用している。このように、弱い順序（ウィークオーダリング）では、同期操作以外の操作をデータ操作に分類することができる[11]。
| プロセッサー1 | プロセッサー2 |
|---|---|
X = 1; fence xready = 1; |
fence
while (!xready) {};
fence
y = 2;
|
同期操作は、すべてのプロセッサによって行われた以前のすべての操作を完了して見たことを確認するために、プロセッサに信号を送信する。弱い順序を維持するために、同期操作の前の書き込み操作は、同期操作の前にグローバルに実行されなければならない。また、同期操作の後に存在する操作は、同期操作が完了した後にのみ実行されなければなりません。したがって、同期変数へのアクセスは逐次的に一貫しており、読み出しや書き込みは、以前の同期操作が完了した後にのみ実行されなければならない。このモデルでは、一貫性は緩和されない。これらの要件が満たされていれば、他のすべての「データ」操作の順序を変更することができる。
プログラム内の明示的な同期への高い依存度がある。弱い順序モデルでは、プログラマは、テスト＆セット、fetch-and-op、ストア・コンディショナル、ロード・リンクなどのアトミック・ロック命令を使用するか、同期変数にラベルを付けるか、フェンスを使用しなければならない。
リリース一貫性
[編集]リリース一貫性モデルは、入口の同期操作と出口の同期操作を区別することで、弱一貫性モデルを緩和する。弱い順序では、同期操作を見ようとするとき、同期操作が完了してプロセッサが進む前に、すべてのプロセッサのすべての操作が見える必要がある。しかし、リリース一貫性モデルでは、「アクワイア（取得）」と呼ばれるクリティカルセクションへの入り口では、ローカルメモリ変数に関するすべての操作が完了している必要があります。また、「リリース（解放）」と呼ばれる終了時には、ローカルプロセッサで行われたすべての変更が他のすべてのプロセッサに伝搬される必要がある。コヒーレンスは維持される。
アクワイア（取得）操作は、クリティカルセクションにアクセスするために実行されるロード/リード（読み込み）である。リリース（解放）操作は、他のプロセッサに共有変数を使用させるために実行されるストア/ライト（書き込み）である。
同期変数の中でも、逐次（シーケンシャル）一貫性やプロセッサ一貫性を保つことができる。逐次一貫性では、競合するすべての同期変数を順番に処理する必要がある。しかし、プロセッサ一貫性では、競合する変数のペアは、この順序に従うだけでよい。新しい取得者（アクワイアする者）が古いリリース（解放）の前に起こることを許容することができる[12]。
エントリー一貫性
[編集]リリース一貫性モデルの一種である。クリティカルセクションへの進入・退出を明示するために、アクワイア（取得）命令とリリース（取得）命令を使用する必要がある。しかし、エントリ一貫性では、すべての共有変数に、その変数に固有の同期変数が割り当てられる。このようにして、変数xに対する取得のときだけ、そのプロセッサに関してxに関連するすべての操作を完了する必要がある。これにより、異なる共有変数の異なるクリティカルセクションの同時操作が可能となる。同一の共有変数に対するクリティカルな操作では同時性は見られない。このような一貫性モデルは、異なる行列要素を同時に処理できる場合に有効である。
一般的な一貫性
[編集]一般的な一貫性[13]では、すべてのプロセスの書き込みが完了した後、メモリ位置のすべてのコピーが最終的に同一になる。
局所一貫性
[編集]ローカル一貫性（局所整合性）[9]では、各プロセスは自分のプログラムで定義された順序で自分の操作を行う。他のプロセスの書き込み操作がどのような順序で行われるかについては、何の制約もない。ローカルコンシステンシーは、共有メモリシステムにおいて最も弱いコンシステンシーモデルである。
緩和型メモリ一貫性モデル
[編集]緩和型一貫性モデルと呼ばれる、逐次一貫性の要件を緩和した一貫性モデルがある[14]。これらの一貫性モデルは、ハードウェアレベルでのメモリ一貫性を提供しない。実際には、プログラマーは同期技術を適用してメモリ一貫性を実装する責任がある。上記のモデルは、4つの基準に基づいて分類されており、さらに詳しく説明する。
緩和した一貫性を定義するために、4つの比較がある。
緩和
[編集]緩和された整合性を分類する一つの方法は，どの逐次整合性要件を緩和するかを定義することである。Adve and Gharachorloo, 1996で定義されたプログラム順序や書き込み原子性の要件を緩和することで、より厳密ではないモデルを作ることができる[15]。プログラム順序は、各プロセスがプログラムによって順序付けられたメモリ要求を発行することを保証し、書き込み不可分性は、メモリ要求が単一のFIFOキューの順序に基づいて処理されることを定義している。プログラム順序の緩和では、write-after-write、read-after-write、read/write-after-readのいずれかまたはすべての操作ペアの順序を緩和することができる。緩和された書き込みの不可分性モデルでは、プロセスは他のプロセッサよりも先に自分の書き込みを見ることができる。
同期型と非同期型
[編集]同期モデルとは、メモリアクセスを2つのグループに分け、それぞれのグループに異なる一貫性制約を割り当てることで定義される。これは、一方のグループには弱い一貫性モデルが必要であり、他方のグループにはより厳しい一貫性モデルが必要であることを考慮したものである。一方、非同期型モデルでは、メモリアクセスタイプに同じ一貫性モデルを割り当てる。
発行方式と観測方式の比較
[編集]発行法式[9]は、プロセスがメモリ操作を行う際の制限を定義することで、逐次的整合性シミュレーションを行う。一方、観測方式は、プロセスのイベント順序に対する可視性の制限を記述する。
相対的なモデルの強さ
[編集]一貫性モデルの中には、他のモデルよりも制限が厳しいものがある。言い換えれば、厳密な一貫性モデルは、より多くの制約を一貫性要件として強制する。モデルの強さは、プログラムの順序や不可分性の緩和によって定義され、モデルの強さを比較することもできる。あるモデルは、同じ緩和を適用しているか、それ以上の緩和を適用している場合、直接に関係している。一方、異なる要件を緩和したモデルは直接関係しない。
逐次整合性（一貫性）には、プログラム順序と書き込みの不可分性という2つの要件がある。これらの要件を緩和することで、異なる緩和された一貫性モデルを得ることができる。これは、緩和された制約とともに、性能が向上するように行われるが、プログラマは、同期技術を適用してメモリ一貫性を実装する責任があり、ハードウェアを十分に理解していなければならない。
緩和の可能性:
- 書き込みから読み込みへのプログラム順序
- 書くために書くプログラムの順序
- 読み込みから読み込みと読み込みから書き込みのプログラム命令
緩和型モデル
[編集]以下のモデルは、緩和された一貫性のいくつかのモデルです。
緩和された書き込みから読み出し
[編集]ハードウェアレベルで性能を向上させるためのアプローチとして、書き込みの後に読み出しを行うプログラム順序（PO）を緩和することで、書き込み操作のレイテンシーを効果的に隠すことができる。この種の緩和は、プロセッサからの以前の書き込みに対して、後続の読み取りの順序を緩和するという最適化に依存している。この緩和のために、XXXのようないくつかのプログラムは、逐次一貫性（SC）の結果を出すことができないかもしれない。一方、YYYのようなプログラムは、残りのプログラム順序制約が適用されているため、一貫した結果が得られることが期待される。
3つのモデルが該当する。IBM 370モデルは、最も厳格なモデルである。読み取りは、異なるアドレスへの先の書き込みの前に完了することができるが、すべてのプロセッサが書き込みを見ていない限り、書き込みの値を返すことは禁止されている。SPARC V8のTSO（total store ordering model）モデルは、IBM 370モデルを部分的に緩和したもので、同じ場所への他の書き込みに対して、自分のプロセッサの書き込みの値を返すことができる。前述のモデルと同様に、これもすべてのプロセッサが書き込みを見ていない限り、書き込みの値を返すことはできない。プロセッサ一貫性モデル（PC）は、3つのモデルの中で最も緩和されたモデルであり、両方の制約を緩和して、他のプロセッサから見えるようになる前であっても、以前の書き込みよりも先に読み取りが完了できるようにしている。
例Aでは、IBM 370ではwrite(A)が完了するまでread(A)が発行されないため、この結果はIBM 370でのみ可能である。一方、TSOやPCでは、1つのプロセッサでフラグの書き込みが完了する前にフラグの読み出しが可能なため、この結果が得られる。
例Bでは、P2がP3に表示される前に書き込みの値を返すことができるため、PCでのみ可能となる。これは、他の2つのモデルでは不可能である。
上記のモデルでは、順序の一貫性を確保するために、セーフティネットやフェンスを用いて手動で制約をかけています。IBM370モデルでは、操作の間に手動で配置される特殊な直列化命令があります。これらの命令は、メモリ命令や分岐などの非メモリ命令で構成される。一方、TSOモデルやプロセッサ一貫性（PC）モデルではセーフティネットが用意されてないが、プログラマはリードモディファイ・ライトオペレーションを使用して、書き込みとそれに続く読み出しの間でプログラムの順序が維持されているように見せることができる。TSOの場合、すでにR-modify-Wの一部となっているRまたはWをR-modify-Wに置き換えれば、プログラム順序（PO）が維持されているように見えるが、これにはR-modify-WのWが読み取り値を返す「ダミー」であることが必要である。PCについても同様に、リードがライトに置き換えられたり、すでにR-modify-Wの一部になっていたりしても、プログラム順序（PO）は維持される。
しかし、この緩和だけを行使しても、コンパイラ最適化はできない。コンパイラ最適化には、プログラム順序（PO）内の任意の2つの操作を並べ替えることができる完全な柔軟性が必要なので、リードに対するライトの並べ替え機能は、この場合には十分に役立たない。
| プロセッサー1 | プロセッサー2 |
|---|---|
| A = flag1 = flag2 = 0 | |
| flag1 = 1 | flag2 = 1 |
| A = 1 | A = 2 |
| reg1 = A | reg3 = A |
| reg2 = flag2 | reg4 = flag1 |
| reg1 = 1; reg3 = 2, reg2 = reg4 = 0 | |
| プロセッサー1 | プロセッサー2 | プロセッサー3 |
|---|---|---|
| A = B = 0 | ||
| A = 1 | ||
| if (A == 1) | ||
| B = 1 | if (B == 1) | |
| reg1 = A | ||
| B = 1, reg1 = 0 | ||
書き込み→読み込み、書き込み→書き込みの緩和
[編集]モデルによっては、プログラムの順序をさらに緩和し、異なる場所への書き込み間の順序制約さえも緩和するものもある。SPARC V8のパーシャルストアオーダーモデル（PSO）は、このようなモデルの唯一の例である。同じプロセッサから異なる場所への書き込みをパイプライン化し、オーバーラップさせることができることが、PSOが可能にする重要なハードウェア最適化である。PSOは、プロセッサが自分の書き込みの値を読み取ることができ、他のプロセッサが他のプロセッサの書き込みを読み取ることができないようにするという点で、不可分性の要件についてはTSOと同様である。2つの書き込み間のプログラム順序は、PSOでは明示的なSTBAR命令を用いて維持される。このSTBAR命令は、FIFO書き込みバッファを持つ実装では、書き込みバッファに挿入される。カウンタは、STBAR命令以前のすべての書き込みが完了したかどうかを判断するために使用され、メモリシステムへの書き込みが開始されてカウンタが増加します。書き込み確認でカウンタが減少し、カウンタが0になると、それまでの書き込みがすべて完了したことになる。
例Aと例Bでは、PSOによってこれらの非連続的に一貫した結果が得られる。PSOが提供するセーフティーネットはTSOのものと同様で、書き込みから読み出しまでのプログラムの順序を決め、書き込みの不可分性を強制する。
前のモデルと同様に、PSOが許容する緩和は、コンパイラの最適化に役立つほど十分に柔軟ではなく、もっと柔軟な最適化が必要である。
読み取りと読み取りから書き込みへのプログラム命令の緩和
[編集]いくつかのモデルでは、異なる場所へのすべての操作が緩和される。読み込みや書き込みは、別の場所にある別の読み込みや書き込みを基準にして、順序を変えることができる。弱い順序はこのカテゴリに分類され、2種類のリリース一貫性モデル(RCscとRCpc)もこのモデルに含まれる。また、この緩和のカテゴリには、Digital Alpha、SPARC V9 relaxed memory order (RMO)、IBM PowerPCの3つの商用アーキテクチャが提案されていた。これらのモデルは、Digital Alphaを除いて、同じ場所への読み出しの再順序付けが可能だった。これらのモデルでは、従来のモデルにはない追加的な緩和が認められており、読み出し操作に続くメモリ操作は、読み出しに対してオーバーラップして順序を変更することができる。RCpcとPowerPCを除くこれらのモデルでは、読み出しが他のプロセッサの初期書き込みの値を返すことができる。プログラマーの観点からすると、これらのモデルは、プロセッサが自分の書き込みを早く読むことができるにもかかわらず、書き込みの不可分性の錯覚を維持しなければならない。
これらのモデルは、提供されるセーフティネットの種類に基づいて2つのカテゴリーに分類される。ここでは、慎重に書かれたプログラムの必要性が見られる。同期の性質によって、弱い命令、RCsc、RCpcモデルに分類される。Alpha、RMO、PowerPCモデルでは、フェンス命令が用意されており、異なるメモリ操作の間にプログラムの順序を課すことができる。
弱い順序
[編集]上記の制約のほとんどを緩和したモデルの例として、弱い順序(Weak Ordering)がある（他のプロセッサの書き込みを早く読むことを除く）。このモデルでは、メモリ操作をデータ操作と同期操作の2つのカテゴリに分類します。プログラムの順序を強制するために、プログラマはプログラムの中に少なくとも1つの同期操作を見つける必要がある。これが機能する前提は、同期操作の間にデータ領域へのメモリ操作を並べ替えても、プログラムの結果には影響しないということである。同期操作は、プログラムの順序を守るためのセーフティネットとして機能する。この仕組みは、データ操作の回数をカウンターで追跡し、このカウンターがゼロになるまで、同期操作は発行されないというものである。さらに、以前の同期操作がすべて完了しない限り、それ以上のデータ操作は発行されない。2つの同期変数の間にあるメモリ操作は、プログラムの正しさに影響を与えることなく、オーバーラップしたり、順序を変えたりすることができる。このモデルでは、書き込みの不可分性が常に維持されるため、弱い順序のための追加のセーフティネットは必要ありません。
リリース一貫性 RCscとRCpc
[編集]リリース一貫性には、RCsc (release consistency with sequential consistency)とRCpc (release consistency with processor consistency)の2種類がある。後者のタイプは、以下で特殊とされる操作に適用される一貫性のタイプを示す。
特殊な(通常の)メモリ操作があり、それは同期操作と非同期操作の2つのクラスの操作からなる。後者は同期に使用されない操作で、前者はアクイジション（取得）とリリース（解放）の操作で構成される。アクイジションとは、ある特定の共有ロケーションへのアクセスを得るための、事実上のリードメモリ操作のことである。一方、リリースとは、共有されている場所へのアクセス許可を与えるために行われる書き込み操作である。
リリース一貫性と逐次一貫性（RCsc）の場合、制約条件は次のようになる。
- アクワイア（取得） → その他の操作
- その他の操作 → リリース（解放）
- 特殊操作 → 特殊操作
プロセッサ一貫性とリリース一貫性（RCpc）では、プログラムの書き込みから読み出しまでの順序が緩和され、次のような制約となる。
- アクワイア（取得） → その他の操作
- その他の操作 → リリース（解放）
- 特殊操作 → 特殊操作 (特殊な書き込みの後に特殊な読み込みが続く場合を想定)。
注：上記のA→Bという表記は、プログラム順でAの操作がBよりも先に行われた場合、プログラム順が強制されることを意味する。
トランザクショナル・メモリー・モデル
[編集]トランザクショナル・メモリー・モデルは、ソフトウェアまたはハードウェアでサポートされる共有メモリ・システムの通信モデルとして、キャッシュ・コヒーレンシーとメモリ一貫性モデルを組み合わせたもので、トランザクション・メモリ・モデルはメモリ一貫性とキャッシュ・コヒーレンシーの両方を提供する。トランザクションとは、一貫性のある状態から別の状態にデータを変換するプロセスによって実行される一連の操作のことである。トランザクションには、衝突がない場合にコミットするものと、中止するものがある。コミットでは、トランザクションが完了したときにすべての変更が他のすべてのプロセスから見えるようになるが、アボートではすべての変更が破棄される。緩和した整合性（一貫性）モデルと比較して、トランザクションモデルは使いやすく、シーケンシャルな整合性（一貫性）モデルよりも高いパフォーマンスを提供することができる。
一貫性とレプリケーション
[編集]Tanenbaum et al., 2007[16]は、レプリケーションを行う主な理由として、信頼性とパフォーマンスの2つを定義している。信頼性は、複製されたファイルシステムにおいて、現在のレプリカが故障した場合に、別のレプリカに切り替えることで実現できる。また、レプリケーションは、異なるレプリカに複数のデータのコピーを提供することで、データの破損を防ぐ。作業を分担することで、パフォーマンスを向上させることもできる。レプリケーションは、パフォーマンスと信頼性を向上させる一方で、複数のデータコピー間で一貫性の問題を引き起こす可能性がある。複数のコピーは、読み取り操作がすべてのコピーから同じ値を返し、単一の不可分操作（トランザクション）としての書き込み操作が、他の操作が行われる前にすべてのコピーを更新する場合、一貫性が保たれる。Tanenbaum, Andrew, & Maarten Van Steen, 2007は、この種の一貫性を、同期レプリケーションが提供するタイトな（堅い）一貫性と呼んでいる。しかし、すべてのコピーの一貫性を保つためにグローバルな同期を適用することはコストがかかる。グローバル同期のコストを削減し、性能を向上させる方法として、一貫性の制限を弱めることが考えられます。
データ中心の一貫性モデル
[編集]Tanenbaum et al., 2007[16]は、一貫性モデルをソフトウェア（プロセス）とメモリ実装（データストア）の間の契約と定義している。このモデルは、ソフトウェアが一定のルールに従えば、メモリが正しく動作することを保証するものである。グローバルクロックを持たないシステムでは、書き込みの中で最後の操作を定義することが難しいため、読み出し操作で返せる値に何らかの制限を加えることができる。
一貫性のある操作の順序
[編集]逐次整合性モデルや因果整合性モデルなどの整合性モデルでは、一貫性を確保するために、複製された共有データに対する操作の順序を扱う。これらのモデルでは、すべてのレプリカが、一貫したグローバルな更新順序に同意しなければならない。
逐次（シーケンシャル）一貫性
[編集]データ中心の一貫性（整合性）モデルの目的はプロセスが並行して更新を行う可能性のあるデータストアに一貫したビューを提供することである。重要なデータ中心一貫性モデルの1つに、Lamport (1979) によって定義された逐次一貫性がある[4]。Tanenbaum et al(2007)[16]は、逐次一貫性を以下の条件で定義している。
任意の実行結果は，データストア上のすべてのプロセスによる（読み書きの）操作が何らかの順序で実行され，個々のプロセスの操作がそのプログラムで指定された順序でこの順序に現れる場合と同じである。
Adve and Gharachorloo, 1996[15]は，逐次整合性を実現するための要件として，プログラムの順序と書き込みの不可分性の2つを定義している．
- プログラムオーダー：各プロセスがメモリ要求をプログラムの順番で発行することを保証する。
- 書き込み不可分性：書き込みの不可分性は、メモリ要求が単一のFIFOキューの順序に基づいて処理される。
逐次整合性では、時間や最新の書き込み操作という概念はない。すべてのプロセスで同じように、いくつかの操作のインターリーブがある。あるプロセスは、すべてのプロセスの書き込み操作を見ることができるが、自分の読み取り操作を見ることができるだけである。
線形化可能性(不可分メモリ)[17][14]は、各操作の開始時刻と終了時刻を考慮することにより、実時間制約のある逐次一貫性として定義できる。各操作の開始時刻と終了時刻の間に点を置くことにより、各操作が線形化可能な順序で行われ、逐次的な一貫性が保証される場合、実行は線形化可能である。
因果整合性
[編集]Hutto and Ahamad, 1990により定義された因果整合性は、因果関係のある操作とそうでない操作を区別することで、逐次整合性よりも弱い整合性モデルである。例えば、ある事象bがそれ以前の事象aから影響を受ける場合、因果的整合性は、すべてのプロセスが事象aの後に事象bを見ることを保証する。
Tanenbaum et al., 2007[16]では、以下の条件でデータストアが因果的に一貫しているとみなされると定義しています。
因果関係がある可能性のある書き込みは、すべてのプロセスで同じ順序で見られなければならない。同時書き込みは異なるマシンでは異なる順序で見られる可能性がある。
結果一貫性
[編集]結果整合性（一貫性）は、同時更新のないシステムにおける弱い整合性（一貫性）モデルである。これは、更新がない状態が非常に長い時間続くと、すべてのレプリカが最終的に一貫性を持つようになることを定義している。
ほとんどの共有分散型データベースは、BASE：基本的に利用可能、ソフトな状態、最終的に一貫性がある、またはACIDとBASEを組み合わせたSALT：逐次的、合意された、導かれた、改ざんされない、また、対称的、管理者なし、導かれた、時間的に合意された、のいずれかの最終的な一貫性モデルを持っている。
グルーピング操作
[編集]グルーピング操作では、同期変数へのアクセスは逐次一貫している。プロセスは、以前の書き込みがすべて完了した同期変数へのアクセスを許可される。つまり、同期変数に対するすべての操作が完了するまで、同期変数へのアクセスは許可されない。
分散システムでは、同時処理を制御するために逐次一貫性を維持することが不可欠である。しかし同時(並行)更新のない特殊なデータストアでは、クライアント中心一貫性モデルを用いることで、よりコストのかからない方法で不整合を処理することができる。以下のモデルは、クライアント中心一貫性モデルの一例である。
単調な読み込み一貫性
[編集]Tanenbaum et al., 2007[16]は、単調な読み込み一貫性を次のように定義しています。
あるプロセスがデータアイテムxの値を読み取った場合，そのプロセスによるxに対する連続した読み取り操作は，常に同じ値またはより最近の値を返す[16]。
単調な読み込み一貫性は、あるプロセスが時刻tにデータ項目xの値を読み込んだ後、そのデータ項目のより古い値を見ることがないことを保証する。
単調な書込み一貫性（Monotonic Write consistency)
[編集]単調書込み一貫性条件は、Tanenbaum et al., 2007[16]によって以下のように定義されている。
あるプロセスによるデータアイテムXへの書き込み操作は、同じプロセスによるXへの連続した書き込み操作の前に完了する[16]。
書き込んだ値の読み込み一貫性 (Read-your-writes)
[編集]あるプロセスがデータ項目Xに対して書き込んだ値は、同じプロセスがデータ項目Xに対して行う連続した読み取り操作に対して常に利用可能である[16]。
書き込み追従型一貫性 (Writes-Follows-Reads)
[編集]書き込み追従型一貫性では，更新は前の読み取り操作を実行した後に伝搬される．Tanenbaum et al., 2007[16]では、Writes-follows-reads consistencyの条件を以下のように定義している。
あるプロセスによるデータアイテムxへの書き込み操作が，同じプロセスによるxへの以前の読み取り操作の後に行われた場合，読み取られたxと同じかより新しい値に対して行われることが保証される[16]。
脚注
[編集]- ^ Mark D. Hill (August 1998). “Multiprocessors Should Support Simple Memory Consistency Models”. IEEE Computer 31 (8): 28–34. doi:10.1109/2.707614.
- ^ Shaz Qadeer (August 2003). “Verifying Sequential Consistency on Shared-Memory Multiprocessors by Model Checking”. IEEE Transactions on Parallel and Distributed Systems 14 (8): 730–741. arXiv:cs/0108016. doi:10.1109/TPDS.2003.1225053.
- ^ a b Todd Lipcon (2014年10月25日). “Design Patterns for Distributed Non-Relational Databases”. 2011年3月24日閲覧。 “A consistency model determines rules for visibility and apparent order of updates. Example: * Row X is replicated on nodes M and N * Client A writes row X to node N * Some period of time t elapses. * Client B reads row X from node M * Does client B see the write from client A? Consistency is a continuum with tradeoffs”
- ^ a b Lamport, Leslie (Sep 1979). “How to make a multiprocessor computer that correctly executes multiprocess programs.”. IEEE Transactions on Computers C-28 (9): 690–691. doi:10.1109/TC.1979.1675439.
- ^ a b “Memory Consistency Models”. 28 July 2021閲覧。
- ^ a b Goodman, James R (1991). “Cache consistency and sequential consistency”. IEEE Scalable Coherent Interface (SCI) Working Group.
- ^ a b Senftleben, Maximilian (2013). Operational Characterization of Weak Memory Consistency Models (PDF) (M.Sc. thesis). University of Kaiserslautern.
- ^ Lipton, R.J.; J.S. Sandberg. (1988). PRAM: A scalable shared memory (Technical report). Princeton University. CS-TR-180-88。
- ^ a b c d Steinke, Robert C.; Gary J. Nutt (2004). “A unified theory of shared memory consistency.”. Journal of the ACM 51 (5): 800–849. arXiv:cs/0208027. doi:10.1145/1017460.1017464.
- ^ Hutto, Phillip W.; Mustaque Ahamad (1990). Slow memory: Weakening consistency to enhance concurrency in distributed shared memories.. 302–309. doi:10.1109/ICDCS.1990.89297. ISBN 978-0-8186-2048-5
- ^ “Shared Memory Consistency Models : A tutorial”. 28 July 2021閲覧。
- ^ Solihin, Yan (2009). Fundamentals of Parallel Computer Architecture. Solihin Books
- ^ Singhal, Mukesh; Niranjan G. Shivaratri (1994). “Advanced concepts in operating systems.”. McGraw-Hill, Inc.
- ^ a b Mankin, Jenny (2007). CSG280: Parallel Computing Memory Consistency Models: A Survey in Past and Present Research.
- ^ a b c d e f g h i j k l Tanenbaum, Andrew; Maarten Van Steen (2007). “Distributed systems”. Pearson Prentice Hall.
- ^ Herlihy, Maurice P.; Jeannette M. Wing (July 1990). “"Linearizability: A correctness condition for concurrent objects." ACM Transactions on Programming Languages and Systems”. ACM Transactions on Programming Languages and Systems 12 (3): 463–492. doi:10.1145/78969.78972.
参考文献
[編集]- Paolo Viotti; Marko Vukolic (2016). “Consistency in Non-Transactional Distributed Storage Systems”. ACM Computing Surveys 49 (1): 19:1–19:34. arXiv:1512.00168. doi:10.1145/2926965.
- Ali Sezgin (2004). Formalization and verification of shared memory. (contains many valuable references)
- Kathy Yelick; Dan Bonachea; Chuck Wallace (2004). A Proposal for a UPC Memory Consistency Model (v1.0).
- Mosberger, David (1993). “Memory Consistency Models”. Operating Systems Review 27 (1): 18–26. doi:10.1145/160551.160553.
- Sarita V. Adve; Kourosh Gharachorloo (December 1996). “Shared Memory Consistency Models: A Tutorial”. IEEE Computer 29 (12): 66–76. doi:10.1109/2.546611 2008年5月28日閲覧。.
- Steinke, Robert C.; Gary J. Nutt (2004). “A unified theory of shared memory consistency”. Journal of the ACM 51 (5): 800–849. arXiv:cs.DC/0208027. doi:10.1145/1017460.1017464.
関連項目
[編集]外部リンク
[編集]- IETF slides
- Memory Ordering in Modern Microprocessors, Part I and Part II, by Paul E. McKenney (2005). Linux Journal
