分布式架構(gòu)系統(tǒng)回顧

分布式系統(tǒng)概念

分布式系統(tǒng)是一個硬件或軟件組件分布在不同的網(wǎng)絡(luò)計算機(jī)上，彼此之間僅僅通過消息傳遞進(jìn)行通信和協(xié)調(diào)的系統(tǒng)。

簡單點說，所謂分布式系統(tǒng)，就是一個業(yè)務(wù)拆分成多個子業(yè)務(wù)，分布在不同的服務(wù)器節(jié)點，共同構(gòu)成的系統(tǒng)稱為分布式系統(tǒng)，同一個分布式系統(tǒng)中的服務(wù)器節(jié)點在空間部署上是可以隨意分布的，這些服務(wù)器可能放在不同的機(jī)柜中，也可能在不同的機(jī)房中，甚至分布在不同的城市。

分布式與集群的區(qū)別

• 集群：多個人在一起做同樣的事
• 分布式 ：多個人在一起做不同的事
  
  分布式系統(tǒng)的特點：
  • 分布性
  • 對等性
  • 并發(fā)性
  • 缺乏全局時鐘
  • 故障總是會發(fā)生

分布式架構(gòu)的演變

• 階段一 單應(yīng)用架構(gòu)
  

• 階段二 應(yīng)用服務(wù)器與數(shù)據(jù)庫服務(wù)器分離
  

• 階段三 應(yīng)用服務(wù)器集群
  

• 階段四 應(yīng)用服務(wù)器負(fù)載客戶
  

• 階段五 數(shù)據(jù)庫讀寫分離
  

• 階段六 添加搜索引擎環(huán)節(jié)讀庫壓力
  

• 階段七 添加緩存機(jī)制緩解數(shù)據(jù)庫壓力
  

• 階段八 數(shù)據(jù)庫水平/垂直拆分
  

• 階段九 應(yīng)用拆分
  

• 階段十 服務(wù)化
  

分布式系統(tǒng)面臨的問題

• 通信異常
  網(wǎng)絡(luò)本身的不可靠性，因此每次網(wǎng)絡(luò)通信都會伴隨著網(wǎng)絡(luò)不可用的風(fēng)險（光纖、路由、DNS等硬件設(shè)備或系統(tǒng)的不可用），都會導(dǎo)致最終分布式系統(tǒng)無法順利進(jìn)行一次網(wǎng)絡(luò)通信，另外，即使分布式系統(tǒng)各節(jié)點之間的網(wǎng)絡(luò)通信能夠正常執(zhí)行，其延時也會大于單機(jī)操作，存在巨大的延時差別，也會影響消息的收發(fā)過程，因此消息丟失和消息延遲變的非常普遍。
• 網(wǎng)絡(luò)分區(qū)
  網(wǎng)絡(luò)之間出現(xiàn)了網(wǎng)絡(luò)不連通，但各個子網(wǎng)絡(luò)的內(nèi)部網(wǎng)絡(luò)是正常的，從而導(dǎo)致整個系統(tǒng)的網(wǎng)絡(luò)環(huán)境被切分成了若干個孤立的區(qū)域，分布式系統(tǒng)就會出現(xiàn)局部小集群，在極端情況下，這些小集群會獨立完成原本需要整個分布式系統(tǒng)才能完成的功能，包括數(shù)據(jù)的事務(wù)處理，這就對分布式一致性提出非常大的挑戰(zhàn)。
• 節(jié)點故障
  節(jié)點故障是分布式系統(tǒng)下另一個比較常見的問題，指的是組成分布式系統(tǒng)的服務(wù)器節(jié)點出現(xiàn)的宕機(jī)或"僵死"現(xiàn)象，根據(jù)經(jīng)驗來說，每個節(jié)點都有可能出現(xiàn)故障，并且經(jīng)常發(fā)生。
• 三態(tài)
  分布式系統(tǒng)每一次請求與響應(yīng)存在特有的“三態(tài)”概念，即成功、失敗和超時。
  分布式系統(tǒng)中，由于網(wǎng)絡(luò)是不可靠的，雖然絕大部分情況下，網(wǎng)絡(luò)通信能夠接收到成功或失敗的響應(yīng)，但當(dāng)網(wǎng)絡(luò)出現(xiàn)異常的情況下，就會出現(xiàn)超時現(xiàn)象，通常有以下兩種情況：
  • 由于網(wǎng)絡(luò)原因，該請求并沒有被成功的發(fā)送到接收方，而是在發(fā)送過程就發(fā)生了丟失現(xiàn)象。
  • 該請求成功的被接收方接收后，并進(jìn)行了處理，但在響應(yīng)反饋給發(fā)送方過程中，發(fā)生了消息丟失現(xiàn)象。

分布式理論：一致性

什么是分布式一致性

分布式數(shù)據(jù)一致性，指的是數(shù)據(jù)在多份副本中存儲時，各副本中的數(shù)據(jù)是一致的。

副本一致性

分布式系統(tǒng)當(dāng)中，數(shù)據(jù)往往會有多個副本。如果是一臺數(shù)據(jù)庫處理所有的數(shù)據(jù)請求，那么通過ACID四原則，基本可以保證數(shù)據(jù)的一致性。而多個副本就需要保證數(shù)據(jù)會有多份拷貝。這就帶來了同步的問題，因為我們幾乎沒有辦法保證可以同時更新所有機(jī)器當(dāng)中的包括備份所有數(shù)據(jù)。 網(wǎng)絡(luò)延遲，即使我在同一時間給所有機(jī)器發(fā)送了更新數(shù)據(jù)的請求，也不能保證這些請求被響應(yīng)的時間保持一致存在時間差，就會存在某些機(jī)器之間的數(shù)據(jù)不一致的情況。

總得來說，我們無法找到一種能夠滿足分布式系統(tǒng)所有系統(tǒng)屬性的分布式一致性解決方案。因此，如何既保證數(shù)據(jù)的一致性，同時又不影響系統(tǒng)運(yùn)行的性能，是每一個分布式系統(tǒng)都需要重點考慮和權(quán)衡的。于是，一致性級別由此誕生：

一致性分類

• 強(qiáng)一致性
  這種一致性級別是最符合用戶直覺的，它要求系統(tǒng)寫入什么，讀出來的也會是什么，用戶體驗好，但實現(xiàn)起來往往對系統(tǒng)的性能影響大。但是強(qiáng)一致性很難實現(xiàn)。

• 弱一致性
  這種一致性級別約束了系統(tǒng)在寫入成功后，不承諾立即可以讀到寫入的值，也不承諾多久之后數(shù)據(jù)能夠達(dá)到一致，但會盡可能地保證到某個時間級別（比如秒級別）后，數(shù)據(jù)能夠達(dá)到一致狀態(tài)。

• 讀寫一致性
  用戶讀取自己寫入結(jié)果的一致性，保證用戶永遠(yuǎn)能夠第一時間看到自己更新的內(nèi)容。

  比如我們發(fā)一條朋友圈，朋友圈的內(nèi)容是不是第一時間被朋友看見不重要，但是一定要顯示在自己的列表上. 解決方案: 方案1：一種方案是對于一些特定的內(nèi)容我們每次都去主庫讀取。 （問題主庫壓力大） 方案2：我們設(shè)置一個更新時間窗口，在剛剛更新的一段時間內(nèi)，我們默認(rèn)都從主庫讀取，過了這個窗口之后，我們會挑 選最近有過更新的從庫進(jìn)行讀取 方案3：我們直接記錄用戶更新的時間戳，在請求的時候把這個時間戳帶上，凡是最后更新時間小于這個時間戳的從庫都 不予以響應(yīng)。

• 單調(diào)讀一致性
  本次讀到的數(shù)據(jù)不能比上次讀到的舊

  由于主從節(jié)點更新數(shù)據(jù)的時間不一致，導(dǎo)致用戶在不停地刷新的時候，有時候能刷出來，再次刷新之后會發(fā)現(xiàn)數(shù)據(jù)不見 了，再刷新又可能再刷出來，就好像遇見靈異事件一樣 解決方案:就是根據(jù)用戶ID計算一個hash值，再通過hash值映射到機(jī)器。同一個用戶不管怎么刷新，都只會被映射到同 一臺機(jī)器上。這樣就保證了不會讀到其他從庫的內(nèi)容，帶來用戶體驗不好的影響。

• 因果一致性
  指的是：如果節(jié)點 A 在更新完某個數(shù)據(jù)后通知了節(jié)點 B，那么節(jié)點 B 之后對該數(shù)據(jù)的訪問和修改都是基于 A 更新后 的值。于此同時，和節(jié)點 A 無因果關(guān)系的節(jié)點 C 的數(shù)據(jù)訪問則沒有這樣的限制。

• 最終一致性
  最終一致性是所有分布式一致性模型當(dāng)中最弱的。可以認(rèn)為是沒有任何優(yōu)化的“最”弱一致性，它的意思是說，我不考慮 所有的中間狀態(tài)的影響，只保證當(dāng)沒有新的更新之后，經(jīng)過一段時間之后，最終系統(tǒng)內(nèi)所有副本的數(shù)據(jù)是正確的。 它最大程度上保證了系統(tǒng)的并發(fā)能力，也因此，在高并發(fā)的場景下，它也是使用最廣的一致性模型
  

分布式理論：CAP定理

CAP 定理

2000 年7月的時候，加州大學(xué)伯克利分校的Eric Brewer 教授提出了 CAP 猜想，2年后，被 來自于麻省理工的Seth Gilbert 和 Nancy Lynch 從理論上證明了猜想的可能性，從此，CAP 定理正式在學(xué)術(shù)上成為了分布式計算領(lǐng)域的公認(rèn)定理。并深深的影響了分布式計算的發(fā)展。

CAP 理論含義是，一個分布式系統(tǒng)不可能同時滿足一致性（C:Consistency)，可用性（A: Availability）和分區(qū)容錯性（P：Partition tolerance） 這三個基本需求，最多只能同時滿足其中的2個。

選項描述

C 一致性	分布式系統(tǒng)當(dāng)中的一致性指的是所有節(jié)點的數(shù)據(jù)一致，或者說是所有副本的數(shù)據(jù)一致
A 可用性	Reads and writes always succeed. 也就是說系統(tǒng)一直可用，而且服務(wù)一直保持正常
P 分區(qū)容錯性	系統(tǒng)在遇到一些節(jié)點或者網(wǎng)絡(luò)分區(qū)故障的時候，仍然能夠提供滿足一致性和可用性的服務(wù)

• C - Consistency
  一致性是值寫操作后讀操作可以讀到最新的數(shù)據(jù)狀態(tài),當(dāng)數(shù)據(jù)分布在多個節(jié)點上時,從任意節(jié)點讀取到的數(shù)據(jù)都是最新的.

  • 商品信息讀寫要滿足一致性需要實現(xiàn)如下目標(biāo):

    • 1.商品服務(wù)寫入主數(shù)據(jù)庫成功, 則想從數(shù)據(jù)庫查詢數(shù)據(jù)也成功
    • 2.商品服務(wù)寫入主數(shù)據(jù)庫失敗,則向從數(shù)據(jù)庫查詢也失敗

  • 如何實現(xiàn)一致性?

    • 1.寫入主數(shù)據(jù)庫后要數(shù)據(jù)同步到從數(shù)據(jù)庫
    • 2.寫入主數(shù)據(jù)庫后,在向從數(shù)據(jù)庫同步期間要將從數(shù)據(jù)庫鎖定, 等待同步完成后在釋放鎖,以免在寫新數(shù)據(jù)后,向從數(shù)據(jù)庫查詢到舊的數(shù)據(jù).

  • 分布式一致性的特點:

    • 1.由于存在數(shù)據(jù)庫同步過程,寫操作的響應(yīng)會有一定的延遲
    • 2.為了保定數(shù)據(jù)的一致性,對資源暫時鎖定,待數(shù)據(jù)同步完成后釋放鎖定資源
    • 3.如果請求數(shù)據(jù)同步失敗的節(jié)點則會返回錯誤信息, 一定不會返回舊數(shù)據(jù).

• A - Availability
  可用性是指任何操作都可以得到響應(yīng)的結(jié)果,且不會出現(xiàn)響應(yīng)超時或響應(yīng)錯誤。

  • 商品信息讀寫要滿足可用性需要實現(xiàn)如下目標(biāo):
    • 1.從數(shù)據(jù)庫接收到數(shù)據(jù)庫查詢的請求則立即能夠響應(yīng)數(shù)據(jù)查詢結(jié)果
    • 2.從數(shù)據(jù)庫不允許出現(xiàn)響應(yīng)超時或錯誤
  • 如何實現(xiàn)可用性?
  • 1.寫入主數(shù)據(jù)庫后要將數(shù)據(jù)同步到從數(shù)據(jù)
  • 2.由于要保證數(shù)據(jù)庫的可用性,不可以將數(shù)據(jù)庫中資源鎖定
  • 3.即使數(shù)據(jù)還沒有同步過來,從數(shù)據(jù)庫也要返回查詢數(shù)據(jù), 哪怕是舊數(shù)據(jù),但不能返回錯誤和超時

• P - Partition tolerance
  分布式系統(tǒng)的各個節(jié)點部署在不同的子網(wǎng)中, 不可避免的會出現(xiàn)由于網(wǎng)絡(luò)問題導(dǎo)致節(jié)點之間通信失敗,此時仍可以對外提供服務(wù), 這個就是分區(qū)容錯性 (分區(qū)容忍性).

  • 商品信息讀寫要滿足分區(qū)容錯性需要實現(xiàn)如下目標(biāo):
    • 1.主數(shù)據(jù)庫想從數(shù)據(jù)庫同步數(shù)據(jù)失敗不形象寫操作
    • 2.其中一個節(jié)點掛掉不會影響另一個節(jié)點對外提供服務(wù)
  • 如何實現(xiàn)分區(qū)容錯性?
    • 1.盡量使用異步取代同步操作,舉例 使用異步方式將數(shù)據(jù)從主數(shù)據(jù)庫同步到從數(shù)據(jù)庫, 這樣節(jié)點之間能有效的實現(xiàn)松耦合;
    • 2.添加數(shù)據(jù)庫節(jié)點,其中一個從節(jié)點掛掉,由其他從節(jié)點提供服務(wù)

CAP只能 3 選 2

關(guān)于CAP這三個特性我們就介紹完了，接下來我們試著證明一下為什么CAP不能同時滿足。
假設(shè)有一個系統(tǒng)如下：

有用戶向N1發(fā)送了請求更改了數(shù)據(jù)，將數(shù)據(jù)庫從V0更新成了V1。由于網(wǎng)絡(luò)斷開，所以N2數(shù)據(jù)庫依然是V0，如果這個時候 有一個請求發(fā)給了N2，但是N2并沒有辦法可以直接給出最新的結(jié)果V1，這個時候該怎么辦呢？ 這個時候無法兩種方法，一種是將錯就錯，將錯誤的V0數(shù)據(jù)返回給用戶。 第二種是阻塞等待，等待網(wǎng)絡(luò)通信恢復(fù)，N2中 的數(shù)據(jù)更新之后再返回給用戶。顯然前者犧牲了一致性，后者犧牲了可用性。 這個例子雖然簡單，但是說明的內(nèi)容卻很重要。在分布式系統(tǒng)當(dāng)中，CAP三個特性我們是無法同時滿足的，必然要舍棄一 個。三者舍棄一個，顯然排列組合一共有三種可能。

舍棄A(可用性)，保留CP(一致性和分區(qū)容錯性)
一個系統(tǒng)保證了一致性和分區(qū)容錯性，舍棄可用性。也就是說在極端情況下，允許出現(xiàn)系統(tǒng)無法訪問的情況出現(xiàn)，這個 時候往往會犧牲用戶體驗，讓用戶保持等待，一直到系統(tǒng)數(shù)據(jù)一致了之后，再恢復(fù)服務(wù)。

舍棄C(一致性)，保留AP(可用性和分區(qū)容錯性)
這種是大部分的分布式系統(tǒng)的設(shè)計，保證高可用和分區(qū)容錯，但是會犧牲一致性。

舍棄P(分區(qū)容錯性)，保留CA(一致性和可用性)
如果要舍棄P，那么就是要舍棄分布式系統(tǒng)，CAP也就無從談起了。可以說P是分布式系統(tǒng)的前提，所以這種情況是不存在的。

分布式理論：BASE 理論

什么是BASE理論
BASE：全稱：Basically Available(基本可用)，Soft state（軟狀態(tài)）,和 Eventually consistent（最終一致性） 三個短語的縮寫，來自 ebay 的架構(gòu)師提出。

BASE是對CAP中一致性和可用性權(quán)衡的結(jié)果，BASE理論的核心思想是：即使無法做到強(qiáng)一致性，但每個應(yīng)用都可以根據(jù)自身業(yè)務(wù)特點，采用適當(dāng)?shù)姆绞絹硎瓜到y(tǒng)達(dá)到最終一致性。

• Basically Available(基本可用)
  基本可用是指分布式系統(tǒng)在出現(xiàn)不可預(yù)知故障的時候，允許損失部分可用性——但請注意，這絕不等價于系統(tǒng)不可用。以下就是兩個"基本可用"的例子

  • 響應(yīng)時間上的損失：正常情況下，一個在線搜索引擎需要在0.5秒之內(nèi)返回給用戶相應(yīng)的查詢結(jié)果，但由于出現(xiàn)故障（比如系統(tǒng)部分機(jī)房發(fā)生斷電或斷網(wǎng)故障），查詢結(jié)果的響應(yīng)時間增加到了1~2秒。
  • 功能上的損失：正常情況下，在一個電子商務(wù)網(wǎng)站（比如淘寶）上購物，消費者幾乎能夠順利地完成每一筆訂單。但在一些節(jié)日大促購物高峰的時候（比如雙十一、雙十二），由于消費者的購物行為激增，為了保護(hù)系統(tǒng)的穩(wěn)定性（或者保證一致性），部分消費者可能會被引導(dǎo)到一個降級頁面，如下：
    

• Soft state（軟狀態(tài)）
  什么是軟狀態(tài)呢？相對于一致性，要求多個節(jié)點的數(shù)據(jù)副本都是一致的，這是一種 “硬狀態(tài)”。

  軟狀態(tài)指的是：允許系統(tǒng)中的數(shù)據(jù)存在中間狀態(tài)，并認(rèn)為該狀態(tài)不影響系統(tǒng)的整體可用性，即允許系統(tǒng)在多個不同節(jié)點的數(shù)據(jù)副本之間進(jìn)行數(shù)據(jù)同步的過程中存在延遲。

• Eventually consistent（最終一致性）
  最終一致性強(qiáng)調(diào)的是系統(tǒng)中所有的數(shù)據(jù)副本，在經(jīng)過一段時間的同步后，最終能夠達(dá)到一個一致的狀態(tài)。因此最終一致性的本質(zhì)是需要系統(tǒng)保證最終數(shù)據(jù)能夠達(dá)到一致，而不需要實時保證系統(tǒng)數(shù)據(jù)的強(qiáng)一致性。

分布式事務(wù)

• 事務(wù)的基本特性：
  我們知道事務(wù)有4個非常重要的特性，即我們常說的（ACID）。

  • Atomicity（原子性）:是說事務(wù)是一個不可分割的整體，所有操作要么全做，要么全不做；只要事務(wù)中有一個操作出錯，回滾到事務(wù)開始前的狀態(tài)的話，那么之前已經(jīng)執(zhí)行的所有操作都是無效的，都應(yīng)該回滾到開始前的狀態(tài)。
  • Consistency（一致性）：是說事務(wù)執(zhí)行前后，數(shù)據(jù)從一個狀態(tài)到另一個狀態(tài)必須是一致的，比如A向B轉(zhuǎn)賬（A、 B的總金額就是一個一致性狀態(tài)），不可能出現(xiàn)A扣了錢，B卻沒收到的情況發(fā)生。
  • Isolation（隔離性）：多個并發(fā)事務(wù)之間相互隔離，不能互相干擾。關(guān)于事務(wù)的隔離性，可能不是特別好理解，這里的并發(fā)事務(wù)是指兩個事務(wù)操作了同一份數(shù)據(jù)的情況；而對于并發(fā)事務(wù)操作同一份數(shù)據(jù)的隔離性問題，則是要求不能出現(xiàn)臟讀、幻讀的情況，即事務(wù)A不能讀取事務(wù)B還沒有提交的數(shù)據(jù)，或者在事務(wù)A讀取數(shù)據(jù)進(jìn)行更新操作時，不允許事務(wù)B率先更新掉這條數(shù)據(jù)。而為了解決這個問題，常用的手段就是加鎖了，對于數(shù)據(jù)庫來說就是通過數(shù)據(jù)庫的相關(guān)鎖機(jī)制來保證。
  • Durablity（持久性）：事務(wù)完成后，對數(shù)據(jù)庫的更改是永久保存的。

• 什么是分布式事務(wù)
  其實分布式事務(wù)從實質(zhì)上看與數(shù)據(jù)庫事務(wù)的概念是一致的，既然是事務(wù)也就需要滿足事務(wù)的基本特性（ACID），只是分布式事務(wù)相對于本地事務(wù)而言其表現(xiàn)形式有很大的不同

分布式理論：一致性協(xié)議 2PC

什么是 2PC

2PC （ Two-Phase Commit縮寫）即兩階段提交協(xié)議，是將整個事務(wù)流程分為兩個階段，準(zhǔn)備階段（Preparephase）、提交階段（commit phase），2是指兩個階段，P是指準(zhǔn)備階段，C是指提交階段。
在計算機(jī)中部分關(guān)系數(shù)據(jù)庫如Oracle、MySQL支持兩階段提交協(xié)議。

兩個階段過程：

準(zhǔn)備階段（Prepare phase）：事務(wù)管理器給每個參與者發(fā)送Prepare消息，每個數(shù)據(jù)庫參與者在本地執(zhí)行事務(wù)，并寫本地的Undo/Redo日志，此時事務(wù)沒有提交。 （Undo日志是記錄修改前的數(shù)據(jù)，用于數(shù)據(jù)庫回滾，Redo日志是記錄修改后的數(shù)據(jù)，用于提交事務(wù)后寫入數(shù)據(jù)文件）

提交階段（commit phase）：如果事務(wù)管理器收到了參與者的執(zhí)行失敗或者超時消息時，直接給每個參與者發(fā)送回滾(Rollback)消息；否則，發(fā)送提交(Commit)消息；參與者根據(jù)事務(wù)管理器的指令執(zhí)行提交或者回滾操作，并釋放事務(wù)處理過程中使用的鎖資源。注意:必須在最后階段釋放鎖資源

2PC執(zhí)行流程

協(xié)議說明：
顧名思義，二階段提交就是將事務(wù)的提交過程分成了兩個階段來進(jìn)行處理。流程如下：

• 階段一:
• 事務(wù)詢問 協(xié)調(diào)者向所有的參與者發(fā)送事務(wù)內(nèi)容，詢問是否可以執(zhí)行事務(wù)提交操作，并開始等待各參與者的響應(yīng)。
• 執(zhí)行事務(wù) (寫本地的Undo/Redo日志)
• 各參與者向協(xié)調(diào)者反饋事務(wù)詢問的響應(yīng)
  總結(jié): 各個參與者進(jìn)行投票是否讓事務(wù)進(jìn)行

什么是Ack

ACK 確認(rèn)字符，在數(shù)據(jù)通信中，接收站發(fā)給發(fā)送站的一種傳輸類控制字符。 表示發(fā)來的數(shù)據(jù)已確認(rèn)接收無誤。

• 階段二:
• 發(fā)送提交請求： 協(xié)調(diào)者向所有參與者發(fā)出 commit 請求。
• 事務(wù)提交： 參與者收到 commit 請求后，會正式執(zhí)行事務(wù)提交操作，并在完成提交之后釋放整個事務(wù)執(zhí)行期間占用的事務(wù)資源。
• 反饋事務(wù)提交結(jié)果： 參與者在完成事務(wù)提交之后，向協(xié)調(diào)者發(fā)送 Ack 信息。
• 完成事務(wù)： 協(xié)調(diào)者接收到所有參與者反饋的 Ack 信息后，完成事務(wù)。

中斷事務(wù)步驟如下：
假如任何一個參與者向協(xié)調(diào)者反饋了No響應(yīng)，或者在等待超時之后，協(xié)調(diào)者尚無法接收到所有參與者的反饋響應(yīng)，那么就會中斷事務(wù)

• 階段一:
• 事務(wù)詢問 協(xié)調(diào)者向所有的參與者發(fā)送事務(wù)內(nèi)容，詢問是否可以執(zhí)行事務(wù)提交操作，并開始等待各參與者的響應(yīng)。
• 執(zhí)行事務(wù) (寫本地的Undo/Redo日志)
• 各參與者向協(xié)調(diào)者反饋事務(wù)詢問的響應(yīng)
  總結(jié): 各個參與者進(jìn)行投票是否讓事務(wù)進(jìn)行.
• 階段二
• 發(fā)送回滾請求： 協(xié)調(diào)者向所有參與者發(fā)出 Rollback 請求。
• 事務(wù)回滾： 參與者接收到 Rollback 請求后，會利用其在階段一中記錄的 Undo 信息來執(zhí)行事務(wù)回滾操作，并在完成回滾之后 釋放在整個事務(wù)執(zhí)行期間占用的資源。
• 反饋事務(wù)回滾結(jié)果： 參與者在完成事務(wù)回滾之后，向協(xié)調(diào)者發(fā)送 Ack 信息。
• 中斷事務(wù)： 協(xié)調(diào)者接收到所有參與者反饋的 Ack 信息后，完成事務(wù)中斷。
  從上面的邏輯可以看出，二階段提交就做了2個事情：投票，執(zhí)行。

2PC 優(yōu)點缺點

• 優(yōu)點
  原理簡單，實現(xiàn)方便
• 缺點
  同步阻塞，單點問題，數(shù)據(jù)不一致，過于保守
  • 同步阻塞：
    二階段提交協(xié)議存在最明顯也是最大的一個問題就是同步阻塞，在二階段提交的執(zhí)行過程中，所有參與該事務(wù)操作的邏輯都處于阻塞狀態(tài)，也就是說，各個參與者在等待其他參與者響應(yīng)的過程中，無法進(jìn)行其他操作。這種同步阻塞極大的限制了分布式系統(tǒng)的性能。
  • 單點問題：
    協(xié)調(diào)者在整個二階段提交過程中很重要，如果協(xié)調(diào)者在提交階段出現(xiàn)問題，那么整個流程將無法運(yùn)轉(zhuǎn)，更重要的是：其他參與者將會處于一直鎖定事務(wù)資源的狀態(tài)中，而無法繼續(xù)完成事務(wù)操作。
  • 數(shù)據(jù)不一致：
    假設(shè)當(dāng)協(xié)調(diào)者向所有的參與者發(fā)送 commit 請求之后，發(fā)生了局部網(wǎng)絡(luò)異常或者是協(xié)調(diào)者在尚未發(fā)送完所有commit 請求之前自身發(fā)生了崩潰，導(dǎo)致最終只有部分參與者收到了 commit 請求。這將導(dǎo)致嚴(yán)重的數(shù)據(jù)不一致問題。
  • 過于保守：
    如果在二階段提交的提交詢問階段中，參與者出現(xiàn)故障而導(dǎo)致協(xié)調(diào)者始終無法獲取到所有參與者的響應(yīng)信息的話，這時協(xié)調(diào)者只能依靠其自身的超時機(jī)制來判斷是否需要中斷事務(wù)，顯然，這種策略過于保守。換句話說，二階段提交協(xié)議沒有設(shè)計較為完善的容錯機(jī)制，任意一個節(jié)點失敗都會導(dǎo)致整個事務(wù)的失敗。

分布式理論：一致性協(xié)議 3PC

什么是三階段提交

3PC，全稱 “three phase commit”，是 2PC 的改進(jìn)版，將 2PC 的 “提交事務(wù)請求” 過程一分為二，共形成了由CanCommit、PreCommit和doCommit三個階段組成的事務(wù)處理協(xié)議。

階段一：CanCommit

• ① 事務(wù)詢問
  協(xié)調(diào)者向所有的參與者發(fā)送一個包含事務(wù)內(nèi)容的canCommit請求，詢問是否可以執(zhí)行事務(wù)提交操作，并開始等待各參與者的響應(yīng)。
• ② 各參與者向協(xié)調(diào)者反饋事務(wù)詢問的響應(yīng)
  參與者在接收到來自協(xié)調(diào)者的包含了事務(wù)內(nèi)容的canCommit請求后，正常情況下，如果自身認(rèn)為可以順利執(zhí)行事務(wù)，則反饋Yes響應(yīng)，并進(jìn)入預(yù)備狀態(tài)，否則反饋No響應(yīng)。

階段二：PreCommit

協(xié)調(diào)者在得到所有參與者的響應(yīng)之后，會根據(jù)結(jié)果有2種執(zhí)行操作的情況：執(zhí)行事務(wù)預(yù)提交，或者中斷事務(wù)

假如所有參與反饋的都是Yes，那么就會執(zhí)行事務(wù)預(yù)提交。

執(zhí)行事務(wù)預(yù)提交分為 3 個步驟

• 發(fā)送預(yù)提交請求：
  協(xié)調(diào)者向所有參與者節(jié)點發(fā)出preCommit請求，并進(jìn)入prepared階段。
• 事務(wù)預(yù)提交：
  參與者接收到preCommit請求后，會執(zhí)行事務(wù)操作，并將Undo和Redo信息記錄到事務(wù)日志中。
• 各參與者向協(xié)調(diào)者反饋事務(wù)執(zhí)行的結(jié)果：
  若參與者成功執(zhí)行了事務(wù)操作，那么反饋Ack

若任一參與者反饋了No響應(yīng)，或者在等待超時后，協(xié)調(diào)者尚無法接收到所有參與者反饋，則中斷事務(wù)

中斷事務(wù)也分為2個步驟：

• 發(fā)送中斷請求：
  協(xié)調(diào)者向所有參與者發(fā)出abort請求。
• 中斷事務(wù)：
  無論是收到來自協(xié)調(diào)者的abort請求或者等待協(xié)調(diào)者請求過程中超時，參與者都會中斷事務(wù)

階段三：do Commit

該階段做真正的事務(wù)提交或者完成事務(wù)回滾，所以就會出現(xiàn)兩種情況：

執(zhí)行事務(wù)提交

• 發(fā)送提交請求：
  進(jìn)入這一階段，假設(shè)協(xié)調(diào)者處于正常工作狀態(tài)，并且它接收到了來自所有參與者的Ack響應(yīng)，那么他將從預(yù)提交狀態(tài)轉(zhuǎn)化為提交狀態(tài)，并向所有的參與者發(fā)送doCommit請求。
• 事務(wù)提交：
  參與者接收到doCommit請求后，會正式執(zhí)行事務(wù)提交操作，并在完成提交之后釋放整個事務(wù)執(zhí)行過程中占用的事務(wù)資源。
• 反饋事務(wù)提交結(jié)果：
  參與者在完成事務(wù)提交后，向協(xié)調(diào)者發(fā)送Ack響應(yīng)。
  ④ 完成事務(wù)：
  協(xié)調(diào)者接收到所有參與者反饋的Ack消息后，完成事務(wù)。

中斷事務(wù)

• 發(fā)送中斷請求：協(xié)調(diào)者向所有的參與者節(jié)點發(fā)送abort請求。
• 事務(wù)回滾：參與者收到abort請求后，會根據(jù)記錄的Undo信息來執(zhí)行事務(wù)回滾，并在完成回滾之后釋放整個事務(wù)執(zhí)行期間占用的資源。
• 反饋事務(wù)回滾結(jié)果：參與者在完成事務(wù)回滾后，向協(xié)調(diào)者發(fā)送Ack消息。
• ④ 中斷事務(wù)：協(xié)調(diào)者接收到所有參與者反饋的Ack消息后，中斷事務(wù)。
  注意：一旦進(jìn)入階段三，可能會出現(xiàn) 2 種故障：
• 協(xié)調(diào)者出現(xiàn)問題
• 協(xié)調(diào)者和參與者之間的網(wǎng)絡(luò)故障
  如果出現(xiàn)了任一一種情況，最終都會導(dǎo)致參與者無法收到 doCommit 請求或者 abort 請求，針對這種情況，參與者都會在等待超時之后，繼續(xù)進(jìn)行事務(wù)提交

2PC對比3PC

• 首先對于協(xié)調(diào)者和參與者都設(shè)置了超時機(jī)制（在2PC中，只有協(xié)調(diào)者擁有超時機(jī)制，即如果在一定時間內(nèi)沒有收到參與者的消息則默認(rèn)失敗）,主要是避免了參與者在長時間無法與協(xié)調(diào)者節(jié)點通訊（協(xié)調(diào)者掛掉了）的情況下，無法釋放資源的問題，因為參與者自身擁有超時機(jī)制會在超時后，自動進(jìn)行本地commit從而進(jìn)行釋放資源。而這種機(jī)制也側(cè)面降低了整個事務(wù)的阻塞時間和范圍。
• 通過CanCommit、PreCommit、DoCommit三個階段的設(shè)計，相較于2PC而言，多設(shè)置了一個緩沖階段保證了在最后提交階段之前各參與節(jié)點的狀態(tài)是一致的 。
• PreCommit是一個緩沖，保證了在最后提交階段之前各參與節(jié)點的狀態(tài)是一致的。
  問題：3PC協(xié)議并沒有完全解決數(shù)據(jù)不一致問題。

分布式理論：一致性算法 Paxos

什么是Paxos算法

Paxos算法是Lamport提出的一種基于消息傳遞的分布式一致性算法，使其獲得2013年圖靈獎。

Paxos由Lamport于1998年在《The Part-Time Parliament》論文中首次公開，最初的描述使用希臘的一個小島Paxos作為比喻，描述了Paxos小島中通過決議的流程，并以此命名這個算法，但是這個描述理解起來比較有挑戰(zhàn)性。后來在2001年，Lamport覺得同行不能理解他的幽默感，于是重新發(fā)表了樸實的算法描述版本《Paxos Made Simple》

自Paxos問世以來就持續(xù)壟斷了分布式一致性算法，Paxos這個名詞幾乎等同于分布式一致性。Google的很多大型分布式系統(tǒng)都采用了Paxos算法來解決分布式一致性問題，如Chubby、Megastore以及Spanner等。開源的ZooKeeper，以及MySQL 5.7推出的用來取代傳統(tǒng)的主從復(fù)制的MySQL Group Replication等紛紛采用Paxos算法解決分布式一致性問題。
然而，Paxos的最大特點就是難，不僅難以理解，更難以實現(xiàn)。

Paxos 解決了什么問題

答：解決了分布式系統(tǒng)一致性問題。

分布式系統(tǒng)才用多副本進(jìn)行存儲數(shù)據(jù) , 如果對多個副本執(zhí)行序列不控制, 那多個副本執(zhí)行更新操作,由于網(wǎng)絡(luò)延遲 超時 等故障到值各個副本的數(shù)據(jù)不一致。 我們希望每個副本的執(zhí)行序列是 [ op1 op2 op3 .... opn ] 不變的, 相同的。 Paxos 一次來確定不可變變量 opi的取值 , 每次確定完Opi之后,各個副本執(zhí)行opi操作,一次類推。 結(jié)論： Paxos算法需要解決的問題就是如何在一個可能發(fā)生上述異常的分布式系統(tǒng)中，快速且正確地在集群內(nèi)部對某個 數(shù)據(jù)的值達(dá)成一致.。 注：這里某個數(shù)據(jù)的值并不只是狹義上的某個數(shù)，它可以是一條日志，也可以是一條命令（command）。根據(jù)應(yīng)用場 景不同，某個數(shù)據(jù)的值有不同的含義

我們假設(shè)一種情況，在一個集群環(huán)境中，要求所有機(jī)器上的狀態(tài)是一致的，其中有2臺機(jī)器想修改某個狀態(tài)，機(jī)器A 想把狀態(tài)改為 A，機(jī)器 B 想把狀態(tài)改為 B，那么到底聽誰的呢？
有的同學(xué)會想到，可以像 2PC，3PC 一樣引入一個協(xié)調(diào)者，誰先到，聽誰的

但是如果，協(xié)調(diào)者宕機(jī)了呢？
所以需要對協(xié)調(diào)者也做備份，也要做集群。這時候，問題來了，這么多協(xié)調(diào)者，聽誰的呢？

Paxos 算法就是為了解決這個問題而生的

Paxos相關(guān)概念

首先一個很重要的概念叫提案（Proposal）。最終要達(dá)成一致的value就在提案里。
提案 (Proposal)：Proposal信息包括提案編號 (Proposal ID) 和提議的值 (Value)
在Paxos算法中，有如下角色：

• Client：客戶端
  • 客戶端向分布式系統(tǒng)發(fā)出請求，并等待響應(yīng)。例如，對分布式文件服務(wù)器中文件的寫請求。
• Proposer：提案發(fā)起者
  • 提案者提倡客戶請求，試圖說服Acceptor對此達(dá)成一致，并在發(fā)生沖突時充當(dāng)協(xié)調(diào)者以推動協(xié)議向前發(fā)展
• Acceptor：決策者，可以批準(zhǔn)提案
  • Acceptor可以接受（accept）提案；如果某個提案被選定（chosen），那么該提案里的value就被選定了
• Learners：最終決策的學(xué)習(xí)者
  • 學(xué)習(xí)者充當(dāng)該協(xié)議的復(fù)制因素

問題描述

假設(shè)有一組可以提出提案的進(jìn)程集合，那么對于一個一致性算法需要保證以下幾點：

• 在這些被提出的提案中，只有一個會被選定
• 如果沒有提案被提出，就不應(yīng)該有被選定的提案。
• 當(dāng)一個提案被選定后，那么所有進(jìn)程都應(yīng)該能學(xué)習(xí)（learn）到這個被選定的value

推導(dǎo)過程

最簡單的方案——只有一個Acceptor

假設(shè)只有一個Acceptor（可以有多個Proposer），只要Acceptor接受它收到的第一個提案，則該提案被選定，該提案里的value就是被選定的value。這樣就保證只有一個value會被選定。
但是，如果這個唯一的Acceptor宕機(jī)了，那么整個系統(tǒng)就無法工作了！
因此，必須要有多個Acceptor！

多個Acceptor

多個Acceptor的情況如下圖。那么，如何保證在多個Proposer和多個Acceptor的情況下選定一個value呢？

下面開始尋找解決方案。
首先我們希望即使只有一個Proposer提出了一個value，該value也最終被選定。
那么，就得到下面的約束：

P1：一個Acceptor必須接受它收到的第一個提案。

但是，這又會引出另一個問題：如果每個Proposer分別提出不同的value，發(fā)給不同的Acceptor。根據(jù)P1，Acceptor分別接受自己收到的第一個提案，就導(dǎo)致不同的value被選定。出現(xiàn)了不一致。如下圖：

剛剛是因為『一個提案只要被一個Acceptor接受，則該提案的value就被選定了』才導(dǎo)致了出現(xiàn)上面不一致的問題。因此，我們需要加一個規(guī)定：

規(guī)定：一個提案被選定需要被半數(shù)以上的Acceptor接受

這個規(guī)定又暗示了：『一個Acceptor必須能夠接受不止一個提案！』不然可能導(dǎo)致最終沒有value被選定。比如上圖的情況。v1、v2、v3都沒有被選定，因為它們都只被一個Acceptor的接受。
所以在這種情況下，我們使用一個全局的編號來標(biāo)識每一個Acceptor批準(zhǔn)的提案，當(dāng)一個具有某value值的提案被半數(shù)以上的Acceptor批準(zhǔn)后，我們就認(rèn)為該value被選定了.
根據(jù)上面的內(nèi)容，我們現(xiàn)在雖然允許多個提案被選定，但必須保證所有被選定的提案都具有相同的value值。否則又會出現(xiàn)不一致。
于是有了下面的約束：

P2：如果某個value為v的提案被選定了，那么每個編號更高的被選定提案的value必須也是v。

一個提案只有被Acceptor接受才可能被選定，因此我們可以把P2約束改寫成對Acceptor接受的提案的約束P2a。

P2a：如果某個value為v的提案被選定了，那么每個編號更高的被Acceptor接受的提案的value必須也是v。

只要滿足了P2a，就能滿足P2。

但是，考慮如下的情況：假設(shè)總的有5個Acceptor。Proposer2提出[M1,V1]的提案，Acceptor2-5（半數(shù)以上）均接受了該提案，于是對于Acceptor2~5和Proposer2來講，它們都認(rèn)為V1被選定。Acceptor1剛剛從宕機(jī)狀態(tài)恢復(fù)過來（之前Acceptor1沒有收到過任何提案），此時Proposer1向Acceptor1發(fā)送了[M2,V2]的提案（V2≠V1且M2>M1），對于Acceptor1來講，這是它收到的第一個提案。根據(jù)P1（一個Acceptor必須接受它收到的第一個提案。），Acceptor1必須接受該提案！同時Acceptor1認(rèn)為V2被選定。這就出現(xiàn)了兩個問題：

Acceptor1認(rèn)為V2被選定，Acceptor2~5和Proposer2認(rèn)為V1被選定。出現(xiàn)了不一致。

V1被選定了，但是編號更高的被Acceptor1接受的提案[M2,V2]的value為V2，且V2≠V1。這就跟P2a（如果某個value為v的提案被選定了，那么每個編號更高的被Acceptor接受的提案的value必須也是v）矛盾了。

所以我們要對P2a約束進(jìn)行強(qiáng)化！

P2a是對Acceptor接受的提案約束，但其實提案是Proposer提出來的，所有我們可以對Proposer提出的提案進(jìn)行約束。得到P2b：

P2b：如果某個value為v的提案被選定了，那么之后任何Proposer提出的編號更高的提案的value必須也是v。

由P2b可以推出P2a進(jìn)而推出P2。
那么，如何確保在某個value為v的提案被選定后，Proposer提出的編號更高的提案的value都是v呢？
只要滿足P2c即可：

P2c：對于任意的Mn和Vn,如果提案[Mn,Vn]被提出，那么肯定存在一個由半數(shù)以上的Acceptor組成的集合S，滿足以下 兩個條件中的任意一個：* 要么S中每個Acceptor都沒有接受過編號小于Mn的提案。* 要么S中所有Acceptor批準(zhǔn)的所有編號小于Mn的提案中，編號最大的那個提案的value值為Vn

從上面的內(nèi)容，可以看出，從P1到P2c的過程其實是對一系列條件的逐步增強(qiáng)，如果需要證明這些條件可以保證一致性，那么就可以進(jìn)行反向推導(dǎo)：P2c =>P2b=>P2a=>P2,然后通過P2和P1來保證一致性。

Proposer生成提案

接下來在P2c的基礎(chǔ)上如何進(jìn)行提案的生成
這里有個比較重要的思想：Proposer生成提案之前，應(yīng)該先去『學(xué)習(xí)』已經(jīng)被選定或者可能被選定的value，然后以該value作為自己提出的提案的value。如果沒有value被選定，Proposer才可以自己決定value的值。這樣才能達(dá)成一致。這個學(xué)習(xí)的階段是通過一個『Prepare請求』實現(xiàn)的。
于是我們得到了如下的提案生成算法：

Proposer選擇一個新的提案編號N，然后向某個Acceptor集合（半數(shù)以上）發(fā)送請求，要求該集合中的每個
Acceptor做出如下響應(yīng)（response）

• Acceptor向Proposer承諾保證不再接受任何編號小于N的提案。
• 如果Acceptor已經(jīng)接受過提案，那么就向Proposer反饋已經(jīng)接受過的編號小于N的，但為最大編號的提案的值。

我們將該請求稱為編號為N的Prepare請求。

如果Proposer收到了半數(shù)以上的Acceptor的響應(yīng)，那么它就可以生成編號為N，Value為V的提案[N,V]。這里的V是所有的響應(yīng)中編號最大的提案的Value。如果所有的響應(yīng)中都沒有提案，那么此時V就可以由Proposer自己選擇。
生成提案后，Proposer將該提案發(fā)送給半數(shù)以上的Acceptor集合，并期望這些Acceptor能接受該提案。我們稱該請求為Accept請求。

Acceptor接受提案

剛剛學(xué)習(xí)了Paxos算法中Proposer的處理邏輯，怎么去生成的提案，下面來看看Acceptor是如何批準(zhǔn)提案的
一個Acceptor可能會受到來自Proposer的兩種請求，分別是Prepare請求和Accept請求，對這兩
類請求作出響應(yīng)的條件分別如下

• Prepare請求：Acceptor可以在任何時候響應(yīng)一個Prepare請求
• Accept請求：在不違背Accept現(xiàn)有承諾的前提下，可以任意響應(yīng)Accept請求

因此，對Acceptor接受提案給出如下約束：

P1a：一個Acceptor只要尚未響應(yīng)過任何編號大于N的Prepare請求，那么他就可以接受這個編號為N的提案。

算法優(yōu)化

上面的內(nèi)容中，分別從Proposer和Acceptor對提案的生成和批準(zhǔn)兩方面來講解了Paxos算法在提案選定過程中的算法細(xì)節(jié)，同時也在提案的編號全局唯一的前提下，獲得了一個提案選定算法，接下來我們再對這個初步算法做一個小優(yōu)化，盡可能的忽略Prepare請求

如果Acceptor收到一個編號為N的Prepare請求，在此之前它已經(jīng)響應(yīng)過編號大于N的Prepare請求。 根據(jù)P1a，該 Acceptor不可能接受編號為N的提案。因此，該Acceptor可以忽略編號為N的Prepare請求。

通過這個優(yōu)化，每個Acceptor只需要記住它已經(jīng)批準(zhǔn)的提案的最大編號以及它已經(jīng)做出Prepare請求響應(yīng)的提案的最大編號，以便出現(xiàn)故障或節(jié)點重啟的情況下，也能保證P2c的不變性，而對于Proposer來說，只要它可以保證不會產(chǎn)生具有相同編號的提案，那么就可以丟棄任意的提案以及它所有的運(yùn)行時狀態(tài)信息。

Paxos算法描述

綜合前面的講解，我們來對Paxos算法的提案選定過程進(jìn)行下總結(jié)，那結(jié)合Proposer和Acceptor對提案的處理邏輯，就可以得到類似于兩階段提交的算法執(zhí)行過程

Paxos算法分為兩個階段。具體如下：

• 階段一：

  • Proposer選擇一個提案編號N，然后向半數(shù)以上的Acceptor發(fā)送編號為N的Prepare請求。
  • 如果一個Acceptor收到一個編號為N的Prepare請求，且N大于該Acceptor已經(jīng)響應(yīng)過的所有Prepare請求的編號，那么它就會將它已經(jīng)接受過的編號最大的提案（如果有的話）作為響應(yīng)反饋給Proposer，同時該Acceptor承諾不再接受任何編號小于N的提案。

• 階段二：

  • 如果Proposer收到半數(shù)以上Acceptor對其發(fā)出的編號為N的Prepare請求的響應(yīng)，那么它就會發(fā)送一個針對[N,V]提案的Accept請求給半數(shù)以上的Acceptor。注意：V就是收到的響應(yīng)中編號最大的提案的value，如果響應(yīng)中不包含任何提案，那么V就由Proposer自己決定。
  • 如果Acceptor收到一個針對編號為N的提案的Accept請求，只要該Acceptor沒有對編號大于N的Prepare請求做出過響應(yīng)，它就接受該提案。

當(dāng)然，實際運(yùn)行過程中，每一個Proposer都有可能產(chǎn)生多個提案，但只要每個Proposer都遵循如上所述的算法運(yùn)行，就一定能夠保證算法執(zhí)行的正確性

Learner學(xué)習(xí)被選定的value

剛剛我們介紹了如何來選定一個提案，下面我們再來看看如

• 方案一：
  Learner獲取一個已經(jīng)被選定的提案的前提是，該提案已經(jīng)被半數(shù)以上的Acceptor批準(zhǔn)，因此，最簡單的做法就是一旦Acceptor批準(zhǔn)了一個提案，就將該提案發(fā)送給所有的Learner
  很顯然，這種做法雖然可以讓Learner盡快地獲取被選定的提案，但是卻需要讓每個Acceptor與所有的Learner逐個進(jìn)行一次通信，通信的次數(shù)至少為二者個數(shù)的乘積
• 方案二：
  另一種可行的方案是，我們可以讓所有的Acceptor將它們對提案的批準(zhǔn)情況，統(tǒng)一發(fā)送給一個特定的Learner（稱為主Learner）, 各個Learner之間可以通過消息通信來互相感知提案的選定情況，基于這樣的前提，當(dāng)主Learner被通知一個提案已經(jīng)被選定時，它會負(fù)責(zé)通知其他的learner在這種方案中，Acceptor首先會將得到批準(zhǔn)的提案發(fā)送給主Learner,再由其同步給其他Learner.因此較方案一而言，方案二雖然需要多一個步驟才能將提案通知到所有的learner，但其通信次數(shù)卻大大減少了，通常只是Acceptor和Learner的個數(shù)總和，但同時，該方案引入了一個新的不穩(wěn)定因素：主Learner隨時可能出現(xiàn)故障
• 方案三：
  在方案二的時候，我們提到，方案二最大的問題在于主Learner存在單點問題，即主Learner隨時可能出現(xiàn)故障，因此，對方案二進(jìn)行改進(jìn)，可以將主Learner的范圍擴(kuò)大，即Acceptor可以將批準(zhǔn)的提案發(fā)送給一個特定的Learner集合，該集合中每個Learner都可以在一個提案被選定后通知其他的Learner。這個Learner集合中的Learner個數(shù)越多，可靠性就越好，但同時網(wǎng)絡(luò)通信的復(fù)雜度也就越高

如何保證Paxos算法的活性

根據(jù)前面的內(nèi)容講解，我們已經(jīng)基本上了解了Paxos算法的核心邏輯，那接下來再來看看Paxos算法在實際過程中的一些細(xì)節(jié)

活性：最終一定會發(fā)生的事情：最終一定要選定value

假設(shè)存在這樣一種極端情況，有兩個Proposer依次提出了一系列編號遞增的提案，導(dǎo)致最終陷入死循環(huán)，沒有value被選定,具體流程如下:

解決：通過選取主Proposer，并規(guī)定只有主Proposer才能提出議案。這樣一來只要主Proposer和過半的Acceptor能夠正常進(jìn)行網(wǎng)絡(luò)通信，那么但凡主Proposer提出一個編號更高的提案，該提案終將會被批準(zhǔn)，這樣通過選擇一個主Proposer，整套Paxos算法就能夠保持活性

分布式理論：一致性算法 Raft

什么是Raft 算法

首先說什么是 Raft 算法：Raft 是一種為了管理復(fù)制日志的一致性算法。

Raft提供了和Paxos算法相同的功能和性能，但是它的算法結(jié)構(gòu)和Paxos不同。Raft算法更加容易理解并且更容易構(gòu)建實際的系統(tǒng)。

Raft將一致性算法分解成了3模塊

領(lǐng)導(dǎo)人選舉

日志復(fù)制

安全性

Raft算法分為兩個階段，首先是選舉過程，然后在選舉出來的領(lǐng)導(dǎo)人帶領(lǐng)進(jìn)行正常操作，比如日志復(fù)制等。

領(lǐng)導(dǎo)人Leader選舉

Raft 通過選舉一個領(lǐng)導(dǎo)人，然后給予他全部的管理復(fù)制日志的責(zé)任來實現(xiàn)一致性。

在Raft中，任何時候一個服務(wù)器都可以扮演下面的角色之一：

• 領(lǐng)導(dǎo)者(leader)：處理客戶端交互，日志復(fù)制等動作，一般一次只有一個領(lǐng)導(dǎo)者
• 候選者(candidate)：候選者就是在選舉過程中提名自己的實體，一旦選舉成功，則成為領(lǐng)導(dǎo)者
• 跟隨者(follower)：類似選民，完全被動的角色，這樣的服務(wù)器等待被通知投票

而影響他們身份變化的則是 選舉。

Raft使用心跳機(jī)制來觸發(fā)選舉。當(dāng)server啟動時，初始狀態(tài)都是follower。每一個server都有一個定時器，超時時間為election timeout（一般為150-300ms），如果某server沒有超時的情況下收到來自領(lǐng)導(dǎo)者或者候選者的任何消息，定時器重啟，如果超時，它就開始一次選舉。

下面用圖示展示這個過程：

初始狀態(tài)下集群中的所有節(jié)點都處于 follower 狀態(tài)。

某一時刻，其中的一個 follower 由于沒有收到 leader 的 heartbeat 率先發(fā)生 election timeout 進(jìn)而發(fā)起選舉。

只要集群中超過半數(shù)的節(jié)點接受投票，candidate 節(jié)點將成為即切換 leader 狀態(tài)。

成為 leader 節(jié)點之后，leader 將定時向 follower 節(jié)點同步日志并發(fā)送 heartbeat。

節(jié)點異常

集群中各個節(jié)點的狀態(tài)隨時都有可能發(fā)生變化。從實際的變化上來分類的話，節(jié)點的異常大致可以分為四種類型：

• leader 不可用；
• follower 不可用；
• 多個 candidate 或多個 leader；
• 新節(jié)點加入集群。

leader 不可用

下面將說明當(dāng)集群中的 leader 節(jié)點不可用時，raft 集群是如何應(yīng)對的。

一般情況下，leader 節(jié)點定時發(fā)送 heartbeat 到 follower 節(jié)點。

由于某些異常導(dǎo)致 leader 不再發(fā)送 heartbeat ，或 follower 無法收到 heartbeat 。

當(dāng)某一 follower 發(fā)生 election timeout 時，其狀態(tài)變更為 candidate，并向其他 follower 發(fā)起投票。

當(dāng)超過半數(shù)的 follower 接受投票后，這一節(jié)點將成為新的 leader，leader 的步進(jìn)數(shù)加 1 并開始向 follower 同步日志。

當(dāng)一段時間之后，如果之前的 leader 再次加入集群，則兩個 leader 比較彼此的步進(jìn)數(shù)，步進(jìn)數(shù)低的 leader 將切換自己的狀態(tài)為 follower。

較早前 leader 中不一致的日志將被清除，并與現(xiàn)有 leader 中的日志保持一致。

follower 節(jié)點不可用

follower 節(jié)點不可用的情況相對容易解決。因為集群中的日志內(nèi)容始終是從 leader 節(jié)點同步的，只要這一節(jié)點再次加入集群時重新從 leader 節(jié)點處復(fù)制日志即可。

• 集群中的某個 follower 節(jié)點發(fā)生異常，不再同步日志以及接收 heartbeat。
  

• 經(jīng)過一段時間之后，原來的 follower 節(jié)點重新加入集群。
  

• 這一節(jié)點的日志將從當(dāng)時的 leader 處同步。
  

多個 candidate 或多個 leader

在集群中出現(xiàn)多個 candidate 或多個 leader 通常是由于數(shù)據(jù)傳輸不暢造成的。出現(xiàn)多個 leader 的情況相對少見，但多個 candidate 比較容易出現(xiàn)在集群節(jié)點啟動初期尚未選出 leader 的“混沌”時期。

• 初始狀態(tài)下集群中的所有節(jié)點都處于 follower 狀態(tài)。
  

• 兩個節(jié)點同時成為 candidate 發(fā)起選舉。
  

• 兩個 candidate 都只得到了少部分 follower 的接受投票。
  

• candidate 繼續(xù)向其他的 follower 詢問。
  

• 由于一些 follower 已經(jīng)投過票了，所以均返回拒絕接受。
  

• candidate 也可能向一個 candidate 詢問投票。
  

• 在步進(jìn)數(shù)相同的情況下，candidate 將拒絕接受另一個 candidate 的請求。
  

• 由于第一次未選出 leader，candidate 將隨機(jī)選擇一個等待間隔（150ms ~ 300ms）再次發(fā)起投票。
  

• 如果得到集群中半數(shù)以上的 follower 的接受，這一 candidate 將成為 leader。
  

• 稍后另一個 candidate 也將再次發(fā)起投票。
  

• 由于集群中已經(jīng)選出 leader，candidate 將收到拒絕接受的投票。
  

• 在被多數(shù)節(jié)點拒絕之后，并已知集群中已存在 leader 后，這一 candidate 節(jié)點將終止投票請求、切換為follower，從 leader 節(jié)點同步日志。
  

日志復(fù)制（保證數(shù)據(jù)一致性）

日志復(fù)制的過程
??Leader選出后，就開始接收客戶端的請求。Leader把請求作為日志條目（Log entries）加入到它的日志中，然后并行的向其他服務(wù)器發(fā)起 AppendEntries RPC復(fù)制日志條目。當(dāng)這條日志被復(fù)制到大多數(shù)服務(wù)器上，Leader將這條日志應(yīng)用到它的狀態(tài)機(jī)并向客戶端返回執(zhí)行結(jié)果。
??
下圖表示了當(dāng)一個客戶端發(fā)送一個請求給領(lǐng)導(dǎo)者，隨后領(lǐng)導(dǎo)者復(fù)制給跟隨者的整個過程。

4 個步驟：

• 客戶端的每一個請求都包含被復(fù)制狀態(tài)機(jī)執(zhí)行的指令。
• leader把這個指令作為一條新的日志條目添加到日志中，然后并行發(fā)起 RPC 給其他的服務(wù)器，讓他們復(fù)制這條信息。
• 跟隨者響應(yīng)ACK,如果 follower 宕機(jī)或者運(yùn)行緩慢或者丟包，leader會不斷的重試，直到所有的 follower 最終都復(fù)制了所有的日志條目。
• 通知所有的Follower提交日志，同時領(lǐng)導(dǎo)人提交這條日志到自己的狀態(tài)機(jī)中，并返回給客戶端。

可以看到，直到第四步驟，整個事務(wù)才會達(dá)成。中間任何一個步驟發(fā)生故障，都不會影響日志一致性。

文章有點長，感謝大家耐心看完，希望大家能有所收獲，其實還有分布式系統(tǒng)設(shè)計策略和分布式架構(gòu)網(wǎng)絡(luò)通信沒寫，下篇繼續(xù)寫，敬請期待！

希望大家每天都能有所收獲！！

總結(jié)

以上是生活随笔為你收集整理的分布式理论，看完这篇你定能有所获的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。