[[274519]]

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

1.1 模型

 

1.1.1 節(jié)點

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

1.1.2 通信

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

1.1.3 存儲

節(jié)點可以通過將數(shù)據(jù)寫入與節(jié)點在同一臺機器的本地存儲設備保存數(shù)據(jù)

1.1.4 異常

(1) 機器down機

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

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

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

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

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

不可靠TCP：到達協(xié)議棧之后與到達進程之間、突然down機、分布式多個節(jié)點的tcp亂序

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

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

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

(5) 其他異常

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

1.2 副本

1.2.1 副本的概念

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

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

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

1.2.2 副本的一致性

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

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

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

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

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

弱一致性：沒有實用價值，略。

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

1.3.1 性能

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

響應延遲：完成某一功能需要使用的時間

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

1.3.2 可用性

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

1.3.3 可擴展性

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

1.3.4 一致性

副本帶來的一致性問題

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

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

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

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

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

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

6、架構師的技術棧應該是怎樣的?你來問，我一定答。

 

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

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

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

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

2.1.1 哈希方式

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

優(yōu)點：

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

缺點：

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

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

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

優(yōu)點：

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

缺點：

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

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

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

2.1.4 一致性哈希

(1) 以機器為節(jié)點

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

優(yōu)點：

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

缺點：

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

(2) 虛節(jié)點

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

優(yōu)點：

某一個節(jié)點不可用導致多個虛節(jié)點不可用，均衡了壓力

加入新節(jié)點導致增加多個虛節(jié)點，緩解了全局壓力

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

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

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

缺點：

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

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

可用性：差。一臺donw機，剩下兩臺壓力增加50%。理想情況會均攤到整個集群，而不是單個副本組

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

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

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

優(yōu)點：

恢復效率：高。可以整個集群同時拷貝

可用性：好。機器donw機的壓力分散到整個集群

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

2.1.6 本地化計算

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

2.2 基本副本協(xié)議

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

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

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

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

2.2.2 primary-secondary協(xié)議

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

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

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

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

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

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

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

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

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

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

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

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

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

如何確定primary副本?primary副本所在機器異常時，如何切換副本?

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

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

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

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

不一致的原因有3種：

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

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

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

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

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

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

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

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

2.3 lease機制

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

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

減少對A的訪問，提高性能

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

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

(2) 解決方案原理：

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

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

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

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

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

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

節(jié)點向A發(fā)起修改元數(shù)據(jù)的請求

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

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

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

(5) 優(yōu)化點

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

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

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

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

2.3.2 lease機制的深入分析

(1) lease定義

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

(2) lease的解讀

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

(3) lease的高可用性

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

(4) lease的時鐘同步

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

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

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

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

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

2.3.4 lease的有效期時間選擇

工程上一般選擇10秒鐘

2.4 Quorum機制

2.4.1 Write-all-read-one

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

缺點：

頻繁讀寫版本號容易成為瓶頸

N-1個副本成功的情況下，仍然被認為更新失敗

2.4.2 Quorum定義

WARO最大程度增強讀服務可用性，最大程度犧牲寫服務的可用性。將讀寫可用性折中，就會得到Quorum機制：

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

由此可見WARO是Quorum中W = N時的一個特例。

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

Quorum的定義基于兩個假設：

讀取者知道當前已提交的版本號

每次都是一次成功的提交

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

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

例如讀到的是(V2 V1 V1)，因為當副本狀態(tài)為(V2 V1 V1 V1 V1)時也會讀到(V2 V1 V1)，而此時V2版本的數(shù)據(jù)是一次失敗的提交。因此只讀3個無法確定最新有效的版本是V2還是V1。

解決方案：

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

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

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

2.4.4 基于Quorum機制選擇primary

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

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

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

蘊含的道理是：

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

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

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

 

2.5 日志技術

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

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

2.5.3 no-undo/no-redo

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

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

2.7 基于MVCC的分布式事務

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

2.8 Paxos協(xié)議

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

2.9 CAP理論

Consitency

Availiablity

Tolerance to the Partition of network

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