Raft - Kubernetes(etcd)のHA構成はなぜ3台以上？

こんにちは。松本です。

Kubernetes コントロールプレーンの HA(High Available) 構成は二通りありますが、公式ドキュメント内に次のような記述があり、いずれの方式でも 3 台以上のマシンでクラスターを構成することが求められています。

For both methods you need this infrastructure:

Three machines that meet kubeadm’s minimum requirements for the masters

（中略）

For the external etcd cluster only, you also need:

Three additional machines for etcd members

この、最小が "three" である必要性は、どこからくる制約なのでしょうか。"two" じゃだめなのでしょうか。

二通りの HA 構成とは次の通りで、その主な違いは etcd クラスターの構成方法であることがわかります。

Stacked etcd topology - スタック化されたコントロールプレーンノードの内部にそれぞれ etcd を配置してクラスターを構成
External etcd topology - コントロールプレーンの外部に etcd クラスターを構成

そこで、etcd のドキュメントを見てみると、HA 構成の実現に Raft consensus algorithm を採用していることがわかりました。

etcd is written in Go and uses the Raft consensus algorithm to manage a highly-available replicated log.

本記事は、この Raft を紐解くことで "three" の意味を理解しようという、私の個人的な趣味による探索のメモです。

主な参考資料：

In Search of an Understandable Consensus Algorithm (Extended Version) | Diego Ongaro and John Ousterhout | Stanford University

State Machine Replication と分散合意アルゴリズム

高可用性（Hight availability）の実現などを目的に、ステートフルなサービスを、同じ機能と状態を持つ複数のノードで構成される分散サービス（レプリケーション）として設計する場合、各ノード上で動作するサービスの一貫性保証が課題になります。

この時、サービスの特性が決定論的であると定義できれば、同じ開始状態から同じ順序で命令（入力）を受け取ることで、どのサービスも同じ状態に到達し、同じ応答（出力）を返すことができます。この考えに基づいた設計を State machine replication とか、State machine approach と呼びます。前述のような個々のノード上で動作するサービスが State machine です。

state machine replication における各ノードは通常、state machine が実行する命令をエントリとしてログに格納し、順番通りに state machine に適用します。この、クラスター内のノードがログを複製し、state machine に適用するための分散合意アルゴリズムが Raft です。

Raft - 基本事項

ステータス

Raft クラスター内のノードには、三つのステータスが存在します。

leader - リーダー
candidate - リーダー候補
follower - フォロワー

通常、クラスター内の leader は一台だけで、その他のノードは全て follower です。leader がクライアントのリクエストを全て処理します。もしクライアントのリクエストが follower に届けば、リクエストは leader にリダイレクトされます。

新しい leader を選出するために立候補したノードが candidate になります。

RPC

Raft で扱う RPC は基本的に次の 2 つで、メッセージタイプは 4 つ（各 RPC のリクエストメッセージとレスポンスメッセージ）しかありません。

RequestVote RPC - leader になるために candidate が発行する RPC
AppendEntries RPC - ログの複製のために leader が発行する RPC

leader は、ログエントリを含まない AppendEntries RPC を heartbeat として定期的にクラスター内の他のノードに向け発行します。

term

Raft は、後述する leader election の開始から、選出された leader が存続する期間に term と呼ぶ番号を割り当てています。leader が確定せず、leader 不在で終了する term も存在します。

term は 0 から始まり、1 ずつインクリメントされます。

log

ノードは、state machine に適用するための命令を、ローカル内に保存しています。この命令のコレクションを log と呼び、log 内のエントリにはそれぞれ、leader がそのエントリを保存した際の term と、エントリを識別するための index が記録されます。

The Raft Consensus Algorithm

合意アルゴリズムは次の二つのメカニズムで構成されています。

Leader Election - 有効な leader の不在時に、新たな leader を決定する
Log Replication - leader がクライアントから受け取った log エントリを、他のノードに複製する

また、これらのメカニズムにおいて、Raft は次の特性が常に真であることを保証しています。

Election Safety - 1 つの term に leader は 1 台まで
Leader Append-Only - leader はローカルの log に対し新たな追記のみが可能で、削除や上書きはできない
Log Matching - ふたつのノードの log に同じ term と index を持つエントリが含まれている場合、その index までの全てのエントリは両者のノードで一致する
Leader Completeness - leader がコミット（後述）した log エントリは、以降の term の leader が持つ log に必ず含まれる
State Machine Safety - leader が state machine に適用した log エントリに対し、他のノードが、同じ index を持ち内容の異なるエントリを state machine に適用することはない

Leader Election のフロー

初期状態：起動された直後のノードのステータスは必ず follower となる。つまり、クラスター起動後は全ノードが follower であり、leader は存在しない。
開始：follower は、leader から最後に RPC を受け取ってから election timeout と呼ばれる時間が経過するまでに新たな RPC が届かなければ、クラスター内に leader が存在しないと判断し、自らのステータスを candidate に変更し、term をインクリメントした上で、leader election を開始する。複数のノードが同時に candidate になる可能性を下げるため、election timeout はノードごとにランダムで決定される。
立候補：candidate から leader に状態遷移するには、クラスター内の過半数のノードから支持を受ける必要がある。candidate はまず自分自身に投票し、続いてクラスター内の他のノードに RequestVote RPC を並列で発行する。
投票：candidate から RequestVote RPC を受け取ったノードは、candidate が leader になることを承諾するか否かを応答する。最新のログを持つノードが leader に選ばれるべきなので、RequestVote RPC への応答は、次の二つをともに満たす場合に承諾する。
- candidate 側 term が自身の term 以上（candidate 側の term は RequestVote RPC の引数 term として渡される）
- candidate 側 log 内の最終エントリがローカルの log 最終エントリと同じか、それより新しい（candidate 側の最終エントリ情報は、RequestVote RPC の引数 lastLogTerm および lastLogIndex として渡される）
結果確定：candidate は、次のいずれかになるまで待機し、その後、leader election を終了する。
- 勝利した - クラスター内全ノードの過半数から承諾を得ると勝利となる。ステータスを candidate から leader に変更。その後、他のノードに heartbeat を打つことで新たな leader election の発生を防ぐ
- 他に leader が現れた - candidate が他のノードから AppendEntries RPC を受け取った場合、他に leader が存在することを示す。ステータスを candidate から follower に変更。ただし、相手の term が自身の term より小さい場合は、拒否する
- 勝者がいないまま期間が過ぎた - candidate は leader election 開始時にも、ランダムな election timeout を開始している。過半数の承諾を得ないままタイムアウトを迎えると、term をインクリメントして新たな leader election を開始する

Log Replication のフロー

複製依頼：クライアントからリクエストを受けた leader は、その内容を新たなエントリとしてローカルの log に追加する。続いて、クラスター内の他のノードに AppendEntries RPC を発行してエントリの複製を要求する。ネットワーク障害やノードのクラッシュなどで複製要求に失敗したら、同ノードに対し AppendEntries RPC を繰り返し送り続ける。
複製：AppendEntries RPC を受け取ったノードは、エントリをローカルの log に追加し、leader に応答を返す。この時、エントリを追加するには次の条件を満たす必要がある。
- leader 側の term が、自身の term 以上（leader 側の term は、AppendEntries RPC の引数 term として渡される）
- 追加しようとしているエントリの直前のエントリがローカルの log 内に含まれている（直前のエントリの index が、AppendEntries RPC の引数 prevLogIndex として渡される）
条件を満たさない場合、ローカル log にエントリを追加せず、leader にエントリ追加失敗を応答として返す。こうすることで、leader 側が AppendEntries RPC を使ってひとつ古いエントリを通知してくれる。また、追加しようとしているエントリと同じ index を持つエントリがローカルの log に含まれている場合（コンフリクト）、ローカル log 内のそれ以降のエントリを全て削除した上で、新たなエントリを追加する。
コミット（leader）：過半数の応答を受け取った leader は、エントリをローカルの state machine に適用する。これをコミットと言う。
コミット（leader 以外）：leader がコミットしたことを、log replication や heartbeat のために発行された AppendEntries RPC により知った follower は、エントリをローカルの state machine に適用する。AppendEntries RPC には leader が最後にコミットした log エントリの index が引数 leaderCommit として含まれている。これとローカルのコミット index を比較し、leader 側にあわせる。

過半数と耐障害性

以上のように、leader election、log replication ともにクラスタ内全ノードの過半数からの承諾を必要としています。こうすることで、例えばネットワークが分断されてスプリットブレインの状況に陥っても、過半数を満たす側のグループだけを機能させることが可能となります。過半数に満たない側のグループはコミットすることも、リーダーを選ぶことも出来なくなるからです。

そしてようやく冒頭の疑問に戻るわけです。

クラスター内のノード数が 2 の場合を考えてみましょう。このケースでは過半数は 2 になるので、1 台がクラッシュすると過半数が成立しなくなり、クラスターは機能しなくなります。

etcd の FAQ 上に掲載されている表がわかりやすいので転記します。

Cluster Size	Majority	Failure Tolerance
1	1	0
2	2	0
3	2	1
4	3	1
5	3	2
6	4	2
7	4	3
8	5	3
9	5	4

表内の Cluster Size はクラスター内の全ノード数、Majority は過半数となるノード数、Failure Tolerance は何台のノードの故障にまで耐えられるかを表しています。

Failure Tolerance を見れば明らかですが、Cluster Size が 3 以上でなければ、Failure Tolerance が 0 となってしまいます。これが、"three" の理由でした。

また、表からは、Cluster Size が奇数になるようにノードを追加しなければ、Failure Tolerance に影響を与えないことも見て取れます。

このようにして、etcd の HA 構成は耐障害性（fault tolerance）を向上させています。

最後に

今回の記事では Raft の log compaction の仕組みや、membership changes について触れませんでした。leader election や log replication も含め、Raft の詳細は下記論文にわかりやすく説明されていますので、興味がある方はこちらをご参考ください。

In Search of an Understandable Consensus Algorithm (Extended Version) | Diego Ongaro and John Ousterhout | Stanford University