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
hashicorp_raftからraftを学ぶ
Search
t10471
June 15, 2023
Technology
0
830
hashicorp_raftからraftを学ぶ
raftの論文の解説とhashicorp/raftの使い方について解説します。
t10471
June 15, 2023
Tweet
Share
More Decks by t10471
See All by t10471
EOSにPull Requestを出してマージされた話
t10471
1
670
分散台帳・暗号通貨とRust ブロックチェーンをRustで作ってる話
t10471
2
1.3k
Kubernetesの ダークカナリアリリースツールを作った話
t10471
0
740
Kubernetes・GCPを使った チャットボットサービスの 機械学習部分の話
t10471
0
160
型についてちょっと考える
t10471
1
300
Other Decks in Technology
See All in Technology
GitHub Actions/Docker/Terraform/Renovate で最小限の Monorepo CD パイプラインを作る / Minimalistic Monorepo CD Pipeline with GitHub Actions, Docker, Terraform and Renovate
yuyatakeyama
4
340
Strict Concurrencyにしたらdeinitでクラッシュする話
0si43
0
120
【shownet.conf_】AI技術とUX監視の応用でShowNetの基盤を支えるモニタリングシステム
shownet
PRO
0
270
CVE alive
ennael
PRO
0
360
ITエンジニアとして知っておいてほしい、電子メールという大きな穴
logica0419
2
300
【shownet.conf_】ローカル5Gを活用したウォーキングツアーの体感向上
shownet
PRO
0
250
virtme-ng
ennael
PRO
0
310
Oracle GoldenGate 23ai 導入Tips
oracle4engineer
PRO
1
200
ガバメントクラウド開発と変化と成長する組織 / Organizational change and growth in developing a government cloud
kazeburo
2
380
MLOpsの「あるある」課題の解決と、そのためのライブラリgokart
mski_iksm
1
150
[JAWS-UG GameTech] 第6回 各種事例紹介_18TRIPにおけるAWSサービスを活用した負荷テスト・障害テスト
naoto_yasuda
0
100
LINEヤフー新卒採用 コーディングテスト解説 アルゴリズム問題編
lycorp_recruit_jp
0
12k
Featured
See All Featured
Being A Developer After 40
akosma
84
590k
Into the Great Unknown - MozCon
thekraken
30
1.4k
Let's Do A Bunch of Simple Stuff to Make Websites Faster
chriscoyier
504
140k
Build your cross-platform service in a week with App Engine
jlugia
229
18k
Typedesign – Prime Four
hannesfritz
39
2.3k
XXLCSS - How to scale CSS and keep your sanity
sugarenia
246
1.3M
The Mythical Team-Month
searls
218
43k
Side Projects
sachag
452
42k
Robots, Beer and Maslow
schacon
PRO
157
8.2k
Building Adaptive Systems
keathley
37
2.1k
For a Future-Friendly Web
brad_frost
174
9.3k
The Straight Up "How To Draw Better" Workshop
denniskardys
231
130k
Transcript
1 hashicorp/raftからraftを学ぶ mercari.go #22 @toshinao
2 • twitter ◦ toshinao • Backend Engineer at Mercoin
◦ 主に外部システム連携を担当 自己紹介
3 • https://www.oreilly.co.jp/books/97848731199 77/ • Go言語による分散サービスの中でraftを使ったシ ステムのハンズオンが記載されている • hashicorp/raftを使った分散ログ保存サービスの コードが載っている
raftについて調べたきっかけ
4 • ログや設定を保存するための分散合意アルゴリズム • etcd(KVS)やcunsul(サービスディスカバリー)の中で使わ れている • Leaderの権限が強い ◦ シンプルで分かりやすいメカニズムを目指して作られた
◦ clientの応答は全てLeaderが返す(と論文には書かれている) ◦ ログの送信(レプリケーション)はLeaderから送る ◦ 過半数に書き込みが成功すると確定したことになる raftについて
5 • 論文は2つある ◦ 最初に博論として書かれた ▪ https://github.com/ongardie/dissertation#readme ◦ よく読まれている論文は元の論文からコンセンサスアルゴリズム部 分を抽出している
▪ https://raft.github.io/raft.pdf • 博論には下記について詳細に書かれている ◦ 構成変更 ◦ ログのコンパクション ◦ clientとのやり取り 論文
6 • ログはどのノードも同じ状態になるような仕組み ◦ 有限状態機械(Finite State Machine; FSM)として同じ順序でロ グを適応することで実現している •
Leaderからheartbeatを送る ◦ leaderから一定期間heartbeatが送られないと選挙が始まる • 論理時計を持つことでクラスターの一貫性を保つ ◦ hashicorp/raftではlamport clockを使用している ◦ term(Leaderの期間)、index(単調増加する値)を保存・送信する 特徴
7 • Followerから始まる • 選挙が始まると(timeoutを検知すると)Candidateになる • 選挙で選ばれるとLeaderになる • Leaderの時に自分より大きいtermのログが届くとFollower になる
サーバーの状態
8 • コンセンサス ◦ AppendEntries RPC ▪ ログの追加 ▪ heartbeat(空で送るとheartbeatになる)
◦ RequestVote RPC ▪ 選挙 • 構成変更(博論にだけ載っている) ◦ AddServer RPC ▪ 新しいサーバー追加 ◦ RemoveServer RPC ▪ サーバーの削除 論文に載っているRPC1
9 • Snapshotの連携(博論にだけ載っている) ◦ InstallSnapshot RPC ▪ ログの連携が遅いフォロワーに対してSnapshotを送る • クライアント(博論にだけ載っている)
◦ ClientRequest RPC ▪ PRCのリクエスト ◦ ClientQuery RPC ▪ Read Onlyのリクエスト ◦ RegisterClient RPC ▪ client毎にidを発行する(重複リクエストを識別出来るようにす るため) 論文に載っているRPC2
10 • Leaderからのheartbeatが途切れたら選挙がはじまる • FollowerからCandidateに変更 • 立候補はランダムな時間をおいてからリクエストする ◦ 立候補とはRequestVote RPCを他のサーバーに送ること
◦ 票が割れてLeaderが決まらないケースを減らす • RequestVote RPC受信側は自分の持っているterm、indexの方が 大きい場合、投票しない 選挙
11 • Leaderが変わるとtermが変わる • Leaderが決まらなかった場合、termが変わる ◦ 票が割れた場合など ◦ Lederがいないtermが存在する termと選挙の関係
12 // 下記の関数でraftインスタンスを生成・起動 func NewRaft(*Config, FSM, LogStore, StableStore, SnapshotStore,Transport) (
*Raft, error) // FSMは下記のメソッドを実装している必要がある type FSM interface { Apply(*Log) interface{} Snapshot() (FSMSnapshot, error) Restore(snapshot io.ReadCloser) error } // LogStoreはAppendEntries RPCで追加するログの保存 // StableStoreは設定を保存 // LogStoreとStableStoreで使えるraft-mdbやraft-boltdbがある // SnapshotStoreはLogStoreのSpanpshot // Transportはサーバー間で通信する為のロジック hashicorp/raftの使い方・生成
13 // Leaderとして起動(BootstrapClusterしないサーバーはFollowerとして起動) func (r *Raft) BootstrapCluster(configuration Configuration) Future //
Logの追加 func (r *Raft) Apply(cmd []byte, timeout time.Duration) ApplyFuture // clusterに参加 func (r *Raft) AddVoter(id ServerID, address ServerAddress, prevIndex uint64, timeout time.Duration) IndexFuture // clusterから抜ける func (r *Raft) RemoveServer(id ServerID, prevIndex uint64, timeout time.Duration) IndexFuture // Leaderを他のサーバーに委譲する func (r *Raft) LeadershipTransfer() Future // restoreを強制的に呼ぶ raft.Restore(meta *SnapshotMeta, reader io.Reader, timeout time.Duration) Leaderで呼ぶ必要があるメソッド
14 // Leaderサーバーのアドレスを取得 func (r *Raft) Leader() ServerAddress // 設定の取得
func (r *Raft) GetConfiguration() ConfigurationFuture // 自サーバーがどの状態(Leader、Follower、Candidate)か取得 func (r *Raft) State() RaftState // snapshotを強制的に呼ぶ func (r *Raft) Snapshot() SnapshotFuture // サーバーをshutdownするときに呼ぶ func (r *Raft) Shutdown() Future Leader以外でも良いメソッド
15 • AppendEntries ◦ logをFollowerに送る ◦ 構成変更もAppendEntriesで送られる • RequestVote ◦
Leaderになるときに他のサーバーに送る ▪ last_log_indexやlast_log_termも送る ◦ responseのGrantedをtrueで返すと投票したことになる • TimeoutNow ◦ Leaderを委譲するサーバーに選挙開始を伝える • InstallSnapshot ◦ コンパクション済みでAppendEntriesで遅れない場合にspanshotを送る hashicorp/raftの内部API
16 • 論文と実装ではことなることがある • Client APIは存在しない ◦ Leader以外で更新系処理を実行するとエラーになる ◦ Leaderが誰か把握している必要がある
◦ 取得系の処理はLeader以外が返しても良い • Configurationの更新もAppendEntriesで伝える ◦ AddServer RPC やRemoveServer RPCは存在しない • TimeoutNowというAPIが存在する ◦ Leaderの委譲時に使う ▪ 移譲先が早くRequestVoteを送るために使用する まとめ