この記事は富士通の有志によるFUJITSU Advent Calendar 2023の21日目の投稿です。
昨日は@koishi_105によるPyATSとSi-Rでした。
Si-Rというルーターに対し、ネットワークテストの自動化ツールであるPyATSを利用してテストの自動化を行った話でした。
とあるテストの工数が200分の1になったとかならないとか。
数字で表現されるとテスト自動化の大切を改めて実感しますよね、、、
そして、「PyATSがSi-Rに対応していないので良い感じに作りました！」はすごいですね。。。
テストの自動化に困っていたら是非読んでみてください。
ところで、
CNDT2023で発表してきました！
CNDT2023はCloudNative Days Tokyo2023の略でクラウドネイティブムーブメントを牽引することを目的としたテックカンファレンスです。今年は12/11と12/12の2日間に渡り、開催されました。
そこでなんと、、、
「etcdとRaftアルゴリズム: Kubernetesコントロールプレーンの信頼性の解剖」というタイトルで発表してきました！🎉
資料も公開しているので、興味があれば見ていただけると嬉しいです。
発表では、Raftのアルゴリズムがetcdでどのように実装されているのかを解説しました。
具体的には、RaftではFollower/Candidate/Leaderなどのstateが定義されていることや、stateの処理としては主にstepXXX関数とtickXXX関数の2種類あることを説明しました。
残念ながら時間の都合上、発表ではstepXXX関数に焦点を当てた解説となっており、tickXXX関数の具体的な処理までは解説できませんでした。
今回は解説しなかったtickXXX関数に焦点を当てたいと思います！
おさらい
今回説明するetcdはv3.5.10を対象に説明していきます。
$ etcd --version
etcd Version: 3.5.10
Git SHA: 0223ca52b
Go Version: go1.21.3
Go OS/Arch: linux/amd64
各stateで実行されるtickXXX関数は以下になります。
- Follower -> tickElection関数
- Candidate -> tickElection関数
- Leader -> tickHeartbeat関数
そして上記の関数はraft構造体のtickフィールドに格納されます。
type raft struct {
// 略
tick func()
// 略
}
Raftなにそれおいしいの？
Raftについての詳細が知りたい場合、「etcdとRaftアルゴリズム: Kubernetesコントロールプレーンの信頼性の解剖」の発表を見ていただけると、ふんわり理解できるかと思います。
実行間隔の定義からtickフィールドの実行まで
まず、実行間隔はectdコマンドの--heartbeat-intervalオプションで指定することができ、デフォルトは100ミリセカンドになります。
$ etcd --help
...
--heartbeat-interval '100'
Time (in milliseconds) of a heartbeat interval.
...
hertbeat-intervalで指定したミリセカンドのTickerが作成され、Tick関数が実行され、raft構造体のtickXXX関数が起動されます。
// Tick advances the internal logical clock by a single tick.
func (rn *RawNode) Tick() {
rn.raft.tick()
}
実行間隔の定義からRawNodeのTick関数起動まで
説明のためにかなり端折ってますが、正確にはもう少し処理が入っています。
興味があれば処理を追ってみててください。
tickHeartbeat関数
まずはLeaderで実行されるtickheartbeat関数の処理を見ていきます。
func (r *raft) tickHeartbeat() {
r.heartbeatElapsed++
// 略
if r.heartbeatElapsed >= r.heartbeatTimeout {
r.heartbeatElapsed = 0
r.Step(pb.Message{From: r.id, Type: pb.MsgBeat})
}
}
処理自体はシンプルで、heartbeatElapsed変数をインクリメントしていき、heartbeatTimeoutに達すると自身に対してMsgBeatを発行します。
MsgBeat受信後の動作
LeaderがMsgBeatを受信すると、sendHeartbeat関数が実行され、Leaderが認識している他のNodeにMsgHeartbeatが送付されます。toはLeadertが認識している任意の他のNodeを表現しており、Nodeの数だけsendHeartbeatが実行されます。sendHeartbeatを受け取ったNode側の処理は後述します。
func (r *raft) sendHeartbeat(to uint64, ctx []byte) {
commit := min(r.prs.Progress[to].Match, r.raftLog.committed)
m := pb.Message{
To: to,
Type: pb.MsgHeartbeat,
Commit: commit,
Context: ctx,
}
r.send(m)
}
tickElection関数
次にCandidate/Followerで実行されるtickElection関数の処理を見ていきます。
// tickElection is run by followers and candidates after r.electionTimeout.
func (r *raft) tickElection() {
r.electionElapsed++
if r.promotable() && r.pastElectionTimeout() {
r.electionElapsed = 0
r.Step(pb.Message{From: r.id, Type: pb.MsgHup})
}
}
処理自体はシンプルで、electionElapsedをインクリメントし、if文の条件式でtrueとなれば、MsgHubを自身に対して発行します。MsgHubが発行されると、campaign関数が実行され、選挙がはじまります。
条件式について簡単に説明すると、下記の判定が行われてます。
- promotable()：リーダーになることができるかどうか
- pastElactionTimeout()：electionElapsedがTimeoutに達しているかどうか
electionElapsedの初期化のタイミング
electionElapsedがインクリメントし続けると選挙が始まってしまうため、定期的に初期化が行われます。初期化のタイミングはいろいろあるのですが、その中の1つにFollowerがMsgHeartbeatを受信した時が含まれています。具体的には、下記に示すstepFollower関数のcase pb.Msgheartbeat:で処理されます。
func stepFollower(r *raft, m pb.Message) error {
switch m.Type {
// 略
case pb.MsgHeartbeat:
r.electionElapsed = 0
r.lead = m.From
r.handleHeartbeat(m)
// 略
}
return nil
}
まとめ
- raft構造体のtickフィールドについてみていきました
- tickは定期的に実行される関数であり、Stateとの対応関係は以下になります
- Follower -> tickElection関数
- Candidate -> tickElection関数
- Leader -> tickHeartbeat関数
- tickXXX関数の処理まとめ
- tickHeartbeat関数
- 定期的にMsgHeartbeatを他のNodeに送付する
- tickElection関数
- electionElapsed変数をインクリメントしていき、タイムアウトすると選挙を開始する
- リーダーからMsgHeartbeatを受け取るとelectionElapsed変数がリセットされる
- tickHeartbeat関数