Leader and Followers は、同じデータを複製して持つノードのうち 1 台を Leader に決め、更新を全て Leader が受け付けて残りの Follower へ配る構成です。更新の受け口が 1 台に絞られるため、同じデータへの更新の順序は Leader が決めた 1 つに定まります。ここでは、ノードが停止する故障とネットワークが分断される故障を扱い、誤った値を返す故障（ビザンチン障害）は対象外とします。

パターンの名前は Unmesh Joshi の書籍『Patterns of Distributed Systems』（邦訳『分散システムのためのデザインパターン』）で使われているもので、Martin Fowler のサイトにも Leader and Followers として要約が置かれています。冒頭の一文は「1 台のサーバに、複数のサーバへまたがる複製を統率させる」で、解法の節は「クラスタの中の 1 台を Leader として選ぶ。Leader はクラスタ全体を代表して決定を下し、その決定を他の全サーバへ伝播させる」と述べています。仕組みの説明には Raft を使います。Raft は、複製したログを全ノードで同じ順序に揃えるための合意アルゴリズムで、動作が論文で細部まで規定されています。

登場人物と経路を以下に示します。

  flowchart LR
    C[Client] -- 更新 --> L[Leader]
    L -- 複製 --> F1[Follower 1]
    L -- 複製 --> F2[Follower 2]
    F1 -. 応答 .-> L
    F2 -. 応答 .-> L
    L -- 結果 --> C

上図の Follower は、更新を受け取っても処理せずに Leader へ案内する決まりで、Leader から届いた内容を自分の複製へ反映します。Leader が落ちた場合は、残った Follower の中から次の Leader を選び直します。Leader を務めるノードは入れ替わり、役割は固定されていません。

なぜ Leader が必要なのか

全ノードが対等に更新を受け付ける構成では、同じデータへの更新が別々のノードへ同時に届きます。各ノードは自分が受け取った順に処理してから相手へ複製するので、到着の順序が入れ替わると、追加の併合規則を置かない限り、最終的に残る値がノードごとに食い違います。

2 台が独立に更新を受け付けた場合に何が起きるかを以下に示します。

  sequenceDiagram
    participant C1 as Client 1
    participant A as Node A
    participant B as Node B
    participant C2 as Client 2
    C1->>A: x = 1
    C2->>B: x = 2
    A->>B: 複製 x = 1
    B->>A: 複製 x = 2
    Note over A: 後に届いたのは<br/>x = 2 なので x = 2
    Note over B: 後に届いたのは<br/>x = 1 なので x = 1

上図で問題なのは、どちらのノードも自分の見た順序で正しく処理しており、間違った動作をしていない点です。順序を決める場所がどこにも無いため、正しく動いた結果として値が 2 通りに割れています。後から一方を選び直すには、どちらが後の更新なのかを判定する材料が別に要ります。

クォーラムで読み書きの相手を重ねれば足りるのではないか、と考える方がいるかもしれません。過半数を要求すると、書き込みに関わったノードの集合と読み取りに関わったノードの集合は、必ず 1 台以上を共有します。ただし、共有するノードが 2 つの更新を両方受け取っている事と、どちらが後の更新なのかを判定できる事は別です。数を数えるだけの過半数には、順序を決める規約が含まれていません。

更新の順序を 1 つに決めるには、全ノードが共有できる 1 つの並びを作る仕組みが要ります。Leader and Followers は、その並びを決める役目を Leader へ集約します。更新は必ず Leader を通り、Leader がログへ並べた順序を Follower が複製します。順序を後から復元する仕組みを用意せずに済む点が、この構成の中心にある効果です。

全体の順序として残るのは、候補のうち確定したものだけです。確定していない更新は、次の Leader が持っていなければ切り捨てられます。次の Leader が持っている場合は残り、現在の任期の更新が確定した時点で一緒に確定します。なお、並びを決める役目を 1 台へ固定しない解き方もあります。

Paxos は Leslie Lamport が示した合意アルゴリズムです。同氏の Paxos Made Simple は、合意アルゴリズムを「提案された値のうち 1 つだけが選ばれる事を保証する」ものだと述べています。この保証は固定された Leader を前提とせず、提案番号とクォーラムだけで守られます。同じ論文は、提案を出すノードが複数居ると、互いに大きな番号を出し合って何も選ばれないまま進まなくなる場面を挙げ、安定して前へ進めるには提案を出す役を 1 台に定めるとよいと書いています。その役の選出が失敗しても、1 つの値だけが選ばれるという保証は崩れません。ログの各位置について Paxos を繰り返し、安定した Leader で処理を効率化する構成が、一般に Multi-Paxos と呼ばれます。

仕組み

任期と選出

Leader は固定ではなく、落ちた時に選び直せる必要があります。Raft は時間を任期（term）という単調増加する番号で区切り、1 つの任期に立つ Leader を最大 1 台に制限します。Diego Ongaro と John Ousterhout が 2014 年に発表した Raft の論文は、この性質を Election Safety と呼び、「1 つの任期で選ばれる Leader は最大 1 台」と定義しています。

Follower は Leader から定期的に届く信号を待ちます。信号が一定時間届かなければ、Leader が落ちたと判断して自分が Candidate になり、任期を 1 つ増やして他のノードへ投票を求めます。クラスタの全構成ノードのうち過半数から票を集めたノードが、その任期の Leader になります。数えるのは応答があったノードの中の過半数ではなく、構成に含まれる全ノードの過半数です。信号そのものはハートビートで、Raft では中身が空の複製要求を流用しています。

役割の遷移を以下に示します。

  stateDiagram-v2
    [*] --> Follower
    Follower --> Candidate: 信号が届かないまま待ち時間を経過
    Candidate --> Leader: 過半数の票を獲得
    Candidate --> Candidate: 票が割れたので任期を増やして再挑戦
    Candidate --> Follower: 自分の任期以上の Leader から複製要求
    Leader --> Follower: より新しい任期を検知

上図で Candidate から Candidate へ戻る経路は、複数のノードが同時に Candidate になって票が割れた場合を表します。全ノードが同じ待ち時間を使うと、票の割れが繰り返されます。そのため、Raft は待ち時間をランダムな幅で散らし、選出を始めるたびに引き直します。Leader から Follower へ戻る経路は、自分より新しい任期を検知した時に通ります。分断から復帰した旧 Leader がここを通るので、「古い Leader を締め出す」で改めて扱います。

投票を受け取った側の処理は短く書けます。Leader が 2 台立つのを防いでいるのは、1 つの任期で 2 票を投じない事と、当選に過半数を要求する事の組み合わせです。過半数の集合はどの 2 つを取っても 1 台以上を共有するので、共有するノードが 1 票しか出さなければ、同じ任期に 2 台が過半数へ届く事はありません。

// handleRequestVote は、Candidate から届いた投票要求を処理します。
// ログの新しさの検査（Raft 論文 5.4 節）は省略しています。
func (n *node) handleRequestVote(term int, candidateID string) bool {
	if term < n.currentTerm {
		return false // 古い任期からの要求は拒否する
	}
	if term > n.currentTerm {
		// 新しい任期を見たら、投票の記録を捨てて Follower へ戻る
		n.currentTerm = term
		n.votedFor = ""
		n.role = roleFollower
	}
	if n.votedFor != "" && n.votedFor != candidateID {
		return false // 同じ任期で 2 台へ投票しない
	}
	n.votedFor = candidateID
	return true
}

上のコードは currentTerm と votedFor をメモリ上で書き換えているだけで、実装としては不足しています。Raft は、この 2 つとログを RPC（Remote Procedure Call、遠隔手続き呼び出し）へ応答する前に安定ストレージへ書く事を要求しています。投票した直後に再起動して votedFor を失うと、同じ任期でもう 1 台へ投票してしまい、Leader が 2 台立ちます。

省略したログの新しさの検査は、確定済みの更新を守るために効いています。Raft は、自分のログが Candidate より新しいノードに投票を拒否させます。確定済みのエントリは過半数が持っており、票を集めるにも過半数が要るので、その 2 つは必ず重なります。確定済みのエントリを持たないノードは、重なったノードに拒否されて Leader になれません。重なりが効く理屈はクォーラムと同じです。

期間を区切って権利を与える点は、Lease と同じ発想です。違いは期限の決め方にあり、Lease は時間の経過で切れるのに対し、任期はより新しい任期の出現で切れます。任期は時計を参照しないので、ノード間で時刻を合わせる必要がありません。その代わり、誰かが新しい任期を始めるまで古い Leader は自分の失効を知りません。

時刻を合わせずに済むのは安全性の話で、可用性はタイミングに依存します。Raft は、信号が往復する時間・選出の待ち時間・ノードが故障する平均間隔が、この順に十分な差で並ぶ事を前提にしています。待ち時間が往復の時間に近いと、生きている Leader が居るのに選出が始まり、更新が進まなくなります。

更新の複製と確定

Client の更新を受け取った Leader は、まず自分のログの末尾へ追記し、続けて同じ内容を Follower へ送ります。ログは WAL（Write-Ahead Log、書き込み先行ログ）と同じ追記型の列で、Leader が決めた順序をそのまま保持します。追記した 1 件をエントリと呼びます。現在の任期で作られたエントリが過半数のノードへ複製された時点で、Leader はそのエントリを確定（commit）させます。過去の任期のエントリは、複製された数だけを根拠に確定させません。確定は実行と同じではありません。Leader は確定したエントリを自分の状態機械（state machine、ログのコマンドを順に適用して状態を作る部分）へ適用し、その実行結果を Client へ返します。

追記しかしないのは Leader のログだけです。Follower のログは Leader のものと突き合わせられ、食い違う位置から後ろが削られます。Raft は、Leader が追記しかしない性質を Leader Append-Only と呼び、「Leader は自分のログのエントリを上書きも削除もせず、追記だけを行う」と定義しています。

確定までの往復を以下に示します。

  sequenceDiagram
    participant C as Client
    participant L as Leader
    participant F1 as Follower 1
    participant F2 as Follower 2
    C->>L: x = 1
    L->>L: 自分のログへ追記
    L->>F1: 複製要求
    L->>F2: 複製要求
    F1-->>L: 受け取った
    Note over L,F1: Leader 自身と合わせて<br/>2 台なので過半数に到達
    L->>L: 確定して状態機械へ適用
    L-->>C: 実行結果
    F2-->>L: 受け取った（遅れて到着）

上図で Leader が Client へ応答したのは、Follower 2 の応答が届く前です。全ノードの応答を待たないため、1 台が遅れていても更新は進みます。遅れた Follower は、後から届いた分を自分のログへ追記して追い付きます。

Leader は、Follower ごとに「どこまで複製できたか」の位置を matchIndex として持ち、確定済みの末尾を commitIndex として持ちます。確定の判定は、matchIndex を数えて過半数に届いた位置まで commitIndex を進める処理になります。

// advanceCommitIndex は、過半数へ複製できた位置まで commitIndex を進めます。
// Leader を務めているノードだけが呼びます。
// n.log は Raft 論文に合わせて添字 1 から使い、log[0] は番兵です。
// commitIndex の初期値 0 は、まだ何も確定していない事を表します。
func (n *node) advanceCommitIndex() {
	total := len(n.matchIndex) + 1 // Follower の数と、Leader 自身の 1 台
	for i := len(n.log) - 1; i > n.commitIndex; i-- {
		if n.log[i].Term != n.currentTerm {
			continue // 過去の任期のエントリは、応答数だけでは確定させない
		}
		agreed := 1 // Leader は自分のログへ追記済み
		for _, m := range n.matchIndex {
			if m >= i {
				agreed++
			}
		}
		if agreed*2 > total {
			n.commitIndex = i
			return
		}
	}
}

注意点として、現在の任期で作られたエントリだけを確定させる条件が入っています。Raft 論文の Figure 2 は確定の規則を「N > commitIndex かつ過半数の matchIndex[i] >= N かつ log[N].term == currentTerm を満たす N があれば commitIndex = N とする」と規定しており、log[N].term == currentTerm がこの条件にあたります。過去の任期のエントリを応答数だけで確定させると、後から別の内容で上書きされる場合があるためです。

古い Leader を締め出す

ネットワークが分断されると、Leader が生きているのに Follower がその信号を受け取れない状態になります。多数派（過半数が残った側）のノードは新しい Leader を選び、少数派に取り残された旧 Leader は自分が Leader のつもりで動き続けます。1 台に集約したはずの更新の受け口が、一時的に 2 台へ増えます。

分断が起きてから旧 Leader が締め出されるまでを以下に示します。

  sequenceDiagram
    participant A as Node A（任期 5 の Leader）
    participant B as Node B
    participant C as Node C
    Note over A,C: 分断が発生し Node A が孤立
    A->>B: 複製要求（任期 5）
    Note over B: 届かない
    B->>C: 投票を要求（任期 6）
    C-->>B: 投票する
    Note over B,C: Node B が任期 6 の Leader へ
    Note over A,C: 分断が解消
    A->>B: 複製要求（任期 5）
    B-->>A: 拒否（現在の任期は 6）
    Note over A: 任期 6 を見て<br/>Follower へ戻る

上図の Node A は、拒否の応答に含まれる任期番号を見て、初めて自分が交代させられた事を知ります。番号の大小だけで新旧を判定しており、時計は参照していません。権利を渡すたびに大きくなる番号で古い操作を拒否する点は、Lease の fencing token と同じ発想です。

分断されている間、Node A が更新を確定させる事はありません。確定には過半数の応答が要り、少数派は定義上その数に届かないためです。確定していない更新なので、Client へ完了を返してもいません。分断が解消すると、Node A のログは任期 6 の Leader のものと突き合わせられ、食い違う位置から後ろが削られます。削られるのは衝突した範囲だけで、新しい Leader のログと一致している部分はそのまま残ります。

締め出しは、複製要求を受け取ったノードの数行で成立します。

// handleAppendEntries は、Leader から届いた複製要求を処理します。
// ログの整合性検査と追記（Raft 論文 5.3 節）は省略しています。
func (n *node) handleAppendEntries(args appendEntriesArgs) appendEntriesReply {
	if args.Term < n.currentTerm {
		// 分断から復帰した旧 Leader は、ここで弾かれる。
		// 応答に自分の任期を載せるので、旧 Leader は交代を知る
		return appendEntriesReply{Term: n.currentTerm, Success: false}
	}
	if args.Term > n.currentTerm {
		n.currentTerm = args.Term
		n.votedFor = ""
	}
	n.role = roleFollower
	n.leaderID = args.LeaderID // Client を現在の Leader へ案内するために覚える
	return appendEntriesReply{Term: n.currentTerm, Success: true}
}

ここまでのコードのレシーバを node で揃えているのは、1 台のノードが Follower・Candidate・Leader を務め分けるためです。役割は role フィールドで表し、より新しい任期を見たノードは、それまでの役割にかかわらず Follower へ戻ります。

読み取りをどこへ流すか

読み取りを Follower へ分散させると、Leader の負荷は下がります。その代わり、確定した更新がまだ届いていない Follower は古い値を返します。更新の直後に自分の書いた値を読み返す用途では、この遅れが表に出ます。

常に最新の値が要る読み取りは、Leader を経由させます。Raft は、そのために 2 つの手順を要求しています（論文 8 節）。1 つ目は、Leader が就任した直後に自分の任期の空エントリを確定させる事です。advanceCommitIndex は現在の任期のエントリしか確定させないため、空エントリが無いと、就任した Leader は前任者が確定させた位置を把握できません。

2 つ目は、読み取りに応答する前に過半数とハートビートを交換する事です。交代させられた事に気付いていない旧 Leader が古い値を返す可能性は、ここで消えます。新しい Leader が既に立っていれば、過半数のうち少なくとも 1 台が新しい任期を返します。古い任期のまま過半数から応答が揃えば、自分がまだ Leader だと確かめられます。

論文は 2 つ目の代替として、ハートビートを Lease のように扱う方法も挙げています。読み取りのたびに過半数へ問い合わせずに済む代わりに、読み取りの安全性だけがタイミングに依存し、ノード間の時計のずれに上限がある事を仮定します。任期の比較やログの複製そのものが時計に依存するわけではありません。

ここまでの厳密さが要らない読み取りであれば、Follower へ流して構いません。集計や一覧の表示のように、数秒古い値でも判断が変わらない用途が候補になります。

利点

  • 更新の順序が Leader の受け付け順に定まり、順序を後から復元する仕組みが要らない
  • 過半数の応答で確定するため、一部のノードが遅れても更新が進む
  • Follower は Leader の内容を写すだけなので、複製の処理が単純になる
  • Leader が落ちても、過半数のノードが残っていれば選び直して処理を続けられる
  • Raft のように任期の番号で新旧を判定する実装なら、時計を合わせずに古い Leader を排除できる

欠点

以下は、更新の順序を 1 台で決める事を優先した結果として現れる制約です。

  • 更新が全て Leader を通るため、書き込みの性能が Leader 1 台の性能で頭打ちになる
  • Leader が落ちてから次が決まるまで、更新を受け付けられない時間が生じる
  • 選出の待ち時間を短くすると誤検知による交代が増え、長くすると復旧が遅れる
  • 拠点をまたぐ構成では、確定のたびに Leader と過半数の間の往復の時間が加わる
  • Follower から読むと、確定済みの更新がまだ届いていない値が返る場合がある

適さないケース

  • 書き込みが多く、1 台では捌けないワークロード。データを分割して Leader を複数立てる構成を検討する
  • 分断中も両側で更新を受け付けたいシステム。CRDT のような、後から併合できるデータ型を検討する
  • 数百台のノードを 1 つの合意グループへ参加させる構成。1 つのグループは数台に絞るのが前提で、システム全体の台数が多い事自体は問題になりません。規模を広げたい場合は、データを分割して小さなグループを複数立てます
  • 更新が稀で、1 台の停止による短い中断を許容できるシステム

CRDT（Conflict-free Replicated Data Type）とは、複数のノードが独立に更新しても、後から併合すれば必ず同じ結果へ収束するように作ったデータ型です。順序を決める代わりに、順序が違っても同じ結果になる演算だけを許す方針だと考えられます。扱えるデータの形が限られるため、任意の更新を順序付けたい用途の代わりにはなりません。

似た構成との比較

更新をどこで受けて、どう 1 つに揃えるかという軸で並べます。

Leader and FollowersCRDT による複製単一ノード
更新の受け口Leader複数のノードに置けるそのノード
全体の更新順序Leader が作る原則として要らないそのノードが作る
衝突の扱いLeader のログの順で決まるデータ型の併合規則で収束させる衝突しない
分断中の更新少数派では確定できない構成次第で両側から更新できる繋がる側だけ
向いている更新順序と一意性が要るもの併合できるもの冗長化が要らないもの

真ん中の列を CRDT に絞ったのは、全ノードで更新を受け付けるという一点では性質が決まらないためです。並べた軸も、更新をどう受けてどう揃えるかという意味の話に限りました。障害耐性・書き込みの性能・どのノードがどこまでのデータを持つかは、複製の置き方や配送の仕組みで決まるので、CRDT というデータ型を選んだだけでは定まりません。

Leader and Followers を選ぶ判断は、更新の性能と順序のどちらを取るかに寄ります。順序を諦めれば書き込みの受け口を増やせるので、併合できるデータだけを扱うと決められる場面では、CRDT による複製の方が素直です。決められない場面では、更新を 1 台へ集約する方が扱いやすいと考えられます。