[Feature]: Membership change

[themanforfree]

Description about the feature

Membership change has two different situations

1. Change only one node at a time, in this case there must be duplicate nodes in majority of the old and new configurations, it is impossible to elect two leaders at the same time, we can handle this situation simply, after the new configuration is committed, the new configuration can be used to make decisions.
   
2. Change multiple nodes at a time, the following situation may occur. nodes using different configurations may have two disjoint majorities, which means that two leaders may be elected, the solution is introduce an intermediate state, after the leader receives the configuration change request, the new configuration node set is C_new, and the old configuration node set is C_old. After C_new is committed, it enters the joint consensus state. When an election occurs, C_old and C_new jointly decide, and then the leader creates an empty Configuration change log, after this log committed, cluster can use C_new alone to make decisions, and the cluster completes this configuration change node, and this configuration change is complete.
   

Learner
When adding a new node to the cluster, the new node does not have the current data of the cluster. At this time, the leader needs to sync the data to the new node. This process may take a while, which will increase the risk of cluster unavailability. Therefore, the Learner node is introduced. Nodes only sync logs, do not participate in voting, wait until the Leaner node catches up with the progress of the leader, and then promote it to a normal node.

I plan to implement the membership change in three stages

1. implement single node change, and prepare some struct for multiple nodes change.
2. implement Learner node.
3. implement multiple nodes change.

Tests

• The member id and cluster id calculated by all nodes should be consistent when Initialize the cluster.
• The new node should pull member IDs directly from the existing cluster and use them, and should not calculate IDs by itself.
• Client should use new configuration after cluster member change

Related papers

1. https://raft.github.io/raft.pdf
2. https://web.stanford.edu/~ouster/cgi-bin/papers/OngaroPhD.pdf

Code of Conduct

• I agree to follow this project's Code of Conduct

[themanforfree]

More details of stage 1

• use Arc to share LogEntry, then we can make LogEntry instead of Command transmitted in conflict checked mpmc channel, this can make curp manage content other than Command. Feature/member add single #382
• Build client without ServerId. refactor: build client without ServerId #412
• Use u64 as ServerId instead of string. refactor: use u64 as ServerId #413
• Handle single node config change logic in curp. (voters, follower status, sync_follower_daemons, sync event, cluster info) feature: add apply_conf_change method for RawCurp #433
• Update photobuf, add new ProposeConfChange interface and implement propose logic. Propose conf change #437
• Use a logical clock to represent the cluster configuration version, and detect that the client rejects the request when using the old configuration. Client discover cluster #460
• Add Cluster Server in Xline. Feat/cluster server #464

[themanforfree]

Problem

At first, I planned to reuse the processing logic for command directly as follows, but the ER and ASR is defined externally, And ConfChange is an internal behavior of curp, so we can't make ConfChange produce externally defined ERs and ASRs.

...
TaskType::SpecExe(entry, pre_err) => {
    let er = if let Some(err_msg) = pre_err {
        Err(err_msg)
    } else {
        match entry.entry_data {
            EntryData::Command(ref cmd) => ce
                .execute(cmd, entry.index)
                .await
                .map_err(|e| e.to_string()),
            EntryData::ConfChange(_) => todo!(),
        }
    };
    let er_ok = er.is_ok();
    cb.write().insert_er(entry.id(), er);
    if !er_ok {
        sp.lock().remove(entry.id());
        let _ig = ucp.lock().remove(entry.id());
    }
    debug!(
        "{id} cmd({}) is speculatively executed, exe status: {er_ok}",
        entry.id()
    );
    er_ok
}
...

Solution

...
TaskType::SpecExe(entry, pre_err) => match entry.entry_data {
    EntryData::Command(ref cmd) => {
        let er = if let Some(err_msg) = pre_err {
            Err(err_msg)
        } else {
            ce.execute(cmd, entry.index)
                .await
                .map_err(|e| e.to_string())
        };
        let er_ok = er.is_ok();
        cb.write().insert_er(entry.id(), er);
        if !er_ok {
            sp.lock().remove(entry.id());
            let _ig = ucp.lock().remove(entry.id());
        }
        debug!(
            "{id} cmd({}) is speculatively executed, exe status: {er_ok}",
            entry.id()
        );
        er_ok
    }
    EntryData::ConfChange(_) => true,
}
...

In fact, cmd_worker only needs to return a bool value to indicate whether the task is running successfully, and does not care about the internal specific execution process, so there is no need for ConfChange to produce ER, just return a bool

[Phoenix500526]

Problem

At first, I planned to reuse the processing logic for command directly as follows, but the ER and ASR is defined externally, And ConfChange is an internal behavior of curp, so we can't make ConfChange produce externally defined ERs and ASRs.

...
TaskType::SpecExe(entry, pre_err) => {
    let er = if let Some(err_msg) = pre_err {
        Err(err_msg)
    } else {
        match entry.entry_data {
            EntryData::Command(ref cmd) => ce
                .execute(cmd, entry.index)
                .await
                .map_err(|e| e.to_string()),
            EntryData::ConfChange(_) => todo!(),
        }
    };
    let er_ok = er.is_ok();
    cb.write().insert_er(entry.id(), er);
    if !er_ok {
        sp.lock().remove(entry.id());
        let _ig = ucp.lock().remove(entry.id());
    }
    debug!(
        "{id} cmd({}) is speculatively executed, exe status: {er_ok}",
        entry.id()
    );
    er_ok
}
...

Solution

...
TaskType::SpecExe(entry, pre_err) => match entry.entry_data {
    EntryData::Command(ref cmd) => {
        let er = if let Some(err_msg) = pre_err {
            Err(err_msg)
        } else {
            ce.execute(cmd, entry.index)
                .await
                .map_err(|e| e.to_string())
        };
        let er_ok = er.is_ok();
        cb.write().insert_er(entry.id(), er);
        if !er_ok {
            sp.lock().remove(entry.id());
            let _ig = ucp.lock().remove(entry.id());
        }
        debug!(
            "{id} cmd({}) is speculatively executed, exe status: {er_ok}",
            entry.id()
        );
        er_ok
    }
    EntryData::ConfChange(_) => true,
}
...

In fact, cmd_worker only needs to return a bool value to indicate whether the task is running successfully, and does not care about the internal specific execution process, so there is no need for ConfChange to produce ER, just return a bool

LGTM