Paxos と Raft はコンセンサスアルゴリズム/プロトコルではないのですか?

インターネットの一員として、私たちは「分散」の雰囲気に浸ることがよくあります。高可用性、高信頼性、高性能などの言葉がいたるところで見られ、CAP、BASE、2PC、Paxos、Raftなどの用語も自由に使用できます。しかし、私たちの「不正確な」コミュニケーションの中で、いくつかの言葉は徐々に誤用されたり、曖昧になったりしてきました。今日は、「一貫性」という言葉について簡単にお話ししましょう。

[[318778]]

Paxos、Raft などは、しばしば誤って「一貫性アルゴリズム」と呼ばれます。しかし、「一貫性」と「コンセンサス」は同じ概念ではありません。 Paxos、Raft などは、実際にはコンセンサス アルゴリズムです。

1998年、レスリー・ランポートはACM Transactions on Computer Systems誌に「The Part-Time Parliament」[1]と題する論文を発表した。これはPaxosアルゴリズムの最初の公開出版物であった。しかし、論文が発表された後も、多くの人が元の論文は難しすぎると感じていました。その後、Lamportは「Paxos Made Simple」[2]という別の論文を書きました。Paxosについて学びたいときは、この論文を直接読むことができます。

話を元に戻して、「Paxos Made Simple」で「Consistency」という単語を検索します。下の図に示すように、一致する結果は実際には存在しません。

一方、「コンセンサス」という単語を検索すると、多くの一致が表示されました。

言い換えれば、一貫性という言葉は Paxos の論文全体では言及されていないので、「Paxos は一貫性アルゴリズムである」という記述はどこから来ているのでしょうか。

同様に、Raftの論文「理解可能なコンセンサスアルゴリズムの探求（拡張版）」[3]では、冒頭でRaftを明確に定義しています。Raftはコンセンサスアルゴリズムです。...ここで使用されている単語はコンセンサスであり、一貫性ではないことに注意してください。

この時点で、もう一度辞書を開いてみるのもよいでしょう。一見すると、辞書の Consistency と Consenus の翻訳は似ており、どちらも「一貫性」を意味しますが、よく見ると異なることがわかります。Consistency: 一貫性、Consensus: 合意、全会一致の意見。

専門的な観点から見ると、分散システムにおける一貫性と通常呼ばれるものは、強い一貫性、順次一貫性、最終的な一貫性など、同じデータの複数のコピーのデータ一貫性を指し、これらはすべてコピー問題における一貫性を説明するために使用されます。コンセンサスは異なります。簡単に言えば、コンセンサスの問題は、複数のノードが特定のアルゴリズムを通じて同じ状態に到達するプロセスです。一貫性は結果を重視しますが、コンセンサスはプロセスを重視します。

「分散システムの概念と設計」という本では、コンセンサスの問題を次のように定義しています。コンセンサスに達するために、各プロセス pi は最初は未決定の状態にあり、セット D から値 vi を提案します。プロセスは相互に通信し、値を交換します。次に、各プロセスは決定変数 di の値を設定します。この場合は決定状態になります。この状態では、彼はもう di を変更しません。

次の図は、コンセンサス アルゴリズムに関係する 3 つのプロセスを示しています。 2 つのプロセスは「続行」を提案し、3 番目のプロセスは「中止」を提案しましたが、その後クラッシュしました。正しいままのプロセスは両方とも「続行」することを決定します。 (ここで、i = 1, 2, …, N; j = 1, 2, …, N)

コンセンサス アルゴリズムでは、実行ごとに次の条件が満たされる必要があります。

• 終了: すべての正しいプロセスは、最終的に決定変数を設定します。
• 一致: すべての正しいプロセスの決定値は同じです。つまり、pi と pj が正しく、決定状態に入っている場合、di = dj になります。
• 完全性: 正しいプロセスがすべて同じ値を提案する場合、決定状態にあるすべての正しいプロセスがその値を選択しています。

コンセンサス問題では、すべてのノードが最終的にコンセンサスに達する必要があります。最終的な目標はすべてのノードが合意に達することであるため、強い一貫性と弱い一貫性の区別はありません。したがって、今後、「Paxos は強力な一貫性アルゴリズムである」や「Raft は強力な一貫性プロトコルである」などの類似の記述を目にしたときは、以下の内容を「批判的な」目で見る必要があります。

私たちのほとんどにとって、私たちの仕事のほとんどにおいて、一貫性とコンセンサスの違いは実際には無関係です。しかし、次元を上げて分散場の内容を深く研究したい場合、これらの最も基本的な概念が明確に区別されていないと、その後の学習プロセスが大きく妨げられます。

単語が似ているほど、より明確に区別する必要があります。同じ単語でも意味が異なる場合があります。たとえば、CAP と ACID の C はどちらも Consistency (一貫性) を表しますが、それぞれのシナリオでの意味は異なります。

• ACID の C はトランザクションの一貫性を意味し、一連のデータ変更操作におけるデータの正確性を保証します。つまり、トランザクション中の複数の操作中に、データが突然消えたり増加したりすることはなく、データの追加、削除、変更の各操作は因果関係があります。たとえば、ユーザー A がユーザー B に 200 元を送金した場合、ユーザー A のお金が差し引かれるが、ユーザー B は受け取っていないという状況は発生しません。
• 分散環境では、複数のサービス間のレプリケーションは非同期で行われ、一定の時間がかかり、即座に完了することはありません。サービス ノードのデータが変更された後、他のサービス ノードに同期されるまでに一定の時間間隔があります。この間隔中に同時読み取り要求があり、これらの要求が複数のノードに負荷分散されている場合、要求がデータ同期を完了していないノードに届く可能性があるため、複数のノードからのデータの不整合が発生する可能性があります。 CAP の C は、分散環境で読み取られたデータの一貫性を保証することです。

一般に、ACID の C は、単一のデータベース トランザクション操作中にデータの整合性と正確性を確保する必要性を強調しますが、CAP 理論の C は、データの複数のバックアップの読み取りと書き込みの一貫性を強調します。

今日の知識ポイントについて何か言いたいことはありますか？コメント欄にご意見をお寄せください。

参考資料 http://lamport.azurewebsites.net/pubs/lamport-paxos.pdf

http://lamport.azurewebsites.net/pubs/paxos-simple.pdf

ラフト

CAPとPaxosコンセンサスアルゴリズムについての簡単な説明

「一貫性」という言葉の誤用

分散コンセンサス: Viewstamped レプリケーション、Raft、Paxos