セキュリティキャンプ2023 Y3分散合意ゼミ 最終発表

Transcript

1. セキュリティキャンプ2023成果発表 Y3分散合意ゼミ 高棟雄斗
2. アジェンダ • 分散合意ゼミのテーマ/目的 • Raftについて • 今回実装したもの • 感想
3. 分散合意ゼミのテーマ/目的 • コンピュータシステムの耐故障性を高めたい場面で分散システムを使用す ることがある • 分散合意は、分散システムにおいてノードを共通の値や状態に合意するプ ロセス • 分散合意アルゴリズムとして代表的なRaftを実装を通して学ぶことがこの ゼミの目的
4. Raftについて • Raftは、分散システム内の複数のノードを同じ状態に合意するためのアル ゴリズム • ノードの中から選挙でリーダーを選出する ◦ リーダーがいなくなった場合は、残りのノードから再選挙される • クラスタに送られてきた通信は全てリーダーに集約され、リーダーから各 ノードにレプリケーションされる
5. 今回実装したもの • リーダー選挙 • ログレプリケーション • ソースコード: https://github.com/shinbunbun/raft.go
6. リーダー選挙
7. リーダー選挙 • 全てのノードの中から1台のLeaderを選出する • 2台以上のLeaderが選出された場合 or 1台もLeaderを選出できなかった 場合はやり直し
8. リーダー選挙のフロー • リーダー検出 ◦ リーダーは定期的に FollowerにHeartbeatを送信している ◦ Followerは、一定時間HeartBeatが送られてこなかった場合に自身を Candidateとしてリーダー選 挙に立候補する • リーダー決定 ◦ Candidateは全てのノードに対して投票リクエストを送り、受け取ったノードは Leaderとして受け入 れるか否かを回答する ◦ 過半数以上の賛成を得れた場合はそのノードが Leaderとなる
9. node01: Leader node02~05: Follower node 01 node 02 node 03 node 04 node 05 HeartBeat
10. node01: Leader node02~05: Follower node 02 node 03 node 04 node 05 node 01
11. node02: Candidate node03~05: Follower node 02 node 03 node 04 node 05 投票リクエスト
12. node02: Candidate node03~05: Follower node 02 node 03 node 04 node 05 投票
13. node02: Leader node03~05: Follower node 02 node 03 node 04 node 05
14. ログレプリケーション
15. ログレプリケーション • 全てのノードにおいて有効なログについて合意を取る ◦ Leaderは過半数以上のFollowerが追加に成功したindexまでのlogを確定 ▪ つまり、状態を問い合わせした際には必ず過半数以上のノードで確定している logが返される ◦ Logの追加に失敗した場合は Followerが必要としているLogの全てが含まれていないものと判断 し、古いLogを含めて再送処理を行う
16. Client {Log: [hoge]} を追加 node 01 node 02 node 03 node 04 node 05 node01: Leader node02~05: Follower Logをレプリケーション {Log: [hoge]} node01 gya, fuga node02 gya node03 gya, fuga node04 gya, fuga node05 gya, fuga
17. node 01 node 02 node 03 node 04 node 05 node01: Leader node02~05: Follower node01 gya, fuga, hoge node02 gya node03 gya, fuga, hoge node04 gya, fuga, hoge node05 gya, fuga, hoge
18. node 01 node 02 node 03 node 04 node 05 node01: Leader node02~05: Follower node01 gya, fuga, hoge node02 gya node03 gya, fuga, hoge node04 gya, fuga, hoge node05 gya, fuga, hoge 再送 {Log: [fuga, hoge]}
19. node 01 node 02 node 03 node 04 node 05 node01: Leader node02~05: Follower node01 gya, fuga, hoge node02 gya, fuga, hoge node03 gya, fuga, hoge node04 gya, fuga, hoge node05 gya, fuga, hoge
20. ビジュアライザ • ノードやデータの動きを可視化するためのビジュアライザを発表用に作成
21. 動画リンク https://youtu.be/Wc2IRQNuEp0
23. 感想 • Channelまわりでバグったりなど、Goの知識が足りない部分があった • 実際に手を動かすことでRaftの仕組みを理解できてとても楽しかった • 今回の講義では一部扱っていない部分があったので、原著論文を読んでちゃんと 実装したい