分布式事務基礎

這一篇主要介紹分布式事務的基礎知識，一些基礎的算法、定理、簡單應用等。下篇文章介紹網際網路業界的具體實踐方案。

1、CAP定理

CAP定理是由加州大學伯克利分校Eric Brewer教授提出來的，其核心思想是任何基于網絡的資料共享，系統最多隻能滿足資料一緻性(Consistency)、可用性(Availability)和網絡分區容忍(Partition Tolerance)三個特性中的兩個，三個特性的定義如下：

• 一緻性(Consistency) ： 等同于所有節點擁有資料的最新版本，對于關系型資料庫，要求更新過的資料能被後續的通路都能看到
• 可用性(Availability) ： 資料具備高可用性
• 分區容錯性(Partition tolerance) ： 容忍網絡出現分區，分區之間網絡不可達

具體地講在分布式系統中，在任何資料庫設計中，一個Web應用至多隻能同時支援上面的兩個屬性。顯然，任何橫向擴充政策都要依賴于資料分區。是以，設計人員必須在一緻性與可用性之間做出選擇。

1.1 CAP的應用執行個體

• CA(一緻性+可用性）without P（容錯性）

  單機的Mysql和Oracle；

  分布式叢集中不存在這種情況，因為多個節點必定考慮主備同步，也就是網絡。

• CP(一緻性+容錯性）without A（可用性）

  分布式的資料庫，如Redis，HBase，Zookeeper

  任何時刻對ZooKeeper請求能得到一緻的資料結果:當master節點網絡故障，會進行選舉機制，選舉時叢集不可用。但是它不能保證每次服務請求的可用性，ZooKeeper可能會丢棄一些請求，消費者程式需要重新請求才能獲得結果。

• AP(可用性+容錯性）without C（一緻性）

  12306買票

  購買的時候提示你是有票的（但是可能實際已經沒票了），但是過了一會系統提示你下單失敗，餘票不足。其實舍棄的隻是強一緻性。退而求其次保證了最終一緻性。

  Eureka

  各個節點平等；有節點挂掉，會立刻換至其他節點，保證服務可用，隻不過查到的資訊可能不是最新的。在網絡穩定後，目前執行個體新的注冊資訊會被同步到其他節點中。

  一旦網絡問題發生，節點之間可能會失去聯系。為了保證高可用，需要在使用者通路時可以馬上得到傳回，導緻全局資料的不一緻性。

2、 BASE理論

在分布式系統中，我們往往追求的是可用性，它的重要程式比一緻性要高，那麼如何實作高可用性呢？ 前人已經給我們提出來了另外一個理論，就是BASE理論，它是用來對CAP定理進行進一步擴充的。BASE理論指的是：

• Basically Available（基本可用）
• Soft state（軟狀态）
• Eventually consistent（最終一緻性）

BASE理論是對CAP中的一緻性和可用性進行一個權衡的結果，理論的核心思想就是：我們無法做到強一緻，但每個應用都可以根據自身的業務特點，采用适當的方式來使系統達到最終一緻性（Eventual consistency）。

3、 Paxos協定

Paxos協定由Leslie Lamport最早在1990年提出，由于Paxos在雲計算領域的廣泛應用Leslie Lamport是以獲得了2013年度圖靈獎。

Paxos協定提出隻要系統中2f+1個節點中的f+1個節點可用，那麼系統整體就可用并且能保證資料的強一緻性，它對于可用性的提升是極大的，仍然假設單節點的可用性是P，那麼2f+1個節點中任意組合的f+1以上個節點正常的可用性P(total)=,又假設P=0.99，f=2，P(total)=0.9999901494，可用性将從單節點的2個9提升到了5個9，這意味着系統每年的當機時間從87.6小時降到0.086小時，這已經可以滿足地球上99.99999999%的應用需求。

Leslie寫的兩篇論文：《The Part-Time Parliament》和《Paxos Made Simple》比較完整的闡述了Paxos的工作流程和證明過程，Paxos協定把每個資料寫請求比喻成一次提案（proposal），每個提案都有一個獨立的編号，提案會轉發到送出者（Proposer）來送出，提案必須經過2f+1個節點中的f+1個節點接受才會生效，2f+1個節點叫做這次提案的投票委員會(Quorum)，投票委員會中的節點叫做Acceptor，Paxos協定流程還需要滿足兩個限制條件： a）Acceptor必須接受它收到的第一個提案；b）如果一個提案的v值被大多數Acceptor接受過，那後續的所有被接受的提案中也必須包含v值（v值可以了解為提案的内容，提案由一個或多個v和提案編号組成）。

Paxos協定流程劃分為兩個階段，第一階段是Proposer學習提案最新狀态的準備階段；第二階段是根據學習到的狀态組成正确提案送出的階段，完整的協定過程如下：

階段 1

1. Proposer選擇一個提案編号n ，然後向半數以上的Acceptors發送編号為 n 的prepare請求。
2. 如果一個Acceptor收到一個編号為n 的prepare請求，且 n 大于它已經響應的所有prepare請求的編号，那麼它就會保證不會再通過(accept)任何編号小于 n 的提案，同時将它已經通過的最大編号的提案(如果存在的話)作為響應。

階段 2

1. 如果Proposer收到來自半數以上的Acceptor對于它的prepare請求(編号為n )的響應，那麼它就會發送一個針對編号為 n ，value值為 v 的提案的accept請求給Acceptors，在這裡 v 是收到的響應中編号最大的提案的值，如果響應中不包含提案，那麼它就是任意值。
2. 如果Acceptor收到一個針對編号n 的提案的accept請求，隻要它還未對編号大于 n 的prepare請求作出響應，它就可以通過這個提案。

用時序圖來描述Paxos協定如圖3所示：

上述Paxos協定流程看起來比較複雜，是因為要保證很多邊界條件下的協定完備性，譬如初試值為空、兩個Proposer同時送出提案等情況，但Paxos協定的核心可以簡單描述為：Proposer先從大多數Acceptor那裡學習提案的最新内容，然後根據學習到的編号最大的提案内容組成新的提案送出，如果提案獲得大多數Acceptor的投票通過就意味着提案被通過。由于學習提案和通過提案的Acceptor集合都超過了半數，是以一定能學到最新通過的提案值，兩次提案通過的Acceptor集合中也一定存在一個公共的Acceptor，在滿足限制條件b時這個公共的Acceptor時保證了資料的一緻性，于是Paxos協定又被稱為多數派協定。

Paxos協定的真正偉大之處在于它的簡潔性，Paxos協定流程中任何消息都是可以丢失的，一緻性保證并不依賴某個特殊消息傳遞的成功，這極大的簡化了分布式系統的設計，極其比對分布式環境下網絡可能分區的特點，相比較在Paxos協定之前的“兩階段送出（2PC）”也能保證資料強一緻性，但複雜度相當高且依賴單個協調者的可用性。

那既然Paxos如此強大，那為什麼還會出現ZAB協定？

4、 ZAB 協定

Paxos協定雖然是完備的，但要把它應用到實際的分布式系統中還有些問題要解決：

• 在多個Proposer的場景下，Paxos不保證先送出的提案先被接受，實際應用中要保證多提案被接受的先後順序怎麼辦？
• Paxos允許多個Proposer送出提案，那有可能出現活鎖問題，出現場景是這樣的：提案n在第二階段還沒有完成時，新的提案n+1的第一階段prepare請求到達Acceptor，按協定規定Acceptor将響應新提案的prepare請求并保證不會接受小于n+1的任何請求，這可能導緻提案n将不會被通過，同樣在n+1提案未完成第二階段時，假如提案n的送出者又送出了n+2提案，這可能導緻n+1提案也無法通過。
• Paxos協定規定提案的值v隻要被大多數Acceptor接受過，後續的所有提案不能修改值v，那現實情況下我還要修改v值怎麼辦？

ZooKeeper的核心算法ZAB通過一個簡單的限制解決了前2個問題：所有提案都轉發到唯一的Leader（通過Leader選舉算法從Acceptor中選出來的）來送出，由Leader來保證多個提案之間的先後順序，同時也避免了多Proposer引發的活鎖問題。

ZAB協定的過程用時序圖描述如圖4所示，相比Paxos協定省略了Prepare階段，因為Leader本身就有提案的最新狀态，不需要有提案内容學習的過程,圖中的Follower對應Paxos協定中的Acceptor，Observer對應Paxos中的Learner。

ZAB引入Leader後也會帶來一個新問題： Leader當機了怎麼辦？其解決方案是選舉出一個新的Leader，選舉Leader的過程也是一個Paxos提案決議過程，這裡不展開讨論。

那如何做到提案的值v可以修改呢？這不是ZAB協定的範疇，研究ZooKeeper源碼後發現它是這麼做的：ZooKeeper提供了一個znode的概念，znode可以被修改，ZooKeeper對每個znode都記錄了一個自增且連續的版本号，對znode的任何修改操作（create/set/setAcl）都會促發一次Paxos多數派投票過程，投票通過後znode版本号加1，這相當于用znode不同版本的多次Paxos協定來破除單次Paxos協定無法修改提案值的限制。

從保證一緻性的算法核心角度看ZAB确實是借鑒了Paxos的多數派思想，但它提供的全局時序保證以及ZooKeeper提供給使用者可修改的znode才讓Paxos在開源界大放異彩，是以ZAB的價值不僅僅是提供了Paxos算法的優化實作，也難怪ZAB的作者一直強調ZAB和Paxos是不一樣的算法。

CAP理論告訴我們在分布式環境下網絡分區無法避免，需要去權衡選擇資料的一緻性和可用性，Paxos協定提出了一種極其簡單的算法在保障資料一緻性時最大限度的優化了可用性，ZooKeeper的ZAB協定把Paxos更加簡化，并提供全局時序保證，使得Paxos能夠廣泛應用到工業場景。

5、兩階段送出協定（2PC）

兩階段送出協定（Two-phase Commit Protocol，簡稱 2PC），是分布式事務的核心協定。在此協定中，一個事務管理器（Transaction Manager，簡稱 TM）協調 1 個或多個資料總管（Resource Manager，簡稱 RM）的活動，所有資料總管向事務管理器彙報自身活動狀态，由事務管理器根據各資料總管彙報的狀态（完成準備或準備失敗）來決定各資料總管是“送出”事務還是進行“復原”操作。

二階段送出的具體流程如下：

1. 應用程式向事務管理器送出請求，發起分布式事務；
2. 在第一階段，事務管理器聯絡所有資料總管，通知它們準備送出事務；
3. 各資料總管傳回完成準備（或準備失敗）的消息給事務管理器（響應逾時算作失敗）；

4. 在第二階段：

   1. 如果所有資料總管均完成準備（如圖 1），則事務管理器會通知所有資料總管執行事務送出；

   2. 如果任一資料總管準備失敗（如圖 2 中的資料總管 B），則事務管理器會通知所有資料總管進行事務復原。

6、TCC模型

Try-Confirm-Cancel（TCC）是初步操作（Try）、确認操作（Confirm）和取消操作（Cancel）三種操作的縮寫，這三種操作的業務含義如下：

• Try 階段：對業務系統做檢測及資源預留；
• Confirm 階段：對業務系統做确認送出。預設 Confirm 階段是不會出錯的，隻要 Try 成功，Confirm 一定成功；
• Cancel 階段：當業務執行出現錯誤，需要復原的狀态下，執行業務取消，釋放預留資源。

TCC 是二階段送出協定（Two-phase Commit Protocol，簡稱 2PC）的擴充，Try 操作對應 2PC 中一階段的準備送出事務（Prepare），Confirm 對應 2PC 中二階段事務送出（Commit），Cancel 對應 2PC 中二階段事務復原（Rollback）。

與 2PC 不同的是，TCC 是一種程式設計模型，是應用層的 2PC；TCC 的 3 個操作均由編碼實作，通過編碼實作了 2PC 資料總管的功能。

TCC 自編碼的特性決定 TCC 資料總管可以跨資料庫、跨應用實作資源管理，将對不同的資料庫通路、不同的業務操作通過編碼方式轉換一個原子操作，解決了複雜業務場景下的事務問題。同時 TCC 的每一個操作對于資料庫來講都是一個本地資料庫事務，操作結束則本地資料庫事務結束，資料庫的資源也就被釋放；這就規避了資料庫層面的 2PC 對資源占用導緻的性能低下問題。

7、柔性事務

7.1 柔性事務的定義

剛性事務（如單資料庫）完全遵循 ACID 規範，即資料庫事務正确執行的四個基本要素：

• 原子性（Atomicity）
• 一緻性（Consistency）
• 隔離性（Isolation）
• 持久性（Durability）

柔性事務（如分布式事務）為了滿足可用性、性能與降級服務的需要，降低一緻性（Consistency）與隔離性（Isolation）的要求，遵循 BASE 理論：

• 基本業務可用性（Basic Availability）
• 柔性狀态（Soft state）
• 最終一緻性（Eventual consistency）

同樣的，柔性事務也部分遵循 ACID 規範：

• 原子性：嚴格遵循
• 一緻性：事務完成後的一緻性嚴格遵循；事務中的一緻性可适當放寬
• 隔離性：并行事務間不可影響；事務中間結果可見性允許安全放寬
• 持久性：嚴格遵循

7.2 柔性事務的分類

柔性事務分為：兩階段型、補償型、異步確定型、最大努力通知型。

• 兩階段型

  分布式事務二階段送出，對應技術上的 XA、JTA/JTS，這是分布式環境下事務處理的典型模式。

• 補償型

  TCC 型事務（Try-Confirm-Cancel）可以歸為補償型。在 Try 成功的情況下，如果事務要復原，Cancel 将作為一個補償機制，復原 Try 操作；TCC 各操作事務本地化，且盡早送出（沒有兩階段限制）；當全局事務要求復原時，通過另一個本地事務實作“補償”行為。

  TCC 是将資源層的二階段送出協定轉換到業務層，成為業務模型中的一部分。

• 異步確定型

  将一些有同步沖突的事務操作變為異步操作，避免對資料庫事務的争用，如消息事務機制。

• 最大努力通知型

  通過通知伺服器（消息通知）進行，允許失敗，有補充機制。