memory - 共有メモリとメッセージパッシングは、大きなデータ構造をどのように処理しますか?

Question

Go と Erlang の並行処理へのアプローチを調べていると、どちらもメッセージパッシングに依存していることに気付きました。

このアプローチでは、共有状態がないため、明らかに複雑なロックの必要性が軽減されます。

ただし、多くのクライアントがメモリ内の単一の大きなデータ構造 (サフィックス配列など) への並列読み取り専用アクセスを必要としている場合を考えてみましょう。

私の質問:

データは読み取り専用で、1 つの場所に存在するだけでよいため、ロックはほとんど不要になるため、共有状態を使用すると、メッセージパッシングよりも高速でメモリ使用量が少なくなりますか?
この問題は、メッセージパッシングコンテキストでどのようにアプローチされるでしょうか? データ構造にアクセスできる単一のプロセスがあり、クライアントはそこからデータを順番に要求するだけでよいでしょうか? または、可能であれば、チャンクを保持するいくつかのプロセスを作成するために、データをチャンクにしますか?
最新の CPU とメモリのアーキテクチャを考えると、2 つのソリューションに大きな違いはありますか? つまり、共有メモリを複数のコアで並列に読み取ることができますか? つまり、両方の実装がほぼ同じように動作するハードウェアのボトルネックがないということです。

score 31 · Accepted Answer

理解しておくべきことの 1 つは、Erlang の並行性モデルでは、メッセージ内のデータをプロセス間でコピーする必要があることを実際には指定していないことです。メッセージの送信が通信する唯一の方法であり、共有状態は存在しないと述べています。すべてのデータは基本的に不変であるため、実装はデータをコピーせずに参照を送信するだけで十分です。または、両方の方法を組み合わせて使用することもできます。いつものように、最善の解決策はなく、その方法を選択する際にはトレードオフが必要です。

BEAM は、参照を送信する大きなバイナリを除き、コピーを使用します。

score 28 · Accepted Answer

はい、この場合、共有状態の方が高速になる可能性があります。ただし、ロックを忘れることができる場合に限ります。これは、完全に読み取り専用である場合にのみ実行可能です。「ほとんど読み取り専用」の場合は、ロックが必要です (ロックのない構造を書くことができない限り、ロックよりもさらにトリッキーであることに注意してください)。優れたメッセージパッシングアーキテクチャとして高速です。
はい、「サーバープロセス」を記述して共有できます。非常に軽量なプロセスを使用すると、データにアクセスするための小さな API を作成するのと同じくらい重くなります。データを「所有」する (OOP の意味での) オブジェクトのように考えてください。データをチャンクに分割して並列処理を強化すること (DB サークルでは「シャーディング」と呼ばれます) は、大きなケース (またはデータが低速のストレージにある場合) に役立ちます。
NUMA が主流になりつつあるとしても、NUMA セルあたりのコア数はますます増えています。大きな違いは、メッセージは 2 つのコア間でのみ受け渡しできるのに対し、ロックはすべてのコアでキャッシュからフラッシュする必要があるため、セル間バスのレイテンシ (RAM アクセスよりもさらに遅い) に制限されることです。どちらかといえば、共有状態/ロックはますます実行不可能になっています。

要するに....メッセージパッシングとサーバープロセスに慣れてください。それは大流行です。

編集：この回答を再検討して、Goのドキュメントにあるフレーズについて追加したいと思います：

通信によってメモリを共有し、メモリを共有して通信しないでください。

アイデアは次のとおりです。スレッド間でメモリのブロックを共有している場合、同時アクセスを回避する一般的な方法は、ロックを使用して調停することです。Go スタイルは、参照とともにメッセージを渡すことです。スレッドは、メッセージを受信するときにのみメモリにアクセスします。それは、ある程度のプログラマーの規律に依存しています。しかし、簡単に校正できる非常にクリーンなコードになるため、比較的簡単にデバッグできます。

利点は、すべてのメッセージでデータの大きなブロックをコピーする必要がなく、一部のロック実装のようにキャッシュを効果的にフラッシュする必要がないことです。このスタイルがより高性能なデザインにつながるかどうかを判断するのは、まだ時期尚早です。(特に、現在の Go ランタイムはスレッドスケジューリングに関してややナイーブであるため)

score 15 · Accepted Answer

Erlang では、すべての値が不変です。そのため、プロセス間でメッセージを送信するときにメッセージをコピーする必要はありません。変更することはできません。

Go では、メッセージの受け渡しは慣例に従っています。チャネルを介して誰かにポインターを送信し、ポイントされたデータを変更することを妨げるものは何もありません。慣例のみであるため、メッセージをコピーする必要はありません。

score 13 · Accepted Answer

最新のプロセッサのほとんどは、MESI プロトコルのバリアントを使用しています。共有状態のため、異なるスレッド間での読み取り専用データの受け渡しは非常に安価です。ただし、変更された共有データは非常にコストがかかります。これは、このキャッシュラインを格納する他のすべてのキャッシュがそれを無効にする必要があるためです。

したがって、読み取り専用のデータがある場合は、メッセージでコピーする代わりにスレッド間で共有する方が非常に安価です。ほとんどが読み取り専用のデータがある場合、スレッド間で共有するとコストがかかる可能性があります。これは、アクセスを同期する必要があることと、書き込みによって共有データのキャッシュフレンドリーな動作が損なわれることが原因の 1 つです。

ここでは、不変のデータ構造が役立ちます。実際のデータ構造を変更する代わりに、古いデータのほとんどを共有する新しいデータ構造を作成するだけですが、変更が必要なものは変更されています。すべてのデータが不変であるため、1 つのバージョンを共有するのは安価ですが、それでも新しいバージョンに効率的に更新できます。

score 5 · Accepted Answer

大規模データ構造とは

大きい人は小さい人です。

先週、私は 2 人の人と話しました.1 人は組み込みデバイスを作っていて、彼は「ラージ」という言葉を使用していました.私は彼にその意味を尋ねました.彼は 256 キロバイト以上だと言いました.同じ週の後半にある人がメディア配布について話していました.彼は「大きい」という言葉の意味を彼に尋ねたところ、彼は少し考えて、「1 台のマシンには収まらない」と言い、20 ～ 100 TBytes と言った

Erlang の用語では、「大きい」は「RAM に収まらない」ことを意味します。つまり、4 GB の RAM データ構造では > 100 MB は大きいと見なされる可能性があります。500 MB のデータ構造をコピーすると問題になる可能性があります。小さなデータ構造 (たとえば 10 MB 未満) のコピーは、Erlang ではまったく問題になりません。

非常に大きなデータ構造 (つまり、1 台のマシンに収まらないもの) は、複数のマシンにコピーして「ストライピング」する必要があります。

だから私はあなたが次のものを持っていると思います：

小さなデータ構造は問題ありません - データが小さいため、処理時間が速く、コピーも高速です (小さいという理由だけで)。

大きなデータ構造は問題です。1 台のマシンに収まらないためです。そのため、コピーが不可欠です。

score 4 · Accepted Answer

メッセージパッシングは共有状態を使用できるため、あなたの質問は技術的に無意味であることに注意してください。したがって、共有状態を回避するためにディープコピーを使用したメッセージパッシングを意味していると想定します（Erlangが現在行っているように）。

データは読み取り専用で、1 つの場所に存在するだけでよいため、ロックはほとんど不要になるため、共有状態を使用すると、メッセージパッシングよりも高速でメモリ使用量が少なくなりますか?

共有状態を使用すると、はるかに高速になります。

この問題は、メッセージパッシングコンテキストでどのようにアプローチされるでしょうか? データ構造にアクセスできる単一のプロセスがあり、クライアントはそこからデータを順番に要求するだけでよいでしょうか? または、可能であれば、チャンクを保持するいくつかのプロセスを作成するために、データをチャンクにしますか?

どちらのアプローチも使用できます。

最新の CPU とメモリのアーキテクチャを考えると、2 つのソリューションに大きな違いはありますか? つまり、共有メモリを複数のコアで並列に読み取ることができますか? つまり、両方の実装がほぼ同じように動作するハードウェアのボトルネックがないということです。

コピーはキャッシュに適していないため、メインメモリである共有リソースの競合が悪化するため、マルチコアでのスケーラビリティが失われます。

最終的に、Erlang スタイルのメッセージパッシングは並行プログラミング用に設計されていますが、スループットパフォーマンスに関する質問は実際には並列プログラミングを対象としています。これらは 2 つのまったく異なる主題であり、実際にはそれらの間の重複はごくわずかです。具体的に言うと、並行プログラミングのコンテキストでは通常、レイテンシーはスループットと同じくらい重要であり、Erlang スタイルのメッセージパッシングは、望ましいレイテンシープロファイル (一貫して低いレイテンシー) を達成するための優れた方法です。共有メモリの問題は、リーダーとライター間の同期ではなく、待機時間の短いメモリ管理です。

score 3 · Accepted Answer

現時点での問題は、ロックとキャッシュラインの一貫性が、より単純なデータ構造 (たとえば、数百バイト) をコピーするのと同じくらい高くつく可能性があることです。

ほとんどの場合、ほとんどのロックを排除しようとする巧妙に作成された新しいマルチスレッドアルゴリズムは、常に高速であり、最新のロックフリーデータ構造でははるかに高速です。特に、Sun の Niagara チップレベルマルチスレッドのような適切に設計されたキャッシュシステムを使用している場合はなおさらです。

システム/問題がいくつかの単純なデータアクセスに簡単に分割できない場合は、問題があります。また、すべての問題がメッセージパッシングで解決できるわけではありません。これが、テラバイトの共有 RAM と同じ共有メモリ上で動作する最大 128 個の CPU を備えているため、Itanium ベースのスーパーコンピューターがまだ販売されている理由です。同じ CPU 能力を持つ主流の x86 クラスターよりも桁違いに高価ですが、データを分割する必要はありません。

これまで言及されていなかったもう 1 つの理由は、マルチスレッドを使用すると、プログラムの作成と保守がはるかに容易になるということです。メッセージの受け渡しとシェアードナッシングアプローチにより、保守性がさらに向上します。

例として、Erlang は物事を高速化するようには設計されていませんが、代わりに多数のスレッドを使用して複雑なデータとイベントフローを構造化しています。

これがデザインのポイントの1つだったと思います。Google の Web の世界では、クラウドで並行して実行できる限り、通常、パフォーマンスは気にしません。また、メッセージパッシングを使用すると、理想的には、ソースコードを変更せずにコンピュータを追加できます。

score 3 · Accepted Answer

ここで紹介していないソリューションの 1 つは、マスター/スレーブレプリケーションです。大規模なデータ構造がある場合は、コピーで更新を実行するすべてのスレーブに変更を複製できます。

これは、非常に人為的な設定 (リモートコンピューターのメモリから読み書きするブロックデバイスの mmap?) なしではメモリを共有する可能性さえない複数のマシンにスケーリングしたい場合に特に興味深いものです。

その変種は、複製されたデータ構造を適切に更新するように要求するトランザクションマネージャーを用意することです。これにより、更新要求が同時に 1 つだけ処理されるようになります。これは、「大きなデータ構造」と見なされる、mnesia テーブルデータのマスターマスターレプリケーションの mnesia モデルに近いものです。

score 1 · Accepted Answer

通常、メッセージパッシング言語 (erlang では不変変数があるため、これは特に簡単です) は、プロセス間での実際のデータコピーを最適化します (もちろん、ローカルプロセスのみ: ネットワーク分散パターンを賢く考えたいと思うでしょう)。たいした問題じゃない。

score 0 · Accepted Answer

The other concurrent paradigm is STM, software transactional memory. Clojure's ref's are getting a lot of attention. Tim Bray has a good series exploring erlang and clojure's concurrent mechanisms

http://www.tbray.org/ongoing/When/200x/2009/09/27/Concur-dot-next

http://www.tbray.org/ongoing/When/200x/2009/12/01/Clojure-Theses

memory - 共有メモリとメッセージパッシングは、大きなデータ構造をどのように処理しますか?

10 に答える 10

Related

Reference