分散相互排除方式は分散技術に不可欠である

分散ミューテックスとは何ですか?

在庫の削減は非常に一般的な例です。 2 つのスレッドが同時に在庫が 10 個あることを確認し、同時に 10 個を販売すると、在庫から 10 個が差し引かれ、在庫に -10 個が残ります。これは明らかに不合理であり、1 つのスレッドが動作しているときは別のスレッドは動作できず、排他的リソース アクセスが必要になります。

分散システムでは、この排他的リソース アクセス方式は分散相互排他と呼ばれ、排他的にアクセスされる共有リソースはクリティカル リソースと呼ばれます。

分散テクノロジーで重要なリソースへの相互排他アクセスを実行する方法を見てみましょう。

横暴な大統領：中央集権型アルゴリズム

集中型アルゴリズムはコーディネーターを確立することです。重要なリソースにアクセスしたい 3 つの当事者は、コーディネータを経由する必要があります。コーディネータがアクセス可能と判断した場合にのみアクセスでき、そうでない場合はアクセスできません。

具体的な操作としては、まず訪問者がコーディネーターを訪問します。コーディネータは、リソースを占有している他のビジターがいないことを検出した場合、現在のビジターに解放信号を送信します。それ以外の場合は、キューイング、スピンなどのコーディネータのルールに従って次のステップに進みます。

この相互排除アルゴリズムは、集中型アルゴリズム、または中央サーバー アルゴリズムと呼ばれます。コーディネーターは集中型プログラムまたは中央サーバーを表すため、このように呼ばれます。

プログラムが重要なリソース アクセスを完了するには、次のプロセスとメッセージのやり取りが必要です。コーディネータに承認要求情報を送信する (1 つのメッセージやり取り)。コーディネータはプログラムに認証情報を発行します (1 つのメッセージ対話)。プログラムが重要なリソースを使用した後、1 つのメッセージ インタラクションで、コーディネータにリリース承認を送信します。したがって、各プログラムは、重要なリソース アクセスを完了するために 3 つのメッセージ インタラクションを実行する必要があります。

集中型アルゴリズムの利点:

直感的でシンプルで、情報のやり取りがほとんど必要なく、実装も簡単です。すべてのプログラムはコーディネータと通信するだけでよく、プログラム間の通信は必要ありません。

集中型アルゴリズムの欠点:

一方では、コーディネーターがシステムのパフォーマンスのボトルネックになります。重要なリソースにアクセスしようとしているプログラムが 100 個ある場合、コーディネーターは 100 * 3 = 300 個のメッセージを処理する必要があると想像してください。つまり、コーディネータによって処理されるメッセージの数は、重要なリソースにアクセスする必要があるプログラムの数に比例して増加します。

その一方で、単一点障害の問題が発生する可能性も高くなります。コーディネータに障害が発生すると、すべてのプログラムが重要なリソースにアクセスできなくなり、システム全体が使用できなくなります。したがって、集中型アルゴリズムを使用する場合は、コーディネーターを実行するために、パフォーマンスと信頼性に優れたサーバーを必ず選択してください。

現在、市場における集中型アルゴリズムの実装は、主に Redis Zookeeper データベースを通じて実現されています。これらのコンポーネントには、高可用性と高パフォーマンスを実現する独自のソリューションがあります。開発者は、さまざまなビジネスに基づいて、使用する方法を選択する必要があります。

民主的な協議：分散アルゴリズム

集中型アルゴリズムは、訪問者がリソースにアクセスする前にコーディネータの同意を求めるアルゴリズムであり、分散型アルゴリズムは、訪問者がリソースにアクセスする前に他の訪問者の同意を求めるアルゴリズムです。

具体的な操作としては、プログラムが重要なリソースにアクセスする場合、まずシステム内の他のプログラムに要求メッセージを送信します。すべてのプログラムから返された同意メッセージを受信した後にのみ、重要なリソースにアクセスできます。リクエスト メッセージには、リクエストされたリソース、リクエスト元の ID、およびリクエストが開始された時刻が含まれている必要があります。

これが民主的な協議方式です。分散分野では、これらを分散アルゴリズム、またはマルチキャストと論理クロックを使用するアルゴリズムと呼びます。

このアルゴリズムでは、プログラムは重要なリソース アクセスを完了するために次の情報操作を実行する必要があります。

1. 重要なリソースにアクセスするために他の n-1 個のプログラムに要求を送信するには、合計 n-1 個のメッセージのやり取りが必要です。
2. リソースにアクセスする前に、他の n-1 個のプログラムから同意メッセージを受信する必要があり、合計 n-1 回のメッセージ インタラクションが必要になります。

プログラムが重要なリソースに正常にアクセスするには、少なくとも 2*(n-1) 回のメッセージのやり取りが必要であることがわかります。システム内の n 個のプログラムが重要なリソースにアクセスする必要があると仮定すると、2n(n-1) 個のメッセージが同時に生成されます。大規模システムで分散アルゴリズムを使用する場合、重要なリソースにアクセスする必要があるプログラムの数に応じてメッセージの数が指数関数的に増加し、簡単に「通信コスト」が高くなる可能性があります。

分散アルゴリズムの利点:

分散アルゴリズムにより、各プログラムは「先着順」および「全員一致の投票」メカニズムに基づいて時系列順に公平にリソースにアクセスできるようになります。シンプルで、大まかで、実装も簡単です。

分散アルゴリズムの欠点:

システム内のより多くのプログラムが重要なリソースにアクセスする必要がある場合、「シグナリング ストーム」が発生する可能性があります。つまり、プログラムが受信した要求が処理能力を完全に超過し、通常の業務を実行できなくなります。

プログラムが失敗して同意メッセージを送信できなくなると、他のプログラムは応答を待つ状態になり、システム全体が停滞して使用できなくなります。したがって、集中型アルゴリズムのコーディネータ障害と比較すると、分散型アルゴリズムの可用性は低くなります。

もちろん、他のプログラムが利用可能かどうかを検出することでブロッキングの問題を解決できますが、これによってシステムの複雑さが増すことは間違いありません。

したがって、分散アルゴリズムは、ノード数が少なく変更頻度が低いシステムに適しており、各プログラムは通信して対話する必要があるため、P2P 構造のシステムに適しています。たとえば、ローカルエリアネットワークで実行される分散ファイルシステム、P2P 構造のシステムなどです。

Hadoop は私たちがよく知っている分散システムです。分散ファイルシステム HDFS のファイル変更は、分散アルゴリズムを適用する典型的なシナリオです。

同じローカル エリア ネットワーク内のコンピュータ 1、2、3 はすべて同じファイルのバックアップ情報を持ち、相互に通信できます。この共有ファイルは重要なリソースです。コンピュータ 1 が共有ファイルを変更する場合、次の操作を行う必要があります。

コンピュータ 1 はコンピュータ 2 と 3 にファイル変更要求を送信します。コンピュータ 2 と 3 はリソースを使用する必要がないと判断し、コンピュータ 1 の要求に同意します。他のすべてのコンピュータから同意メッセージを受信した後、コンピュータ 1 はファイルの変更を開始します。コンピュータ 1 は変更を完了すると、ファイル変更完了メッセージをコンピュータ 2 および 3 に送信し、変更されたファイル データを送信します。コンピュータ 1 から新しいファイル データを受信した後、コンピュータ 2 と 3 はローカル バックアップ ファイルを更新します。

交代型 CEO: トークン リング アルゴリズム

重要なリソースにアクセスするプログラムの問題も、CEO を交代させるというアイデアによって解決できます。下の図に示すように、すべてのプログラムはリング構造を形成します。トークンはプログラム間で時計回り (または反時計回り) に渡されます。トークンを受け取ったプログラムには、重要なリソースにアクセスする権利があります。アクセスが完了すると、トークンは次のプログラムに渡されます。プログラムが重要なリソースにアクセスする必要がない場合、トークンは次のプログラムに直接渡されます。分散分野では、このアルゴリズムはトークン リング アルゴリズム、またはリング ベース アルゴリズムと呼ばれます。理解と記憶を容易にするために、この方法をローテーション CEO 方式として鮮明に理解することができます。

写真

トークンリングアルゴリズムの利点:

分散アルゴリズムと比較すると、トークン リング アルゴリズムでは、他のすべての訪問者の同意を求める必要はなく、トークンを次の訪問者に渡すだけで済みます。これにより、通信圧力が相対的に軽減され、通信効率が高まります。

公平性が向上し、すべてのプログラムがサイクル内でストリート リソースにアクセスできるようになります。

一点だけの問題はありません。訪問者が失敗した場合、トークンは次の訪問者に直接渡され、失敗した訪問者は自動的に排除されます。

トークンリングアルゴリズムの欠点:

リング内のプログラムがリソースにアクセスするかどうかに関係なく、トークンを受け取って渡す必要があり、これによって無効な通信も発生します。システムに 100 個のプログラムがあると仮定すると、プログラム 1 がリソースにアクセスした後、他の 99 個のプログラムがアクセスを必要としない場合でも、トークンが他の 99 個のプログラムに渡されるまで待機しなければ、リソースに再度アクセスできず、システムのリアルタイム パフォーマンスが低下します。

トークン リング アルゴリズムは、単一点障害が改善された後、高い公平性と高い安定性を備えています。これは、システムが小規模で、システム内の各プログラムが重要なリソースを頻繁に、比較的短い期間使用するシナリオに適しています。

この記事では、分散技術における一般的な分散相互排除アルゴリズムを紹介します。次の記事では、分散相互排他実装スキームの具体的な内容、つまり分散ロックの具体的な実装について説明します。