Paxos（帕克索斯）一緻性算法[卷一]

文章目錄

• • 導讀
  • 究竟是什麼？
  • 主要3種角色
  • 主要流程
  • 問題：為什麼能做到一緻性？

導讀

譯《The Part-Time Parliament》——終于讀懂了Paxos協定！

究竟是什麼？

簡單說，paxos是為了解決強一緻性的算法

算法中，大概有3種角色（一人可以作為多個角色）

主要3種角色

• proposer：提議發起者

  proposer可以發起proposal（提議）
   
   proposal（提議）包括：
   
   1.Proposal Value：提議的值；
   
   2.Proposal Number：提議編号，要求提議編号不能沖突；
             

  

  proposer：提議發起者，主要有兩種行為：
   
   1.向acceptor發prepare請求
   
   2.向acceptor發accept請求
             

• acceptor：提議接受者，主要行為：

  根據協定規則，對（proposer：提議發起者）的請求作出應答；
             

• learner：提議學習者，主要行為：

  可以根據（acceptor：提議接受者）的狀态，學習最終被确定的值。
             

主要流程

1.[prepare]階段

進行[prepare]請求

（proposer：提議發起者）
	
	選擇一個proposalValue(提議編号)n，
	
	向所有的acceptor廣播prepare(n)請求。
           

進行[promised]響應

（acceptor：提議接受者）
	
	若proposalValue(提議編号)n比之前階段接收的prepare(請求)都要大，
	{
    promised(承諾)之後的[accept]階段，proposalValue(提議編号)隻能>=n
    promised(承諾)之後新的[prepare]階段，proposalValue(提議編号)隻能>n
	}
	并傳回上一次的[accept]階段中，
	proposalValue(提議編号)m < n  且
	m為上一次[accept]階段中最大proposalValue(提議編号)的proposal(提議)
           

2.[accept]階段

進行[propose]請求

（proposer：提議發起者）
   
   得到了多數acceptor的承諾後，如果沒有發現有一個acceptor接受過一個值
   
   那麼向所有的acceptor發起自己的值和提議編号n，否則，
   
   從所有接受過的值中選擇對應的提議編号最大的，作為提議的值，提議編号仍然為n。
           

進行[accept]響應

（acceptor：提議接受者）
   
    接收到提議後，如果該提議編号不違反自己做過的承諾，則接受該提議。
           

問題：為什麼能做到一緻性？