Raft

Raftは状態機械の複製に使用されます：複数のノードが一連のコマンドに対して整合されたコミット済み順序を形成し、その後、決定論的な状態遷移を同じ順序で実行します。Raftが許容するのは、プロトコルの仮定内のダウン、再起動、およびネットワークの異常であり、任意の悪意あるノードではありません。

学習する際は、以下の3つの事実を明確に区別してください：ログがすでにノードに保存されていること、ログがプロトコルによってコミットされていること、コマンドが状態機械に適用されていることです。これら3つの時点は通常異なります。Raftは、コミット済み履歴が後の正当なリーダーによって書き換えられないことを保証し、未コミットのテールが一時的に分岐することを許容し、回復時に置き換えられます。

任期と役割：新鮮さは物理時間ではない

term（任期）は単調増加する論理任期番号です。Follower（フォロワー）は選挙タイムアウト後にCandidate（候補者）になり、termを増加させて投票を開始します；設定で要求された過半数の票を獲得するとLeader（リーダー）になります。ランダムなタイムアウトは同時競争の確率を低下させ、1回の選挙での成功を保証するものではなく、すべてのネットワークに適用可能な固定ミリ秒数もありません。

ノードがより高いtermのプロトコルメッセージを受信すると、任期を更新してフォロワーに戻ります。分離された古いリーダーは、そのメッセージを直ちに受信しない可能性があり、まだ在任中であると見なしているかもしれません。安全性は、すべてのノードが誰がリーダーであるかを直ちに知ることに依存するのではなく、必要なquorum（過半数）を取得して新しい正当なコミットを完了できないことに依存します。外部リソースへのアクセスには、プロセス内の役割変数だけに頼らず、適切なフェンシング（排他制御）も必要です。

どの状態を保持しなければならないか

永続状態が変更される際、その変更を依存する成功応答の前に永続化要件を満たす必要があります；ステートレスなハートビートごとに個別にfsyncを行う必要があるわけではありません。状態機械が結果をすでに永続化している場合、回復時に該当するコマンドを盲目的に二度実行してはなりません。

選挙：一票一票だけでは不十分

候補者は末尾ログの (lastLogTerm,lastLogIndex) を送信します。投票者は任期と投票条件が満たされる際に、候補者のログが少なくとも自分自身と同じくらい新しいことを確認する必要があります：まず最後のログのtermを比較し、termが同じ場合はindexを比較します。ログの長さだけを見れば十分ではありません。より長い古い任期のテールは、必ずしも資格があるとは限りません。

同じ任期では、各ノードは最大1つの候補者に投票します。2つの過半数集合は交差するため、同じ任期内で正当な過半数票を獲得したリーダーが2人存在することはありません。異なる任期にまたがるコミット済みログの保持については、ログの一致、選挙制限、およびコミットルールを組み合わせて証明する必要があります。「ログの更新」を「必ず古いエントリを含む」と直接見なしてはいけません。

ログ複製：まず共通接頭辞を見つける

リーダーのAppendEntriesは、直前のログのindexとtermを伴います。フォロワーは、その接頭辞のチェックが通過した場合にのみ、後のエントリを受信します；同じindexで異なるtermの競合に遭遇すると、競合エントリとその後のテールを削除し、新しい内容を追加します。

拒否されると、リーダーはnextIndexを調整して共通接頭辞を再検索します。実装では、競合するtermなどの情報を使用して巻き戻しを加速できます。短いハートビートを受信するたびにフォロワーを切り詰めてはいけません：エントリの競合がない場合、メッセージに特定のテールが含まれていないからといって、それを削除する理由にはなりません。

ログの一致性質は、2つのログが同じindexで同じtermを持つ場合、それ以前の接頭辞が一致するというものです。これにより、リーダーは短い接頭辞チェックで段階的に整合されたログを構築でき、履歴全体を毎回比較する必要がありません。

なぜ空のハートビートでテールを勝手に削除してはいけないか

以下は、AppendEntriesのログとコミット位置の部分のみをシミュレートします。リクエストの任期とリーダーの身元はプロトコルチェックを通過したと仮定します。ログは (term, command) で表され、位置0にはシーント（番兵）を置きます。選挙、永続化、またはスナップショット後のインデックス変換の実装は行いません。

def append_entries(log, committed, prev_index, prev_term, entries, leader_commit):
    if not 0 <= prev_index < len(log) or log[prev_index][0] != prev_term:
        return False, list(log), committed
    updated = list(log)
    for index, entry in enumerate(entries, start=prev_index + 1):
        if index < len(updated) and updated[index][0] != entry[0]:
            if index <= committed:
                raise ValueError("正当なRaftの履歴は、コミット済み接頭辞に競合してはならない")
            del updated[index:]
        if index == len(updated):
            updated.append(entry)
        elif updated[index] != entry:
            raise ValueError("同じindex、同じtermだが異なるコマンドは、入力仮定に違反する")
    matched_end = prev_index + len(entries)
    new_commit = max(committed, min(leader_commit, matched_end))
    return True, updated, new_commit

log = [(0, "sentinel"), (1, "a"), (2, "b"), (2, "c"), (2, "d")]
ok, same, commit = append_entries(log, 1, 2, 2, [], 4)
assert ok and same == log and commit == 2
ok, fixed, commit = append_entries(log, 2, 2, 2, [(3, "new-c")], 3)
assert ok and fixed == log[:3] + [(3, "new-c")] and commit == 3
assert append_entries(fixed, 3, 2, 2, [(3, "new-c")], 3) == (True, fixed, 3)
assert append_entries(log, 2, 2, 99, [], 4) == (False, log, 2)

最初の呼び出しは、位置2の接頭辞が一致していることを証明するだけで、メッセージに3や4が含まれていないからといってそれらを削除することはできませんし、フォロワーのローカルに3や4がちょうどあるからといって、コミットを4に進めることもできません。2回目は位置3とterm 3を伴い、ローカルのterm 2と実際に競合するため、3とその後の古いテールを削除し、新しいエントリを追加します。

2回目のリクエストを繰り返しても、2番目のコマンドが追加されるわけではありません。実装では、「すでに存在する一致エントリ」「新しいエントリ」「競合エントリ」を区別する必要があり、受信した全体のサフィックスをローカルのログに無条件で上書きしてはいけません。上記の処理は、Raft Figure 2のAppendEntriesルールに対応しています。

コミット：なぜ現在の任期を見なければならないか

基本的な過半数設定では、リーダーはNでcommitIndexを進めることができます。条件には、Nが現在のコミット位置より大きいこと、少なくとも過半数のノードでmatchIndexがN以上であること、そして log[N].term == currentTerm であることが含まれます。Nをコミットすることは、その前のログ接頭辞も同時にコミットします。

古い任期のエントリが一時的に過半数のノードに存在しても、現在見ているレプリカ数だけで直接コミットを宣言することはできません。理由は、投票は末尾のtermを優先して比較するためです。より高い任期のテールを持つ別の候補者は、まだ実行中である可能性があり、未コミットのエントリを上書きして後の選挙に勝つ可能性があります。現在の任期のエントリが過半数に複製されることは、コミット接頭辞を安全に進めるために必要な追加条件を提供します。

実際に読み取り可能な例：新しいリーダーの現在のtermは7で、index 40、term 6のエントリを継承します。index 41にterm 7のno-opを書き込み、安全にコミットした後、index 40は接頭辞と一緒にコミットされます。古いコマンドを新しいtermに置き換えて再実行する必要はありません。厳密な証明と反例については、Raft論文の第5.4節とFigure 8を参照してください。

過半数の位置が40に達しても、39までしかコミットできない場合がある

5ノードのリーダーの現在の任期は7で、ログ40は任期6に属し、41は任期7のno-opです。コミットは39までです。複製進捗が [41,40,40,39,38] の場合、40には3つのレプリカがありますが、現在の任期の条件はまだ満たされていません。41も過半数に到達してから、40と一緒に進めることができます。

def advance_commit(committed, current_term, terms, matches):
    majority = len(matches) // 2 + 1
    eligible = [index for index, term in terms.items()
                if index > committed and term == current_term
                and sum(position >= index for position in matches) >= majority]
    return max([committed] + eligible)

terms = {39: 6, 40: 6, 41: 7}
assert advance_commit(39, 7, terms, [41, 40, 40, 39, 38]) == 39
assert advance_commit(39, 7, terms, [41, 41, 41, 39, 38]) == 41
assert advance_commit(41, 7, terms, [41, 41, 41, 39, 38]) == 41
assert (7, 10) > (6, 100)  # 選挙時にはまず末尾のtermを比較し、ログの長さではない

ここでmatchesにはリーダー自身が含まれており、同じ固定された5ノード設定から来ており、ノードの欠落や重複ACKを複数のレプリカとして扱っていません。メンバー変更中である場合、固定された過半数の人数の公式をそのまま適用することはできず、現在の設定のquorumルールを使用する必要があります。このフィルタリング関数は、進める条件を示すものであり、完全な安全性証明を担うものではありません。

複製は過半数に達したが、コミットラインがまだ動かないのはなぜ？

複製の証拠をコミット条件の隣に描画することで、「レプリカが十分にある」ことを完全な証明と誤解するのを避けることができます。以下のスライダーは、独立した複製進捗のスナップショットを1つ選択し、変更時にコミット済みの39から再計算します。これは、実際のノードがすでに確認された永続ログを失ったことを示すものではありません。適用ボタンを押すと、個別に示されます：コミット可能な接頭辞が拡大した後、状態機械はこれらのコマンドを実行する必要があります。

$$\#\{i:{\mathrm{matchIndex}}_i\ge n\}\ge 3\wedge \mathrm{term}(n)=7$$

適用とクライアントのリトライ

ノードは、コミット済み順序でlastAppliedを進めます。状態機械の実行は決定論的である必要があります：乱数、現在時刻、および外部クエリの結果が状態に影響を与える場合、明確なプロトコルを通じてコマンドまたは整合された入力に組み込む必要があり、各レプリカが自由に異なる値を取得することはできません。

Raftのログが安全であっても、クライアントはコマンドがすでにコミットされた後に応答を失い、同じビジネス操作を再コミットする可能性があります。状態機械の複製では、通常、リクエストIDと結果の重複排除が必要です。Raft自体は、2つの重複するビジネスリクエストを自動的に同じコマンドとは見なしません。

線形整合性読み取り：リーダーであると信じているだけでは不十分

分離された古いリーダーは、古くなった状態を持っている可能性があります。安全に読み取るためには、今回の読み取りが依存するリーダー権限がまだ有効であることを確認し、状態機械が対応する安全なコミット位置に適用されるのを待つ必要があります。

quorumベースの読み取り方式は、通常、リーダーが現在の任期のコミット境界を確認した後、過半数のノードに連絡して読み取りバリアを確立し、ローカルのlastAppliedが安全な位置に達するのを待ちます。リース読み取りは一部の通信を削減できますが、その正しさには、プロトコルで規定された時間とリースの仮定が必要です。詳細は実際のシステムを参照してください。

スナップショット：状態とそれに対応する履歴位置を保持する

スナップショットは、ある適用済み接頭辞の状態と、lastIncludedIndex、lastIncludedTerm、および回復に必要な設定などのメタデータを記録します。スナップショットが確実に保存されて初めて、プロトコルに従って対応する古いログを回収できます。

遅れたフォロワーは、必要なログがすでに回収されている場合、InstallSnapshotによって接頭辞を回復し、後のログを追跡できます。インストールによってノードが適用済み状態よりも古いビューに巻き戻ることはできません。後のログを保持するかどうかは、境界が一致しているかどうかを確認する必要があります。スナップショットは、変化しているデータディレクトリを任意にコピーすることではありません。

メンバー変更：quorumの定義も変化している

古い集合を直接新しい集合に切り替えると、互いに交差しない過半数がそれぞれ行動する可能性があります。Joint consensus（合意形成）は、古い集合の過半数と新しい集合の過半数の両方を同時に満たすことを要求する結合設定を使用し、新しい設定に遷移します。これは、2つのグループのノードを結合して、総人数の過半数だけを採取することではありません。

もう一つの実装は、変更を安全な単一メンバーステップに制限し、設定がいつ有効になるかを規定します。具体的な実装は異なるインターフェースをサポートする場合があります。「単一ノードの変更」が見えただけで、その適用順序と回復ルールをスキープしてはいけません。新しいレプリカの追加も、quorumの閾値をすぐに引き上げるデータのない新しい投票者を避けるため、通常、投票しないlearnerとして追跡します。

結合設定は5人中から3人を選ぶことではない

古い設定 {A,B,C}、新しい設定 {C,D,E}。古い過半数 {A,B} と新しい過半数 {D,E} は完全に交差しない可能性があります。「2つの設定それぞれが過半数を使用する」だけでは不十分であることを示しています。結合フェーズでは、1つの決定が同時に、古い設定から少なくとも2つ、新しい設定から少なくとも2つのノードの確認を得ることを要求します。

from itertools import combinations
old, new = set("ABC"), set("CDE")

def majority(acks, members):
    return len(acks & members) >= len(members) // 2 + 1

def joint(acks):
    return majority(acks, old) and majority(acks, new)

assert majority(set("ABC"), old | new)  # 5人のうちの3人
assert not joint(set("ABC"))  # 新しい設定ではCのみ、1つの確認では不十分
assert joint(set("ACD"))  # 古い設定でA、C；新しい設定でC、D
assert not (set("AB") & set("DE"))
all_sets = [set(nodes) for size in range(6) for nodes in combinations("ABCDE", size)]
valid = [acks for acks in all_sets if joint(acks)]
assert all(a & b for a in valid for b in valid)

共有ノードCの確認は、両方に同時にカウントできますが、旧側に余分にあるA、Bの確認を、新側のD、Eとして扱うことはできません。このルールは可用性に影響します：旧グループが過半数を構成でき、新グループができない場合、結合フェーズでは結合quorumを必要とする決定を完了できません。設定エントリがいつ有効になり、どのように回復するかは、完全な再設定プロトコルに従う必要があり、単なる多数判断関数の置換では不十分です。Raftメンバー変更

5票のうち3票あっても、まだ不十分な場合がある

結合条件は、2つの述語の「AND」であり、ノードの和集合を新しい過半数問題として扱うことではありません。A、B、Cを選択すると、合計3票ありますが、新しい設定ではCのみが1票です。Dを追加して初めて、両側を同時に満たします。逆に、C、D、Eも古い設定の1票が不足しています。元の静的図は設定関係を示していますが、以下ではオプションの確認集合を使用してこれらの境界を検証します。

$$|A\cap C_{old}|\ge 2\wedge |A\cap C_{new}|\ge 2$$

チェックリスト：省略できない制限事項

• 過半数の永続化に基づく直接コミット判断には、現在の任期条件を満たす必要があります。
• 選挙では、末尾のtermを比較し、次にindexを比較します。
• リーダーの身元だけでは、ローカル読み取りが十分新しいことを独自に証明することはできません。
• スナップショット、重複排除状態、およびメンバー設定は、完全な回復の一部です。
• 安全性は通信の異常時に維持できますが、継続的な進行には、通信可能なquorumと適切な時間条件が必要です。

参考

• In Search of an Understandable Consensus Algorithm。
• Raftプロジェクトと論文の入口。

Keywords: Raft, term, election, log matching, commitIndex, ReadIndex, snapshot, joint consensus