スレッド間のメッセージング。 従来のブロッキングアルゴリズム

スクープを手に持ってサンドボックスから出たら、ノンブロッキングキューとスレッド間のデータ転送に関する投稿をしました 。 その投稿は、アルゴリズムとその実装に関するものではなく、パフォーマンスの測定に関するものでした。 それから、コメントで、従来のブロッキング送信アルゴリズムについて完全に合理的な質問をされました-それらがどれくらい遅いか、一般的に特定のタスクに最適なアルゴリズムを選択する方法。

もちろん、私は約束し、熱心に仕事に取り掛かりましたが、面白い結果さえ得ました...しかし、十分な熱意がなく、退屈でフラットでした。 その結果、私の完璧主義者は私の偽装されていない先延ばし者と協力し、二人とも私を打ち負かし、ドラフト草案で長い間断食し、私の良心でさえ忘れられた見出しを見て震えませんでした。

しかし、すべてが変化し、新しいテクノロジーが現れ、古いテクノロジーがアーカイブから消え、私は突然借金を返済して約束を守る時だと決めました。 罰として、私はすべてをゼロから書き直さなければなりませんでした。もし貪欲な人が二度支払うなら、怠け者は二度リメイクするので、そうする必要があります。

はい、KDPVについておaび申し上げます-もちろん、これは完全に異なる主題分野からのものですが、それにもかかわらず、フロー間の相互作用を示すのに完全に適合します。

それでヘルツェンは何を目覚めさせたのでしょうか

行動の知人を紹介します -C ++イディオムを継承し、強力に前進させ、同時に、ポインターを含む有効な低レベルツールを保持した、非常に概念的に美しい言語。 おそらくこのため、私の意見では、標準ライブラリDにはいくつかの二分法があります-ほとんどの機能は、ボックスから、シンプルで簡単な方法で、またはネイティブインターフェイスに近いインターフェイスを介して、システムのリソースと機能を完全に使用して呼び出すことができます。 C ++が連続スペクトルで範囲全体をカバーしている場合、Dではこの区分が通常はっきりと見えます。 時間間隔を測定する必要があります。素晴らしいモジュールstd.datetimeがありますが、測定量は100 nsです。これは絶対に十分ではありません。素晴らしいモジュールcore.timeがあります。 制限まで軽量な javascriptのような std.concurrency.spawnは、 あなたには向いていません -花束全体をcore.threadから使用できます。 そのため、ほぼすべての場所で、1つを除き、非常に重要な場所-ストリーム間のデータの分離。 はい、はい、特定のスレッドのすべてのローカル変数はスレッドローカルストレージに配置され、他のスレッドにアドレスを強制的に表示させることはできません。 そして、データ交換のために、組み込みのキューが提供されます。それは非常に便利であると認識される必要があります-多形性、重要なメッセージの並外れた送信と非常に素晴らしいインターフェースの可能性。 値または不変リンクのいずれかを使用して、データを自然に送信できます。 初めてそれについて読んだとき、私は単にdigりから飛び出しました-「あなたの不潔な手はどのように上がったのですか...」 、しかし、合格しないのは明確な設計エラーです。

それでも、問題は宙に浮いています-Dのラインはどれほど効果的ですか？ そうでない場合、言語の他のすべての有効性、つまり組み込みのボトルネックが無効になります。 それで目を覚まし、再び測定を始めました。

何を正確に測定しますか？

質問は実際には単純ではなく、前回書いたので、おそらく繰り返します。 Nメッセージを送信するときの通常の「単純な」アプローチでは、合計時間を測定し、Nで除算することはできません 。 見てみましょう、 キューのパフォーマンスを測定しますよね？ したがって、測定プロセス中にメッセージジェネレーターとメッセージレシーバーの速度が無限になり、データがキュー内にコピーされないという合理的な仮定で、 可能な限り多くのデータをキューに配置し、内部ポインターを1回送信するだけでデータが既に存在することが有益であることがわかります。 この場合、 メッセージあたりの平均時間は1 / N（実際には数ナノ秒の挿入/削除時間によって下から制限されます）になりますが、理論的には各メッセージの配信時間は一定であり、実際にはO（N）になります。

代わりに、私は反対のアプローチを使用します-各メッセージが送信され、時間が測定されてから、次のメッセージ（ レイテンシ ）が送信されます。 その結果、結果は、X軸-時間、Y軸-この時間中に配信されたパケットの数に沿って、ヒストグラムの形式で表示されます。 数値的に最も興味深いのは、平均配信時間の中央値と、何らかの（任意の）上限に適合しなかったメッセージの割合の2つのパラメーターです。

厳密に言えば、このアプローチも適切ではありませんが、パフォーマンス要件をはるかに正確に記述しています。 結論として少し自己批判を行います。完全な説明には、すべての可能なタイプのトラフィックの生成と統計的手法による分析が含まれると言うまで、QA理論の分野から本格的な科学的仕事を得るか、すぐに先延ばしの攻撃に追いつくでしょう。

別の点として、最後に長い議論があったので、メッセージジェネレーターはそれらをキューに任意にすばやく挿入できますが、受信者が平均してそれらを抽出して処理することを条件にすると、これに言及します。そうでない場合、測定全体は単に無意味です。 受信ストリームがデータストリームを処理できない場合、コードを高速化し、処理を並列化し、メッセージプロトコルを変更する必要がありますが、いずれにしても、キュー自体はそれとは無関係です。 これは単純なアイデアのように思えますが、最後のコメントはコメントで何度か繰り返さなければなりませんでした。 突然キューに大量のメッセージが存在する場合、速度の変動は非常に可能性があり、避けられないこともありますが、これは適切に設計されたアルゴリズムが平滑化する要因の1つにすぎませんが、これは最大受信速度が平均送信速度よりも大きい場合にのみ可能です。

で始まる

これは何？ これが実際の結果であり、私の作品はすべて1つの写真に収まりますが、ここで何が、なぜ描かれているのかを長い間説明します。

ピンク 標準ギアD

5マイクロ秒、それはたくさんですか、それとも少しですか？ ほとんどすべての場合、これは小さいです（つまり、非常に優れています）。 実際のプロジェクトの大部分では、これは十分な速度を上回っています。さらに、そのような伝送時間は、特別な鉄および/または非常に特別なソフトウェアの助けを借りてのみ得られます。 ここには、標準ライブラリのツールと、他の多くのおいしいパンがあり、すべての実用的なニーズに十分な速度で対応しています。 評価は素晴らしいです。 しかし、この実装には速度に関連しないいくつかの欠点があるため、それは素晴らしいことではありません。虐待の部分で説明します。

繰り返しになりますが、プログラミングの主な魔法は魔法がないことです。 あなたが内部に入ると（もちろん、私は覗かざるを得ませんでした）、コードは完全に普通であることがわかります-ミューテックスによって保護された単純に接続されたリスト。 ラインを実装するという意味で、彼は私たちに新しいことを何も言わないので、私は彼をここに連れてきません。 しかし、ノンブロッキングアルゴリズムを含む、より高速なアルゴリズムを本当に必要とする少数の人は、便利だが速度の遅いバンをすべて削除することで、独自のバージョンを簡単に書くことができます。 しかし、Dがどれほど簡潔で表現力豊かな言語であるかを示すためだけにコードを提供します。

青 激しくて偽装されていないC ++。

400ナノ秒！ ビンゴ！ 並んで、すべての非ブロッキングおよびその他のトリッキーなアルゴリズム！ それともまだないですか？

もちろん、これはひどい挑発です。実際、このバージョンでは、読み取りストリームがスリープ状態になることはなく、ループ内で着信メッセージのキューを継続的にチェックし続けます。 このオプションは、競合するプロセスが表示されるとすぐにCPUが実行する必要がないだけで機能します。特に、共有リソースについて同様に不注意な場合、すべてが予測不能に滑り始めます。 はい、このスレッドを処理するコアの1つを強制的に指定するオプションがありますが、アーキテクチャ上、これは非常に悪い決定です。後でこれに戻ります。 それが正当化される、または必要な場所さえありますが、あなたがそのような場所で働いているなら、おそらくあなたはすでにあなた自身すべてを知っているでしょう、この投稿はあなたにとって完全に不要です。

しかし、重要な情報を受け取りました-現代のシステムでは、トランザクションの速度はミューテックスまたはデータのコピーの速度によってまったく決定されず、主な要因は強制的または自発的な一時停止後のストリームのウェイクアップ時間です。 したがって、モラル-キューからのメッセージを処理するための専用のCPUを必要としないか、余裕がない場合は、高速で複雑だがソリューションを使用するのは不便である前によく考えてください。トランザクション中のアルゴリズム自体。 そして、はい、ここで私は意味します

それでは、理性の範囲内に留まることで何ができるでしょうか？

赤 合理的でバランスの取れたC ++。

usleep（）などが他の人の頭に浮かんだ場合、忘れないでください。応答時間を少なくとも40マイクロ秒に増やすことが保証されています。これは、最新のカーネルが保証できる最善の方法です。 Yield（）はわずかに優れていますが、わずかな負荷でも十分に機能しますが、CPU時間を誰とでも共有する傾向があります。 唯一の方法があり、それは明らかです-同期用のmutexはすでに使用されており、コードの変更は最小限になるため、 std :: condition_variableを使用します。 この実施形態では、待ち行列が空である場合、受信者は変数で眠りに落ち、パートナーが眠っている可能性があると疑う場合、メッセージ生成器は信号を送信する。 この場合、カーネルには最適化のすべての可能性があり、3マイクロ秒という結果が得られます。 基本的なコードは非常にシンプルであり、あらゆる場面に適応させることができますが、すごい、私たちは文字通りあらゆる種類のトリッキーな実装の真っon中にいると言うことができます。 もちろん、ここではDのような多態性はありませんでしたが、ほぼ2倍の速さで判明しました。 冗談ではありません、これはノンブロッキングアルゴリズムとの非常に本当の競争相手です。

緑色 スケーラビリティ、スケーラビリティ。

結果は非常にシンプルに見えますが、これは私が長い間探し求め、持ち歩いてきたアーキテクチャソリューションです。 人々はしばしば、キューなどを介して毎秒いくつのメッセージを送信できるかを尋ね、逆の状況がそれほど頻繁に発生しないことを忘れて-特定の数のスレッドをビジネスに持ち、あまり頻繁ではなく、時々メッセージを送信するようにしますしかし重要です。 そのようなストリームごとに別々のリスナーをハングアップさせたくないので、ほとんどの場合はスリープ状態のままになります。そのため、すべてのキューをポーリングし、到着時にメッセージを処理する共通の処理センターを1つ作成する必要があります。 しかし、今日は長いコードの夕べではなく、短い概念の断片の夕べなので、 boost :: asioを大きなボーナスとして使用することをお勧めします。このストリームはソケットとタイマーにも対応できます。 ここで、ところで、転送された関数で直接データをキャプチャするキューなしで簡単に実行できます。キューは、データのアグリゲーターおよびバッファーとして、また前の例とのセマンティックリンクとしても機能します。

そして、私たちは何を得ますか？ 1つのジェネレーターからのプロセスでは4.3マイクロ秒で、まったく悪くありません。 多くのスレッドが同時にメッセージを書き込むシステムでは結果が必然的に悪化することを念頭に置く必要がありますが、スケーラビリティは事実上無制限であり、コストがかかります。

繰り返しになりますが、このフラグメントの哲学的な意味を強調したいと思います。データだけでなく、データに加えて、クロススレッド仮想のようなデータの操作方法を知っているファンクターを別のストリームに送信しています。 これは非常に一般的な概念であるため、おそらく別のデザインパターンのタイトルを主張できます。

---

すべてのテストにコードが必要な場合、これで実験部分は終了します。 注意、これは既製のライブラリではないため、不注意にコピーすることはお勧めしませんが、コードを開発するための非常に有用なチュートリアルとして役立ちます。 追加や改善を歓迎します。

ケースではなく、非常に異なる推論。

メッセージキューが必要な理由 例Dが教えているように、これはマルチスレッドシステムを設計するための最もコーシャパターンであり、未来は未来とキューも意味します。 しかし、すべてのキューは同じですか？ オプションは何ですか？違いは何ですか？ これについてお話します。

まず、 データ ストリームとメッセージフローを区別する必要があります 。 データストリームでは、すべてが比較的単純であり、送信される各フラグメントはセマンティックロードを持たず、フラグメント間の境界は非常にarbitrary意的です。 コピーのコストは、キュー自体が消費するリソースに匹敵するか、それを上回ります。この場合のレシピは非常に単純です。可能な限り内部バッファーを増やすと、信じられないほどの速度が得られます。 たとえば、データクォンタム（大きなファイル）は、1つのメッセージと見なすことができるため、技術的には一度に送信できません。 まあ、それだけです。おそらくそれ以上言うことはありません。 しかし、メッセージフローでは、後続の各フラグメントが完全な情報の塊を運び、即時の反応を引き起こすはずです。今日それらについて話します。

接続性 、何が何に接続するかという観点からアーキテクチャを分析することも役立ちます。 最も単純なタイプの「パイプ」は、ライターとリーダーの2つのストリームを接続します。その主な目的は、入力ストリームと出力ストリームの分離を提供することです。理想的には、どちらも他の問題を知らないはずです。 キューの2番目のアトミックタイプは「ファンネル」で、任意の数のスレッドが書き込むことができますが、読み取るスレッドは1つだけです。 これはおそらく最も一般的なケースであり、最も単純な例はロガーです。 そして実際はそれだけです。1つのスレッドが複数のスレッドを読み書きする場合の反対のケースは、「パイプ」の束を使用して実装されるため、アトミックではありません。一般的な生活、特にマルチスレッドシステムの設計に対する態度を再考することを強くお勧めします。

入力ストリームと出力ストリームの分離に戻ると、これは必然的に理想的なキューが無次元である必要があるという結論につながります。つまり、必要に応じて無限に多くのメッセージが含まれます。 簡単な例：非常に重要で責任のあるストリームが短いメッセージをログに書き込み、その非常に重要な事項に戻りたいとしましょう。 ただし、固定サイズのバッファを備えたキューに基づいて作成したログは、誰かが「戦争と平和」を完全に投げただけです。 どうする ロガーなどの優先度の低いタスクで呼び出しスレッドをブロックし、エラーまたは例外を返すことは、アーキテクチャの観点からは非常に望ましくありません（呼び出し機能に責任を移し、すべての可能な結果を​​監視することを義務付け、呼び出しコードとエラーの確率を非常に複雑にしますが、代わりに何も得られない-何をすべきかはまだ明確ではない）。 そして、一般に、ここで私たちの目の前にあるのであれば、ノンブロッキングキューに関するこのすべての話のポイントは何でしたか？ そのため、標準Dキューはスレッド間通信の普遍的なソリューションではなく、さらに、オプションの1つにあるノンブロッキングブースト::ロックフリー::キューも固定バッファーを使用し、実際にはノンブロッキングアルゴリズムではありませんが、非ブロッキングキューではないことを既に述べた理由です。

幸いなことに、RAMは最も安価なリソースの1つであるため、 適応戦略はおそらく汎用のものの中で最も最適です-メモリは必要に応じてヒープから割り当てられ（ 2回実行しないように大きな断片で）、決して解放されないため、キューサイズはバーストに調整されますトラフィックと、通常の統計では、アロケーターへのアクセスは一般的ではなくなりました。 経験上、平均的な手持ちのサーバーでも、このアプローチは数時間のハンディキャップを簡単に与え、そのために何かを修正したり 、計画的な停止に到達したり、少なくとも別の仕事を見つけたりすることができます 。

最後に、トラフィックの統計的な性質があります。 データ転送とメッセージ転送の違いについてはすでに説明しましたが、メッセージには異なる時間分布もあります。 奇妙なことに、最も簡単なケースは、データができるだけ早く（ただし、キューから削除するよりも速くない）、同時に均等に到着する場合です。 同時に、スピンロックからシステムに組み込まれたツールまで、さまざまなアクセラレータが可能な限り効率的に機能します。 より複雑なのは、処理速度を超えることが保証されているメッセージフローで強力なスパイクが発生した場合です。 このモードでは、キューは着信メッセージを効率的に蓄積し、必要に応じてメモリを割り当て、大幅なスローダウンを許可しません。 ただし、最も難しいモードは可能です-メッセージが非常にまれに到着するが、すぐに応答する必要がある場合。 そのような場合、スワップに陥るなど、何でも起こり得ます。 間隔の正規分布でこのようなイベントがめったに発生せず、テストで拒否した割合の割合に該当する場合、この場合、効率は桁違いに低下する可能性があります。

在庫のレーキの不完全なリスト。

• 書き込みと読み取りのバランスを保ちます ：読み取りストリームが失敗した場合、アルゴリズムはあなたを救いません。 あなたがそれをスピードアップしたいものは何でもしますが、ラインを非難しないでください。
• 累積的なスローダウン ：実装によっては、キューの速度がその中のメッセージの数に依存する場合があります。その後、アクティビティのランダムなバーストによりキューが非常に遅くなり、次のバーストまでトラフィックジャムのように解放されません。 このような不安定性は、テスト中にモデル化するのはかなり困難です。
• 夜警症候群 ：OSの観点からは、メッセージが非常にまれに1時間に1回、または1日1回であることがありますが、それは常に永遠です。 ポストの監視員が座ってアラームを待機しているが、彼の生涯に一度も信号がなかった場合、彼は重要な瞬間に何をしますか？ そのような自然に眠りに落ちるのと戦うことは困難です。
• ディストリビューションのテールについて考えてみましょう。上記のテストでは、1000ごとに2〜3個のメッセージが長時間異常に処理されました。これは、すべての汎用オペレーティングシステムに共通の機能です。 突然この数を減らす必要がある場合は、一生懸命働く必要があります。
• 専用CPUに頼らないでください 。これは強力な加速要因ですが、スケーラブルではありません。 メモリとは異なり、CPUは高価なリソースです。 システムに100500のコアがある場合でも、100500 + 1人の開発者が1つのことを望んでいます
  個人的な使用のため。

  1年前にキューを高速化するためにコアを予約することを提案した同じPMは、正直な青い目で魂を調べ、「フロントエンドの人が私に来た、会社のロゴはメインページのメインページに再描画されます」と言います。 彼らはあなたにコアの1つを割り当てるように頼みます、あなたは理解しています-これは深刻であり、顧客が最近注意を払ったとしても誰でも見ることができます そして、あなたのサーバーはすでに動作しているようで、とにかく誰もそれを見ません。」 これが発生した場合、深呼吸をしてゆっくり10まで数えることをお勧めします。そうしないと、破壊と犠牲が避けられません。
• もっとたくさんあります ：しかし、私は正確に何を忘れました

---

楽観的なメモで終わるのが慣習です：マルチスレッドの場合、それは未来ではなく、現在です。 そして、強力で、柔軟で、普遍的なメッセージングメカニズムのために-未来ですが、まだ明確に書かれておらず、明らかに私たちを待っています。

すべて成功。