約Paxos的一些問題

Question

我被弄得價值選擇通過提案人。用 來舉例說明。如果現在要保人要鎖定文件，那麼它會發送L1是processer_number，且v1的「鎖定文件」的價值，受體接受它。 比提議者想要解鎖文件，並且發送（l2> l1）v2是「解鎖文件」的值，之後，接受者返回最後的值並且提議者選擇它並且再次發送。

in這個例子中，V2失去了什麼？或者這個例子中的真實過程是什麼？ 還有，這些是兩輪還是一輪呢？如何處理這一輪？

Answer 1

Paxos不是原子寄存器;一旦值爲通過選擇的Paxos，它不能改變

首先，注意到你的鎖是有限狀態機：

  on_lock 
     .-----------. 
     |   | 
+------+---+ +--v-----+ 
| UNLOCKED | | LOCKED |<--- start 
+------^---+ +--+-----+ 
     |   | 
     `-----------' 
     on_unlock 

Paxos可以用來決定一個轉換序列;但每個新的轉換都必須在新的Paxos實例中決定。

我建議考慮看看一些周圍StackOverflow上的其它的Paxos問題：

• paxos value choice
• implementation of Paxos algorithm
• Questions about Paxos implementation

Answer 2

我們需要描述鎖定協議，我們可以使用Paoxs運行以瞭解何時有多個值可用並查看選擇值的結果。

的鎖處於格式L={T,P}，其中P是進程持有鎖和T是過程花費鎖的時間保持鎖定令牌值的小區。獲取客戶端發送V={Lc,Ln}其中Lc是它認爲是當前鎖定令牌和Ln={T',P'}是它要設定新的鎖定令牌鎖。可以發送特殊標記Nil來解鎖該鎖。如果消息未指出與當前令牌匹配的正確Lc，則新令牌未設置。此比較和交換（CAS）可防止錯誤應用延遲解鎖消息。當客戶端可以竊取它時它也可以超時鎖定;如果兩個進程發送兩個賽車的消息{L1,L2}和{L1,L3}只有一個能夠成功。進程通過檢查作爲鎖定值L的返回值來了解其操作是否成功。一個進程可以查詢通過發送{Nil,Nil}這是解鎖一個打開的鎖是「什麼都不做」 CAS鎖值;但是如果鎖關閉，則返回誰擁有鎖。

寫操作必須經過領導者。如果一個節點知道它不是領導者，它應該將客戶端重定向到領導者。如果節點不知道誰是領導者，它應該拋出一個錯誤，客戶端應該隨機選擇另一個節點。如果節點認爲它是領導者，那麼只有在確定大多數節點已接受新值時才能對客戶端做出響應。這是因爲Paxos確保多數人接受的價值已被集羣持久化。如果節點處於領先地位，則不會聽到大多數接受，它無法響應客戶端。它可能與其他節點隔離。其他節點可能有新當選的領導。這也適用於{Nil,Nil}需要大部分接受的查詢，以確認領導者仍然是領導者，以告訴客戶當前的鎖定值。最終，節點應該聽到一個新的領導是否存在，否則超時試圖獲得大多數人接受的價值。然後，它應該將客戶端重定向到新的領導者，否則向客戶端返回錯誤。

現在我們可以在領導故障轉移期間考慮多個值。客戶端A發送一個有效的CAS更新V1，該更新應該連接到三節點羣集的領導者節點X。節點X自己發送accept(N1,V1)，節點Y和Z。它接受自己的價值，並從Y獲得承諾，但網絡將該消息丟棄到Z。然後節點X變黑，並停止發送任何消息一段時間。它可能已經死亡或停滯，但我們還不知道。它已經看到了大部分X,Y，但現在是一個神祕的薛定諤的貓，要麼死或活，直到我們看到另一個消息來知道它的命運。無論接下來發生什麼，Paxos都選擇使用協作來獲得一致和正確的結果。

經過一段時間後，節點Z超時，因爲它沒有聽到領導者太長時間。它向自身和其他節點發出propose(N2)。它從節點Y和promise(N2,empty)自身獲取promise(N2,V1)。它擁有大多數Y,Z並且可以領先。只有節點X知道值V1已被大多數人接受，並且客戶是否已被告知其CAS成功;但它是沉默的。節點Z必須做出保守的選擇。如果假設X已經死亡，則可能是錯誤的：節點X可能處於活動狀態，並且可能已告知客戶端操作成功。節點Z必須協作並以V1作爲其第一值完成最後領導者的部分工作。所以它將accept(N2,V1)發送給所有三個節點。現在，如果節點X已經死了或者已經告訴客戶端操作成功了，那麼這並不重要。在任何情況下，鎖定協議都不會被違反，並且如果錯誤重試，客戶端將最終發現它有鎖定;它沒有看到也不在意哪個提案和哪個節點實施了這項工作。