ReCraft: Self-Contained Split, Merge, and Membership Change of Raft Protocol

Kezhi Xiong¹ Soonwon Moon² Joshua H. Kang¹ Bryant Curto¹

Jieung Kim³ Ji-Yong Shin¹

¹Northeastern University ²Seoul National University ³Yonsei University

The 55th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, June 26, 2025

1

Reconfiguration

​

​

​

​

​

​

​

1. Changing member nodes of a distributed system
2. Changing the organization (e.g., for sharding) of a distributed system

​

​

​

2

Crucial for liveness and performance of a distributed system

Reconfiguration for distributed systems

• Configuration change needs to be done consistently

​

​

​

​

​

​

​

​

​

3

Config

Config

Config

Reconfiguration of consensus-based systems?

• Reliance on external services �(consensus-based system relying on consensus-based system)

​

​

​

​

​

​

​

​

​

4

Reconfiguration of consensus-based systems?

• Self-contained approach

​

​

​

​

​

​

​

5

Consensus-based system

Consensus

New configuration

State machine replication log

Update

Update

New�Config

Update

Initial�Config

• Non-stopping approach: Reconfigure while system is running� (Raft and ReCraft approach)

• Stopping approach: Stop regular ops -> Reconfigure -> Resume� (Bad for performance)

ReCraft: ❸ Self-Contained Split, Merge, and � ❷ Membership Change of ❶Raft Protocol

❷ Why new membership change?

• Design from new insight �[Honoré et al., PLDI 2022]

​

​

❸ Why new split and merge protocols?

• No self-contained, non-stopping scheme
• For better fault-tolerance, performance, and operability

​

6

❶ Why Raft? Most popular consensus protocol

​

ReCraft

• Introduction

​

• Raft/ReCraft Assumptions and a Brief Intro to Membership Change� (Please refer to the paper for more details)

​

• ReCraft Split and Merge Protocols

​

• Evaluation

​

• Conclusion

7

ReCraft and Raft assumptions and conditions

• Inherits Raft’s assumptions
• Asynchronous non-Byzantine network failures
• Each cluster of N nodes with a quorum size Q can tolerate up to f = N – Q node failures

​

• Inherits Raft’s preconditions for reconfiguration�
1. All prior reconfiguration in the leader’s log must be committed� [Originally proposed in Ongaro’s PhD Thesis, 2014]
2. Consecutive configurations should always maintain a quorum overlap� [Relaxed by Honoré et al., PLDI 2022]
3. Leader must commit a log entry in its term before starting a reconfiguration� [Added by Ongaro as bug fix, 2015]

8

Q is usually majority, but can be bigger during reconfiguration

Raft Revisited

9

Total # of nodes = 2f+1 = 3

Quorum size = f+1 = 2

Max # of failures = f = 1

A

C

B

0

α

0

α

0

α

Leader Election

(Leader must have an up-to-date log)

Committed due to Quorum Overlap:

all possible majority sets contain “β”

{A, B} {A, C} {B, C} {A, B, C}

New leader carries β

!

All decisions require an agreement of a quorum

!

Raft Membership Change

10

Old Config {A, B, C}

New Config (NC) {A,B,C,D,E}

Raft

Raft vs ReCraft Membership Change (see Paper for details)

11

Old Config {A, B, C}

New Config (NC) {A,B,C,D,E}

2. adjusts to Q-new (conditional)

ReCraft

Raft

When Q-new+ = Q-new,

ReCraft can omit one consensus step

(e.g., adding 2 nodes to 2-node cluster)

NC

ReCraft

• Introduction

​

• Raft and ReCraft Assumptions and Membership change� (Please refer to the paper for more details)

​

• ReCraft Split and Merge Protocols

​

• Evaluation

​

• Conclusion

12

ReCraft Split Based on Quorum Overlap

13

B

C

A

E

D

• Conf-old
• Range: α – ω
• Q-old: 3 out of A-E

​

EnterJoint (EJ)

LeaveJoint (LJ)

ReCraft Split

14

EnterJoint (EJ)

LeaveJoint (LJ)

Split

Done

Allows non-stopping

updates to new config

Commit with

smaller # of messages

than Q-joint > Q-old

Prefix of term #;

incremented when Split/Merge succeeds

B

C

A

E

D

α – μ

ν - ω

α – ω

What can go wrong?

15

D and E can get stuck

If epoch is larger,

pull data up to LJ

Updates only when Split or Merge is done.

​

Clearly marks configuration change

Epoch: 1

α – ω

ν - ω

ReCraft Merge: Lock-based-2PC over Consensus

16

2PC prepare

2PC commit/abort

Data exchange

Only blocking operation in ReCraft

What can go wrong?

17

B

C

A

α

α

α

Epoch: 3

E

F

D

π

π

π

Epoch: 5

α – μ

ν - ω

2PC prepare

The main cause of a “NO” answer is

ongoing transaction, our precondition #1

Evaluation

• Implementation
• Modified Raft library and relevant code in etcd ver 3.5
• 4K+ lines of Go code modification

​

• Experimental setup
• Public research cloud
• 16 VMs each with 2 vCPUs and 8GB DRAM
• Uniform random put workload

​

• Baseline
• Emulation of Multi-Raft design (TiKV and CockroachDB) on etcd

18

Adopted Multi-Raft baseline

19

Split Procedures

Cluster Manager

• Relies on external configuration manager
• Stops extensively

Split

20

ReCraft Does not need data transfer: always constant time

1 x 6 node cluster to 2 x 3-node clusters

Lower is better

Merge

21

ReCraft blocks minimally and transfers data in parallel

MultiRaft serially sends data through the cluster manager

2 x 3-node clusters to 1 x 6 node cluster

Lower is better

Fault tolerance

22

Minimum # of node failures to completely stop the split/merge

in previous experiments

Fail 6-node cluster = 3

Fail two 3-node clusters = 4

Fail one 3-node cluster = 2

Fail one 3-node cluster = 2

Fail one 3-node cluster = 2

Fail standalone CM = 1

Fail standalone CM = 1

Fail one 3-node cluster = 2

Fail one 3-node cluster = 2

Triple replication with Raft

• Multi-Raft requires running an extra CM module
• ReCraft can serve clients under failures due to non-stopping design

Conclusion

• ReCraft: reconfiguration protocol for Raft

​

• Improved membership change protocol to Raft�(details in the paper)

​

• First self-contained split and merge protocol for Raft �(can be ported to multi-Paxos as well)

​

• Etcd implementation shows effectiveness against Multi-Raft

23

Thank you!�Q & A�

More in the paper

• Detailed ReCraft membership change
• Handling other corner cases for split and merge
• Formal proof sketch of correctness
• Links to
1. Artifact (Go code & Rocq proofs)
2. Extended version of the paper

Ji-Yong Shin �(j.shin@northeastern.edu; https://www.jiyongshin.info)

Extra: ReCraft Membership change vs Raft

• # of required messages for reconfiguration

25

Extra: ReCraft Membership change vs Raft

• # of consensus for reconfiguration

26

Fault tolerance

27

Minimum # of node failures to completely stop the split/merge

• f_old = f of 6 node cluster
• f_sub = f of 3 node cluster
• f_cm = f of 3 node cluster

Fail 6-node cluster = 3

Fail two 3-node clusters = 4

Fail one 3-node cluster = 2

Fail one 3-node cluster = 2

Fail one 3-node cluster = 2

Fail standalone CM = 1

Fail standalone CM = 1

Fail one 3-node cluster = 2

Fail one 3-node cluster = 2

Triple replication with Raft

• MultiRaft requires maintaining extra CM module
• ReCraft can servicing client under partial failures �due to non-stopping design

Raft vs ReCraft Membership Change (see Paper for details)

28

Old Config {A, B}

New Config (NC) {A, B, C, D}

B

A

Checks for quorum Q-old:

2 of {A,B}

Checks for Q-old

Checks for Q-new

B

C

D

A

Checks for quorum Q-new:

3 of {A,B,C,D}

2. Adjusts quorum to Q-new, � if necessary

1. Activates Q-new+

❷ In general,

Q-new+ ≥ Q-new

ReCraft

Raft

Q-new+ = 3 out of {A, B, C, D}

Because Q-new+ = Q-new, second step is omitted