Loading article…
分散コンピューティングは、相互に通信するコンポーネントが異なるネットワークコンピュータ上に存在するコンピュータシステムとして定義される分散システムを研究するコンピュータ科学の分野です。[ 1 ] [ 2 ]
分散システムのコンポーネントは、共通の目標を達成するために、互いにメッセージを渡すことで通信し、動作を調整します。分散システムの 3 つの課題は、コンポーネントの並行性を維持すること、グローバル クロックがないことを克服すること、およびコンポーネントの独立した障害を管理することです。[ 1 ] 1 つのシステムのコンポーネントが故障しても、システム全体が故障することはありません。[ 3 ]分散システムの例は、SOA ベースのシステムからマイクロサービス、大規模マルチプレイヤー オンライン ゲーム、ピアツーピア アプリケーションまで多岐にわたります。分散システムは、主に追加のハードウェア、サーバー、ゲートウェイ、ファイアウォール、新しいサブネット、プロキシなどの必要性が増加するため、モノリシック アーキテクチャよりもコストがかかります。[ 4 ]分散システムは、分散コンピューティングの誤謬に陥ることもあります。逆に、適切に設計された分散システムは、単一のマシンにデプロイされたモノリシック アプリケーションよりも、スケーラブルで、耐久性があり、変更可能で、より微調整されています。[ 5 ]マーク・ブルッカーによれば、「システムは、追加のワークロードの限界コストがほぼ一定である範囲でスケーラブルである」。サーバーレス技術はこの定義に当てはまるが、インフラストラクチャのコストだけでなく、総所有コストも考慮する必要がある。[ 6 ]
分散システム内で実行されるコンピュータプログラムは分散プログラムと呼ばれ、[ 7 ]分散プログラミングとはそのようなプログラムを作成するプロセスです。[ 8 ]メッセージパッシングメカニズムの実装には、純粋なHTTP、 RPCライクなコネクタ、メッセージキューなど、多くの種類があります。[ 9 ]
分散コンピューティングとは、計算問題を解決するために分散システムを使用することも指します。分散コンピューティングでは、問題は多数のタスクに分割され、それぞれのタスクは1台以上のコンピュータによって解決され、それらのコンピュータはメッセージパッシングを介して相互に通信します。[ 10 ] [ 11 ]
「分散システム」、「分散プログラミング」、「分散アルゴリズム」などの用語における「分散」という言葉は、元々は個々のコンピュータが物理的に地理的な領域内に分散しているコンピュータネットワークを指していました。[ 12 ]現在では、これらの用語ははるかに広い意味で使用されており、同じ物理コンピュータ上で実行され、メッセージパッシングによって相互にやり取りする自律的なプロセスを指す場合もあります。[ 11 ]
分散システムには単一の定義はないが、[ 13 ]一般的に2つの共通の特性が挙げられている。
分散システムは、大規模な計算問題を解決するなど、共通の目標を持つ場合があります。[ 16 ]この場合、ユーザーは自律的なプロセッサの集合を一つの単位として認識します。あるいは、各コンピュータに個別のニーズを持つユーザーがいて、分散システムの目的は共有リソースの使用を調整したり、ユーザーに通信サービスを提供したりすることです。[ 17 ]
分散システムのその他の典型的な特性は以下のとおりです。
分散コンピューティングで使用される一般的なアーキテクチャパターンを以下に示します。 [ 21 ]
分散システムでは、イベントは事実または状態の変化（例：OrderPlaced）を表し、通常は複数のコンシューマーに非同期的にブロードキャストされ、疎結合とスケーラビリティを促進します。イベントは一般的に即時の応答を期待しませんが、確認メカニズムは、イベントパターン自体に内在するものではなく、インフラストラクチャ レベルで実装されることがよくあります（例：Kafka コミット オフセット、SNS 配信ステータス）。[ 22 ] [ 23 ]
対照的に、メッセージはより広い役割を果たし、コマンド（例: ProcessPayment）、イベント（例: PaymentProcessed）、およびドキュメント（例: DataPayload）を含みます。イベントとメッセージの両方は、テクノロジースタックと実装に応じて、少なくとも1回、最大1回、正確に1回など、さまざまな配信保証をサポートできます。ただし、正確に1回の配信は、真のインフラストラクチャレベルの正確に1回セマンティクスではなく、冪等性メカニズムによって実現されることがよくあります。[ 22 ] [ 23 ]
イベントとメッセージの両方の配信パターンには、パブリッシュ/サブスクライブ（1対多）とポイントツーポイント（1対1）があります。リクエスト/リプライは技術的には可能ですが、純粋なイベント駆動システムよりもメッセージングパターンに関連付けられることが多いです。イベントは状態伝播と疎結合通知に優れており、メッセージはコマンド実行、ワークフローオーケストレーション、明示的な調整に適しています。[ 22 ] [ 23 ]
現代のアーキテクチャでは、分散状態変化通知にはイベントを、特定のタイミング、順序、配信要件に基づくターゲットコマンド実行と構造化ワークフローにはメッセージを、両方のアプローチを組み合わせるのが一般的です。[ 22 ] [ 23 ]
分散システムとは、共通の作業目標を共有するネットワーク接続されたコンピュータのグループです。「同時実行コンピューティング」、「並列コンピューティング」、「分散コンピューティング」という用語は重複する部分が多く、明確な区別はありません。[ 24 ]同じシステムが「並列」と「分散」の両方として特徴付けられる場合があり、典型的な分散システムのプロセッサは並列に同時実行されます。[ 25 ]並列コンピューティングは、分散コンピューティングの特に密結合な形態と見なされる場合があり、[ 26 ]分散コンピューティングは、並列コンピューティングの疎結合な形態と見なされる場合があります。[ 13 ]それにもかかわらず、次の基準を使用して、同時実行システムを「並列」または「分散」に大まかに分類することは可能です。
右の図は、分散システムと並列システムの違いを示しています。図(a)は、典型的な分散システムの概略図です。このシステムは、各ノードがコンピュータであり、ノード間を接続する各線が通信リンクであるネットワークトポロジーとして表されています。図(b)は、同じ分散システムの詳細を示しています。各コンピュータは独自のローカルメモリを持ち、利用可能な通信リンクを使用してノード間でメッセージを渡すことによってのみ情報を交換できます。図(c)は、各プロセッサが共有メモリに直接アクセスできる並列システムを示しています。
並列アルゴリズムと分散アルゴリズムという用語の従来の用法が、上記の並列システムと分散システムの定義と完全に一致しないため、状況はさらに複雑になります（詳細については後述を参照）。しかしながら、経験則として、共有メモリマルチプロセッサにおける高性能並列計算では並列アルゴリズムが使用され、大規模分散システムの協調では分散アルゴリズムが使用されます。[ 29 ]
メッセージパッシングを介して通信する並行プロセスの使用は、1960年代に研究されたオペレーティングシステムアーキテクチャにルーツがある。 [ 30 ]最初の広く普及した分散システムは、1970年代に発明されたイーサネットなどのローカルエリアネットワークであった。 [ 31 ]
インターネットの前身の一つであるARPANETは1960年代後半に導入され、ARPANET電子メールは1970年代初頭に発明されました。電子メールはARPANETの最も成功したアプリケーションとなり[ 32 ]、おそらく大規模分散アプリケーションの最も初期の例です。ARPANET（およびその後継であるグローバルインターネット）に加えて、その他の初期の世界的コンピュータネットワークには、 1980年代のUsenetとFidoNetがあり、どちらも分散ディスカッションシステムをサポートするために使用されました[ 33 ] 。
分散コンピューティングの研究は、1970年代後半から1980年代初頭にかけてコンピュータサイエンスの独立した分野となった。この分野で最初の会議である分散コンピューティングの原理に関するシンポジウム（PODC）は1982年に開催され、その対となる分散コンピューティングに関する国際シンポジウム（DISC）は、1985年にオタワでグラフ上の分散アルゴリズムに関する国際ワークショップとして初めて開催された。[ 34 ]
分散コンピューティングには、さまざまなハードウェアおよびソフトウェアアーキテクチャが使用されます。低レベルでは、回路基板上に印刷されたネットワークであろうと、疎結合されたデバイスとケーブルで構成されているネットワークであろうと、何らかのネットワークで複数のCPUを相互接続する必要があります。高レベルでは、これらのCPU上で実行されているプロセスを何らかの通信システムで相互接続する必要があります。[ 35 ]
これらのCPUがリソースを共有するかどうかによって、3種類のアーキテクチャが最初に区別される。
分散プログラミングは通常、クライアント/サーバー、3層、n層、ピアツーピアなどのいくつかの基本的なアーキテクチャ、または疎結合、密結合などのカテゴリに分類されます。[ 36 ]
分散コンピューティングアーキテクチャのもう1つの基本的な側面は、並行プロセス間での通信と作業の調整方法です。さまざまなメッセージパッシングプロトコルを介して、プロセスは、通常、メイン/サブの関係で、互いに直接通信することができます。あるいは、「データベース中心」アーキテクチャでは、共有データベースを利用することで、プロセス間の直接通信を一切行わずに分散コンピューティングを実行できます。[ 39 ]特にデータベース中心アーキテクチャは、ライブ環境リレーを可能にする概略アーキテクチャでリレーショナル処理分析を提供します。これにより、ネットワークデータベースのパラメータ内外で分散コンピューティング機能が可能になります。[ 40 ]
セルベースアーキテクチャは、計算リソースをセルと呼ばれる自己完結型のユニットに編成する分散コンピューティングのアプローチです。各セルは独立して動作し、スケーラビリティ、障害分離、可用性を維持しながら要求を処理します。[ 41 ] [ 42 ] [ 43 ]
セルは通常、複数のサービスまたはアプリケーション コンポーネントで構成され、自律的な単位として機能します。実装によっては、サービスセット全体を複数のセルに複製するものもあれば、ワークロードをセル間で分割するものもあります。複製モデルでは、別のセルで障害が発生した場合、リクエストを稼働中のセルに再ルーティングすることができます。この設計は、局所的な障害の影響を軽減することで、システムの回復力を高めることを目的としています。[ 44 ] [ 45 ] [ 46 ]
一部の実装では、セル内およびセル間でサーキットブレーカーが使用されています。セル内では、サーキットブレーカーを使用してサービス間の連鎖的な障害を防ぐことができます。一方、セル間サーキットブレーカーは、障害が発生したセルを隔離し、トラフィックを稼働中のセルにリダイレクトすることができます。[ 47 ] [ 48 ] [ 49 ]
セルベースアーキテクチャは、特にクラウドネイティブ環境や高可用性環境など、障害分離と冗長性が重要な設計上の考慮事項となる大規模分散システムで採用されています。その実装は、システム要件、インフラストラクチャの制約、運用目標によって異なります。[ 50 ] [ 51 ] [ 52 ]
分散システムや分散コンピューティングを利用する理由としては、以下のようなものが挙げられます。
分散システムと分散コンピューティングの応用例には、次のものがあります。[ 54 ]
リアクティブマニフェストによれば、リアクティブ分散システムは応答性、回復力、弾力性、メッセージ駆動型です。その結果、リアクティブシステムはより柔軟で、疎結合で、スケーラブルです。システムをリアクティブにするには、リアクティブ原則を実装することをお勧めします。リアクティブ原則は、クラウドネイティブアプリケーションとエッジネイティブアプリケーションをよりリアクティブにするのに役立つ一連の原則とパターンです。[ 56 ]
コンピュータを使って自動化したいタスクの多くは、質問と回答のやり取りを伴うものです。つまり、私たちが質問を投げかけ、コンピュータがそれに答えるというものです。理論計算機科学では、このようなタスクは計算問題と呼ばれます。厳密に言えば、計算問題は、インスタンスと、それぞれのインスタンスに対する解から構成されます。インスタンスとは、私たちが投げかけることができる質問であり、解とは、これらの質問に対する望ましい回答です。
理論計算機科学は、どの計算問題をコンピュータで解決できるか（計算可能性理論）と、その効率性（計算複雑性理論）を理解しようとします。従来、与えられたインスタンスに対して正しい解を生成するアルゴリズムを設計できれば、問題はコンピュータで解決できると言われてきました。このようなアルゴリズムは、汎用コンピュータ上で実行されるコンピュータプログラムとして実装できます。プログラムは、入力から問題インスタンスを読み込み、何らかの計算を実行し、出力として解を生成します。ランダムアクセスマシンやユニバーサルチューリングマシンなどの形式体系は、このようなアルゴリズムを実行する逐次汎用コンピュータの抽象モデルとして使用できます。[ 57 ] [ 58 ]
並行分散コンピューティングの分野では、複数のコンピュータの場合、あるいは相互作用するプロセスのネットワークを実行するコンピュータの場合において、同様の疑問が研究されています。すなわち、そのようなネットワークではどのような計算問題を、どの程度効率的に解決できるのか、という問題です。しかし、並行システムや分散システムにおいて「問題を解決する」とはどういう意味なのかは、必ずしも明らかではありません。例えば、アルゴリズム設計者の役割とは何でしょうか？また、逐次的な汎用コンピュータに相当する並行システムや分散システムにおける役割とは何でしょうか？
以下の議論は複数のコンピュータの場合に焦点を当てていますが、多くの問題点は単一のコンピュータ上で並行して実行されるプロセスにも共通しています。
一般的に用いられる視点は3つあります。
分散アルゴリズムの場合、計算問題は一般的にグラフに関連しています。多くの場合、コンピュータネットワークの構造を記述するグラフが問題のインスタンスとなります。これは次の例で示されています。 [ 63 ]
与えられたグラフGの彩色を求める計算上の問題を考えてみましょう。さまざまな分野では、次のようなアプローチが取られる可能性があります。
並列アルゴリズムの分野は分散アルゴリズムの分野とは異なる焦点を持っていますが、両分野の間には多くの相互作用があります。たとえば、グラフ彩色のためのコール・ヴィシュキンアルゴリズム[ 64 ]は元々並列アルゴリズムとして発表されましたが、同じ手法を分散アルゴリズムとして直接使用することもできます。
さらに、並列アルゴリズムは、並列システム（共有メモリを使用）または分散システム（メッセージパッシングを使用）のいずれでも実装できます。[ 65 ]並列アルゴリズムと分散アルゴリズムの従来の境界（適切なネットワークを選択するか、任意のネットワークで実行するか）は、並列システムと分散システム（共有メモリとメッセージパッシング）の境界と同じ場所にはありません。
並列アルゴリズムでは、時間と空間に加えて、コンピュータの数もリソースとなります。実際、実行時間とコンピュータの数の間にはトレードオフが存在することがよくあります。並列に実行されるコンピュータの数が多いほど、問題はより速く解決できます（スピードアップを参照）。多項式数のプロセッサを使用して決定問題を多対数時間で解決できる場合、その問題はクラスNCに属すると言われます。[ 66 ]クラス NC は、PRAM 形式またはブール回路を使用して同様に定義できます。PRAM マシンはブール回路を効率的にシミュレートでき、その逆も同様です。[ 67 ]
分散アルゴリズムの分析では、通常、計算ステップよりも通信操作に重点が置かれます。分散コンピューティングの最も単純なモデルは、すべてのノードが同期して動作する同期システムです。このモデルは一般にローカルモデルとして知られています。各通信ラウンドでは、すべてのノードが並列に (1) 隣接ノードから最新のメッセージを受信し、(2) 任意のローカル計算を実行し、(3) 隣接ノードに新しいメッセージを送信します。このようなシステムでは、中心的な複雑性尺度は、タスクを完了するために必要な同期通信ラウンドの数です。[ 68 ]
この複雑度尺度は、ネットワークの直径と密接に関係しています。Dをネットワークの直径とします。一方では、同期分散システムでは、計算可能な問題であれば何でも、約 2 D回の通信ラウンドで簡単に解決できます。つまり、すべての情報を 1 つの場所に集め ( Dラウンド)、問題を解決し、各ノードに解決策を通知する ( Dラウンド) だけです。
一方、アルゴリズムの実行時間がD 回の通信ラウンドよりはるかに短い場合、ネットワーク内のノードは、ネットワークの遠隔部分に関する情報を取得する可能性なしに、出力を生成する必要があります。言い換えれば、ノードは、ローカルの D 近傍で利用可能な情報に基づいて、グローバルに一貫した決定を下す必要があります。実行時間がDラウンドよりはるかに短い分散アルゴリズムは多数知られており、そのようなアルゴリズムで解決できる問題を理解することは、この分野の中心的な研究課題の 1 つです。[ 69 ]通常、ネットワークサイズに対して多対数時間で問題を解決するアルゴリズムは、このモデルでは効率的であると考えられています。
もう1つのよく使われる尺度は、ネットワークで送信されるビットの総数です（通信の複雑さを参照）。[ 70 ]この概念の特徴は、通常、CONGEST(B) モデルで捉えられます。これは LOCAL モデルと同様に定義されますが、単一のメッセージには B ビットしか含めることができません。
従来の計算問題は、ユーザーが質問をし、コンピュータ（または分散システム）がその質問を処理し、回答を生成して停止するという流れで進められます。しかし、食事中の哲学者問題やその他の類似の相互排他問題のように、システムが停止してはならない問題も存在します。これらの問題では、分散システムは共有リソースの使用を継続的に調整し、競合やデッドロックが発生しないようにする必要があります。
分散コンピューティングには、フォールトトレランスに関連するものなど、固有の根本的な課題も存在します。関連する問題の例としては、コンセンサス問題[ 71 ] 、ビザンチンフォールトトレランス[ 72 ]、自己安定化[ 73 ]などが挙げられます。
分散システムの非同期性を理解することにも多くの研究が集中している。
分散システムでは、レイテンシは「中央値」や「平均値」では誤解を招く可能性があるため、「99パーセンタイル」で測定する必要があることに注意してください。[ 77 ]
コーディネーター選出（またはリーダー選出）とは、複数のコンピュータ（ノード）に分散されたタスクのオーガナイザーとして単一のプロセスを指定するプロセスです。タスクが開始される前は、すべてのネットワークノードは、どのノードがタスクの「コーディネーター」（またはリーダー）として機能するのかを知らないか、現在のコーディネーターと通信できません。しかし、コーディネーター選出アルゴリズムが実行されると、ネットワーク全体の各ノードは、特定の固有のノードをタスクコーディネーターとして認識します。[ 78 ]
ネットワークノードは、どのノードが「コーディネーター」状態になるかを決定するために、互いに通信します。そのためには、ノード間の対称性を破る何らかの方法が必要です。たとえば、各ノードが一意で比較可能な識別子を持っている場合、ノードは自身の識別子を比較し、最も高い識別子を持つノードをコーディネーターと決定することができます。[ 78 ]
この問題の定義は、トークンが失われたトークンリングネットワークで新しいトークンを作成する方法として形式化されたLeLannによるものとされることが多い。 [ 79 ]
コーディネーター選出アルゴリズムは、送信されるバイト総数と時間の点で経済的になるように設計されています。Gallager、Humblet、Spira [ 80 ]が提案した一般的な無向グラフ向けのアルゴリズムは、分散アルゴリズム全般の設計に大きな影響を与え、分散コンピューティングにおける影響力のある論文としてダイクストラ賞を受賞しました。
無向リング、単方向リング、完全グラフ、グリッド、有向オイラーグラフなど、さまざまな種類のネットワークグラフに対して、他にも多くのアルゴリズムが提案されました。グラフファミリーの問題をコーディネーター選出アルゴリズムの設計から切り離す一般的な方法は、Korach、Kutten、およびMoranによって提案されました。[ 81 ]
分散システムでは、協調動作を行うためにコーディネータの概念が用いられます。コーディネータ選出問題とは、分散システム内の異なるプロセッサ上のプロセス群の中から、中央コーディネータとして機能するプロセスを選択することです。中央コーディネータ選出アルゴリズムはいくつか存在します。[ 82 ]
これまでのところ、焦点は与えられた問題を解決する分散システムの設計に置かれてきた。補完的な研究課題は、与えられた分散システムの特性を研究することである。 [ 83 ] [ 84 ]
停止問題は、集中型計算の分野における類似の例です。コンピュータプログラムが与えられ、それが停止するか、永遠に実行されるかを判定することが課題です。停止問題は一般的には決定不能であり、当然ながら、コンピュータネットワークの動作を理解することは、少なくとも1台のコンピュータの動作を理解することと同じくらい困難です。[ 85 ]
しかし、決定可能な興味深い特殊なケースは数多く存在します。特に、有限状態機械のネットワークの挙動について推論することが可能です。一例として、相互作用する（非同期かつ非決定的な）有限状態機械のネットワークがデッドロックに達する可能性があるかどうかを判定することが挙げられます。この問題はPSPACE完全問題[ 86 ]、すなわち決定可能ですが、大規模ネットワークの場合にこの問題を解決する効率的な（集中型、並列型、または分散型の）アルゴリズムが存在する可能性は低いと考えられます。
物理的に分散した複数のコンポーネントで構成され、各コンポーネントは独自のストレージを使用して独立して動作しますが、明示的なメッセージパッシングによって時折通信を行います。このようなシステムは分散システムと呼ばれます。
分散プログラムは、並行して動作し、明示的なメッセージパッシングによって通信するプロセスの集合で構成されます。各プロセスは、他のプロセスによって変更可能な変数とは互いに排他的な変数セットにアクセスできます。
{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）{{cite journal}}: CS1 maint: 複数の名前: 著者リスト (リンク)
ウィキメディア・コモンズにある分散コンピューティング関連のメディア