Raftは簡単だ. Yeah. Raftは素晴らしい. YEAH! しかしMembership Change… WHAT!?
おれは, In Search of an Understandable Consensus Algorithm (Extended Version) (https://raft.github.io/raft.pdf) を読んだ. Membership Changeの章で分からないことがあったので, とりあえずメールしてみたらわりと速攻で返ってきた. ありがとうディエイゴー
Dr. Diego Ongaro,
I am Akira Hayakawa. I am working as a software engineer.
I am implementing Raft algorithm based on your paper and I have one question:
Does joint consensus algorithm described in your paper works in case the C_old and C_new don't have any intersection?
I think the answer is no because there is a case that no leader can be elected under C_old,new. This case is artificially made in such scenario:
Client sends request to update membership from [0,1,2] to [3,4,5] Leader distributes and [0,1,2,3,4,5] and it's committed. Leader crashes The cluster needs to elect new leader from C_old,new the membership that all the follower recognize.
I am not pointing any theoretical defect in the algorithm but just from my curiosity.
Thanks,
Akira
質問は, Membership ChangeでC_old, C_newに仮に共通集合がなかった場合はリーダーが選出出来なくなって破綻するケースがありませんか？ということ.
Hi Akira,
The short answer is yes, C_old and C_new do not need any servers in common. There's a simpler algorithm and better explanation in my dissertation ( https://github.com/ongardie/dissertation/), but make sure you check the errata too. If you want to discuss further, please use the raft-dev Google group, where others are likely to chime in before me.
Best, Diego
答えは,
- 破綻はしない (short answer)
- simpler algorithm and better explanation in my dissertation
- より議論したい場合はraft-devへ
とのことだった. 博士論文を見てみると遥かに詳しく書いてある. Simpler algorithmについて分かったらシェアします.
追記
破綻しないというのは分かった. 頭が悪くて混乱していた.
破綻するケースはないというのは, 単に[3,4,5]は[0,1,2]の中のcandidateにvoteすることが出来るから. membershipはどいつらからmajorityを確保するか発信側が決めることであって, それにvoteするかどうかはmembershipは関係なく, consistency checkのみが関わる. だから例えば0がcandidateになったとして, [1]と[3,4]からvoteを受ければリーダーになることが出来る.
Simpler algorithmというのは, シングルサーバの追加・削除に限定した場合の話のようである. 一応読む. 面白ければシェアする.