この記事は、分散システムにおける真実と虚偽を理解するのに役立ちます

[[409590]]

分散システム内の各サーバーはインターネットを介して接続されていることはご存じのとおりです。その結果、各サーバーの実際の状態を把握することが困難になります。たとえば、別のサーバーに問題があるかどうかを判断する唯一の方法は、そのサーバーにリクエストを送信することです。返事が来た時だけ、良かったと思うのです。応答がない場合は、ネットワーク障害が原因で応答がない可能性があり、実際には相手側のマシンに問題がある可能性があるため、相手側のサーバーに問題があるかどうかを判断するのは困難です。では、分散システムでこれらの問題を正確に判断するにはどうすればよいでしょうか?この記事では関連する方法を詳しく紹介します。

多数の事実に基づく

多くの場合、ノードには実際には問題がない可能性があります。たとえば、GC を実行している場合、GC 期間中はいかなる要求にも応答できません。現時点では、ノード自体の観点から見ると、非常に大丈夫であり、問題はありません。しかし、他のノードから見ると、この GC ノードは問題のあるノードとまったく同じです。リクエストに応答せず、再試行にも応答しません。そのため、他のノードはそれが問題があると考えることになります。この観点から見ると、ノード自体が問題があるかどうかを知ることは実際には困難です。

現在、ノードに問題があるかどうかを判断するための最も一般的なアルゴリズムは、多数決による意思決定に基づいています。たとえば、ノードが 5 つある場合は、全員が一緒に投票します。一定数以上のノード (通常は半数以上、ここでは 3 つのノード) が問題があると判断した場合、このノードには本当に問題があると判断されます。ノード自体に問題がなくても、大多数が問題があると考えている限り、問題があるとみなします。ここで多数決が使用される理由は、システム内に多数決が 2 つ存在することはできず、1 つだけであるため、衝突が起こらないためです。

リーダーとロック

ノードに問題があるかどうかを判断する必要があるのはなぜですか?実際、分散システムでは、次のように一度しか使用できない概念が使用されるシナリオが数多くあります。

データベースパーティション内の1つのノードのみがリーダーになれる
同時書き込みを防ぐため、オブジェクトのロックを保持できるのは 1 つのトランザクションまたはクライアントのみです。
ユーザー名は一意である必要があるため、ユーザーのみが登録できます。

これらのシナリオでは、設計時に注意する必要があります。たとえば、あるノードが自分だけが選択されていると考えている場合でも (たとえば、自分がリーダーであると考えている、オブジェクトのロックを持っていると考えているなど)、他のほとんどのノードは問題があると考える可能性があります。デザインが良くないと問題が発生します。次の例を見てみましょう。

この例では、複数のクライアントが同じデータにアクセスするのを防ぐために、書き込み後に各クライアントがロックを取得することを要求します。このロックはリースロックであり、タイムアウトすると解除されます。ここでは、Client1 が最初にロックを申請したことがわかりますが、残念ながら、ロックを取得した後すぐに GC が発生し、リースタイムアウトを超えて GC が発生したため、リースタイムアウト後にロックが解放されました。その後、クライアント2はロックを取得し、更新を行いました。 GC が戻った後、クライアント 1 はロックを保持していると判断して直接書き込み、問題が発生します。ここでの問題は、GC が戻った後、クライアント 1 がロックをまだ保持していると誤って認識することです。

フェンシングトークン

では、このような誤解にどう対処すればよいのでしょうか?一般的な技術はフェンシングです。次の図に示すように:

ここで行われた変更は、ロックを取得するたびにトークン値がクライアントに返され、このトークンはロックが取得されるたびに増加することです。このように、クライアントが書き込むときに、トークンも送り返す必要があります。このようにして、ストレージはこのトークンを使用して、古いトークンの書き込みを拒否するかどうかを決定できます。

一般的な実装方法は、ZooKeeper の TransactionID またはノードバージョンを fencingToken として使用することです。

ビザンチン断層

上記の FencingToken には、クライアントによって送信されたトークンが実際に受信されるという前提があります。書き込み時にクライアントから送信されたトークンが偽のトークンである場合、明らかに fencingToken に問題が発生することが想像できます。したがって、分散システムの場合、ノードが存在すると、問題はさらに複雑になります。私たちはこの状況をビザンチン問題と呼んでいます。これは、ビザンチン将軍問題とも呼ばれることが多いものです。

ビザンチン問題のあるシステムでは、メッセージが信頼できないノードが 1 つまたは 2 つ存在する可能性があると単純に想定できます。この信頼性の低さは、次のような理由により発生する可能性があります。

何らかの理由で、マシンのメモリまたは CPU レジストリ内のデータが破損しています。たとえば、レジストリの読み取り時にエラーが発生した場合は、デフォルト値や任意の値などを返します。
たとえば、不正行為や攻撃が発生したとします。この場合、ノードは信頼されません。

もちろん、現実には、この信頼できない問題は、ほとんどまたはすべてのノードではなく、比較的少数のノードで発生すると考えられます。したがって、ほとんどのノードで信頼できない事態が発生した場合 (たとえば、受信したトークンに常に乱数を追加するコードにバグがある場合)、対応するアルゴリズムではこの問題を解決できません。

嘘を減らす

ただし、嘘をついているノードはほとんどないと考えています。しかし、次のようなノードを検出または保護するためのメカニズムがあればさらに良いでしょう。

ネットワークパケットについては、正しいかどうかを検出するためのチェックサムを追加します。
ユーザーの入力値が妥当な範囲内であるかどうかを確認するなど、いくつかのチェックをユーザー入力値に追加します。
NTP クライアントは複数のアドレスに接続し、多数派のフィードバックを参照して実際の時間を決定します。

システムモデルと現実

私たちは、さまざまな分散システムの問題を解決するために多くのアルゴリズムを設計してきました。これらのアルゴリズムは一連のソフトウェアとハードウェアのペアに基づいているため、多くの仮定があり、これらの依存関係は一般にシステムモデルと呼ばれています。

たとえば、時間の仮定について話すとき、次の 3 つが一般的なシステムモデルです。

同期モデル

いわゆる同期モデルとは、ネットワークの遅延、プロセスの一時停止、クロックのドリフトが一定の制限を超えないことがわかっていることを意味します。もちろん、ネットワーク遅延がないという意味ではなく、制限を超えないことがわかっているという意味です。もちろん、このモデルは現実には現実的ではありません。予期しない遅延が常に発生するからです。

部分同期モデル

いわゆる部分同期モデルは、ほとんどの場合に同期モデルと見なされるもので、特定の制限を超えることはありませんが、場合によってはこれらの制限を超えることもあります。これはより現実的なモデルです。

非同期モデル

このモデルはいかなる仮定も行わず、クロックさえ信頼しません。たとえば、タイムアウトは使用しません。このモデルの制限は非常に大きいです。

時間に関する上記の想定に加えて、もう 1 つの一般的な問題は、ノード障害の想定です。通常、次の 3 つのモデルがあります。

クラッシュストップエラー

このモデルでは、ノードに応答しないなどの問題がある場合、そのノードは二度と戻ってこないとアルゴリズムが判断します。

クラッシュ回復エラー

このモデルでは、アルゴリズムはノードに問題があり、しばらくすると再発すると考えます。もちろん何が戻ってくるかは分かりません。これには、クラッシュ後でも回復できるように、ディスクに多くのものを書き込むなど、ノードに共通のストレージメディアが必要になる場合があります。

ビザンチンエラー

上で述べたように、ノードには何でも起こり得ます。

実際に見られる最も一般的なモデルは、部分的に同期したクラッシュ回復エラーです。では、分散システムのアルゴリズムはこれらのモデルをどのように使用するのでしょうか?

アルゴリズムの正確さ

アルゴリズムの正しさを判断するときは、いくつかの特性を使用して判断する必要があります。たとえば、小さいものから大きいものに並べ替えるアルゴリズムでは、出力内の 2 つの異なる要素は、前者が後者よりも小さいという要件を満たす必要があります。これが最も簡単な判断方法です。

同様に、分散システムのアルゴリズムが正しいかどうかをどのように判断するのでしょうか?ロックを例に挙げてみましょう。判断には次の属性を使用できます。

ユニークさ

2 つのリクエストが同じトークンを受信することはありません。

単調増加

x を要求するトークンが tx であり、y を要求するトークンが ty であり、x が y の前にある場合、tx<ty です。

信頼性

ノードがリクエストを送信すると、クラッシュしない限り、最終的には応答を受信します。

安全性と活力

ここでは、セキュリティと活性という 2 つの概念を区別する必要があります。例えば、上記の例では、一意性と単調増加性が安全性であり、信頼性が活力です。両者の簡単な違いは、一般的に安全性は悪いことが起こり得ないことを意味し、活力は良いことが最終的に起こることを意味するということです。これら 2 つを区別することで、より複雑なシステムモデルを処理できるようになります。