[[274519]]

1. 分布式系統(tǒng)相關(guān)概念

1.1 模型

 

1.1.1 節(jié)點(diǎn)

節(jié)點(diǎn)是一個(gè)可以獨(dú)立按照分布式協(xié)議完成一組邏輯的程序個(gè)體，工程中往往指進(jìn)程。

1.1.2 通信

節(jié)點(diǎn)之間完全獨(dú)立互相隔離，通信唯一方式是通過不可靠的網(wǎng)絡(luò)。

1.1.3 存儲(chǔ)

節(jié)點(diǎn)可以通過將數(shù)據(jù)寫入與節(jié)點(diǎn)在同一臺(tái)機(jī)器的本地存儲(chǔ)設(shè)備保存數(shù)據(jù)

1.1.4 異常

(1) 機(jī)器down機(jī)

大型集群每日down機(jī)發(fā)生概率0.1%，后果是該機(jī)器節(jié)點(diǎn)不能工作、重啟后失去所有內(nèi)存信息。

(2) 網(wǎng)絡(luò)異常

消息丟失：網(wǎng)絡(luò)擁塞、路由變動(dòng)、設(shè)備異常、network partition(部分不正常)

消息亂序：IP存儲(chǔ)轉(zhuǎn)發(fā)、路由不確定性、網(wǎng)絡(luò)報(bào)文亂序

數(shù)據(jù)錯(cuò)誤：比特錯(cuò)誤

不可靠TCP：到達(dá)協(xié)議棧之后與到達(dá)進(jìn)程之間、突然down機(jī)、分布式多個(gè)節(jié)點(diǎn)的tcp亂序

(3) 分布式系統(tǒng)的三態(tài)

任何請(qǐng)求都要考慮三種情況：成功、失敗、超時(shí)。對(duì)于超時(shí)的請(qǐng)求，無法獲知該請(qǐng)求是否被成功執(zhí)行。

(4) 存儲(chǔ)數(shù)據(jù)丟失

(5) 其他異常

IO操作緩慢、網(wǎng)絡(luò)抖動(dòng)、擁塞

1.2 副本

1.2.1 副本的概念

replica/copy 指在分布式系統(tǒng)中為數(shù)據(jù)或服務(wù)提供的冗余：

數(shù)據(jù)副本：在不同的節(jié)點(diǎn)上持久化同一份數(shù)據(jù)。例如GFS同一個(gè)chunk的數(shù)個(gè)副本

服務(wù)副本：數(shù)個(gè)節(jié)點(diǎn)提供相同的服務(wù)，服務(wù)不依賴本地存儲(chǔ)，數(shù)據(jù)來自其他節(jié)點(diǎn)。例如Map Reduce的Job Worker

1.2.2 副本的一致性

副本的consistency是針對(duì)分布式系統(tǒng)而言的，不是針對(duì)某一個(gè)副本而言。根據(jù)強(qiáng)弱程度分為：

強(qiáng)一致性：任何時(shí)刻任何用戶/節(jié)點(diǎn)都可以讀到最近一次更新成功的副本數(shù)據(jù)

單調(diào)一致性：任何時(shí)刻任何用戶一旦讀到某個(gè)數(shù)據(jù)某次更新后的值，就不會(huì)再讀到更舊的值

會(huì)話一致性：任何時(shí)刻任何用戶在某次會(huì)話內(nèi)一旦讀到某個(gè)數(shù)據(jù)某次更新后的值，就不會(huì)在這次會(huì)話再讀到更舊的值

最終一致性：各個(gè)副本的數(shù)據(jù)最終將達(dá)到一致狀態(tài)，但時(shí)間不保證

弱一致性：沒有實(shí)用價(jià)值，略。

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

1.3.1 性能

吞吐量：某一時(shí)間可以處理的數(shù)據(jù)總量

響應(yīng)延遲：完成某一功能需要使用的時(shí)間

并發(fā)能力：QPS(query per second)

1.3.2 可用性

系統(tǒng)停服務(wù)的時(shí)間與正常服務(wù)的時(shí)間的比例

1.3.3 可擴(kuò)展性

通過擴(kuò)展集群機(jī)器提高系統(tǒng)性能、存儲(chǔ)容量、計(jì)算能力的特性，是分布式系統(tǒng)特有的性質(zhì)

1.3.4 一致性

副本帶來的一致性問題

1.3.5：分布式架構(gòu)系統(tǒng)的可視化監(jiān)控方案

1、架構(gòu)師是如何解決分布式架構(gòu)系統(tǒng)監(jiān)控難題的。

2、ELK是誰，從哪里來，要到哪里去?

3、京東海量數(shù)據(jù)檢索，我們一起來感受。

4、只需點(diǎn)擊鼠標(biāo)，高逼格監(jiān)控界面一鍵搞定。

5、你離互聯(lián)網(wǎng)架構(gòu)師到底有遠(yuǎn)?聽聽就知道。

6、架構(gòu)師的技術(shù)棧應(yīng)該是怎樣的?你來問，我一定答。

 

轉(zhuǎn)發(fā) 轉(zhuǎn)發(fā) 轉(zhuǎn)發(fā) 重要的事情說3遍 轉(zhuǎn)發(fā)關(guān)注我私信會(huì)發(fā):Java架構(gòu) 領(lǐng)取分布式架構(gòu)思維導(dǎo)圖 以及資深架構(gòu)師講解的分布式精講視頻資料(還會(huì)提供高并發(fā)，spring源碼，mybatis源碼，dubbo，netty等多個(gè)知識(shí)點(diǎn)的視頻技術(shù)分享!

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

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

無論計(jì)算還是存儲(chǔ)，問題輸入對(duì)象都是數(shù)據(jù)，如何拆分分布式系統(tǒng)的輸入數(shù)據(jù)稱為分布式系統(tǒng)的基本問題。

2.1.1 哈希方式

一種常見的哈希方式是按照數(shù)據(jù)屬于的用戶id計(jì)算哈希。

優(yōu)點(diǎn)：

• 散列性：好
• 元信息：只需要函數(shù)+服務(wù)器總量

缺點(diǎn)：

• 可擴(kuò)展性：差。一旦集群規(guī)模擴(kuò)展，大多數(shù)數(shù)據(jù)都需要被遷移并重新分布
• 數(shù)據(jù)傾斜：當(dāng)某個(gè)用戶id的數(shù)據(jù)量異常龐大時(shí)，容易達(dá)到單臺(tái)服務(wù)器處理能力的上限

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

將數(shù)據(jù)按特征值的值域范圍劃分?jǐn)?shù)據(jù)。例如將用戶id的值域分為[1, 33), [33, 90), [90, 100)，由三臺(tái)服務(wù)器處理。注意區(qū)間大小與區(qū)間內(nèi)的數(shù)據(jù)大小沒有關(guān)系。

優(yōu)點(diǎn)：

• 可擴(kuò)展性：好。靈活根據(jù)數(shù)據(jù)量拆分原有數(shù)據(jù)區(qū)間

缺點(diǎn)：

• 元信息：大。容易成為瓶頸。

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

與按范圍分布數(shù)據(jù)方式類似，元信息容易成為瓶頸

2.1.4 一致性哈希

(1) 以機(jī)器為節(jié)點(diǎn)

用一個(gè)hash函數(shù)計(jì)算數(shù)據(jù)(特征)的hash值，令該hash函數(shù)的值域成為一個(gè)封閉的環(huán)，將節(jié)點(diǎn)隨機(jī)分布在環(huán)上。每個(gè)節(jié)點(diǎn)負(fù)責(zé)處理從自己開始順時(shí)針到下一節(jié)點(diǎn)的值域上的數(shù)據(jù)。

優(yōu)點(diǎn)：

• 可擴(kuò)展性：極好。任意動(dòng)態(tài)添加、刪除節(jié)點(diǎn)，只影響相鄰節(jié)點(diǎn)

缺點(diǎn)：

• 元信息：大而且復(fù)雜
• 隨機(jī)分布節(jié)點(diǎn)容易造成不均勻
• 動(dòng)態(tài)增加節(jié)點(diǎn)后只能緩解相鄰節(jié)點(diǎn)
• 一個(gè)接點(diǎn)異常時(shí)壓力全轉(zhuǎn)移到相鄰節(jié)點(diǎn)

(2) 虛節(jié)點(diǎn)

虛節(jié)點(diǎn)，虛節(jié)點(diǎn)個(gè)數(shù)遠(yuǎn)大于機(jī)器個(gè)數(shù)，將虛節(jié)點(diǎn)均勻分布到值域環(huán)上，通過元數(shù)據(jù)找到真實(shí)機(jī)器節(jié)點(diǎn)。

優(yōu)點(diǎn)：

某一個(gè)節(jié)點(diǎn)不可用導(dǎo)致多個(gè)虛節(jié)點(diǎn)不可用，均衡了壓力

加入新節(jié)點(diǎn)導(dǎo)致增加多個(gè)虛節(jié)點(diǎn)，緩解了全局壓力

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

前邊4中數(shù)據(jù)分布方式的討論中沒有考慮數(shù)據(jù)副本的問題。

(1) 以機(jī)器為單位的副本

缺點(diǎn)：

恢復(fù)效率：低。假如1出問題，從2 3 中全盤拷貝數(shù)據(jù)較消耗資源，為避免影響服務(wù)一般會(huì)將2下線專門做拷貝，導(dǎo)致正常工作的副本只有3

可擴(kuò)展性：差。假如系統(tǒng)3臺(tái)機(jī)器互為副本，只增加兩臺(tái)機(jī)器的情況下無法組成新的副本組。

可用性：差。一臺(tái)donw機(jī)，剩下兩臺(tái)壓力增加50%。理想情況會(huì)均攤到整個(gè)集群，而不是單個(gè)副本組

(2) 以數(shù)據(jù)段為單位的副本

例如3臺(tái)服務(wù)器，10G數(shù)據(jù)，按100hash取模得到100M每個(gè)的數(shù)據(jù)段，每臺(tái)服務(wù)器負(fù)責(zé)333個(gè)數(shù)據(jù)段。一旦將數(shù)據(jù)分成數(shù)據(jù)段，就可以以數(shù)據(jù)段為單位管理副本，副本與機(jī)器不再硬相關(guān)。

例如系統(tǒng)中3個(gè)數(shù)據(jù)o p q, 每個(gè)數(shù)據(jù)段有三個(gè)副本，系統(tǒng)中有4臺(tái)機(jī)器：

優(yōu)點(diǎn)：

恢復(fù)效率：高?？梢哉麄€(gè)集群同時(shí)拷貝

可用性：好。機(jī)器donw機(jī)的壓力分散到整個(gè)集群

工程中完全按照數(shù)據(jù)段建立副本會(huì)引起元數(shù)據(jù)開銷增大，這種做法是將數(shù)據(jù)段組成一個(gè)大數(shù)據(jù)段。

2.1.6 本地化計(jì)算

如果計(jì)算節(jié)點(diǎn)和存儲(chǔ)節(jié)點(diǎn)位于不同的物理機(jī)器，開銷很大，網(wǎng)絡(luò)帶寬會(huì)成為系統(tǒng)的瓶頸;將計(jì)算調(diào)度到與存儲(chǔ)節(jié)點(diǎn)在同一臺(tái)物理機(jī)器上的節(jié)點(diǎn)計(jì)算，稱為計(jì)算本地化。

2.2 基本副本協(xié)議

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

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

并發(fā)控制：多個(gè)節(jié)點(diǎn)同時(shí)需要修改副本數(shù)據(jù)時(shí)，需要解決的“寫寫”、“讀寫”等并發(fā)沖突

單機(jī)系統(tǒng)使用加鎖等方式進(jìn)行并發(fā)控制，中心化協(xié)議也可以使用。缺點(diǎn)是過分依賴中心節(jié)點(diǎn)。

2.2.2 primary-secondary協(xié)議

這是一種常用的中心化副本控制協(xié)議，有且僅有一個(gè)節(jié)點(diǎn)作為primary副本。有4個(gè)問題需要解決：

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

由primary協(xié)調(diào)完成更新

外部節(jié)點(diǎn)將更新操作發(fā)給primary節(jié)點(diǎn)

primary節(jié)點(diǎn)進(jìn)行并發(fā)控制并確定并發(fā)更新操作的先后順序

primary節(jié)點(diǎn)將更新操作發(fā)送給secondary節(jié)點(diǎn)

primary根據(jù)secondary節(jié)點(diǎn)的完成情況決定更新是否成功，然后將結(jié)果返回外部節(jié)點(diǎn)

其中第4步，有些系統(tǒng)如GFS使用接力的方式同步數(shù)據(jù)，primary -> secondary1 ->secondary2，避免primary的帶寬稱為瓶頸。

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

方法一：由于數(shù)據(jù)更新流程都是由primary控制的，primary副本上數(shù)據(jù)一定最新。所以永遠(yuǎn)只讀primary副本的數(shù)據(jù)能夠?qū)崿F(xiàn)強(qiáng)一致性。為了避免機(jī)器浪費(fèi)，可以使用之前討論的方法，將數(shù)據(jù)分段，將數(shù)據(jù)段作為副本單位。達(dá)到每臺(tái)機(jī)器都有primary副本的目的。

方法二：由primary控制secondary的可用性。當(dāng)primary更新某個(gè)secondary不成功時(shí)，將其標(biāo)記為不可用。不可用的secondary副本繼續(xù)嘗試與primary同步數(shù)據(jù)，直到成功同步后轉(zhuǎn)為可用狀態(tài)。

方法三：Quorum機(jī)制。后續(xù)討論。

(3) primary副本的確定與切換

如何確定primary副本?primary副本所在機(jī)器異常時(shí)，如何切換副本?

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

切換副本難點(diǎn)有兩個(gè)方面：如何確定節(jié)點(diǎn)狀態(tài)以發(fā)現(xiàn)原primary節(jié)點(diǎn)出現(xiàn)異常(Lease機(jī)制)。切換primary后不能影響一致性(Quorum機(jī)制)。

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

當(dāng)發(fā)生secondary與primary不一致的情況，需要secondary向primary進(jìn)行同步(reconcile)。

不一致的原因有3種：

網(wǎng)絡(luò)分化等異常導(dǎo)致secondary落后于primary

常用的方式是回放primary上的操作日志(redo日志)，追上primary的更新進(jìn)度

某些協(xié)議下secondary是臟數(shù)據(jù)

丟棄轉(zhuǎn)到第三種情況;或者設(shè)計(jì)基于undo日志的方式

secondary是一個(gè)新增副本完全沒有數(shù)據(jù)

直接copy primary的數(shù)據(jù)，但要求同時(shí)primary能繼續(xù)提供更新服務(wù)，這就要求primary副本支持快照(snapshot)功能。即對(duì)某一刻的副本數(shù)據(jù)形成快照，然后copy快照，再使用回放日志的方式追趕快照后的更新操作。

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

去中心化副本控制協(xié)議沒有中心節(jié)點(diǎn)，節(jié)點(diǎn)之間通過平等協(xié)商達(dá)到一致。工程中唯一能應(yīng)用在強(qiáng)一致性要求下的是paxos協(xié)議。后續(xù)介紹。

2.3 lease機(jī)制

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

(1) 需求：分布式系統(tǒng)中有一個(gè)節(jié)點(diǎn)A存儲(chǔ)維護(hù)系統(tǒng)的元數(shù)據(jù)，系統(tǒng)中其他節(jié)點(diǎn)通過訪問A讀取修改元數(shù)據(jù)，導(dǎo)致A的性能成為系統(tǒng)瓶頸。為此，設(shè)計(jì)一種元數(shù)據(jù)cache，在各個(gè)節(jié)點(diǎn)上cache元數(shù)據(jù)信息，使得：

減少對(duì)A的訪問，提高性能

各個(gè)節(jié)點(diǎn)cache數(shù)據(jù)始終與A一致

最大可能處理節(jié)點(diǎn)down機(jī)、網(wǎng)絡(luò)中斷等異常

(2) 解決方案原理：

A向各個(gè)節(jié)點(diǎn)發(fā)送數(shù)據(jù)的同時(shí)向節(jié)點(diǎn)頒發(fā)一個(gè)lease，每個(gè)lease具有一個(gè)有效期，通常是一個(gè)明確的時(shí)間點(diǎn)。一旦真實(shí)時(shí)間超過次時(shí)間點(diǎn)則lease過期

在lease有效期內(nèi)，A保證不會(huì)修改對(duì)應(yīng)數(shù)據(jù)的值。

A在修改數(shù)據(jù)時(shí)，首先阻塞所有新的讀請(qǐng)求，等待之前為該數(shù)據(jù)發(fā)出的所有l(wèi)ease過期，然后修改數(shù)據(jù)的值

(3) 客戶端節(jié)點(diǎn)讀取元數(shù)據(jù)的流程

if (元數(shù)據(jù)處于本地cache && lease處于有效期內(nèi)) { 直接返回cache中的元數(shù)據(jù);} else { Result = 向A請(qǐng)求讀取元數(shù)據(jù)信息; if (Result.Status == SUCCESS) { WriteToCache(Result.data, Result.lease); } else if (Result.Status == FAIL || Result.Status == TIMEOUT) { retry() or exit(); }}

(4) 客戶端節(jié)點(diǎn)修改元數(shù)據(jù)的流程

節(jié)點(diǎn)向A發(fā)起修改元數(shù)據(jù)的請(qǐng)求

A收到修改請(qǐng)求后阻塞所有新的讀數(shù)據(jù)請(qǐng)求，即接受讀請(qǐng)求但不返回?cái)?shù)據(jù)

A等待所有與該元數(shù)據(jù)相關(guān)的lease超時(shí)

A修改元數(shù)據(jù)并向節(jié)點(diǎn)返回修改成功

(5) 優(yōu)化點(diǎn)

A修改元數(shù)據(jù)時(shí)要阻塞所有新的讀請(qǐng)求

這是為了防止發(fā)出新的lease而引起不斷有新的cache節(jié)點(diǎn)持有l(wèi)ease，形成活鎖。優(yōu)化的手段是：一旦A進(jìn)入修改流程，不是盲目屏蔽讀請(qǐng)求，而是對(duì)讀請(qǐng)求只返回?cái)?shù)據(jù)不返回lease。造成cache節(jié)點(diǎn)只能讀取數(shù)據(jù)，不能cache數(shù)據(jù)。進(jìn)一步的優(yōu)化是返回當(dāng)前已發(fā)出的lease的最大值。這樣同樣能避免活鎖問題。

A在修改元數(shù)據(jù)時(shí)需要等待所有l(wèi)ease過期

優(yōu)化手段是：A主動(dòng)通知各個(gè)持有l(wèi)ease的節(jié)點(diǎn)，放棄lease并清除cache中相關(guān)數(shù)據(jù)。如果收到cache節(jié)點(diǎn)的reply，確認(rèn)協(xié)商通過，則可以提前完成修改動(dòng)作;如果中間失敗或超時(shí)，則進(jìn)入正常等待lease過期的流程，不會(huì)影響協(xié)議正確性。

2.3.2 lease機(jī)制的深入分析

(1) lease定義

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

(2) lease的解讀

由于lease僅僅是一種承諾，具體的承諾內(nèi)容可以非常寬泛，可以是上節(jié)中數(shù)據(jù)的正確性，也可以是某種權(quán)限。例如并發(fā)控制中同一時(shí)刻只給某一個(gè)節(jié)點(diǎn)頒發(fā)lease，只有持有l(wèi)ease才能修改數(shù)據(jù);例如primary-secondary中持有l(wèi)ease的節(jié)點(diǎn)具有primary身份等等

(3) lease的高可用性

有效期的引入，非常好的解決了網(wǎng)絡(luò)異常問題。由于lease是確定的時(shí)間點(diǎn)，所以可以簡(jiǎn)單重發(fā);一旦受到lease之后，就不再依賴網(wǎng)絡(luò)通信

(4) lease的時(shí)鐘同步

工程上將頒發(fā)者有效期設(shè)置的比接受者打，大過時(shí)鐘誤差，來避免對(duì)lease有效性產(chǎn)生影響。

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

在分 布式系統(tǒng)中確定一個(gè)節(jié)點(diǎn)是否處于正常工作狀態(tài)困難的問題。由可能存在網(wǎng)絡(luò)分化，節(jié)點(diǎn)的狀態(tài)無法通過網(wǎng)絡(luò)通信來確定的。

例如： a b c 互為副本 a為主節(jié)點(diǎn)，q為監(jiān)控節(jié)點(diǎn)。q通過ping來判斷abc的狀態(tài)，認(rèn)為a不能工作。就將主節(jié)點(diǎn)切換成b。但是事實(shí)上僅僅是ping沒收到，a自己認(rèn)為自己沒有問題，就出現(xiàn)了 a b都覺得自己是主節(jié)點(diǎn)的“雙主”問題。

解決方法是q在發(fā)送heartbeat時(shí)加上lease，表示確認(rèn)了abc的狀態(tài)，并允許節(jié)點(diǎn)在lease有效期內(nèi)正常工作。q給primary節(jié)點(diǎn)一個(gè)特殊的lease，表示該節(jié)點(diǎn)作為primary工作。一旦q希望切換primary，只需要等待之前primary的lease過期，避免出現(xiàn)雙主問題。

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

工程上一般選擇10秒鐘

2.4 Quorum機(jī)制

2.4.1 Write-all-read-one

對(duì)于某次更新操作Wi，只有在所有N個(gè)副本上都更新成功，才認(rèn)為是一次“成功提交的更新操作”，對(duì)應(yīng)的數(shù)據(jù)為“成功提交的數(shù)據(jù)”，數(shù)據(jù)版本為Vi。

缺點(diǎn)：

頻繁讀寫版本號(hào)容易成為瓶頸

N-1個(gè)副本成功的情況下，仍然被認(rèn)為更新失敗

2.4.2 Quorum定義

WARO最大程度增強(qiáng)讀服務(wù)可用性，最大程度犧牲寫服務(wù)的可用性。將讀寫可用性折中，就會(huì)得到Quorum機(jī)制：

Quorum機(jī)制下，某次更新Wi一旦在所有N個(gè)副本中的W個(gè)副本上成功，就稱為“成功提交的更新操作”，對(duì)應(yīng)的數(shù)據(jù)為“成功提交的數(shù)據(jù)”。令R > N - W，最多需要讀取R個(gè)副本則一定能讀到Wi更新后的數(shù)據(jù)Vi。

由此可見WARO是Quorum中W = N時(shí)的一個(gè)特例。

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

Quorum的定義基于兩個(gè)假設(shè)：

讀取者知道當(dāng)前已提交的版本號(hào)

每次都是一次成功的提交

現(xiàn)在取消這兩個(gè)假設(shè)，分析下面這個(gè)實(shí)際問題：

N = 5, W = 3, R = 3，某一次的副本狀態(tài)為(V2 V2 V2 V1 V1)。理論上讀取任何3個(gè)副本一定能讀到最新的數(shù)據(jù)V2，但是僅讀3個(gè)副本卻無法確定讀到最新的數(shù)據(jù)。

例如讀到的是(V2 V1 V1)，因?yàn)楫?dāng)副本狀態(tài)為(V2 V1 V1 V1 V1)時(shí)也會(huì)讀到(V2 V1 V1)，而此時(shí)V2版本的數(shù)據(jù)是一次失敗的提交。因此只讀3個(gè)無法確定最新有效的版本是V2還是V1。

解決方案：

限制提交的更新操作必須嚴(yán)格遞增，只有前一個(gè)更新操作成功后才可以提交下一個(gè)。保證成功的版本號(hào)連續(xù)

讀取R個(gè)副本，對(duì)其中版本號(hào)最高的數(shù)據(jù)：若已存在W個(gè)，則該數(shù)據(jù)為最新結(jié)果;否則假設(shè)為X個(gè)，則繼續(xù)讀取其他副本直到成功讀取W個(gè)該版本的副本。如果無法找到W個(gè)，則第二大的版本號(hào)為最新成功提交的版本。

因此單純使用Quorum機(jī)制時(shí)，最多需要讀取R + (W - R - 1) = N個(gè)副本才能確定最新成功提交的版本。實(shí)際工程中一般使用quorum與primary-secondary結(jié)合的手段，避免需要讀取N個(gè)副本。

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

在primary-secondary協(xié)議中引入quorum機(jī)制：即primary成功更新W個(gè)副本后向用戶返回成功

當(dāng)primary異常時(shí)需要選擇一個(gè)新的primary，之后secondary副本與primary同步數(shù)據(jù)

通常情況下切換primary由監(jiān)控節(jié)點(diǎn)q完成，引入quorum之后，選擇新的primary的方式與讀取數(shù)據(jù)相似，即q讀取R個(gè)副本，選擇R個(gè)副本中版本號(hào)最高的副本作為新的primary。新primary與除去q選舉出的副本外，其余的至少W個(gè)副本完成數(shù)據(jù)同步后，再作為新的primary。

蘊(yùn)含的道理是：

R個(gè)副本中版本號(hào)最高的副本一定蘊(yùn)含了最新的成功提交的數(shù)據(jù)。

雖然不能確定版本號(hào)最高的數(shù)據(jù) == 這個(gè)最新成功提交的數(shù)據(jù)，但新的primary立即完成了對(duì)W個(gè)副本的更新，從而使其變成了成功提交的數(shù)據(jù)

例如：N = 5 W = 3 R = 3的系統(tǒng)，某時(shí)刻副本狀態(tài)(V2 V2 V1 V1 V1)，此時(shí)V1是最新成功提交的數(shù)據(jù)，V2是處于中間狀態(tài)未成功提交的數(shù)據(jù)。V2是作為臟數(shù)據(jù)扔掉，還是作為新數(shù)據(jù)被同步，完全取決于能否參與q主持的新primary的選舉大會(huì)。如果q選擇(V1 V1 V1)，則在接下來的更新過程中 V2會(huì)被當(dāng)成臟數(shù)據(jù)扔掉;如果q選擇(V2 V1 V1)則V2會(huì)將V1更新掉，成為最新成功的數(shù)據(jù)。

 

2.5 日志技術(shù)

日志技術(shù)不是一種分布式系統(tǒng)技術(shù)，但分布式系統(tǒng)廣泛使用日志技術(shù)做down機(jī)恢復(fù)。

2.5.1 數(shù)據(jù)庫系統(tǒng)日志回顧

數(shù)據(jù)庫的日志分為 undo redo redo/undo no-redo/no-undo四種，這里不做過多介紹。

2.5.2 redo與check point

通過redo log恢復(fù)down機(jī)的缺點(diǎn)是需要掃描整個(gè)redolog，回放所有redo日志。解決這個(gè)問題的辦法是引入checkpoint技術(shù)，簡(jiǎn)化模型下checkpoint就是在begin和end中間，將內(nèi)存以某種數(shù)據(jù)組織方式dump到磁盤上。這樣down機(jī)恢復(fù)時(shí)只需要從最后一個(gè)end向前找到最近一個(gè)begin，恢復(fù)中間的內(nèi)存狀態(tài)即可。

2.5.3 no-undo/no-redo

這種技術(shù)也叫做01目錄，即有兩個(gè)目錄，活動(dòng)目錄和非活動(dòng)目錄，另外還有一個(gè)主記錄，要么“記錄目錄0”，妖魔記錄“使用目錄1”，目錄0和1記錄了各個(gè)數(shù)據(jù)在日志文件中的位置。

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

2.7 基于MVCC的分布式事務(wù)

由于這兩個(gè)都與數(shù)據(jù)庫事務(wù)有關(guān)，且兩階段提交協(xié)議在工程中使用價(jià)值不高，均略去不談。

2.8 Paxos協(xié)議

唯一在工程中有使用價(jià)值的去中心化副本節(jié)點(diǎn)控制協(xié)議。過于復(fù)雜，沒看懂。

2.9 CAP理論

Consitency

Availiablity

Tolerance to the Partition of network

無法設(shè)計(jì)一種分布式協(xié)議，使得完全具備CAP三個(gè)屬性。永遠(yuǎn)只能介于三者之間折中。理論的意義是：不要妄想設(shè)計(jì)完美的分布式系統(tǒng)。