Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
セキュリティキャンプ2023 Y3分散合意ゼミ 最終発表
Search
Yuto Takamune
August 11, 2023
Programming
0
3.6k
セキュリティキャンプ2023 Y3分散合意ゼミ 最終発表
Yuto Takamune
August 11, 2023
Tweet
Share
More Decks by Yuto Takamune
See All by Yuto Takamune
GPT-3.5 Turbo をファインチューニングして自分のクローンを作った話
shinbunbun_
0
300
RustのLINEBot SDKを自作した話
shinbunbun_
0
1.6k
NixOSでもご自宅k8sがしたい!
shinbunbun_
2
3.5k
カーネルレベルでTwitterを禁止しよう
shinbunbun_
0
220
CRDTで始めるコンフリクトしないデータ同期
shinbunbun_
0
470
Haskell初心者がHaskellの楽しさについて語る
shinbunbun_
0
180
Rustで楕円曲線暗号の署名アルゴリズムをフルスクラッチ実装してみた話
shinbunbun_
0
1.5k
IEEE802.1X認証を導入してみた
shinbunbun_
0
250
UBICの食材管理APIを作った話
shinbunbun_
0
210
Other Decks in Programming
See All in Programming
TypeScriptのmoduleオプションを改めて整理する
bicstone
4
430
推論された型の移植性エラーTS2742に挑む
teamlab
PRO
0
150
Spring gRPC で始める gRPC 入門 / Introduction to gRPC with Spring gRPC
mackey0225
0
140
TypeScript だけを書いて Tauri でデスクトップアプリを作ろう / Tauri with only TypeScript
tris5572
2
540
〜可視化からアクセス制御まで〜 BigQuery×Looker Studioで コスト管理とデータソース認証制御する方法
cuebic9bic
2
270
TypeScript製IaCツールのAWS CDKが様々な言語で実装できる理由 ~他言語変換の仕組み~ / cdk-language-transformation
gotok365
7
380
List Unfolding - 'unfold' as the Computational Dual of 'fold', and how 'unfold' relates to 'iterate'"
philipschwarz
PRO
0
140
Practical Domain-Driven Design - Workshop at NDC 2025
mufrid
0
130
インターフェース設計のコツとツボ
togishima
2
490
CRUD から CQRS へ ~ 分離が可能にする柔軟性
tkawae
0
230
ts-morph実践:型を利用するcodemodのテクニック
ypresto
1
540
バランスを見極めよう!実装の意味を明示するための型定義 TSKaigi 2025 Day2 (5/24)
whatasoda
2
780
Featured
See All Featured
Code Reviewing Like a Champion
maltzj
523
40k
[Rails World 2023 - Day 1 Closing Keynote] - The Magic of Rails
eileencodes
34
2.3k
Building Adaptive Systems
keathley
41
2.6k
Product Roadmaps are Hard
iamctodd
PRO
53
11k
Into the Great Unknown - MozCon
thekraken
39
1.8k
Evolution of real-time – Irina Nazarova, EuRuKo, 2024
irinanazarova
8
750
Building an army of robots
kneath
306
45k
Statistics for Hackers
jakevdp
799
220k
Music & Morning Musume
bryan
47
6.6k
Building Applications with DynamoDB
mza
95
6.4k
Performance Is Good for Brains [We Love Speed 2024]
tammyeverts
10
850
Visualizing Your Data: Incorporating Mongo into Loggly Infrastructure
mongodb
45
9.6k
Transcript
セキュリティキャンプ2023成果発表 Y3分散合意ゼミ 高棟雄斗
アジェンダ • 分散合意ゼミのテーマ/目的 • Raftについて • 今回実装したもの • 感想
分散合意ゼミのテーマ/目的 • コンピュータシステムの耐故障性を高めたい場面で分散システムを使用す ることがある • 分散合意は、分散システムにおいてノードを共通の値や状態に合意するプ ロセス • 分散合意アルゴリズムとして代表的なRaftを実装を通して学ぶことがこの ゼミの目的
Raftについて • Raftは、分散システム内の複数のノードを同じ状態に合意するためのアル ゴリズム • ノードの中から選挙でリーダーを選出する ◦ リーダーがいなくなった場合は、残りのノードから再選挙される • クラスタに送られてきた通信は全てリーダーに集約され、リーダーから各
ノードにレプリケーションされる
今回実装したもの • リーダー選挙 • ログレプリケーション • ソースコード: https://github.com/shinbunbun/raft.go
リーダー選挙
リーダー選挙 • 全てのノードの中から1台のLeaderを選出する • 2台以上のLeaderが選出された場合 or 1台もLeaderを選出できなかった 場合はやり直し
リーダー選挙のフロー • リーダー検出 ◦ リーダーは定期的に FollowerにHeartbeatを送信している ◦ Followerは、一定時間HeartBeatが送られてこなかった場合に自身を Candidateとしてリーダー選 挙に立候補する
• リーダー決定 ◦ Candidateは全てのノードに対して投票リクエストを送り、受け取ったノードは Leaderとして受け入 れるか否かを回答する ◦ 過半数以上の賛成を得れた場合はそのノードが Leaderとなる
node01: Leader node02~05: Follower node 01 node 02 node 03
node 04 node 05 HeartBeat
node01: Leader node02~05: Follower node 02 node 03 node 04
node 05 node 01
node02: Candidate node03~05: Follower node 02 node 03 node 04
node 05 投票リクエスト
node02: Candidate node03~05: Follower node 02 node 03 node 04
node 05 投票
node02: Leader node03~05: Follower node 02 node 03 node 04
node 05
ログレプリケーション
ログレプリケーション • 全てのノードにおいて有効なログについて合意を取る ◦ Leaderは過半数以上のFollowerが追加に成功したindexまでのlogを確定 ▪ つまり、状態を問い合わせした際には必ず過半数以上のノードで確定している logが返される ◦ Logの追加に失敗した場合は
Followerが必要としているLogの全てが含まれていないものと判断 し、古いLogを含めて再送処理を行う
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
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
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]}
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
ビジュアライザ • ノードやデータの動きを可視化するためのビジュアライザを発表用に作成
動画リンク https://youtu.be/Wc2IRQNuEp0
None
感想 • Channelまわりでバグったりなど、Goの知識が足りない部分があった • 実際に手を動かすことでRaftの仕組みを理解できてとても楽しかった • 今回の講義では一部扱っていない部分があったので、原著論文を読んでちゃんと 実装したい