Disclaimer: I worked on this project in my free time. It is not affiliated, associated, endorsed by, or in any way officially connected with my current employer Facebook, or any of its subsidiaries or its affiliates.
I have been spending a lot of time at home and doing a lot of readings on distributed systems during the pandemic. Recently I noticed that the main observation of Heidi Howard’s Flexible Paxos (FPaxos) work is applicable to Raft. Heidi Howard already extended Raft’s TLA+ proof for that. There is also a few open source Raft implementations that mention FPaxos, but as far as I see nobody has implemented the idea yet.
I analyzed the simple quorums and improved majority quorums settings of FPaxos in the context of Raft consensus algorithm, and had a few interesting findings. I wanted to present my findings in a concise way, so I wrote a short paper for it.
Improved Majority Quorums for Raft
Raft has gained widespread adoption in the industry as a newcomer, thanks to its pragmatic approach to the distributed consensus problem. Also, its resemblance to Paxos allows it to benefit from decades of research on Paxos. In this work, we study simple quorums and improved majority quorums of FPaxos in the context of Raft consensus algorithm. Even-sized clusters are prone to a greater risk of unavailability compared to odd-sized clusters because of the majority quorum requirement. Our main finding, which applies equally to Raft and Multi-Paxos, shows that even-sized clusters can employ improved majority quorums to obtain the same degree of availability as odd-sized ones with one less server. We also use improved majority quorums to simplify Raft cluster membership changes. Our solution minimizes availability gaps during cluster membership changes without any extra phase or voting state. We expect existing Raft implementations to utilize our findings with quite small code changes.
You can click here to download the paper.
My dear wife, Fatma Kahveci, contributed proof of the equation I present in the paper.
My fellas, Marko Topolnik, Mehmet Dogan, and Milan Savic reviewed multiple drafts of this paper. Marko provided his valuable feedback to improve the readability of the paper.
Kudos to all!
Last, all errors belong to me.