[[333060]]

1 概念

1.1 模型

節(jié)點(diǎn)

在具體的工程項(xiàng)目中，一個(gè)節(jié)點(diǎn)往往是一個(gè)操作系統(tǒng)上的進(jìn)程。在本文的模型中，認(rèn)為節(jié)點(diǎn)是一個(gè)完整的、不可分的整體，如果某個(gè)程序進(jìn)程實(shí)際上由若干相對(duì)獨(dú)立部分構(gòu)成，則在模型中可以將一個(gè)進(jìn)程劃分為多個(gè)節(jié)點(diǎn)。

異常

• 機(jī)器宕機(jī)：機(jī)器宕機(jī)是最常見的異常之一。在大型集群中每日宕機(jī)發(fā)生的概率為千分之一左右，在實(shí)踐中，一臺(tái)宕機(jī)的機(jī)器恢復(fù)的時(shí)間通常認(rèn)為是24 小時(shí)，一般需要人工介入重啟機(jī)器。
• 網(wǎng)絡(luò)異常：消息丟失，兩片節(jié)點(diǎn)之間彼此完全無法通信，即出現(xiàn)了“網(wǎng)絡(luò)分化”;
• 消息亂序，有一定的概率不是按照發(fā)送時(shí)的順序依次到達(dá)目的節(jié)點(diǎn)，考慮使用序列號(hào)等機(jī)制處理網(wǎng)絡(luò)消息的亂序問題，使得無效的、過期的網(wǎng)絡(luò)消息不影響系統(tǒng)的正確性;
• 數(shù)據(jù)錯(cuò)誤;不可靠的TCP，TCP 協(xié)議為應(yīng)用層提供了可靠的、面向連接的傳輸服務(wù)，但在分布式系統(tǒng)的協(xié)議設(shè)計(jì)中不能認(rèn)為所有網(wǎng)絡(luò)通信都基于TCP 協(xié)議則通信就是可靠的。
• TCP協(xié)議只能保證同一個(gè)TCP 鏈接內(nèi)的網(wǎng)絡(luò)消息不亂序，TCP 鏈接之間的網(wǎng)絡(luò)消息順序則無法保證。
• 分布式三態(tài)：如果某個(gè)節(jié)點(diǎn)向另一個(gè)節(jié)點(diǎn)發(fā)起RPC(Remote procedure call)調(diào)用，即某個(gè)節(jié)點(diǎn)A 向另一個(gè)節(jié)點(diǎn)B 發(fā)送一個(gè)消息，節(jié)點(diǎn)B 根據(jù)收到的消息內(nèi)容完成某些操作，并將操作的結(jié)果通過另一個(gè)消息返回給節(jié)點(diǎn)A，那么這個(gè)RPC 執(zhí)行的結(jié)果有三種狀態(tài)：“成功”、“失敗”、“超時(shí)(未知)”，稱之為分布式系統(tǒng)的三態(tài)。
• 存儲(chǔ)數(shù)據(jù)丟失:對(duì)于有狀態(tài)節(jié)點(diǎn)來說，數(shù)據(jù)丟失意味著狀態(tài)丟失，通常只能從其他節(jié)點(diǎn)讀取、恢復(fù)存儲(chǔ)的狀態(tài)。
• *異常處理原則*：被大量工程實(shí)踐所檢驗(yàn)過的異常處理黃金原則是：任何在設(shè)計(jì)階段考慮到的異常情況一定會(huì)在系統(tǒng)實(shí)際運(yùn)行中發(fā)生，但在系統(tǒng)實(shí)際運(yùn)行遇到的異常卻很有可能在設(shè)計(jì)時(shí)未能考慮，所以，除非需求指標(biāo)允許，在系統(tǒng)設(shè)計(jì)時(shí)不能放過任何異常情況。

1.2 副本

副本(replica/copy)指在分布式系統(tǒng)中為數(shù)據(jù)或服務(wù)提供的冗余。對(duì)于數(shù)據(jù)副本指在不同的節(jié)點(diǎn)上持久化同一份數(shù)據(jù)，當(dāng)出現(xiàn)某一個(gè)節(jié)點(diǎn)的存儲(chǔ)的數(shù)據(jù)丟失時(shí)，可以從副本上讀到數(shù)據(jù)。

數(shù)據(jù)副本是分布式系統(tǒng)解決數(shù)據(jù)丟失異常的唯一手段。另一類副本是服務(wù)副本，指數(shù)個(gè)節(jié)點(diǎn)提供某種相同的服務(wù)，這種服務(wù)一般并不依賴于節(jié)點(diǎn)的本地存儲(chǔ)，其所需數(shù)據(jù)一般來自其他節(jié)點(diǎn)。

副本協(xié)議是貫穿整個(gè)分布式系統(tǒng)的理論核心。

副本一致性

分布式系統(tǒng)通過副本控制協(xié)議，使得從系統(tǒng)外部讀取系統(tǒng)內(nèi)部各個(gè)副本的數(shù)據(jù)在一定的約束條件下相同，稱之為副本一致性(consistency)。副本一致性是針對(duì)分布式系統(tǒng)而言的，不是針對(duì)某一個(gè)副本而言。

• 強(qiáng)一致性(strong consistency)：任何時(shí)刻任何用戶或節(jié)點(diǎn)都可以讀到最近一次成功更新的副本數(shù)據(jù)。強(qiáng)一致性是程度最高的一致性要求，也是實(shí)踐中最難以實(shí)現(xiàn)的一致性。
• 單調(diào)一致性(monotonic consistency)：任何時(shí)刻，任何用戶一旦讀到某個(gè)數(shù)據(jù)在某次更新后的值，這個(gè)用戶不會(huì)再讀到比這個(gè)值更舊的值。
• 單調(diào)一致性是弱于強(qiáng)一致性卻非常實(shí)用的一種一致性級(jí)別。因?yàn)橥ǔ碚f，用戶只關(guān)心從己方視角觀察到的一致性，而不會(huì)關(guān)注其他用戶的一致性情況。
• 會(huì)話一致性(session consistency)：任何用戶在某一次會(huì)話內(nèi)一旦讀到某個(gè)數(shù)據(jù)在某次更新后的值，這個(gè)用戶在這次會(huì)話過程中不會(huì)再讀到比這個(gè)值更舊的值。
• 會(huì)話一致性通過引入會(huì)話的概念，在單調(diào)一致性的基礎(chǔ)上進(jìn)一步放松約束，會(huì)話一致性只保證單個(gè)用戶單次會(huì)話內(nèi)數(shù)據(jù)的單調(diào)修改，對(duì)于不同用戶間的一致性和同一用戶不同會(huì)話間的一致性沒有保障。
• 實(shí)踐中有許多機(jī)制正好對(duì)應(yīng)會(huì)話的概念，例如php 中的session 概念。
• 最終一致性(eventual consistency)：最終一致性要求一旦更新成功，各個(gè)副本上的數(shù)據(jù)最終將達(dá) 到完全一致的狀態(tài)，但達(dá)到完全一致狀態(tài)所需要的時(shí)間不能保障。
• 對(duì)于最終一致性系統(tǒng)而言，一個(gè)用戶只要始終讀取某一個(gè)副本的數(shù)據(jù)，則可以實(shí)現(xiàn)類似單調(diào)一致性的效果，但一旦用戶更換讀取的副本，則無法保障任何一致性。
• 弱一致性(week consistency)：一旦某個(gè)更新成功，用戶無法在一個(gè)確定時(shí)間內(nèi)讀到這次更新的值，且即使在某個(gè)副本上讀到了新的值，也不能保證在其他副本上可以讀到新的值。
• 弱一致性系統(tǒng)一般很難在實(shí)際中使用，使用弱一致性系統(tǒng)需要應(yīng)用方做更多的工作從而使得系統(tǒng)可用。

1.3 衡量分布式系統(tǒng)的指標(biāo)

• 性能：系統(tǒng)的吞吐能力，指系統(tǒng)在某一時(shí)間可以處理的數(shù)據(jù)總量，通常可以用系統(tǒng)每秒處理的總的數(shù)據(jù)量來衡量;
  • 系統(tǒng)的響應(yīng)延遲，指系統(tǒng)完成某一功能需要使用的時(shí)間;
  • 系統(tǒng)的并發(fā)能力，指系統(tǒng)可以同時(shí)完成某一功能的能力，通常也用QPS(query per second)來衡量。
  • 上述三個(gè)性能指標(biāo)往往會(huì)相互制約，追求高吞吐的系統(tǒng)，往往很難做到低延遲;系統(tǒng)平均響應(yīng)時(shí)間較長時(shí)，也很難提高QPS。
• 可用性：系統(tǒng)的可用性(availability)指系統(tǒng)在面對(duì)各種異常時(shí)可以正確提供服務(wù)的能力。
  • 系統(tǒng)的可用性可以用系統(tǒng)停服務(wù)的時(shí)間與正常服務(wù)的時(shí)間的比例來衡量，也可以用某功能的失敗次數(shù)與成功次數(shù)的比例來衡量?？捎眯允欠植际降闹匾笜?biāo)，衡量了系統(tǒng)的魯棒性，是系統(tǒng)容錯(cuò)能力的體現(xiàn)。
• 可擴(kuò)展性：系統(tǒng)的可擴(kuò)展性(scalability)指分布式系統(tǒng)通過擴(kuò)展集群機(jī)器規(guī)模提高系統(tǒng)性能(吞吐、延遲、并發(fā))、存儲(chǔ)容量、計(jì)算能力的特性。好的分布式系統(tǒng)總在追求“線性擴(kuò)展性”，也就是使得系統(tǒng)的某一指標(biāo)可以隨著集群中的機(jī)器數(shù)量線性增長。
• 一致性：分布式系統(tǒng)為了提高可用性，總是不可避免的使用副本的機(jī)制，從而引發(fā)副本一致性的問題。越是強(qiáng)的一致的性模型，對(duì)于用戶使用來說使用起來越簡單。

2 分布式系統(tǒng)原理

2.1 數(shù)據(jù)分布方式

所謂分布式系統(tǒng)顧名思義就是利用多臺(tái)計(jì)算機(jī)協(xié)同解決單臺(tái)計(jì)算機(jī)所不能解決的計(jì)算、存儲(chǔ)等問題。

單機(jī)系統(tǒng)與分布式系統(tǒng)的最大的區(qū)別在于問題的規(guī)模，即計(jì)算、存儲(chǔ)的數(shù)據(jù)量的區(qū)別。

將一個(gè)單機(jī)問題使用分布式解決，首先要解決的就是如何將問題拆解為可以使用多機(jī)分布式解決，使得分布式系統(tǒng)中的每臺(tái)機(jī)器負(fù)責(zé)原問題的一個(gè)子集。由于無論是計(jì)算還是存儲(chǔ)，其問題輸入對(duì)象都是數(shù)據(jù)，所以如何拆解分布式系統(tǒng)的輸入數(shù)據(jù)成為分布式系統(tǒng)的基本問題。

哈希方式

 

哈希分布數(shù)據(jù)的缺點(diǎn)同樣明顯，突出表現(xiàn)為可擴(kuò)展性不高，一旦集群規(guī)模需要擴(kuò)展，則幾乎所有的數(shù)據(jù)需要被遷移并重新分布。工程中，擴(kuò)展哈希分布數(shù)據(jù)的系統(tǒng)時(shí)，往往使得集群規(guī)模成倍擴(kuò)展，按照數(shù)據(jù)重新計(jì)算哈希，這樣原本一臺(tái)機(jī)器上的數(shù)據(jù)只需遷移一半到另一臺(tái)對(duì)應(yīng)的機(jī)器上即可完成擴(kuò)展。

針對(duì)哈希方式擴(kuò)展性差的問題，一種思路是不再簡單的將哈希值與機(jī)器做除法取模映射，而是將對(duì)應(yīng)關(guān)系作為元數(shù)據(jù)由專門的元數(shù)據(jù)服務(wù)器管理.同時(shí)，哈希值取模個(gè)數(shù)往往大于機(jī)器個(gè)數(shù)，這樣同一臺(tái)機(jī)器上需要負(fù)責(zé)多個(gè)哈希取模的余數(shù)。但需要以較復(fù)雜的機(jī)制維護(hù)大量的元數(shù)據(jù)。哈希分布數(shù)據(jù)的另一個(gè)缺點(diǎn)是，一旦某數(shù)據(jù)特征值的數(shù)據(jù)嚴(yán)重不均，容易出現(xiàn)“數(shù)據(jù)傾斜”(data skew)問題。

哈希分布數(shù)據(jù)的另一個(gè)缺點(diǎn)是，一旦某數(shù)據(jù)特征值的數(shù)據(jù)嚴(yán)重不均，容易出現(xiàn)“數(shù)據(jù)傾斜”(data skew)問題

 

按數(shù)據(jù)范圍分布

按數(shù)據(jù)范圍分布是另一個(gè)常見的數(shù)據(jù)分布式，將數(shù)據(jù)按特征值的值域范圍劃分為不同的區(qū)間，使得集群中每臺(tái)(組)服務(wù)器處理不同區(qū)間的數(shù)據(jù)。

 

工程中，為了數(shù)據(jù)遷移等負(fù)載均衡操作的方便，往往利用動(dòng)態(tài)劃分區(qū)間的技術(shù)，使得每個(gè)區(qū)間中服務(wù)的數(shù)據(jù)量盡量的一樣多。當(dāng)某個(gè)區(qū)間的數(shù)據(jù)量較大時(shí)，通過將區(qū)間“分裂”的方式拆分為兩個(gè)區(qū)間，使得每個(gè)數(shù)據(jù)區(qū)間中的數(shù)據(jù)量都盡量維持在一個(gè)較為固定的閾值之下。

一般的，往往需要使用專門的服務(wù)器在內(nèi)存中維護(hù)數(shù)據(jù)分布信息，稱這種數(shù)據(jù)的分布信息為一種元信息。甚至對(duì)于大規(guī)模的集群，由于元信息的規(guī)模非常龐大，單臺(tái) 計(jì)算機(jī)無法獨(dú)立維護(hù)，需要使用多臺(tái)機(jī)器作為元信息服務(wù)器。

按數(shù)據(jù)量分布

數(shù)據(jù)量分布數(shù)據(jù)與具體的數(shù)據(jù)特征無關(guān)，而是將數(shù)據(jù)視為一個(gè)順序增長的文件，并將這個(gè)文件按照某一較為固定的大小劃分為若干數(shù)據(jù)塊(chunk)，不同的數(shù)據(jù)塊分布到不同的服務(wù)器上

與按數(shù)據(jù)范圍分布數(shù)據(jù)的方式類似的是，按數(shù)據(jù)量分布數(shù)據(jù)也需要記錄數(shù)據(jù)塊的具體分布情況，并將該分布信息作為元數(shù)據(jù)使用元數(shù)據(jù)服務(wù)器管理。

由于與具體的數(shù)據(jù)內(nèi)容無關(guān)，按數(shù)據(jù)量分布數(shù)據(jù)的方式一般沒有數(shù)據(jù)傾斜的問題，數(shù)據(jù)總是被均勻切分并分布到集群中。

當(dāng)集群需要重新負(fù)載均衡時(shí)，只需通過遷移數(shù)據(jù)塊即可完成。集群擴(kuò)容也沒有太大的限制，只需將部分?jǐn)?shù)據(jù)庫遷移到新加入的機(jī)器上即可以完成擴(kuò)容。

按數(shù)據(jù)量劃分?jǐn)?shù)據(jù)的缺點(diǎn)是需要管理較為復(fù)雜的元信息，與按范圍分布數(shù)據(jù)的方式類似，當(dāng)集群規(guī)模較大時(shí)，元信息的數(shù)據(jù)量也變得很大，高效的管理元信息成為新的課題。

一致性哈希

一致性哈希(consistent hashing)是另一個(gè)種在工程中使用較為廣泛的數(shù)據(jù)分布方式。一致性哈希最初在P2P 網(wǎng)絡(luò)中作為分布式哈希表(DHT)的常用數(shù)據(jù)分布算法。

一致性哈希的基本方式是使用一個(gè)哈希函數(shù)計(jì)算數(shù)據(jù)或數(shù)據(jù)特征的哈希值，令該哈希函數(shù)的輸出值域?yàn)橐粋€(gè)封閉的環(huán)，即哈希函數(shù)輸出的最大值是最小值的前序。將節(jié)點(diǎn)隨機(jī)分布到這個(gè)環(huán)上，每個(gè)節(jié)點(diǎn)負(fù)責(zé)處理從自己開始順時(shí)針至下一個(gè)節(jié)點(diǎn)的全部哈希值域上的數(shù)據(jù)。

 

使用一致性哈希的方式需要將節(jié)點(diǎn)在一致性哈希環(huán)上的位置作為元信息加以管理，這點(diǎn)比直接使用哈希分布數(shù)據(jù)的方式要復(fù)雜。然而，節(jié)點(diǎn)的位置信息只于集群中的機(jī)器規(guī)模相關(guān)，其元信息的量通常比按數(shù)據(jù)范圍分布數(shù)據(jù)和按數(shù)據(jù)量分布數(shù)據(jù)的元信息量要小很多。

為此一種常見的改進(jìn)算法是引入虛節(jié)點(diǎn)(virtual node)的概念，系統(tǒng)初始時(shí)就創(chuàng)建許多虛節(jié)點(diǎn)，虛節(jié)點(diǎn)的個(gè)數(shù)一般遠(yuǎn)大于未來集群中機(jī)器的個(gè)數(shù)，將虛節(jié)點(diǎn)均勻分布到一致性哈希值域環(huán)上，其功能與基本一致性哈希算法中的節(jié)點(diǎn)相同。為每個(gè)節(jié)點(diǎn)分配若干虛節(jié)點(diǎn)。

操作數(shù)據(jù)時(shí)，首先通過數(shù)據(jù)的哈希值在環(huán)上找到對(duì)應(yīng)的虛節(jié)點(diǎn)，進(jìn)而查找元數(shù)據(jù)找到對(duì)應(yīng)的真實(shí)節(jié)點(diǎn)。使用虛節(jié)點(diǎn)改進(jìn)有多個(gè)優(yōu)點(diǎn)。

首先，一旦某個(gè)節(jié)點(diǎn)不可用，該節(jié)點(diǎn)將使得多個(gè)虛節(jié)點(diǎn)不可用，從而使得多個(gè)相鄰的真實(shí)節(jié)點(diǎn)負(fù)載失效節(jié)點(diǎn)的壓里。同理，一旦加入一個(gè)新節(jié)點(diǎn)，可以分配多個(gè)虛節(jié)點(diǎn)，從而使得新節(jié)點(diǎn)可以 負(fù)載多個(gè)原有節(jié)點(diǎn)的壓力，從全局看，較容易實(shí)現(xiàn)擴(kuò)容時(shí)的負(fù)載均衡。

副本與數(shù)據(jù)分布

分布式系統(tǒng)容錯(cuò)、提高可用性的基本手段就是使用副本。對(duì)于數(shù)據(jù)副本的分布方式主要影響系統(tǒng)的可擴(kuò)展性。一種基本的數(shù)據(jù)副本策略是以機(jī)器為單位，若干機(jī)器互為副本，副本機(jī)器之間的數(shù)據(jù)完全相同。這種策略適用于上述各種數(shù)據(jù)分布方式。其優(yōu)點(diǎn)是非常簡單，其缺點(diǎn)是恢復(fù)數(shù)據(jù)的效率不高、可擴(kuò)展性也不高。

更合適的做法不是以機(jī)器作為副本單位，而是將數(shù)據(jù)拆為較合理的數(shù)據(jù)段，以數(shù)據(jù)段為單位作為副本。

實(shí)踐中，常常使得每個(gè)數(shù)據(jù)段的大小盡量相等且控制在一定的大小以內(nèi)。數(shù)據(jù)段有很多不同的稱謂，segment，fragment，chunk，partition 等等。數(shù)據(jù)段的選擇與數(shù)據(jù)分布方式直接相關(guān)。

對(duì)于哈希分?jǐn)?shù)據(jù)的方式，每個(gè)哈希分桶后的余數(shù)可以作為一個(gè)數(shù)據(jù)段，為了控制數(shù)據(jù)段的大小，常常使得分桶個(gè)數(shù)大于集群規(guī)模。一旦將數(shù)據(jù)分為數(shù)據(jù)段，則可以以數(shù)據(jù)段為單位管理副本，從而副本與機(jī)器不再硬相關(guān)，每臺(tái)機(jī)器都可以負(fù)責(zé)一定數(shù)據(jù)段的副本。

 

一旦副本分布與機(jī)器無關(guān)，數(shù)據(jù)丟失后的恢復(fù)效率將非常高。這是因?yàn)?，一旦某臺(tái)機(jī)器的數(shù)據(jù)丟失，其上數(shù)據(jù)段的副本將分布在整個(gè)集群的所有機(jī)器中，而不是僅在幾個(gè)副本機(jī)器中，從而可以從整個(gè)集群同時(shí)拷貝恢復(fù)數(shù)據(jù)，而集群中每臺(tái)數(shù)據(jù)源機(jī)器都可以以非常低的資源做拷貝。作為恢復(fù)數(shù)據(jù)源的機(jī)器即使都限速1MB/s，若有100 臺(tái)機(jī)器參與恢復(fù)，恢復(fù)速度也能達(dá)到100MB/s。

再者，副本分布與機(jī)器無關(guān)也利于集群容錯(cuò)。如果出現(xiàn)機(jī)器宕機(jī)，由于宕機(jī)機(jī)器上的副本分散于整個(gè)集群，其壓力也自然分散到整個(gè)集群。

最后，副本分布與機(jī)器無關(guān)也利于集群擴(kuò)展。理論上，設(shè)集群規(guī)模 為N 臺(tái)機(jī)器，當(dāng)加入一臺(tái)新的機(jī)器時(shí)，只需從各臺(tái)機(jī)器上遷移1/N – 1/N+1 比例的數(shù)據(jù)段到新機(jī)器即實(shí)現(xiàn)了新的負(fù)載均衡。由于是從集群中各機(jī)器遷移數(shù)據(jù)，與數(shù)據(jù)恢復(fù)同理，效率也較高。

工程中，完全按照數(shù)據(jù)段建立副本會(huì)引起需要管理的元數(shù)據(jù)的開銷增大，副本維護(hù)的難度也相應(yīng)增大。一種折中的做法是將某些數(shù)據(jù)段組成一個(gè)數(shù)據(jù)段分組，按數(shù)據(jù)段分組為粒度進(jìn)行副本管理。這樣做可以將副本粒度控制在一個(gè)較為合適的范圍內(nèi)。

本地化計(jì)算

在分布式系統(tǒng)中，數(shù)據(jù)的分布方式也深深影響著計(jì)算的分布方式。在分布式系統(tǒng)中計(jì)算節(jié)點(diǎn)和保存計(jì)算數(shù)據(jù)的存儲(chǔ)節(jié)點(diǎn)可以在同一臺(tái)物理機(jī)器上，也可以位于不同的物理機(jī)器。

如果計(jì)算節(jié)點(diǎn)和存儲(chǔ)節(jié)點(diǎn)位于不同的物理機(jī)器則計(jì)算的數(shù)據(jù)需要通過網(wǎng)絡(luò)傳輸，此種方式的開銷很大，甚至網(wǎng)絡(luò)帶寬會(huì)成為系統(tǒng)的總體瓶頸。

另一種思路是，將計(jì)算盡量調(diào)度到與存儲(chǔ)節(jié)點(diǎn)在同一臺(tái)物理機(jī)器上的計(jì)算節(jié)點(diǎn)上進(jìn)行，這稱之為本地化計(jì)算。本地化計(jì)算是計(jì)算調(diào)度的一種重要優(yōu)化，其體現(xiàn)了一種重要的分布式調(diào)度思想：“移動(dòng)數(shù)據(jù)不如移動(dòng)計(jì)算”。

數(shù)據(jù)分布方式的選擇

在實(shí)際工程實(shí)踐中，可以根據(jù)需求及實(shí)施復(fù)雜度合理選擇數(shù)據(jù)分布方式。另外，數(shù)據(jù)分布方式是可以靈活組合使用的，往往可以兼?zhèn)涓鞣N方式的優(yōu)點(diǎn)，收到較好的綜合效果。

例：數(shù)據(jù)傾斜問題，在按哈希分?jǐn)?shù)據(jù)的基礎(chǔ)上引入按數(shù)據(jù)量分布數(shù)據(jù)的方式，解決該數(shù)據(jù)傾斜問題。按用戶id 的哈希值分?jǐn)?shù)據(jù)，當(dāng)某個(gè)用戶id 的數(shù)據(jù)量特別大時(shí)，該用戶的數(shù)據(jù)始終落在某一臺(tái)機(jī)器上。此時(shí)，引入按數(shù)據(jù)量分布數(shù)據(jù)的方式，統(tǒng)計(jì)用戶的數(shù)據(jù)量，并按某一閾值將用戶的數(shù)據(jù)切為多個(gè)均勻的數(shù)據(jù)段，將這些數(shù)據(jù)段分布到集群中去。由于大部分用戶的數(shù)據(jù)量不會(huì)超過閾值，所以元數(shù)據(jù)中僅僅保存超過閾值的用戶的數(shù)據(jù)段分布信息，從而可以控制元數(shù)據(jù)的規(guī)模。這種哈希分布數(shù)據(jù)方式與按數(shù)據(jù)量分布數(shù)據(jù)方式組合使用的方案，在某真實(shí)系統(tǒng)中使用，取得了較好的效果。

2.2 基本副本協(xié)議

副本控制協(xié)議指按特定的協(xié)議流程控制副本數(shù)據(jù)的讀寫行為，使得副本滿足一定的可用性和一致性要求的分布式協(xié)議。副本控制協(xié)議要具有一定的對(duì)抗異常狀態(tài)的容錯(cuò)能力，從而使得系統(tǒng)具有一定的可用性，同時(shí)副本控制協(xié)議要能提供一定一致性級(jí)別。由CAP 原理(在2.9 節(jié)詳細(xì)分析)可知，要設(shè)計(jì)一種滿足強(qiáng)一致性，且在出現(xiàn)任何網(wǎng)絡(luò)異常時(shí)都可用的副本協(xié)議是不可能的。為此，實(shí)際中的副本控制協(xié)議總是在可用性、一致性與性能等各要素之間按照具體需求折中。

副本控制協(xié)議可以分為兩大類：“中心化(centralized)副本控制協(xié)議”和“去中心化(decentralized)副本控制協(xié)議”。

中心化副本控制協(xié)議

中心化副本控制協(xié)議的基本思路是由一個(gè)中心節(jié)點(diǎn)協(xié)調(diào)副本數(shù)據(jù)的更新、維護(hù)副本之間的一致性。

圖給出了中心化副本協(xié)議的通用架構(gòu)。中心化副本控制協(xié)議的優(yōu)點(diǎn)是協(xié)議相對(duì)較為簡單，所有的副本相關(guān)的控制交由中心節(jié)點(diǎn)完成。并發(fā)控制將由中心節(jié)點(diǎn)完成，從而使得一個(gè)分布式并發(fā)控制問題，簡化為一個(gè)單機(jī)并發(fā)控制問題。

所謂并發(fā)控制，即多個(gè)節(jié)點(diǎn)同時(shí)需要修改副本數(shù)據(jù)時(shí)，需要解決“寫寫”、“讀寫”等并發(fā)沖突。單機(jī)系統(tǒng)上常用加鎖等方式進(jìn)行并發(fā)控制。對(duì)于分布式并發(fā)控制，加鎖也是一個(gè)常用的方法，但如果沒有中心節(jié)點(diǎn)統(tǒng)一進(jìn)行鎖管理，就需要完全分布式化的鎖系統(tǒng)，會(huì)使得協(xié)議非常復(fù)雜。

中心化副本控制協(xié)議的缺點(diǎn)是系統(tǒng)的可用性依賴于中心化節(jié)點(diǎn)，當(dāng)中心節(jié)點(diǎn)異?；蚺c中心節(jié)點(diǎn)通信中斷時(shí)，系統(tǒng)將失去某些服務(wù)(通常至少失去更新服務(wù))，所以中心化副本控制協(xié)議的缺點(diǎn)正是存在一定的停服務(wù)時(shí)間。

 

primary-secondary 協(xié)議

在primary-secondary 類型的協(xié)議中，副本被分為兩大類，其中有且僅有一個(gè)副本作為primary 副本，除primary 以外的副本都作為secondary 副本。維護(hù)primary 副本的節(jié)點(diǎn)作為中心節(jié)點(diǎn)，中心節(jié)點(diǎn)負(fù)責(zé)維護(hù)數(shù)據(jù)的更新、并發(fā)控制、協(xié)調(diào)副本的一致性。

Primary-secondary 類型的協(xié)議一般要解決四大類問題：數(shù)據(jù)更新流程、數(shù)據(jù)讀取方式、Primary 副本的確定和切換、數(shù)據(jù)同步(reconcile)。

數(shù)據(jù)更新基本流程

1. 數(shù)據(jù)更新都由primary 節(jié)點(diǎn)協(xié)調(diào)完成。
2. 外部節(jié)點(diǎn)將更新操作發(fā)給primary 節(jié)點(diǎn)
3. primary 節(jié)點(diǎn)進(jìn)行并發(fā)控制即確定并發(fā)更新操作的先后順序
4. primary 節(jié)點(diǎn)將更新操作發(fā)送給secondary 節(jié)點(diǎn)
5. primary 根據(jù)secondary 節(jié)點(diǎn)的完成情況決定更新是否成功并將結(jié)果返回外部節(jié)點(diǎn)

 

在工程實(shí)踐中，如果由primary 直接同時(shí)發(fā)送給其他N 個(gè)副本發(fā)送數(shù)據(jù)，則每個(gè) secondary 的更新吞吐受限于primary 總的出口網(wǎng)絡(luò)帶寬，最大為primary 網(wǎng)絡(luò)出口帶寬的1/N。

為了解決這個(gè)問題，有些系統(tǒng)(例如，GFS)，使用接力的方式同步數(shù)據(jù)，即primary 將更新發(fā)送給第一 個(gè)secondary 副本，第一個(gè)secondary 副本發(fā)送給第二secondary 副本，依次類推。

數(shù)據(jù)讀取方式

數(shù)據(jù)讀取方式也與一致性高度相關(guān)。如果只需要最終一致性，則讀取任何副本都可以滿足需求。

如果需要會(huì)話一致性，則可以為副本設(shè)置版本號(hào)，每次更新后遞增版本號(hào)，用戶讀取副本時(shí)驗(yàn)證版本號(hào)，從而保證用戶讀到的數(shù)據(jù)在會(huì)話范圍內(nèi)單調(diào)遞增。使用primary-secondary 比較困難的是實(shí)現(xiàn)強(qiáng)一致性。

由于數(shù)據(jù)的更新流程都是由primary 控制的，primary 副本上的數(shù)據(jù)一定是最新的，所以 如果始終只讀primary 副本的數(shù)據(jù)，可以實(shí)現(xiàn)強(qiáng)一致性。如果只讀primary 副本，則secondary 副本將不提供讀服務(wù)。

實(shí)踐中，如果副本不與機(jī)器綁定，而是按照數(shù)據(jù)段為單位維護(hù)副本，僅有primary 副本提供讀服務(wù)在很多場景下并不會(huì)造出機(jī)器資源浪費(fèi)。

將副本分散到集群中個(gè)，假設(shè)primary 也是隨機(jī)的確定的，那么每臺(tái)機(jī)器上都有一些數(shù)據(jù)的primary 副本，也有另一些數(shù)據(jù)段的secondary 副本。從而某臺(tái)服務(wù)器實(shí)際都提供讀寫服務(wù)。

由primary 控制節(jié)點(diǎn)secondary 節(jié)點(diǎn)的可用性。當(dāng)primary 更新某個(gè)secondary 副本不成功時(shí)，primary 將該secondary 副本標(biāo)記為不可用，從而用戶不再讀取該不可用的副本。不可用的 secondary 副本可以繼續(xù)嘗試與primary 同步數(shù)據(jù)，當(dāng)與primary 完成數(shù)據(jù)同步后，primary 可以副本標(biāo)記為可用。

這種方式使得所有的可用的副本，無論是primary 還是secondary 都是可讀的，且在一個(gè)確定的時(shí)間內(nèi)，某secondary 副本要么更新到與primary 一致的最新狀態(tài)，要么被標(biāo)記為不可用，從而符合較高的一致性要求。這種方式依賴于一個(gè)中心元數(shù)據(jù)管理系統(tǒng)，用于記錄哪些副本可用，哪些副本不可用。某種意義上，該方式通過降低系統(tǒng)的可用性來提高系統(tǒng)的一致性。

primary 副本的確定與切換

在primary-secondary 類型的協(xié)議中，另一個(gè)核心的問題是如何確定primary 副本，尤其是在原primary 副本所在機(jī)器出現(xiàn)宕機(jī)等異常時(shí)，需要有某種機(jī)制切換primary 副本，使得某個(gè)secondary 副本成為新的primary 副本。

通常的，在primary-secondary 類型的分布式系統(tǒng)中，哪個(gè)副本是primary 這一信息都屬于元信息，由專門的元數(shù)據(jù)服務(wù)器維護(hù)。執(zhí)行更新操作時(shí)，首先查詢?cè)獢?shù)據(jù)服務(wù)器獲取副本的primary 信息，從而進(jìn)一步執(zhí)行數(shù)據(jù)更新流程。

由于分布式系統(tǒng)中可靠的發(fā)現(xiàn)節(jié)點(diǎn)異常是需要一定的探測時(shí)間的，這樣的探測時(shí)間通常是10 秒級(jí)別，這也意味著一旦primary 異常，最多需要10 秒級(jí)別的發(fā)現(xiàn)時(shí)間，系統(tǒng)才能開始primary 的切換，在這10 秒時(shí)間內(nèi)，由于沒有primary，系統(tǒng)不能提供更 新服務(wù)，如果系統(tǒng)只能讀primary 副本，則這段時(shí)間內(nèi)甚至不能提供讀服務(wù)。從這里可以看到，primary-backup 類副本協(xié)議的最大缺點(diǎn)就是由于primary 切換帶來的一定的停服務(wù)時(shí)間。

數(shù)據(jù)同步

不一致的secondary 副本需要與primary 進(jìn)行同步(reconcile)。

通常不一致的形式有三種：

一、由于網(wǎng)絡(luò)分化等異常，secondary 上的數(shù)據(jù)落后于primary 上的數(shù)據(jù)。

二、在某些協(xié)議下，secondary 上的數(shù)據(jù)有可能是臟數(shù)據(jù)，需要被丟棄。所謂臟數(shù)據(jù)是由于primary 副本沒有進(jìn)行某一更新操作，而secondary 副本上反而進(jìn)行的多余的修改操作，從而造成secondary 副本數(shù)據(jù)錯(cuò)誤。

三、secondary 是一個(gè)新增加的副本，完全沒有數(shù)據(jù)，需要從其他副本上拷貝數(shù)據(jù)。

對(duì)于第一種secondary 數(shù)據(jù)落后的情況，常見的同步方式是回放primary 上的操作日志(通常是redo 日志)，從而追上primary 的更新進(jìn)度。

對(duì)于臟數(shù)據(jù)的情況，較好的做法是設(shè)計(jì)的分布式協(xié)議不產(chǎn)生臟數(shù)據(jù)。如果協(xié)議一定有產(chǎn)生臟數(shù)據(jù)的可能，則也應(yīng)該使得產(chǎn)生臟數(shù)據(jù)的概率降到非常低得情況，從而一旦發(fā)生臟數(shù)據(jù)的情況可以簡單的直接丟棄有臟數(shù)據(jù)的副本，這樣相當(dāng)于副本沒有數(shù)據(jù)。

另外，也可以設(shè)計(jì)一些基于undo 日志的方式從而可以刪除臟數(shù)據(jù)。如果secondary 副本完全沒有數(shù)據(jù)，則常見的做法是直接拷貝primary 副本的數(shù)據(jù)，這種方法往往比回放日志追更新進(jìn)度的方法快很多。但拷貝數(shù)據(jù)時(shí)primary 副本需要能夠繼續(xù)提供更新服務(wù)，這就要求primary 副本支持快照(snapshot)功能。即對(duì)某一刻的副本數(shù)據(jù)形成快照，然后拷貝快照，拷貝完成后使用回放日志的方式追快照形成后的更新操作。

去中心化副本控制協(xié)議

去中心化副本控制協(xié)議沒有中心節(jié)點(diǎn)，協(xié)議中所有的節(jié)點(diǎn)都是完全對(duì)等的，節(jié)點(diǎn)之間通過平等協(xié)商達(dá)到一致。從而去中心化協(xié)議沒有因?yàn)橹行幕?jié)點(diǎn)異常而帶來的停服務(wù)等問題。

去中心化協(xié)議的最大的缺點(diǎn)是協(xié)議過程通常比較復(fù)雜。尤其當(dāng)去中心化協(xié)議需要實(shí)現(xiàn)強(qiáng)一致性時(shí)，協(xié)議流程變得復(fù)雜且不容易理解。由于流程的復(fù)雜，去中心化協(xié)議的效率或者性能一般也較中心化協(xié)議低。一個(gè)不恰當(dāng)?shù)谋确骄褪?，中心化副本控制協(xié)議類似專制制度，系統(tǒng)效率高但高度依賴于中心節(jié)點(diǎn)，一旦中心節(jié)點(diǎn)異常，系統(tǒng)受到的影響較大;去中心化副本控制協(xié)議類似民主制度，節(jié)點(diǎn)集體協(xié)商，效率低下，但個(gè)別節(jié)點(diǎn)的異常不會(huì)對(duì)系統(tǒng)總體造成太大影響。

 

2.3 Lease 機(jī)制

Lease 機(jī)制是最重要的分布式協(xié)議，廣泛應(yīng)用于各種實(shí)際的分布式系統(tǒng)中。

基于lease 的分布式cache 系統(tǒng)

基本的問題背景如下：在一個(gè)分布式系統(tǒng)中，有一個(gè)中心服務(wù)器節(jié)點(diǎn)，中心服務(wù)器存儲(chǔ)、維護(hù)著一些數(shù)據(jù)，這些數(shù)據(jù)是系統(tǒng)的元數(shù)據(jù)。系統(tǒng)中其他的節(jié)點(diǎn)通過訪問中心服務(wù)器節(jié)點(diǎn)讀取、修改其上的元數(shù)據(jù)。

由于系統(tǒng)中各種操作都依賴于元數(shù)據(jù)，如果每次讀取元數(shù)據(jù)的操作都訪問中心服務(wù)器 節(jié)點(diǎn)，那么中心服務(wù)器節(jié)點(diǎn)的性能成為系統(tǒng)的瓶頸。為此，設(shè)計(jì)一種元數(shù)據(jù)cache，在各個(gè)節(jié)點(diǎn)上 cache 元數(shù)據(jù)信息，從而減少對(duì)中心服務(wù)器節(jié)點(diǎn)的訪問，提高性能。

另一方面，系統(tǒng)的正確運(yùn)行嚴(yán)格依賴于元數(shù)據(jù)的正確，這就要求各個(gè)節(jié)點(diǎn)上cache 的數(shù)據(jù)始終與中心服務(wù)器上的數(shù)據(jù)一致，cache 中的數(shù)據(jù)不能是舊的臟數(shù)據(jù)。最后，設(shè)計(jì)的cache 系統(tǒng)要能最大可能的處理節(jié)點(diǎn)宕機(jī)、網(wǎng)絡(luò)中斷等異常，最大程度的提高系統(tǒng)的可用性。

為此，利用lease 機(jī)制設(shè)計(jì)一套cache 系統(tǒng)，其基本原理為如下。

中心服務(wù)器在向各節(jié)點(diǎn)發(fā)送數(shù)據(jù)時(shí)同時(shí)向節(jié)點(diǎn)頒發(fā)一個(gè)lease。每個(gè)lease 具有一個(gè)有效期，和信用卡上的有效期類似，lease 上的 有效期通常是一個(gè)明確的時(shí)間點(diǎn)，例如12:00:10，一旦真實(shí)時(shí)間超過這個(gè)時(shí)間點(diǎn)，則lease 過期失效。這樣lease 的有效期與節(jié)點(diǎn)收到lease 的時(shí)間無關(guān)，節(jié)點(diǎn)可能收到lease 時(shí)該lease 就已經(jīng)過期失效。這里首先假設(shè)中心服務(wù)器與各節(jié)點(diǎn)的時(shí)鐘是同步的，在下節(jié)中討論時(shí)鐘不同步對(duì)lease 的影響。中心服務(wù)器發(fā)出的lease 的含義為：在lease 的有效期內(nèi)，中心服務(wù)器保證不會(huì)修改對(duì)應(yīng)數(shù)據(jù)的值。因此，節(jié)點(diǎn)收到數(shù)據(jù)和lease 后，將數(shù)據(jù)加入本地Cache，一旦對(duì)應(yīng)的lease 超時(shí)，節(jié)點(diǎn)將對(duì)應(yīng)的本地cache 數(shù)據(jù)刪除。中心服務(wù)器在修改數(shù)據(jù)時(shí)，首先阻塞所有新的讀請(qǐng)求，并等待之前為該數(shù)據(jù)發(fā)出的所有l(wèi)ease 超時(shí)過期，然后修改數(shù)據(jù)的值。

基于lease 的cache，客戶端節(jié)點(diǎn)讀取元數(shù)據(jù)

1. 判斷元數(shù)據(jù)是否已經(jīng)處于本地cache 且lease 處于有效期內(nèi)1.1 是：直接返回cache 中的元數(shù)據(jù)1.2 否：向中心服務(wù)器節(jié)點(diǎn)請(qǐng)求讀取元數(shù)據(jù)信息1.2.1 服務(wù)器收到讀取請(qǐng)求后，返回元數(shù)據(jù)及一個(gè)對(duì)應(yīng)的lease 1.2.2 客戶端是否成功收到服務(wù)器返回的數(shù)據(jù) 1.2.2.1 失敗或超時(shí)：退出流程，讀取失敗，可重試1.2.2.2 成功：將元數(shù)據(jù)與該元數(shù)據(jù)的lease 記錄到內(nèi)存中，返回元數(shù)據(jù)
2. 基于lease 的cache，客戶端節(jié)點(diǎn)修改元數(shù)據(jù)流程2.1 節(jié)點(diǎn)向服務(wù)器發(fā)起修改元數(shù)據(jù)請(qǐng)求。2.2 服務(wù)器收到修改請(qǐng)求后，阻塞所有新的讀數(shù)據(jù)請(qǐng)求，即接收讀請(qǐng)求，但不返回?cái)?shù)據(jù)。2.3 服務(wù)器等待所有與該元數(shù)據(jù)相關(guān)的lease 超時(shí)。2.4 服務(wù)器修改元數(shù)據(jù)并向客戶端節(jié)點(diǎn)返回修改成功。

上述機(jī)制可以保證各個(gè)節(jié)點(diǎn)上的cache 與中心服務(wù)器上的中心始終一致。這是因?yàn)橹行姆?wù)器節(jié)點(diǎn)在發(fā)送數(shù)據(jù)的同時(shí)授予了節(jié)點(diǎn)對(duì)應(yīng)的lease，在lease 有效期內(nèi)，服務(wù)器不會(huì)修改數(shù)據(jù)，從而客戶端節(jié)點(diǎn)可以放心的在lease 有效期內(nèi)cache 數(shù)據(jù)。上述lease 機(jī)制可以容錯(cuò)的關(guān)鍵是：服務(wù)器一旦 發(fā)出數(shù)據(jù)及l(fā)ease，無論客戶端是否收到，也無論后續(xù)客戶端是否宕機(jī)，也無論后續(xù)網(wǎng)絡(luò)是否正常，服務(wù)器只要等待lease 超時(shí)，就可以保證對(duì)應(yīng)的客戶端節(jié)點(diǎn)不會(huì)再繼續(xù)cache 數(shù)據(jù)，從而可以放心的修改數(shù)據(jù)而不會(huì)破壞cache 的一致性。

上述基礎(chǔ)流程有一些性能和可用性上的問題，但可以很容易就優(yōu)化改性。優(yōu)化點(diǎn)一：服務(wù)器在修改元數(shù)據(jù)時(shí)首先要阻塞所有新的讀請(qǐng)求，造成沒有讀服務(wù)。這是為了防止發(fā)出新的lease 從而引起不斷有新客戶端節(jié)點(diǎn)持有l(wèi)ease 并緩存著數(shù)據(jù)，形成“活鎖”。優(yōu)化的方法很簡單，服務(wù)器在進(jìn)入修改數(shù)據(jù)流程后，一旦收到讀請(qǐng)求則只返回?cái)?shù)據(jù)但不頒發(fā)lease。從而造成在修改流程執(zhí)行的過程中，客戶端可以讀到元數(shù)據(jù)，只是不能緩存元數(shù)據(jù)。進(jìn)一步的優(yōu)化是，當(dāng)進(jìn)入修改流程，服務(wù)器頒發(fā)的lease 有效期限選擇為已發(fā)出的lease 的最大有效期限。這樣做，客戶端可以繼續(xù)在服務(wù)器進(jìn)入修改流程后繼續(xù)緩存元數(shù)據(jù)，但服務(wù)器的等待所有l(wèi)ease 過期的時(shí)間也不會(huì)因?yàn)轭C發(fā)新的lease 而不斷延長。

最后，=cache 機(jī)制與多副本機(jī)制的區(qū)別。Cache 機(jī)制與多副本機(jī)制的相似之處都 是將一份數(shù)據(jù)保存在多個(gè)節(jié)點(diǎn)上。但Cache 機(jī)制卻要簡單許多，對(duì)于cache 的數(shù)據(jù)，可以隨時(shí)刪除丟棄，并命中cache 的后果僅僅是需要訪問數(shù)據(jù)源讀取數(shù)據(jù);然而副本機(jī)制卻不一樣，副本是不能隨意丟棄的，每失去一個(gè)副本，服務(wù)質(zhì)量都在下降，一旦副本數(shù)下降到一定程度，則往往服務(wù)將不再可用。

lease 機(jī)制的分析

lease 的定義：Lease 是由頒發(fā)者授予的在某一有效期內(nèi)的承諾。頒發(fā)者一旦發(fā)出lease，則無論接受方是否收到，也無論后續(xù)接收方處于何種狀態(tài)，只要lease 不過期，頒發(fā)者一定嚴(yán)守承諾;另一方面，接收方在lease 的有效期內(nèi)可以使用頒發(fā)者的承諾，但一旦lease 過期，接收方一定不能繼續(xù)使用頒發(fā)者的承諾。

Lease 機(jī)制具有很高的容錯(cuò)能力。首先，通過引入有效期，Lease 機(jī)制能否非常好的容錯(cuò)網(wǎng)絡(luò)異常。Lease 頒發(fā)過程只依賴于網(wǎng)絡(luò)可以單向通信，即使接收方無法向頒發(fā)者發(fā)送消息，也不影響lease 的頒發(fā)。

由于lease 的有效期是一個(gè)確定的時(shí)間點(diǎn)，lease 的語義與發(fā)送lease 的具體時(shí)間無關(guān)，所以 同一個(gè)lease 可以被頒發(fā)者不斷重復(fù)向接受方發(fā)送。即使頒發(fā)者偶爾發(fā)送lease 失敗，頒發(fā)者也可以 簡單的通過重發(fā)的辦法解決。一旦lease 被接收方成功接受，后續(xù)lease 機(jī)制不再依賴于網(wǎng)絡(luò)通信，即使網(wǎng)絡(luò)完全中斷l(xiāng)ease 機(jī)制也不受影響。

再者，Lease 機(jī)制能較好的容錯(cuò)節(jié)點(diǎn)宕機(jī)。如果頒發(fā)者宕機(jī)，則宕機(jī)的頒發(fā)者通常無法改變之前的承諾，不會(huì)影響lease 的正確性。在頒發(fā)者機(jī)恢復(fù)后，如果頒發(fā)者恢復(fù)出了之前的lease 信息，頒發(fā)者可以繼續(xù)遵守lease 的承諾。如果頒發(fā)者無法恢復(fù)lease 信息，則只需等待一個(gè)最大的lease 超時(shí)時(shí)間就可以使得所有的lease 都失效，從而不破壞lease機(jī)制。

例如上節(jié)中的cache 系統(tǒng)的例子中，一旦服務(wù)器宕機(jī)，肯定不會(huì)修改元數(shù)據(jù)，重新恢復(fù)后，只需等待一個(gè)最大的lease 超時(shí)時(shí)間，所有節(jié)點(diǎn)上的緩存信息都將被清空。

對(duì)于接受方宕機(jī)的情況，頒發(fā)者 不需要做更多的容錯(cuò)處理，只需等待lease 過期失效，就可以收回承諾，實(shí)踐中也就是收回之前賦予的權(quán)限、身份等。最后，lease 機(jī)制不依賴于存儲(chǔ)。頒發(fā)者可以持久化頒發(fā)過的lease 信息，從而在 宕機(jī)恢復(fù)后可以使得在有效期的lease 繼續(xù)有效。但這對(duì)于lease 機(jī)制只是一個(gè)優(yōu)化，如之前的分析，即使頒發(fā)者沒有持久化lease 信息，也可以通過等待一個(gè)最大的lease 時(shí)間的方式使得之前所有頒發(fā) 的lease 失效，從而保證機(jī)制繼續(xù)有效。

Lease 機(jī)制依賴于有效期，這就要求頒發(fā)者和接收者的時(shí)鐘是同步的。一方面，如果頒發(fā)者的 時(shí)鐘比接收者的時(shí)鐘慢，則當(dāng)接收者認(rèn)為lease 已經(jīng)過期的時(shí)候，頒發(fā)者依舊認(rèn)為lease 有效。接收者可以用在lease 到期前申請(qǐng)新的lease 的方式解決這個(gè)問題。另一方面，如果頒發(fā)者的時(shí)鐘比接收 者的時(shí)鐘快，則當(dāng)頒發(fā)者認(rèn)為lease 已經(jīng)過期的時(shí)候，接收者依舊認(rèn)為lease 有效，頒發(fā)者可能將lease 頒發(fā)給其他節(jié)點(diǎn)，造成承諾失效，影響系統(tǒng)的正確性。對(duì)于這種時(shí)鐘不同步，實(shí)踐中的通常做法是將頒發(fā)者的有效期設(shè)置得比接收者的略大，只需大過時(shí)鐘誤差就可以避免對(duì)lease 的有效性的影響。

基于lease 機(jī)制確定節(jié)點(diǎn)狀態(tài)

分布式協(xié)議依賴于對(duì)節(jié)點(diǎn)狀態(tài)認(rèn)知的全局一致性，即一旦節(jié)點(diǎn)Q 認(rèn)為某個(gè)節(jié)點(diǎn) A 異常，則節(jié)點(diǎn)A 也必須認(rèn)為自己異常，從而節(jié)點(diǎn)A 停止作為primary，避免“雙主”問題的出現(xiàn)。

解決這種問題有兩種思路，第一、設(shè)計(jì)的分布式協(xié)議可以容忍“雙主”錯(cuò)誤，即不依賴于對(duì)節(jié)點(diǎn)狀 態(tài)的全局一致性認(rèn)識(shí)，或者全局一致性狀態(tài)是全體協(xié)商后的結(jié)果;

第二、利用lease 機(jī)制。對(duì)于第一 種思路即放棄使用中心化的設(shè)計(jì)，而改用去中心化設(shè)計(jì)，超過本節(jié)的討論范疇。下面著重討論利用 lease 機(jī)制確定節(jié)點(diǎn)狀態(tài)。

由中心節(jié)點(diǎn)向其他節(jié)點(diǎn)發(fā)送lease，若某個(gè)節(jié)點(diǎn)持有有效的lease，則認(rèn)為該節(jié)點(diǎn)正?？梢蕴峁┓?務(wù)。用于例2.3.1 中，節(jié)點(diǎn)A、B、C 依然周期性的發(fā)送heart beat 報(bào)告自身狀態(tài)，節(jié)點(diǎn)Q 收到heart beat 后發(fā)送一個(gè)lease，表示節(jié)點(diǎn)Q 確認(rèn)了節(jié)點(diǎn)A、B、C 的狀態(tài)，并允許節(jié)點(diǎn)在lease 有效期內(nèi)正常工 作。節(jié)點(diǎn)Q 可以給primary 節(jié)點(diǎn)一個(gè)特殊的lease，表示節(jié)點(diǎn)可以作為primary 工作。一旦節(jié)點(diǎn)Q 希望切換新的primary，則只需等前一個(gè)primary 的lease 過期，則就可以安全的頒發(fā)新的lease 給新的 primary 節(jié)點(diǎn)，而不會(huì)出現(xiàn)“雙主”問題。

在實(shí)際系統(tǒng)中，若用一個(gè)中心節(jié)點(diǎn)發(fā)送lease 也有很大的風(fēng)險(xiǎn)，一旦該中心節(jié)點(diǎn)宕機(jī)或網(wǎng)絡(luò)異常，則所有的節(jié)點(diǎn)沒有l(wèi)ease，從而造成系統(tǒng)高度不可用。為此，實(shí)際系統(tǒng)總是使用多個(gè)中心節(jié)點(diǎn)互為副本，成為一個(gè)小的集群，該小集群具有高可用性，對(duì)外提供頒發(fā)lease 的功能。chubby 和zookeeper 都是基于這樣的設(shè)計(jì)。

lease 的有效期時(shí)間選擇

工程中，常選擇的lease 時(shí)長是10 秒級(jí)別，這是一個(gè)經(jīng)過驗(yàn)證的經(jīng)驗(yàn)值，實(shí)踐中可以作為參考并綜合選擇合適的時(shí)長。

2.4 Quorum 機(jī)制

先做這樣的約定：更新操作(write)是一系列順序的過程，通過其他機(jī)制確定更新操作的順序(例如primary-secondary 架構(gòu)中由primary 決定順序)，每個(gè)更新操作記為wi， i 為更新操作單調(diào)遞增的序號(hào)，每個(gè)wi 執(zhí)行成功后副本數(shù)據(jù)都發(fā)生變化，稱為不同的數(shù)據(jù)版本，記 作vi。假設(shè)每個(gè)副本都保存了歷史上所有版本的數(shù)據(jù)。

write-all-read-one

Write-all-read-one(簡稱WARO)是一種最簡單的副本控制規(guī)則，顧名思義即在更新時(shí)寫所有的副本，只有在所有的副本上更新成功，才認(rèn)為更新成功，從而保證所有的副本一致，這樣在讀取數(shù)據(jù)時(shí)可以讀任一副本上的數(shù)據(jù)。

由于更新操作需要在所有的N 個(gè)副本上都成功，更新操作才能成 功，所以一旦有一個(gè)副本異常，更新操作失敗，更新服務(wù)不可用。對(duì)于更新服務(wù)，雖然有N 個(gè)副本， 但系統(tǒng)無法容忍任何一個(gè)副本異常。另一方面，N 個(gè)副本中只要有一個(gè)副本正常，系統(tǒng)就可以提供讀服務(wù)。對(duì)于讀服務(wù)而言，當(dāng)有N 個(gè)副本時(shí)，系統(tǒng)可以容忍N(yùn)-1 個(gè)副本異常。從上述分析可以發(fā)現(xiàn)WARO 讀服務(wù)的可用性較高，但更新服務(wù)的可用性不高，甚至雖然使用了副本，但更新服務(wù)的可用性等效于沒有副本。

Quorum 定義

在Quorum 機(jī)制下，當(dāng)某次更新操作wi 一旦在所有N 個(gè)副本中的W 個(gè)副本上都成功，則就稱 該更新操作為“成功提交的更新操作”，稱對(duì)應(yīng)的數(shù)據(jù)為“成功提交的數(shù)據(jù)”。令R>N-W，由于更新 操作wi 僅在W 個(gè)副本上成功，所以在讀取數(shù)據(jù)時(shí)，最多需要讀取R 個(gè)副本則一定能讀到wi 更新后 的數(shù)據(jù)vi 。如果某次更新wi 在W 個(gè)副本上成功，由于W+R>N，任意R 個(gè)副本組成的集合一定與 成功的W個(gè)副本組成的集合有交集，所以讀取R 個(gè)副本一定能讀到wi 更新后的數(shù)據(jù)vi。

如圖 2-10， Quorum 機(jī)制的原理可以文森圖表示。

 

某系統(tǒng)有5 個(gè)副本，W=3，R=3，最初5 個(gè)副本的數(shù)據(jù)一致，都是v1，某次更新操作 w2 在前3 副本上成功，副本情況變成(v2 v2 v2 v1 v1)。

此時(shí)，任意3 個(gè)副本組成的集合中一定包括 v2。在上述定義中，令W=N，R=1，就得到WARO，即WARO 是Quorum 機(jī)制的一種特例。與分析WARO 相似，分析Quorum 機(jī)制的可用性。限制Quorum 參數(shù)為W+R=N+1。由于更新 操作需要在W 個(gè)副本上都成功，更新操作才能成功，所以一旦N-W+1 個(gè)副本異常，更新操作始終無法在W 個(gè)副本上成功，更新服務(wù)不可用。

另一方面，一旦N-R+1 個(gè)副本異常，則無法保證一定可以讀到與W 個(gè)副本有交集的副本集合，則讀服務(wù)的一致性下降。

再次強(qiáng)調(diào)：僅僅依賴quorum 機(jī)制是無法保證強(qiáng)一致性的。因?yàn)閮H有quorum 機(jī)制時(shí)無法確定最新已成功提交的版本號(hào)，除非將最新已提交的版本號(hào)作為元數(shù)據(jù)由特定的元數(shù)據(jù)服務(wù)器或元數(shù)據(jù)集群管理，否則很難確定最新成功提交的版本號(hào)。在下一節(jié)中，將討論在哪些情況下，可以僅僅 通過quorum 機(jī)制來確定最新成功提交的版本號(hào)。

Quorum 機(jī)制的三個(gè)系統(tǒng)參數(shù)N、W、R 控制了系統(tǒng)的可用性，也是系統(tǒng)對(duì)用戶的服務(wù)承諾：數(shù)據(jù)最多有N 個(gè)副本，但數(shù)據(jù)更新成功W 個(gè)副本即返回用戶成功。對(duì)于一致性要求較高的Quorum 系統(tǒng)，系統(tǒng)還應(yīng)該承諾任何時(shí)候不讀取未成功提交的數(shù)據(jù)，即讀取到的數(shù)據(jù)都是曾經(jīng)在W 個(gè)副本上成功的數(shù)據(jù)。

讀取最新成功提交的數(shù)據(jù)

Quorum 機(jī)制只需成功更新N 個(gè)副本中的W 個(gè)，在讀取R 個(gè)副本時(shí)，一定可以讀到最新的成功提交的數(shù)據(jù)。但由于有不成功的更新情況存在，僅僅讀取R 個(gè)副本卻不一定能確定哪個(gè)版本的數(shù)據(jù) 是最新的已提交的數(shù)據(jù)。對(duì)于一個(gè)強(qiáng)一致性Quorum 系統(tǒng)，若存在個(gè)數(shù)據(jù)少于W 個(gè)，假設(shè)為X 個(gè)，則繼續(xù)讀取其他副本，直若成功讀取到W 個(gè) 該版本的副本，則該數(shù)據(jù)為最新的成功提交的數(shù)據(jù);如果在所有副本中該數(shù)據(jù)的個(gè)數(shù)肯定不滿 足W 個(gè)，則R 中版本號(hào)第二大的為最新的成功提交的副本。

例：在讀取到(v2 v1 v1)時(shí)，繼續(xù)讀取剩余的副本，若讀到剩余兩個(gè)副本 為(v2 v2)則v2 是最新的已提交的副本;若讀到剩余的兩個(gè)副本為(v2 v1)或(v1 v1)則v1 是最新成功提交的版本;若讀取后續(xù)兩個(gè)副本有任一超時(shí)或失敗，則無法判斷哪個(gè)版本是最新的成功提交的版本。

可以看出，在單純使用Quorum 機(jī)制時(shí)，若要確定最新的成功提交的版本，最多需要讀取R+ (W-R-1)=N 個(gè)副本，當(dāng)出現(xiàn)任一副本異常時(shí)，讀最新的成功提交的版本這一功能都有可能不可用。

實(shí)際工程中，應(yīng)該盡量通過其他技術(shù)手段，回避通過Quorum 機(jī)制讀取最新的成功提交的版本。例如，當(dāng)quorum 機(jī)制與primary-secondary 控制協(xié)議結(jié)合使用時(shí)，可以通過讀取primary 的方式讀取到最新的已提交的數(shù)據(jù)。

基于Quorum 機(jī)制選擇primary副本

讀取數(shù)據(jù)時(shí)依照一致性要求的不同可以有不同的做法：如果需要強(qiáng)一致性的立刻讀取到最新的成功提交的數(shù)據(jù)，則可以簡單的只讀取primary 副本上的數(shù)據(jù)即可，也可以通過上節(jié)的方式讀取;

如果需要會(huì)話一致性，則可以根據(jù)之前已經(jīng)讀到的數(shù)據(jù)版本號(hào)在各個(gè)副本上進(jìn)行選擇性讀取;如果只需要弱一致性，則可以選擇任意副本讀取。

在primary-secondary 協(xié)議中，當(dāng)primary 異常時(shí)，需要選擇出一個(gè)新的primary，之后secondary 副本與primary 同步數(shù)據(jù)。

通常情況下，選擇新的primary 的工作是由某一中心節(jié)點(diǎn)完成的，在引入 quorum 機(jī)制后，常用的primary 選擇方式與讀取數(shù)據(jù)的方式類似，即中心節(jié)點(diǎn)讀取R 個(gè)副本，選擇 R 個(gè)副本中版本號(hào)最高的副本作為新的primary。新primary 與至少W 個(gè)副本完成數(shù)據(jù)同步后作為新的primary 提供讀寫服務(wù)。

首先，R 個(gè)副本中版本號(hào)最高的副本一定蘊(yùn)含了最新的成功提交的數(shù)據(jù)。再者，雖然不能確定最高版本號(hào)的數(shù)是一個(gè)成功提交的數(shù)據(jù)，但新的primary 在隨后與secondary 同 步數(shù)據(jù)，使得該版本的副本個(gè)數(shù)達(dá)到W，從而使得該版本的數(shù)據(jù)成為成功提交的數(shù)據(jù)。

例：在N=5，W=3，R=3 的系統(tǒng)中，某時(shí)刻副本最大版本號(hào)為(v2 v2 v1 v1 v1)，此時(shí)v1 是系統(tǒng)的最新的成功提交的數(shù)據(jù)，v2 是一個(gè)處于中間狀態(tài)的未成功提交的數(shù)據(jù)。假設(shè)此刻原primary 副本異常，中心節(jié)點(diǎn)進(jìn)行primary 切換工作。這類“中間態(tài)”數(shù)據(jù)究竟作為“臟數(shù)據(jù)”被刪除，還是作為新的數(shù)據(jù)被同步后成為生效的數(shù)據(jù)，完全取決于這個(gè)數(shù)據(jù)能否參與新primary 的選舉。下面分別分析這兩種情況。

 

第一、如圖 2-12，若中心節(jié)點(diǎn)與其中3 個(gè)副本通信成功，讀取到的版本號(hào)為(v1 v1 v1)，則任 選一個(gè)副本作為primary，新primary 以v1 作為最新的成功提交的版本并與其他副本同步，當(dāng)與第1、第2 個(gè)副本同步數(shù)據(jù)時(shí)，由于第1、第2 個(gè)副本版本號(hào)大于primary，屬于臟數(shù)據(jù)，可以按照2.2.2.4 節(jié)中介紹的處理臟數(shù)據(jù)的方式解決。

實(shí)踐中，新primary 也有可能與后兩個(gè)副本完成同步后就提供數(shù)據(jù)服務(wù)，隨后自身版本號(hào)也更新到v2，如果系統(tǒng)不能保證之后的v2 與之前的v2 完全一樣，則新 primary 在與第1、2 個(gè)副本同步數(shù)據(jù)時(shí)不但要比較數(shù)據(jù)版本號(hào)還需要比較更新操作的具體內(nèi)容是否一樣。

 

第二、若中心節(jié)點(diǎn)與其他3 個(gè)副本通信成功，讀取到的版本號(hào)為(v2 v1 v1)，則選取版本號(hào)為 v2 的副本作為新的primary，之后，一旦新primary 與其他2 個(gè)副本完成數(shù)據(jù)同步，則符合v2 的副 本個(gè)數(shù)達(dá)到W 個(gè)，成為最新的成功提交的副本，新primary 可以提供正常的讀寫服務(wù)。

2.5 日志技術(shù)

日志技術(shù)是宕機(jī)恢復(fù)的主要技術(shù)之一。日志技術(shù)最初使用在數(shù)據(jù)庫系統(tǒng)中。嚴(yán)格來說日志技術(shù)不是一種分布式系統(tǒng)的技術(shù)，但在分布式系統(tǒng)的實(shí)踐中，卻廣泛使用了日志技術(shù)做宕機(jī)恢復(fù)，甚 至如BigTable 等系統(tǒng)將日志保存到一個(gè)分布式系統(tǒng)中進(jìn)一步增強(qiáng)了系統(tǒng)容錯(cuò)能力。

Redo Log 與Check point

設(shè)計(jì)一個(gè)高速的單機(jī)查詢系統(tǒng)，將數(shù)據(jù)全部存放在內(nèi)存中以實(shí)現(xiàn)高速的數(shù)據(jù)查詢，每次更新操作更新一小部分?jǐn)?shù)據(jù)(例如 key-value 中的某一個(gè)key)。現(xiàn)在問題為利用日志技術(shù)實(shí)現(xiàn)該內(nèi)存查詢系統(tǒng)的宕機(jī)恢復(fù)。與數(shù)據(jù)庫的事務(wù)不同的是，這個(gè)問題模型中的每個(gè)成功的更新操作都會(huì)生效。這也等效為數(shù)據(jù)庫的每個(gè)事務(wù)只有一個(gè)更新操作，且每次更新操作都可以也必須立即提交(Auto commit)。

Redo Log

• 將更新操作的結(jié)果(例如Set K1=1，則記錄K1=1)以追加寫(append)的方式寫入磁盤的 日志文件
• 按更新操作修改內(nèi)存中的數(shù)據(jù)
• 返回更新成功

從Redo Log 的流程可以看出，Redo 寫入日志的是更新操作完成后的結(jié)果(雖然本文不討論Undo Log，這點(diǎn)是與Undo Log 的區(qū)別之一)，且由于是順序追加寫日志文件，在磁盤等對(duì)順序?qū)懹辛Φ?存儲(chǔ)設(shè)備上效率較高。

用Redo Log 進(jìn)行宕機(jī)恢復(fù)非常簡單，只需要“回放”日志即可。

流程2.5.2：Redo Log 的宕機(jī)恢復(fù)

從頭讀取日志文件中的每次更新操作的結(jié)果，用這些結(jié)果修改內(nèi)存中的數(shù)據(jù)。

從Redo Log 的宕機(jī)恢復(fù)流程也可以看出，只有寫入日志文件的更新結(jié)果才能在宕機(jī)后恢復(fù)。這也是為什么在Redo Log 流程中需要先更新日志文件再更新內(nèi)存中的數(shù)據(jù)的原因。

假如先更新內(nèi)存中的數(shù)據(jù)，那么用戶立刻就能讀到更新后的數(shù)據(jù)，一旦在完成內(nèi)存修改與寫入日志之間發(fā)生宕機(jī)，那么最后一次更新操作無法恢復(fù)，但之前用戶可能已經(jīng)讀取到了更新后的數(shù)據(jù)，從而引起不一致的問題。

Check point

在簡化的模型下，check point 技術(shù)的過程即將內(nèi)存中的數(shù)據(jù)以某種易于重新加載的數(shù)據(jù)組織方式完整的dump 到磁盤，從而減少宕機(jī)恢復(fù)時(shí)需要回放的日志數(shù)據(jù)。

流程：check point

1. 向日志文件中記錄“Begin Check Point”
2. 將內(nèi)存中的數(shù)據(jù)以某種易于重新加載的數(shù)據(jù)組織方式dump 到磁盤上
3. 向日志文件中記錄“End Check Point” 在check point 流程中，數(shù)據(jù)可以繼續(xù)按照流程2.5.1 被更新，這段過程中新更新的數(shù)據(jù)可以dump 到磁盤也可以不dump 到磁盤，具體取決于實(shí)現(xiàn)。例如，check point 開始時(shí)k1=v1，check point 過程 中某次更新為k1 = v2，那么dump 到磁盤上的k1 的值可以是v1 也可以是v2。

流程：基于check point 的宕機(jī)恢復(fù)流程

將dump 到磁盤的數(shù)據(jù)加載到內(nèi)存。

從后向前掃描日志文件，尋找最后一個(gè)“End Check Point”日志。

從最后一個(gè)“End Check Point”日志向前找到最近的一個(gè)“Begin Check Point”日志，并回 放該日志之后的所有更新操作日志。

No Undo/No Redo log

若數(shù)據(jù)維護(hù)在磁盤中，某批更新由若干個(gè)更新操作組成，這些更新操作需要原子生效，即要么同時(shí)生效，要么都不生效。

 

0/1 目錄技術(shù)中有兩個(gè)目錄結(jié)構(gòu)，稱為目錄0(Directory 0)和目錄1(Directory 1)。另有一個(gè)結(jié)構(gòu)稱為主記錄(Master record)記錄當(dāng)前正在使用的目錄稱為活動(dòng)目錄。主記錄中要么記錄使用目錄0，要么記錄使用目錄1。目錄0 或目錄1 中記錄了各個(gè)數(shù)據(jù)的在日志文件中的位置。0/1 目錄的數(shù)據(jù)更新過程始終在非活動(dòng)目錄上進(jìn)行，只是在數(shù)據(jù)生效前，將主記錄中的0、1 值反轉(zhuǎn)，從而切換主記錄。

流程：0/1 目錄數(shù)據(jù)更新流程

1. 將活動(dòng)目錄完整拷貝到非活動(dòng)目錄。
2. 對(duì)于每個(gè)更新操作，新建一個(gè)日志項(xiàng)紀(jì)錄操作后的值，并在非活動(dòng)目錄中將相應(yīng)數(shù)據(jù)的位置修改為新建的日志項(xiàng)的位置。
3. 原子性修改主記錄：反轉(zhuǎn)主記錄中的值，使得非活動(dòng)目錄生效。

0/1 目錄的更新流程非常簡單，通過0、1 目錄的主記錄切換使得一批修改的生效是原子的。0/1 目錄將批量事務(wù)操作的原子性通過目錄手段歸結(jié)到主記錄的原子切換。

由于多條記錄的原子修改一般較難實(shí)現(xiàn)而單條記錄的原子修改往往可以實(shí)現(xiàn)，從而降低了問題實(shí)現(xiàn)的難度。

在工程中0/1 目錄的思想運(yùn)用非常廣泛，其形式也不局限在上述流程中，可以是內(nèi)存中的兩個(gè)數(shù)據(jù)結(jié)構(gòu)來回切換，也可以是磁盤上的兩個(gè)文件目錄來回生效切換。

2.6 兩階段提交協(xié)議

兩階段提交協(xié)議是一種經(jīng)典的強(qiáng)一致性中心化副本控制協(xié)議。雖然在工程中該協(xié)議有較多的問題，但研究該協(xié)議能很好的理解分布式系統(tǒng)的幾個(gè)典型問題。

流程描述

兩階段提交協(xié)議是一種典型的“中心化副本控制”協(xié)議。在該協(xié)議中，參與的節(jié)點(diǎn)分為兩類：一個(gè)中心化協(xié)調(diào)者節(jié)點(diǎn)(coordinator)和N 個(gè)參與者節(jié)點(diǎn)(participant)。每個(gè)參與者節(jié)點(diǎn)即上文背景介紹中的管理數(shù)據(jù)庫副本的節(jié)點(diǎn)。

兩階段提交的思路比較簡單，在第一階段，協(xié)調(diào)者詢問所有的參與者是否可以提交事務(wù)(請(qǐng)參與者投票)，所有參與者向協(xié)調(diào)者投票。

在第二階段，協(xié)調(diào)者根據(jù)所有參與者的投票結(jié)果做出是否事務(wù)可以全局提交的決定，并通知所有的參與者執(zhí)行該決定。在一個(gè)兩階段提交流程中，參與者不能改變自己的投票結(jié)果。

兩階段提交協(xié)議的可以全局提交的前提是所有的參與者都同意提交事務(wù)，只要有一個(gè)參與者投票選擇放棄(abort)事務(wù)，則事務(wù)必須被放棄。

流程：兩階段提交協(xié)調(diào)者流程

1. 寫本地日志“begin_commit”，并進(jìn)入WAIT 狀態(tài);
2. 向所有參與者發(fā)送“prepare 消息”;
3. 等待并接收參與者發(fā)送的對(duì)“prepare 消息”的響應(yīng);3.1 若收到任何一個(gè)參與者發(fā)送的“vote-abort 消息”;3.1.1 寫本地“global-abort”日志，進(jìn)入ABORT;3.1.2 向所有的參與者發(fā)送“global-abort 消息”;3.1.3 進(jìn)入ABORT 狀態(tài);3.2 若收到所有參與者發(fā)送的“vote-commit”消息;3.2.1 寫本地“global-commit”日志，進(jìn)入COMMIT 狀態(tài);3.1.2 向所有的參與者發(fā)送“global-commit 消息”;
4. 等待并接收參與者發(fā)送的對(duì)“global-abort 消息”或“global-commit 消息”的確認(rèn)響應(yīng)消息，一旦收到所有參與者的確認(rèn)消息，寫本地“end_transaction” 日志流程結(jié)束。

流程：兩階段提交協(xié)調(diào)者流程

1. 寫本地日志“init”記錄，進(jìn)入INIT 狀態(tài)
2. 等待并接受協(xié)調(diào)者發(fā)送的“prepare 消息”，收到后 2.1 若參與者可以提交本次事務(wù) 2.1.1 寫本地日志“ready”，進(jìn)入READY 狀態(tài) 2.1.2 向協(xié)調(diào)者發(fā)送“vote-commit”消息 2.1.4 等待協(xié)調(diào)者的消息2.1.4.1 若收到協(xié)調(diào)者的“global-abort”消息2.1.4.1.1 寫本地日志“abort”，進(jìn)入ABORT 狀態(tài)2.1.4.1.2 向協(xié)調(diào)者發(fā)送對(duì)“global-abort”的確認(rèn)消息 2.1.4.2 若收到協(xié)調(diào)者的“global-commit”消息2.1.4.1.1 寫本地日志“commit”，進(jìn)入COMMIT 狀態(tài) 2.1.4.1.2 向協(xié)調(diào)者發(fā)送對(duì)“global-commit”的確認(rèn)消息 2.2 若參與者無法提交本次事務(wù) 2.2.1 寫本地日志“abort”，進(jìn)入ABORT 狀態(tài) 2.2.2 向協(xié)調(diào)者發(fā)送“vote-abort”消息 2.2.3 流程對(duì)該參與者結(jié)束 2.2.4 若后續(xù)收到協(xié)調(diào)者的“global-abort”消息可以響應(yīng)
3. 即使流程結(jié)束，但任何時(shí)候收到協(xié)調(diào)者發(fā)送的“global-abort”消息或“global-commit”消息也都要發(fā)送一個(gè)對(duì)應(yīng)的確認(rèn)消息。

異常處理

宕機(jī)恢復(fù)

1. 協(xié)調(diào)者宕機(jī)恢復(fù) 協(xié)調(diào)者宕機(jī)恢復(fù)后，首先通過日志查找到宕機(jī)前的狀態(tài)。如果日志中最后是“begin_commit”記錄，說明宕機(jī)前協(xié)調(diào)者處于WAIT 狀態(tài)，協(xié)調(diào)者可能已經(jīng)發(fā)送過“prepare 消息”也可能還沒發(fā)送，但協(xié)調(diào)者一定還沒有發(fā)送過“global-commit 消息”或“global-abort 消息”，即事務(wù)的全局狀態(tài)還沒有確定。此時(shí)，協(xié)調(diào)者可以重新發(fā)送“prepare 消息” 繼續(xù)兩階段提交流程，即使參與者已經(jīng)發(fā)送過對(duì)“prepare 消息”的響應(yīng)，也不過是再次重傳之前的響應(yīng)而不會(huì)影響協(xié)議的一致性。如果日志中最后是“global-commit”或“global-abort”記錄，說明宕機(jī)前協(xié)調(diào)者處于COMMIT 或ABORT 狀態(tài)。此時(shí)協(xié)調(diào)者只需重新向所有的參與者發(fā)送“global-commit 消息”或“global-abort 消息”就可以繼續(xù)兩階段提交流程。
2. 參與者宕機(jī)恢復(fù)參與者宕機(jī)恢復(fù)后，首先通過日志查找宕機(jī)前的狀態(tài)。如果日志中最后是“init”記錄，說明參與者處于INIT 狀態(tài)，還沒有對(duì)本次事務(wù)做出投票選擇，參與者可以繼續(xù)流程等待協(xié)調(diào)者發(fā)送的“prepare 消息”。如果日志中最后是“ready”記錄，說明參與者處于REDAY 狀態(tài)，此時(shí)說明參與者已經(jīng)就本次 事務(wù)做出了投票選擇，但宕機(jī)前參與者是否已經(jīng)向協(xié)調(diào)者發(fā)送“vote-commit”消息并不可知。所以此時(shí)參與者可以向協(xié)調(diào)者重發(fā)“vote-commit”，并繼續(xù)協(xié)議流程。如果日志中最后是“commit”或“abort”記錄，說明參與者已經(jīng)收到過協(xié)調(diào)者的“global-commit 消息”(處于COMMIT 狀態(tài))或者“global-abort 消息”(處于ABORT 狀態(tài))。至于是否向協(xié)調(diào)者發(fā) 送過對(duì)“global-commit”或“global-abort”的確認(rèn)消息則未知。但即使沒有發(fā)送過確認(rèn)消息，由于協(xié)調(diào)者會(huì)不斷重發(fā)“global-commit”或“global-abort”，只需在收到這些消息時(shí)發(fā)送確認(rèn)消息既可，不影響協(xié)議的全局一致性。

協(xié)議分析

兩階段提交協(xié)議在工程實(shí)踐中真正使用的較少，主要原因有以下幾點(diǎn)：

1. 兩階段提交協(xié)議的容錯(cuò)能力較差。從上文的分析可以看出，兩階段提交協(xié)議在某些情況下存在流程無法執(zhí)行下去的情況，且也無法判斷流程狀態(tài)。在工程中好的分布式協(xié)議往往總是可以在即使發(fā)生異常的情況下也能執(zhí)行下去。例如，回憶Lease 機(jī)制(2.3 )，一旦lease 發(fā)出，無論出現(xiàn)任何異常，Lease 服務(wù)器節(jié)點(diǎn)總是可以通過時(shí)間判定出Lease 是否有效，也可以用等待Lease 超時(shí)的方法收回Lease 權(quán)限，整個(gè)Lease 協(xié)議的流程不存在任何流程被阻塞而無法執(zhí)行下去的情況。與Lease 機(jī)制的簡單有效相比，兩階段提交的協(xié)議顯得較為復(fù)雜且容錯(cuò)能力差。
2. 兩階段提交協(xié)議的性能較差。一次成功的兩階段提交協(xié)議流程中，協(xié)調(diào)者與每個(gè)參與者 之間至少需要兩輪交互4 個(gè)消息“prepare”、“vote-commit”、“global-commit”、“確認(rèn)global-commit”。過多的交互次數(shù)會(huì)降低性能。另一方面，協(xié)調(diào)者需要等待所有的參與者的投票結(jié)果，一旦存在較慢的參與者，會(huì)影響全局流程執(zhí)行速度。

雖然存在一些改進(jìn)的兩階段提交協(xié)議可以提高容錯(cuò)能力和性能，然而這類協(xié)議依舊是在工程中使用較少的一類協(xié)議，其理論價(jià)值大于實(shí)踐意義。

2.7 MVCC

MVCC(Multi-version Cocurrent Control，多版本并發(fā)控制)技術(shù)。MVCC 技術(shù)最初也是在數(shù)據(jù)庫系統(tǒng)中被提出，但這種思想并不局限于單機(jī)的分布式系統(tǒng)，在分布式系統(tǒng)中同樣有效。

MVCC 即多個(gè)不同版本的數(shù)據(jù)實(shí)現(xiàn)并發(fā)控制的技術(shù)，其基本思想是為每次事務(wù)生成 一個(gè)新版本的數(shù)據(jù)，在讀數(shù)據(jù)時(shí)選擇不同版本的數(shù)據(jù)即可以實(shí)現(xiàn)對(duì)事務(wù)結(jié)果的完整性讀取。在使用MVCC 時(shí)，每個(gè)事務(wù)都是基于一個(gè)已生效的基礎(chǔ)版本進(jìn)行更新，事務(wù)可以并行進(jìn)行，從而可以產(chǎn)生一種圖狀結(jié)構(gòu)。

 

基礎(chǔ)數(shù)據(jù)的版本為1，同時(shí)產(chǎn)生了兩個(gè)事務(wù)：事務(wù)A 與事務(wù)B。這兩個(gè)事務(wù)都各自對(duì)數(shù)據(jù)進(jìn)行了一些本地修改(這些修改只有事務(wù)自己可見，不影響真正的數(shù)據(jù))，之后事務(wù)A 首先提交，生成數(shù)據(jù)版本2;基于數(shù)據(jù)版本2，又發(fā)起了事務(wù)C，事務(wù)C 繼續(xù)提交，生成了數(shù)據(jù)版 本3;最后事務(wù)B 提交，此時(shí)事務(wù)B 的結(jié)果需要與事務(wù)C 的結(jié)果合并，如果數(shù)據(jù)沒有沖突，即事務(wù) B 沒有修改事務(wù)A 與事務(wù)C 修改過的變量，那么事務(wù)B 可以提交，否則事務(wù)B 提交失敗。MVCC 的流程過程非常類似于SVN 等版本控制系統(tǒng)的流程，或者說SVN 等版本控制系統(tǒng)就是 使用的MVCC 思想。事務(wù)在基于基礎(chǔ)數(shù)據(jù)版本做本地修改時(shí)，為了不影響真正的數(shù)據(jù)，通常有兩種做法，一是將基礎(chǔ)數(shù)據(jù)版本中的數(shù)據(jù)完全拷貝出來再修改，SVN 即使用了這種方法，SVN check out 即是拷貝的過程;二是每個(gè)事務(wù)中只記錄更新操作，而不記錄完整的數(shù)據(jù)，讀取數(shù)據(jù)時(shí)再將更新操作應(yīng)用到用基礎(chǔ)版本的數(shù)據(jù)從而計(jì)算出結(jié)果，這個(gè)過程也類似SVN 的增量提交。

2.8 Paxos協(xié)議

Paxos 協(xié)議是少數(shù)在工程實(shí)踐中證實(shí)的強(qiáng)一致性、高可用的去中心化分布式協(xié)議。Paxos 協(xié)議的流程較為復(fù)雜，但其基本思想?yún)s不難理解，類似于人類社會(huì)的投票過程。Paxos 協(xié)議中，有一組完全對(duì)等的參與節(jié)點(diǎn)(稱為accpetor)，這組節(jié)點(diǎn)各自就某一事件做出決議，如果某個(gè)決議獲得了超過半數(shù)節(jié)點(diǎn)的同意則生效。Paxos 協(xié)議中只要有超過一半的節(jié)點(diǎn)正常，就可以工作，能很好對(duì)抗宕機(jī)、網(wǎng)絡(luò)分化等異常情況。

角色

Proposer：提案者。Proposer 可以有多個(gè)，Proposer 提出議案(value)。所謂value，在工程中可以是任何操作，例如“修改某個(gè)變量的值為某個(gè)值”、“設(shè)置當(dāng)前primary 為某個(gè)節(jié)點(diǎn)”等等。Paxos 協(xié)議中統(tǒng)一將這些操作抽象為value。不同的Proposer 可以提出不同的甚至矛盾的value，例如某個(gè)Proposer 提議“將變量X 設(shè)置為1”，另一個(gè)Proposer 提議“將變量X 設(shè)置為2”，但對(duì)同一輪Paxos 過程，最多只有一個(gè)value 被批準(zhǔn)。Acceptor：批準(zhǔn)者。Acceptor 有N 個(gè)，Proposer 提出的value 必須獲得超過半數(shù)(N/2+1)的Acceptor 批準(zhǔn)后才能通過。Acceptor 之間完全對(duì)等獨(dú)立。Learner：學(xué)習(xí)者。Learner 學(xué)習(xí)被批準(zhǔn)的value。所謂學(xué)習(xí)就是通過讀取各個(gè)Proposer 對(duì)value 的選擇結(jié)果，如果某個(gè)value 被超過半數(shù)Proposer 通過，則Learner 學(xué)習(xí)到了這個(gè)value?；貞?2.4 ) 不難理解，這里類似Quorum 機(jī)制，某個(gè)value 需要獲得W=N/2 + 1 的Acceptor 批準(zhǔn)，從而學(xué)習(xí)者需要至少讀取N/2+1 個(gè)Accpetor，至多讀取N 個(gè)Acceptor 的結(jié)果后，能學(xué)習(xí)到一個(gè)通過的value。上述三類角色只是邏輯上的劃分，實(shí)踐中一個(gè)節(jié)點(diǎn)可以同時(shí)充當(dāng)這三類角色。

流程

Paxos 協(xié)議一輪一輪的進(jìn)行，每輪都有一個(gè)編號(hào)。每輪Paxos 協(xié)議可能會(huì)批準(zhǔn)一個(gè)value，也可 能無法批準(zhǔn)一個(gè)value。如果某一輪Paxos 協(xié)議批準(zhǔn)了某個(gè)value，則以后各輪Paxos 只能批準(zhǔn)這個(gè) value。上述各輪協(xié)議流程組成了一個(gè)Paxos 協(xié)議實(shí)例，即一次Paxos 協(xié)議實(shí)例只能批準(zhǔn)一個(gè)value，這也是Paxos 協(xié)議強(qiáng)一致性的重要體現(xiàn)。每輪Paxos 協(xié)議分為階段，準(zhǔn)備階段和批準(zhǔn)階段，在這兩個(gè)階段Proposer 和Acceptor 有各自的處理流程。

流程：Proposer 的流程 (準(zhǔn)備階段)

1. 向所有的Acceptor 發(fā)送消息“Prepare(b)”;這里b 是Paxos 的輪數(shù)，每輪遞增
2. 如果收到任何一個(gè)Acceptor 發(fā)送的消息“Reject(B)”，則對(duì)于這個(gè)Proposer 而言本輪Paxos 失敗，將輪數(shù)b 設(shè)置為B+1 后重新步驟1;(批準(zhǔn)階段，根據(jù)收到的Acceptor 的消息作出不同選擇)
3. 如果接收到的Acceptor 的“Promise(b, v_i)”消息達(dá)到N/2+1 個(gè)(N 為Acceptor 總數(shù)，除法取整， 下同);v_i 表示Acceptor 最近一次在i 輪批準(zhǔn)過value v。3.1 如果收到的“Promise(b, v)”消息中，v 都為空，Proposer 選擇一個(gè)value v，向所有Acceptor 廣播Accept(b, v);3.2 否則，在所有收到的“Promise(b, v_i)”消息中，選擇i 最大的value v，向所有Acceptor 廣播消息Accept(b，v);
4. 如果收到Nack(B)，將輪數(shù)b 設(shè)置為B+1 后重新步驟1;

流程：Accpetor 流程 (準(zhǔn)備階段)

1. 接受某個(gè)Propeser 的消息Prepare(b)。參數(shù)B 是該Acceptor 收到的最大Paxos 輪數(shù)編號(hào);V 是Acceptor 批準(zhǔn)的value，可以為空 1.1 如果b>B，回復(fù)Promise(b, V_B)，設(shè)置B=b; 表示保證不再接受編號(hào)小于b 的提案。1.2 否則，回復(fù)Reject(B) (批準(zhǔn)階段)
2. 接收Accept(b, v)， 2.1 如果b < B, 回復(fù)Nack(B)，暗示proposer 有一個(gè)更大編號(hào)的提案被這個(gè)Acceptor 接收了 2.2 否則設(shè)置V=v。表示這個(gè)Acceptor 批準(zhǔn)的Value 是v。廣播Accepted 消息。

例子

基本例子里有5 個(gè)Acceptor，1 個(gè)Proposer，不存在任何網(wǎng)絡(luò)、宕機(jī)異常。我們著重考察各個(gè)Accpetor 上變量B 和變量V 的變化，及Proposer 上變量b 的變化。

1. 初始狀態(tài)
2. Proposer 向所有Accpetor 發(fā)送“Prepare(1)”，所有Acceptor 正確處理，并回復(fù)Promise(1, NULL
3. Proposer 收到5 個(gè)Promise(1, NULL)，滿足多余半數(shù)的Promise 的value 為空，此時(shí)發(fā)送 Accept(1, v1)，其中v1 是Proposer 選擇的Value。
4. 此時(shí)，v1 被超過半數(shù)的Acceptor 批準(zhǔn)，v1 即是本次Paxos 協(xié)議實(shí)例批準(zhǔn)的Value。如果Learner 學(xué)習(xí)value，學(xué)到的只能是v1

在同一個(gè)Paxos 實(shí)例中，批準(zhǔn)的Value 是無法改變的，即使后續(xù)Proposer 以更高的序號(hào)發(fā)起Paxos 協(xié)議也無法改變value。Paxos 協(xié)議的核心就在于“批準(zhǔn)的value 無法改變”，這也是整個(gè)協(xié)議正確性的基礎(chǔ)。

Paxos 協(xié)議是被人為設(shè)計(jì)出來，其設(shè)計(jì)過程也是協(xié)議的推導(dǎo)過程。Paxos 協(xié)議利用了Quorom 機(jī) 制，選擇的W=R=N/2+1。

簡單而言，協(xié)議就是Proposer 更新Acceptor 的過程，一旦某個(gè)Acceptor 成功更新了超過半數(shù)的Acceptor，則更新成功。Learner 按Quorum 去讀取Acceptor，一旦某個(gè)value 在超過半數(shù)的Proposer 上被成功讀取，則說明這是一個(gè)被批準(zhǔn)的value。協(xié)議通過引入輪次，使得高輪次的提議搶占低輪次的提議來避免死鎖。協(xié)議設(shè)計(jì)關(guān)鍵點(diǎn)是如何滿足“在一次Paxos 算法實(shí)例過程中只批準(zhǔn)一個(gè)Value”這一約束條件。

2.9 CAP

CAP 理論的定義很簡單，CAP 三個(gè)字母分別代表了分布式系統(tǒng)中三個(gè)相互矛盾的屬性：

1. Consistency (一致性)：CAP 理論中的副本一致性特指強(qiáng)一致性(1.3.4 );
2. Availiablity(可用性)：指系統(tǒng)在出現(xiàn)異常時(shí)已經(jīng)可以提供服務(wù);
3. Tolerance to the partition of network (分區(qū)容忍)：指系統(tǒng)可以對(duì)網(wǎng)絡(luò)分區(qū)(1.1.4.2 )這種異常情 況進(jìn)行容錯(cuò)處理;

CAP 理論指出：無法設(shè)計(jì)一種分布式協(xié)議，使得同時(shí)完全具備CAP 三個(gè)屬性，即1)該種協(xié)議下的副本始終是強(qiáng)一致性，2)服務(wù)始終是可用的，3)協(xié)議可以容忍任何網(wǎng)絡(luò)分區(qū)異常;分布式系統(tǒng)協(xié)議只能在CAP 這三者間所有折中。

熱力學(xué)第二定律說明了永動(dòng)機(jī)是不可能存在的，不要去妄圖設(shè)計(jì)永動(dòng)機(jī)。與之類似，CAP 理論的意義就在于明確提出了不要去妄圖設(shè)計(jì)一種對(duì)CAP 三大屬性都完全擁有的完美系統(tǒng)，因?yàn)檫@種系統(tǒng)在理論上就已經(jīng)被證明不存在。

• Lease 機(jī)制: Lease 機(jī)制犧牲了部分異常情況下的A，從而獲得了完全的C 與很好的P。
• Quorum 機(jī)制: Quorum 機(jī)制，在CAP 三大因素中都各做了折中，有一定的C，有較好 的A，也有較好的P，是一種較為平衡的分布式協(xié)議。
• 兩階段提交協(xié)議: 兩階段提交系統(tǒng)具有完全的C，很糟糕的A，很糟糕的P。
• Paxos 協(xié)議：同樣是強(qiáng)一致性協(xié)議，Paxos 在CAP 三方面較之兩階段提交協(xié)議要優(yōu)秀得多。Paxos 協(xié)議具有 完全的C，較好的A，較好的P。Paxos 的A 與P 的屬性與Quorum 機(jī)制類似，因?yàn)镻axos 的協(xié)議本 身就具有Quorum 機(jī)制的因素