[CNDT2023] etcdとRaftアルゴリズム: Kubernetes Control Planeの信頼性の解剖

etcdとRaftアルゴリズム: Kubernetes Control Planeの信頼性の解剖 @shukawam/@ystkfujii 1

Shuhei Kawamura(X: @shukawam) Job: CSP - Cloud Architect (Cloud Native, AuthNZ, AI/ML) ひとこと: 早く雪山にこもりたい Job: 何でも屋（Terraform/k8s/Golang) ひとこと: 来年のガンダムの映画が楽しみ Yoshitaka Fujii(X: @ystkfujii) 2

はじめに ▪ ▪ ▪ 目標 ▫ RaftとetcdにおけるRaft実装を”完全理解”すること 話すこと ▫ Raftとはなにか ▫ etcdのRaftの実装を読む 話さないこと ▫ etcdのRaft以外の実装 3

Kubernetes Components … Control Plane Node Node 4 参考: https://kubernetes.io/ja/docs/concepts/overview/components

• https://kubernetes.io/ja/docs/concepts/overview/components

Kubernetes Components … Control Plane Node Node 5 参考: https://kubernetes.io/ja/docs/concepts/overview/components

• https://kubernetes.io/ja/docs/concepts/overview/components

What is etcd? ▪ ▪ 分散システムの最も重要なデータのための信頼性の高いKVS ▫ Simple - 明確に定義されたユーザー向けのAPI(gRPC) ▫ Secure - (optional)クライアント証明書認証による自動TLS ▫ Fast - 10,000 writes/secの書き込み ▫ Reliable - Raftを用いた適切な分散 Kubernetesでは全てのクラスター情報の保存場所として利用 6 参考: https://github.com/etcd-io/etcd

• https://github.com/etcd-io/etcd

7 引用: https://github.com/etcd-io/etcd

• https://github.com/etcd-io/etcd

Replicated state machines ▪ ▪ ▪ 分散システムで障害耐性を持つために、同じ状態(State)のマシンを複 製(Replicated)するアプローチのこと 各State machineが実行するべき一連のコマンド（ログ）を複製すること で同じ状態を複製する コンセンサス・アルゴリズムは、複製されたログの一貫性を保つ 8

Replicated state machines 9 引用: https://github.com/etcd-io/etcd

• https://github.com/etcd-io/etcd

What is Raft? ▪ ▪ ▪ コンセンサス・アルゴリズムの一種（Raft, Paxos, …） Paxosと比べ耐障害性や性能を維持しつつ、理解しやすいよう設計 採用されている代表的なサービス／プロダクト ▫ etcd, Kafka(KRaft), CockroachDB, … 10

Raft basics ▪ ▪ ▪ 各ノードは、Leader, Follower, Candidateいずれかの役割を持つ 主な動作は2つだけ ▫ Leader election（リーダー選挙） - RequestVote RPC ▫ Log replication（ログ複製） - AppendEntries RPC Raftクラスタは奇数台(3, 5, 7)のノード構成を推奨 ▫ 偶数台／奇数台の場合で障害許容ノード数は変わらないが、障害 耐性が下がるため ▫ 参考: https://etcd.io/docs/v3.6/faq/#what-is-failure-tolerance 11

• https://etcd.io/docs/v3.6/faq/#what-is-failure-tolerance

Leader election - Term ▪ ▪ 任意の長さに分割された時間のこと Termは選挙で始まり、最大で1つのLeaderがいることを保証する 12 引用: https://raft.github.io/raft.pdf

• https://raft.github.io/raft.pdf

Leader election - State transition ▪ 各ノードは、Leader, Follower, Candidateいずれかの役割を持つ ▫ 起動直後 → Follower ▫ 選挙開始 → Candidate ▫ 選挙勝利 → Leader 13 引用: https://raft.github.io/raft.pdf

• https://raft.github.io/raft.pdf

Leader election flow Candidate Follower Starts election Vote myself F F Leader Increment Term RequestVote RPC voteGranted: true win!! Become Leader AppendEntries RPC 14

Leader election flow Candidate Follower Starts election Vote myself F F Leader Increment Term RequestVote RPC voteGranted: true win!! Become Leader AppendEntries RPC 15

RequestVote RPC Arguments: term 候補者のTerm candidateId 投票をリクエストしている候補者 lastLogIndex 候補者の最後のログエントリのインデックス lastLogTerm 候補者の最後のログエントリのターム Results: term currentTerm、候補者が自分自身を更新する voteGranted 候補者が票を得た場合 true 16 引用: https://raft.github.io/raft.pdf

• https://raft.github.io/raft.pdf

AppendEntries RPC - 1/2 Arguments: term リーダーのTerm leaderId リーダーのID prevLogIndex 新しいエントリの直前のログエントリのインデックス prevLogTerm prevLogIndex のターム entries[] 保存するログエントリ （ハートビートの場合は空 ; 効率のために複数送信も可） leaderCommit リーダーのcommitIndex 17 引用: https://raft.github.io/raft.pdf

• https://raft.github.io/raft.pdf

AppendEntries RPC - 2/2 Results: term currentTerm、リーダーが自分自身を更新する success フォロワーがprevLogIndexとprevLogTermに一致するエント リを含んでいた場合は true 18 引用: https://raft.github.io/raft.pdf

• https://raft.github.io/raft.pdf

Log replication ▪ Leader → FollowerへLogを複製し、各Followerはそれらを順序通りに 処理し、その実行結果をクライアントに返す ▫ Logの複製には、AppendEntries RPCが用いられる 19 引用: https://raft.github.io/raft.pdf

• https://raft.github.io/raft.pdf

Log replication flow Client Leader F F Messages Append to local log entries AppendEntries RPC success: true Success Commit log entries AppendEntries RPC w/ Leader committed index 20

Cluster membership changes オンラインでクラスターの構成変更を実施する上での考慮事項 ▪ ▪ ▪ 移行中の同一タームに2人のリーダーが選出されてはならない Raftでは、2段階の合意プロセスで構成移行を実施 ▫ Phase1. 新旧両方の構成を組み合わせた構成に移行 ▫ Joint Consensus ▫ Phase2. 新しい構成に移行 安全性の観点から、一度に1つのサーバーしかクラスタに追加、削除で きないようにRaftでは制限を設けている 21

Cluster membership changes flow C_old = {A, B, C}, C_new = {A, B, C, D} A(Leader) B AppendEntries RPC Config of {old, new} Phase 1 C_old ↓ C_old, new success: true Phase 2 AppendEntries RPC Config of {new} C D 新旧全てのノードに 構成変更ログを複製 新旧構成ともに 過半数の合意 C_old, new ↓ C_new success: true 新構成から 過半数の同意 22

23

諸注意 ▪ ▪ ▪ 対象のバージョンはetcd v3.5.10 細かい点は省いています コードに修正を加えている部分があります 24

Raftの立ち位置 Write Workflow ８：DBへの書き込み Client EtcdServer BoltDB MVCC １：書き込みリクエスト ６：コミット ７：コミットを通知 Raft Write Ahead Log ２：Raftにフォワード ３：WALに書き込み ３：Peerへ書き込み依頼 ５：書き込み完了報告 EtcdServer Raft Write Ahead Log ４：WALに書き込み（６の後にコミット Raftのコアロジックをライブラリとして分離 ● 受け取ったリクエストに対する処理 ● Peerへの依頼内容 ● コミット管理 など 25 MVCC: Multi-Version Concurrency Control

Basic action ▪ ▪ ▪ etcdのノードがどのStateなのか？ そのStateの処理は何か？ その処理のトリガーは何か？ 26

Basic action: Which state ? ▪ ▪ Nodeの状態はraft構造体のstateで管理されている becomeXXX関数でstateを変更する 27 参照: https://github.com/etcd-io/etcd/blob/v3.5.10/raft/raft.go

Basic action: Processing of state ▪ ▪ 定期実行の処理 -> tickXXX関数 State毎の処理 -> stepXXX関数 28 参照: https://github.com/etcd-io/etcd/blob/v3.5.10/raft/raft.go

Basic action: Processing of state ▪ ▪ 定期実行の処理 -> tickXXX関数 State毎の処理 -> stepXXX関数 29 参照: https://github.com/etcd-io/etcd/blob/v3.5.10/raft/raft.go

Basic action: Message ▪ MessageはNodeへの入力をまとめた もの ▫ ▪ 種類/送付先/エントリーなど MessageTypeの使い分け ▫ ▫ ▫ MsgProp : ログ追加の提案 MsgVote : 投票要求 MsgVoteResp: 投票要求への応答 など 30 参考: https://pkg.go.dev/go.etcd.io/raft/v3#hdr-MessageType

Basic action: Triggers for processing Message Receive Run loop If Ready ? Yes Step Func No If Message Appears Tick Func Send Message To Peers 31 参考: https://github.com/etcd-io/etcd/blob/v3.5.10/raft/node.go#L300

Basic action: Summary becomeLeader becomeCandidate Candidate Follower becomeFollower Leader becomeCandidate Message受信で実行 stepFollower stepCandidate stepLeader 定期的に実行 tickElection tickElection tickHeartbeat 32

Leader election flow Candidate Follower Starts election Vote myself F F Leader Increment Term RequestVote RPC voteGranted: true win!! Become Leader AppendEntries RPC 33

Leader election flow Candidate Follower Starts election Vote myself F F Leader Increment Term RequestVote RPC voteGranted: true win!! Become Leader 34

Leader election: Candidate Side 35 参照: https://github.com/etcd-io/etcd/blob/v3.5.10/raft/raft.go

Leader election: Candidate Side Candidateになる 36 参照: https://github.com/etcd-io/etcd/blob/v3.5.10/raft/raft.go

Leader election: Candidate Side 投票者のIDでループ 37 参照: https://github.com/etcd-io/etcd/blob/v3.5.10/raft/raft.go

Leader election: Candidate Side MsgVoteを投票者に送付 実際には、 msgsにappendされるのみ 38 参照: https://github.com/etcd-io/etcd/blob/v3.5.10/raft/raft.go

Leader election: Candidate Side 投票結果を集計 39 参照: https://github.com/etcd-io/etcd/blob/v3.5.10/raft/raft.go

Leader election: Candidate Side 勝てば Leaderになる 負ければ Followerになる VotePendingの場合は何もしない 40 参照: https://github.com/etcd-io/etcd/blob/v3.5.10/raft/raft.go

Leader election flow Candidate Follower Starts election Vote myself F F Leader Increment Term RequestVote RPC voteGranted: true win!! Become Leader AppendEntries RPC 41

Leader election: Follower side 送付元が投票先の場合 まだ誰にも投票していないかつリーダーが分からない場合 投票する 投票しない デフォルトは StateFuncの実行 42 参照: https://github.com/etcd-io/etcd/blob/v3.5.10/raft/raft.go

Leader election flow Candidate Follower Starts election Vote myself F F Leader Increment Term RequestVote RPC voteGranted: true win!! Become Leader AppendEntries RPC 43

Leader election: bcastAppend Followerのlogの状況を取得 ← toがここの場合 44 引用: https://raft.github.io/raft.pdf

• https://raft.github.io/raft.pdf

Log replication flow Client Leader F F Messages Append to local log entries AppendEntries RPC success: true Success Commit log entries AppendEntries RPC w/ Leader committed index 45

Implementation for log replication 46 参照: https://github.com/etcd-io/etcd/blob/v3.5.10/raft/raft.go

Implementation for log replication Followerに書き込まれた場合、 Leaderに転送 47 参照: https://github.com/etcd-io/etcd/blob/v3.5.10/raft/raft.go

Implementation for log replication Entriesを追加 Peerに送付 LeaderからのMessageでAppend 48 参照: https://github.com/etcd-io/etcd/blob/v3.5.10/raft/raft.go

Summary ▪ ▪ ▪ etcdの信頼性を担っているのはRaft Raftのアルゴリズムについて説明した 具体的な実装をetcdのコードベースで説明した 49

FIN 50