スプリットブレイン、投票、クォーラムの回避

Question

n個のプロセスがn個あるとします。n> 2個のプロセスがあるとします。だから、彼らはどちらがアクティブであるかを判断するために互いを見て投票する必要があります。

すべてのプロセスは任意の時点で失敗する可能性があり、我々は可能な場合はアクティブなプロセスを持っているしたいのですが、...

、彼らがすることはできませんので、もし我々がはが、同時にアクティブに2を持っていてはいけません誰もアクティブにしない方がよいと確信してください。 （すなわち、私たちは頭脳の分割を避けたい）

これらの間で利用できる通信メカニズムは、pub-subメッセージング（ポイントツーポイントではない）だけです。

1つ以上のデータベースが使用できますが、1つのデータベースで単一障害点が発生することはありません。つまりすべてのプロセスが動作可能であり、単一のデータベースが失われてもそのようなことができなければ、非常に望ましくないことになります。

デザインは？どのメッセージを公開する必要がありますか？

Answer 1

論：

これはまた時々The Two Generals Problem呼ばれる、Consensus Problemの一形態であるリーダー選挙、です。いくつかの仮定のセット（完全に非同期であり、メッセージは失われる可能性があります）では不可能であることが証明されており、その証明は特に優雅です。

この問題の直感は次のとおりです。いくつかの固定数のメッセージでコンセンサスに達することを可能にするアルゴリズムがあるとします。障害は許容されるため、プロトコルからメッセージを1つドロップすることはできますが、それでも機能するはずです。メッセージが全くなくなるまでこのプロセスを繰り返すことはできますが、明らかに不可能です。

実際には、同期システムをシミュレートするために障害検出器を使用してこれを克服しています。

コンセンサスを解決する最も広く知られているアルゴリズムは、参加ノードの最大半分の障害を許容できるPaxosです。パクソスはプロトコルの細部のわずかな誤解でさえ、正確性を損なうため、実装が非常に難しいという評判を持っています。

実用的なソリューション：

一般的には問題は非常に困難ですが、作業システムを得ることがはるかに容易です。 Paxosの棚の実装や同等のアルゴリズムが利用できます。 Apache Zookeeperは私が知っている最高のものです。あなたの特定の問題については、私はそれがあなたの最速ルートになると確信しています。他のPaxosの実装もありますし、Wackamoleなどのネットワーク冗長仮想IPツールで何かを構築することも可能です。私は、ほとんどの商用データベースのハイエンドバージョンでは、（高価な）オプションとしてクォーラム機能を提供していると思います。

また、多くのアプリケーションでは、正確性をわずかに弱めるか、問題をより簡単に解決できるように調整することは許容されます。

たとえば、リカバリが迅速である可能性があるため、シングルポイント障害が許容される場合、問題は簡単です。ただ1つの特別なノードで作業してください。

偶数のアクションの周りにシステムを構築して、重複した処理が許容されるようにすることも考えられます。

最後に、ワークロードを非冗長システムのプールに分割することができます。ここでは、障害が回復まで処理が遅延しますが、そのノードの項目のみが処理されます。

これらの種類の妥協はずっと簡単で、しばしばより良い選択です。 1つは、それを実装する複雑さに対して完全なソリューションの有用性を評価し、本当に価値があるかどうかを確認する必要があります。このため、多くの実用的システムでは、2 Phaseまたは3 Phase Commitが使用されますが、いくつかのシナリオではブロックされますが、フルクォーラムシステムの複雑さに比べて可用性が低下します。

Answer 2

私はpub-subメッセージでは明確ではありません。

外部ソースから何らかの種類の作業オブジェクトを取得していて、そのうちの1人に作業を処理させたい場合は、2^64の値をスペースで割ります各ノードはチャンクをとる。各ノードは、作業オブジェクトが入ってきたときにそれらをハッシュし、それがそれらのオブジェクトであるかどうかを判断することができます。

Answer 3

ルーティングプロトコル（OSPFおよびIS-IS）がどのようにそれを行うのかを見て、それがあなたに適しているかどうかを見てください。彼らはリーダーを選出する（OSPFの場合はバックアップリーダー）。