「Rustで作って学ぶ分散合意アルゴリズムRaft」を書きたいという意思表明
2.5K Views
January 23, 25
スライド概要
Osaki.rs #3
https://osaki-rs.connpass.com/event/341887/
Working at Deno Land, Studying at Georgia Tech
関連スライド
各ページのテキスト
Rustで作って学ぶ 分散合意アルゴリズム Raft を書きたいという 意思表明 2025/01/22 Osaki.rs #3 Yusuke Tanaka
Who am I 米ジョージア工科大学のオンライン修士 課程に通いながらDeno Land Inc.で Deno Deployを作っています🦕 ← リアルで会った方にはもれなくこの名 刺をプレゼント！ GitHub: https://github.com/magurotuna 𝕏: https://x.com/yusuktan 🦋: https://bsky.app/profile/magurotuna.bsky.social mixi2: https://mixi.social/@magurotuna
今日の内容
Rustで作って学ぶ 分散合意アルゴリズム Raft
を書きたい (Zennとかで)
（あんまり Rustの話出てきません）
背景 ● 大学院の前学期で Distributed Computing という授業をとった ● 課題で分散キーバリューストアを実装 ● consensus (合意) をとるためのアルゴリズムとしてPaxosを利用 ○ むずすぎた ● 2014年に論文が出た Raft というのがナウでイケてるらしい ○ Raftの論文 “In search of an understandable consensus algorithm” (理解可能なコンセンサスアルゴリズムを求めて) ● Raftでナウなヤングになりたい！！
そもそも ……
Rustで作って学ぶ ← 🤗 分散合意アルゴリズム ← 🤔 Raft← 🤔
「分散合意」とは？
分散合意とは？ ● 複数のノードが通信を通じて一貫した決定をすること ● 通信を通じて？ ○ 複数ノードが参照できるグローバル変数みたいなものはない ○ 複数ノードが参照できる同期された時計もない ○ 通信は不安定かもしれない（メッセージ損失、順番の入れ替わり、メッ セージが複製されて届くなど） ● 決定？ ○ 例: 複数のノードのうち、今のリーダーは誰か？ ○ 例: あるステートマシンへの入力を表す「コマンドの列」
Raft とは？
Raftとは？ ● 分散システム上で、各ノードは突然処理が遅くなったり、完全に停止したり してしまうかもしれない ● 通信も常に期待通りにできるとは限らない ● そんな過酷な状況でも、ノードのうち過半数が生きてさえいれば、一貫した 決定（の列）を失うことなく稼働し続けられる ○ （Raftでは各ノードは壊れるとしたら「ただ停止する」ものという仮定をおいている。悪意のあるノードがいるか もしれない場合は別のアルゴリズムが必要: pBFTとかで調べてみてください） ● これを実現するアルゴリズム Paxos が20世紀末に登場 ● 難しすぎて2014年に Raft が登場、10年で一気に広がる ○ Etcd, CockroachDB, TiDB, など
論文読んでみた https://raft.github.io/raft.pdf
分かりやすすぎて感動 (Paxos 比)
年末年始に Javaで実装してみた (授業の課題で使ったフレームワーク の上で)
わりとすぐできた ※できた = 用意されているテストケースがけっ こう通せた
Rust でも書きたい！！ ちなみに既存実装はたくさんある tikv/raft-rs とか databendlabs/openraft とか
記事か本で発信したい！
展望 ● 今年中にやる ○ 大学院の学期が始まってしまったので、ちょっと休止…… ● 方針 ○ テストをちゃんと書きながら進めていく ○ 書いたRaftをライブラリとして使い、その上に何か分散システムの実 例を作るところまでやる （無難にkey-valueストア？） ● ライブラリ選定 ○ ノード間のメッセージのやり取りをいい感じに抽象化してくれるアク タークレート ractor が気になっている
LTすることで退路を断つスタイル
Thank you all 🦀