文章目錄

• 分布式一致性
• • 1. 線性一致性
  • 2. 順序一致性
  • 3. 因果一致性
  • 4. 單調一致性
  • 5. 最終一致性
• 一致性協議
• • 1. Paxos算法
  • 2. Raft算法

---

分布式一致性

在CAP、ACID和BASE中都提到了一致性。但是對于一致性的整個定義還是非常模糊的，所以本文會詳細介紹一致性的模型，以及目前比較流行的一致性協議。

數據一致性并不只有存在與不存在兩種情況，就像可以用0%到100%之間的任意數值來代表可用性的程度一樣，一致性也有一些分類。一致性模型按照強弱可以粗略地分為弱一致性模型、最終一致性模型和強一致性模型。

• 弱一致性模型的特點是向系統更新或者寫入一個數值后，后續的讀操作不一定能夠讀到這個最新的數值。
• 最終一致性模型的特點是向系統更新或者寫入一個數值后，后續一段時間內的讀操作可能讀取不到這個最新的值，但在該時間段過后，一定能夠讀到最新的數值。最終一致性模型又可細分為：因果一致性、單調一致性和最終一致性。
• 強一致性模型的特點是向系統更新或寫入一個數值后，無論何時都能夠讀到這個最新的數值。強一致性模型又可以細分為兩類：線性一致性和順序一致性。

---

下面就分別介紹一下這幾種一致性模型。

1. 線性一致性

線性一致性又稱為原子一致性和強一致性。

Linearizability: A Correctness Condition for Concurrent Objects. Maurice P. Herlihy, Jeannette M. Wing. 1987.

如果需要達到線性一致性，則需要滿足如下條件：

• 1）任何一次讀操作都可以讀到某個數據的最新值。
• 2）系統中所有的節點內執行的時間順序都和系統級別時鐘下看到的時間順序一致。

第一點非常容易理解，第二點則約束了兩個維度下時間的執行順序都必須是一樣的。這兩個維度是指單個進程內的時鐘順序和整個系統的時鐘順序。下面通過一個例子來理解一下。

圖中有三個進程P1、P2、P3，從P1進程來看，只是執行了一次寫操作。從P2和P3進程來看。事件順序都是先執行一次寫操作，然后執行一次讀操作。從整個系統的時鐘順序來看，先執行三次寫操作，然后執行兩次讀操作，所以最近一次的值是3，讀操作讀到的值也就是3。

2. 順序一致性

上面的例子中五個事件在時間上沒有重疊，但是在實際的場景中，不同進程的事件執行的時間點一定會有重疊，如下面的例子：

這三個進程在執行三次寫操作和三次讀操作時的時間點有重疊，從系統級時鐘的維度來看，整個事件的執行順序應該是write1→write2→write3→read2→read3→read2（數字代表進程標識）。如果按照線性一致性的約束，則第一次read2讀到的值應該是a=3，因為第一次read前一次的寫操作時write3。但是圖中的結果卻是a=2，這是因為write3操作雖然實在read2操作之前開始執行的，但是write3操作結束的事件卻是在第一次read2操作開始之后。從進程P2的視角看，事件執行順序應該時write2→read2→write3→write1→read2，P2進程和系統級別時鐘的視角看到的事件執行順序是完全不一樣的。而這種時間點重疊，并且不滿足系統級別時鐘的事件執行順序的一致性成為順序一致性。

順序一致性的約束如下：

• 1）任何一次讀操作都可以讀到某個數據的最新值，這一點和線性一致性是相同的。
• 2）任何進程看到的事件順序是合理的，達成一致即可，并不需要所有進程的時間順序和系統級時鐘下的事件順序一致，它放寬了對一致性的要求，并不像線性一致性一樣嚴格。

3. 因果一致性

線性一致性和順序一致性有一個相同的約束，就是任何一次讀操作都可以讀到某個數據的最新值，這是強一致性的表現。而因果一致性屬于最終一致，它的約束如下：

• 1）對于具有因果關系的讀/寫事件，所有進程看到的事件順序必須一致。
• 2）對于沒有因果關系的讀/寫事件，進程可以以不同的順序看到這些并發的事件。

4. 單調一致性

單調一致性可以分為單調讀一致性和單調寫一致性。

單調讀一致性指的是任何時刻一旦讀到某個數據項在某次更新后的值，就不會再讀到比這個值更舊的值。

單調寫一致性指的是一個進程對某一個數據項執行的寫操作必須在該進程對數據項執行任何后續寫操作之前完成。

相較于因果一致性，單調一致性更聚焦于單個進程內的讀/寫操作順序。

5. 最終一致性

因果一致性和單調一致性都屬于最終一致性中的一種，只是在最終一致性的基礎上增加了一致性的強度，因果一致性是在最終一致性的基礎上增加了因果關系的約束，單調一致性是在最終一致性的基礎上增加了單進程內的約束。而沒有增加其他約束的最終一致性也就是字面上的最終一致性的意思，只有一個約束，就是向系統寫入更新或者寫入一個數值，后續一段時間內的讀操作可能讀取不到這個最新的值，但是在該時間段過后，一定能夠讀到這個最新的數值。

對比以上幾個一致性模型的約束條件，可以發現它們之間也有一定的強弱之分，由弱到強，分別是最終一致性、單調一致性、因果一致性、順序一致性、線性一致性。

一致性模型是理論總結，一致性協議則是一致性模型的具體表現形式。與之經常混淆的是共識算法。共識和一致性描述的內容并不相同，共識用來描述一組進程間的協作過程，并且確定下一個操作，而一致性描述的是進程間某一時刻的狀態。共識和一致性相比，共識的概念更狹隘一些，因為達成共識就可以達到一致性。但是需要達到一致性，并不一定需要達成共識，而一致性有強弱之分，共識算法是一致性協議的一種具體實現手段。

---

一致性協議

1. Paxos算法

Paxos是一種基于消息傳遞且具有高度容錯特性的共識算法。

在分布式系統中，只能減少卻無法避免進程掛掉、進程重啟、通信消息丟失、延遲等情況，Paxos算法實現的就是在發生這些異常時，不會破壞分布式系統決議的一致性。一些進程可以提出各種請求，最終只有一個請求會被選中，只要有一個請求被選中，那么其他進程都能獲得該請求帶來的變化。

在Paxos算法中有三類角色，分別是

• Acceptor（決策者）：用于決策最終選用哪個決議。
• Proposer（提議者）：該角色的職責為向決策者提出提議。
• Learner（最終決策執行者）：該角色的職責是執行最終選定的提議。

從提議的提出到提議的選定，再到提議的執行，可以大致分為兩個階段，第一個階段就是決策者選出一個最終的提議（其實是Proposer與Acceptor之間的交互），第二階段就是最終決策執行者如何獲取并執行該提議。

由于Paxos算法是一套偏向理論的算法，難以理解且實現，所以本文就不展開介紹細節了。

2. Raft算法

Raft是一種用來管理復制狀態機的算法，復制狀態機通常使用復制日志實現，Raft也不例外。每個服務器存儲一個包含一系列命令的日志，其狀態機按順序執行日志中的命令。每個日志中的命令都相同且順序也一樣，因此只要處理相同的命令序列，就能得到相同的狀態和相同的輸出序列。這也是Raft實現一致性的核心思想。

Raft算法有三種角色：

• Leader（領袖）：該角色的職責是接受和處理一切請求，并同步數據給Follower。
• Follower（群眾）：該角色的職責是轉發請求給Leader，接受Leader的同步數據，以及參與投票。
• Candidate（候選人）：該角色的職責是競選Leader。

這三種角色分別代表服務節點的三種狀態，這三種狀態之間可以互相轉化。

對于raft角色的轉化，在官網有一個動畫，可以自己設置各節點的狀態：https://raft.github.io/

從圖中可以看出，集群最初的狀態——所有服務器都是Follower，當這些服務啟動完成后，由于起初沒有Leader，所以Follower一定不會收到Leader的心跳信息。經過一段時間后，發生選舉，此時Follower先增加自己的當前任期號并且轉換到Candidate身份，然后投票給自己并且并行地向集群中的其他服務器節點發送競選請求。

當滿足以下三個條件中的一個時，Candidate身份會發生轉變：

• 集群內超過半數的服務節點同意該 Candidate 成為 Leader，也就是超過半數的節點響應了競選請求，此時 Candidate 會變成 Leader。（這是對圖中“receives votes from majority of servers”的解釋）
• 集群內其他的某個服務器節點已經成為 Leader，此時 Candidate 會變回 Follower。 因為當 Leader 產生后，它會向其他的服務器節點發送心跳消息來確定自己的地位并阻止新的選舉。（這是對圖中“discovers current leader or new term”的解釋）
• 如果有多個 Follower 同時成為 Candidate，那么選票可能會被瓜分，以至于沒有Candidate 贏得過半的投票，也就是選舉超時后還是沒有選出 Leader，會通過增加當前任期號來開始一輪新的選舉，但是這種情況有可能無限重復（這是對圖中“times out, new election”的解釋）。為了防止這種情況發生，Raft 算法使用超機選舉超時時間的方法來確保很少發生選票瓜分的情況。也就是每個 Candidate 在開始一次選舉的時候重置一個隨機的選舉超時時間，然后一直等待直到選舉超時。該 Candidate 會增加當前的任期號，重新發起競選請求，此時其他 Candidate 可能還在等待中，那么其他服務節點認為該超時的 Candidate 的任期號最大，所以它會被選為 Leader。

還有一種從Leader直接變成Follower的情況，這種情況多數出現在Leader發生了網絡分區的時候。當Leader發生網絡分區后恢復時，新的Leader已經產生，它會接受新Leader的心跳請求，發現新的Leader的任期號比自己的大，它會自動變成Follower。 而舊的Leader如果發送心跳請求給其他服務器節點時，Candidate和Follower都會對比任期號，如果任期號小于自己的任期號，則直接拒絕此次心跳請求。

總結

以上是生活随笔為你收集整理的【RPC】分布式一致性与一致性协议的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。