數據庫通常有著完善的事務支持，但是局限于單機的存儲和性能，于是就出現了各種分布式解決方案。最近讀了《Designing Data-Intensive Applications》這本書，所以做一個總結，供大家做個參考，有什么不對的請大家指正，一起討論。

數據模型

數據模型可以說軟件開發中最重要的部分，因為影響著我們的思考方式、解題思路以及代碼的編寫方式。多數應用使用層層疊加的數據模型進行構建，對于每層數據模型的關鍵問題是：它如何用低一層的數據模型來表示。

多數應用程序開發都使用面向對象編程的編程語言來開發，所以一個數據模型是否能夠很好表示對象以及對象之間的關系就成為我們選擇的標準。

對象由各類屬性組成，對象的關系通常有一對多/多對一和多對多。

 

關系模型

關系模型使用表、行、字段分別表示一類實體的集合、一個實體以及一個實體的一個屬性；在其中一個實體的字段中存儲另一實體的Id標識來表示實體之間多對一的關系，使用單獨的關聯表存儲兩個實體的Id標識來表示實體建多對多的關系。

關系模型具有強模式，必須在寫數據前定義好，即寫模式，類似編程語言的靜態（編譯時）類型檢查。

下面的示例是Linked的一個簡歷的關系型表示：

 

文檔模型

采用類似JSON的格式存儲，存儲的內容是文檔型。利用JSON天然的嵌套關系可以靈活表示一對多的實體關系，當然通過存儲文檔的Id，也可以表示多對一和多對多的關系。

相對于關系模型，文檔模型減少了應用程序代碼和存儲層之間的阻抗不匹配，在一對多關系下，具有更好的局部性。

文檔模型具有讀時模式，對寫入沒有模式要求。類似編程語言的動態（運行時）類型檢查。

對于上面簡歷的例子，使用文檔模型的表示如下：

 

圖模型

圖模型強調是對象之間的連接，當應用是圍繞眾多對象連接以及對這些連接進行的查詢和計算時，就需要考慮使用圖模型的數據庫。

一個圖由頂點（表示的是實體）和邊（實體之間關系）組成，一個復雜的圖模型通常由數十億的頂點和千億的邊組成。

以下是社交網絡的一個示例：表示的是兩個人之間的以及居住地點。

 

每種數據模型都有其對應的查詢語言，關系型使用SQL，而圖模型也有相應的查詢語言來描述圖模型的特點，但是還沒有形成業界標準。

 

 

存儲引擎

上面我們熟悉了數據模型，但是了解數據內部的存儲和檢索原理，對于我們設計和開發應用以及數據庫的選型也是非常有幫助的。

數據庫的主要功能是存儲數據以及后續進行查詢和更新，目前主要有兩大類數據庫：傳統關系型數據庫（面向頁面 page-oriented） 和 NoSQL數據庫（基于日志結構log-structured）。

面向頁面

B樹是幾乎是數據庫標準的索引實現，B數將數據庫分解成固定大小的塊或頁面，通常在4k-32k范圍，一次只能讀取或寫入一個頁面。這種設計更接近與底層的硬件，因為磁盤也是由固定大小的塊組成的。

每個頁面都可以使用地址來標識，一個頁面引用另一個頁面，類似于指針，但是在磁盤而不是在內存中，如圖所示：

 

在B樹的頁面中對子頁面的引用的數量稱為分支因子，分支因子取決于頁面大小和索引key的大小，分支因子越大越好。（分支因子為500的4KB頁面的四級樹可以存儲多大256TB）

數據查詢時，從根頁面（通常緩存在內存）出發，根據頁面引用尋找滿足條件范圍的頁面，一直到葉子節點。

數據更新時，定位到葉子結點，用新數據覆蓋磁盤的頁面。

數據插入和刪除時，會涉及到頁面的拆分和合并，來保持B樹的平衡

為了保證數據查詢和寫入的高性能，數據庫通常會對頁面數據進行內存緩存，當數據有更新時，不會立即更新磁盤數據，而是先更新內存緩存的頁面數據，同步追加寫入WAL日志（write-ahead-log），異步將內存中的臟頁刷到磁盤上（將磁盤隨機寫變為順序寫）。當數據庫崩潰后恢復時，這個日志用來是B樹恢復到一致的狀態。

日志結構

基于日志結構的存儲模式，每次數據新增或更新時，僅僅將數據追加到特定日志文件中，當文件超過一定大小時，則打開一個新的文件寫入。

每個日志結構存儲段都是一系列鍵值對，但是為了后續便于查詢數據，要求鍵值對在文件中按照鍵排序，這種排序的字符串表(Sorted String Table)稱為SSTable。

為了保證日志文件保持在一定的個數，多個文件段進行合并（歸并算法），當出現多個同一鍵值時，用新的值覆蓋老的，保證一個合并段同一個鍵出現一次。

內存中維護者鍵到日志文件的索引，該索引是稀疏的，每幾千個字節的段文件就有一個鍵就足夠了，因為幾千字節可以很快被掃描。（可以將部分記錄分組到塊，壓縮寫入磁盤）

 

如何構建和維護SSTable呢（保證按照鍵排序存儲）

• 寫入數據時（新增、刪除、更改），將其添加到內存中的平衡樹結構（如紅黑樹），這個內存樹稱為內存表（memtable);
• 為了避免丟失數據，寫入內存表的同時會通過追加的方式寫入WAL日志（數據庫崩潰恢復時使用）；
• 當內存表大于某個閾值（通常為幾兆字節）時，將其作為SSTable文件寫入磁盤。新的SSTable文件成為數據庫的最新部分。

數據查詢時，首先嘗試在內存表中查找，然后在多個文件段中進行查找。（通過合并文件段使其維持在一定的個數，保證查找效率）

這種基于合并和壓縮排序文件原理的存儲引擎通常被稱為LSM存儲引擎。

當查找不存在的鍵時，LSM樹算法可能會很慢。為了優化這種訪問，通常使用額外的Bloom過濾器。

LSM樹的基本思想

保存一系列在后臺合并的SSTables，即使數據集比可用內存大得多，仍能繼續工作。由于數據按序存儲，因此可以高效地執行范圍查詢（掃描所有高于某些最小值和最高值的所有鍵），并且磁盤寫入時連續的，所以可以支持非常高的寫入吞吐量。

事務

在數據庫系統中，會遇到各種問題：

• 數據庫軟件、硬件可能在任意時刻故障（包括寫操作進行一半時）
• 應用程序任何時刻都可能崩潰（包括一系列操作的中間）
• 網絡中斷會切斷應用與數據庫的連接，或數據庫之間的連接
• 多個應用可能會同時寫入數據庫，覆蓋彼此的修改
• 應用可能會讀取到無意義的數據，因為數據只更新了一部分
• 應用質檢的競爭條件可能導致各種非預期結果

事務一直是簡化這些問題的首選機制。事務是應用程序將多個讀寫操作組合成一個邏輯單元的一種方式。從概念上講，事務中的所有讀寫操作被視為單個操作來執行：整個事務要么成功，要么失敗后回滾。如果失敗，應用可以安全地重試。對于事務來說，應用的錯誤處理簡單多了，不用擔心部分失敗的情況了。

事務提供的安全保障，由ACID來描述。即原子性Atomicity,一致性Consistency，隔離性Isolation，持久性Durability，旨在為數據庫中的容錯性建立精確的術語。

單對象 vs 多對象

事務通常被理解為，將對多個對象上的多個操作合并為一個執行單元的機制。但許多分布式數據庫只提供了單對象的原子性和隔離性（原子性通過同步寫日志實現崩潰恢復；隔離性通過每個對象上鎖實現單線程訪問），以及更復雜的原子操作，如自增 和 CAS。所以要注意這一點，看是否滿足自己的應用場景。

多對象事務，除了要處理復雜原子性和隔離性，分布式場景下，還會涉及到跨分區（不能分區可能在不同的機器上），即分布式事務。

隔離級別

如果兩個事務不觸及相同的數據，它們可以安全地并行執行，因為兩者都不依賴對方。當一個事務讀取另一個事務同時修改的數據，或者兩個事務試圖同時修改相同的數據，并發問題才會出現。

并發bug很難通過測試找到，因為這樣的錯誤只有在特殊時機下才會觸發，很難重現。出于這個原因，數據庫一直試圖通過提供事務隔離來隱藏應用開發者的并發問題。事務隔離級別越強越能夠避免發生的并發問題，比如可序列化保證事務的效果與串行執行是一樣的，但這意味著并發性能的犧牲。所以數據庫系統通常使用較弱的隔離級別，來防止一部分并發問題，而不是全部，所以了解這些對于開發出正確的應用非常重要。

 

 

 

 

 

臟寫

臟寫是指一個事務覆蓋另一個事務未提交的數據，現有的隔離級別都會保證沒有臟寫。數據庫通常使用行鎖來防止臟寫。

臟讀

臟讀是指一個事務寫了部分數據，未提交，這是另一個事務讀取到了這部分未提交的數據。

不可重復讀

同一個事務兩次讀取的數據（讀偏差） 或者 讀取的記錄數（幻讀）不一致

丟失更新

兩個事務同時讀取數據，并進行更新，兩個事務都更新成功，更新邏輯都是基于原先讀取的值，但是事務提交會改變先前讀取的值，導致丟失更新。典型的場景就是 讀 -> 改 -> 寫。

寫偏差

可以將寫入偏差視為丟失更新問題的一般化。如果兩個事務讀取相同的對象，然后更新其中的一些對象（不同的事務可能更新不同的對象），則可能發生寫入偏差。

讀已提交

讀已提交提供兩種保證

• 從數據庫讀時，只能看到已經提交的數據（沒有臟讀）
• 寫入數據庫時，只能覆蓋已經寫入的數據（沒有臟寫）

可重復讀/快照隔離

支持快照隔離的數據庫保留了一個對象的不同的提交版本，因為各種正在進行的事務可能需要看到數據庫在不同時間點的狀態。這種技術被稱為多版本并發控制（MVCC，multi-version concurrency control）。

當一個事務開始，它被賦予一個唯一個的，永遠增長的事務ID（txid）。每當事務向數據庫寫入任何內容時，它所寫入的數據都會被標記上寫入者的事務ID。

一個事務能查到一個對象，滿足以下兩個條件：

• 讀事務開始時，創建該對象的事務已經提交
• 對象未被標記為刪除，或如果被標記為刪除，請求刪除的事務在讀事務開始時尚未提交

對于丟失更新和有數據交叉的寫偏差，數據庫可以結合快照隔，可以自動檢測到丟失更新，中止相應的事務。但是MySQL/InnoDB的可重復讀并不會檢測丟失更新。有些作者認為，數據能防止丟失更新才能稱得上快照隔離，所以這種定義下，MySQL并不提供快照隔離。

MySQL/InnoDB可重復讀隔離級別下，可以使用 鎖定讀 （select for update）或者 比較并設置CAS 來避免丟失更新。

需要注意的是，如果數據庫允許where字句從舊快照中讀取，則此語句可能無法防止丟失更新，因為即使發生了另一個并發寫入，where條件也可能是真的。

序列化

但對于寫入數據無交叉的寫偏差，只能通過序列化的隔離級別來避免，但是可以在應用層面通過 物化沖突的方式，人為的在數據庫中引入一個鎖對象。

序列化隔離級別有三種實現方式：

• 字面意義的串行順序執行事務
• 兩階段鎖定（2PL，two-phase locking），通過對讀操作對象加共享鎖，對寫操作對象加獨占鎖實現，共享鎖可以升級為獨占鎖。共享鎖之間不互斥，共享鎖與獨占鎖 以及 獨占鎖之間互斥。同時數據庫會自動檢測事務之間的思索，并中止一個。兩階段是一種所謂的悲觀并發控制機制。
• 樂觀并發控制技術，可序列化的快照隔離SSI（serializable snapshot isolation），是一種樂觀的并發控制機制，讀寫數據時并不加鎖，而是在事務提交時，通過特定的算法檢測寫入之間的序列化沖突，并確定要中止哪些事務。好處是讀和寫不相互阻塞，只讀查詢運行在一致的快照上，對于讀取繁重的場景非常有吸引力。但是中止率顯著影響SSI整體的表現。長時間讀取和寫入數據的事務很可能會發生沖突并中式，因為SSI要求同時讀寫的事務盡量短。

分布式事務

在多對象事務中，如果不同對象存在不同的分區中，則就需要處理分布式事務。提到分布式事務，就不得不介紹兩階段提交，兩階段提交是分布式事務的基本思想。

兩階段提交

兩階段提交2PC（two-phase commit）是一種用于實現跨多個節點的原子事務提交的算法。可以在數據庫內部使用，也可以以XA事務的形式對應用可用。

 

兩階段提交引入了協調者的角色，整體分為兩個階段，具體的過程如下：

• 當應用想要啟動一個分布式事務時，它向協調者請求一個全局唯一的事務ID。
• 應用在每個參與者啟動單節點事務，每個單節點事務都帶上這個全局事務ID。所有的讀寫都是在單節點事務中各自完成的。如果這個階段出現任何問題，則協調者或任何參與者都可以中止。
• 當應用準備提交時，協調者向所有參與者發送一個準備請求，并帶上全局事務ID。如果任意一個請求失敗或超時，則協調者向所有參與者發送針對該事務ID的中止請求。
• 參與者收到準備請求時，需要確保在任何情況下都的確可以提交事務。這包括所有事務數據寫入磁盤（出現故障，電源故障，或磁盤空間不足都不能是稍后拒絕提交的理由）以及檢查是否存在任何額沖突或違反約束。一旦作出承諾，就不允許反悔。
• 當協調者收到所有準備請求的答復時，會就提交或中止事務作出明確的決定（只有所有參與者贊成的情況下才會提交）。協調者必須吧這個決定寫到磁盤的事務日志中。
• 一旦協調者的決定落盤，提交或放棄請求會發送給所有參與者。如果請求超時或失敗，協調者必須永遠保持重試。

兩階段提交固有的成本：由于崩潰恢復所需的強制刷盤以及額外的網絡往返，另外整個過程會進行資源的鎖定。

Percolator

Percolator是由google公司開發的、為大數據集群進行增量處理更新的系統，主要用于google網頁搜索索引服務。使用基于Percolator的增量處理系統代替原有的批處理索引系統后，Google在處理同樣數據量的文檔時，將文檔的平均搜索延時降低了50%。

 

 

Percolator 是一個無中心化（沒有協調者）的兩階段提交，基于BigTable的單行事務，實現了跨行的事務引擎。另外借助BigTable的多時間戳版本，可以實現快照隔離級別。

Percolator依賴中心的授時器，沒有單點 Coordinator 的角色，交由所有客戶端來協調上鎖協議，但是趕上崩潰鎖會泄露。Percolator 選擇了惰性地回收泄露的鎖：其他客戶端在 Get() 到這行數據時，如果遇到鎖，則選擇等待退避重試，或者清理鎖。

但是由于Percolator使用樂觀鎖檢測機制，對于熱點數據的并發更新不友好。我覺得這一點可以通過在Percolator之上實現悲觀鎖機制來解決。

分區

分區（partitions）也叫分片（sharding），是將數據集進行拆分成多個分區，每個分區存儲在不同的機器上，擴展了整體的存儲量，提高了寫入和讀取的性能。但也帶來了新的困難，數據庫要支持跨分區的寫入和讀取。

分區方式

分區的目標是將數據和查詢負載均勻的分布在各個節點上。如果分區是不公平的，或者沒有考慮熱點數據，那么一些分區比其他分區有更多的數據或查詢，我們稱之為偏斜（skew）。數據分區通常基于Key進行拆分，在考慮數據偏斜的情況，要根據數據庫的特定的分區算法，特別注意Key的設計。

根據Key的范圍分區 為每個分區指定一塊連續的Key范圍，分區Key的邊界一般由數據庫自動選擇。好處是范圍掃描非常簡單。但是如果Key的設計不合理，會到熱點數據，影響查詢效率。

根據Key的散列分區 通過一個散列函數對Key進行計算后，再進行分區。這樣可以消除偏斜和熱點的風險，但是失去了原有Key的范圍查詢的屬性。

有些數據庫，如Cassandra，采取了折中的策略，使用多個列組成的復合主鍵來聲明。鍵中只有第一列會作為散列的依據，而其他列則被用作Cassandra的SSTables中排序數據的連接索引。盡管查詢無法在復合主鍵的第一列中按掃描掃表，但如果第一列已經指定了固定值，則可以對該鍵的其他列執行有效的范圍掃描。組合索引的方法為一對多關系提供了一個優雅的數據模型。

索引構建

上面我們討論了主鍵的分區策略，實際情況上輔助索引/二級索引也是很有必要的，特別是在關系模型中。

輔助索引的構建方式有兩種：本地索引和全局索引

 

本地索引 文檔分區所以，在這種索引方法中，每個分區是完全獨立的，每個分區維護自己的二級索引，僅覆蓋該分區中的文檔。當數據寫入時（添加、刪除、更新），只需要處理分區內數據的索引更新。數據查詢時，則需要將查詢發送到所有的分區，并合并所有返回的結果。

這種查詢分區數據庫的方法有時被稱為分散/聚集（scatter/gather），并且可能會是二級索引上的讀取查詢相當昂貴。即使并行查詢分區，已容易導致尾部延遲放大。MongoDB、Cassandra、ElasticSearch、SolrCloud都是使用這種文檔分區二級索引。

 

全局索引 關鍵詞分區，這種索引方法跟主鍵分區的方式是一樣的。相對于文檔分區索引，讀取更有效率，不需要分散/聚集所有分區，客戶端只需要向包含關鍵詞的分區發出請求。缺點在于寫入速度較慢且較為復雜，因為寫入單個文檔可能會影響索引的多個分區。

理想情況下，索引總是最新的。寫入數據庫的每個文檔都會立即反映在索引中。在基于關鍵詞的全局索引中，這需要跨分區的分布式事務，并不是所有的數據庫都支持。在實踐中，對全局二級索引的更新通常是異步的。

分區再平衡

隨著數據集大小增加、查詢吞吐量的增加，需要更多的機器來處理。這些都需要數據和請求從一個節點移動到另一個節點，這一過程稱為再平衡（reblancing）。

再平衡通常要滿足以下幾點要求：

• 再平衡之后，負載（數據存儲、讀取和寫入請求）應該在集群中的節點之間公平地共享
• 再平衡發生時，數據庫應該繼續接受讀取和寫入
• 節點之間只移動必須的數據，以便快速再平衡，并減少網絡和磁盤I/O負載

平衡策略可以分為幾種：固定數量的分區、動態數量的分區和按節點比例分區

固定數量的分區 創建比節點更多的分區，并為每個節點分配多個分區。如果一個節點被添加到集群中，新節點可以從當前每個節點中竊取一些分區，直到分區再次公平分配。ElasticSearch使用這種方式分區策略。

只有分區在節點間移動，分區的數量不會改變，鍵所對應的分區也不會改變，唯一改變的是分區所在的節點。這種變更不是實時的（網絡上傳輸數據需要時間），傳輸過程中，原有分區仍然會接手讀寫請求。

分區的數量通常在數據庫第一次建立時確定，之后不會改變。每個分區包含了總數據量固定比率的數據，因此每個分區的大小與集群中的數據總量成比例增長。如果數據集的總大小難以預估，選擇正確的分區數是困難的。分區太大，再平衡和節點故障恢復變得昂貴；分區太小，則會產生太多的開銷。

動態數量的分區 對于使用鍵范圍進行分區的數據庫，具有固定邊界的固定數量的分區將非常不方便：如果出現邊界錯誤，則可能會導致某些分區的沒有數據。按鍵范圍進行分區的數據庫通常會動態創建分區。

當分區增長到超過配置的大小時，會被拆分成兩個分區，每個分區約占一半的數據。動態分區的優點是分區數量適應總數據量，能夠平衡各方面的開銷。HBase和MongoDB采用的就是這種策略。

數據集開始時很小，直到達到第一個分區的分隔點，所有寫入操作都必須由單個節點處理，而其他節點處于空閑狀態。為了解決這個問題，HBase和MongoDB允許在一個空的數據庫上配置一組初始分區（預分隔，pre-splitting）。在鍵范圍分區的情況下，預分隔需要提前知道鍵時如何分配的。

按照節點比例分區 分區數與節點數量成正比，即每個節點具有固定數量的分區。每個分區的大小與數據集大小成比例的增長。當增加節點時，隨機選擇固定數量的現有分區進行拆分，然后占有這些拆分分區中的每個分區的一半。

請求路由

現在我們已經數據集分割到多個節點上運行的多個分片上，客戶端發起請求時，如何知道連接哪個結點。隨著分區再平衡，分區對節點的分配也發生變化。

 

不僅限于數據庫，這個問題可以概括為服務發現（service discovery），通常有以下三種方案：

• 允許客戶端連接任何節點，如果該節點恰巧擁有請求的分區，則直接處理該請求；否則將請求轉發到適當的節點，接收結果并返回給客戶端。
• 客戶端發送請求到路由層，它決定了應該處理請求的節點，并相應的轉發。
• 客戶端知道分區和節點的分配，直接連接到適當的節點。

以上問題的關鍵在于：做出路由決策的組件如何了解分區-節點之間的分配關系變化？這是一個具有挑戰性的問題，因為需要所有的參與者達成一致。

很多分布式系統都依賴于一個獨立的協調服務，比如ZooKeeper來跟蹤集群元數據。

• 每個節點在ZooKeeper上注冊自己，ZooKeeper維護分區到節點的可靠映射
• 路由層可以在ZooKeeper訂閱此信息，當分區分配發生變化能實時感知

 

復制

復制意味著在通過網絡連接的多臺機器上保留相同數據的副本，復制數據能帶來以下的好處：

• 提高可用性，即使系統的一部分出現故障，系統也能繼續工作
• 擴展可以接受讀請求的機器數量，從而提高讀取吞吐量
• 使得數據與用戶再地理上接近，從而減少延遲

復制的困難之處在于處理復制數據的變更。目前流行有三種變更復制算法：單領導者（single leader），多領導（multi leader）和無領導者（leaderless），幾乎所有的分布式數據庫都使用這三種方法之一。

單領導者復制過程：

• 每一次向數據庫的寫入操作都需要傳播到所有的副本上，否則副本就會包含不一樣的數據。最常見的解決方案被稱為基于領導者的復制 或 主從復制
• 副本之一被指定為領導者（或主庫），當客戶端要向數據庫寫入時，它必須發給領導者，領導者會將新數據寫入其本地存儲；
• 其他副本被稱為追隨者（只讀副本、從庫），會同步主庫的變更日志，按照主庫相同的順序寫入
• 當客戶端從數據庫讀取數據時，可以向領導者或追隨者查詢

同步 or 異步

復制系統的一個重要細節是 復制 是 同步發生 還是 異步發生。同步復制會使得數據寫入時間變長，而異步復制會使得副本之間的數據不一致，客戶端可能會讀取到歷史的數據，并且在主庫故障時有可能會丟失數據。所以復制系統的核心就是如何讓副本保持一致，并且在主庫故障時能夠自動切換。

一致性模型

 

一致性模型（consistency model）實質上是進程和數據存儲存儲之間的一個約定。即，如果進程同意遵守某些規則，那么數據存儲將正常運行。正常情況下，一個進程在一個數據項執行讀操作時，它期待該操作返回的是該數據在其最后一次寫操作之后的結果。

在沒有全局時鐘的情況下，精確地定義哪次寫操作時最后一次寫操作是十分困難的。作為替代的方法，我們需要提供其他的定義，因此產生了一系列的一致性模型。每種模型都有效地限制了在一個數據項上執行一次讀操作所應返回的值。

注意：不將數據庫事務的一致性與其混淆，分布式副本的一致性指的是單個對象的寫入和讀取。

以數據為中心

線性一致性

線性一致性也稱為嚴格一致性（Strict Consistency）或者原子一致性（Atomic Consistency），需要滿足以下兩個條件：

• 任何一次讀都能讀取到某個數據最近的一次寫的數據。
• 所有進程看到的操作順序都跟全局時鐘下的順序一致。

線性一致性的想法是讓一個系統看起來只有一個數據副本，而且所有的操作都是原子性的。應用不用擔心多個副本帶來諸多問題，是一個完美的理想模型，作為其他模型的參考（最強一致性模型）。

在線性一致性的數據存儲中不存在并發操作：必須有且僅有一條時間線，所有的操作都在這條時間線上，構成一個全序關系。

順序一致性

順序一致性最早出現在Shared-Memory Multi-Processor System單機模型中，為程序員提供了極強的內存可見性保證。順序一致性內存模型有兩大特性：

• 任何執行的結果都與所有處理器的操作按某種順序執行的相同。
• 每個單獨的處理器的操作順序均按照其程序指定的順序。
• 所有操作都必須相對于每個其他處理器立即或原子執行（立即可見）。

 

在時間順序上，C1發生于B2之后。對于線性一致性來說，C1一定在B2之后，但是對于順序一致性B2可以發生在C1之后。

順序一致性可能會產生不確定的結果。這是因為在程序的不同運行期間，處理器之間的順序操作的順序可能會有所不同。

對于順序一致性來說，它要找到一個合法的順序執行過程，該執行過程要保留線程/進程內部原有的順序

對于線性一致性來說，它也是要找到一個合法的順序執行過程。但是這個順序執行過程，不僅要保留線程/進程內部的先后順序，還要保留線程/進程之間的操作的先后順序。

線性一致性可以定義為具有實時約束（real-time constraint）的順序一致性。

個人理解，在分布式副本的領域中，不太可能找到 除了時序之外，各個進程能夠一致認可的順序。所以在分布式副本領域參考意義不大，更容易造成疑惑。

因果一致性

相對于線性一致性保證讀寫具有全局順序，而因果一致性只需要保證具有相互依賴的讀寫操作保持相同的順序即可。實際上因果一致性是性能和可用最高的強一致性模型。

因果一致性實現的難點在于如何定義和捕獲因果關系，你需要知道哪個操作發生在哪個操作之前（happen before）。但是這種因果關系更多是來自上層應用，底層存儲是無法感知的，所以跟蹤所有的因果關系是不及實際的。

因果關系的操作在時序上一定是有先后，所以通過全序的的序列化或時間戳（邏輯時鐘）來排序操作，這樣所有的操作都有了時間上的因果先后關系。所以線性一致性是所有操作都滿足因果一致性（即使大部分操作沒有依賴關系）。

最終一致性

最終一致性不能算是一致性模型，沒有任何一致性保證，只是說在沒有更新的情況下，副本之間會在一定時間內保持一致。因為由于網絡延遲的存在，應用任何時候都可能讀取到不一致的數據。可以說是可接受的最弱的一致性模型。

以客戶端為中心

上面討論的以數據存儲為視角的一致性，在因果一致性以及更強的一致性模型中，從客戶端而言是不會發生預料之外的讀寫問題的。但是在更弱的一致性模型而言，出現各種讀寫問題。

以客戶端為中心的一致性為單一客戶端提供一致性保證，保證該客戶端對數據存儲的訪問的一致性，但是它不為不同客戶端的并發訪問提供任何一致性保證。

以客戶端為中心的一致性包含了四種模型：

• 單調讀一致性（Monotonic-read Consistency）：如果一個進程讀取數據項 x 的值，那么該進程對于 x 后續的所有讀操作要么讀取到第一次讀取的值要么讀取到更新的值。即保證客戶端不會讀取到舊值。
• 單調寫一致性（Monotonic-write Consistency）：一個進程對數據項 x 的寫操作必須在該進程對 x 執行任何后續寫操作之前完成。即保證客戶端的寫操作是串行的。
• 讀寫一致性（Read-your-writes Consistency）：一個進程對數據項 x 執行一次寫操作的結果總是會被該進程對 x 執行的后續讀操作看見。即保證客戶端能讀到自己最新寫入的值。
• 寫讀一致性（Writes-follow-reads Consistency）：同一個進程對數據項 x 執行的讀操作之后的寫操作，保證發生在與 x 讀取值相同或比之更新的值上。即保證客戶端對一個數據項的寫操作是基于該客戶端最新讀取的值。

但是真實情況是，由于服務器負載均衡以及服務器故障的存在，會導致客戶端會話會發生轉移，因此基于客戶端訪問的一致性模型是不靠譜的。

共識協議

Lamport時間戳

我們知道分布式系統中，各個機器擁有相同的時鐘（全局時鐘）是不太可能的。1978年Lamport在一篇論文中提出了一種邏輯時間戳，來解決分布式系統中區分事件發生的時序問題。這篇論文是分布式系統領域被引用最多的論文之一。

 

 

Lamport時間戳就是兩者的簡單結合：時間戳/計數器 + 節點ID，規則如下：

• 每個事件對應一個Lamport時間戳，初始值為0
• 如果事件在節點內發生，本地進程中的時間戳加1
• 如果事件屬于發送事件，本地進程中的時間戳加1并在消息中帶上該時間戳
• 如果事件屬于接收事件，本地進程中的時間戳 = Max(本地時間戳，消息中的時間戳) + 1
• 事件的順序按照時間戳排序，時間戳相同則按照節點ID大小排序

上圖，ABC節點的所有事件的全序關系如下：

 

Lamport時間戳背后的思想是：兩個事件可以建立時序（因果）關系的前提是兩個事件之間是否發生過信息傳遞。因此Lamport時間戳只保證因果關系（偏序）的正確性，不保證絕對時序的正確性。

全序廣播

Lamport時間戳通過消息的傳遞來確定事件的時序關系，引出了全序廣播（在節點間交換消息的協議）。全序廣播需要滿足兩個安全屬性：

• 可靠交付 （reliable delivery），沒有消息丟失：如果消息被傳遞到一個節點，它將傳遞到所有節點
• 全序交付（total ordered delivery），消息以相同的順序傳遞給每個節點

全序廣播正是數據庫復制所需要的：如果每個消息都代表一次數據庫寫入，且每個副本都按照相同的順序處理相同的寫入，那么副本相互保持一致（除了臨時的復制延遲，可以將讀操作也作為消息，來實現一致讀）。這個原理被稱為狀態機復制（state machine replication）。

因為數據庫的寫入和讀取操作都是通過消息交互達成一致，依據Lamport時間戳，所有的操作是全序的，因此可以實現線性一致性存儲。

Raft協議

Raft是一種共識算法，旨在使其易于理解。 它在容錯和性能上與Paxos等效。 不同之處在于它被分解為相對獨立的子問題，并且干凈地解決了實際系統所需的所有主要部分，實際將上面的 全序廣播/狀態機復制 的工程化。

 

 

Raft協議動畫演示：thesecretlivesofdata.com/raft/

在Raft集群里，服務器可能會是這三種身份其中一個：領導（leader）、追隨者（follower），或是候選人（candidate）。在正常情況下只會有一個領導，其他都是追隨者。而領導會負責所有外部的請求，如果不是領導的機器收到時，請求會被導到領袖。

Raft將問題拆成數個子問題分開解決：

• 領導選舉（Leader Election）
• 日志復制（Log Replication）
• 集群成員變化 （Cluster membership changes）
• 安全性（Safety）