[TOC] # 簡介 為了解決分布式場景下數據一致性的問題,paxos算法誕生了. 假設有一組可以提出提案的進程集合,提案用`[編號,值]`的形式描述,一致性算法需要保證以下幾點: * 只有當一個提案被提出后才能被選定 * 這些進程集合中只有一個提案會被選定 * 如果某個進程認為某個提案被選定了,那么這個提案確實是已經被選定了 該一致性算法分為三個角色,我們用proposer,acceptor和learner來表示. proposer可以批準提案,acceptor可以提交提案,而learner只能獲取已經被批準的提案. # 階段一 1. proposer選擇一個提案編號n,然后向超過半數的acceptor發送編號n的prepare請求. 2. 如果以個acceptor收到了一個編號為n的proposer請求,并且編號n大于這個acceptor之前已經響應的proposer請求編號,那么它就會將已經批準過的最大編號的提案作為響應發送給proposer,并且承諾不會再批準任何編號小于n的提案 # 階段二 1. 如果proposer收到了半數以上的acceptor對編號n的prepare請求的回應,那么它就會發送一個針對`[n,v]`提案的accept請求給哪些acceptor.這里v值就是收到響應中編號最大的提案的值 2. 如果acceptor收到了這個針對`[n,v]`提案的accept請求,只要該acceptor還沒有對編號大于n的提案進行響應,他就會通過這個提案 paxos通過引入過半提交的概念解決了在兩階段和三階段提交協議中會出現的種種問題. 這個世界上只有一種分布式一致性算法,那就是paxos