分布式系統(tǒng)中Membership Change 源碼解讀

01

背景

在分布式系統(tǒng)的應(yīng)用場景中，難免會出現(xiàn)增刪節(jié)點(diǎn)或者替換節(jié)點(diǎn)的需求，最簡單的解決方式就是臨時(shí)關(guān)閉集群，然后直接修改配置文件添加新的節(jié)點(diǎn)，完成后再將集群重新啟動，這樣的方式的確能達(dá)成我們的目的，但是其存在的問題也很明顯，變更期間集群是不可用的狀態(tài)，這對需要高可用性的系統(tǒng)來說是無法接受的，并且手動操作的過程還可能引發(fā)其他的錯誤，這也會降低系統(tǒng)的穩(wěn)定性。因此，如何才能高效且安全的完成集群成員變更，也就成為了分布式系統(tǒng)開發(fā)過程中的關(guān)鍵問題。對于 Xline 來說，不僅要處理常規(guī)的變更流程，還要將其與 Curp 協(xié)議相結(jié)合，保證引入集群成員變更不會導(dǎo)致前端協(xié)議出錯。

02

動態(tài)成員變更的問題以及解決方案

由于 Xline 使用 Raft 作為后端協(xié)議，因此想要為 Xline 添加動態(tài)變更成員的能力，就需要解決 Raft 協(xié)議自身會遇到的問題。Raft 協(xié)議能夠正常工作的一個重要前提是，同一時(shí)間只能有一個 Leader，如果不加任何限制，直接向集群添加節(jié)點(diǎn)，那么就有可能破壞這個前提，具體情況如下圖所示：

由于網(wǎng)絡(luò)延遲等原因，無法保證各節(jié)點(diǎn)從切換到 的時(shí)間相同，就有可能出現(xiàn)圖中的情況，假設(shè)此時(shí) Server 1 和 Server 5 同時(shí)開始選舉，Server 1 獲得了 Server 2 ?的投票，滿足 中的 quorum 需求，成為 Leader，Server 5 獲得了 Server 3 和 Server 4 的投票，滿足 中的 quorum 需求，Server 5 也成為 Leader，此時(shí)集群就會同時(shí)有兩個 Leader，產(chǎn)生一致性問題。 ? 為了解決這個問題，Raft 的作者提供了兩種解決思路。

Joint Consensus

單步成員變更

Joint Consensus Joint Consensus 本質(zhì)上就是在成員變更過程中添加一個中間狀態(tài)。

Leader 收到成員變更請求時(shí)，會創(chuàng)建一條一個配置并通過 AppendEntries 同步到 Follower，收到 的節(jié)點(diǎn)會同時(shí)使用兩個配置做決策，也就是選舉等操作需要 和 都同意才視為成功 ，等到 ?commit 之后，Leader 會再創(chuàng)建 配置并同步給 Follower。 ? 在這種方案下，集群成員變更的中間狀態(tài)有以下幾種可能： ? 1.?? 創(chuàng)建之后提交之前，這個階段集群中可能同時(shí)存在 ， 兩種配置，在此階段內(nèi)任意節(jié)點(diǎn)想要成為 Leader 都需要 配置同意，因此不會出現(xiàn)兩個 Leader。 ? 2.?提交之后，創(chuàng)建之前，這個階段集群中可能同時(shí)存在 ? 兩種配置，但只有使用 的節(jié)點(diǎn)才能夠成為 Leader，因?yàn)榇穗A段 中的多數(shù)節(jié)點(diǎn)已經(jīng)切換到了 配置，剩余還未切換的節(jié)點(diǎn)不足以選出新 Leader。 ? 3.?創(chuàng)建之后提交之前，這個階段集群中可能同時(shí)存在 三種配置，其中 配置無法選出 Leader，原因如上，和 中要選出 Leader，就需要 同意，此情況也不會出現(xiàn)兩個 Leader。 ? 4.?commit 之后，由 獨(dú)立決策，不會出現(xiàn)兩個 Leader。 ? ? 單步節(jié)點(diǎn)變更 除了 Joint Consensus 以外，還有一種方法可以安全的完成集群成員變更，那就是單步節(jié)點(diǎn)變更。該方法每次只會增加或減少一個節(jié)點(diǎn)，這種情況下，新舊配置的 majority 中必然有重疊節(jié)點(diǎn)，重疊的節(jié)點(diǎn)只能給一個節(jié)點(diǎn)投票，這樣就保證了不會同時(shí)存在兩個 Leader。復(fù)雜的變更行為就需要轉(zhuǎn)換成多次單步節(jié)點(diǎn)變更來完成。

這種方案沒有中間狀態(tài)，只需要一步操作就可以完成變更，邏輯上比 Joint Consensus 更加簡潔，沒有那么多復(fù)雜的中間狀態(tài)，實(shí)現(xiàn)起來也會簡單一點(diǎn)，當(dāng)然它的功能也沒有 Joint Consensus 強(qiáng)大。 Xline 目前采用的方法就是單步成員變更，未來我們也會添加對 Joint Consensus 的支持。

03

Curp 協(xié)議的融合

Membership change 的主要流程，只通過后端的 Raft 就能夠完成，但是這個過程可能會擾亂前端 Curp 協(xié)議的流程。正常處理時(shí)，Curp client 會向集群中所有節(jié)點(diǎn)廣播 Propose 請求，并根據(jù)成功相應(yīng)的數(shù)量是否大于當(dāng)前集群成員數(shù)量的 superquorum 來判斷本次 propose 是否在 curp 中 commit，實(shí)現(xiàn) membership change 以前，所有成員都在創(chuàng)建 client 時(shí)確定，但是引入了 membership change 之后，就需要有一種機(jī)制能夠保證 Client 在使用舊的配置時(shí)，也能夠探測到服務(wù)端使用的新配置，并且使用新配置重試當(dāng)前的請求，否則可能導(dǎo)致 Curp 協(xié)議無法正常工作。

如圖所示，假設(shè) Client 向一個三節(jié)點(diǎn)集群廣播 Propose，那么 Client 收到 3（3 節(jié)點(diǎn)的 superquorum） 個成功響應(yīng)后就會認(rèn)為這一次 Propose 已經(jīng)在 Curp 中 commit，在此次 Propose 過程中，集群成員發(fā)生了變更，Server4 加入了集群，然而 4 節(jié)點(diǎn)的 superquorum 是 4，也就是說剛剛在 3 節(jié)點(diǎn)集群中被 curp commit 的請求，在成員變更之后就不再滿足 Curp 的 commit 條件了，這可能會導(dǎo)致已經(jīng)返回給 Client 的請求丟失。 為了解決這個問題，我們?yōu)橥獠?client 發(fā)送的請求引入了一個新的字段 cluster_version ，這個字段表示集群當(dāng)前使用配置的版本，每次執(zhí)行成員變更，都會增加這個值，這樣 Server 端就能夠通過這個字段來判斷發(fā)送請求的 Client 是否在使用最新配置，并且直接拒絕使用舊配置的請求，Client 探測到 cluster_version 不一致后，就會主動拉取 Server 端的最新配置，并以最新配置發(fā)起新一輪的請求。在上述實(shí)例中，Propose 和成員變更同時(shí)發(fā)生時(shí)，Server1、2、3 中一定有節(jié)點(diǎn)已經(jīng)在使用新配置了，那么該節(jié)點(diǎn)就會使用更大的 cluster_version 拒絕本次 Propose，Client 檢測到更大的 cluster_version 后，會重新向集群拉取當(dāng)前的成員配置，然后以新配置重試整個請求。

04

源碼解讀

Leader 發(fā)起成員變更 開始變更成員的第一步，就是向 Leader 發(fā)送 ProposeConfChangeRequest，這個請求包含了本次 propose 要變更的節(jié)點(diǎn)信息和一些其他的輔助字段。 Server 端收到該請求后，首先會檢查請求攜帶的 cluster_version 是否和集群當(dāng)前 cluster_version 匹配，不匹配的請求直接拒絕，然后才會進(jìn)入 Server 端的處理邏輯:

///Handle`propose_conf_change`request
pub(super)fnhandle_propose_conf_change(
&self,
propose_id:ProposeId,
conf_changes:Vec,
)->Result<(),?CurpError>{
//...
self.check_new_config(&conf_changes)?;
letentry=log_w.push(st_r.term,propose_id,conf_changes.clone())?;
debug!("{}getsnewlog[{}]",self.id(),entry.index);
let(addrs,name,is_learner)=self.apply_conf_change(conf_changes);
self.ctx
.last_conf_change_idx
.store(entry.index,Ordering::Release);
let_ig=log_w.fallback_contexts.insert(
entry.index,
FallbackContext::clone(&entry),addrs,name,is_learner),
);
//...
}

Leader 節(jié)點(diǎn)在處理時(shí)，會通過 check_new_config 方法檢查本次 conf change 的有效性，提前拒絕一些無法處理的變更，比如插入一個已經(jīng)存在的節(jié)點(diǎn)或者移除一個不存在的節(jié)點(diǎn)。檢查通過之后，就會進(jìn)入和常規(guī)請求相同的流程，通過共識將其同步到所有 Follower 上，除了這部分相同流程以外， conf change 還需要做一些特殊處理，在其插入 log 之后，就會立刻應(yīng)用新配置，并且記錄用于回退配置的上下文。這里和 Raft 論文中提到的方式相同，在節(jié)點(diǎn)擁有這條日志之后，不需要等待它 commit，就讓它立刻生效，在 Raft 中沒有 commit 的日志是有被覆蓋的可能的，因此才需要記錄上下文，如果日志被覆蓋，就能夠通過這個上下文來回退本次修改。 Follower 處理成員變更 對于 Follower 節(jié)點(diǎn)，成員變革的主要邏輯發(fā)生在 handle_append_entries 中，這個方法被用來處理 Leader 發(fā)送的日志，其中就包括 conf change

pub(super)fnhandle_append_entries(
&self,
term:u64,
leader_id:ServerId,
prev_log_index:LogIndex,
prev_log_term:u64,
entries:Vec>,
leader_commit:LogIndex,
)->Result{
//...
//appendlogentries
letmutlog_w=self.log.write();
let(cc_entries,fallback_indexes)=log_w
.try_append_entries(entries,prev_log_index,prev_log_term)
.map_err(|_ig|(term,log_w.commit_index+1))?;
//fallbackoverwrittenconfchangeentries
foridxinfallback_indexes.iter().sorted().rev(){
letinfo=log_w.fallback_contexts.remove(idx).unwrap_or_else(||{
unreachable!("fall_back_infosshouldcontaintheentryneedtofallback")
});
letEntryData::ConfChange(refconf_change)=info.origin_entry.entry_dataelse{
unreachable!("theentryinthefallback_infoshouldbeconfchangeentry");
};
letchanges=conf_change.clone();
self.fallback_conf_change(changes,info.addrs,info.name,info.is_learner);
}
//applyconfchangeentries
foreincc_entries{
letEntryData::ConfChange(refcc)=e.entry_dataelse{
unreachable!("cc_entryshouldbeconfchangeentry");
};
let(addrs,name,is_learner)=self.apply_conf_change(cc.clone());
let_ig=log_w.fallback_contexts.insert(
e.index,
FallbackContext::clone(&e),addrs,name,is_learner),
);
}
//...
}

對于常規(guī)日志的處理此處直接省略，不再贅述。Follower 在嘗試追加 Leader 發(fā)來的日志時(shí)，會判斷當(dāng)前節(jié)點(diǎn)上有哪些新的 conf change 日志，以及哪些沒有被 commit 的 conf change 會被覆蓋，然后通過預(yù)先記錄的上下文，將被覆蓋的變更逆序回退，并且應(yīng)用新的變更，在應(yīng)用新變更時(shí)，也需要在此處記錄新變更的上下文。 成員變更日志的 commit

asyncfnworker_as,RC:RoleChange>(
entry:Arc>,
prepare:Option,
ce:&CE,
curp:&RawCurp,
)->bool{
//...
letsuccess=matchentry.entry_data{
EntryData::ConfChange(refconf_change)=>{
//...
letshutdown_self=
change.change_type()==ConfChangeType::Remove&&change.node_id==id;
//...
ifshutdown_self{
curp.shutdown_trigger().self_shutdown();
}
true
}
_=>//...
};
ce.trigger(entry.inflight_id(),entry.index);
success
}

在 Conf change 被 commit 之后的 after sync 階段，除了一些常規(guī)操作以外，還需要判斷被 commit 的 conf change是否將當(dāng)前節(jié)點(diǎn) remove，如果這個節(jié)點(diǎn)被 remove 的話，就需要在此處開始 shutdown 當(dāng)前節(jié)點(diǎn)，一般只有 leader 節(jié)點(diǎn)會執(zhí)行到此處并將 remove 自身的日志 commit，在其 shutdown 自身后，剩余節(jié)點(diǎn)會選出一個擁有最新日志的 leader。 New Node 加入集群 為了區(qū)分創(chuàng)建新集群運(yùn)行的節(jié)點(diǎn)，和新啟動的需要加入現(xiàn)有集群的節(jié)點(diǎn)，需要在啟動時(shí)傳入一個新的參數(shù) `InitialClusterState`，這是一個枚舉類型，只有兩個成員， `InitialClusterState::New` 表示本次啟動的節(jié)點(diǎn)是新啟動集群的成員之一；`InitialClusterState::Existing` 表示本次啟動的節(jié)點(diǎn)是要加入已有集群的新節(jié)點(diǎn)。

letcluster_info=match*cluster_config.initial_cluster_state(){
InitialClusterState::New=>init_cluster_info,
InitialClusterState::Existing=>get_cluster_info_from_remote(
&init_cluster_info,
server_addr_str,
&name,
Duration::from_secs(3),
)
.await
.ok_or_else(||anyhow!("Failedtogetclusterinfofromremote"))?,
_=>unreachable!("xlineonlysupportstwoinitialclusterstates:new,existing"),
};

這兩種方式的本質(zhì)區(qū)別在于，新建集群是各節(jié)點(diǎn)初始的集群成員是相同的，可以直接通過這部分初始信息各自計(jì)算出一個全局統(tǒng)一的節(jié)點(diǎn) ID，保證每個節(jié)點(diǎn)都有一個唯一 ID，而加入現(xiàn)有集群時(shí)，新節(jié)點(diǎn)不能自己計(jì)算節(jié)點(diǎn)的 ID，需要通過 get_cluster_info_from_remote 方法去拉取現(xiàn)有集群的信息，直接繼承現(xiàn)有集群正在使用的 ID 和其他信息，以保證集群內(nèi) ID 和節(jié)點(diǎn)的對應(yīng)關(guān)系，避免出現(xiàn) ID 重復(fù)或一個節(jié)點(diǎn)有多個 ID 的情況。 為保證與 etcd 接口的兼容，新節(jié)點(diǎn)開始運(yùn)行前時(shí)沒有 name 的，etcdctl 中會根據(jù) name 是否為空來判斷相應(yīng)節(jié)點(diǎn)是否已啟動，在新節(jié)點(diǎn)啟動并加入集群后，會向 Leader 發(fā)送一個 Publish Rpc，用來在集群內(nèi)發(fā)布自己的 name。 Node remove 假設(shè)我們在 remove 一個節(jié)點(diǎn)之后，不將其關(guān)閉，那么它將會選舉超時(shí)并向其余節(jié)點(diǎn)發(fā)送 Vote 請求，浪費(fèi)其他節(jié)點(diǎn)的網(wǎng)絡(luò)和 CPU 資源，想要解決這個問題，首先能想到的有兩個辦法：

在節(jié)點(diǎn)應(yīng)用會 remove 自身的新配置后，立刻關(guān)閉自身節(jié)點(diǎn)。很明顯，這種方案一定是不可行的，因?yàn)樵趹?yīng)用新配置時(shí)，這一條日志還沒有被 commit，還有被回退的可能，如果在此處關(guān)閉自身，那假如配置變更發(fā)生了回退，被 remove 的這個節(jié)點(diǎn)就已經(jīng)被關(guān)閉無法直接回復(fù)了，這不是我們想看到的結(jié)果。

在節(jié)點(diǎn) commit 會 remove 自身的日志后，立刻關(guān)閉自身節(jié)點(diǎn)。因?yàn)橐呀?jīng)被 commit，所以這種方法時(shí)沒有上述問題的，但是據(jù)此實(shí)現(xiàn)后就會發(fā)現(xiàn)，被 remove 的節(jié)點(diǎn)有時(shí)還是不能自動關(guān)閉。因?yàn)楸?remove 的節(jié)點(diǎn)可能根本不會 commit 新配置，假設(shè)我們要 remove 一個 Follower 節(jié)點(diǎn)，Leader 講這一條 remove 記錄添加到自己的日志之后，立刻開始使用新日志，此時(shí) Leader 已經(jīng)不會向這個 Follower 發(fā)送任何請求了，F(xiàn)ollower 自然也不可能commit 這條日志并關(guān)閉自身。這個問題在 Leader 上是不存在的，Leader 將會臨時(shí)管理不包含自己的集群，直到日志被 commit。

最直接的方法都不能使用，那被 remove 的節(jié)點(diǎn)應(yīng)該如何關(guān)閉自身呢？假設(shè)我們不添加這里的關(guān)閉邏輯，會發(fā)生什么事？Leader 向集群同步 conf change 日志，新集群的所有成員都會正常處理并 commit 這條日志，被 remove 的節(jié)點(diǎn)會在自己不知情的請款下離開原集群，收不到 Leader 的心跳，這個節(jié)點(diǎn)就會超時(shí)并開始選舉，這里也就是我們最終我們決定修改的位置。

pub(super)fnhandle_pre_vote(
&self,
term:u64,
candidate_id:ServerId,
last_log_index:LogIndex,
last_log_term:u64,
)->Result<(u64,?Vec>),Option>{
//...
letcontains_candidate=self.cluster().contains(candidate_id);
letremove_candidate_is_not_committed=
log_r
.fallback_contexts
.iter()
.any(|(_,ctx)|matchctx.origin_entry.entry_data{
EntryData::ConfChange(refcc)=>cc.iter().any(|c|{
matches!(c.change_type(),ConfChangeType::Remove)
&&c.node_id==candidate_id
}),
_=>false,
});
//extrachecktoshutdownremovednode
if!contains_candidate&&!remove_candidate_is_not_committed{
returnErr(None);
}
//...
}

我們在 ProVote 階段加入了額外的檢查邏輯，收到 pre-vote 的節(jié)點(diǎn)會檢查 candidate 是否已經(jīng)被 Remove，假設(shè) candidate 不在當(dāng)前節(jié)點(diǎn)的配置中，并且可能會進(jìn)行的回退操作，也不會讓這個節(jié)點(diǎn)重新加入集群，那就說明這是一個已經(jīng)被 Remove 的 candidate，此時(shí)處理請求的節(jié)點(diǎn)將會給 Follower 回復(fù)一個帶有 shutdown_candidate 字段的特殊 VoteResponse。Candidate 在收到該響應(yīng)后，會判斷 shutdown_candidate 是否為 true，為 true 則開始關(guān)閉自身，不為 true則繼續(xù)選舉流程。

05

總結(jié)

本篇文章我們深入探討了在分布式系統(tǒng)中如何進(jìn)行集群成員變更，簡單介紹了兩種主要的解決方案：Joint Consensus 和單步成員變更，Joint Consensus 通過引入中間狀態(tài)來保證變更期間不會出現(xiàn)兩個 Leader，單步集群變更則是犧牲了一定的功能，通過逐個變更節(jié)點(diǎn)來簡化實(shí)現(xiàn)邏輯。并且對 Xline 目前使用的單步成員變更方案進(jìn)行了源碼級的分析，展示了 Leader 和 Follower 都是如何處理變更的，以及引入集群變更之后，會有哪些新邏輯需要處理。 目前 Xline 對集群成員變更的處理僅使用了單步集群變更這一種方法，提供了基本的變更能力，未來我們還會嘗試支持 Joint Consensus，增強(qiáng) Xline 的功能。

審核編輯：黃飛