---
title: Raft入門
tags:  #lifull #raft  
author: [株式会社LIFULL](https://convert.docswell.com/user/LIFULL)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/LJ3RKMMZE5.jpg?width=480
description: 分散合意アルゴリズムのRaftの説明
published: April 16, 24
canonical: https://convert.docswell.com/s/LIFULL/KNRYPG-2024-04-16-185526
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/LJ3RKMMZE5.jpg)

Raft入門
プラットフォームG 宮崎 泰輔


# Page. 2

![Page Image](https://bcdn.docswell.com/page/8JDY3664JG.jpg)

Raftとは何なのか


# Page. 3

![Page Image](https://bcdn.docswell.com/page/VEP64YYV78.jpg)

Raftとは何なのか
Raftは安全な State Machine Replication (SMR) を実装するための
分散合意アルゴリズムである
Paxos系のアルゴリズムの代替として設計された。
Paxosの理解が難しすぎる、実装によってどこまで保証されているか
かなり異なっていたので、
「理解可能性」を重視しつつ、有用な性質は維持するように設計された


# Page. 4

![Page Image](https://bcdn.docswell.com/page/27V3XGGRJQ.jpg)

State Machine Replicationとは
耐障害性を備えるためにデータを複数のサーバーでコピーを持ち合う。
複数のサーバーにデータのコピーを作る方法の一つ。
複数のサーバーで同じ初期状態から開始した有限状態機械(FSM)に同じコ
マンドを同じ順序で適用することで、すべてのサーバーが
同じ状態遷移をする。
「同じ状態から同じ状態遷移すれば、同じ状態になる」


# Page. 5

![Page Image](https://bcdn.docswell.com/page/5JG3V886EL.jpg)

そうは言っても複数のマシンで同じ状態遷移をさせるのは難しい


# Page. 6

![Page Image](https://bcdn.docswell.com/page/47Q56992EP.jpg)

なぜ難しいのか
サーバーたちはネットワークを介してやり取りを行う。
そしてネットワークでのメッセージの伝播速度はバラバラなので、
複数のサーバーが同時にメッセージを送っても、順番が変わってしまう
初期状態A
サーバー1: A -&gt; Bに状態遷移させたい(時刻 t1)
サーバー2: A -&gt; a に状態遷移させたい(時刻t1)
サーバー3: 時刻t2にB, aどちらになっているべき？


# Page. 7

![Page Image](https://bcdn.docswell.com/page/KE494XXPJ1.jpg)

なぜ難しいのか
リーダーを置いて、リーダーがメッセージの順序を決める
複数のサーバーがそれぞれ新しい状態に遷移させようとしない。
リーダー以外は受け取ったメッセージを自分の状態機械に適用するだけ
これで順序を決められるからOK？
NO


# Page. 8

![Page Image](https://bcdn.docswell.com/page/L71K4NNXEG.jpg)

障害が発生しうる
- Crash-Stop
-
ネットワークから突然消えて復帰しない
- Omission
-
メッセージがロストする
- Performance, Timing
-
タイムアウトまでに応答がない(タイムアウトを過ぎて応答があるかも
- Crash-Recovery
-
止まっていたインスタンスが復帰してくる（状態が古い）
- Byzantine, Arbitrary
-
悪意ある行動


# Page. 9

![Page Image](https://bcdn.docswell.com/page/G7WDX44KE2.jpg)

障害が発生しうる
しかも、ネットワーク越しだと
相手サーバーがクラッシュしたのか、メッセージがロストしたのか、
それともそのうち復帰してくるのかはわからない
自分視点だと単に応答がないようにしか見えない


# Page. 10

![Page Image](https://bcdn.docswell.com/page/4JZG622N73.jpg)

Raftの話
Raftは複数サーバーで何かを合意するときに quorum (定足数) に達している
かで物事を決める。
Raftのクラスタは、1つのリーダーとリーダー以外のフォロワーによって構成さ
れる。（Raftがやり取りするメッセージはログと呼ばれる）
重要な動作
- リーダー選挙
- ログ複製


# Page. 11

![Page Image](https://bcdn.docswell.com/page/YE6Y2VV9JV.jpg)

リーダー選挙
それぞれのサーバーはリーダーか、フォロワー、そして選挙時には
候補者のどれかの役割を必ず持っていて、最初はみんな候補者として
リーダーを決めることから始まる。
状態遷移図


# Page. 12

![Page Image](https://bcdn.docswell.com/page/GE5G2DDDE4.jpg)

リーダー選挙
リーダーには任期（term）が存在する
termは単調増加で、リーダーを選ぶタイミングごとにインクリメント
選ぶタイミングごとなので、リーダーが決定しない任期が存在する
※後述


# Page. 13

![Page Image](https://bcdn.docswell.com/page/972Y1MMM7R.jpg)

リーダー選挙の流れ
1. 全員候補者から開始
2. 自分のtermをインクリメントする
3. RequestVote を全サーバーに送る
4. 過半数以上のレスポンスを受け取ったらLeaderになる
5. その後Leaderは定期的にハートビートを送ってLeaderを維持する


# Page. 14

![Page Image](https://bcdn.docswell.com/page/DJYGZXXPJM.jpg)

リーダー選挙の流れ
4で票が別れた場合(複数の候補者がRequestVoteを送ると起き得る)
1. タイムアウトまで待っても票が集まらなかったらリトライする
（リトライの時にtermがインクリメントされる）
リトライまでにランダムな時間waitする
自分より大きなtermのRequestVoteが届いたら
- 自分はフォロワーになる


# Page. 15

![Page Image](https://bcdn.docswell.com/page/V7NG311ME8.jpg)

リーダー選挙の流れ
遷移図再掲


# Page. 16

![Page Image](https://bcdn.docswell.com/page/YJ9W955WJ3.jpg)

リーダー選出の流れ
全員Followerから始め
ハートビートを受け取るタイムアウトまで待つ
F
F
F


# Page. 17

![Page Image](https://bcdn.docswell.com/page/GJ8N9YYRED.jpg)

リーダー選出の流れ
1. タイムアウトして候補者になる
(タイムアウトする時間はランダムにちょっと違う)
2. 自分を含め全員にRequestVoteを送る
F
C
RequestVote
(term=1)
C


# Page. 18

![Page Image](https://bcdn.docswell.com/page/LJLPW442ER.jpg)

リーダー選出の流れ
過半数の投票（応答）を得たため、リーダーになる
F
C
OK
(term=1)
L


# Page. 19

![Page Image](https://bcdn.docswell.com/page/47M49KK9EW.jpg)

リーダー選出の流れ
1. 全員に自分がリーダーであることを通知する(AppendEntries)
2. CandidateはFollowerになる(元々Followerでも、termを設定し直す)
3. ハートビートは定期的に送られる
F
F
AppendEntries
(term=1)
L


# Page. 20

![Page Image](https://bcdn.docswell.com/page/P7RWGXX9E9.jpg)

ログのレプリケーション
「Leaderが保持しているログがマスター」
「コミットされた」データは絶対に改変されない
1. リーダーがクライアントからのリクエストを受け取る
2. リーダーのログのエントリに追加
3. Followerに対して、AppendEntries でエントリを送信
4. 過半数からエントリを保存した応答があれば
リーダーのエントリをコミットする
5. コミット内容をクライアントに送信する


# Page. 21

![Page Image](https://bcdn.docswell.com/page/PJXPX663EX.jpg)

まとめ
リーダー選出の大まかな流れを説明した
ログレプリケーションの大まかな流れを説明した
ただし、ここで説明しただけだと実は不十分な箇所がある
気になる人は調べてみてください
- コミットされた通知をFollowerが受け取ってくれる前にLeaderが
死んだら、コミットされたのに他のFollowerにLeaderが変更されると変更
内容が失われる


# Page. 22

![Page Image](https://bcdn.docswell.com/page/3JKDW11N7D.jpg)

まとめ
- サーバーを止めずにクラスタの構成を更新したい場合
- ログが肥大化してしまう
-
スナップショットを使う


