Yige

分散型排他#

内容来自极客时间专栏: 《分散型技術原理とアルゴリズム解析》

排他とは、ある条件のリソースが同時に一つのユニットによってのみ占有されることを指します。分散型システムにおいて、この排他性のあるリソースアクセス方式は分散型排他（Distributed Mutual Exclusion）と呼ばれ、この排他アクセスされる共有リソースはクリティカルリソース（Critical Resource）と呼ばれます。

分散型排他のいくつかの実装方法:

集中型アルゴリズム#

Yarnのリソーススケジューリングメカニズムを連想させます

システムはコーディネーターの役割を導入し、各プログラムはリソースを要求する際にまずコーディネーターにリクエストを送信します。次に、コーディネーターはリソースが空いているかどうかを判断し、空いていればそのプログラムに直接割り当てます。占有されている場合は、そのリクエストに番号を付け、リソースを取得するためのリクエストキューに並ぶことになります。しかし、同時に以下の 2 つの問題も存在します:

• 単一障害点の問題。コーディネーターが故障すると、すべてのプログラムがクリティカルリソースにアクセスできなくなり、システム全体が利用できなくなります。そのため、コーディネーターの正常な運用状態を保証するための追加メカニズムが必要です（実際、zookeeper もこのようなものに似ています）。
• コーディネーターは通常、システムの性能ボトルネックになります。コーディネーターが処理するメッセージの数は、クリティカルリソースにアクセスするプログラムの数に応じて線形に増加します。
  集中型アルゴリズムの示意図は以下の通りです:
  

分散型アルゴリズム#

HDFS のファイル変更メカニズムはこのアルゴリズムを採用しています

集中型アルゴリズムとは異なり、分散型アルゴリズムの実装原理は、あるプログラムがリソースを要求する際に、まずシステム内の他のすべてのプログラムにリクエストを送信し、他のプログラムがそのリソースを占有していなければ同意の結果を返します。すべての他のプログラムから同意メッセージを受け取った後にのみ、クリティカルリソースにアクセスできます。
このアルゴリズムは可用性が非常に低く、主に 2 つの理由があります:

• システム内のプログラム数が増えるにつれて、メッセージの数はクリティカルリソースにアクセスするプログラムの数に対して指数関数的に増加します（2n * (n-1)）、これにより“シグナリングストーム”が発生し、プログラムが受け取るリクエストが自分の処理能力を完全に超えてしまい、正常な業務が行えなくなります。
• コンピュータネットワークにおいてメッセージの信頼性を保証することも難しく、メッセージの喪失や遅延到着などの状況が発生します。分散型アルゴリズムでも同様で、たとえばあるプログラムが故障し、同意リクエストの応答メッセージを送信できなかったり、遅延応答したりすると、他のプログラムは待機状態に陥り、システムがブロックされ、利用できなくなります。

分散型アルゴリズムは「先着順」および「全票投票通過」のメカニズムに基づき、各プログラムが時間順に公平にリソースにアクセスできるようにします。シンプルで実装が容易であり、クリティカルリソースの使用頻度が低く、システム規模が小さいシナリオに適しています。

トークンリングアルゴリズム#

アルゴリズムの示意図は以下の通りです：

示されているように、プログラムは環状構造に並び、トークンが循環して渡されます。トークンを受け取ったプログラムはクリティカルリソースにアクセスする権利を持ち、アクセスが完了した後、トークンを次のプログラムに渡します。もしそのプログラムがクリティカルリソースにアクセスする必要がない場合は、トークンを次のプログラムに直接渡します。

ps: 最初は制限メカニズムのトークンバケットアルゴリズムを考えましたが、実際には異なります。

まとめ & 考察#

考察：#

以下の考察内容には問題があるかもしれませんので、指摘を歓迎します。

集中型アルゴリズム#

改善のアイデア: redis クラスター通信モードを参照し、ハッシュキーを使用して大量のリクエストを異なるマスターに分散させ、大量のリクエストを処理します。各マスターは小さなクラスターの主従ノードによって単一障害を保証します。

分散型アルゴリズム#

タイムアウトを設定し、あるノードが故障し、応答が遅れてタイムアウト制限に達した場合、そのノードをシステムから除外するか、直接無視します。

トークンリングアルゴリズム#

改善のアイデア：参加者の使用頻度に基づいて重みをリストアップし、スムーズな加重ラウンドロビンアルゴリズムを組み合わせて次の参加者を選出します。同時に、環の中のあるノードが故障した場合は、迅速に除外し、トークンが正常なノード間で渡されることを保証する必要があります。

伝統的な単一機械での排他方法が分散環境で使用できない理由#

単一機械では、信号量、ロックメカニズム、スレッド同期などの方法を使用して排他を実現できますが、JVM レベルや単一ハードウェアレベルで排他を実現できます。分散環境では、各ノードが異なるサーバー上で実行されており、お互いに認識できないため、追加の手段を使用して各ノードの排他アクセスを保証する必要があります。