假設拍賣者各自在自己家裡拍賣,透過郵局信件發出自己的拍賣資訊,拍賣者之間除非等到郵局投遞人告訴他們彼此之間的報價,否則是無法知道對方報價的。如果郵局信件投遞這個環節出了問題,投遞速度慢了甚至無法投遞了,那麼整個拍賣程式就無法繼續進行下去。
Paxos解決共識思路
Paxos是一個解決共識問題consensus problem的演算法,現實中Paxos的實現以及成為一些世界級軟體的心臟,如Cassandra, Google的 Spanner資料庫, 分散式鎖服務Chubby. 一個被Paxos管理的系統實際上談論的是值 狀態和跟蹤等問題,其目標是建造更高可用性和強一致性的分散式系統。
Paxos完成一次寫操作需要兩次來回,分別是prepare/promise, 和 propose/accept:
第一次由提交者Leader向所有其他伺服器發出prepare訊息請求準備,所有伺服器中大多數如果回覆諾言承諾就表示準備好了,可以接受寫入;第二次提交者向所有伺服器發出正式建議propose,所有伺服器中大多數如果回覆已經接收就表示成功了。
為了詳細描述這個兩段過程,首先讓我們定義一下我們將使用的一些名詞術語:
·一個流程是系統中計算機的一個. 人們使用有關複製或節點等詞語表達,都差不多。
·一個客戶端是屬於系統中一個成員的計算機,但是詢問系統值是什麼或者要求系統獲取一個新的值。
Paxos構建分散式資料庫的小片段: 它僅僅實現流程將一個新的東西精確地寫入系統中,流程是由Paxos的一個例項管治,可以失敗或者不知道任何東西、或者大多數流程都知道一個同樣的值,這就是共識,Paxos並不真的告訴我們如何用它來構建資料庫或類似的東西,它只是負責獨立節點之間通訊的流程, 這些流程伺服器會基於一個新值執行決定,Paxos會儲存一個值資料,只是一次性的,一旦你第一次設定以後就不能再改變它。
Paxo讀操作
其實Paxos精華是在寫操作,將讀操作放在寫操作前面講解,是著重Paxos以大多數伺服器達成共識為重要標誌,透過讀取判斷是否達成共識這一狀態。
為了從Paxos系統中讀取一個值資料,客戶端會請求讀取所有流程中儲存的當前值,然後從大多數流程伺服器中獲得這個值,如果數量湊不夠大多數或者沒有足夠的客戶端響應,讀取操作失敗,下面圖示你會看到一個客戶端詢問其他節點他們的值是多少,這些節點返回值給客戶端,當客戶端獲得了大多數節點的響應,返回的值都是同樣的,它就算成功地讀操作了,並順便儲存讀結果。
與單節點系統(只有一臺伺服器)相比這有些奇怪,這兩個系統中,客戶端都需要觀察系統已決定狀態,但是在非分散式系統中像MySQL或一個memcached伺服器中, 客戶端只需直接向標準的狀態儲存的伺服器地址獲取狀態即可,在簡單的Paxos中, 客戶端也是同樣的方式觀察狀態,但是因為並沒有標準的狀態儲存的伺服器地址,它需要詢問所有的成員,以便能夠確定僅有一個會報告值資料,實際上是大多數節點都持有的值資料,如果客戶端詢問一個節點,有可能這個節點流程已經過期,得到了錯誤的值資料,流程失效過期的原因有很多:由於不可靠的網路導致本應送達到它們的訊息丟失了;或者他們也許當機然後使用了一個過期狀態恢復;或者演算法還在執行計算中,流程並沒有正好得到訊息等等。在現實中使用Paxos實現時,其實不需要每個節點都進行一次讀取,會有更好的讀取方式,但是他們都是拓展的原始 Paxos 演算法。
Paxos寫操作
當一個客戶端要求寫入系統一個新值時,讓我們看看Paxos讓我們叢集的流程都做了什麼?下面的過程都是隻有一個值的寫入,最終我們能用這個流程作為原始資料,允許值資料在彼此之間一個個設定,但是基本的Paxos演算法管治了一個新值資料的寫操作流程, 然後做重複的事情。
首先Paxos管理的系統中一個客戶端要求寫入一個新值,客戶端這裡如圖所示是紅圈,其它流程是藍圈, Paxos能保證客戶端傳送它們的寫請求到Paxos叢集中任何成員, 這裡演示中客戶端隨機挑選流程中任意一個,這種方式是重要且巧妙的,意味著沒有任何單點風險,意味著我們的Paxos管治系統能繼續保持線上可用,無論任何一個節點當機或其他不可用原因無響應。如果我們設計一個特定節點作為“推薦人proposer”或者 "the master" 等, 如果這個主節點宕機,那麼整個系統就崩潰了。
當寫請求被接受後,Paxos流程會接受這個寫新值到系統中請求“建議”, “建議”是Paxos中一個正式概念: 向一個Paxos管治的系統建議可能會成功或失敗,需要步驟來確保共識能夠達成維繫,這個建議以準備訊息從那些與客戶端連線的流程節點們被髮往整個系統。
序列號
這個準備訊息儲存在被建議的值資料中,它們也稱為序列號sequence number,序列號是由建議流程產生的,它定義了接受流程應該準備接受帶有序列號的建議,這個序列號是關鍵: 它用於表明新舊建議之間的區別,如果兩個流程試圖獲得需要設定一個值,Paxos認為最後一個流程應該有優先權,這樣讓流程分辨哪個是最後一個,這樣它就能設定最新的值。
這些接受的流程能夠進行在系統中關鍵的檢查:這個在到來的準備訊息中序列號是我見過的最高階別嗎?如果是,那就很cool, 我能準備好接受將要到來的值資料,那就不要管之前聽到的任何其他值資料了,你能看到這個過程在右邊演示中:客戶端每隔一段向一個流程建議一個新值,這個流程傳送準備訊息給其他流程,然後那些流程注意到這是一個成功的更高的超過舊的新序列號,然後就放手那些舊建議。
這裡有一個順序的設計(先傳送準備訊息),這是為避免單點風險,如果沒有這個順序,Paxos中成員就無法分辨哪個建議是他們可以有信心地準備接受的。
我們不能想象有另外不同的共識演算法,不是按照如下步驟:首先傳送第一個訊息詢問其他流程,以確保將設定的新值是最新的值,儘管方式可以再簡單些,但是可能就不能滿足共識演算法安全的需求了,如果兩個流程正好同時建議不同的值,如下所示:
大自然經常會這樣欺騙我們,每個包都能另外一半的流程相信它們接受的也許是正確也許是錯誤的值,系統將進入一個僵局,存在兩個相同數量的組卻有不同的值,那麼就無法確定大多數這個概念了,這個僵局能夠被第一個Paxos訊息避免,因為Paxos的序列號,那些有問題的建議將有被其他更低的序列號,這樣序列號更高的建議就會毫不含糊地被大多數流程接收,它們也首先獲得了更高的序列號,然後如果接受到更低的序列號就會拒絕,Paxos 就是這樣透過用序列號控制整個系統的時間節奏。
上圖演示了客戶端首先發一個準備訊息給Paxos流程,Paxos流程會檢查下一步將到來的建議的序列號,以分辨是否準備接受這個新值,所有流程都是這樣消除歧義,共識由此達成。
注意:保證沒有兩個建議使用相同的序列號是很重要的,這是確保他們的順序,這樣每個序列號只有一個建議,這樣才能比較兩個建議,實現Paxos時,全域性唯一有序的序列號實際是精確系統時間和叢集中節點數量的複製,隨著時間不斷增加,從來不會重複。
Paxos第一階段:準備Perpare/諾言Promises
Paxos的第一階段是prepare/promise,準備階段就是將建議值傳送到各個目標節點。
為了決定一個建議是否已經有足夠的回覆諾言promises, 提交建議者只是統計一下它接受到的 promise 訊息數量,然後和整個系統中節點伺服器數量比較一下,“足夠”意味著大多數(N/2 + 1)個流程伺服器在某段時間內都回復了諾言promises。如果超過一半的流程伺服器沒有返回諾言,這意味著這個建議沒有被大多數透過,那麼在前面描述的讀演算法中就不能滿足大多數的要求,也就不能達成共識,這個建議就退出。其他包括網路分割槽錯誤也可能會阻止大多數達成共識,
第二階段:Paoxs接納Acceptance
當完成prepare/promise階段,進入了 propose/accept階段。
一旦建議提交者已經從大多數其他流程伺服器獲得了諾言,它會要求許諾的流程伺服器接收它們之前承諾接受的新值資料,這是一個“確認commit”階段,如果沒有衝突建議 失敗或分割槽錯誤,那麼這個新建議將被所有其他節點接受,那麼Paxos過程就完成了。
你能看到右邊的演示,注意這個演示比上面promise在最後多了一個動作,也就是提交建議者將新值發給那些許諾言的流程伺服器,讓它們接受了這個新值。
接受的過程也許可能會發生失敗,在回覆了諾言訊息以後,在接受到Accept訊息之前,如果有足夠多的伺服器正好在這個時間段失敗,那麼接受行為只能是少數伺服器,那麼Paxos進入了厄運狀態:一些流程伺服器接受了新值,而不是全部的,這種不一致已經在前面讀操作中描述:一個客戶端試圖從系統中大多數節點伺服器讀取它們同意接受的值,它發現一些節點伺服器報告有不同的值資料,這會引起讀失敗,但是Paxos還保持一致性,不允許在沒有達成共識情況下任何寫操作發生,這種壞的情況在實踐中經常透過重複接受階段來讓大多數節點最終接受。
總結
Paxos演算法是保證在分散式系統中寫操作能夠順利進行,保證系統中大多數狀態是一致的,沒有機會看到不一致,因此,Paxos演算法的特點是一致性>可用性。
vector clock向量時鐘是另外一種保證複製的演算法,其特點是可用性>一致性,但是,一旦發生衝突,不像Paxos能自行解決,需要人工干預編寫程式碼解決。
Paxos演算法和Vector Clock都是由Leslie Lamport提出。