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

この記事は富士通の有志による[FUJITSU Advent Calendar 2023](https://qiita.com/advent-calendar/2023/fujitsu)の21日目の投稿です。
昨日は@koishi_105による[PyATSとSi-R](https://qiita.com/koishi_105/items/1c4eb245795affdb3892)でした。
Si-Rというルーターに対し、ネットワークテストの自動化ツールであるPyATSを利用してテストの自動化を行った話でした。

> とあるテストの工数が200分の1になったとかならないとか。

数字で表現されるとテスト自動化の大切を改めて実感しますよね、、、
そして、「PyATSがSi-Rに対応していないので良い感じに作りました！」はすごいですね。。。

テストの自動化に困っていたら是非読んでみてください。

---

ところで、

## CNDT2023で発表してきました！

CNDT2023はCloudNative Days Tokyo2023の略でクラウドネイティブムーブメントを牽引することを目的としたテックカンファレンスです。今年は12/11と12/12の2日間に渡り、開催されました。

- [CloudNative Days Tokyo 2023](https://event.cloudnativedays.jp/cndt2023)

そこでなんと、、、

「[etcdとRaftアルゴリズム: Kubernetesコントロールプレーンの信頼性の解剖](https://event.cloudnativedays.jp/cndt2023/talks/2029)」というタイトルで発表してきました！🎉

資料も公開しているので、興味があれば見ていただけると嬉しいです。

https://www.docswell.com/s/ystkfujii/ZRX79E-2023-12-11-165757

発表では、Raftのアルゴリズムがetcdでどのように実装されているのかを解説しました。
具体的には、RaftではFollower/Candidate/Leaderなどのstateが定義されていることや、stateの処理としては主にstepXXX関数とtickXXX関数の2種類あることを説明しました。
残念ながら時間の都合上、発表ではstepXXX関数に焦点を当てた解説となっており、tickXXX関数の具体的な処理までは解説できませんでした。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/967883/a5db6669-90e9-72ce-3eed-532b825ac6b3.png)

今回は解説しなかったtickXXX関数に焦点を当てたいと思います！

## おさらい

今回説明するetcdはv3.5.10を対象に説明していきます。

```console
$ 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フィールドに格納されます。

```golang
type raft struct {
    // 略
	tick func()
    // 略
}
```

https://github.com/etcd-io/etcd/blob/v3.5.10/raft/raft.go#L306

:::note info
__Raftなにそれおいしいの？__
Raftについての詳細が知りたい場合、「[etcdとRaftアルゴリズム: Kubernetesコントロールプレーンの信頼性の解剖](https://event.cloudnativedays.jp/cndt2023/talks/2029)」の発表を見ていただけると、ふんわり理解できるかと思います。
:::


## 実行間隔の定義からtickフィールドの実行まで

まず、実行間隔はectdコマンドの`--heartbeat-interval`オプションで指定することができ、デフォルトは100ミリセカンドになります。

```console
$ etcd --help 
...
  --heartbeat-interval '100'
    Time (in milliseconds) of a heartbeat interval.
...
```

hertbeat-intervalで指定したミリセカンドのTickerが作成され、Tick関数が実行され、raft構造体のtickXXX関数が起動されます。

```golang
// Tick advances the internal logical clock by a single tick.
func (rn *RawNode) Tick() {
	rn.raft.tick()
}
```

https://github.com/etcd-io/etcd/blob/v3.5.10/raft/rawnode.go#L58

:::note info
__実行間隔の定義からRawNodeのTick関数起動まで__
説明のためにかなり端折ってますが、正確にはもう少し処理が入っています。
興味があれば処理を追ってみててください。
:::

## tickHeartbeat関数

まずはLeaderで実行されるtickheartbeat関数の処理を見ていきます。

```golang
func (r *raft) tickHeartbeat() {
	r.heartbeatElapsed++

    // 略

	if r.heartbeatElapsed >= r.heartbeatTimeout {
		r.heartbeatElapsed = 0
		r.Step(pb.Message{From: r.id, Type: pb.MsgBeat})
	}
}
```

https://github.com/etcd-io/etcd/blob/v3.5.10/raft/raft.go#L655

処理自体はシンプルで、heartbeatElapsed変数をインクリメントしていき、heartbeatTimeoutに達すると自身に対してMsgBeatを発行します。

### MsgBeat受信後の動作

LeaderがMsgBeatを受信すると、sendHeartbeat関数が実行され、Leaderが認識している他のNodeにMsgHeartbeatが送付されます。toはLeadertが認識している任意の他のNodeを表現しており、Nodeの数だけsendHeartbeatが実行されます。sendHeartbeatを受け取ったNode側の処理は後述します。

```golang
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)
}
```
https://github.com/etcd-io/etcd/blob/v3.5.10/raft/raft.go#L495

## tickElection関数

次にCandidate/Followerで実行されるtickElection関数の処理を見ていきます。

```golang
// 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})
	}
}
```
https://github.com/etcd-io/etcd/blob/v3.5.10/raft/raft.go#L645

処理自体はシンプルで、electionElapsedをインクリメントし、if文の条件式でtrueとなれば、MsgHubを自身に対して発行します。MsgHubが発行されると、campaign関数が実行され、選挙がはじまります。
条件式について簡単に説明すると、下記の判定が行われてます。

- [promotable()](https://github.com/etcd-io/etcd/blob/v3.5.10/raft/raft.go#L1612)：リーダーになることができるかどうか
- [pastElactionTimeout()](https://github.com/etcd-io/etcd/blob/v3.5.10/raft/raft.go#L1708)：electionElapsedがTimeoutに達しているかどうか

### electionElapsedの初期化のタイミング

electionElapsedがインクリメントし続けると選挙が始まってしまうため、定期的に初期化が行われます。初期化のタイミングはいろいろあるのですが、その中の1つにFollowerがMsgHeartbeatを受信した時が含まれています。具体的には、下記に示すstepFollower関数の`case pb.Msgheartbeat:`で処理されます。

```golang
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
}
```

https://github.com/etcd-io/etcd/blob/v3.5.10/raft/raft.go#L1415


## まとめ

- raft構造体のtickフィールドについてみていきました
- tickは定期的に実行される関数であり、Stateとの対応関係は以下になります
  - Follower　-> tickElection関数
  - Candidate -> tickElection関数
  - Leader　　-> tickHeartbeat関数
- tickXXX関数の処理まとめ
  - tickHeartbeat関数
    - 定期的にMsgHeartbeatを他のNodeに送付する
  - tickElection関数
    - electionElapsed変数をインクリメントしていき、タイムアウトすると選挙を開始する
    - リーダーからMsgHeartbeatを受け取るとelectionElapsed変数がリセットされる