etcdのraft.tickは何をしているのか

この記事は富士通の有志による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日間に渡り、開催されました。

• CloudNative Days Tokyo 2023

そこでなんと、、、

「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変数がリセットされる