[[428425]]

一 引言

分布式系統(tǒng)運(yùn)行過(guò)程中節(jié)點(diǎn)經(jīng)常會(huì)出現(xiàn)故障，需要支持節(jié)點(diǎn)的動(dòng)態(tài)增加、刪除和替換。

成員變更是分布式系統(tǒng)繞不開(kāi)的話題，特別是在一致性系統(tǒng)中，對(duì)于提升運(yùn)維能力和服務(wù)可用性都有很大的幫助。

Raft提出的兩階段成員變更Joint Consensus是業(yè)界主流的成員變更方法，極大的推動(dòng)了成員變更的工程應(yīng)用。但Joint Consensus成員變更采用兩階段，一次變更需要提議兩條日志， 在一些系統(tǒng)中直接使用時(shí)有些不便。雖然Raft也提出了單步成員變更方法，但單步成員變更方法一次只能增加或減少一個(gè)成員，限制較大，并且容易踩坑，一般不推薦使用。

那么很自然的想到，Joint Consensus成員變更能否只使用單步實(shí)現(xiàn)呢?本文對(duì)這個(gè)問(wèn)題進(jìn)行了深入探討。

二 成員變更

我們先來(lái)回顧下一致性協(xié)議中的成員變更問(wèn)題。成員變更是在集群運(yùn)行過(guò)程中改變運(yùn)行一致性協(xié)議的節(jié)點(diǎn)，如增加、減少節(jié)點(diǎn)、節(jié)點(diǎn)替換等。成員變更過(guò)程不能影響系統(tǒng)的可用性。

成員變更也是一個(gè)一致性問(wèn)題，即所有節(jié)點(diǎn)對(duì)成員配置達(dá)成一致。但是成員變更又有其特殊性，因?yàn)樵诔蓡T變更的過(guò)程中，參與投票的成員會(huì)發(fā)生變化。

圖1 成員變更的某一時(shí)刻Cold和Cnew中同時(shí)存在兩個(gè)不相交的多數(shù)派

如果將成員變更當(dāng)成一般的一致性問(wèn)題，成員變更過(guò)程中，各節(jié)點(diǎn)從舊成員配置Cold切換到新成員配置Cnew的時(shí)刻可能有差異，可能在某一時(shí)刻Cold和Cnew中同時(shí)存在兩個(gè)不相交的多數(shù)派，形成雙Quorum，破壞一致性。

為了解決這個(gè)問(wèn)題，Raft提出了兩階段的成員變更方法Joint Consensus。

1 Joint Consensus成員變更

Joint Consensus成員變更為了避免雙Quorum問(wèn)題，引入一個(gè)聯(lián)合成員配置Cold,new作為過(guò)渡配置， Cold,new是Cold和Cnew的組合。Cold與Cold,new的Quorum有交集，Cold,new與Cnew的Quorum也有交集。成員變更先從Cold切換到Cold,new，待Cold,new提交后，再切換到Cnew，保證Cold與Cnew不同時(shí)使用，因而不會(huì)形成雙Quorum，保障安全性。

圖2 Cold與Cold, new與Cnew三者的Quorum集合之間的關(guān)系

Joint Consensus使用兩條日志完成成員變更過(guò)程。Leader收到成員變更請(qǐng)求后，先向Cold和Cnew同步一條Cold,new日志，此后所有日志都需要Cold和Cnew兩個(gè)多數(shù)派的確認(rèn)。Cold,new日志在Cold和Cnew都達(dá)成多數(shù)派之后才能提交，此后Leader再向Cold和Cnew同步一條只包含Cnew的日志，此后日志只需要Cnew的多數(shù)派確認(rèn)。Cnew日志只需要在Cnew達(dá)成多數(shù)派即可提交，此時(shí)成員變更完成，不在Cnew中的成員自動(dòng)下線。

 圖3 Joint Consensus成員變更過(guò)程

成員變更過(guò)程中如果發(fā)生Failover，老Leader宕機(jī)，Cold,new中任意節(jié)點(diǎn)都可能成為新Leader，如果新Leader上沒(méi)有Cold,new日志，則繼續(xù)使用Cold，F(xiàn)ollower上如果有Cold,new日志會(huì)被新Leader截?cái)啵赝说紺old，成員變更失敗;如果新Leader上有Cold,new日志，則繼續(xù)將未完成的成員變更流程走完。

2 單步成員變更

Joint Consensus成員變更之所以需要兩個(gè)階段，是因?yàn)閷?duì)Cold與Cnew的關(guān)系沒(méi)有做任何假設(shè)，為了避免Cold和Cnew各自形成不相交的多數(shù)派而形成雙Quorum，才引入了兩階段方案。

如果增強(qiáng)成員變更的限制，假設(shè)Cold與Cnew的Quorum交集不為空，Cold與Cnew就無(wú)法形成雙Quorum，則成員變更就可以簡(jiǎn)化為一階段。

實(shí)現(xiàn)單步的成員變更，關(guān)鍵在于限制Cold與Cnew，使Cold與Cnew的Quorum交集不為空。那么怎么樣限制Cold與Cnew，才能使Cold與Cnew的Quorum交集不為空呢?方法就是每次成員變更只允許增加或刪除一個(gè)成員。

圖4 增加或刪除一個(gè)成員時(shí)Cold與Cnew的Quorum

增加或刪除一個(gè)成員時(shí)的情形，如圖4所示，可以從數(shù)學(xué)上嚴(yán)格證明，只要每次只允許增加或刪除一個(gè)成員，Cold與Cnew不可能形成兩個(gè)不相交的Quorum。因此只要每次只增加或刪除一個(gè)成員，從Cold可直接切換到Cnew，無(wú)需過(guò)渡成員配置，實(shí)現(xiàn)單步成員變更。

單步成員變更一次只能變更一個(gè)成員，如果需要變更多個(gè)成員，如實(shí)現(xiàn)替換成員等，可以通過(guò)執(zhí)行多次單步成員變更來(lái)實(shí)現(xiàn)。

單步成員變更理論雖然簡(jiǎn)單，但卻埋了很多坑，實(shí)際用起來(lái)并不是那么簡(jiǎn)單。先前的文章Raft成員變更的工程實(shí)踐中有詳細(xì)介紹。

三 兩階段成員變更的單步實(shí)現(xiàn)

Joint Consensus成員變更雖然通用但是采用兩階段，一次變更需要提交兩條日志，單步成員變更雖然只需要提交一條日志，但是限制較大，一次只能變更一個(gè)成員。兩者的優(yōu)勢(shì)能否結(jié)合呢?Joint Consensus成員變更能否只用單步實(shí)現(xiàn)呢?

Joint Consensus成員變更過(guò)程中，Cold,new日志的提交已經(jīng)讓各節(jié)點(diǎn)對(duì)Cnew配置達(dá)成了一致，那么Cnew日志有什么作用呢?能否在Cold,new日志提交后就從Cold,new配置切換到Cnew配置呢?這樣是不是就可以不需要Cnew日志，變成單步實(shí)現(xiàn)了呢?

考慮Joint Consensus成員變更中Cnew日志的作用，Cnew日志在Cold,new日志提交之后發(fā)起提議，節(jié)點(diǎn)收到并持久化Cnew日志后從Cold,new配置切換到Cnew配置，不在Cnew配置中的成員在Cnew日志提交后下線。根據(jù)這個(gè)過(guò)程，可以總結(jié)出Cnew日志的作用：

通知節(jié)點(diǎn)在收到并持久化Cnew日志后從Cold,new配置切換到Cnew配置。

通知不在Cnew配置中的節(jié)點(diǎn)在Cnew日志提交后下線。

成員變更過(guò)程中發(fā)生Failover后，本地有Cnew日志的節(jié)點(diǎn)具有優(yōu)先選舉權(quán)。

如果能不使用Cnew日志同時(shí)又完成Cnew日志的工作，不就可以用單步實(shí)現(xiàn)兩階段的Joint Consensus成員變更嗎?事實(shí)上已經(jīng)有系統(tǒng)探索過(guò)這條路。

1 ZooKeeper成員變更

ZooKeeper從3.5.0版本開(kāi)始在Zab的基礎(chǔ)上支持了成員變更。ZooKeeper具有Primary Order特性，而使用兩條日志的Joint Consensus成員變更無(wú)法保證Primary Order特性，為了既滿足成員變更的通用性，又不喪失Primary Order特性，ZooKeeper在論文《Dynamic Reconfiguration of Primary/Backup Clusters》中提出了自己的成員變更方法，并在ZooKeeper中應(yīng)用了此方法，比Raft的提出還早。

如圖5是ZooKeeper成員變更協(xié)議，圖中舊成員配置用S表示，新成員配置用S‘表示，P為L(zhǎng)eader節(jié)點(diǎn)，圖5展示了將B1和B2節(jié)點(diǎn)替換成B3和B4節(jié)點(diǎn)的過(guò)程：

圖5 ZooKeeper成員變更協(xié)議

• 為了讓新節(jié)點(diǎn)追上最新數(shù)據(jù)，新成員配置S’中的新節(jié)點(diǎn)B3、B4先連接到當(dāng)前的主節(jié)點(diǎn)P，P會(huì)向它們傳輸自己當(dāng)前的狀態(tài)作為他們的初始狀態(tài)。在Zab協(xié)議中當(dāng)備節(jié)點(diǎn)連接上主節(jié)點(diǎn)時(shí)這樣的狀態(tài)傳輸就會(huì)自動(dòng)發(fā)生，并且會(huì)繼續(xù)從主節(jié)點(diǎn)P接收所有后續(xù)的操作日志(例如圖中的Op1和Op2)，這個(gè)過(guò)程中節(jié)點(diǎn)B3、B4不參與投票。
• 主節(jié)點(diǎn)P向連接到它的所有備節(jié)點(diǎn)(S U S‘)發(fā)送成員變更日志COP，COP日志中攜帶舊成員配置S和新成員配置S‘，并等待舊成員配置S中的節(jié)點(diǎn)確認(rèn)。一旦S中的多數(shù)派確認(rèn)了COP日志，就對(duì)S’達(dá)成了共識(shí)。
• 在COP日志之前的日志只需要舊成員配置S中的多數(shù)派確認(rèn)，可以在舊成員配置和新成員配置(S U S‘)中提交;在COP命令之后且在S’的激活消息ACTIVATE之前的日志需要新舊成員配置(S U S‘)兩個(gè)多數(shù)派確認(rèn)，并且只能在S’中提交;在S’的激活消息ACTIVATE后的日志，只需要在S‘中確認(rèn)和提交。
• 主節(jié)點(diǎn)P等待COP日志以及S'中COP之前的日志的確認(rèn)。
• 一旦新舊成員配置(S U S1)兩個(gè)多數(shù)派都確認(rèn)了COP日志，主節(jié)點(diǎn)P就提交COP日志，并廣播一條激活消息ACTIVATE來(lái)激活新成員配置S’從而完成成員變更。與日志同步消息類似，ACTIVATE消息包含主節(jié)點(diǎn)P的Epoch，攜帶過(guò)時(shí)的Epoch的ACTIVATE消息將被忽略。

成員變更過(guò)程中如果發(fā)生Failover，可能出現(xiàn)下面幾種情況：

如果在COP日志發(fā)送之前Failover，那么成員變更失敗，在舊成員配置中重新選主后繼續(xù)工作;

如果在COP日志發(fā)送之后并且在ACTIVATE之前Failover，新舊成員配置中任意節(jié)點(diǎn)都可能成為新Leader，如果新Leader上沒(méi)有COP日志，則成員變更失敗;如果新Leader上有COP日志，則繼續(xù)將未完成的成員變更流程走完。

如果在ACTIVATE后Failover，成員變更已經(jīng)完成，但還無(wú)法保證新Leader一定在新成員配置中，此時(shí)不在新成員配置中的節(jié)點(diǎn)還不能下線。因此在發(fā)送ACTIVATE消息后還需要在新成員配置中提交一條no-op日志，no-op日志提交后可保證新Leader一定在新成員配置中，不在新成員配置中的節(jié)點(diǎn)可以安全下線。

ZooKeeper利用異步的Commit消息，也即ACTIVATE消息來(lái)通知節(jié)點(diǎn)從新舊成員配置切換到新成員配置。使用異步的no-op日志讓不在新成員配置中的節(jié)點(diǎn)安全下線。ZooKeeper的ACTIVATE消息和異步的no-op日志起到了Joint Consensus成員變更中Cnew日志的作用。

2 改進(jìn)的單步實(shí)現(xiàn)

ZooKeeper成員變更協(xié)議不如Joint Consensus成員變更那么簡(jiǎn)潔，Joint Consensus成員變更通過(guò)兩階段可以利用協(xié)議本身而不需要做過(guò)多的限制來(lái)保證成員變更的安全性。那么ZooKeeper成員變更協(xié)議是否可以改進(jìn)呢?

ZooKeeper成員變更協(xié)議中異步的ACTIVATE消息和no-op日志其實(shí)就是為了完成Joint Consensus成員變更中Cnew日志的作用，明白了這一點(diǎn)后那么也可以將Joint Consensus成員變更的Cnew日志改為異步的，在Cold,new日志提交后就認(rèn)為成員變更完成，然后異步的提交Cnew日志。之所以可以將Cnew日志改為異步的，在Cold,new日志提交后就認(rèn)為成員變更完成，是因?yàn)镃old,new日志一旦提交，各節(jié)點(diǎn)已經(jīng)對(duì)新成員配置達(dá)成了一致，再也不會(huì)回退到舊成員配置了，剩下的過(guò)程最終一定會(huì)執(zhí)行完成，Cnew日志最終一定會(huì)提交。

還有一種改進(jìn)方法是繼續(xù)保留ACTIVATE消息，但不使用no-op日志，那么怎么樣保證切換到新成員配置的節(jié)點(diǎn)具有優(yōu)先選舉權(quán)呢?根據(jù)選舉的安全性，具有最新日志的節(jié)點(diǎn)具有優(yōu)先選舉權(quán)，那么可以在選舉的時(shí)候攜帶節(jié)點(diǎn)當(dāng)前的成員配置，在日志一樣新的情況下，優(yōu)先給已經(jīng)切換到新成員配置的節(jié)點(diǎn)投票，即可保證切換到新成員配置的節(jié)點(diǎn)具有優(yōu)先選舉權(quán)。新成員配置中的大多數(shù)節(jié)點(diǎn)切換到新成員配置后，不在新成員配置中的節(jié)點(diǎn)可以安全下線。

四 總結(jié)

Joint Consensus成員變更的提出極大的推動(dòng)了成員變更的工程應(yīng)用，其簡(jiǎn)潔優(yōu)美并且通用，但是采用兩階段，一次變更需要提交兩條日志。本文探討了兩階段的Joint Consensus成員變更的單步實(shí)現(xiàn)方法，并做了一些改進(jìn)，為成員變更的工程應(yīng)用提供了更多的選擇。

五 思考

為什么Cold,new日志提交后，Cnew日志最終一定會(huì)提交?

使用ACTIVATE消息讓節(jié)點(diǎn)切換到新成員配置后，如果節(jié)點(diǎn)重啟，如何保證繼續(xù)使用新成員配置?

兩階段成員變更的單步實(shí)現(xiàn)還有沒(méi)有其它實(shí)現(xiàn)方法?