RaftのMembership Changeは博士論文を読めとのこと

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というのは, シングルサーバの追加・削除に限定した場合の話のようである. 一応読む. 面白ければシェアする.

comments powered by Disqus
Built with Hugo
テーマ StackJimmy によって設計されています。