跳到正文
cloudflare blog(blog.cloudflare.com)· João Pedro Leite·· 11 天前精選品質評分76

Cloudflare 為何選擇 QuePaxa 共識演演算法

Choosing QuePaxa, an unusual consensus algorithm

重點導讀

Cloudflare 說明其全球控制平面系統 Meerkat 選用 QuePaxa 共識演演算法的原因,以及演演算法如何在網路延遲與連線波動時持續處理請求。

AI 伴隨問答

自備 Key 深度分析

針對這篇報導有疑問?可直接點選快捷問題或向 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成果。

來源: cloudflare blog (blog.cloudflare.com)
開啟原文

讀者討論

理性交流 · 即時討論