今日は、さまざまなプログラム、特に分散システムでの同時および順次実行のトピックに再び触れたいと思います。 9月にこのテーマに関する記事「 Synchronicity is myth 」を公開しましたが、現在、より深刻な研究の翻訳版を公開しています。
コンピューターサイエンスには、キャッシュ無効化エラーの名前が間違っていることを認めるという現実的な問題が1つだけあります。 これらは、時間の使用に関連するユニットエラーです。-不明な著者
時間は奇妙なことです。
私たちは本当にそれが完全に合理化されたと信じたいので、今回はとても奇妙です。 15.00のイベントは、16,00のイベントの前に（私たちが言うように）発生するようです-例外、議論、または妥協なし。
ただし、コンピューターサイエンスは、この要件に厳密にではなくアプローチする必要がある場合、多くの例を知っています。 プロセッサ、コンパイラ、ネットワークノードのレベルで現れます。 スタックのさまざまなレベルで、何度も何度も計算を行いますが、2つのイベントに直面している状況にあり、それらが発生した順序はわかりません。 時間は明らかに合計ではありません。 彼女は断片化されています。
なんで？ 私たちが存在する抽象化のレベルはこの質問に対する答えを提供しないため、事実は私たちがこれを知らないということです。 それが偶然であるかどうかにかかわらず、私たちの計算抽象化は手順に関する保証を与えません。 多くの場合、イベントを並べ替える自由により、より生産的で手頃な価格のシステムを作成できます。
プロセッサには、 メモリ順序モデルがあります。 これは、アセンブリの段階でプロセッサが保証を与えたくない保証を反映しています。たとえば、どの命令が以前に実行され、どの命令が後で実行されるかなどです。 プロセッサは、命令の伝達方法を正確に決定し、それらを順不同で実行します。つまり、私が思っていたよりも効率的にチップを使用します。
言語には、 メモリ一致モデル （略して「メモリモデル」）があります。 これは、アセンブリを生成するとき、たとえば複数のスレッドに命令を分散するときなど、言語が提供しない保証を反映しています。 そのような並べ替えは、メモリのハードウェアモデルに固有の定義によるものであり、そのような「弱い」時間の概念がコンパイラで提供される理由の大部分を説明しています。 非ブロッキングコードを記述するときにプログラミングする言語で実装された、このようなメモリモデルのフレームワーク内です。
言語レベルで実装されたメモリモデルの有名な例は、C ++ 11標準の強いメモリモデルと弱いメモリモデルです。 デフォルトでは、C ++は同期を伴うアトミック操作を提供しますが、パフォーマンスを改善するためにメモリアクセスモデルを弱めることもできます。 この方法で提供される動作は、現在使用されているメインプロセッサアーキテクチャ（x86、POWER、およびARM）を抽象化することを目的としています。
最後に、分散システムには独自の一貫性モデルがあります。 これは、システムがグローバルコンピューターネットワークのクライアントとレプリカでのイベントの順序に関してユーザーに提供しない保証を反映しています。 通信遅延または同期の欠如に直接関連する再配置は、主に、分散システムで前述の弱い時間モデルなしではできない理由を説明します。 分散アプリケーションを作成するときにプログラムするのは、この一貫性のモデルです。
実際には、分散システムをプログラミングするときに使用できる整合性モデルの巨大な動物園があります。 そのようなすべての状況で、これらのモデルは、そのシステムの外部から観察されるシステムの（望ましい）動作を記述します。 私-特定のクライアントまたは特定のストリーム-値を書き込み、すぐにそれを読むと、私のものよりも古いレコードが確実に表示されることが保証されますか？ 時間が断片化されていない場合、システムの操作がどの順序で行われているのかを常に明確に考えていれば、当然、この質問に対する答えは肯定的です。 このような質問をするのはまったく奇妙です。
しかし、時間は断片的です-したがって、そのような質問を提起する必要があります。
一貫性モデル-つまり、メモリモデル
そのような断片化された秩序について話すことはしばしば困難であり、常に不快です。 スタックのすべてのレベルで、ACIDトランザクションまたはアトミック操作/ロックのいずれであっても、時間は常に絶対的に絶対であるという事実から進めたいと思います。 保証が厳しくなるほど、自然に簡単にプログラミングできます！
しかし、私たちは皆、スピードを求めて努力しています。 アクセシビリティのために厳密な一貫性を犠牲にする必要がある分散システムであろうと、同期コストを回避するために弱いメモリモデルを使用するノンブロッキングプログラミングであろうと、通常、あらゆるレベルのスタックで作業するプログラマーがこれらの複雑な議論に入ることをお勧めします。
共有メモリモデルの一貫性と分散メモリモデルの一貫性はどちらも抽象的です。 それらは、システムを操作するプログラマー、このシステムのインターフェースを記述しています。 当然のことながら、システム内のイベントの順序付けの一般的なプロパティが機能しなくなったため、弱いメモリモデルに対応する動作の種類を理解することができます。 これらの2つの記憶モデルは似ているように見えるかもしれませんが、両方のコミュニティはそれらを議論するために独自の談話を開発しました。 それらで使用される値は異なりますが、重複します。
これがどれほど混乱するかをすでに想像しています。 どうする？
エンティティとしての時間の説明。2〜8種類の半順序を意味します。
2014年の本では、 Sebastian Burkhardtが一貫性モデルの多くのオプションを網羅的に説明しようとしています。 この特性とともに、他の数学的構造とともに、イベントの論理的な順序の2つのバリアントが使用されます。「可視性」と「調停」は、Burkhardt等の他の作品でも前述しました。たとえば、ポインティングとチェックに関する記事を参照してください複製されたデータ型（2014）。
「可視性」は、潜在的な条件付けに固有の部分的な順序です。 これにより、どのイベント（他のレプリカにある可能性がある）がどの他のイベントから見えるかを追跡できます。 非周期性以外の可視性の要件はありません。 オブジェクト内のイベントは別のオブジェクト内のイベントから見えるようにすることができ、イベントの読み取りまたは書き込みの操作は他のイベントの可視性に影響しません。
「Ar意性」とは、選択した状況が発生する分散システムがどのイベントを早期に発生させ、どのイベントを後で発生させるかを追跡できる一般的な手順です。
分散一貫性モデルはメモリモデルに似ているため、メモリモデルを議論するときに、このような可視性とランダム性の現象も役立つことがわかります。 特に、 2014年の記事の付録では、 BurkhardtがC ++ 11の弱いメモリモデルがオブジェクトごとの一貫性に「どれだけ近い」かを示していますが、興味深い逸脱がいくつかあります。 これについては、ポストの残りで説明します。
まず、「読み取り」と「変更の順序」を考慮して、可視性とランダム性を指定しましょう。 「読み取り」の場合、2つのオブジェクト間の可視性は、読み取りと書き込みの両方が同じオブジェクトに接触する状況でのみ考慮され、読み取り時には1つのレコード（または複数）のみが表示されます。
これは、異なるスレッドが異なる原因と結果の瞬間にアクセスする場合でも、特定のオブジェクトの共有メモリを持つプロセッサが特定のオブジェクトの1つのメモリセルに情報を記録できる状況に対応します（一方で、分散システムでは、オブジェクトは多くの個別のレプリカに直接書き込むことができます）。
「変更順序」は、意性を具体化する同じ段階に対応し、客観的であり、記録のみを許可します。 繰り返しますが、この特殊化は、弱いメモリ仕様では、1つのオブジェクトのレベルでのみカテゴリカル保証が与えられるという事実に基づいています。
次に、Burkhardt et al。によって定式化された一貫性の公理について説明し、それらが弱メモリモデルにどのように適用されるかを見てみましょう。 注：「軸」という言葉にもかかわらず、これらは単なるプロパティであり、さまざまなメモリモデルで提供される場合と提供されない場合があります。 Burkhardtの記事は、オブジェクト間の因果関係を決定するプロパティに焦点を当てています。
最終的にコヒーレンス
特定のイベントに対して、それを表示しないイベントが無制限に多数存在することはできません。 つまり、イベントは最終的にシステムに表示されます。
弱いメモリモデルを備えたシステムでこのような条件を論理的に構築することは、やや難しくなります。特定のレコードについて、このレコードまたは以前のレコードを（修正順序で）読み取らない無限の数の読み取り操作は存在できないと主張する必要があります。
C ++ 11仕様では、この公理への準拠は保証されていませんが、実際には反例を見つけることは困難です。
エーテルの一貫性
フロー/クライアント操作のレベルで「潜在的な条件」を追跡するとき、可視性/可読性に関しては、戻り時間がないことを理解する必要があります。 そのため、読み取りを意味するフローを順序付けるときの閉包は非周期的である必要があります。 原則として、このプロパティが分散システムで観察されることは間違いありませんが、システムで弱いメモリモデルが使用されている場合、一部の投機バージョンでユーザーの可視性を許可しないのはこのプロパティです。
Burkhardtらは、この公理はC ++ 11仕様では「確認されていない」ことを指摘し、 「サイクルの満足」が実際に観察できるかどうかは「検証しない」ことを明確にしています。
条件性の公理
弱い記憶モデルの下で条件性の現象がどのように関係するかを正確に指定するために、どのイベントが他のどのイベントの結果に影響するかを正確に決定する必要があります。 最初に、標準的な因果関係の公理であるセッション保証を検討してください。 これらは、異なるストリームで発生する読み取りおよび書き込み操作のコヒーレンスプロパティを反映する4つの相互に関連する品質であり、さらに、各オブジェクトのレベルで指定する必要があります（ Burkhardt et al 。、 図23を参照）。
- RYW（レコードの読み取り）：書き込み操作に続く読み取り操作は、同じセル、同じストリーム/レプリカ/セッション内で行われます。レコードよりも関連性の低いデータを読み取る必要があります。 分散システムのこのプロパティのバリアントは、可視性の観点からのみ指定されますが、弱いメモリモデルのバリアントは、読み取り順序と変更順序の両方に基づいている必要があります。
- MR（モノリシック測定値）：後続の測定値（同じストリーム内、同じセル内）でも、将来関連性の低いデータが表示されるはずです。
- WFR（最初の読み取り、次に書き込み）：書き込みが同じセル内でストリーム内の読み取りに続く場合、変更の順序で読み取り操作よりも遅くなります。
- MW（モノリシックレコード）：後のレコード（ストリーム内、同じセル内）は、変更順で後になるはずです。
WFRとMWの元のバージョンには、ランダム性と可視性の2つのバージョンがあります。 ただし、これは整数用のレジスタよりも複雑なデータセルで作業する場合にのみ重要です。
これらの特性は、私たちの常識と一致する条件付けの概念を反映しています。 しかし、彼らは最も興味深いものを見逃しています。 特に、弱いメモリモデルで分析する場合、そのような条件付き現象は、フロー/レプリカ/セッション、およびエントリが作成される特定のセル/オブジェクトによって制限されます。 この場合、「条件ごとのオブジェクトの可視性」と「条件ごとのオブジェクトの意性」について説明します。図も参照してください。 23.これらの現象は、異なるストリームが異なるセルに情報を書き込むときのシステムの動作を完全に制限するものではありません。
次に、オブジェクト間コンディショニングの公理は、さまざまなオブジェクト/メモリセルのレベルでの因果関係の効果を説明します。
- COCV（Cross-Object Conditional Visibility）：RYWと同じケースですが、最終読み取りをすべて同じスレッド/レプリカ/セッションで実行する必要があるという条件はありません。 このオブジェクトのレコードより客観的に遅いオブジェクトからの読み取り値は、記録中に入力されたデータよりも関連性の低いデータを取得する必要があります。
C ++ 11仕様には、これらのプロパティが反映されています。 注：録画の可視性の制限と変更順序の意性がこれらの定義にあまり反映しないように定義されています。
ただし、これは後者のプロパティには適用されません。
- COCA（Cross-Object Conditional Arbitrary）：モノリシックレコードに似ていますが、COCVに似た異なるストリームに適用されます-異なるストリームに対してRYWです。 ただし、変更順序は1つのオブジェクトのレコードにのみ影響するため、弱いメモリモデルの定式化により、システムは異なるオブジェクトでの記録イベントの一貫性のない分布を持つことができ、レコードは読み取り値またはストリーム内の順序に対応しない場合があります。
特に、弱いメモリモデルのCOCAは、はるかに弱いプロパティです。 弱いメモリモデルでは、次のコードが
{x ≡ 0, y ≡ 0}
返す場合があるのはそのためです。
Thread A: y := 0; x := 1; return x
Thread B: x := 0; y := 1; return y
各ストリーム内の順序は、オブジェクトごとの順序および変更の順序と一致しない場合があります。 注：RYWでは、変更順序に
x := 0 → x := 1
がなく、
y
も同じです。 したがって、変更順序には
x := 1 → x := 0
および
y := 1 → y := 0
を含める必要があります。 したがって、修正順序は明らかにフローの順序でサイクルを形成します。
このようなループは、弱いメモリモデルのCOCAで許可されます。 ストリーム/読み取りの順序が変更の順序に反するということではなく、各ストリームが一貫した記録履歴を見るということです。 これらのストーリーは、他のフローのストーリーと一貫性がありますが、それは、その適用範囲を客観的に制限する場合のみです。
これはどういう意味ですか？
時間は断片化されています。
時間が非常に規則正しく流れるように思えますが、分散システムと弱いメモリモデルを調べると、そうではないことが明らかになります。 これらの状況の両方で、合計時間がどれだけであるかに応じて、標準的な過剰近似がパフォーマンスを制限する理由です。
次に、時間が本当に断片化されていることを認識すると、このような部分性の多様性の間に多くの小さいながらも重要な違いが見つかります。 一見非常に類似しているように見える上記の2つのフィールドでさえ、多くの微妙なニュアンスで、相互に影響していると考えられるイベントのタイプを区別することができます。
あるフィールドのプロパティを別のフィールドの言語で表現できるようになった後、さまざまなプロパティの技術的な詳細をより詳細に理解する必要があります。
時間は断片化されています。 おそらく、それに慣れる必要があるだけです。