分散式系統中的領導人選舉

領導人選舉是一種簡單的概念，亦即對分散式系統中的一件事物 (程序、主機、執行緒、物件或人) 賦予一些特殊的權力。這類特殊權力的例子包括能夠指派工作、能夠修改資料片段，甚至能處理系統中所有請求。

領導人選舉是一種強大的工具，能夠提升效率，降低協調的需要，並能簡化架構和減少操作量。但另一方面，領導人選舉也能引入新的故障模式和擴展上的瓶頸。此外，領導人選舉恐怕會讓人更難以評估系統的正確性。

鑑於有這些複雜的情形，實作領導人選舉之前，我們要謹慎考量其他選項。對於資料處理和工作流程，工作流程服務例如 AWS Step Functions 具備與領導人選舉相同的許多益處，又能避開許多風險。對於其他系統，我們通常會實作等冪 API、最佳鎖定及其他無必要採行單一領導人的模式。

本人將在此文章中討論領導人選舉一般的利與弊，以及 Amazon 如何在分散式系統中採行領導人選舉，並提出領導人故障方面的洞察。

選舉領導人的方式有許多種，從演算法 (例如 Paxos) 到像是 Apache ZooKeeper 等軟體、到自訂軟體、租賃等。租賃是 Amazon 使用最廣泛的領導人選舉機制。租賃的理解和實作皆相當直接了當，並且有內建的容錯能力。租賃是以單一資料庫儲存目前的領導人來運作。因此，租賃要求領導人定期發出活動訊號，表明其仍為領導人。如果現任領導人經過一段時間沒有發出活動訊號，其他候選領導人可嘗試接管。

就算有 Amazon Elastic Compute Cloud (Amazon EC2) 絕佳的時間同步功能，我們仍會避免倚賴分散式系統中的時間。這是因為難以確保全叢集的系統時脈之同步程度高到足以倚賴該同步來為分散式操作進行定序或協調。在 Amazon，分散式系統僅將時間供人使用。租賃倚賴時間。不過，所倚賴的限於本機經過的時段，並非有所同步，並且需要多重伺服器協議的實際時鐘時間。

DynamoDB 鎖定用戶端原始程式碼提供有領導人選舉的相關範例和詳細資料。不過我們發現，雖然租賃和鎖定的概念類似，但要想正確實作，可能需要相當微妙的工夫。實作上需要瞭解伺服器測量本機時段的方式。例如，若測量時間的伺服器或程式庫認為時間偶爾會往後跳，遇到租賃內建的時段就會打破其中假設。時段避開了從閏秒到持續高 CPU 使用率時間久後本機時脈偏離，而造成伺服器停止議定時間為何的全域時脈同步問題。

租賃以及所有種類的分散式鎖定還有一個更大的問題，那就是如何確定領導人僅在握有鎖定時執行作業。確保領導人握有鎖定，實際上相當困難。我們發現對於慢速或耗損網路上的領導人，確保其不致於相信握有鎖定的時間比實際更長，這一點相當重要。同樣道理，檢查鎖定至完成作業之間的廢棄項目收集暫停，能導致行為不正確。實務上，針對這些問題加以強化往往是莫大的挑戰。

DynamoDB 和 ZooKeeper 提供簡易的租賃型鎖定用戶端，能進行具有容錯功能的領導人選舉。除非有具體需要，我們偏好這類用戶端，因為在我們認為，這是實作領導人選舉最簡易也最通過考驗的方式。Amazon 的團隊偏好避免建立自訂型的領導人選舉實作。我們喜愛完善通過測試，經得起實戰考驗的現有用戶端。

領導人選舉是在全 Amazon 廣泛部署的一種模式。例如：

• 使用傳統關聯式資料庫管理系統 (RDBMS) 的系統幾乎全都靠領導人選舉來挑選領導人資料庫，負責處理所有寫入，有時候也包括所有讀取。在這些系統中，選舉可能為自動化方式，但經常由操作人員手動完成。
• Amazon EBS 在許多儲存伺服器器上分散磁碟區的讀寫。為確保一致性，其使用領導者選舉來選擇磁碟區中每個區域的主要項，從而對讀取和寫入進行排序。若主要項發生故障，則實行項目使用相同的領導者選舉機制複製步驟。在 Amazon EBS 中，領導人選舉可確保一致，同時避免於資料層面進行協調，以提升效能。DynamoDB、Amazon Quantum Ledger Database (Amazon QLDB) 及 Amazon Kinesis (Kinesis) 因為同樣的理由採行類似的方針。
• Kinesis Client Library (KCL) 利用租賃來確保每個 Kinesis 碎片各由一個擁有者處理，便於進行 Kinesis 串流的擴展處理。

需要謹慎思考的另一點是領導人故障時，其作業會有何後果。如果領導人在執行任務當中故障，新領導人如何完成該項任務？ 如果領導人來不及使作業耐用之前便先故障，系統是否依然正確？ 許多種類的系統有分立的「使作業耐用」和「通知大家已完成」步驟。在 Amazon，我們的系統始終會先做前者，再做後者 (亦即容許資料遺失)。再次重申，冪等在此十分實用。原因在於容許新領導人有信心地將退職前的領導人可能已完成一部份、或雖然完成，但尚未對外通知的作業加以重新驅動。

為了容許故障，Amazon 的分散式系統未設單一領導人。而是讓領導身分作為屬性，在伺服器或程序之間傳遞。在分散式系統中，無以保證系統中確切有一個領導人。情況是多半為一個領導人，故障時可能有零個、也可能有兩個領導人。

領導人故障時我們如何選擇系統的行為，取決於系統中有兩個領導人時會發生什麼情況。執行等冪作業的系統經常能容許有兩個領導人，對效率影響甚小。有兩個領導人之下，系統能達到更高的可用性，亦可選擇較弱的領導人選舉方式。

絕對要求至多一個領導人的系統，比多個領導人的系統更難建置。採行領導人選舉的系統必須始終正確、一致。同時也必須確保即將退職的領導人在選出新領導人之間去職，這比表面上看起來困難。在分散式系統中，經常難以得知系統是否故障，還是只不過在某個其他的網路分區繼續執行作業。在 Amazon，我們會確保一切領導人選舉系統都能處理這種邊角案例。

在 Amazon，我們遵循下列領導人選舉的最佳實務：

• 經常檢查剩餘的租賃時間 (或一般的鎖定狀態)，尤其在有超出領導人本身的副作用之一切操作起始之前。
• 考慮到慢速網路、逾時、重試和廢棄項目收集暫停能造成剩餘的租賃時間在程式碼預期之前到期。
• 避免背景執行緒中有發出活動訊號的租賃。如果當租賃到期或是發出活動訊號的執行緒結束時，執行緒無法岔斷程式碼，此情形可造成正確性的問題。如果在發出活動訊號的執行緒保留租賃時，作業執行緒結束或停止，即可能發生可用性的問題。
• 備有可靠的指標，以展現與領導人目前正在做多少相較能夠做多少工作。應經常檢視這些指標，確定設有計畫，能在容量用盡之前預先擴展。
• 應當能夠方便找出哪部主機是目前的領導人，以及任何給定時間擔任領導人的主機是哪一部。應保存領導權變化的稽核追蹤或日誌。
• 使用例如 TLA+ 等工具，建立模型並且正式驗證分散式演算法的正確性。如此能捕捉微妙、難以察覺和稀有的錯誤，以免當應用程式在於領導人選舉協定提供的保證之上有過多假設時悄悄滲入。

領導人選舉是全 Amazon 系統中採用的強大工具，不但利於我們的系統容錯，操作上也更簡便。不過，當我們使用領導人選舉時，會謹慎考量各組領導人選舉協定所提供的保證，更重要的是必須注意未提供的是哪些。

Amazon 的系統經常利用領導人選舉來確保內建有容錯能力。系統使用領導人選舉以確保至少有一部伺服器在處理任務時，會另用其他機制，在面對多重並行領導人時能夠維護正確性。例如，可使用基礎資料庫以確定若有兩個領導人認為兩者接握有租賃時，不會相互干擾。不對租賃實作所提供的保證作出假設，我們專注在系統的正確性，經常以例如 TLA+ 等技術建立模型來達成。

儘管有些小麻煩，在 Amazon 的分散式系統工具組中，領導人選舉加上例如冪等和最佳鎖定等模式，對我們而言仍然是好用的工具。

關於租賃的運作方式如需更多資訊，請參閱：

• 如何執行分散式鎖定
• Burrows，鬆散耦合分散式系統的 Chubby 鎖定服務
• Gray 和 Cheriton，租賃：分散式檔案快取一致的高效容錯機制