C ++のマルチスレッド連想コンテナ。 Yandexレポート

シニア開発者のセルゲイ・ムリョーヨフのレポートから、WG21の一部として開発されている標準ライブラリのマルチスレッド連想コンテナについて学ぶことができます。 セルゲイは、この問題に対する一般的なソリューションの長所と短所、および開発者が選択した方法について話しました。





-おそらくタイトルから、今日のレポートは、ワーキンググループ21のフレームワーク内で、コンテナをstd :: unordered_mapに似たものにしたものの、マルチスレッド環境向けであると推測しているでしょう。



多くのプログラミング言語（Java、C＃、Python）では、これはすでに存在しており、非常に広く使用されています。 しかし、最愛の最速で最も生産的なC ++では、これは起こりませんでした。 しかし、私たちは相談し、そのようなことをすることにしました。







標準に何かを追加する前に、人々がそれをどのように使用するかを考える必要があります。 次に、より適切なインターフェースを作成します。これは、委員会によって採用される可能性が最も高く、できれば修正なしで行ってください。 そして、最終的には、あることを行ったものは存在しませんが、別のことを行いました。



最も有名で広く使用されているオプションは、大規模で重いコンピューティングをキャッシュすることです。 よく知られているサービスMemcachedがあります。これは、Webサーバーの応答をメモリに単純にキャッシュします。 競合する連想コンテナがある場合、アプリケーションの側でほぼ同じことを実行できることは明らかです。 どちらのアプローチにも長所と短所があります。 ただし、このようなコンテナがない場合は、独自の自転車を作成するか、何らかのMemcachedを使用する必要があります。



別の一般的なユースケースは、イベントの重複排除です。 この部屋の多くはあらゆる種類の分散システムを記述し、Apache KafkaやAmazon Kinesisなどのコンポーネント間の通信には分散キューがよく使用されることを知っていると思います。 これらは、1つのメッセージを1人の消費者に数回送信できるという特徴によって区別されます。 これは、少なくとも1回の配信と呼ばれ、少なくとも1回の配信の保証を意味します。それ以上は可能ですが、以下は不可能です。



実生活の観点からこれを考慮してください。 メッセージングが行われるチャットルームやソーシャルネットワークのバックエンドがあると想像してください。 これにより、誰かがメッセージを作成し、後で誰かが携帯電話でプッシュ通知を数回受信したという事実につながる可能性があります。 ユーザーがこれを見ると、それについて満足しないことは明らかです。 このようなすばらしいマルチスレッドコンテナを使用すると、この問題を解決できると主張されています。



次にあまり使用されないケースは、サーバー側の何か、ユーザーのメタデータを保存するだけの場合です。 たとえば、次にユーザーにユーザー名とパスワードを要求するタイミングを理解するために、ユーザーが最後に認証された時間を節約できます。



このスライドの最後のオプションは統計です。 実際のアプリケーションから、Facebookの仮想マシンでの使用例を挙げることができます。 彼らは、PHPを最適化するために仮想マシン全体を作成し、仮想マシンで、すべての組み込み関数のマルチスレッドハッシュテーブルに呼び出された引数を書き込もうとします。 そして、キャッシュに結果がある場合は、すぐにそれを提供し、何もカウントしないようにします。

^{_{スライドからのリンク}}

標準に大きく複雑なものを追加するのは簡単ではなく、高速でもありません。 原則として、大きなものが追加された場合、技術仕様を通過します。 現在、標準は、標準ライブラリでのマルチスレッドのサポートを拡張するために大きく動いています。 具体的には、マルチスレッドキューに関する提案P0260R3が現在進行中です。 この提案は、私たちに非常によく似たデータ構造に関するものであり、設計上の決定は多くの点で非常に似ています。



実際のところ、設計の基本概念の1つは、インターフェースが標準std ::キューとは異なるということです。 ポイントは何ですか？ 標準キューを見て、そこから要素を抽出するには、2つの操作を行う必要があります。 カウントするにはフロント操作を行い、削除するにはポップ操作を行う必要があります。 マルチスレッド条件下で作業している場合、これら2つの呼び出し間のキューで何らかの操作が行われる可能性があり、1つの要素を考慮して別の要素を削除することがあります。 したがって、これらの2つの呼び出しはそこで1つに置き換えられ、try pushおよびtry popのカテゴリからさらにいくつかの呼び出しが追加されました。 しかし、一般的な考え方は、マルチスレッドコンテナーは通常のインターフェイスと同じではないということです。



マルチスレッドキューには、いくつかの異なるタスクを解決するさまざまな実装もあります。 最も一般的なタスクはプロデューサーとコンシューマーのタスクです。いくつかのタスクを生成するスレッドがあり、キューからタスクを取得して処理するスレッドがいくつかあります。



2番目のケースは、何らかの種類の同期キューが必要な場合です。 メーカーと消費者の場合、最上部と最下部に限定されたラインを取得します。 比較的言えば、空のキューから抽出しようとすると、待機状態になります。 そして、キューに収まらないサイズを追加しようとすると、おおよそ同じことが起こります。



また、この提案では、内部にある実装がブロックされているか、ロックフリーであるかを区別できるように、個別に作成されたインターフェイスがあることを説明しています。 ここで提案のどこにでもロックフリーで書かれているという事実は、実際には、無料で待機として本に書かれています。 これは、アルゴリズムが一定数の操作に対して機能することを意味します。 そこでロックを解除することは少し異なることを意味しますが、それはポイントではありません。







ハッシュテーブルの実装がブロックされた場合にどのように見えるかを示す典型的な図を見てみましょう。 いくつかのセグメントに分割されています。 原則として、各セグメントには、Mutex、Spinlock、またはさらにトリッキーなものなど、何らかの種類のロックが含まれています。 また、MutexまたはSpinlockに加えて、このビジネスで保護されている通常のハッシュテーブルも含まれています。



この図では、リストに作成されたハッシュテーブルがあります。 実際、リファレンス実装では、パフォーマンス上の理由から、オープンアドレス指定のハッシュテーブルを作成しました。 パフォーマンスに関する考慮事項は、基本的には、std :: vectorがstd :: listよりも高速である理由と同じです。これは、ベクターは相対的に言えば、メモリに順次格納されるためです。 それに沿って進むと、シーケンシャルアクセスが行われ、キャッシュされます。 何らかの種類のシートを使用すると、メモリの異なるセクション間であらゆる種類のジャンプが行われます。 そして、原則として、全体は生産性を失うという事実で終わります。



最初に、このハッシュテーブルで何かを見つけたい場合、キーからハッシュコードを取得します。 あなたはそれをモジュロにして他のことをして、セグメント番号を取得することができます。そして、通常のハッシュテーブルのように、私たちが探しているセグメントで、もちろん、同時にロックを取得します。

^{_{スライドからのリンク}}

私たちのデザインの主なアイデア。 もちろん、std :: unordered_mapに一致しないインターフェイスも作成しました。 理由はこれです。 たとえば、通常のstd :: unordered_mapには、イテレーターのような素晴らしいものがあります。 まず、すべての実装がそれらを正常にサポートできるわけではありません。 そして、原則として、サポートできるものは、ガベージコレクションまたはその背後のメモリをクリーンアップする何らかのスマートポインタのいずれかを必要とする、ある種のロックフリー実装です。



これに加えて、私たちが捨てた他のタイプの操作がいくつかあります。 実際、反復子は、多くの場所にあります。 たとえば、それらはJavaにあります。 しかし、原則として、奇妙なことに、それらはそこで同期しません。 そして、異なるスレッドからそれらを使って何かをしようとすると、それらは簡単に無効な状態になる可能性があり、Javaで例外を取得することができ、これをプラスに書くと、おそらく未定義の動作になり、さらに悪いことになります。 ところで、未定義の振る舞いについては、私の意見では、GitHubのオープンソースに投稿されているFacebookの仲間たちがそれをやったのです。 Javaでインターフェイスをコピーして、このような素晴らしいイテレータを取得しました。



また、メモリに関する苦情もありません。つまり、コンテナに何かを追加し、メモリを取得した場合、すべてを削除しても、それを返却しません。 この決定のもう1つの前提条件は、内部にオープンアドレス指定のハッシュテーブルがあることです。 ベクトルのようにメモリを返さない線形データ構造で動作します。



次の概念上の瞬間は、どのような状況でも、外部オブジェクトへの内部オブジェクトへのリンクまたはポインターを決して与えないということです。 これは、ガベージコレクションの必要性を防ぐためだけに行われ、スマートポインターを強制するためではありません。 十分な大きさのオブジェクトをいくつか格納すると、値によってそれらを内部に格納することは利益を生まないことは明らかです。 ただし、この場合、選択したスマートポインターにいつでもラップできます。 また、たとえば、値に対して何らかの同期を行いたい場合は、boost :: synchronized_valueでそれらをラップできます。



しばらく前に、このオブジェクトへのアクティブなリンクの数を返すメソッドからshared_ptrクラスが削除されたという事実を見ました。 そして、いくつかの関数、つまり、size、count、empty、buckets_countも捨てる必要があるという結論に達しました。なぜなら、関数からこの値を返すとすぐに、誰かができるので、すぐに無効になるからです。同じ瞬間を変更します。



以前の会議の1つで、通常のstd :: unordered_mapのようなシングルスレッドモードでコンテナにアクセスできるように、一種のモードを追加するように依頼されました。 このようなセマンティクスにより、マルチスレッドモードで作業する場所とそうでない場所を明確に区別できます。 そして、人々がマルチスレッドのコンテナを使用するときの不快な状況を避けるために、すべてがうまくいくことを期待し、イテレータを使用すると、突然すべてが悪いことがわかります。

^{_{スライドからのリンク}}

ハワイでのこの会議では、私たちに対して全体の提案が書かれました。 :)マルチスレッドの連想コンテナを作成する方法はたくさんあるので、そのようなものは標準には適さないと言われました。



それぞれに長所と短所があり、最終的に成功するものをどのように使用するかは明確ではありません。 原則として、何らかの極端なパフォーマンスが必要な場合に使用されます。 そして、私たちのボックス化されたソリューションは適切ではないようです。特定のケースごとに最適化する必要があります。



この提案の2番目のポイントは、Facebookがその標準ライブラリからGitHubに投稿したという事実と互換性がないということです。



実際、そこには特に問題はありませんでした。 「読んだことがないが非難する」というカテゴリーからの質問があっただけです。 彼らはただ見た-インターフェースが異なる、つまり互換性がないことを意味します。



提案の考え方は、有効にする機能と無効にする機能を備えたビットマスクを渡すことができる追加のテンプレートパラメータを作成する必要がある場合、いわゆるポリシーベースの設計の助けを借りて同様のタスクを解決する必要があるということでもありました。 実際、これは少しワイルドに聞こえ、約2 ^ nの実装が得られるという事実につながります。ここで、nはさまざまな機能の数です。







コードでは、このように見えます。 何らかの種類のパラメーターと、そこに渡すことができるいくつかの定義済み定数があります。 奇妙なことに、この提案は拒否されました。







実際、委員会は、マルチスレッドキューがSG1を通過したときにそのようなことが起こるべきであるという立場をすでに取っているからです。 この問題に対する投票すらありませんでした。 しかし、投票には2つの質問が寄せられました。



最初の。 多くの人々は、ロックを使用せずに読み取りをサポートするために、リファレンス実装の側に私たちを望んでいました。 したがって、完全に非ブロッキングの読み取り値が得られます。 原則として、最も一般的なユーザーケースはキャッシュです。 そして、すぐに読むことは非常に有益です。



第二の瞬間。 誰もがポリシーベースの設計について話した前の友人から多くを聞いた。 誰もがアイデアを持っていました-しかし、何、私のアイデアについても話させてください！ そして、誰もが政策に基づいた設計に投票しました。 言わなければならないが、この話全体はかなり前から続いており、Intelの同僚であるArch RobinsonとAnton Malakhovがこれを前にやっていた。 そして、彼らはすでにこのテーマに関していくつかの提案をしていました。 彼らは、 SeepOrderedListアルゴリズムに基づいたロックフリー実装を追加することを提案しました。 また、メモリの不満があるポリシーベースの設計もありました。



そして、この提案は図書館進化ワーキンググループを好まなかった。 これは、標準の単語数を無制限に増やすだけの理由で終わりました。 適切にプレビューして、コードに単純に実装することはまったく不可能です。



アイデア自体についてはコメントがありません。 ほとんどの場合、リファレンス実装に関するコメントがあります。 そしてもちろん、それをより明確にするために導入できるアイデアがいくつかあります。 しかし、本質的には、次回はほぼ同じ提案を行います。 モジュールと同じように、同じ提案で5つの呼び出しが行われないことを心から願っています。 私たちは心から自分を信じており、次の呼び出しに進むことを許可されますが、それでも図書館進化ワーキンググループは私たちの意見を主張し、ポリシーベースの設計を推進させません。 相手が止まらないからです。 彼はそれが必要であることを皆に証明することにしました。 しかし、彼らが言うように、時間はわかります。 私はすべてを持っています、あなたの注意をありがとう。