文章目錄
- 前言
- CAP理論
- C consistency 一緻性
- A availability 可用性
- P partition tolerance 分區容錯性
- 一緻性模型
- 弱一緻性
- 強一緻性
- 強一緻性算法
- 需要明确的問題
- 強一緻算法： 主從同步
- 強一緻性算法：多數派
- 強一緻算法：Paxos
- Basic Paxos
- Multi Paxos
- 第一個版本：使用Proposer表示唯一的一個Leader
- 第二個版本：将算法角色進一步簡化
- 強一緻算法： Raft(基于log replicated的共識算法)
- 強一緻算法：ZAB
- 總結
前言
分布式系統是目前網際網路領域的一個重要且大勢所趨的一種解決計算，存儲，網絡相關問題的方向，利用數量龐大的伺服器節點作為底層，在其之上搭建一個可以跨省甚至跨國的龐大系統。
它能夠保證使用者資料的一緻性，對使用者提供服務的高可用性，以及跨地域的分區容錯性，而分布式一緻性算法就是為了保證分布式系統能夠滿足其特性。
分布式一緻性算法，我将其劃分到了分布式存儲技能樹中的分布式理論中：
本文的總結，将按照以下導圖進行知識點的總結和梳理
CAP理論
提到分布式系統，那麼CAP理論便無法繞過了。自從2000年，Eric Brewer教授提出了分布式系統設計一定會遵循：一緻性，可用性，分區容錯性的三個原則之後，網際網路界的分布式系統便都将其作為自己的衡量标準。後續的分布式系統設計也都按照CAP理論進行設計，但是任何一個系統都隻能在三個原則中滿足兩個，無法三個都滿足，即使像最近的亞馬遜S3和google spanner等全球分布式系統也隻能滿足CP兩種，對于A則也隻能提供多個9的可用性。
後續該理論上升為定理之後也有相關的證明論文，本節隻是将其作為一個基本理論掃盲的介紹。
C consistency 一緻性
在分布式系統中有多個節點，整個系統對外提供的服務應該是一緻的。即使用者在不同的系統節點通路資料的時候應該是同樣的結果，不能出現1号節點是結果1， 2号節點是結果2這種不一緻的情況。
A availability 可用性
分布式系統為使用者提供服務，需要保證能夠在一些節點異常的情況下仍然支援為使用者提供服務。
P partition tolerance 分區容錯性
分布式系統的部署可能跨省，甚至跨國。不同省份或者國家之間的伺服器節點是通過網絡進行連接配接，此時如果兩個地域之間的網絡連接配接斷開，整個分布式系統的展現就是分區容錯性了。
在這種系統出現網絡分區的情況下系統的服務就需要在一緻性 和 可用性之間進行取舍。
如果為了在出現網絡分區之後提供仍然能夠提供可用性，那麼一緻性必然無法滿足。因為可用性的要求是系統仍然能夠提供服務，但是這個時候分布式系統在兩個地域之間無法通信，那麼America的請求無法同步到China的服務節點上，整個系統的一緻性顯然不能滿足。
同理 為了保證一緻性，那麼可用性也必然不能滿足，因為一緻性的要求是請求A寫入America之後從China中讀，一定要能夠讀到這個請求（強一緻性）或者 經過一段時間之後也能夠讀到（弱一緻性）。但是兩地域已經出現了網絡分區，那麼請求會阻塞進而降低可用性。
是以CAP理論一定是無法全部滿足三者，隻能滿足其中的兩者。
一緻性模型
弱一緻性
弱一緻性展現的是最終一緻性，即如上CAP理論中 ，兩個地域的請求分别通過兩地的節點寫入，可以不用立即進行同步，而是經過一段時間之後兩地的使用者資料變為一緻。這種一緻性成為弱一緻性，即最終一緻性。
也就是使用者一地寫入之後從另外一個節點讀取，無法立即讀到剛才寫入的資料。
比如DNS域名系統，Cassandra的 Gossip協定等都是最終一緻性的展現。
全球目前的域名系統可以看作一個域名樹，由一個根域名節點
.cn
下轄多個
.edu
,
.org
,
.com
等子域名節點，而這一些子域名之下🈶️更多的子域名（以企業為例www.kuaishou.com，之下有多個資料中心，不同的資料中心又數百上千的存儲節點），當我們向某一個節點更新域名資訊的時候，在其他節點立即通路該記錄則不一定立即通路到最終的更新，而是經過一段時間之後我們能夠看到更新。
強一緻性
強一緻性是非常有必要的，比如業界的銀行系統，支付系統等對一緻性要求非常高。
當下比較流行的強一緻性算法 像 Paxos,以及基于paxos衍生的raft,ZAB都能提供強一緻性的能力。
強一緻性描述的是一個請求在一個節點寫入之後在其他節點讀取，則該資料的更新能夠被讀到。
接下來主要描述的是一些強一緻性算法的原理。
強一緻性算法
需要明确的問題
- 資料不能存放在單個節點上，當然這個是分布式系統的基礎形态，不滿足這個分布式系統也不能稱為分布式系統了
-
分布式系統對分區容錯的方案是 state machine replication （複制狀态機），而強一緻算法也被稱為共識算法(consensus)
state狀态機 簡單來說就是一個函數，根據輸入的不同值來執行對應的請求處理邏輯。
為了保證系統的最終一緻性，不僅需要系統内部達成共識，也需要一些client的行為。
強一緻算法： 主從同步
主從同步複制：
-
master
-
master
-
master
這是一個強一緻性算法的基礎，但是這樣的模型會出現如下問題：
比如一個slave節點異常當機，那麼master遲遲等不到該節點的傳回，此時client請求便會阻塞。這樣的模型就是強一緻模型，但是系統的可用性就會非常差，一個節點挂掉會導緻整個系統不可用。
強一緻性算法：多數派
為了避免主從同步那樣一個節點異常，整個叢集不可用的情況，推出了多數派。即每次寫入隻需要保證寫入節點數大于N/2 個，讀節點數保證大于N/2個節點，此時即可認為能夠向用戶端傳回了。
這樣既能夠保證一緻性，又提高了可用性。但是這個情況也隻是針對單個請求寫入的情況下，而我們實際生産環境中會存在大量的并發場景。
比如：
并發這個分布式系統的不同節點執行不同的操作，在滿足多數派的情況下可能會出現順序的問題，不同的節點因為請求同步的時間問題可能出現請求的順序不一緻。
強一緻算法：Paxos
基礎的Paxos算法包括如下三種：
- Basic Paxos
- Multi Paxos
- Fast Paxos
paxos算法是Lasile Lamport的發明，這個算法已經有很多論文對其基本原理進行描述，因為本身角色很多又要在不同的異常場景下描述清楚，很難真正讓讀者對該算法融會貫通的。
Lamport
為了更加形象的描述，提出了虛拟出來一個叫做Paxos的希臘城邦，這個城邦的管理者為了友善對群眾的管理，提出了一系列法案用來對群眾進行限制，當群眾有民事請求時，會送出民事訴訟給國會，有一個組織者将該訴訟整理成法案交給一個個議員進行處理，議員之間又分為投票者和接受者用來實際進行該法案最終是否要處理的決定，最終将結果回報給組織者，由組織者将最終的結果再返還給群眾。
具體的角色如下：
-
Client
-
Proposer
Client
-
Accpetor
-
Learner
Basic Paxos
主要分為如下幾個階段(phases):
-
Phase 1a
： Prepare階段
這個階段
Proposer
Proposer
Acceptor
-
Phase 1b
: Promise階段
如果N大于此
Acceptor
-
Phase 2a
: Accept階段
如果
Acceptor
Proposer
-
Phase2b
: Accepted階段
如果此acceptor在此期間沒有收到任何編号大于N的提案，則接受此提案内容，否則忽略。接受之後會向Proposer傳回成功，且将議案的内容交給
Learner
正常的處理流程如下：
用戶端發起request請求到Proposer，然後Proposer發出提案并攜帶提案的編号1，分别發給每一個Acceptor；每一個Acceptor根據天都編号是否滿足大于1，将投票結果通過Propose階段回報給Proposer；Proposer收到Acceptor的結果判斷是否達到了多數派，達到了多數派則向Acceptor發出Accept請求，并攜帶提案的具體内容V；Acceptor收到提案内容後向Proposer回報Accepted表示收到，并将提案内容交給Learner進行備份。
Learner寫入提案内容之後向Client發送完成請求的響應。
當Acceptor出現異常時流程如下：
雖然Accetor3 出現異常，沒有向Proposer回報，但是Proposer此時收到的接受提案的回報有2個Acceptor，仍然滿足多數派的情況，此時仍然能夠将提案内容繼續寫入的，是以後續的Accept的發送隻需要發送給剩下的兩個Acceptor即可。當Proposer出現異常時的情況如下：
Proposer失敗的話表示收到Acceptor的Propose請求之後無法繼續發送Accept請求，這個時候叢集會重新選出另一個新的能夠工作的Proposer，再從prepare階段開始處理，同時Prepare的提案版本号會增加一個，但是提案的内容還是之前的内容。當出現活鎖的情況：
簡化了如下處理流程，當然其中的 Proposers和Acceptors 不隻一個，是由多個組成的。
基本情況就是叢集中有多個Propser，當proposer1發送prepare版本為1并收到propose的時候節點發生了異常，叢集切換到了新的proposer，并重新prepare 版本2，準備好和版本1相同的内容的提案。（因為acceptor處理的過程中發現更高版本的提案，會丢棄目前的版本，轉向更高版本去處理）。
當proposer2等待acceptor的propose傳回時，proposer1有上線了，發現自己prepare(1)提案被打斷，此時又準備了一個更高版本的prepare(3)提案，打斷了proposer2的2版本提案；當proposer2發現自己的2号版本被打斷，又準備了更高的4号版本，進而打斷了propose1的3号提案版本；依此下去，整個叢集将會阻塞在相同的提案的不斷送出之中，這種情況就是叢集出現了活鎖。
當然也有較好的解決措施，比如：proposer1的上線之後 重新送出法案使用随機時間機制，即随機生成一個時間戳，在這段時間内不向Acceptor發送消息；這樣proposer2的提案能夠被處理完成，這個時候proposer1再次送出新的提案。
綜上這一些基本異常情況來看，basic paxos還是能夠保證系統的一緻性和可用性，共識算法還是能夠正常工作。
但是basic還是有一些缺點：
-
難實作
有太多的角色需要實作
-
效率低(2輪 rpc)
每一個請求需要proposer和acceptor 至少互動兩次才能完成請求的處理
- 活鎖
這個時候推出了Multi Paxos，其中的特色就是Leader概念，Leader是由唯一的Proposer表示，所有的請求都需要經過這個Leader進行轉發。
Multi Paxos
第一個版本：使用Proposer表示唯一的一個Leader
Proposer可以直接用來做提案是否被接受的決定，而不用所有的acceptor各自決定是否要接受提案。
正常處理流程如下：
- 處理第一個請求的時候因為需要選擇leader，是以還是會走2輪rpc,從prepare 到最後的Accepted。
- 從第二個請求開始，所有的請求隻需要交給Proposer，Proposer即可完成是否接受請求的決定，一次Accept即可達成将請求寫入Learner的過程。
第二個版本：将算法角色進一步簡化
這個簡化之後便更加接近我們實際的分布式系統的情況
當然這個還是正常請求的處理流程，不過隻會通過一輪Accept通信即可完成請求的處理。
ps：簡化後的叢集第一個請求還是會走2輪rpc，為了從servers中選舉出一個leader，這個過程還是會從prepare開始到Accepted完成。
強一緻算法： Raft(基于log replicated的共識算法)
raft是更為簡化的
multi paxos
（其實也就是上一個圖中的paxos）算法，相比于paxos的複雜實作來說角色更少，問題更加精簡。
rafti整體來說可以拆分成三個子問題來達成共識：
-
Leader Election
-
Log Replication
-
Safety
重新定義了新的角色：
-
Leader
-
Follower
-
Cadidate
除了以上的精簡之外，raft還提供了完善的社群 甚至 完整共識過程的可視化展示，這裡可以通過原理動畫展示 : http://thesecretlivesofdata.com/raft/ 浏覽。
主體過程如下：
- 三個基本的節點角色介紹一下
-
Leader Election的選舉過程
初始所有節點都是follower狀态，當開始選舉的時候将待選舉節
node a
點置為candidate狀态
canditdate會向其他的follower節點發送請求進行leader投票，其他節點投票通過，則将candidate節點的狀态置為leader狀态。
接下來通過兩種心跳時間來詳細看一下選舉過程的實作
在leader election選舉的過程中會有兩種timeout的設定來控制整個的選舉過程：
-
Election timeout
candidate
。 raft給的設定值一般在150ms-300ms之間的随機值。
變成candidate之後，目前節點會立即發送leader的投票請求，其他的follower節點會重置選舉的逾時時間。
-
heartbeat timeout
新選舉出來的leader每隔一段時間會發送一個請求給follower，這個時間就是心跳時間。
同樣follower在相同的時間間隔内回複leader一個請求，表示自己已經收到。
這樣的心跳間隔将會一直持續，直到一個follower停止接受心跳，變成candidate。
重新選舉的過程就是candidate發送選舉請求，follower接受到之後傳回對應的心跳回應，candidate根據心跳回應的個數判斷是否滿足多數派，進而變成leader。變成leader之後，會持續發送心跳包來保證follower的存活。
-
Log Replication
過程
主要過程如下：
用戶端發送請求到leader，leader接受之後将請求封裝成log entry，并将log副本發送給其他的follower節點。
等待其他的follower節點回複，發現達到了多數派之後leader便将該entry寫入到自己的檔案系統之中；
寫入之後再發送請求，表示follower節點也可以寫入了。
接下來我們詳細看看log Replicated的實作過程，我們的leader被選舉出來之後用于請求的轉發，将接受到的使用者請求封裝成log entry，并将log entry的副本轉發給follower，這個log enry發送到follower之後也會用于重置follower的心跳時間。
- 用戶端會發送一條請求到leader，這個請求會追加到leader的log上，但此時還沒有寫入leader所在節點的檔案系統之上
- 這個條leader的log 會在leader發送下一條心跳包的時候攜帶該請求的資訊 一起發送給follower
- 當entry送出到follower，且收到多數派的回複之後會給client一個回複，表示叢集已經寫入完成。同時将leader的log寫入自己的檔案系統，并且發送command讓從節點也進行寫入。這個過程就是multi paxos中的accepted階段。
關于raft更加詳細嚴謹的細節介紹和性能測試 可以參考論文raft paper
強一緻算法：ZAB
基本和raft相同，隻是在一些名詞的叫法上有一些差別
比如ZAB 将某一個leader的周期稱為epoch,而raft稱為 term。
實作上的話 raft為了保證日志連續性，心跳方向是從leader到follower，ZAB則是相反的。
總結
本篇從理論和實作邏輯上描述了CAP理論、paxos相關的一緻性算法變種以及基于multi paxos實作的簡化版強一緻算法協定raft和ZAB，後續會從源碼層面一一觀察以及自實作基礎raft的通信來加深對分布式系統設計的了解。
可以看到分布式系統的核心算法還是圍繞CAP理論來進行取舍，從系統前期的角色設計，到每個角色承擔的任務，到最後異常情況下的各個角色做出的反應都能看到CAP的影子。這一些設計原則最終還是會回報到使用者體驗之上，雙十一的巨量流量，國外的APP群體和國内實時通信互動，看似簡單的一個使用者功能背後的每一個RPC都是一段跨省，跨國的異地戀，即使異國之路被封鎖，合理的系統設計也能夠讓這段戀情持續。