那麼，讓我們想像一下。 房間裡鎖著5隻貓，為了叫醒主人，需要它們都同意，因為只有五隻貓靠在門上才能打開門。 如果其中一隻貓是薛定諤的貓，而其他貓不知道他的決定，就會出現問題：“它們怎麼能做到呢？”
在本文中，我將簡單地向您介紹分散式系統世界的理論組成部分及其運作原理。 我還將粗略地研究 Paxos 的主要思想。
當開發人員使用雲端基礎設施、各種資料庫並在大量節點的叢集中工作時，他們確信資料將是完整、安全且始終可用的。 但保證在哪裡呢？
本質上，我們的保證是供應商的保證。 它們在文件中的描述如下：“這項服務非常可靠，它有給定的 SLA，不用擔心，一切都會按照您的預期分散式工作。”
我們傾向於相信最好的，因為來自大公司的聰明人向我們保證一切都會好起來的。 我們不會問這樣的問題：事實上，為什麼這能行得通？ 此類系統的正確運作是否有任何正式的理由？
我最近去了 並受到這個話題的啟發。 學校的講座更像是微積分課程，而不是與電腦系統相關的課程。 但這正是我們每天使用的最重要的演算法在不知不覺中被一次證明的方式。
大多數現代分散式系統都使用 Paxos 共識演算法及其各種修改。 最酷的是，只需用筆和紙就可以證明該演算法的有效性以及原則上存在的可能性。 在實踐中，該演算法用於在雲端中大量節點上運行的大型系統。
接下來討論的內容的簡單說明：兩位將軍的任務我們先來看看熱身 .
我們有兩支軍隊──紅軍和白軍。 白軍駐紮在被圍困的城市。 A1、A2將軍率領的紅軍分佈在城市兩側。 紅髮人的任務是進攻白色城市並取得勝利。 然而，每個紅將軍的軍隊單獨比白軍小。
紅方勝利條件：兩名將領必須同時進攻，才能對白方取得數量優勢。 為此，將軍 A1 和 A2 需要彼此達成協議。 如果大家分頭攻擊的話，紅髮就會輸。
為了達成協議，將軍A1和A2可以透過白城境內互相派遣使者。 信差可能會成功到達盟軍將軍那裡，也可能會被敵人攔截。 問題：紅髮將軍之間是否存在這樣的通信序列（從A1到A2發送信使，反之亦然從A2到A1發送信使的序列），在該序列中他們保證同意在X小時發動攻擊。這裡，保證意味著兩位將軍都將明確確認盟友（另一位將軍）一定會在指定時間X 發動攻擊。
假設A1向A2發送訊息：“我們今天午夜進攻吧！” 未經將軍 A1 確認，將軍 A2 無法攻擊。 如果A1的信使已經到達，那麼A2將軍會發送確認訊息：“是的，我們今天殺掉白人。” 但現在A2將軍不知道他的使者是否已經到達，他無法保證攻擊是否會同時進行。 現在將軍A2再次需要確認。
如果我們進一步描述他們的通信，就會發現，無論有多少個訊息交換週期，都無法保證兩位將軍都收到了他們的訊息（假設任何一個信使都可以被攔截）。
兩將軍問題很好地說明了一個非常簡單的分散式系統，其中有兩個通訊不可靠的節點。 這意味著我們不能 100% 保證它們會同步。 類似的問題僅在本文後面進行更大規模的討論。
我們引入分散式系統的概念
分散式系統是一組可以交換訊息的電腦（以下我們稱之為節點）。 每個單獨的節點都是某種自治實體。 節點可以自行處理任務，但為了與其他節點通信，它需要發送和接收訊息。
訊息到底是如何實現的，使用什麼協議——在這種情況下，我們對此不感興趣。 分散式系統的節點可以透過發送訊息來相互交換數據，這一點很重要。
定義本身看起來並不是很複雜，但是我們必須考慮到分散式系統有許多對我們來說很重要的屬性。
分散式系統的屬性
- 並發 – 系統中同時或併發事件發生的可能性。 此外，只要我們沒有明確的事件發生順序，我們就會認為兩個不同節點上發生的事件可能是併發的。 但是，一般來說，我們沒有。
- 沒有全域時鐘。 由於缺乏全球時鐘，我們沒有明確的事件順序。 在普通人的世界裡，我們習慣我們絕對有時鐘和時間。 當涉及到分散式系統時，一切都會改變。 即使超精密原子鐘也會出現漂移，在某些情況下我們可能無法判斷兩個事件中哪一個先發生。 因此，我們也不能依賴時間。
- 系統節點獨立故障。 還有另一個問題：僅僅因為我們的節點不會永遠持續下去，就會出現問題。 硬碟可能會發生故障，雲端中的虛擬機器可能會重新啟動，網路可能會閃爍且訊息可能會遺失。 此外，可能存在節點工作但同時對系統不利的情況。 最後一類問題甚至有一個單獨的名稱：問題 。 存在此問題的分散式系統最受歡迎的例子是區塊鏈。 但今天我們不考慮這一類特殊的問題。 我們會對僅一個或多個節點可能發生故障的情況感興趣。
- 節點之間的通訊模型（訊息傳遞模型）。 我們已經確定節點透過交換訊息進行通訊。 有兩種著名的訊息傳遞模型：同步和非同步。
分散式系統中節點之間的通訊模型
同步模型 – 我們確信存在一個有限的已知時間增量，在此期間訊息可以保證從一個節點到達另一個節點。 如果這個時間過去了且訊息還沒有到達，我們可以有把握地說該節點已經失敗。 在這個模型中，我們有可預測的等待時間。
非同步模型 – 在非同步模型中，我們認為等待時間是有限的，但不存在這樣的時間增量，在此之後我們可以保證節點發生故障。 那些。 來自節點的訊息的等待時間可以是任意長。 這是一個重要的定義，我們將進一步討論它。
分散式系統中共識的概念
在正式定義共識的概念之前，讓我們考慮一個我們需要共識的情況的例子，即： 狀態機複製.
我們有一些分散式日誌。 我們希望它是一致的，並且在分散式系統的所有節點上包含相同的資料。 當其中一個節點獲知要寫入日誌的新值時，它的任務就是將該值提供給所有其他節點，以便日誌在所有節點上更新，並且系統進入新的一致狀態。 在這種情況下，節點之間達成一致非常重要：所有節點都同意提議的新值是正確的，所有節點都接受這個值，只有在這種情況下，每個人都可以將新值寫入日誌。
換句話說：沒有一個節點反對它有更多相關信息，並且建議的值不正確。 節點之間的協定以及單一正確接受值的協定是分散式系統中的共識。 接下來，我們將討論能夠保證分散式系統達成共識的演算法。
更正式地說，我們可以將共識演算法（或簡稱共識演算法）定義為將分散式系統從狀態A轉移到狀態B的某種函數。而且，這個狀態是所有節點都接受的，並且所有節點都可以確認它。 事實證明，這項任務並不像乍看之下那麼微不足道。
共識演算法的屬性
共識演算法必須具備三個屬性才能使系統繼續存在並在從一個狀態轉移到另一個狀態方面取得一些進展：
- 協議 – 所有正確操作的節點必須採用相同的值（在文章中該屬性也稱為安全屬性）。 目前正在運行的所有節點（未發生故障或與其他節點失去聯繫）必須達成協議並接受一些最終的共同值。
這裡重要的是要理解我們正在考慮的分散式系統中的節點想要達成一致。 也就是說，我們現在談論的系統中，某些東西可能會簡單地失敗（例如，某些節點失敗），但在這個系統中絕對不存在故意與其他節點作對的節點（拜占庭將軍的任務）。 由於此屬性，系統保持一致。
- 誠信 — 如果所有正確工作的節點提供相同的值 v，這意味著每個正確運行的節點都必須接受這個值 v.
- 終止 – 所有正確運行的節點最終都會呈現一定的值（活性屬性），這使得演算法能夠在系統中取得進展。 每個單獨正確運行的節點遲早必須接受最終值並確認它：“對我來說，這個值是真實的，我同意整個系統。”
共識演算法如何運作的範例
雖然該演算法的屬性可能並不完全清楚。 因此，我們將透過一個例子來說明，在具有同步訊息傳遞模型的系統中，最簡單的共識演算法會經歷哪些階段，其中所有節點都按預期運行，訊息不會丟失，也不會中斷（這真的會發生嗎？）。
- 這一切都始於求婚（Propose）。 假設一個客戶端連接到一個名為“Node 1”的節點並啟動了一個事務，將一個新值傳遞給該節點 - O。從現在開始，我們將稱為“Node 1” 提供。 作為提議者，「節點 1」現在必須通知整個系統它有新數據，並向所有其他節點發送訊息：「看！ 我突然想到了「O」的意思，我想把它寫下來！ 請確認您還將在日誌中記錄“O”。”
- 下一階段是對提議值進行投票（投票）。 它是做什麼用的？ 其他節點可能會收到更新的訊息，並且它們擁有相同交易的資料。
當節點「節點 1」發送其提議時，其他節點會檢查其日誌中是否有有關此事件的資料。 如果沒有矛盾，節點宣布：「是的，我沒有關於此事件的其他數據。 “O”值是我們應得的最新信息。”在任何其他情況下，節點都可以回應“節點 1”：“聽著！ 我有關於這筆交易的最新數據。 不是‘O’，而是更好的東西。”
在投票階段，節點做出決定：要麼全部接受相同的值，要麼其中一個節點投反對票，表示他擁有更新的資料。
- 如果一輪投票成功並且每個人都讚成，那麼系統將進入一個新階段——接受該值。 「節點1」收集其他節點的所有回應並報告：「每個人都同意值「O」！ 現在我正式宣布「O」是我們的新意義，對每個人都一樣！ 把它記在你的小本子上，不要忘記。 把它記在你的日誌裡！”
- 其餘節點發送確認（已接受），表明它們已寫下值“O”；在此期間沒有任何新內容到達（一種兩階段提交）。 在這個重大事件之後，我們認為分散式事務已經完成。
因此，簡單情況下的共識演算法由四個步驟組成：提議、投票（voting）、接受（accept）、確認接受（accepted）。
如果在某個步驟我們無法達成一致，那麼演算法會再次開始，同時考慮拒絕確認建議值的節點提供的資訊。
非同步系統中的共識演算法
在此之前，一切都很順利，因為我們談論的是同步訊息傳遞模型。 但我們知道，在現代世界中，我們習慣非同步完成所有事情。 類似的演算法如何在具有非同步訊息傳遞模型的系統中工作，在該系統中，我們認為節點響應的等待時間可以是任意長的（順便說一句，節點故障也可以被認為是當節點可以響應任意長的時間）。
現在我們知道了共識演算法的工作原理，對於那些好奇的讀者來說，有一個問題是：在具有非同步訊息模型的 N 個節點的系統中，有多少個節點可以失敗，以便系統仍然可以達成共識？
正確答案和理由都在劇透後面。正確答案： 0。 非同步系統中即使有一個節點發生故障，系統也將無法達成共識。 這一說法在某些圈子裡眾所周知的 FLP 定理中得到了證明（1985 年，Fischer、Lynch、Paterson，鏈接到文章末尾的原文）：“如果至少一個節點發生故障，就不可能達成分佈式共識” 。
夥計們，那麼我們有一個問題，我們已經習慣了一切都是異步的。 就是這樣。 如何繼續生活？
我們只是在談論理論、數學。 從數學語言翻譯成我們的工程語言，「無法達成共識」是什麼意思？ 這意味著“不可能總是實現”，即存在無法達成共識的情況。 這是一個什麼樣的案例呢？
這正是對上述活性屬性的違反。 我們沒有一個共同的協議，在沒有得到所有節點回應的情況下，系統無法取得進展（無法在有限時間內完成）。 因為在非同步系統中，我們沒有可預測的回應時間，我們無法知道節點是否已崩潰或只是需要很長時間才能回應。
但在實務上我們可以找到解決辦法。 讓我們的演算法在故障的情況下能夠長時間工作（有可能無限期地工作）。 但在大多數情況下，當大多數節點都正常運作時，我們的系統就會取得進展。
在實踐中，我們處理部分同步通訊模型。 部分同步的理解如下：一般情況下，我們有一個非同步模型，但形式上引入了某個時間點的「全局穩定時間」的概念。
這一刻可能不會持續很長時間，但總有一天會到來。 虛擬鬧鐘將會響起，從那一刻起我們就可以預測訊息到達的時間增量。 從這一刻起，系統從非同步轉為同步。 在實踐中，我們處理的正是這樣的系統。
Paxos演算法解決共識問題
是解決部分同步系統的共識問題的一系列演算法，但可能會出現某些節點失敗的情況。 Paxos的作者是 。 他於1989年提出了該演算法的存在性和正確性的形式證明。
但事實證明這個證明絕非微不足道。 第一份出版物於 1998 年發布（33 頁），描述了該演算法。 事實證明，這篇文章極難理解，2001 年發表了一篇長達 14 頁的文章解釋。 給出出版物的數量是為了表明事實上共識問題一點也不簡單，這些演算法的背後隱藏著最聰明的人的大量工作。
有趣的是，萊斯利·蘭波特本人在演講中指出，在第二篇解釋文章中，有一個陳述，一行（他沒有具體說明是哪一行），可以有不同的解釋。 正因為如此，大量現代 Paxos 實作並不能完全正確運作。
詳細分析 Paxos 的工作需要不止一篇文章，因此我將嘗試非常簡短地傳達該演算法的主要想法。 在我的文章末尾的連結中，您將找到進一步深入研究該主題的資料。
Paxos 的角色
Paxos演算法有一個角色的概念。 讓我們考慮三個主要的（有附加角色的修改）：
- 提議者（也可以使用以下術語：領導者或協調員）。 這些人從用戶那裡了解一些新價值並承擔領導者的角色。 他們的任務是發起一輪新值提案並協調節點的進一步行動。 此外，Paxos 允許在某些情況下存在多個領導者。
- 接受者（投票者）。 這些節點投票接受或拒絕特定值。 他們的角色非常重要，因為決策取決於他們：在共識演算法的下一個階段之後系統將（或不會）進入什麼狀態。
- 學習者。 當系統狀態改變時，節點只接受並寫入新的接受值。 他們不做出決定，只是接收數據並將其提供給最終用戶。
一個節點可以在不同情況下組合多個角色。
法定人數的概念
我們假設我們有一個系統 N 節點而其中最大的 F 節點可能會失敗。 如果 F 個節點失敗，那麼我們至少一定要有 2層+1 受體節點。
這是必要的，這樣即使在最壞的情況下，我們也始終擁有大多數正常工作的「好」節點。 那是 女+1 同意的“好”節點，最終值將被接受。 否則，可能會出現我們不同的地方群體具有不同的含義並且彼此之間無法達成一致的情況。 因此，我們需要絕對多數才能贏得投票。
Paxos共識演算法如何運作的整體思路
Paxos演算法涉及兩個大階段，每個階段又分為兩個步驟：
- 第 1a 階段：準備。 在準備階段，領導者（提議者）通知所有節點：「我們正在開始一個新的投票階段。 我們有新一輪。 本輪次數為n。 現在我們將開始投票。” 目前，它只是報告新周期的開始，但不報告新值。 此階段的任務是啟動新一輪並告知每個人其唯一編號。 輪數很重要，它必須大於所有先前領導者的所有投票數。 因為正是透過這個輪數，系統中的其他節點才能了解領導者資料的最新程度。 其他節點很可能已經有了後來幾輪的投票結果，並且只會告訴領導者他落後於時代。
- 第 1b 階段：承諾。 當接受節點收到新投票階段的編號時，可能有兩種結果：
- 新投票的數量 n 大於接受者先前參與的任何投票的數量。 然後acceptor向leader發送承諾，不再參與數量低於n的投票。 如果接受者已經對某件事進行了投票（也就是說，它已經在第二階段接受了某些值），那麼它將接受的值和它參與的投票數附加到它的承諾中。
- 否則，如果接受者已經知道較高編號的投票，它可以簡單地忽略準備步驟並且不回應領導者。
- 第 2a 階段：接受。 領導者需要等待法定人數（系統中的大多數節點）的回應，如果收到所需數量的回應，那麼他有兩種事件發展選擇：
- 一些接受者發送了他們已經投票贊成的值。 在這種情況下，領導者從投票中選擇數量最多的值。 我們將此值稱為x，它會向所有節點發送一條訊息，例如：“Accept (n, x)”，其中第一個值是其自己的Propose 步驟中的投票數，第二個值是每個人收集的值， IE。 我們實際投票的價值。
- 如果沒有一個接受者發送任何值，但他們只是承諾在這一輪中投票，則領導者可以邀請他們為他們的價值投票，即他首先成為領導者的值。 我們稱之為 y。 它向所有節點發送一條訊息，例如：“Accept (n, y)”，與先前的結果類似。
- 第 2b 階段：已接受。 此外，接受者節點在收到來自領導者的「Accept(...)」訊息後，只有在沒有承諾某些（其他）的情況下才同意該訊息（向所有節點發送他們同意新值的確認）領導者以輪數參與投票 n' > n，否則他們會忽略確認請求。
如果大多數節點對領導者做出了回應，並且所有節點都確認了新值，則認為新值被接受。 萬歲！ 如果未達到多數或有節點拒絕接受新值，則一切重新開始。
這就是 Paxos 演算法的工作原理。 每個階段都有很多微妙之處，我們實際上沒有考慮各種類型的故障、多個領導者的問題等等，但本文的目的只是向讀者介紹高層次的分散式運算世界。
另外值得注意的是，Paxos 並不是唯一的一種，還有其他演算法，例如， ，但這是另一篇文章的主題。
進一步研究材料的鏈接
初學者級：
- ，Preethi Kasireddy，Medium 上的部落格文章
- ，Adi Kancherla，Medium 上的部落格文章
- ，伊泰·亞伯拉罕，博客
- ，Ittai Abraham，部落格文章
萊斯利·蘭波特等級：
- ，Fischer、Lynch 和 Paterson，研究論文，1985 年
- ，萊斯利·蘭波特，研究論文，1998
- ，萊斯利·蘭波特，研究論文，2001
來源： www.habr.com