###### tags: `memo` `systems`
# LEC 19 Replicated State Machines

Slide URL: http://web.mit.edu/6.033/www/lec/s19-partial.pdf

## 前回までの話
- トランザクションは atomicity と isolation を提供する
- atomicity を実現する方法のとして以下がある
- shadow copies
- logging
- isolation を実現する方法のとして以下がある
- 2PL
- 複数マシンにまたがるトランザクションを実現する方法として以下がある
- 2PC

## 今回の話

- データを複数のマシンに複製し、かつ、一貫性を担保したい

## 一貫性を担保しながら冗長性を担保する (3つの方法)

### :one: ナイーブな方法

<small>※講義スライドより引用</small>

coordinator が同じ書き込みリクエストを複数の worker に送るだけ

以下の処理を考える

- coordinator A から worker1, worker2 にそれぞれ A = 30 を書き込む
- coordinator B から worker1, worker2 にそれぞれ A = 20 を書き込む

もし、これが以下の順番で実行されると…

1. [coordinator A] worker1 A = 30
2. [coordinator B] worker2 A = 20
3. [coordinator A] worker2 A = 30
4. [coordinator B] worker1 A = 20

**最終的に worker1 には 20、worker2 には 30 が格納され、inconsistent な状態になる**

### :two: worker を primary/backup に分ける方法
<small>※講義スライドより引用</small>

1. coordinator は primary と backup の場所を知っている
2. coordinator はリクエストを primary にだけ送信する
3. primary で操作の順番を確定し、backup にも同じ操作をさせる
4. backup の操作が完了してから primary は coordinator に ACK を返す

primary に障害があったら、backup を primary に昇格

以下の場合を考える

<small>※講義スライドより引用</small>

- coordinator が 2 つあり（coordinator A と B）、2 つとも primary につながっている
- ネットワークが以下の 2 つの部分に分断したとする
- coordinator A と primary が通信できる（partition1）
- partition1 では backup とつながっていないだけで、primary は生きているので、coordinator A は相変わらず primary と通信する
- coordinator B と backup が通信できる（partition2）
- partition2 では coordinator B が primary と繋がらなくなったので、backup を primary に昇格する

**primary が 2 つ存在することになり、inconsistent な状態になる**

### :three: Replicated State Machines: RSMs

<small>※講義スライドより引用</small>

- view server はどの worker が primary、backup かの情報（view）を管理する
- view server は view を世代管理する
- view server は worker に primary/backup などの role を通知する（**状態を共有**）
- **view server から worker に view (状態) を複製するので replicated state machines？**
- coordinator は view server に primary の在り処を聞き、その後 primary と通信する
- primary/backup は定期的に view server に heart beat を送信し、生きていることを通知する

view server と primary が network partition により分断した場合どうなるのか、以下の 2 ステージに分けて考える。なお、primary は S1、backup は S2 とする

1. **view server は view を更新し、S2 を新たな primary に据える（ただし、まだ S2 に通知してない）**
- view server は S2 を primary だと思っている
- S1 と S2 は S1 が primary だと思っている
- この状態で coordinator が S1 にリクエストしたらどうなるか？
- **通常通り動く**
- S1 と S2 は S1 が primary だと思っているので何も問題はない
2. **1. の後、view server と S2 の view が同期した場合**
- view server と S2 は S2 が primary だと思っている
- S1 だけが S1 を primary だと思っている
- この状態で coordinator が S1 にリクエストしたらどうなる？
- S1 は S2 を backup だと思っているので、操作ログを backup にも流す
- しかし、S2 は自身を primary だと認識しているので、これを reject
- 結果、S1 は coordinator にエラーを返すことになる
- coordinator はこれを受けて、view server に再度 primary の場所を聞く
- view server は S2 だと答える
- **結果 coordinator は S2 を primary だと認識する**
3. **S2 が primary になった後に S1 が復活した場合**
- S1 は heart beat を view server に送る
- view server は S1 の復帰を検知し、S1 を backup として view を更新する
- heart beat のレスポンスで S1 は自身の view が古いことに気づき、view を更新する
- **S1 は自身を backup だと認識する**

#### RSMs で View Server で障害が起きたらどうなる？

- 単一障害点なので死ぬ
- なので、何かしらの対処が必要
- distributed consensus が必要になる
- view server を 1 〜 N 個に分散できる
- view server 群を取りまとめる super view server を設けてどうにかならない？
- そうすると、今度は super view server が単一障害点になる…
- Raft の論文を読めとのこと