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.7k
セキュリティキャンプ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.6k
カーネルレベルでTwitterを禁止しよう
shinbunbun_
0
230
CRDTで始めるコンフリクトしないデータ同期
shinbunbun_
0
480
Haskell初心者がHaskellの楽しさについて語る
shinbunbun_
0
180
Rustで楕円曲線暗号の署名アルゴリズムをフルスクラッチ実装してみた話
shinbunbun_
0
1.5k
IEEE802.1X認証を導入してみた
shinbunbun_
0
260
UBICの食材管理APIを作った話
shinbunbun_
0
210
Other Decks in Programming
See All in Programming
Haskell でアルゴリズムを抽象化する / 関数型言語で競技プログラミング
naoya
11
2.2k
少数精鋭エンジニアがフルスタック力を磨く理由 -そしてAI時代へ-
rebase_engineering
0
150
TypeScript LSP の今までとこれから
quramy
1
460
型安全RESTで爆速プロトタイピング – Hono RPC実践
tacke_jp
0
110
F#で自在につくる静的ブログサイト - 関数型まつり2025
pizzacat83
0
230
統一感のある Go コードを生成 AI の力で手にいれる
otakakot
0
1.8k
CSC307 Lecture 17
javiergs
PRO
0
110
Prism.parseで 300本以上あるエンドポイントに 接続できる権限の一覧表を作ってみた
hatsu38
1
100
バランスを見極めよう!実装の意味を明示するための型定義 TSKaigi 2025 Day2 (5/24)
whatasoda
2
810
Cloudflare Realtime と Workers でつくるサーバーレス WebRTC
nekoya3
0
360
從零到一:搭建你的第一個 Observability 平台
blueswen
0
310
型付きアクターモデルがもたらす分散シミュレーションの未来
piyo7
0
610
Featured
See All Featured
Imperfection Machines: The Place of Print at Facebook
scottboms
267
13k
The Language of Interfaces
destraynor
158
25k
How to Ace a Technical Interview
jacobian
276
23k
Adopting Sorbet at Scale
ufuk
77
9.4k
Fireside Chat
paigeccino
37
3.5k
Product Roadmaps are Hard
iamctodd
PRO
53
11k
Cheating the UX When There Is Nothing More to Optimize - PixelPioneers
stephaniewalter
280
13k
Embracing the Ebb and Flow
colly
85
4.7k
How GitHub (no longer) Works
holman
314
140k
GraphQLの誤解/rethinking-graphql
sonatard
71
11k
Optimizing for Happiness
mojombo
378
70k
The MySQL Ecosystem @ GitHub 2015
samlambert
251
13k
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の仕組みを理解できてとても楽しかった • 今回の講義では一部扱っていない部分があったので、原著論文を読んでちゃんと 実装したい