Paxos成員組變更

01-29

本文是Paxos三部曲中的第三篇，在前一篇文章《使用Multi-Paxos協議的日誌同步與恢復》（[Paxos三部曲之二] 使用Multi-Paxos協議的日誌同步與恢復）中，我們討論了基於Multi-Paxos協議的日誌同步方案，在這個方案中，我們有一個隱含的前提，就是Paxos成員組是確定的，並且所有成員啟動後都能載入一致的成員組信息。而在實際的工程應用中，往往需要在不停服務的情況下修改成員組，最典型的比如類似spanner的系統，對子表的遷移操作過程，就包含了對其Paxos成員組的變更操作。本文將基於Raft論文，討論通用的成員組變更方法，和簡化的一階段成員組變更方法，以及成員組變更與日誌同步操作的關係。

請注意，本文假設讀者已了解Basic-Paxos和Multi-Paxos協議，並且本文假設集群工作在上一篇文章所述的Multi-Paxos協議之下。

在線成員組變更的難點

Paxos執行兩階段投票協議的前提是有一個明確的Paxos成員組，而對於完全無中心化的Paoxs協議來說，成員組的內容本身又需要通過Paxos協議來維護一致性。對於變更後的新成員組從什麼時機開始生效，存在「先有雞還是先有蛋」的問題，如果還像同步普通日誌一樣來同步新成員組，那麼在新舊成員組交接的過程中宕機，則可能出現選票分裂的情況，比如由成員組ABC變更為ABCDE過程中宕機，AB未持久化新成員組，CED已持久化新成員組，那麼在宕機重啟後，會出現AB形成了舊成員組的多數派，而CDE形成了新成員組的多數派，會出現兩個leader的情況。

因此我們可以總結對在線成員組變更方案的幾個基本要求：

P1. 成員組正常Paxos日誌同步服務不中斷

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

P3. 不會出現1個以上的多數派選出大於1個leader的情況

成員組變更的基本思路

成員組變更代表了「舊朝代」的結束和「新朝代」的開啟，可以理解為依次執行如下兩個投票操作：

Pa. 「舊朝代」的多數派成員對「舊朝代結束」這件事達成一致，達成一致後舊成員組不再投票

Pb. 「新朝代」的多數派成員對「新朝代開啟」這件事達成一致，達成一致後新成員組開始投票

但是簡單的按照這種兩階段的操作進行成員變更，雖然能夠保證上述P3的約束，但是無法滿足P1和P2，比如Pa執行成功後，在Pb執行成功之前：沒有成員組可以投票，服務會中斷；如果集群宕機重啟，新的成員組的各個成員由於還未對新成員組達成一致，而無法選出leader。

為了保證P1和P2的約束，我們在上述基本成員變更的基礎上，將Pa和Pb合併為一步操作，即新舊成員組一起對「舊朝代結束+新朝代開啟」這件事達成一致後，才表示成員組變更成功。在開始成員變更的投票後，集群就進入了一個「中間狀態」，在這個過程中宕機恢復後可能退回「舊朝代」也可能進入「新朝代」，因此在這個中間狀態過程中投票的日誌，要求在新舊成員組中都達成一致。

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

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

Joint-Consensus是Raft論文中提到的兩階段成員變更方案，這個方案比較通用，甚至可以做到完整的成員組替換，但是兩階段方案的工程實現都比較複雜，而通用的場景需求又不多，因此在他博士論文最終版的成員變更一章中，更多篇幅分析了簡化的一階段方案（下一節討論），而把Joint-Consensus的篇幅省略了很多。但是作為成員變更方案的基礎，我這裡還是希望能夠從Joint-Consensus開始，分析它的正確性，並且嘗試推導出一階段的成員變更方法。

Joint-Consensus的方案如下，設成員變更前的成員組為C(old)，變更後的成員組為C(new)，成員組內容中包含單調增長的Version。

變更操作

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

協議約束

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

持有[[C(old),C(new)]]的成員當選leader後，要重新對[[C(old),C(new)]]分別在C(old)和C(new)內投票達成多數派，然後繼續成員變更流程，對[[C(new)]]在C(new)內投票達成多數派。然後才能開始leader恢複流程和leader服務
持有[[C(old)]]的成員當選leader後，要重新對[[C(old)]]在C(old)內投票達成多數派，然後才能開始leader恢複流程和leader服務
持有[[C(new)]]的成員當選leader後，要重新對[[C(new)]]在C(new)內投票達成多數派，然後才能開始leader恢複流程和leader服務

選主投票原則

持有[[C(old),C(new)]]的候選人要得到C(old)和C(new)兩個多數派都確認，才能當選leader
持有[[C(old)]]的候選人要得到C(old)多數派確認，才能當選leader
持有[[C(new)]]的候選人要得到C(new)多數派確認，才能當選leader

Joint-Consensus的協議分析

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

對[[C(old),C(new)]]的投票已開始，但未形成兩個多數派確認，集群宕機。那麼重啟選主時，要麼持有[[C(old)]]的成員當選leader，要麼持有[[C(old),C(new)]]的成員當選leader。
對[[C(new)]]的投票已開始，但未形成多數派確認，集群宕機。那麼重啟選主時，要麼持有[[C(new)]]的成員當選leader，要麼持有[[C(old),C(new)]]的成員當選leader。

如上文所述，持有[[C(old),C(new)]]的leader要先完成成員變更流程。之後再執行Multi-Paxox中的日誌「重確認」，因此日誌「重確認」過程不會進入「要得到兩個成員組確認」的情況。

Joint-Consensus允許C(old)與C(new)交集為空，在這種情況下成員變更後，舊leader要卸任，並且將leader許可權轉讓給確認[[C(new)]]的一個多數派成員。

Joint-Consensus方案比較通用且容易理解，但是實現比較複雜，同時兩階段的變更協議也會在一定程度上影響變更過程中的服務可用性，因此我們期望增強成員變更的限制，以簡化操作流程，考慮Joint-Consensus成員變更，之所以分為兩個階段，是因為對C(old)與C(new)的關係沒有做任何假設，為了避免C(old)和C(new)各自形成多數派選出兩個leader，才引入了兩階段方案。因此如果增強成員組變更的限制，假設C(old)與C(new)任意的多數派交集不為空，這兩個成員組就無法各自形成多數派，那麼成員變更方案就可能簡化為一階段。

一階段成員變更方法

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

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

C(new)成員數為N+1

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

C(new)成員數為N-1

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

啟用新成員組的時機

啟用新成員組的時機是指從何時開始，對日誌的投票開始使用C(new)進行，這裡需要考慮的問題是成員變更過程中宕機，重啟選主後，持有[[C(old)]]的成員被選為leader，在宕機前使用C(new)同步的日誌是否可能丟失。分析如下幾種情況：

下線成員，C(new)與C(old)多數派成員數相同，比如ABCDE變更為ABCD，C(new)的任意多數派集合一定是C(old)的某個多數派，變更過程中使用C(new)同步的日誌，在C(old)中依然能夠保持多數派。
下線成員，C(new)的多數派成員數小於C(old)，比如ABCD變更為ABC，這個情況比較特殊，我們來仔細分析，這種情況下在C(new)中形成的多數派成員只能達到C(old)成員數的一半，從嚴格的Basic-Paxos協議來分析，只做到N/2的成員確認，是不能保證決議持久化的。但是我們放在Multi-Paxos的環境中，使用lease機制保證leader有效（leader「有效」的意思是：StartWorking日誌已形成多數派，且完成日誌「重確認」，參考上一篇《使用Multi-Paxos協議的日誌同步與恢復》）的前提下，因為不會有1個以上的成員並發提出議案，同時又因為在N為偶數時，N/2的成員集合與N/2+1的成員集合的交集一定不為空，可以分析出：在leader 有效的前提下，只要N/2（N為偶數）的成員確認，即可保證數據持久化。因此，在這種情況下，在C(new)形成多數派的日誌，宕機重啟後，在C(old)中可以被多數派「重確認」，不會丟失。
上線成員，C(new)的多數派成員數大於C(old)，比如ABC變更為ABCD，C(new)的任意多數派集合一定包含了C(old)的某個多數派，變更過程中使用C(new)同步的日誌，在C(old)中依然能夠保持多數派。
上線成員，C(new)與C(old)多數派成員數相同，比如ABCD變更為ABCDE，某些情況下可能產生C(new)的多數派（如ABE）與C(old)的多數派（如AB）交集只達到C(old)的一半，情況與第2點相同。

最大commit原則

這裡的最大commit原則體現在，同步[[C(new)]]的過程中集群宕機，持有[[C(new)]]的成員當選leader，重啟後無法確認當前多數派持有的成員組是[[C(new)]]還是[[C(old)]]，需要leader將當前持有的成員組重新投票形成多數派確認後，才能開始leader後續的上任處理。否則可能出現連續變更情況下，成員組分裂各自選出1個leader的情況，如Raft報出的這個bug，https://groups.google.com/forum/#!topic/raft-dev/t4xj6dJTP6E，修正方法也很簡單就是實用最大commit原則，對成員組重新投票得到多數派確認。

一階段成員變更方案總結

成員變更限制每次只能增加或刪除一個成員
成員變更由有效的leader發起，確認新的成員組得到多數派確認後，才能返回成員變更成功
一次成員變更成功前不允許開始下一次成員變更,因此新任leader在開始提供服務前要將自己本地保存的最新成員組重新投票形成多數派確認
leader只要開始同步新成員組後，即可開始使用新的成員組進行日誌同步
成員組實用Version標記，持有更大Version的成員不能給持有較小Version的成員投票

成員組變更與日誌同步

Log Barrier
對於下線成員的場景，我們需要保證所有日誌在剩餘在線的機器上能夠形成多數派備份，否則可能丟失日誌。比如下面的場景，logID為2的日誌，在連續成員變更後，僅A上有，無法在A/B/C上形成多數派:
因此我們要求leader在持久化新的成員組時，要像普通日誌一樣為它分配logID（稱為成員變更日誌），它是一個「單向barrier」，即要求所有成員保證logID小於它的日誌都持久化本地後，才能持久化成員變更日誌，而logID大於它的日誌則不受此約束。在上面的例子中,要求B/C保證在持久化 Cnew1之前,一定先保證2號日誌持久化。