分散ミューテックス#
内容来自极客时间专栏: 《分散技術原理とアルゴリズム解析》
ミューテックスとは、条件付きリソースに対して、同時に 1 つのユニットだけが占有できることを指します。分散システムにおいて、この排他的なリソースアクセス方式は分散ミューテックス（Distributed Mutual Exclusion）と呼ばれ、ミューテックスでアクセスされる共有リソースはクリティカルリソース（Critical Resource）と呼ばれます。
分散ミューテックスのいくつかの実装方法:
集中型アルゴリズム#
Yarnのリソーススケジューリングメカニズムを連想させます
システムはコーディネーターの役割を導入し、各プログラムはリソースを要求する際にまずコーディネーターにリクエストを送信します。次に、コーディネーターはリソースが空いているかどうかを判断し、空いている場合はそのプログラムに直接割り当てます。もし占有されている場合は、そのリクエストに番号を付け、リソースを取得するためのリクエストキューに並ぶことになります。しかし、同時に以下の 2 つの問題も存在します:
- 単一障害点の問題。コーディネーターが故障すると、すべてのプログラムがクリティカルリソースにアクセスできなくなり、システム全体が利用不可になります。そのため、コーディネーターの正常な運用状態を保証するための追加メカニズムが必要です（実際、zookeeper もこのようなものに似ています）。
- コーディネーターは通常、システムのパフォーマンスボトルネックになります。コーディネーターが処理するメッセージの数は、クリティカルリソースにアクセスするプログラムの数に応じて線形に増加します。
集中型アルゴリズムの概念図は以下の通りです:
分散型アルゴリズム#
HDFS のファイル変更メカニズムはこのアルゴリズムを採用しています
集中型アルゴリズムとは異なり、分散型アルゴリズムの実装原理は、あるプログラムがリソースを要求する際に、まずシステム内の他のすべてのプログラムにリクエストを送信し、他のプログラムがそのリソースを占有していなければ同意の結果を返します。すべての他のプログラムから同意メッセージを受け取った後にのみ、クリティカルリソースにアクセスできます。
このアルゴリズムは可用性が非常に低く、主に 2 つの理由があります:
- システム内のプログラム数が増えるにつれて、メッセージの数はクリティカルリソースにアクセスするプログラムの数に対して指数関数的に増加します（
2n * (n-1)）、これにより“シグナリングストーム”が発生し、プログラムが受け取るリクエストが処理能力を完全に超え、正常な業務が行えなくなります。 - コンピュータネットワークにおいてメッセージの信頼性を保証することも難しく、メッセージの喪失や遅延到着などの状況が発生します。分散型アルゴリズムでも同様で、例えばあるプログラムが故障し、同意リクエストの応答メッセージを送信できない、または遅延応答する場合、他のプログラムは待機状態に陥り、システムがブロックされ、利用不可になります。
分散型アルゴリズムは「先着順」と「全票投票通過」のメカニズムに基づいて、各プログラムが時間順に公平にリソースにアクセスできるようにします。シンプルで実装が容易であり、クリティカルリソースの使用頻度が低く、システム規模が小さいシナリオに適しています。
トークンリングアルゴリズム#
アルゴリズムの概念図は以下の通りです：
示されているように、プログラムは環状構造に並び、トークンが循環して渡されます。トークンを受け取ったプログラムはクリティカルリソースにアクセスする権利を持ち、アクセスが完了したらトークンを次のプログラムに渡します。もしそのプログラムがクリティカルリソースにアクセスする必要がない場合は、直接トークンを次のプログラムに渡します。
ps: 最初は制限メカニズムのトークンバケットアルゴリズムを考えましたが、実際には異なります。
まとめ & 考察#
考察：#
以下の考察内容には問題があるかもしれませんので、指摘を歓迎します。
集中型アルゴリズム#
改善のアイデア: redis クラスター通信モードを参考にし、ハッシュキーを使用して大量のリクエストを異なるマスターに分散させ、大量のリクエストを処理します。各マスターは小さなクラスターの主従ノードによって単一障害を保証します。
分散型アルゴリズム#
タイムアウトを設定し、あるノードが故障し、応答が遅れてタイムアウト制限に達した場合、そのノードをシステムから除外するか、直接無視します。
トークンリングアルゴリズム#
改善のアイデア：参加者の使用頻度に基づいて重みをリストアップし、スムーズな加重ラウンドロビンアルゴリズムを組み合わせて次の参加者を選出します。
また、環の中であるノードが故障した場合は、迅速に除外し、トークンが正常なノード間で渡されることを保証する必要があります。
伝統的な単一機械のミューテックス方法が分散環境で使用できない理由#
単一機械では、ミューテックスはセマフォ、ロックメカニズム、スレッド同期などの方法を使用して、JVM レベルまたは単一機械のハードウェアレベルで実現できます。分散環境では、各ノードが異なるサーバーで実行され、互いに認識できないため、追加の手段を使用して各ノードのアクセスをミューテックスする必要があります。