---
title: [CNDT2023] etcdとRaftアルゴリズム: Kubernetes Control Planeの信頼性の解剖
tags:  #tech  
author: [Shuhei Kawamura](https://convert.docswell.com/user/shukawam)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/DEYVWYW9EM.jpg?width=480
description: 2023/12/11 に行われた CNDT2023 で使用したスライドです
published: December 11, 23
canonical: https://convert.docswell.com/s/shukawam/KW1YL4-etcd-raft
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/DEYVWYW9EM.jpg)

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


# Page. 2

![Page Image](https://bcdn.docswell.com/page/VJNM9P9D78.jpg)

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


# Page. 3

![Page Image](https://bcdn.docswell.com/page/YE9N2328E3.jpg)

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


# Page. 4

![Page Image](https://bcdn.docswell.com/page/GE8K5M5Z7D.jpg)

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


# Page. 5

![Page Image](https://bcdn.docswell.com/page/LELZY3Y1JR.jpg)

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


# Page. 6

![Page Image](https://bcdn.docswell.com/page/4JMVNDN5JW.jpg)

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


# Page. 7

![Page Image](https://bcdn.docswell.com/page/PJR2D4DZE9.jpg)

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


# Page. 8

![Page Image](https://bcdn.docswell.com/page/PEXD12117X.jpg)

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


# Page. 9

![Page Image](https://bcdn.docswell.com/page/3EKX2M2M7D.jpg)

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


# Page. 10

![Page Image](https://bcdn.docswell.com/page/L7354Y42E5.jpg)

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


# Page. 11

![Page Image](https://bcdn.docswell.com/page/87DDQ5Q67G.jpg)

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


# Page. 12

![Page Image](https://bcdn.docswell.com/page/VJPXLGGZ78.jpg)

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


# Page. 13

![Page Image](https://bcdn.docswell.com/page/2EVLQ66MJQ.jpg)

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


# Page. 14

![Page Image](https://bcdn.docswell.com/page/57GXWNNXEL.jpg)

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


# Page. 15

![Page Image](https://bcdn.docswell.com/page/4EQ83QQ5JP.jpg)

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


# Page. 16

![Page Image](https://bcdn.docswell.com/page/KJ421NNVE1.jpg)

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


# Page. 17

![Page Image](https://bcdn.docswell.com/page/LE1MG5547G.jpg)

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


# Page. 18

![Page Image](https://bcdn.docswell.com/page/GEW3K55ZE2.jpg)

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


# Page. 19

![Page Image](https://bcdn.docswell.com/page/47ZVZNNLE3.jpg)

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


# Page. 20

![Page Image](https://bcdn.docswell.com/page/YJ65Z88M7V.jpg)

Log replication ﬂow
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


# Page. 21

![Page Image](https://bcdn.docswell.com/page/GJ5YW99QJ4.jpg)

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


# Page. 22

![Page Image](https://bcdn.docswell.com/page/LE354YYZJ5.jpg)

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


# Page. 23

![Page Image](https://bcdn.docswell.com/page/8EDDQ554EG.jpg)

23


# Page. 24

![Page Image](https://bcdn.docswell.com/page/V7PXLGGVE8.jpg)

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


# Page. 25

![Page Image](https://bcdn.docswell.com/page/2JVLQ66R7Q.jpg)

Raftの立ち位置
Write Workﬂow
８：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


# Page. 26

![Page Image](https://bcdn.docswell.com/page/5EGXWNN6JL.jpg)

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


# Page. 27

![Page Image](https://bcdn.docswell.com/page/4JQ83QQ27P.jpg)

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


# Page. 28

![Page Image](https://bcdn.docswell.com/page/K7421NNPJ1.jpg)

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


# Page. 29

![Page Image](https://bcdn.docswell.com/page/LJ1MG55XEG.jpg)

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


# Page. 30

![Page Image](https://bcdn.docswell.com/page/GJW3K55KJ2.jpg)

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


# Page. 31

![Page Image](https://bcdn.docswell.com/page/4EZVZNNNJ3.jpg)

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


# Page. 32

![Page Image](https://bcdn.docswell.com/page/Y765Z889EV.jpg)

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


# Page. 33

![Page Image](https://bcdn.docswell.com/page/G75YW99D74.jpg)

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


# Page. 34

![Page Image](https://bcdn.docswell.com/page/9J2GQ25MJR.jpg)

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


# Page. 35

![Page Image](https://bcdn.docswell.com/page/DEYVWYKPEM.jpg)

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


# Page. 36

![Page Image](https://bcdn.docswell.com/page/VJNM9PRM78.jpg)

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


# Page. 37

![Page Image](https://bcdn.docswell.com/page/YE9N23MWE3.jpg)

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


# Page. 38

![Page Image](https://bcdn.docswell.com/page/GE8K5MLR7D.jpg)

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


# Page. 39

![Page Image](https://bcdn.docswell.com/page/LELZY3L2JR.jpg)

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


# Page. 40

![Page Image](https://bcdn.docswell.com/page/4JMVNDM9JW.jpg)

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


# Page. 41

![Page Image](https://bcdn.docswell.com/page/PJR2D4V9E9.jpg)

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


# Page. 42

![Page Image](https://bcdn.docswell.com/page/PEXD12Z37X.jpg)

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


# Page. 43

![Page Image](https://bcdn.docswell.com/page/3EKX2M8N7D.jpg)

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


# Page. 44

![Page Image](https://bcdn.docswell.com/page/L7354Y2ZE5.jpg)

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


# Page. 45

![Page Image](https://bcdn.docswell.com/page/87DDQ5Z47G.jpg)

Log replication ﬂow
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


# Page. 46

![Page Image](https://bcdn.docswell.com/page/VJPXLGDV78.jpg)

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


# Page. 47

![Page Image](https://bcdn.docswell.com/page/2EVLQ61RJQ.jpg)

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


# Page. 48

![Page Image](https://bcdn.docswell.com/page/57GXWN26EL.jpg)

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


# Page. 49

![Page Image](https://bcdn.docswell.com/page/4EQ83QP2JP.jpg)

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


# Page. 50

![Page Image](https://bcdn.docswell.com/page/KJ421NYPE1.jpg)

FIN
50


