『Rabia: Simplifying State-Machine Replication Through Randomization』
Paxos は実際実装しようとするといろいろ追加でやらないといけないことが多い
Fail-over, Reconfiguration, Snapshotting, Log Compaction, ...
論文では auxiliary protocols と呼んでいる
拡張するとその拡張が正しいかわからなくなる
Paxos ほどではないけど Raft もそう
同一 DC 内のような Stable Network に限定すると、より簡単にできることがわかった
(Stable Network とはなに？どのように形式化しているのか？)
Rabia は Fail-over はいらない。Log Compaction その他もシンプルになる
(どうやって？)
パフォーマンスもいい
まずは2値の合意をする
2値だけだと SMR を使って Key-Value Store みたいなのは作れないのでなんとかする
Randomized Consensus と Deterministic Consensus
Randomized Consensus
probablistic termination
故障していないレプリカはいつかリクエストを100%の確率で受け取る
時間が経つにつれて、受け取る確率が100%に漸近する
任意の時間かかる可能性はあるが、現実的にはこれで問題ない
(こういうのに確率は出てくるだろうとは Actario を作っているとき思っていた)
Deterministic Consensus
類似アルゴリズムたち
single leader
Chubby の論文: 「Paxos とリアルワールドシステムの間には大きなギャップがあった。...最終的なシステムは unproven なプロトコルになった」
single leader
論文にリアルワールドで使うための拡張も書いてあるがまだ難しい
Fail-over がいらない
パフォーマンスが悪い
ネットワークスイッチのシーケンサー機能？を使う
Fail-over がいらない
パフォーマンスはとてもいい (Multi-Paxos の4.7倍)
ネットワークスイッチにフォワーディングルールを追加する必要あり
多くのクラウドではできない
ランダム2値合意
probablistic termination を満たす
leader less
joint decision
レイテンシがめちゃくちゃあるし予測できない
合意するまで何度もメッセージを送り合う可能性 (それでも何度もやっていれば確率1で合意する)
早くても Multi-Paxos より遅い
メッセージ数も多い
論文の説明ではよくわからない。一人死んだらだめでは？
Rabia
システムモデル
n 個のサーバ (レプリカ)
f 個のレプリカが死ぬ可能性あり
n >= 2f + 1
多数決できるギリギリまでは死ねる
ビザンチン故障は考えない
レプリカが追加されたり取り除かれたりすることはない (一旦)
アルゴリズム (Weak-MVC 以外)
Algorithm 1 に書いてあるとおり
クライアントからのリクエスト
Priority Queue (PQ) に、タイムスタンプをキーにして入れて他のノードにプロキシ
たぶんログに追記されるまでクライアントは待たせる
PQ からとって合意してログに追記、をループ
Weak-MVC というやつでシーケンス番号と一緒に合意
MVC = Mult- Valued Consensus
PQ からとったやつがすでにログにあったら捨てる
Weak-MVC で合意した値が PQ からとったのと違っていれば PQ に入れ直してやり直し
たぶんそのシーケンス番号がすでに合意している値なら、そのシーケンス番号の値が返ってくる
同じシーケンス番号で並行に合意しようとするノードがいたらそっちの値になるかもしれない
ログエントリがアプリケーションに渡されたらそのログエントリは消していい (Log Compaction)
Stable Network だと速い理由
Fast path になるのは以下のいずれかのとき
(1) すべてのレプリカが同じプロポーザルを持つ
リクエストが来る速度よりもリクエストをプロキシする速度のほうが早ければ、どのノードでも最も古いリクエストは同じものになることが多い
(それは Stable Network のおかげというよりも、リクエストがあんまり来ないからなのでは。Stable ではなくてもリクエストが来なければいいのでは)
(2) 同じリクエストをプロポーズするレプリカはマジョリティではない
(よくわからなかった)
Weak-MVC は、合意に至るまで長くなりそうなら諦めて NULL を返す
アルゴリズム (Weak-MVC)
Weak Validity
合意された値は、プロポーズされた値か、NULL である
「か、NULL である」が Weak であるところ
前提
Stable Network
TCP 前提
メッセージの順序は保証されている
生きているノードからのメッセージは Exactly Once で届く
疑問メモ
確かにアルゴリズムは簡単だけどうまくいくの？
ひとつのノードが突然とても遅くなったりしたらどうなる？
飛び交うメッセージの数多すぎない？ノード数3か5くらいが限界？
Log Compaction が簡単なのは、ログの再送を行わないからでOK?
ログの順序はリクエストの実時間順にはならないという理解であっている？
seq はどうやって合意している？seq が異常に古いノードがいたら、seq が最新になるまで Weak-MVC を何度も繰り返さないといけない？遅くない？
PQ からとってきたリクエストがすでにログにあったら捨てる、ってやつ、ログコンパクションで捨てられていたらすでにログにあるかどうかがわからない可能性があるのでは？
Section 4 で説明されるっぽい
Weak-MVC の Randomized Binary Consensus Stage が必要な理由がわからない
v=0 で終わったら結局 NULL が返るし
Exchange Phase で過半数のが同じ値をプロポーズしてこなかったら即 NULL を返すのとの違いがわからない
これがあることで fail-over しなくてよくなるらしいがよくわからない
FindReturnValue で v=1 でも m が見つからない場合があるのでは？
最初から v=1 になっているときは floor(n/2)+1 回現れている m があるといえると思うが、CoinFlip で v=1 になったときは m は floor(n/2)+1 回現れていないこともあるのでは
が、論文のとわりと違っていて、これだと論文の主旨 (拡張いらないよという話) に反しているのでは
見つからない例
n=5で3つが同じプロポーザル、一つだけstate=1、全部vote=?、二週目全部state=1のとき、見つからない場合を作れる
ただ、ノード間の通信で片方からの通信が届くならもう片方の通信も必ず届くという前提ならこの例は成り立たないかも
最初state=1のノードのプロポーザルは過半数を超えている、を使うなら別かも
これも成り立たない例を作れる
決定したときにその値をブロードキャストするというやつをなぜ論文では抜いたのかわからない。これがないといろいろ成り立たなくなると思う。論文は不完全では。Ben-Orの証明の論文では一応文章で書かれてはいるのに
Weak-MVC が最低でも3メッセージ必要なら、Multi-Paxos とか Raft (どちらも2メッセージで合意できる) よりも遅いのでは？
Rabia はクライアントからのリクエストのプロキシでも1メッセージ使うし
seq の同期は必要だったりする？同じ seq でどのノードも同時に Weak-MVC が始まらないとだめ？
一度遅れたノードは使えるようになるには seq が同じ値になるまで待たないとだめそう？
死んだように見せかけて遅いだけで死んでいなかったやつがいたときの振る舞いが気になる
Weak-MVC を他のアルゴリズムと入れ替えることはできる？
CoinFlip を Common (全ノードで同じ値を用いる) にする理由は？
probabilistic termination を満たすためっぽいが
Fast path で NULL を返しても問題を後回しにしているだけなのでは
fail-over protocol ってなに
Raft であれば leader が死んだら leader election が起こるが、そういうやつのこと
Figure 3 で "Replica 1 has seen at least two votes on v,so Replica 2 and 3 must have state = 1" と書いてあるけど、Replica 1 からの vote はないのだろうか (自分自身の vote は自分では受け取らない？でもそうするとその後 Replica 1 が死んだあとに 2 と 3 が 2 votes 受け取っているのがよくわからない)
生きているノードは Weak-MVC の各フェーズを同期的に実行していくということであっている？
つまり生きているノードが極端に遅くなることはないという前提をおいている？
Safety には関係ないが
極端に遅くなるノードが多数あったらそのノードを待つ
つまり、n - f ノードの中に遅いノードがいたらそいつがボトルネックになる
n - f のノードの中にいなければ合意は進んでいく (が、そいつは取り残される)
生きているノードは合意に取り残されないみたいな性質あったりする？
Randomized Consensus のフェーズで n - f のメッセージを待つので、n - f 数のノードは取り残されない。
他の遅いノードは取り残されるかもしれないが、生きているノードからのメッセージは必ずやってくるのでそれを覚えてさえいたら合意は可能 (なはず)
決定した値のブロードキャストが入るならそれを見るだけでもOK
FindReturnValue で v=1 の場合必ず過半数の同じ値がプロポーザルにあるみたいな性質が成り立ったりする？
reconfiguration で add-replica する場合、どうやって過去のログを引っ張ってくるのか
スナップショットから復元するのだろうけど、復元している間にもログは伸びていくので、どうするのか
先に合意クラスタに参加だけしておいて、そこからどこかのノードのスナップショットを取り始めて、スナップショットから復元したらその seq からログを適用する、とするとたぶん安全にいけそう
このくらいでいいので書いておいてほしかった
感想
手法について
単発の Weak Multi-Valued Consensus をするアルゴリズムだけ作れたら SMR は簡単に作れそうなのでよい
合意に時間がかかりそうなら諦めて次にまわす、というやり方でもパフォーマンスがいいのが意外だった
Multi-Paxos とか Raft よりもメッセージ数もラウンドも多くてもパフォーマンスがいいのが意外だった
コネクションが切れることを想定していない (切れたらクラッシュしたとみなす必要がありそう) なので、その辺勝手にリトライして繋ぎ直すライブラリを下に使っているとダメそう
Rabiaはメッセージのリオーダー、ドロップを許さないので
これけっこう厳しそう
Weak-MVC の部分はもうちょっといいアルゴリズムが今後出てくる気がする
Weak-MVCのところは入れ替えられる
Weak-MVCのメッセージ数が多すぎるのがやっぱりデメリットではないか
理解も難しい (Raftよりむずいと思う)
Bottom を許すならなんかもうちょっと簡単なやりかたがありそうな気がする
全員が同じ値をプロポーズするならそれ、そうでないならボトム、みたいなめちゃ簡単なやつでパフォーマンスがどうなるか気になる
一人死んだら終わるからだめそう
過半数が同じ値をプロポーズするならそれ、だと Agreement に違反する例を簡単に作れるのでだめそう
意外に難しいのかも
ただBen-Orだけ入れ替えるというのは無理そう。FindReturnValueの事前条件に関わってくるので
Weak-MVC をどうやってググったらいいかわからない
論文の Weak Validity が一般的な (Wikipedia に書いてあるような) 定義と異なっている
めちゃくちゃアクセスが多い場合 (合意のスピードよりも速い場合) には ⊥ が大量に発生しそう
まあ合意のスピードよりもリクエストが速い時点でほかの合意アルゴリズムもだめなのは同じか
PQ が溜まってきていたら 503 みたいなのを返すとかは簡単にできそう
Raft とかよりも実装は簡単かも
論文について
FindReturnValueの事前条件が強すぎて理解がきつい
値を決定したらブロードキャストなりもう一周待つなりする話は書いておいて欲しい。これがないと合意に取り残されるノードが出てくる
同じノードから連続してメッセージが送信されたとして、後に送ったメッセージが届いたらその前のメッセージも全て届いている、という性質を暗黙に使いまくっているので、Stable Networkというのはこういうものですよと書いておいて欲しい
形式的に証明するにしても証明の概略は書いておいて欲しい