paxos演算法

『壹』 號稱史上最晦澀的演算法paxos，如何變得平易近人

分布式一致性演算法（Consensus Algorithm）是一個分布式計算領域的基礎性問題，其最基本的功能是為了在多個進程之間對某個（某些）值達成一致（強一致）；進而解決分布式系統的可用性問題（高可用）。Paxos是最重要的分布式一致性演算法，很多人都把它作為「分布式一致性協議」的代名詞（Mike Burrows, inventor of the Chubby service at Google, says that「there is only one consensus protocol, and that』s Paxos」）。
關於Paxos的歷史和原理，已經有很多經典的論文可以參考，也有廠內外的文章有詳細的描述，本文就不再重復了。感興趣的同學可以閱讀下這些論文[1,2,3,4]。

『貳』 如何淺顯易懂地解說 Paxos 的演算法

Paxos演算法解決的問題是在一個可能發生消息可能會延遲、丟失、重復的分布式系統中如何就某個值達成一致，保證不論發生以上任何異常，都不會破壞決議的一致性。

一個典型的場景是，在一個分布式資料庫系統中，如果各節點的初始狀態一致，每個節點都執行相同的操作序列，那麼他們最後能得到一個一致的狀態。為保證每個節點執行相同的命令序列，需要在每一條指令上執行一個「一致性演算法」以保證每個節點看到的指令一致。

一個通用的一致性演算法可以應用在許多場景中，是分布式計算中的重要問題。 節點通信存在兩種模型：共享內存和消息傳遞。Paxos演算法就是一種基於消息傳遞模型的一致性演算法。

分析Paxos演算法的目的

Paxos演算法的目的是為了解決分布式環境下一致性的問題。多個節點並發操縱數據，如何保證在讀寫過程中數據的一致性，並且解決方案要能適應分布式環境下的不可靠性（系統如何就一個值達到統一）。

Paxos演算法中，可分為4種角色：

• Proposer：提議發起者，處理客戶端請求，將客戶端的請求發送到集群中，以便決定這個值是否可以被批准。

• Acceptor：提議批准者，負責處理接收到的提議，他們的回復就是一次投票。會存儲一些狀態來決定是否接收一個值。

• Client：產生議題者，Proposer就像Client的使者，由Proposer使者拿著Client的議題去向Acceptor提議，讓Acceptor來決策。

• Learner：最終決策學習者，最終學習的目標是Acceptor們最終接受了什麼議題？

Paxos演算法的原理

例如：公司商定年會舉辦的地點，每個人都可以提出建議。在現實環境中我們可以在一個會議室共同討論或在微信群中討論（基於內存共享方式）；但在基於消息傳遞的分布式環境中每個人只能通過手機簡訊與其它人通過。如何在這種會延遲、丟失的環境中確定一個年會舉辦地點。

Paxos演算法是這樣解決這個問題：

每個人都可以提出建議、同意建議、接受建議

少數服從多數。只要建議被多數人同意即可確定該建議。

於是確定以下討論方式：

• 只有被提出來的建議才能被大家同意。

• 最終只能確定一個建議。

• 如果某個人認為大家同意了某 個建議，那麼這個建議必須真的是被大家同意的。

Paxos演算法圖解



在實現環境中會通過一次提議，選擇一個Leader。後續所有的提議都只能由Leader提出。

原來paxos演算法里的角色都是這樣的不靠譜，不過沒關系，結果靠譜就可以了。該演算法就是為了追求結果的一致性。

原文鏈接：什麼是Paxos演算法？Paxos演算法是區塊鏈核心演算法之一

『叄』 如何淺顯易懂地解說 Paxos 的演算法

Paxos真的並不是很容易理解，而且最初版本的Paxos也不能實現，相對而言一些變種演算法更加容易理解，而且在工程實現上也比較簡單。

其實看論文確實是最有效的，但卻不是最高效的。理解運作過程也好，推導過程也好，大家的回答都是為了幫助大家更高效的掌握這門演算法。大家的回答已經很好， 我這里作為補充，也是算另一個角度，幫助大家去理解paxos的數學推導過程，寫了這么一篇文章：Paxos理論介紹(1): 樸素Paxos演算法理論推導與證明 - 分布式一致性與高可用實踐 - 知乎專欄。希望能幫到大家。

『肆』 chubby的設計目標是什麼4 paxos演算法在chubby起什麼作用

其實就是簡單的 replica
冗餘存在的目的就是為了防止掛掉
任何形式的掛掉都要防止
基本的原理異常的簡單
如下：
每一個replica HDFS ，HBse 這些都有各自的replica
每一個replica都會企圖在 zookeeper 的某一個目錄節點獲取一個鎖
拿到鎖的就是master ， 比如說replica（1）拿到了鎖，但是需要定期的和zookeeper 交流感情，
要麼就是zookeeper periodical 的ping一下，看看那個replica（1）還活著沒有，要麼就是replica（1）主動去報道，告訴master 「 呵呵我還活著」 這個叫 master session
其他沒拿到鎖的 replica (2.3.4.5.6.)就告訴 zookeeper 說：「你要是覺得那個replica（1）掛了你告訴我一聲 啊！
注意： 是覺得哦！ 這里分兩種可能
1） replica（1）掛了
2） network partition 把replica（1） 從網路中物理的隔開了。
這個時候其他的replica（2.3.4.5.6.) 就會再去爭搶那個 master了.

這就是冗餘機制 其實 hdfs的冗餘機制沒啥特別的 ， 主要是 作為BigTable的開源實現，NONsql資料庫的特性比較重要吧

而且zookeeper 本身 作為 Google Chubby 的開源實現 ，也是通過實現 PAXOS 演算法來保持 自身的 Consensus 的 只不過它是建立在 TCP 協議基礎上的， 所以zookeeper吧Chubby的演算法改進了一下換了個名字叫 ..total order broadcast protocol 略無恥.

所謂特點的話： 其實就是在有這個zookeeper （Chubby） 以前 Google 使用另外一種演算法來保證核心鎖機制的 Consensus的 .. 只是那個有很多問提， 需要有人值守 這個就是我上面為什麼提到掛掉的那兩種可能的原因

基本上就是這樣了 。。。
你要是想學的話 Google scholar + Hadoop in action 用起來 五六個月就能有所小成了

『伍』 paxos演算法在chubby起什麼作用

其實就是簡單的 replica ... 冗餘存在的目的就是為了防止掛掉 任何形式的掛掉都要防止 基本的原理異常的簡單 如下： 每一個replica ... HDFS ，HBse 這些都有各自的replica 每一個replica都會企圖在 zookeeper 的某一個目錄節點獲取一個鎖

『陸』 raft演算法與paxos演算法相比有什麼優勢，使用場景有什麼差異

演算法（Algorithm）是指解題方案的准確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制。也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。如果一個演算法有缺陷，或不適合於某個問題，執行這個演算法將不會解決這個問題。不同的演算法可能用不同的時間、空間或效率來完成同樣的任務。一個演算法的優劣可以用空間復雜度與時間復雜度來衡量。
演算法中的指令描述的是一個計算，當其運行時能從一個初始狀態和（可能為空的）初始輸入開始，經過一系列有限而清晰定義的狀態，最終產生輸出並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化演算法在內的一些演算法，包含了一些隨機輸入。

『柒』 Paxos 演算法的幾種演算法

上面通過證明如果一個協議滿足B1-B3 約束條件，那麼就可以保證一致性。直接從這些約束得到preliminary protocol ，basic protocol 是preliminary protocol 的限製版，保證了一致性。complete Synod protocol 進一步限制了basic protocol ，滿足一致性和過程需求（progress requirements）。下面將這三個演算法的具體過程。 滿足B1，牧師發起選舉的編號必須滿足偏序關系，有一個方法是每個發起牧師使用遞增的數值作為選舉編號，但這樣牧師無法立即知道他們選的數值有沒有被其他牧師選作選舉編號已經被使用。還有一個方法是使用數字+牧師姓名作為選舉編號，這樣就避免了自己的選舉編號被其他牧師使用。
滿足B2，每次選舉的法定人數必須是一個大部分集合（majority set）Q，這樣任意兩個選舉都會有一個共同的牧師。這里大部分集合是一個靈活的選擇，在原文中Lamport 使用體重打比方，體重的人更有可能呆在議會大廳，這樣就可以使用體重超過一半的牧師集合作為大部分集合。至於實際情況中的大部分集合是什麼要看具體情況了。
滿足B3，要求每個牧師p 每次在發起選舉前必須找到B_qrm 中每個牧師q 的MaxVote(b,q,B)。
根據以上要求，可以得到初始協議：
1. 牧師p 選擇一個選舉編號b ，並發送NextBallot(b)送給其他牧師
2. 其他牧師q 在收到NextBallot(b) 後，返回LastVote(b,v) 給牧師p，v=MaxVote(b,q,B)$是小於b 編號的q 投的最大的贊成票。為了保證B3，q 不能在b 和b_bal 之間的選舉投贊成票。（如果q 在發送了LastVote(b,v)又對新的選舉投票了那麼v 也就不是q 投的最大贊成票）
3. 牧師p 從一個大部分集合Q 中每個牧師q 中都收到LastVote(b,v) 後，發起一個新的選舉，編號為b，法定人數為Q，法律d滿足B3。然後牧師p 將這個法律寫在自己賬目的背面，發送BeginBallot(b,d)給Q 中每個牧師。
4. 牧師q 收到BeginBallot(b,d) 後決定是否為這次選舉投贊成票，如果贊同，則他將發送Vote(b,q) 給牧師p。
5. 如果牧師p 收到Q 中每個牧師q 發來的贊成票Vote(b,q)，則將法律d 寫入他的賬目中，並向所有q發送Success(d) 消息。
6. 收到Success(d) 消息後，牧師q 將法律d 寫入到自己的賬目中。
說明：第一步表示發起法律的牧師p 希望下一個選舉的編號是b 。牧師q 用LastVote(b,v) 回應了牧師p 的請求，也就是向牧師p 通過法律時保證了v=MaxVote(b,q,B) 的被改變，具體來說就是不在b 和b_bal 之間的選舉投贊成票。
第三步要求法律d 需要滿足B3，這里我開始有點迷糊，實際系統中的值是客戶端決定的，而不應該是B3 決定的。這里我們還是用上面的key-value 資料庫的例子來理清下思路：當某個節點/牧師第一次發起更新前相當於B為空集，發起更新/選舉的操作不斷進行，直至所有法定人數（quorum）都對法律投了贊成票（即majority set 的節點都更新了該key-value 的值則認為更新成功），B3對應的就是之前的更新沒有成功，那麼新的選舉值需要保持的情況。第四步允許牧師可以不發送Vote(b,q) 或者發送幾次，對應的是發送的信息可能因為通信而失敗而未發送或者被多次發送。一旦牧師投了贊成票則確認可以修改該值。
考慮到最後第六步法律d 才被牧師q 寫入到賬目，有可能出現的情況就是在第五步的時候牧師p 將法律寫入到了自己賬目中，接著發送Success(d) 給其他牧師，其中因為通信或者牧師離開議會大廳而沒有被寫入到自己的賬目中，導致不一致。所以真正寫入到賬目時機應該是在第四步牧師q 在發送給牧師p 贊成票的同時就法律寫入到了各自賬目中。而不用考慮如何保證牧師q 第四步寫入的法律會導致不一致，因為法律如果沒有通過則還有更多的選舉來保證一致性。後面也談到了當法律第一次別寫入到賬目中算通過法律。 初始協議（Preliminary Protocol）要求每個牧師都保存 (i) 他發起的每個選舉； (ii) 他投的每個贊成票； (iii) 他發送的每個$LastVote$。為了簡化牧師需要保存的數據，我們對上面的協議做一個限制，得到基礎（Basic Protocol）協議。首先介紹三個新的參數：
lastTried[p] 牧師p 發起的最後一個選舉
prevVote[p] 牧師p 最近一次的投票
nextBal[p] 收到的選舉編號的b 的最大值，即牧師p參加的最大選舉編號
在初始協議中，每個牧師可以同時發起任意個選舉，在基礎協議中要求每個牧師只能發起一個選舉lastTried[p]，一旦發起一個選舉，那麼之前發起選舉的信息就都不重要了。在初始協議中要求每個牧師不能在b_bal 和b 之間投贊成票，在基礎協議中則更嚴格地要求不能給小於b 的選舉投贊成票。那麼基礎協議可以概述為下面幾步：
1. 牧師p 選擇一個大於lastTried[p] 的選舉編號b ，發送NextBallot(b)給其他牧師
2. 牧師q 收到NextBallot(b) 且b>nextBal[q]後設置nextBal[q]=b ，接著發送LastVote(b,v) 給牧師p，其中v==prevBa[q] 。（如果b 小於或等於nextBal[q]，則不回復）
3. 從滿足某個大部分集合Q 中每個牧師收到了LastVote(b,v) 信息，牧師p 發起一個編號為b ，法定人數為Q ，法律為d（滿足B3 ）的選舉，並將BeginBallot(b,d) 發送給Q 中每個牧師。（如果沒有滿足任意大部分集合Q 的牧師返回，則返回第一步）
4. 牧師q 收到BeginBallot(b,d) ，決定投贊成票，設置prevVote[p] 為這次投票，並發送Vote(b,q) 給牧師p。（如果在收到BeginBallot(b,d) 後發現b 不等於nextBal[q] 則忽略這條信息，說明這期間牧師q 還收到了其他的編號更大的選舉）
5. 牧師p 從大部分集合Q 中每個牧師q 收到了Voted(b,d) ，且b==lastTried[p] ，則認為這次選舉成功，將法律d 記錄在賬目中，並向Q 中每個牧師q 發功成功消息Success(d) 。
6. 每個牧師q 收到Success(d) 消息後將法律寫入賬目。
基礎協議是初始協議的限製版，因為兩者都對牧師沒有行為要求，所以也不保證過程（QS）。下面介紹一個保證過程的協議— 完整議會協議（complete Synode protocol）。 基礎協議保證了一致性卻沒有保證任何過程，因為它只闡述了牧師可能做什麼，沒有要求牧師應該做什麼。為了達到之前談到的過程需求（Qrogress Requirements），我們需要添加一些額外的要求使得牧師們盡快執行完2-6 步。
考慮一種情況如果牧師q 第二步收到的選舉編號b 都比之前收到的要大，那麼他就要放棄之前收到的所有選舉。可是在選舉編號為b 的選舉在未確認前，可能又會收到更大編號的選舉b』 ，這樣就無法通過任何法律，過程也不能保證。所以為了達到過程需求則需要一個選舉成功後再發起另一個選舉。而首先應該知道服務員傳遞消息和牧師處理消息的時間，在網路中常常通過設置timeout 來實現，同樣的如果超過了一定時間牧師沒有收到服務員的回復，則認為該服務員或者對應的牧師離開了議會大廳。
假設牧師執行一個動作在7 分鍾以內，服務員傳遞一個消息在4 分鍾以內，那麼一個牧師p 發送消息給牧師q ，希望其回復的時間應該是在22 分鍾內（7+4+7+4 分鍾）。
有了上面時間的假設，再考慮上面討論過的情況，如果發起選舉的牧師p 會在第二步和第四步期望22 分鍾內收到其他牧師的回復，如果沒有則可能是一些牧師或者服務員離開了議會大廳，或者還有一些牧師發起了編號更大的選舉。遇到這兩種情況都牧師p 應該終止本次選舉，而重新開始發起一個新的選舉，為了不至於新發起的選舉編號還是太小而仍不能執行，需要從其他牧師哪裡獲取最新的選舉編號，從而選取一個更大的編號發起選舉。
進而假設牧師p 是唯一能夠發起選舉的牧師且議會大廳內有大部分集合的牧師，那麼可以保證在99分鍾內通過一條法律：22 分鍾內發現了有更大編號的法律，22 分鍾內獲取最大編號並選擇個更大的編號，55 分鍾內完成1-6 步完成一次成功的選舉（疑問：既然只有牧師p 能夠發起選舉，那麼編號都是由其控制的，前兩步發現並選擇更大的編號似乎就沒有必要了。答：並不是所有的選舉都是president發起的，其他牧師發起選舉，president向其他希望發起選舉的牧師配發選舉編號）。從上面的過程我們發現完整議會協議需要一個選舉president的過程，president的選舉演算法不是文章重點，所以文章中僅用T 分鍾代替了選舉president的時間，這樣T+99 分鍾內可以通過一部法律。
文中選擇president的方法是誰的姓在字母表中最後，並將自己的姓發送給議會大廳內所有牧師，如果在T-11 分鍾內某個牧師沒有收到比自己姓在字母表中更靠後的姓，則認為自己是president（我覺得廣播體重也應該不錯，不是說體重更重的呆在議會大廳會更久么？^_^）。還有一個細節：在選舉president的時候每個牧師p 需要將自己的lastTried[p] 發送給其他牧師，以使得president能夠在第一次選舉時選擇一個足夠大的編號。
至此，通過選舉president和設置超時，完整議會協議就可以保證過程了。
多法律國會協議
上節的議會協議（complete Synod protocol）中，president被選舉出來後，每個希望發起選舉的牧師通知他，president給牧師配發選舉編號，每次僅通過一部法律。多法律國會協議（The Multi-Decree Parliment）選擇一個president通過一系列法律，且只需要執行前兩步一次即可。
具體方法是president第一步發送NextBallot(b,n) 代替NextBallot(b) ，表示希望通過n-b 之間的所有的法律，在president 的賬目上，編號n 之前的法律都是連續記錄了的，b>n 。其他牧師q 收到消息後將每部已經出現在其賬目中編號大於$n$的法律都返回給president，不在賬目上的返回正常的LastVote 信息。
下面談到多法律國會協議有關性質，首先是法律的順序，不同法律編號的選舉同時進行，發起選舉的每個牧師都認為自己是president（不知道president 是怎麼選舉出來的，也不知道法律通過的順序）。在完整議會協議第三步中法律被提議，第一次寫入到賬目上時稱法律被通過。當一個president需要提出新的法案時，他必須從大部分集合牧師中學習到那麼法律他們都投了贊成票，每部法律都被大部分集合牧師中至少一個牧師投了票，所以president發起新的選舉前總能學到所有之前通過了的法律。president不會在空缺的法律編號內填補重要的法律。，也不會亂序提議法律，所以協議滿足「法律有序性」：如果法律A 和法律B 都是重要的法律，法律A 在法律B 提議之前通過，那麼法律A 有比法律B 更低的法律編號。第二點屬性是president在選舉出後且沒有人再進出議會大廳，法律是按照下面步驟不斷通過的（對應完整議會協議的3-5步）：
3. president 向一個法定人數牧師中每個牧師發送BeginBallot ；
4.每個牧師向president 發送Voted 信息。
5.president向每個牧師發送Success 消息。這樣通過每部法律只需要三次消息傳遞，通過合並BeginBallot 和Success 命令可以進一步減少消息傳遞。

『捌』 共識演算法ByzantinePaxos（2010）是誰發明的

原始Paxos的BFT版本，在相同網路假設下存在1/3拜占庭故障節點時是安全的。這是由LeslieLamport發明的，是他最初的Paxos論文的延伸。

『玖』 分布式存儲中，怎樣使用paxos演算法保證數據的一致性

在分布式系統中，我們經常遇到多數據副本保持一致的問題，在我們所能找到的資料中該問題講的很籠統，模模糊糊的，把多個問題或分類糅合在一起，難以理解。在思考和翻閱資料後，通俗地把一致性的問題可分解為2個問題：
1、任何一次修改保證數據一致性。
2、多次數據修改的一致性。
在弱一致性的演算法，不要求每次修改的內容在修改後多副本的內容是一致的，對問題1的解決比較寬松，更多解決問題2，該類演算法追求每次修改的高度並發性，減少多副本之間修改的關聯性，以獲得更好的並發性能。例如最終一致性，無所謂每次用戶修改後的多副本的一致性及格過，只要求在單調的時間方向上，數據最終保持一致，如此獲得了修改極大的並發性能。
在強一致性的演算法中，強調單次修改後結果的一致，需要保證了對問題1和問題2要求的實現，犧牲了並發性能。本文是討論對解決問題1實現演算法，這些演算法往往在強一致性要求的應用中使用。
解決問題1的方法，通常有兩階段提交演算法、採用分布式鎖服務和採用樂觀鎖原理實現的同步方式,下面分別介紹這幾種演算法的實現原理。

兩階段提交演算法

在兩階段提交協議中，系統一般包含兩類機器（或節點）：一類為協調者（coordinator），通常一個系統中只有一個；另一類為事務參與者（participants，cohorts或workers），一般包含多個，在數據存儲系統中可以理解為數據副本的個數。兩階段提交協議由兩個階段組成，在正常的執行下，這兩個階段的執行過程如下所述：
階段1：請求階段（commit-request phase，或稱表決階段，voting phase）。
在請求階段，協調者將通知事務參與者准備提交或取消事務，然後進入表決過程。在表決過程中，參與者將告知協調者自己的決策：同意（事務參與者本地作業執行成功）或取消（本地作業執行故障）。
階段2：提交階段（commit phase）。
在該階段，協調者將基於第一個階段的投票結果進行決策：提交或取消。當且僅當所有的參與者同意提交事務協調者才通知所有的參與者提交事務，否則協調者將通知所有的參與者取消事務。參與者在接收到協調者發來的消息後將執行響應的操作。
舉個例子：A組織B、C和D三個人去爬長城：如果所有人都同意去爬長城，那麼活動將舉行；如果有一人不同意去爬長城，那麼活動將取消。用2PC演算法解決該問題的過程如下：
首先A將成為該活動的協調者，B、C和D將成為該活動的參與者。
階段1：A發郵件給B、C和D，提出下周三去爬山，問是否同意。那麼此時A需要等待B、C和D的郵件。B、C和D分別查看自己的日程安排表。B、C發現自己在當日沒有活動安排，則發郵件告訴A它們同意下周三去爬長城。由於某種原因，D白天沒有查看郵件。那麼此時A、B和C均需要等待。到晚上的時候，D發現了A的郵件，然後查看日程安排，發現周三當天已經有別的安排，那麼D回復A說活動取消吧。
階段2：此時A收到了所有活動參與者的郵件，並且A發現D下周三不能去爬山。那麼A將發郵件通知B、C和D，下周三爬長城活動取消。此時B、C回復A「太可惜了」，D回復A「不好意思」。至此該事務終止。
兩階段提交演算法在分布式系統結合，可實現單用戶對文件（對象）多個副本的修改，多副本數據的同步。其結合的原理如下：
1、客戶端（協調者）向所有的數據副本的存儲主機（參與者）發送：修改具體的文件名、偏移量、數據和長度信息，請求修改數據，該消息是1階段的請求消息。
2、存儲主機接收到請求後，備份修改前的數據以備回滾，修改文件數據後，向客戶端回應修改成功的消息。 如果存儲主機由於某些原因（磁碟損壞、空間不足等）不能修改數據，回應修改失敗的消息。
3、客戶端接收發送出去的每一個消息回應，如果存儲主機全部回應都修改成功，向每存儲主機發送確認修改的提交消息；如果存在存儲主機回應修改失敗，或者超時未回應，客戶端向所有存儲主機發送取消修改的提交消息。該消息是2階段的提交消息。
4、存儲主機接收到客戶端的提交消息，如果是確認修改，則直接回應該提交OK消息；如果是取消修改，則將修改數據還原為修改前，然後回應取消修改OK的消息。
5、 客戶端接收全部存儲主機的回應，整個操作成功。
在該過程中可能存在通信失敗，例如網路中斷、主機宕機等諸多的原因，對於未在演算法中定義的其它異常，都認為是提交失敗，都需要回滾，這是該演算法基於確定的通信回復實現的，在參與者的確定回復（無論是回復失敗還是回復成功）之上執行邏輯處理，符合確定性的條件當然能夠獲得確定性的結果哲學原理。

分布式鎖服務

分布式鎖是對數據被外界修改持保守態度，在整個數據處理過程中將數據處於鎖定狀態，在用戶修改數據的同時，其它用戶不允許修改。
採用分布式鎖服務實現數據一致性，是在操作目標之前先獲取操作許可，然後再執行操作，如果其他用戶同時嘗試操作該目標將被阻止，直到前一個用戶釋放許可後，其他用戶才能夠操作目標。分析這個過程，如果只有一個用戶操作目標，沒有多個用戶並發沖突，也申請了操作許可，造成了由於申請操作許可所帶來的資源使用消耗，浪費網路通信和增加了延時。
採用分布式鎖實現多副本內容修改的一致性問題， 選擇控制內容顆粒度實現申請鎖服務。例如我們要保證一個文件的多個副本修改一致， 可以對整個文件修改設置一把鎖，修改時申請鎖，修改這個文件的多個副本，確保多個副本修改的一致，修改完成後釋放鎖；也可以對文件分段，或者是文件中的單個位元組設置鎖， 實現更細顆粒度的鎖操作，減少沖突。
常用的鎖實現演算法有Lamport bakery algorithm （俗稱麵包店演算法）， 還有Paxos演算法。下面對其原理做簡單概述。

Lamport麵包店演算法

是解決多個線程並發訪問一個共享的單用戶資源的互斥問題的演算法。 由Leslie Lamport（英語：Leslie Lamport）發明。
Lamport把這個並發控制演算法可以非常直觀地類比為顧客去麵包店采購。麵包店只能接待一位顧客的采購。已知有n位顧客要進入麵包店采購，安排他們按照次序在前台登記一個簽到號碼。該簽到號碼逐次加1。根據簽到號碼的由小到大的順序依次入店購貨。完成購買的顧客在前台把其簽到號碼歸0. 如果完成購買的顧客要再次進店購買，就必須重新排隊。
這個類比中的顧客就相當於線程，而入店購貨就是進入臨界區獨占訪問該共享資源。由於計算機實現的特點，存在兩個線程獲得相同的簽到號碼的情況，這是因為兩個線程幾乎同時申請排隊的簽到號碼，讀取已經發出去的簽到號碼情況，這兩個線程讀到的數據是完全一樣的，然後各自在讀到的數據上找到最大值，再加1作為自己的排隊簽到號碼。為此，該演算法規定如果兩個線程的排隊簽到號碼相等，則線程id號較小的具有優先權。
把該演算法原理與分布式系統相結合，即可實現分步鎖。

Paxos演算法

該演算法比較熱門，參見WIKI，http://zh.wikipedia.org/wiki/Paxos%E7%AE%97%E6%B3%95
Paxos演算法解決的問題是一個分布式系統如何就某個值(決議)達成一致。一個典型的場景是，在一個分布式資料庫系統中，如果各節點的初始狀態一致，每個節點都執行相同的操作序列，那麼他們最後能得到一個一致的狀態。為保證每個節點執行相同的命令序列，需要在每一條指令上執行一個「一致性演算法」以保證每個節點看到的指令一致。一個通用的一致性演算法可以應用在許多場景中，是分布式計算中的重要問題。節點通信存在兩種模型：共享內存(Shared memory)和消息傳遞(Messages passing)。Paxos演算法就是一種基於消息傳遞模型的一致性演算法。BigTable使用一個分布式數據鎖服務Chubby，而Chubby使用Paxos演算法來保證備份的一致性。

採用樂觀鎖原理實現的同步

我們舉個例子說明該演算法的實現原理。如一個金融系統，當某個操作員讀取用戶的數據，並在讀出的用戶數據的基礎上進行修改時（如更改用戶帳戶余額），如果採用前面的分布式鎖服務機制，也就意味著整個操作過程中（從操作員讀出數據、開始修改直至提交修改結果的全過程，甚至還包括操作員中途去煮咖啡的時間），資料庫記錄始終處於加鎖狀態，可以想見，如果面對幾百上千個並發，這樣的情況將導致怎樣的後果。
樂觀鎖機制在一定程度上解決了這個問題。樂觀鎖，大多是基於數據版本（ Version）記錄機制實現。何謂數據版本？即為數據增加一個版本標識，在基於資料庫表的版本解決方案中，一般是通過為資料庫表增加一個 「version」 欄位來實現。讀取出數據時，將此版本號一同讀出，之後更新時，對此版本號加一。此時，將提交數據的版本數據與資料庫表對應記錄的當前版本信息進行比對，如果提交的數據版本號大於資料庫表當前版本號，則予以更新，否則認為是過期數據。
對於上面修改用戶帳戶信息的例子而言，假設資料庫中帳戶信息表中有一個 version 欄位，當前值為 1 ；而當前帳戶余額欄位（ balance ）為 $100 。
操作員 A 此時將其讀出（version=1 ），並從其帳戶余額中扣除 $50（$100-$50 ）。
在操作員 A 操作的過程中，操作員B也讀入此用戶信息（ version=1 ），並從其帳戶余額中扣除 $20 （ $100-$20 ）。
操作員 A 完成了修改工作，將數據版本號加一（ version=2 ），連同帳戶扣除後余額（ balance=$50 ），提交至資料庫更新，此時由於提交數據版本大於資料庫記錄當前版本，數據被更新，資料庫記錄 version 更新為 2 。
操作員 B 完成了操作，也將版本號加一（ version=2 ）試圖向資料庫提交數據（ balance=$80 ），但此時比對資料庫記錄版本時發現，操作員 B 提交的數據版本號為 2 ，資料庫記錄當前版本也為 2 ，不滿足 「 提交版本必須大於記錄當前版本才能執行更新 「 的樂觀鎖策略，因此，操作員 B 的提交被駁回。這樣，就避免了操作員 B 用基於 version=1 的舊數據修改的結果覆蓋操作員A 的操作結果的可能。
樂觀鎖機制與分布式系統相結合上， 我整理了偽代碼如下：
obj 操作的目標
vlaue 修改的值
atom_update_ver 每個目標上的版本，每次修改該值遞增
set( obj, value)
{
//從每個節點上取出修改前的對象版本
get original_ver = obj.atom_update_ver from each node;
//將值賦到每個節點的obj目標
set obj = value from each node;
//條件修改每個節點的obj版本，目標版本加一
//比較和修改操作是原子操作
result = (set obj.atom_update_ver = original_ver + 1
where original_ver + 1 > obj.atom_update_ver
for each node);
if(result == ok)
return set_ok;
else
return set(obj, value);//不成功遞歸修改

該演算法未考慮節點下線、失效等問題，在後續我將分析採用樂觀鎖原理實現一致性演算法，解決問題2、節點失效、通信失敗等問題。

『拾』 Paxos怎麼讀，麻煩給出英文音標

Paxos讀作[ˈpæksoʊs]。

Paxos

發音：[ˈpæksoʊs]

含義：Paxos（帕克索斯）演算法

用法：在句子中充當主語或賓語。

例句：

The High Replication Datastore increases the number of data centers that maintain replicas of your data by using the Paxos algorithm to synchronize that data across datacenters in real time.

High Replication Datastore使用Paxos演算法來實時同步跨越多個數據中心的數據，進而增加了用於維護數據復制的數據中心數量。

(10)paxos演算法擴展閱讀：

Paxos 演算法的背景：

Paxos 演算法解決的問題是一個分布式系統如何就某個值（決議）達成一致。一個典型的場景是，在一個分布式資料庫系統中，如果各節點的初始狀態一致，每個節點執行相同的操作序列，那麼他們最後能得到一個一致的狀態。

為保證每個節點執行相同的命令序列，需要在每一條指令上執行一個「一致性演算法」以保證每個節點看到的指令一致。一個通用的一致性演算法可以應用在許多場景中，是分布式計算中的重要問題。因此從20世紀80年代起對於一致性演算法的研究就沒有停止過。

節點通信存在兩種模型：共享內存（Shared memory）和消息傳遞（Messages passing）。Paxos 演算法就是一種基於消息傳遞模型的一致性演算法。