Cloudflare 為何選擇 QuePaxa 共識演演算法
Choosing QuePaxa, an unusual consensus algorithm
Cloudflare 說明其全球控制平面系統 Meerkat 選用 QuePaxa 共識演演算法的原因,以及演演算法如何在網路延遲與連線波動時持續處理請求。
AI 伴隨問答
針對這篇報導有疑問?可直接點選快捷問題或向 AI 追問背景脈絡與技術細節:
文章拆解 QuePaxa 如何以提案協作與選擇性領導因應全球網路延遲,並說明這些設計如何影響 Meerkat 的可用性與吞吐量。
Cloudflare 最近宣佈推出 Meerkat,這是一項實驗性的分散式共識服務,旨在管理我們內部的全球控制平面。它採用研究人員 Tennage & Băsescu 等人發表的新共識演算法 QuePaxa(2023)。
QuePaxa 是個不尋常的選擇;大多數共識系統都採用 Raft、(Multi-)Paxos 或 Viewstamped Replication 等成熟的共識演算法。這些演算法廣為人知、實作成熟,通常也運作良好。
然而,在網路連線不穩定、延遲變化大的廣域網路中,常見的共識演算法往往會遇到問題;網際網路就是這類網路,而 Meerkat 正是在網際網路上運作。這些演算法仰賴單一領導者 程式保持可用,且延遲可預測。如果領導者停止運作、延遲高於平常,或失去連線,整個共識系統就會變慢或無法使用,直到替換領導者為止。這對 Meerkat 來說不可接受。
Meerkat 的全球部署環境,讓我們轉而採用較新的共識演算法 QuePaxa。即使網路狀況不穩定,它仍有望維持較佳的穩定性,主要原因是它不必依賴領導者就能持續運作。在這篇文章中,我們將說明 選擇 QuePaxa 的原因,以及 QuePaxa 演算法的運作方式。
我們正在打造的系統,以及它的獨特之處
Meerkat 是一種分散式系統,其中的複本會就一份有序的事件日誌達成共識,而每個事件都是由共識演算法決定。
共識演算法讓一群機器即使有些當機或中斷連線,也能對同一個共同事實達成共識。共識演算法提供一項重要保證:機器絕不會決定出互相衝突的值。這可確保 Meerkat 複本的日誌永遠不會分歧。
Meerkat 使用由共識機制支援的日誌,提供類似鍵值儲存庫的應用程式 ,其中日誌的每個專案都是 get 或 put。由於共識演算法保證複本的日誌永遠不會分歧,因此所有複本都會建立相同的鍵值(KV)狀態。其他採用共識機制支援的系統包括 Consul、etcd 和 Apache ZooKeeper。
然而,與類似系統不同的是,Meerkat 專為全球規模而設計。Meerkat 叢集可能分佈在不同洲,並透過延遲通常偏高且變化大的連線互相連線。對共識系統而言,這是種少見的部署方式;這類系統通常部署在規模較小、範圍較區域性的網路中,並有嚴格的延遲要求。
全球規模下的共識挑戰
雖然所有共識演算法都能確保複本對相同的值達成共識,但許多演算法在網路狀況惡化時(機器並未當機),可用性會大幅下降,或運作速度變得很慢。我們親身經歷過這種情況:2020 年,Cloudflare 核心網路交換器發生區域性故障,導致一套由共識機制支援的系統效能下降,儀錶板速度比平常慢了 80 倍,持續六小時。關鍵是,系統沒有遺失任何資料。但在問題解決前,系統無法處理寫入;這是不可接受的。
理想的共識演算法應該能在延遲突增和連線中斷時持續運作,而不只是能因應複本故障。這在全球規模下尤其成問題,因為故障更可能源自網路,而非我們自己的伺服器。
我們來看看共識演算法的兩種常見特性,在網路環境惡劣時可能導致效能下降:破壞性幹擾與故障偵測。稍後我們會看到 QuePaxa 如何避開這兩個問題。
破壞性幹擾與領導者
以 Paxos 為例,它可說是大多數共識演算法的始祖。許多共識演算法都承襲了 Paxos 的架構,好的部分和不太好的 部分都有。
省略了 大量細節後,以下是 Paxos 的運作方式。系統中有兩種程式:提議者和接受者。概括來說,系統的目標是讓多數接受者同意由某個提議者提出的值。流程分為兩個階段:Prepare 階段和 Accept 階段。在 Prepare 階段,任何提議者都可以向多數接受者傳送一個選票編號。 這個選票編號代表一項承諾:接受者只會接受選票編號等於或高於該編號的提案。接著,在 Accept 階段,提議者再次將提案連同選票編號傳送給多數接受者。如果多數接受者仍持有該提案的選票編號,多數接受者就會接受提案,而提議者便能安全地決定該提案。
當兩個或多個提議者同時提交提案時,就會出現問題。具體來說,另一個提議者可能會在兩個階段之間插入自己的較高選票編號,阻擋所有較低的選票。兩個提議者可能會不斷互相阻擋,無法繼續推進,實際上是在爭奪接受權。
當提議者以這種方式互相競爭並阻擋對方時,我們稱之為破壞性幹擾。提議者提出的選票越多,破壞性幹擾就越嚴重。並行的提議者越多,系統就越可能反覆提出提案,陷入停滯。即使沒有任何副本當機或無法使用,多個提議者與行為異常的網路仍可能阻擋 Paxos。形式上來說,若不假設在某個時間點之後,所有訊息都能在有限時間內送達,Paxos 就無法保證活性 (也就是提案最終都會得到決定);這項假設稱為部分同步。
為了避免多個提議者不斷競爭,大多數實際部署的共識演算法,例如 Raft、Multi-Paxos 和 Viewstamped Replication,都會加入一個特殊的領導者 提議者。領導者是唯一可以提出提案的副本。將提案權集中在一個副本上,能為並行請求排定順序,避擴音案互相競爭,還有一項額外好處:只需一次網路往返就能做出決定,而非兩次。只要領導者正常運作且網路狀況良好,以領導者為基礎的協定就很快速。
代價是領導者必須持續運作並保持可連線。當領導者故障、速度過慢,或與叢集斷線時,系統就會停滯。唯一的解決方式,是讓其餘副本偵測領導者故障,並選出新的領導者取而代之。
領導者復原不穩定時
領導者故障時,系統必須透過選出新領導者來復原。有趣的是,破壞性幹擾往往就是透過領導者復原,再次潛入以領導者為基礎的系統。
以 Raft 為例。基於安全性考量,Raft 會透過多數決選出新領導者。懷疑領導者已故障的副本會宣佈自己為領導者候選人,並向其他副本請求投票。如果超過半數的副本同意投票給候選人,該候選人就會成為新領導者。如果沒有,系統就會再次舉行選舉,候選人也會再次嘗試。
多個副本可能同時成為候選人——只要偵測到領導者已停止運作即可。接著,所有候選人可能同時嘗試取得多數票。問題在於,候選人會為了多數票而互相競爭 ,這表示 Raft 的選舉也會遭遇我們剛才在 Paxos 中看到的破壞性幹擾:兩個副本可能互相阻止對方取得多數支援並成為領導者。選舉失敗的次數越多,就會有越多副本嘗試競選領導者。
即使領導者不再故障,選舉仍會持續 幹擾原本可能正常運作的系統。這稱為亞穩態故障:即使最初的故障原因已排除,故障模式仍會自行延續。兩秒的網路中斷——或網路交換器短暫故障——可能讓領導者看起來 像是故障,進而觸發領導者選舉;選舉可能失敗,並引發更多選舉。 網路中斷會在兩秒後結束,但由於候選人持續互相阻撓,選舉可能還會持續更久。
理想情況下,共識演算法不需要任何復原流程,因為這類流程很複雜、容易受到幹擾,也會成為另一個停機原因。
故障偵測出錯時
領導者選舉中的破壞性幹擾問題,會因過於敏感的故障偵測而加劇,在廣域網路中特別如此。以領導者為基礎的共識演算法要選出新領導者,副本必須先偵測 到領導者已故障。然而,如果副本對領導者故障的偵測不準確,系統可能會耗費大量時間進行復原,而無法處理請求。
在分散式系統中,機器透過網路彼此連線,故障偵測終究得仰賴預期。程式無法直接觀察遠端程式是否故障,只能觀察預期訊息是否已送達。若要判斷機器是否正常運作,我們需要可預測的通訊模式,例如心跳訊號或確認訊息。如果預期訊息未能在預期時間內送達,我們就會懷疑發生了故障。難處在於如何妥善設定這些預期。
在真實網路中,尤其是廣域網路,訊息並非總是 能如預期般送達。訊息送達時間沒有保證的上限。這並不是說網路速度很慢或不可靠——大多數 訊息都會在我們預期的時間內送達。相反地,延遲突然飆高或連線中斷,可能會在短時間內毫無預警地增加訊息穿越網路所需的時間。我們稱這類網路為非同步網路。
非同步網路最大的問題在於,如果某臺伺服器沒有在指定時間內回應,我們其實無法判斷伺服器是故障了,還是網路只是變慢了——透過網路觀察,兩者無從區分。任何實際可用的故障偵測器都必須 根據等待時間與預期的差距來猜測,而這種猜測有時會出錯。
在以領導者為基礎的演算法中,這種猜測正是觸發領導者選舉的原因。有時領導者已經離線;有時則是訊息延遲,或連線在沒有任何提示的情況下中斷。協定在做出反應之前,無法知道究竟發生了哪一種情況。如果猜錯了,副本以為領導者故障,但實際上並非如此,選舉就會開始,整個系統都必須 停止。在新領導者接任之前,系統無法繼續運作——而如同我們剛才所見,這可能需要一段時間。
非同步網路中的故障偵測本質上容易出錯;偵測器一旦判斷錯誤,系統就會停機。
故障偵測緩慢時
即使故障偵測器猜對了,還是會遇到問題。故障偵測器 會透過觀察網路上的訊息來偵測故障,因此回應時間必須配合網路延遲——偵測器的逾時時間不能短於網路延遲。這就是為什麼 Raft 部署時,選舉逾時通常設為網路往返時間的五到十倍。 逾時必須夠長,讓領導者有機會發出存活訊號,避免誤觸發選舉。選舉逾時可以 設得短得多,但由於領導者選舉會讓整個系統完全停止運作,因此逾時通常會保守地設得較長。
大致來說,橫跨半個地球的往返時間以數百毫秒計。如果選舉逾時設為數次往返時間,偵測協調者故障可能需要約一秒。即使故障偵測完全準確,速度仍然很慢;在高延遲的全球網路中更是如此。在偵測器做出反應之前,系統都無法運作。
為什麼 QuePaxa 是合適的選擇
我們發現,任何仰賴固定領導者或精確逾時的演算法,在透過網際網路運作的共識系統中,終究都會停滯。我們開始尋找專為非同步環境設計的共識演算法——這類協定不仰賴穩定可靠的網路或精準的計時也能運作。這讓我們找到QuePaxa;這套協定由 Tennage & Băsescu 等人於 2023 年發表。
QuePaxa 最引人注目之處,在於網路狀況良好時能以一次往返高效率地達成共識,同時在延遲尖峰、連線問題和伺服器故障期間,也能平順地降低效能。QuePaxa 透過三項關鍵設計,解決我們剛才討論的問題:採用可選用 的領導者、完全移除對故障偵測的依賴,以及讓提案者之間能產生建設性干涉 。
QuePaxa 和 Paxos 一樣,有兩種角色:提案者和記錄者。提案者提交待決定的提案;記錄者則在提案者之間扮演中介,記錄自己收到的每一項提案。
在 QuePaxa 中,提案者不必彼此競爭,爭取讓自己的提案獲得決議,而是會合作提出一個所有人都支援的提案。QuePaxa 會為提案指定一個以隨機數表示的優先順序。可選的領導者會獲得獨有的最高優先順序。執行期間,提案者會將提案提交給記錄器,由記錄器將提案傳播給其他活躍的提案者。當提案者從記錄器收到優先順序高於自己提案的提案時,就會採用這個新提案,也就是開始廣播優先順序較高的提案。一般而言,QuePaxa 的提案者會合作決定他們共同得知的最高優先順序提案。這表示提案者無法無限期阻止彼此決定提案。
但有個限制:提案可能無法充分傳播,讓大家達成共識,因此提案者必須重試,每次嘗試都算是一個回合。不過,提交提案的提案者越多,他們就越有可能收斂到優先順序最高的提案。這正是 QuePaxa 成為隨機化演算法的原因:非領導者提案者隨機產生的優先順序,有可能讓大家在某個回合中對已知的最高優先順序達成共識,但無法保證如此。然而,只要回合數足夠,提案者就保證能對某個提案達成共識。
其中一位提案者會被指定為領導者。只有領導者能在單次往返中決定提案。領導者提出的提案永遠具有最高優先順序;如果領導者知道自己已在其他提案者之前傳播了提案,就能立即做出決定。客戶端不必向領導者提出請求,任何提案者都能提出提案。如果領導者停止運作,客戶端仍可向其他提案者提出請求。領導者完全是可選的。領導者只是比其他提案者更有可能做出決定,而且能在單次往返中更快完成。
不過,由於只有領導者能在單次往返中做出決定,我們希望盡可能使用領導者。為了運用這條快速路徑,又不造成單點故障,向系統提交提案的客戶端會分散風險:把提案請求送給每個副本,非領導者副本則會等待一小段時間,讓領導者有機會自行提出提案並做出決定。在我們自行實作 QuePaxa 時,實際上沒有遵循論文的做法,而是讓客戶端等待這段分散風險的逾時時間,而非讓副本等待,以減少在網路上傳送的訊息量;但整體結果相同。
這種分散風險逾時與 Raft 或 Multi-Paxos 使用的逾時機制很不一樣。它不是故障偵測,因此不受網路延遲限制;逾時時間由副本在本機決定,想設多短都可以。 在 Raft 中,如果網路延遲為 100 毫秒,卻設定 5 毫秒的逾時時間,系統就會完全停擺。但在 QuePaxa 中,5 毫秒的分散風險逾時只會增加活躍提案者的數量。
不過,採取備援策略並非沒有代價:提案者越多,廣播的提案就越多,副本也越可能無法在一個回合內做出決定。因此,備援策略提供了一種取捨:我們可以縮短備援逾時時間,更快因應領導者變更,但會增加頻寬成本,也可能需要更長時間才能做出決定。這種取捨對我們來說完全值得。
如果 QuePaxa 的領導者停止運作,我們可以按照所需速度恢復,不受網路延遲限制。這就是 QuePaxa 如何克服故障偵測問題:由於任何人都能提出提案,而不只有領導者,QuePaxa 可以透過備援主動處理領導者故障,而不是等故障發生後才反應。
QuePaxa 的運作原理
若要了解 QuePaxa 如何具備這些優點,讓我們看看 QuePaxa 實際上如何運作。
QuePaxa 以回合運作,每個回合由四個階段組成。如果提案在最後一個階段仍未確定,就會開始新的一回合,QuePaxa 也會重新開始。每個階段開始時,提案者都會將目前採用的提案廣播給所有記錄者。提案者收到多數記錄者的回覆後,就會進入下一個階段。以下是各階段的大致流程:
- 階段 0(提案與採用):提案者會隨機選擇優先順序,將提案傳送給記錄者,並採用自己從多數記錄者收到的提案中優先順序最高者。如果這是第一個回合,而且領導者知道自己的提案最先送達多數記錄者,領導者就會立即做出決定。
- 階段 1(散佈):提案者將自己採用的提案散佈給多數記錄者。
- 階段 2(檢查與決定):提案者向多數記錄者詢問上一個階段中見過的優先順序最高提案。如果該提案與自己採用的提案相符,就會據此做出決定。
- 階段 3(延續):未能做出決定的提案者會採用自己從多數記錄者看到的最佳提案,為下一個回合做準備。
讓我們逐一檢視幾種執行範例,並深入瞭解各階段如何共同實現我們希望 QuePaxa 具備的整體行為。每次執行都會有兩位提案者(其中一位是領導者)和三位記錄者。
領導者快速路徑 (階段 0):第一個階段會完成三件重要的事:隨機化優先順序(這是避開FLP 不可能性定理所必須的)、檢查領導者是否最先取得多數支援,以及在領導者未能取得多數支援時,協助提案者收斂至相同提案。領導者的提案不會經過隨機化,並且永遠具有最高的優先順序。
在上面的範例中,領導者的提案比其他人的提案更早送達多數記錄者,並收到確認回覆。領導者可以安全地立即做出決定。這看起來或許很危險,但由於一項稱為多數交集的性質,這樣做完全安全:任意兩個記錄者多數集合中,至少會有一位記錄者重疊。由於領導者已取得多數支援,任何其他提案者在查詢多數記錄者時,都必定會遇到領導者的提案並採用該提案。因為領導者的提案優先順序最高,其他提案者都會採用領導者的提案。因此,不可能有任何其他提案被選定。
並行慢速路徑(階段 0–3):不過,當有多個提案者同時提出提案時,無法保證領導者會立即做出決定。領導者可能無法率先取得多數記錄器的支援,也可能只收到一則支援其他提案者的回覆。接下來看看其他提案者與領導者競爭時會發生什麼事。
階段 0: 如下圖所示,第二個提案者(以紅色表示) 先抵達第二個和第三個記錄器。快速路徑因此受阻。提案者不會彼此競爭,而是採用從多數記錄器收到的最高優先順序提案,並進入第二階段。在這個階段,兩個提案者可能 都會採用領導者的提案而達成一致。為了方便說明,這個範例會延遲領導者傳送的訊息,避擴音案者達成一致。
階段 1: 提案者將在階段 0 剛採用的提案 傳給多數記錄器。記錄器會追蹤自己收到的最高優先順序提案。這個步驟簡單卻至關重要:它能避免協定之後決定較低優先順序的提案。這再次仰賴多數交集:下一階段查詢的任何多數記錄器,都至少包含一個在此階段看到已採用提案的記錄器。為了方便說明,我們會在此階段延遲領導者傳給第三個記錄器的訊息,避擴音案者達成一致,因此該記錄器不會採用領導者的提案。
階段 2: 此時便可能做出決定。每個提案者都會向多數記錄器詢問 階段 1期間觀察到的最高優先順序提案,以確認是否有更高優先順序的提案取得足夠支援,超越自己的提案。如果回報的最高優先順序提案仍是自己採用的提案,就可以做出決定。在圖中,領導者從多數記錄器收到的回覆都是自己的提案,因此能安全地做出決定。另一個提案者收到互相矛盾的摘要,因此尚不能做出決定。 與階段 1 相同,記錄器會追蹤自己收到的最高優先順序提案。
階段 3: 如果提案者在階段 2 尚未做出決定,就會進入最後的清理階段,為下一輪做準備。提案者再次傳送自己的提案,並採用從多數記錄器收到的最佳提案。在此例中,剩下的提案者找到已決定的提案並採用它,接著進入下一輪。
這是刻意安排的——如果前一階段已經做出決定,多數記錄器就會持有該提案,而所有剩下的提案者都保證會採用它。這裡再次展現提案者之間的合作:即使某一輪失敗,提案者仍會嘗試在進入下一輪前採用相同的提案。
進入下一輪: 第四階段結束後,提案者會進入下一輪。此時已沒有領導者快速路徑,唯一的決定方式是在第三階段達成一致。值得注意的是,由於提案採用機制,隨著輪次增加,做出決定會變得越來越容易,難度呈指數級下降。QuePaxa 論文預測每一輪有 50% 的機率做出決定,但實務上,由於提案者能達成一致,這個機率高得多。
把四個階段合在一起來看,就能瞭解 QuePaxa 如何保持韌性。第一階段讓領導者能透過一次往返快速完成流程。如果快速流程失敗,隨機優先順序和提案採納機制會幫助提案者達成共識,而非彼此競爭。第二和第三階段透過多數交集確保決策安全;第四階段則把提案者學到的資訊帶到下一輪,以防提案者尚未做出決策。
提案者不必先偵測到領導者失效才能繼續推進,而某一輪失敗也不會丟棄已完成的工作。網路運作正常時,QuePaxa 的速度很快;網路狀況不佳時,QuePaxa 仍會持續運作。
QuePaxa 如何讓 Meerkat 成為可能
在我們自行評估 Meerkat 的過程中,伺服器幾乎遍佈所有大洲,我們直接體驗到 QuePaxa 對系統整體效能與可用性的影響。即使領導者當機、斷線,或只是變慢,Meerkat 仍會持續處理請求。我們從未遇過系統完全停擺的情況。這正是我們想要的。
Meerkat 處理請求的速率通常也相當穩定。大多數決策(超過 95%)都由領導者在第一階段完成,因此我們的輸送量相當穩定。如果第一階段未能做出決策,輸送量就會短暫下降,最多降至平常的三分之一,表示這次決策需要三次往返、也就是三個階段,而非只需一個階段。系統速度會變慢,但不會完全停擺。
QuePaxa 也讓我們能在叢集運作期間,有把握地切換由哪個副本擔任領導者。由於領導者並非決策的唯一推動者,而且提案者會互相配合,暫時不理想的領導者所造成的限制,就不像其他演算法那麼大;在其他演算法中,領導者設定不當 可能會讓系統完全停擺。我們可以動態調整由哪個提案者擔任領導者,而不必太擔心影響 Meerkat 叢集的穩定性。
接下來將介紹的內容
為了讓 Meerkat 適用於全球網路,我們必須重新檢視處理分散式共識的方式。我們沒有沿用那些不太符合需求的常見預設做法,而是參考了學界和業界數十年來的研究成果。這番探索讓我們找到 QuePaxa。
選擇 QuePaxa,代表選擇一條較少人走的路。它不像 Raft 或 Paxos 那樣經過廣泛的實戰考驗,而且我們也正在擴充原本的崩潰停止設計,讓它支援崩潰後復原。因此,我們需要謹慎地進行工程實作,並提出比一般系統更有力的正確性證據。
因此,我們正以形式化方法驗證 QuePaxa 的實作,以及整個 Meerkat 系統,並進行大量模擬和故障注入測試。本系列後續文章將說明我們如何驗證 Meerkat 和 QuePaxa 的 Rust 實作、如何測試難以在正式環境重現的故障、基準測試,以及我們將學術協定轉化為正式環境系統時的心得。
敬請留意 Cloudflare Blog 上的 Meerkat 後續訊息;如果你想進一步瞭解 Cloudflare 的研究,歡迎參閱我們的Cloudflare Research成果。