本文是Paxos三部曲的第三篇，在前一篇文章 ?Paxos第二篇 - 使用Multi-Paxos協(xié)議的日志同步與恢復(fù) ?中，我們討論了基于Multi-Paxos協(xié)議的日志同步方案，在這個(gè)方案中，我們有一個(gè)隱含的前提，就是Paxos成員組是確定的，并且所有成員啟動(dòng)后都能加載一致的成員組信息。而在實(shí)際的工程應(yīng)用中，往往需要在不停服務(wù)的情況下修改成員組，最典型的比如類似spanner的系統(tǒng)，對(duì)子表的遷移操作過(guò)程，就包含了對(duì)其Paxos成員組的變更操作。本文將基于Raft論文，討論通用的成員組變更方法，和簡(jiǎn)化的一階段成員組變更方法，以及成員組變更與日志同步操作的關(guān)系。

請(qǐng)注意，本文假設(shè)讀者已了解Basic-Paxos和Multi-Paxos協(xié)議，并且本文假設(shè)集群工作在上一篇文章所述的Multi-Paxos協(xié)議之下。

• 在線成員組變更的難點(diǎn)

Paxos執(zhí)行兩階段投票協(xié)議的前提是有一個(gè)明確的Paxos成員組，而對(duì)于完全無(wú)中心化的Paoxs協(xié)議來(lái)說(shuō)，成員組的內(nèi)容本身又需要通過(guò)Paxos協(xié)議來(lái)維護(hù)一致性。對(duì)于變更后的新成員組從什么時(shí)機(jī)開(kāi)始生效，存在“先有雞還是先有蛋”的問(wèn)題，如果還像同步普通日志一樣來(lái)同步新成員組，那么在新舊成員組交接的過(guò)程中宕機(jī)，則可能出現(xiàn)選票分裂的情況，比如由成員組ABC變更為ABCDE過(guò)程中宕機(jī)，AB未持久化新成員組，CED已持久化新成員組，那么在宕機(jī)重啟后，會(huì)出現(xiàn)AB形成了舊成員組的多數(shù)派，而CDE形成了新成員組的多數(shù)派，會(huì)出現(xiàn)兩個(gè)leader的情況。

因此我們可以總結(jié)對(duì)在線成員組變更方案的幾個(gè)基本要求：

P1. 成員組正常Paxos日志同步服務(wù)不中斷

P2. 任何情況下宕機(jī)都能夠保證存活的多數(shù)派成員間能夠選舉leader

P3. 不會(huì)出現(xiàn)1個(gè)以上的多數(shù)派選出大于1個(gè)leader的情況

• 成員組變更的基本思路

成員組變更代表了“舊朝代”的結(jié)束和“新朝代”的開(kāi)啟，可以理解為依次執(zhí)行如下兩個(gè)投票操作：

Pa. “舊朝代”的多數(shù)派成員對(duì)“舊朝代結(jié)束”這件事達(dá)成一致，達(dá)成一致后舊成員組不再投票

Pb. “新朝代”的多數(shù)派成員對(duì)“新朝代開(kāi)啟”這件事達(dá)成一致，達(dá)成一致后新成員組開(kāi)始投票

但是簡(jiǎn)單的按照這種兩階段的操作進(jìn)行成員變更，雖然能夠保證上述P3的約束，但是無(wú)法滿足P1和P2，比如Pa執(zhí)行成功后，在Pb執(zhí)行成功之前：沒(méi)有成員組可以投票，服務(wù)會(huì)中斷；如果集群宕機(jī)重啟，新的成員組的各個(gè)成員由于還未對(duì)新成員組達(dá)成一致，而無(wú)法選出leader。

為了保證P1和P2的約束，我們?cè)谏鲜龌境蓡T變更的基礎(chǔ)上，將Pa和Pb合并為一步操作，即新舊成員組一起對(duì)“舊朝代結(jié)束+新朝代開(kāi)啟”這件事達(dá)成一致后，才表示成員組變更成功。在開(kāi)始成員變更的投票后，集群就進(jìn)入了一個(gè)“中間狀態(tài)”，在這個(gè)過(guò)程中宕機(jī)恢復(fù)后可能退回“舊朝代”也可能進(jìn)入“新朝代”，因此在這個(gè)中間狀態(tài)過(guò)程中投票的日志，要求在新舊成員組中都達(dá)成一致。

在這個(gè)基本思路的指導(dǎo)下，可以抽象出一個(gè)通用的成員變更方法：Jonit-Consensus。

• 通用成員組變更方法–Joint-Consensus

Joint-Consensus是Raft論文中提到的兩階段成員變更方案，這個(gè)方案比較通用，甚至可以做到完整的成員組替換，但是兩階段方案的工程實(shí)現(xiàn)都比較復(fù)雜，而通用的場(chǎng)景需求又不多，因此在他博士論文最終版的成員變更一章中，更多篇幅分析了簡(jiǎn)化的一階段方案（下一節(jié)討論），而把Joint-Consensus的篇幅省略了很多。但是作為成員變更方案的基礎(chǔ)，我這里還是希望能夠從Joint-Consensus開(kāi)始，分析它的正確性，并且嘗試推導(dǎo)出一階段的成員變更方法。

Joint-Consensus的方案如下，設(shè)成員變更前的成員組為C(old)，變更后的成員組為C(new)，成員組內(nèi)容中包含單調(diào)增長(zhǎng)的Version。

• • 變更操作

• 成員變更操作前，C(old)的多數(shù)派中持久化的成員組為[[C(old)]]
• 成員變更操作由leader執(zhí)行，leader收到命令后，將成員組[[C(old),C(new)]]發(fā)送給C(old)∪C(new)的所有成員，在此之后新的日志同步需要保證得到C(old)和C(new)兩個(gè)多數(shù)派的確認(rèn)
• leader收到C(old)和C(new)兩個(gè)多數(shù)派確認(rèn)后，將成員組[[C(new)]]發(fā)送給C(new)的所有成員，收到C(new)多數(shù)派確認(rèn)后，表示成員變更成功，后續(xù)的日志只要得到C(new)多數(shù)派確認(rèn)即可

• • 協(xié)議約束

• Version投票約束：持有Version較大的成員，不能給持有Version較小的候選人投票
• 最大commit原則：

• 持有[[C(old),C(new)]]的成員當(dāng)選leader后，要重新對(duì)[[C(old),C(new)]]分別在C(old)和C(new)內(nèi)投票達(dá)成多數(shù)派，然后繼續(xù)成員變更流程，對(duì)[[C(new)]]在C(new)內(nèi)投票達(dá)成多數(shù)派。然后才能開(kāi)始leader恢復(fù)流程和leader服務(wù)
• 持有[[C(old)]]的成員當(dāng)選leader后，要重新對(duì)[[C(old)]]在C(old)內(nèi)投票達(dá)成多數(shù)派，然后才能開(kāi)始leader恢復(fù)流程和leader服務(wù)
• 持有[[C(new)]]的成員當(dāng)選leader后，要重新對(duì)[[C(new)]]在C(new)內(nèi)投票達(dá)成多數(shù)派，然后才能開(kāi)始leader恢復(fù)流程和leader服務(wù)

• • • 選主投票原則

持有[[C(old),C(new)]]的候選人要得到C(old)和C(new)兩個(gè)多數(shù)派都確認(rèn)，才能當(dāng)選leader

持有[[C(old)]]的候選人要得到C(old)多數(shù)派確認(rèn)，才能當(dāng)選leader

持有[[C(new)]]的候選人要得到C(new)多數(shù)派確認(rèn)，才能當(dāng)選leader

• Joint-Consensus的協(xié)議分析

• 成員變更過(guò)程中，對(duì)[[C(old),C(new)]]的投票要求在C(old)和C(new)中都得到多數(shù)派的確認(rèn)，是為了保證在C(old)投票“舊朝代結(jié)束”成功的同時(shí)，“新朝代開(kāi)啟”能夠在C(new)生效，不會(huì)出現(xiàn)服務(wù)中斷或者宕機(jī)重啟后無(wú)法選出leader的情況。
• 對(duì)于成員變更的第二步，在[[C(old),C(new)]]形成兩個(gè)多數(shù)派確認(rèn)后，還要對(duì)[[C(new)]]在C(new)中進(jìn)行投票，是為了結(jié)束需要向C(old)和C(new)都同步數(shù)據(jù)的“中間狀態(tài)”。[[C(new)]]得到C(new)的多數(shù)派確認(rèn)后，由于后面將要提到的“Version投票約束”原則的保證，可以確保后續(xù)宕機(jī)重啟只有C(new)中的成員能夠當(dāng)選leader，因此無(wú)需再向C(old)同步數(shù)據(jù)。
• Version投票約束，實(shí)際上是Paxos協(xié)議Prepare階段對(duì)ProposalID的約束，如本系列的前一篇Multi-Paxos一文所述，選主過(guò)程本質(zhì)上是Paoxs的Prepare過(guò)程，我們將成員組內(nèi)容視為Paxos提案，那么Version就是ProposalID，Paxos不允許Prepare階段應(yīng)答ProposalID更低的提案，所以我們要求持有較大Version的成員不能給持有較小Version的候選人投票。從直觀上來(lái)分析，Version投票約束可以保證，在[[C(new)]]形成多數(shù)派確認(rèn)后，C(old)中那些錯(cuò)過(guò)了成員變更日志的成員，不可能再得到C(old)多數(shù)派的選票。
• 最大commit原則，是Paxos最重要的隱含規(guī)則之一，在成員變更過(guò)程中的宕機(jī)重啟，持有[[C(old),C(new)]]的成員可能當(dāng)選leader，但是[[C(old),C(new)]]可能并未形成多數(shù)派，根據(jù)成員變更協(xié)議，成員變更過(guò)程要在[[C(old),C(new)]]形成兩個(gè)多數(shù)派確認(rèn)后，才能對(duì)[[C(new)]]進(jìn)行投票。否則如果立即對(duì)[[C(new)]]進(jìn)行投票，宕機(jī)重啟后，可能出現(xiàn)C(old)和C(new)兩個(gè)投票組各自選出一個(gè)leader。因此，持有[[C(old),C(new)]]的成員當(dāng)選leader后，無(wú)論[[C(old),C(new)]]是否已經(jīng)形成兩個(gè)成員組的多數(shù)派確認(rèn)，我們都按照最大commit原則對(duì)它重新投票確認(rèn)形成多數(shù)派后，才能繼續(xù)leader后續(xù)的上任處理。
• 選主投票原則，持有[[C(old),C(new)]]的成員當(dāng)選leader，需要得到C(old)和C(new)兩個(gè)多數(shù)派都確認(rèn)，是為了避免C(old)與C(new)各自形成多數(shù)派選出兩個(gè)leader的情況。在成員變更過(guò)程中，可以歸結(jié)為如下兩種情況：

• 對(duì)[[C(old),C(new)]]的投票已開(kāi)始，但未形成兩個(gè)多數(shù)派確認(rèn)，集群宕機(jī)。那么重啟選主時(shí)，要么持有[[C(old)]]的成員當(dāng)選leader，要么持有[[C(old),C(new)]]的成員當(dāng)選leader。
• 對(duì)[[C(new)]]的投票已開(kāi)始，但未形成多數(shù)派確認(rèn)，集群宕機(jī)。那么重啟選主時(shí)，要么持有[[C(new)]]的成員當(dāng)選leader，要么持有[[C(old),C(new)]]的成員當(dāng)選leader。

如上文所述，持有[[C(old),C(new)]]的leader要先完成成員變更流程。之后再執(zhí)行Multi-Paxox中的日志“重確認(rèn)”，因此日志“重確認(rèn)”過(guò)程不會(huì)進(jìn)入“要得到兩個(gè)成員組確認(rèn)”的情況。

Joint-Consensus允許C(old)與C(new)交集為空，在這種情況下成員變更后，舊leader要卸任，并且將leader權(quán)限轉(zhuǎn)讓給確認(rèn)[[C(new)]]的一個(gè)多數(shù)派成員。

Joint-Consensus方案比較通用且容易理解，但是實(shí)現(xiàn)比較復(fù)雜，同時(shí)兩階段的變更協(xié)議也會(huì)在一定程度上影響變更過(guò)程中的服務(wù)可用性，因此我們期望增強(qiáng)成員變更的限制，以簡(jiǎn)化操作流程，考慮Joint-Consensus成員變更，之所以分為兩個(gè)階段，是因?yàn)閷?duì)C(old)與C(new)的關(guān)系沒(méi)有做任何假設(shè)，為了避免C(old)和C(new)各自形成多數(shù)派選出兩個(gè)leader，才引入了兩階段方案。因此如果增強(qiáng)成員組變更的限制，假設(shè)C(old)與C(new)任意的多數(shù)派交集不為空，這兩個(gè)成員組就無(wú)法各自形成多數(shù)派，那么成員變更方案就可能簡(jiǎn)化為一階段。

• 一階段成員變更方法

Raft作者在他博士論文最終版的成員變更一章中，簡(jiǎn)化了Joint-Consensus的篇幅，而著重介紹了一階段的成員變更方法，在工程上一階段的成員變更方法確實(shí)更簡(jiǎn)單實(shí)用，下面是我對(duì)一階段成員變更方案的一些分析。

• • 每次只變更一個(gè)成員

如上一節(jié)所述，如果做到C(old)與C(new)任意的多數(shù)派交集都不為空，那么即可保證C(old)與C(new)無(wú)法各自形成多數(shù)派投票。方法就是每次成員變更只允許增加或刪除一個(gè)成員。假設(shè)C(old)的成員數(shù)為N，分析如下：

• • • C(new)成員數(shù)為N+1
    • 假設(shè)選出的leader持有C(new)，那么一定是C(new)中有多數(shù)派，即(N+1)/2+1的成員給leader投票，那么持有C(old)且未給leader投票的成員最多為(N+1)-((N+1)/2+1)=(N-1)/2，這個(gè)值小于C(old)的多數(shù)派值N/2+1，無(wú)法選出leader
    • 假設(shè)選出的leader持有C(old)，那么一定是C(old)中有多數(shù)派，即N/2+1的成員給leader投票，那么持有C(new)且未給leader投票的成員最多為(N+1)-(N/2+1)=N/2，這個(gè)值小于C(new)的多數(shù)派值(N+1)/2+1，無(wú)法選出leader
    • C(new)成員數(shù)為N-1
    • 假設(shè)選出的leader持有C(new)，那么一定是C(new)中有多數(shù)派，即(N-1)/2+1的成員給leader投票，那么持有C(old)且未給leader投票的成員最多為N-((N-1)/2+1)=(N-1)/2，這個(gè)值小于C(old)的多數(shù)派值N/2+1，無(wú)法選出leader
    • 假設(shè)選出的leader持有C(old)，那么一定是C(old)中有多數(shù)派，即N/2+1的成員給leader投票，那么持有C(new)且未給leader投票的成員最多為N-(N/2+1)=(N-2)/2，這個(gè)值小于C(new)的多數(shù)派值(N-1)/2+1，無(wú)法選出leader

• • 啟用新成員組的時(shí)機(jī)

啟用新成員組的時(shí)機(jī)是指從何時(shí)開(kāi)始，對(duì)日志的投票開(kāi)始使用C(new)進(jìn)行，這里需要考慮的問(wèn)題是成員變更過(guò)程中宕機(jī)，重啟選主后，持有[[C(old)]]的成員被選為leader，在宕機(jī)前使用C(new)同步的日志是否可能丟失。分析如下幾種情況：

• • • 下線成員，C(new)與C(old)多數(shù)派成員數(shù)相同，比如ABCDE變更為ABCD，C(new)的任意多數(shù)派集合一定是C(old)的某個(gè)多數(shù)派，變更過(guò)程中使用C(new)同步的日志，在C(old)中依然能夠保持多數(shù)派。
    • 下線成員，C(new)的多數(shù)派成員數(shù)小于C(old)，比如ABCD變更為ABC，這個(gè)情況比較特殊，我們來(lái)仔細(xì)分析，這種情況下在C(new)中形成的多數(shù)派成員只能達(dá)到C(old)成員數(shù)的一半，從嚴(yán)格的Basic-Paxos協(xié)議來(lái)分析，只做到N/2的成員確認(rèn)，是不能保證決議持久化的。但是我們放在Multi-Paxos的環(huán)境中，使用lease機(jī)制保證leader有效（leader“有效”的意思是：StartWorking日志已形成多數(shù)派，且完成日志“重確認(rèn)”，參考上一篇《使用Multi-Paxos協(xié)議的日志同步與恢復(fù)》）的前提下，因?yàn)椴粫?huì)有1個(gè)以上的成員并發(fā)提出議案，同時(shí)又因?yàn)樵贜為偶數(shù)時(shí)，N/2的成員集合與N/2+1的成員集合的交集一定不為空，可以分析出：在leader?有效?的前提下，只要N/2（N為偶數(shù)）的成員確認(rèn)，即可保證數(shù)據(jù)持久化。因此，在這種情況下，在C(new)形成多數(shù)派的日志，宕機(jī)重啟后，在C(old)中可以被多數(shù)派“重確認(rèn)”，不會(huì)丟失。
    • 上線成員，C(new)的多數(shù)派成員數(shù)大于C(old)，比如ABC變更為ABCD，C(new)的任意多數(shù)派集合一定包含了C(old)的某個(gè)多數(shù)派，變更過(guò)程中使用C(new)同步的日志，在C(old)中依然能夠保持多數(shù)派。
    • 上線成員，C(new)與C(old)多數(shù)派成員數(shù)相同，比如ABCD變更為ABCDE，某些情況下可能產(chǎn)生C(new)的多數(shù)派（如ABE）與C(old)的多數(shù)派（如AB）交集只達(dá)到C(old)的一半，情況與第2點(diǎn)相同。

• 最大commit原則

這里的最大commit原則體現(xiàn)在，同步[[C(new)]]的過(guò)程中集群宕機(jī)，持有[[C(new)]]的成員當(dāng)選leader，重啟后無(wú)法確認(rèn)當(dāng)前多數(shù)派持有的成員組是[[C(new)]]還是[[C(old)]]，需要leader將當(dāng)前持有的成員組重新投票形成多數(shù)派確認(rèn)后，才能開(kāi)始leader后續(xù)的上任處理。否則可能出現(xiàn)連續(xù)變更情況下，成員組分裂選出2個(gè)leader的情況，如Raft報(bào)出的這個(gè)bug，https://groups.google.com/forum/#!topic/raft-dev/t4xj6dJTP6E，修正方法也很簡(jiǎn)單就是實(shí)用最大commit原則，對(duì)成員組重新投票得到多數(shù)派確認(rèn)。

• • 階段成員變更方案總結(jié)

成員變更限制每次只能增加或刪除一個(gè)成員

成員變更由有效的leader發(fā)起，確認(rèn)新的成員組得到多數(shù)派確認(rèn)后，返回成員變更成功

一次成員變更成功前不允許開(kāi)始下一次成員變更,因此新任leader在開(kāi)始提供服務(wù)前要將自己本地保存的最新成員組重新投票形成多數(shù)派確認(rèn)

leader只要開(kāi)始同步新成員組后，即可開(kāi)始使用新的成員組進(jìn)行日志同步

成員組實(shí)用Version標(biāo)記，持有更大Version的成員不能給持有較小Version的成員投票

• 成員組變更與日志同步

  • Log Barrier

對(duì)于下線成員的場(chǎng)景，我們需要保證所有日志在剩余在線的機(jī)器上能夠形成多數(shù)派備份，否則可能丟失日志。比如下面的場(chǎng)景，logID為2的日志，在連續(xù)成員變更后，僅A上有，無(wú)法在A/B/C上形成多數(shù)派:

因此我們要求leader在持久化新的成員組時(shí)，要像普通日志一樣為它分配logID（稱為成員變更日志），它是一個(gè)“單向barrier”，即要求所有成員保證logID小于它的日志都持久化本地后，才能持久化成員變更日志，而logID大于它的日志則不受此約束。在上面的例子中,要求B/C保證在持久化?Cnew1之前,一定先保證2號(hào)日志持久化

總結(jié)

以上是生活随笔為你收集整理的Paxos第三篇 - Paxos成员组变更的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。