1. 前文回顧

在上一篇中，我們主要介紹了分布式系統中常見的複制模型，并描述了每一種模型的優缺點以及使用場景，同時闡述了分布式系統中特有的一些技術挑戰。首先，常見的分布式系統複制模型有3種，分别是主從模型、多主模型以及無主模型。此外，複制從用戶端的時效性來說分為同步複制&&異步複制，異步複制具有滞後性，可能會造成資料不一緻，因為這個不一緻，會帶來各種各樣的問題。

此外，第一篇文章用了“老闆安排人幹活”的例子比喻了分布式系統中特有的挑戰，即部分失效以及不可靠的時鐘問題。這給分布式系統設計帶來了很大的困擾。似乎在沒有機制做保證的情況下，一個樸素的分布式系統什麼事情都做不了。

在上一篇的最後，我們對分布式系統系統模型做了一些假設，這些假設對給出後面的解決方案其實是非常重要的。首先針對部分失效，是我們需要對系統的逾時進行假設，一般我們假設為半同步模型，也就是說一般情況下延遲都非常正常，一旦發生故障，延遲會變得偏差非常大。另外，對于節點失效，我們通常在設計系統時假設為崩潰-恢複模型。最後，面對分布式系統的兩個保證Safty和Liveness，我們優先保證系統是Safety，也就是安全；而Liveness（活性）通常在某些前提下才可以滿足。

2. 本文簡介

通過第一篇文章，我們知道了留待我們解決的問題有哪些。那麼這篇文章中，将分别根據我們的假設去解決上述的挑戰。這些保證措施包括事務、一緻性以及共識。接下來講介紹它們的作用以及内在聯系，然後我們再回過頭來審視一下Kafka複制部分的設計，看看一個實際的系統在設計上是否真的可以直接使用那些套路，最後介紹業界驗證分布式算法的一些工具和架構。接下來，繼續我們的資料複制之旅吧！

3. 事務&外部一緻性

說到事務，相信大家都能簡單說出個一二來，首先能本能做出反應出的，應該就是所謂的“ACID”特性了，還有各種各樣的隔離級别。是的，它們确實都是事務需要解決的問題。

在這一章中，我們會更加有條理地了解下它們之間的内在聯系，詳細看一看事務究竟要解決什麼問題。在《DDIA》一書中有非常多關于資料庫事務的具體實作細節，但本文中會弱化它們，畢竟本文不想詳細介紹如何設計一款資料庫，我們隻需探究問題的本身，等真正尋找解決方案時再去詳細看設計，效果可能會更好。下面我們正式開始介紹事務。

3.1 事務的産生

系統中可能會面臨下面的問題：

程式依托的作業系統層，硬體層可能随時都會發生故障（包括一個操作執行到一半時）。
應用程式可能會随時發生故障（包括操作執行到一半時）。
網絡中斷可能随時會發生，它會切斷用戶端與服務端的連結或資料庫之間的連結。
多個用戶端可能會同時通路服務端，并且更新統一批資料，導緻資料互相覆寫（臨界區）。
用戶端可能會讀到過期的資料，因為上面說的，可能操作執行一半應用程式就挂了。

假設上述問題都會出現在我們對于存儲系統（或者資料庫）的通路中，這樣我們在開發自己應用程式的同時，還需要額外付出很大代價處理這些問題。事務的核心使命就是嘗試幫我們解決這些問題，提供了從它自己層面所看到的安全性保證，讓我們在通路存儲系統時隻專注我們本身的寫入和查詢邏輯，而非這些額外複雜的異常處理。而說起解決方式，正是通過它那大名鼎鼎的ACID特性來進行保證的。

3.2 不厭其煩——ACID特性

這四個縮寫所組成的特性相信大家已形成本能反應，不過《DDIA》一書中給出的定義确實更加有利于我們更加清晰地了解它們間的關系，下面将分别進行說明：

A：原子性（Atomicity）：原子性實際描述的是同一個用戶端對于多個操作之間的限制，這裡的原子表示的是不可分割，原子性的效果是，假設有操作集合{A,B,C,D,E}，執行後的結果應該和單個用戶端執行一個操作的效果相同。從這個限制我們可以知道：

對于操作本身，就算發生任何故障，我們也不能看到任何這個操作集中間的結果，比如操作執行到C時發生了故障，但是事務應該重試，直到我們需要等到執行完之後，要麼我們應該恢複到執行A之前的結果。
對于操作作用的服務端而言，出現任何故障，我們的操作不應該對服務端産生任何的副作用，隻有這樣用戶端才能安全的重試，否則，如果每次重試都會對服務端産生副作用，用戶端是不敢一直安全的重試的。

是以，對于原子性而言，書中描述說的是能在執行發生異常時丢棄，可以直接終止，且不會對服務端産生任何副作用，可以安全的重試，原子性也成為“可終止性”。

C：一緻性（Consistency）：這個名詞有太多的重載，也就是說它在不同語境中含義會截然不同，但可能又有聯系，這就可能讓我們陷入混亂，比如：

資料複制時，副本間具有一緻性，這個一緻性應該指上一章中提到的不同副本狀态的一緻。
一緻性Hash，這是一種分區算法，個人了解是為了能夠在各種情況下這個Hash算法都可以以一緻的方式發揮作用。
CAP定理中的一緻性指的是後面要介紹的一個特殊的内部一緻性，稱為“線性一緻性”。
我們稍後要介紹ACID中的一緻性，指的是程式的某些“不變式”，或“良好狀态”。

我們需要區分不同語境中一緻性所表達含義的差別，也希望大家看完今天的分享，能更好地幫助大家記住這些差別。話說回來，這裡的一緻性指的是對于資料一組特定陳述必須成立，即“不變式”，這裡有點類似于算法中的“循環不變式”，即當外界環境發生變化時，這個不變式一定需要成立。

書中強調，這個裡面的一緻性更多需要使用者的應用程式來保證，因為隻有使用者知道所謂的不變式是什麼。這裡舉一個簡單的小例子，例如我們往Kafka中append消息，其中有兩條消息内容都是2，如果沒有額外的資訊時，我們也不知道到底是用戶端因為故障重試發了兩次，還是真的就有兩條一模一樣的資料。

如果想進行區分，可以在使用者程式消費後走自定義的去重邏輯，也可以從Kafka自身出發，用戶端發送時增加一個“發号”環節标明消息的唯一性（高版本中Kafka事務的實作大緻思路）這樣引擎本身就具備了一定的自己設定“不變式”的能力。不過如果是更複雜的情況，還是需要使用者程式和調用服務本身共同維護。

I：隔離性（Isolation）：隔離性實際上是事務的重頭戲，也是門道最多的一環，因為隔離性解決的問題是多個事務作用于同一個或者同一批資料時的并發問題。一提到并發問題，我們就知道這一定不是個簡單的問題，因為并發的本質是時序的不确定性，當這些不确定時序的作用域有一定沖突（Race）時就可能會引發各種各樣的問題，這一點和多線程程式設計是類似的，但這裡面的操作遠比一條計算機指令時間長得多，是以問題會更嚴重而且更多樣。

這裡給一個具體的執行個體來直覺感受下，如下圖展示了兩個用戶端并發的修改DB中的一個counter，由于User2的get counter發生的時刻在User1更新的過程中，是以讀到的counter是個舊值，同樣User2更新也類似，是以最後應該預期counter值為44，結果兩個人看到的counter都是43（類似兩個線程同時做value++）。

一個完美的事務隔離，在每個事務看來，整個系統隻有自己在工作，對于整個系統而言這些并發的事務一個接一個的執行，也仿佛隻有一個事務，這樣的隔離成為“可序列化（Serializability）”。當然，這樣的隔離級别會帶來巨大的開銷，是以出現了各種各樣的隔離級别，進而滿足不同場景的需要。後文會詳細介紹不同的隔離級别所解決的問題。

圖1 隔離性問題導緻更新丢失

D：持久性（Durability）: 這個特性看似比較好了解，就一點，隻要事務完成，不管發生任何問題，都不應該發生資料丢失。從理論上講，如果是單機資料庫，起碼資料已被寫入非易失性存儲（至少已落WAL），分布式系統中資料被複制到了各個副本上，并受到副本Ack。但實際情況下，也未必就一定能保證100%的持久性。這裡面的情況書中有詳細的介紹，這裡就不做重複的Copy工作了，也就是說事務所保證的持久性一般都是某種權衡下的結果。

上面四個特性中，實際上對于隔離性的問題，可能是問題最多樣的，也是最為複雜的。因為一味強調“序列化”可能會帶來不可接受的性能開銷。是以，下文将重點介紹一些比可序列化更弱的隔離級别。

3.3 事務按操作對象的劃分&&安全的送出重試

在介紹後面内容前，有兩件事需要事先做下強調，分别是事務操作的對象以及事務的送出與重試，分為單對象&&多對象。

單對象寫入：這種書中給出了兩種案例。

1. 第一個是單個事物執行一個長時間的寫入，例如寫入一個20KB的JSON對象，假設寫到10KB時斷掉會發生什麼？

a. 資料庫是否會存在10KB沒法解析的髒資料。

b. 如果恢複之後數是否能接着繼續寫入。

c. 另一個用戶端讀取這個文檔，是否能夠看到恢複後的最新值，還是讀到一堆亂碼。

2. 另一種則是類似上圖中counter做自增的功能。

這種事務的解決方法一般是通過日志回放（原子性）、鎖（隔離性）、CAS（隔離性）等方式來進行保證。

多對象事務：這類事務實際上是比較複雜的，比如可能在某些分布式系統中，操作的對象可能會跨線程、跨程序、跨分區，甚至跨系統。這就意味着，我們面臨的問題多于上一篇文章提到的那些分布式系統特有的問題，處理那些問題顯然要更複雜。有些系統幹脆把這種“鍋”甩給使用者，讓應用程式自己來處理問題，也就是說，我們可能需要自己處理因沒有原子性帶來的中間結果問題，因為沒有隔離性帶來的并發問題。當然，也有些系統實作了這些所謂的分布式事務，後文中會介紹具體的實作手段。

另一個需要特别強調的點是重試，事務的一個核心特性就是當發生錯誤時，用戶端可以安全的進行重試，并且不會對服務端有任何副作用，對于傳統的真的實作ACID的資料庫系統，就應該遵循這樣的設計語義。但在實際實踐時，如何保證上面說的能夠“安全的重試”呢？書中給出了一些可能發生的問題和解決手段：

假設事務送出成功了，但服務端Ack的時候發生了網絡故障，此時如果用戶端發起重試，如果沒有額外的手段，就會發生資料重複，這就需要服務端或應用程式自己提供能夠區分消息唯一性的額外屬性（服務端内置的事務ID或者業務自身的屬性字段）。
由于負載太大導緻了事務送出失敗，這是貿然重試會加重系統的負擔，這時可在用戶端進行一些限制，例如采用指數退避的方式，或限制一些重試次數，放入用戶端自己系統所屬的隊列等。
在重試前進行判斷，盡在發生臨時性錯誤時重試，如果應用已經違反了某些定義好的限制，那這樣的重試就毫無意義。
如果事務是多對象操作，并且可能在系統中發生副作用，那就需要類似“兩階段送出”這樣的機制來實作事務送出。

3.4 弱隔離級别

事務隔離要解決的是并發問題，并發問題需要讨論兩個問題時序與競争，往往由于事物之間的操作對象有競争關系，并且又因為并發事務之間不确定的時序關系，會導緻這些所操作的有競争關系的對象會出現各種奇怪的結果。

所謂不同的隔離級别，就是試圖去用不同的開銷來滿足不同場景下對于時序要求的嚴格程度。我們可能不一定知道具體怎麼實作這些事務隔離級别，但每個隔離級别解決的問題本身我們應該非常清晰，這樣才不會在各種隔離級别和開銷中比較輕松的做權衡。這裡，我們不直接像書中一樣列舉隔離級别，我們首先闡述并發事務可能産生的問題，然後再去介紹每種隔離級别分别能夠解決那些問題。

髒讀

所謂髒讀，指的就是使用者能不能看到一個還沒有送出事務的結果，如果是，就是髒讀。下圖展示了沒有髒讀應該滿足什麼樣的承諾，User1的一個事務分别設定x=3、y=3，但在這個事務送出之前，User2在調用get x時，需要傳回2，因為此時User1并沒有送出事務。

圖2 髒讀

防止髒讀的意義：

如果是單對象事務，用戶端會看到一個一會即将可能被復原的值，如果我需要依據這個值做決策，就很有可能會出現決策錯誤。
如果是多對象事務，可能用戶端對于不同系統做通路時一部分資料更新，一部分未更新，那樣使用者可能會不知所措。

髒寫

如果一個用戶端覆寫了另一個用戶端尚未送出的寫入，我們就稱這樣的現象為髒寫。

這裡同樣給個執行個體，對于一個二手車的交易，需要更新兩次資料庫實作，但有兩個使用者并發的進行交易，如果像圖中一樣不禁止髒寫，就可能存在銷售清單顯示交易屬于Bob但發票卻發給了Alice，因為兩個事務對于兩個資料的相同記錄互相覆寫。

圖3 髒寫

讀偏差（不可重複讀）

直接上例子，Alice在兩個銀行賬戶總共有1000塊，每個賬戶500，現在她想從一個賬戶向另一個賬戶轉賬100，并且她想一直盯着自己的兩個賬戶看看錢是否轉成功了。不巧的是，他第一次看賬戶的時候轉賬還沒發生，而成功後隻查了一個賬戶的值，正好少了100，是以最後加起來會覺得自己少了100元。

如果隻是這種場景，其實隻是個臨時性的現象，後面再查詢就會得到正确的值，但是如果基于這樣的查詢去做别的事情，那可能就會出現問題了，比如将這個記錄Select出來進行備份，以防DB崩潰。但不巧如果後面真的崩潰，如果基于這次查詢到的資料做備份，那這100元可能真的永久的丢失了。如果是這樣的場景，不可重複讀是不能被接受的。

圖4 讀偏差

更新丢失

這裡直接把之前那個兩個使用者同時根據舊值更新計數器的例子搬過來，這是個典型的更新丢失問題：

圖5 隔離性問題導緻更新丢失

寫偏差 && 幻讀

這種問題描述的是，事務的寫入需要依賴于之前判斷的結果，而這個結果可能會被其他并發事務修改。

圖6 幻讀

執行個體中有兩個人Alice和Bob決定是否可以休班，做這個決定的前提是判斷目前是否有兩個以上的醫生正在值班，如果是則自己可以安全的休班，然後修改值班醫生資訊。但由于使用了快照隔離（後面會介紹）機制，兩個事務傳回的結果全都是2，進入了修改階段，但最終的結果其實是違背了兩名醫生值班的前提。

造成這個問題的根本原因是一種成為“幻讀”的現象，也就是說兩個并發的事務，其中一個事務更改了另一個事物的查詢結果，這種查詢一般都是查詢一個聚合結果，例如上文中的count或者max、min等，這種問題會在下面場景中出現問題。

搶訂會議室
多人遊戲更新位置
唯一使用者名

上面我們列舉了事務并發可能産生的問題，下面我們介紹各種隔離級别所能解決的問題。

3.5 本章小結

事務用它的ACID特性，為使用者屏蔽了一些錯誤的處理。首先，原子性為使用者提供了一個可安全重試的環境，并且不會對相應的系統産生副作用。一緻性能夠在一定程度上讓程式滿足所謂的不變式，隔離性通過不同的隔離級别解決不同場景下由于事務并發導緻的不同現象，不同的隔離性解決的問題不同，開銷也不同，需要使用者按需決策，最後持久性讓使用者安心的把資料寫進我們設計的系統。

總體而言，事務保證的是不同操作之間的一緻性，一個極度完美的事務實作，讓使用者看上去就隻有一個事務在工作，每次隻執行了一個原子操作。是以，我們稱事務所解決的是操作的一緻性。這一章中，我們更多談論的還是單機範圍的事務。接下來，我們會把問題阈擴大，實際上分布式系統也有這樣的問題，并且分布式系統還有類似的複制滞後問題，導緻就算看似是操作的是一個對象，也存在不同的副本，這會使得我們所面對的問題更加複雜。下一章，我們重點介紹另一種一緻性問題以及解決。

4. 内部一緻性與共識

4.1 複制滞後性的問題

這裡我們首先回到上一篇中講的複制的滞後性，滞後性所帶來的的一個最直覺的問題就是，如果在複制期間用戶端發起讀請求，可能不同的用戶端讀到的資料是不一樣的。這裡面書中給了三種不同類型的一緻性問題。我們分别來看這些事例：

圖7 複制滞後問題

第一張圖給出的是一個使用者先更新，然後檢視更新結果的事例，比如使用者對某一條部落格下做出了自己的評論，該服務中的DB采用純的異步複制，資料寫到主節點就傳回評論成功，然後使用者想重新整理下頁面看看自己的評論能引發多大的共鳴或跟帖，這是由于查詢到了從節點上，是以發現剛才寫的評論“不翼而飛”了，如果系統能夠避免出現上面這種情況，我們稱實作了“寫後讀一緻性”（讀寫一緻性）。

上面是使用者更新後檢視的例子，下一張圖則展示了另一種情況。使用者同樣是在系統中寫入了一條評論，該子產品依舊采用了純異步複制的方法實作，此時有另一位使用者來看，首先重新整理頁面時看到了User1234的評論，但下一次重新整理，則這條評論又消失了，好像時鐘出現了回撥，如果系統能夠保證不會讓這種情況出現，說明系統實作了“單調讀”一緻性（比如騰訊體育的比分和詳情頁）。

圖8 複制滞後問題

除了這兩種情況外還有一種情況，如下圖所示：

圖9 複制滞後問題

這個問題會比前面的例子看上去更荒唐，這裡有兩個寫入用戶端，其中Poons問了個問題，然後Cake做出了回答。從順序上，MrsCake是看到Poons的問題之後才進行的回答，但是問題與回答恰好被劃分到了資料庫的兩個分區（Partition）上，對于下面的Observer而言，Partition1的Leader延遲要遠大于Partition2的延遲，是以從Observer上看到的是現有答案後有的問題，這顯然是一個違反自然規律的事情，如果能避免這種問題出現，那麼可稱為系統實作了“字首讀一緻性”。

在上一篇中，我們介紹了一可以檢測類似這種因果的方式，但綜上，我們可以看到，由于複制的滞後性，帶來的一個後果就是系統隻是具備了最終一緻性，由于這種最終一緻性，會大大的影響使用者的一些使用體驗。上面三個例子雖然代表了不同的一緻性，但都有一個共性，就是由于複制的滞後性帶來的問題。所謂複制，那就是多個用戶端甚至是一個用戶端讀寫多個副本時所發生的的問題。這裡我們将這類一緻性問題稱為“内部一緻性（記憶體一緻性）”，即表征由于多個副本讀寫的時序存在的資料不一緻問題。

4.2 内部一緻性概述

實際上，内部一緻性并不是分布式系統特有的問題，在多核領域又稱記憶體一緻性，是為了約定多處理器之間協作。如果多處理器間能夠滿足特定的一緻性，那麼就能對多處理器所處理的資料，操作順序做出一定的承諾，應用開發人員可以根據這些承諾對自己的系統做出假設。如下圖所示：

圖10 CPU結構

每個CPU邏輯核心都有自己的一套獨立的寄存器和L1、L2Cache，這就導緻如果我們在并發程式設計時，每個線程如果對某個主存位址中變量進行修改，可能都是優先修改自己的緩存，并且讀取變量時同樣是會先讀緩存。這實際上和我們在分布式中多個用戶端讀寫多個副本的現象是類似的，隻不過分布式系統中是操作粒度，而處理器則是指令粒度。在多處理器的記憶體一緻性中，有下面幾種常見的模型。

圖11 記憶體一緻性——百度百科

可以看到，這些一緻性限制的核心區分點就是在産生并發時對順序的限制，而用更專業一點的詞來說，線性一緻性需要的是定義“全序”，而其他一緻性則是某種“偏序”，也就是說允許一些并發操作間不比較順序，按所有可能的排列組合執行。

4.3 舉一反三：分布式系統中的内部一緻性

如下圖所示：

圖12 記憶體一緻性

分布式中的内部一緻性主要分為4大類：線性一緻性-->順序一緻性-->因果一緻性-->處理器一緻性，而從偏序與全序來劃分，則劃分為強一緻性（線性一緻性）與最終一緻性。

但需要注意的是，隻要不是強一緻的内部一緻性，但最終一緻性沒有任何的偏序保障。圖中的這些一緻性實際都是做了一些偏序的限制，比樸素的最終一緻性有更強的保證，這裡其他一緻性性的具體執行個體詳見《大資料日知錄》第二章，那裡面有比較明确對于這些一緻性的講解，本章我們重點關注強一緻。

4.4 我們口中的“強一緻性”——線性一緻性

滿足線性一緻性的系統給我們這樣一種感覺，這系統看着隻有一個副本，這樣我就可以放心地讀取任何一個副本上的資料來繼續我們的應用程式。這裡還是用一個例子來具體說明線性一緻性的限制，如下圖所示：

圖13 線性一緻性

這裡有三個用戶端同時操作主鍵x，這個主鍵在書中被稱為寄存器（Register），對該寄存器存在如下幾種操作：

write(x，v) =>r表示嘗試更新x的值為v，傳回更新結果r。
read(x) => v表示讀取x的值，傳回x的值為v。

如圖中所示，在C更新x的值時，A和B反複查詢x的最新值，比較明确的結果是由于ClientA在ClientC更新x之前讀取，是以第一次read(x)一定會為0，而ClientA的最後一次讀取是在ClientC成功更新x的值後，是以一定會傳回1。而剩下的讀取，由于不确定與write(x,1)的順序（并發），是以可能會傳回0也可能傳回1。對于線性一緻性，我們做了下面的規定：

圖14 線性一緻性

在一個線性一緻性系統中，在寫操作調用到傳回之前，一定有一個時間點，用戶端調用read能讀到新值，在讀到新值之後，後續的所有讀操作都應該傳回新值。（将上面圖中的操作做了嚴格的順序，及ClientA read->ClientB read->ClientC write-ClientA read->clientB read->clientAread）這裡為了清晰，書中做了進一步細化。在下面的例子中，又增加了一種操作：

cas(x, v_old, v_new)=>r 及如果此時的值時v_old則更新x的值為v_new，傳回更新結果。

如圖：每條數顯代表具體事件發生的時點，線性一緻性要求：如果連接配接上述的豎線，要求必須按照時間順序向前推移，不能向後回撥（圖中的read(x)=2就不滿足線性化的要求，因為x=2在x=4的左側）。

圖15 線性一緻性

4.5 什麼時候需要依賴線性化？

如果隻是類似論壇中評論的先後順序，或者是體育比賽頁面重新整理頁面時的來回跳變，看上去并不會有什麼緻命的危害。但在某些場景中，如果系統不是線性的可能會造成更嚴重的後果。

加鎖&&選主：在主從複制模型下，需要有一個明确的主節點去接收所有寫請求，這種選主操作一般會采用加鎖實作，如果我們依賴的鎖服務不支援線性化的存儲，那就可能出現跳變導緻“腦裂”現象的發生，這種現象是絕對不能接受的。是以針對選主場景所依賴的分布式鎖服務的存儲子產品一定需要滿足線性一緻性（一般而言，中繼資料的存儲也需要線性化存儲）。
限制與唯一性保證：這種場景也是顯而易見的，比如唯一ID、主鍵、名稱等等，如果沒有這種線性化存儲承諾的嚴格的順序，就很容易打破唯一性限制導緻很多奇怪的現象和後果。
跨通道（系統）的時間依賴：除了同一系統中，可能服務橫跨不同系統，對于某個操作對于不同系統間的時序也需要有限制，書中舉了這樣一個例子。

圖16 跨通道線性一緻性

比如使用者上傳圖檔，類似後端存儲服務可能會根據全尺寸圖檔生成低像素圖檔，以便增加使用者服務體驗，但由于MQ不适合發送圖檔這種大的位元組流，是以全尺寸圖檔是直接發給後端存儲服務的，而截取圖檔則是通過MQ在背景異步執行的，這就需要2中上傳的檔案存儲服務是個可線性化的存儲。如果不是，在生成低分辨率圖像時可能會找不到，或讀取到半張圖檔，這肯定不是我們希望看到的。

線性化不是避免競争的唯一方法，與事務隔離級别一樣，對并發順序的要求，可能會根據場景不同有不同的嚴格程度。這也就誕生了不同級别的内部一緻性級别，不同的級别也同樣對應着不同的開銷，需要使用者自行決策。

4.6 實作線性化系統

說明了線性化系統的用處，下面我們來考慮如何實作這樣的線性化系統。

根據上文對線性化的定義可知，這樣系統對外看起來就像隻有一個副本，那麼最容易想到的方式就是，幹脆就用一個副本。但這又不是分布式系統的初衷，很大一部分用多副本是為了做容錯的，多副本的實作方式是複制，那麼我們來看看，上一篇分享中那些常見的複制方式是否可以實作線性系統：

主從複制（部分能實作）：如果使用同步複制，那樣系統确實是線性化的，但有一些極端情況可能會違反線性化，比如由于成員變更過程中的“腦裂”問題導緻消費異常，或者如果我們使用異步複制故障切換時會同時違反事務特性中的持久化和内部一緻性中的線性化。
共識算法（線性化）：共識算法在後文會重點介紹，它與主從複制類似，但通過更嚴格的協商機制實作，可以在主從複制的基礎上避免一些可能出現的“腦裂”等問題，可以比較安全的實作線性化存儲。
多主複制（不能線性化）。
無主複制（可能不能線性化）：主要取決于具體Quorum的配置，對強一緻的定義，下圖給了一種雖然滿足嚴格的Quorum，但依然無法滿足線性化的例子。

圖17 Quorum無法實作線性一緻

實作線性化的代價——是時候登場了，CAP理論

在上一次分享中，我們講過，分布式系統中網絡的不可靠性，而一旦網絡斷開（P），副本間一定會導緻狀态無法達到線性一緻，這時候到底是繼續提供服務但可能得到舊值（A），還是死等網絡恢複保證狀态的線性一緻呢（C），這就是著名的CAP了。

但是其實CAP理論的定義面還是比較窄的，其中C隻是線性一緻性，P隻代表網絡分區（徹底斷開，而不是延遲），這裡面實際有相當多的折中，就可以完全滿足我們系統的需求了，是以不要迷信這個理論，還是需要根據具體的實際情況去做分析。

層層遞進——實作線性化系統

從對線性一緻性的定義我們可以知道，順序的檢測是實作線性化系統的關鍵，這裡我們跟着書中的思路一步步地來看：我們怎麼能對這些并發的事務定義出它們的順序。

a. 捕捉因果關系

與上一次分享的内容類似，并發操作間有兩種類型，可能有些操作間具有天然邏輯上的因果關系，還有些則沒法确定，這裡我們首先先嘗試捕獲那些有因果關系的操作，實作個因果一緻性。這裡的捕獲我們實際需要存儲資料庫（系統）操作中的所有因果關系，我們可以使用類似版本向量的方式（忘記的同學，可以回看上一篇中兩個人并發操作購物車的示例）。

b. 化被動為主動——主動定義

上面被動地不加任何限制的捕捉因果，會帶來巨大的運作開銷（記憶體，磁盤），這種關系雖然可以持久化到磁盤，但分析時依然需要被載入記憶體，這就讓我們有了另一個想法，我們是否能在操作上做個标記，直接定義這樣的因果關系？

最最簡單的方式就是建構一個全局發号器，産生一些序列号來定義操作間的因果關系，比如需要保證A在B之前發生，那就確定A的全序ID在B之前即可，其他的并發操作順序不做硬限制，但操作間在處理器的相對順序不變，這樣我們不但實作了因果一緻性，還對這個限制進行了增強。

c. Lamport時間戳

上面的設想雖然比較理想，但現實永遠超乎我們的想象的複雜，上面的方式在主從複制模式下很容易實作，但如果是多主或者無主的複制模型，我們很難設計這種全局的序列号發号器，書中給出了一些可能的解決方案，目的是生成唯一的序列号，比如：

每個節點各自産生序列号。
每個操作上帶上時間戳。
預先配置設定每個分區負責産生的序列号。

但實際上上面的方法都可能破壞因果關系的偏序承諾，原因就是不同節點間負載不同、時鐘不同、參照系不同。這裡我們的并發大神Lamport登場了，他老人家自創了一個Lamport邏輯時間戳，完美地解決了上面的所有問題。如下圖所示：

圖18 Lamport時間戳

初識Lamport時間戳，還是研究所學生分布式系統課上，當時聽得雲裡霧裡，完全不知道在說啥。今天再次拿過來看，有了上下文，稍微懂了一點點。簡單來說定義的就是使用邏輯變量定義了依賴關系，它給定了一個二進制組<Counter, NodeId>，然後給定了一個比較方式：

先比較Counter，Counter大的後發生（會承諾嚴格的偏序關系）。
如果Counter相同，直接比較NodeId，大的定義為後發生（并發關系）。

如果隻有這兩個比較，還不能解決上面的因果偏序被打破的問題，但是這個算法不同的是，它會把這個Node的Counter值内嵌到請求的響應體中，比如圖中的A，在第二次向Node2發送更新max請求時，會傳回目前的c=5，這樣Client會把本地的Counter更新成5，下一次會增1這樣使用Node上的Counter就維護了各個副本上變量的偏序關系，如果并發往兩個Node裡寫就直接定義為并發行為，用NodeId定義順序了。

d. 我們可以實作線性化了嗎——全序廣播

到此我們可以确認，有了Lamport時間戳，我們可以實作因果一緻性了，但仍然無法實作線性化，因為我們還需要讓這個全序通知到所有節點，否則可能就會無法做決策。

舉個例子，針對唯一使用者名這樣的場景，假設ABC同時向系統嘗試注冊相同的使用者名，使用Lamport時間戳的做法是，在這三個并發請求中最先送出的傳回成功，其他傳回失敗，但這裡面我們因為有“上帝視角”，知道ABC，但實際請求本身在發送時不知道有其他請求存在（不同請求可能被發送到了不同的節點上）這樣就需要系統做這個收集工作，這就需要有個類似協調者來不斷詢問各個節點是否有這樣的請求，如果其中一個節點在詢問過程中發生故障，那系統無法放心決定每個請求具體的RSP結果。是以最好是系統将這個順序廣播到各個節點，讓各個節點真的知道這個順序，這樣可以直接做決策。

假設隻有單核CPU，那麼天然就是全序的，但是現在我們需要的是在多核、多機、分布式的情況下實作這個全序的廣播，就存在這一些挑戰。主要挑戰個人認為是兩個：

多機
分布式

對于多機，實際上實作全序廣播最簡單的實作方式使用主從模式的複制，讓所有的操作順序讓主節點定義，然後按相同的順序廣播到各個從節點。對于分布式環境，需要處理部分失效問題，也就是如果主節點故障需要處理主成員變更。下面我們就來看看書中是怎麼解決這個問題的。

這裡所謂的全序一般指的是分區内部的全序，而如果需要跨分區的全序，需要有額外的工作

對于全序廣播，書中給了兩條不變式：

可靠發送：需要保證消息做到all-or-nothing的發送（想想上一章）。
嚴格有序：消息需要按完全相同的順序發給各個節點。

實作層面

我們對着上面的不變式來談談簡單的實作思路，首先要做到可靠發送，這裡有兩層含義：

消息不能丢
消息不能發一部分

其中消息不能丢意味着如果某些節點出現故障後需要重試，如果需要安全的重試，那麼廣播操作本身失敗後就不能對系統本身有副作用，否則就會導緻消息發送到部分節點上的問題。上一章的事務的原子性恰好就解決的是這個問題，這裡也就衍射出我們需要采用事務的一些思路，但與上面不同，這個場景是分布式系統，會發到多個節點，是以一定是分布式事務（耳熟能詳的2PC一定少不了）。

另外一條是嚴格有序，實際上我們就是需要一個能保證順序的資料結構，因為操作是按時間序的一個Append-only結構，恰好Log能解決這個問題，這裡引出了另一個常會被提到的技術，複制狀态機，這個概念是我在Raft的論文中看到的，假設初始值為a，如果按照相同的順序執行操作ABCDE最後得到的一定是相同的結果。是以可以想象，全序廣播最後的實作一定會用到Log這種資料結構。

e. 線性系統的實作

現在假設我們已經有了全序廣播，那麼我們繼續像我們的目标--線性化存儲邁進，首先需要明确一個問題，線性化并不等價于全序廣播，因為在分布式系統模型中我們通常采用異步模型或者半同步模型，這種模型對于全序關系何時成功發送到其他節點并沒有明确的承諾，是以還需要再全序廣播上做點什麼才真正能實作線性化系統。

書中仍然舉了唯一使用者名的例子：可以采用線性化的CAS操作來實作，當使用者建立使用者名時當且僅當old值為空。實作這樣的線性化CAS，直接采用全序廣播+Log的方式。

在日志中寫入一條消息，表明想要注冊的使用者名。
讀取日志，将其廣播到所有節點并等待回複（同步複制）。
如果表名第一次注冊的回複來自目前節點，送出這條日志，并傳回成功，否則如果這條回複來自其他節點，直接向用戶端傳回失敗。

而這些日志條目會以相同的順序廣播到所有節點，如果出現并發寫入，就需要所有節點做決策，是否同意，以及同意哪一個節點對這個使用者名的占用。以上我們就成功實作了一個對線性CAS的寫入的線性一緻性。然而對于讀請求，由于采用異步更新日志的機制，用戶端的讀取可能會讀到舊值，這可能需要一些額外的工作保證讀取的線性化。

線性化的方式擷取目前最新消息的位置，即確定該位置之前的所有消息都已經讀取到，然後再進行讀取（ZK中的sync()）。
在日志中加入一條消息，收到回複時真正進行讀取，這樣消息在日志中的位置可以确定讀取發生的時間點。
從保持同步更新的副本上讀取資料。

4.7 共識

上面我們在實作線性化系統時，實際上就有了一點點共識的苗頭了，即需要多個節點對某個提議達成一緻，并且一旦達成，不能被撤銷。在現實中很多場景的問題都可以等價為共識問題：

可線性化的CAS
原子事務送出
全序廣播
分布式鎖與租約
成員協調
唯一性限制

實際上，為以上任何一個問題找到解決方案，都相當于實作了共識。

兩階段送出

a. 實作

書中直接以原子送出為切入點來聊共識。這裡不過多說明，直接介紹兩階段送出，根據書中的描述，兩階段送出也算是一種共識算法，但實際上在現實中，我們更願意把它當做實作更好共識算法的一個手段以及分布式事務的核心實作方法（Raft之類的共識算法實際上都有兩階段送出這個類似的語義）。

圖19 兩階段送出

這個算法實際上比較樸素，就是兩個階段，有一個用于收集資訊和做決策的協調者，然後經過樸素的兩個階段：

協調者向參與者發送準備請求詢問它們是否可以送出，如果參與者回答“是”則代表這個參與者一定會承諾送出這個消息或者事務。
如果協調者收到所有參與者的區确認資訊，則第二階段送出這個事務，否則如果有任意一方回答“否”則終止事務。

這裡一個看似非常簡單的算法，平平無奇，無外乎比正常的送出多了個準備階段，為什麼說它就可以實作原子送出呢？這源于這個算法中的約定承諾，讓我們繼續拆細這個流程：

當啟動一個分布式事務時，會向協調者請求一個事務ID。
應用程式在每個參與節點上執行單節點事務，并将這個ID附加到操作上，這是讀寫操作都是單節點完成，如果發生問題，可以安全的終止（單節點事務保證）。
當應用準備送出時，協調者向所有參與者發送Prepare，如果這是有任何一個請求發生錯誤或逾時，都會終止事務。
參與者收到請求後，将事務資料寫入持久化存儲，并檢查是否有違規等，此時出現了第一個承諾：如果參與者向協調者發送了“是”意味着該參與者一定不會再撤回事務。
當協調者收到所有參與者的回複後，根據這些恢複做決策，如果收到全部贊成票，則将“送出”這個決議寫入到自己本地的持久化存儲，這裡會出現第二個承諾：協調者一定會送出這個事務，直到成功。
假設送出過程出現異常，協調者需要不停重試，直到重試成功。

正是由于上面的兩個承諾保證了2PC能達成原子性，也是這個範式存在的意義所在。

b. 局限性

協調者要儲存狀态，因為協調者在決定送出之後需要擔保一定要送出事務，是以它的決策一定需要持久化。
協調者是單點，那麼如果協調者發生問題，并且無法恢複，系統此時完全不知道應該送出還是要復原，就必須交由管理者來處理。
兩階段送出的準備階段需要所有參與者都投贊成票才能繼續送出，這樣如果參與者過多，會導緻事務失敗機率很大。

更為樸素的共識算法定義

看完了一個特例，書中總結了共識算法的幾個特性：

協商一緻性：所有節點都接受相同的提議。
誠實性：所有節點一旦做出決定，不能反悔，不能對一項提議不能有兩次不同的決議。
合法性：如果決定了值v，這個v一定是從某個提議中得來的。
可終止性：節點如果不崩潰一定能達成決議。

如果我們用這幾個特性對比2PC，實際上卻是可以認為它算是個共識算法，不過這些并不太重要，我們重點還是看這些特性會對我們有什麼樣的啟發。

前三個特性規定了安全性（Safety），如果沒有容錯的限制，直接人為指定個Strong Leader，由它來充當協調者，但就像2PC中的局限性一樣，協調者出問題會導緻系統無法繼續向後執行，是以需要有額外的機制來處理這種變更（又要依賴共識），第四個特性則決定了活性（Liveness）之前的分型中說過，安全性需要優先保證，而活性的保證需要前提。這裡書中直接給出結論，想讓可終止性滿足的前提是大多數節點正确運作。

共識算法與全序廣播

實際在最終設計算法并落地時，并不是讓每一條消息去按照上面4條特性來一次共識，而是直接采用全序廣播的方式，全序廣播承諾消息會按相同的順序發送給各個節點，且有且僅有一次，這就相當于在做多輪共識，每一輪，節點提出他們下面要發送的消息，然後決定下一個消息的全序。使用全序廣播實作共識的好處是能提供比單輪共識更高的效率（ZAB, Raft，Multi-paxos）。

讨論

這裡面還有一些事情可以拿出來做一些讨論。首先，從實作的角度看，主從複制的模式特别适用于共識算法，但在之前介紹主從複制時，但光有主從複制模型對解決共識問題是不夠的，主要有兩點：

主節點挂了如何确定新主
如何防止腦裂

這兩個問題實際上是再次用了共識解決。在共識算法中，實際上使用到了epoch來辨別邏輯時間，例如Raft中的Term，Paxos中的Balletnumber，如果在選舉後，有兩個節點同時聲稱自己是主，那麼擁有更新Epoch的節點當選。

同樣的，在主節點做決策之前，也需要判斷有沒有更高Epoch的節點同時在進行決策，如果有，則代表可能發生沖突（Kafka中低版本隻有Controller有這個辨別，在後面的版本中，資料分區同樣帶上了類似的辨別）。此時，節點不能僅根據自己的資訊來決定任何事情，它需要收集Quorum節點中收集投票，主節點将提議發給所有節點，并等待Quorum節點的傳回，并且需要确認沒後更高Epoch的主節點存在時，節點才會對目前提議做投票。

詳細看這裡面涉及兩輪投票，使用Quorum又是在使用所謂的重合，如果某個提議獲得通過，那麼投票的節點中一定參加過最近一輪主節點的選舉。這可以得出，此時主節點并沒有發生變化，可以安全的給這個主節點的提議投票。

另外，乍一看共識算法全都是好處，但看似好的東西背後一定有需要付出的代價：

在達成一緻性決議前，節點的投票是個同步複制，這會使得共識有丢消息的風險，需要在性能和線性一直間權衡（CAP）。
多數共識架設了一組固定的節點集，這意味着不能随意的動态變更成員，需要深入了解系統後才能做動态成員變更（可能有的系統就把成員變更外包了）。
共識對網絡極度敏感，并且一般采用逾時來做故障檢測，可能會由于網絡的抖動導緻莫名的無效選主操作，甚至會讓系統進入不可用狀态。

外包共識

雖然可以根據上面的描述自己來實作共識算法，但成本可能是巨大的，最好的方式可能是将這個功能外包出去，用成熟的系統來實作共識，如果實在需要自己實作，也最好是用經過驗證的算法來實作，不要自己天馬行空。ZK和etcd等系統就提供了這樣的服務，它們不僅自己通過共識實作了線性化存儲，而且還對外提供共識的語義，我們可以依托這些系統來實作各種需求：

線性化CAS
操作全序
故障檢測
配置變更

4.8 本章小結

本章花費了巨大力氣講解了分布式系統中的另一種一緻性問題，内部一緻性，這種問題主要是因為複制的滞後性産生，首先我們介紹了這種問題的起源，然後映射到分布式系統中，對不同一緻性進行分類。

對于裡面的強一緻性，我們進行了詳細的探讨，包括定義、使用場景以及實作等方面，并從中引出了像全序與偏序、因果關系的捕捉與定義（Lamport時間戳）、全序廣播、2PC最後到共識，足以見得這種一緻性解決起來的複雜性。

5. 再談分布式系統

至此，我們從複制這一主題出發，讨論了分布式系統複制模型、挑戰、事務以及共識等問題，這裡結合兩篇文章的内容，我嘗試對分布式系統給出更細節的描述，首先描述特性和問題，然後給出特定的解決。

與單機系統一樣，分布式系統同樣會有多個用戶端同時對系統産生各種操作。每個操作所涉及的對象可能是一個，也可能是多個，這些用戶端并發的操作可能會産生正确性問題。
為了實作容錯，分布式系統的資料一般會有多個備份，不同副本之間通過複制實作。
常見複制模型包括：

主從模式
多主模式
無主模式

而從時效性和線性一緻性出發，可分為：

同步複制
異步複制

異步複制可能存在滞後問題，會引發各種内部一緻性問題。
分布式系統相比單機系統，具有兩個獨有的特點。

部分失效
缺少全局時鐘

面對這麼多問題，如果一個理想的分布式資料系統，如果不考慮任何性能和其他的開銷，我們期望實作的系統應該是這樣的：

整個系統的資料對外看起來隻有一個副本，這樣使用者并不用擔心更改某個狀态時出現任何的不一緻（線性一緻性）。
整個系統好像隻有一個用戶端在操作，這樣就不用擔心和其他用戶端并發操作時的各種沖突問題（串行化）。

是以我們知道，線性一緻性和串行化是兩個正交的分支，分别表示外部一緻性中的最進階别以及内部一緻性的最進階别。如果真的實作這個，那麼使用者操作這個系統會非常輕松。但很遺憾，達成這兩方面的最進階别都有非常大的代價，是以由着這兩個分支衍生出各種的内部一緻性和外部一緻性。

用Jepsen官網對這兩種一緻性的定義來說，内部一緻性限制的是單操作對單對象可能不同副本的操作需要滿足時間全序，而外部一緻性則限制了多操作對于多對象的操作。這類比于Java的并發程式設計，内部一緻性類似于volatile變量或Atomic的變量用來限制實作多線程對同一個變量的操作，而外部一緻性則是類似于synchronize或者AQS中的各種鎖來保證多線程對于一個代碼塊（多個操作，多個對象）的通路符合程式員的預期。

圖20 一緻性

但是需要注意的是，在分布式系統中，這兩種一緻性也并非完全孤立，我們一般采用共識算法來實作線性一緻，而在實作共識算法的過程中，同樣可能涉及單個操作涉及多個對象的問題，因為分布式系統的操作，往往可能是作用在多個副本上的。也就是說，類似2PC這樣的分布式事務同樣會被用來解決共識問題（雖然書中把它也成為共識，但其實還是提供了一種類似事務原子性的操作），就像Java并發程式設計中，我們在synchronize方法中也可能會使用一些volatile變量一樣。

而2PC不是分布式事務的全部，可能某些跨分區的事務同樣需要用基于線性一緻性的操作來滿足對某個對象操作的一緻性。也就是說想完整的實作分布式的系統，這兩種一緻性互相依賴，彼此互補，隻有我們充分了解它們的核心作用，才能遊刃有餘地在實戰中應用這些看似枯燥的名詞。

6. 士别三日，當刮目相看--再看Kafka

了解完上面這些一緻性，我們再回過頭來看看Kafka的實複制，我們大緻從複制模型、内部一緻性、外部一緻性等角度來看。Kafka中與複制模式相關的配置大緻有下面幾個：

複制因子（副本數）
min.insync.replicas
acks

使用者首先通過配置acks先大體知道複制模式，如果ack=1或者0，則表示完全的異步複制；如果acks=all則代表完全的同步複制。而如果配置了異步複制，那麼單分區實際上并不能保證線性一緻性，因為異步複制的滞後性會導緻一旦發生Leader變更可能丢失已經送出的消息，導緻打破線性一緻性的要求。

而如果選擇ack=-1，則代表純的同步複制，而此時如果沒有min.insync.replicas的限制，那樣會犧牲容錯，多副本本來是用來做容錯，結果則是有一個副本出問題系統就會犧牲掉Liveness。而min.insync.replicas參數給了使用者做權衡的可能，一般如果我們要保證單分區線性一緻性，需要滿足多數節點正常工作，是以我們需要配置min.insync.replicas為majority。

而針對部分失效的處理，在實作複制時，kafka将成員變更進行了外包，對于資料節點而言，托管給Controller，直接由其指定一個新的主副本。而對于Controller節點本身，則将這個職責托管給了外部的線性存儲ZK，利用ZK提供的鎖于租約服務幫助實作共識以達成主節點選舉，而在高版本中，Kafka去掉了外部的共識服務，而轉而自己用共識算法實作Controller選主，同時中繼資料也由原來依賴ZK變為自主的Kraft實作的線性化存儲進行自治。

而在外部一緻性範疇，目前低版本Kafka并沒有類似事務的功能，是以無法支援多對象的事務，而高版本中，增加了事務的實作（詳見blog）。由于對象跨越多機，是以需要實作2PC，引入了TransactionCoordinator來承擔協調者，參考上面2PC的基本流程。

一個大緻的實作流程基本如下：首先向協調者擷取事務ID（後文統稱TID），然後向參與者發送請求準備送出，帶上這個TID，參與者現在本地做append，如果成功傳回，協調者持久化決策的内容，然後執行決策，參與者将消息真正寫到Log中（更新LSO，與HW高水位區分）。但是上文也講了2PC實際上是有一些問題的，首先2PC協調者的單點問題，Kafka的解決方法也比較簡單，直接利用自己單分區同步複制保證線性一緻性的特性，将協調者的狀态存儲在内部Topic中，然後當協調者崩潰時可以立刻做轉移然後根據Topic做恢複，因為Topic本身就單分區而言就是個線性存儲。

另外，就是2PC的協調者本質是個主從複制的過程，由于TransactionCoordinator本來就挂靠在Broker上，是以這個選舉依然會委托給Controller，這樣就解決了2PC中的比較棘手的問題。而對于事務的隔離級别，Kafka僅實作到了“讀已送出（RC）”級别。

7. 分布式系統驗證架構

在分布式領域有兩把驗證分布式算法的神器，其中一款是用于白盒模組化的工具TLA+TLA Homepage，對于TLA+，個人強烈推薦看一看Lamport老人家的視訊教程視訊教程（帶翻譯），或去看一看《Specifing Systems》。我們會知道，這個語言不光能定義分布式算法，應該說是可以定義整個計算機系統，如果掌握了使用數學定義系統的能力，可以讓我們從代碼細節中走出來，以狀态機的思維來看待系統本身，我們可能會有不一樣的感悟。TLA+的核心是通過數學中的集合論，數理邏輯和狀态搜尋來定義系統的行為。我們需要正确的對我們的系統或算法做抽象，給出形式化的規約，然後使用TLA+進行驗證。

另一款則是黑盒，其核心原理則是生成多個用戶端對一個存儲系統進行正常的讀寫操作并記錄每次操作的結果，在測試中間引入故障，最後根據檢測這些操作曆史是否符合各種一緻性所滿足的規定。我們簡單看下它的架構，然後本文将大緻示範它的使用方法。

圖21 Jepsen

Jepsen主要有下面幾個子產品構成：

DB Node（引擎本身的節點，存儲節點）。
Control Node 控制節點，負責生成用戶端，生成操作，生成故障等，其與DB Node通常是SSH免密的。
Client 用戶端用于進行正常讀寫操作。
Generator 用來生成計劃。
Nemesis 故障制造者。
Checker 用來進行最後的一緻性校驗。

我們團隊使用Jepsen測試了Kafka系統的一緻性，其中Kafka用戶端與服務端的配置分别為：同步複制（ack=-1），3複制因子（副本數），最小可用副本為2（min.insync.isr）。在該配置下，Jepsen内置的故障注入最後均通過了驗證。

8. 小結

我們的資料之旅到這裡就要告一段落了，希望大家通過我的文章了解常見分布式系統的核心問題，以及面對這些問題所謂的事務，一緻性和共識所能解決的問題和内在聯系，能夠在适當的時候合理的使用校驗工具或架構對我們的系統的正确性和活性進行校驗，這樣就達到兩篇系列文章的目的了。

分布式系統是個“大家夥”，希望今後能夠跟大家一起繼續努力，先将其“庖丁解牛”，然後再“逐個擊破”，真正能夠掌控一些比較複雜的分布式系統的設計。最後感謝團隊中的小夥伴們，能将這樣的思考系統化的産出，離不開組内良好的技術分享文化和濃厚的技術氛圍，也歡迎大家加入美團技術團隊。

Replication（下）：事務、一緻性與共識