這是 中興大數(shù)據(jù)第200篇原創(chuàng)文章

分布式系統(tǒng)是大數(shù)據(jù)的基礎(chǔ)，大數(shù)據(jù)是分布式系統(tǒng)的最佳實(shí)踐。本文將介紹分布式系統(tǒng)對數(shù)據(jù)的基本處理方法，包括數(shù)據(jù)的分布方式和對數(shù)據(jù)副本進(jìn)行控制的協(xié)議和算法。這些算法也是大數(shù)據(jù)各類組件技術(shù)的基礎(chǔ)。

分布式系統(tǒng)定義

分布式系統(tǒng)是若干獨(dú)立計(jì)算機(jī)的集合，但這些計(jì)算機(jī)系統(tǒng)集合從用戶的使用角度來說，則是一個(gè)單一的應(yīng)用系統(tǒng)。組建一個(gè)分布式系統(tǒng)具備五個(gè)關(guān)鍵目標(biāo)：

1. 資源的可訪問性：用戶能夠方便的訪問遠(yuǎn)程資源，并且可以以一種受控的方式與其他用戶共享資源；

2. 透明性：資源在網(wǎng)絡(luò)上的分布對用戶不可見，用戶的使用體驗(yàn)就是在一個(gè)入口做操作；

3. 開放性：系統(tǒng)通過一整套標(biāo)準(zhǔn)化的接口來提供服務(wù)，任何第三方系統(tǒng)都可以通過該標(biāo)準(zhǔn)接口接入該系統(tǒng)，并使用其提供的服務(wù)；

4. 可擴(kuò)展性：系統(tǒng)在規(guī)模上可以擴(kuò)展，可以方便的增加資源來為更多的用戶提供服務(wù)。

5. 容錯(cuò)性：系統(tǒng)可以從部分失效中自動(dòng)恢復(fù)，而且不會(huì)嚴(yán)重的影響整體性能。特別是，當(dāng)故障發(fā)生時(shí)，分布式系統(tǒng)應(yīng)該在進(jìn)行故障恢復(fù)的同時(shí)依然可以提供基本的操作能力。也就是說，它應(yīng)該能容忍錯(cuò)誤，在發(fā)生錯(cuò)誤時(shí)某種程度上可以繼續(xù)操作。

整個(gè)系統(tǒng)由分布在不同位置或者服務(wù)器上的節(jié)點(diǎn)和進(jìn)程組成，這二者是分布式系統(tǒng)的基本元素，而節(jié)點(diǎn)/進(jìn)程間的通信是分布式系統(tǒng)的核心。節(jié)點(diǎn)/進(jìn)程間通過命名服務(wù)和同步來相互協(xié)作。

一致性和復(fù)制是分布式系統(tǒng)要解決的二個(gè)重要問題，對數(shù)據(jù)進(jìn)行復(fù)制是為了增強(qiáng)系統(tǒng)的可靠性或提高性能。而實(shí)現(xiàn)數(shù)據(jù)復(fù)制的主要難題是保證各個(gè)副本的一致性。

分布式系統(tǒng)體系結(jié)構(gòu)

把分布式系統(tǒng)的邏輯組織結(jié)構(gòu)看作軟件組件來分析其體系結(jié)構(gòu)，則通常分布式系統(tǒng)可以劃分為：

基于分層的體系架構(gòu)：組件組成不同的層，各層的請求自頂向下依次調(diào)用，而請求結(jié)果則從下往上。如下圖“基于分層的體系架構(gòu)”所示，TCP/IP協(xié)議的模型是這種體系架構(gòu)的經(jīng)典。

基于分層的體系架構(gòu)

基于對象的體系架構(gòu)：這是一種很松散的組織結(jié)構(gòu)，每個(gè)對象是一個(gè)組件，組件間通過遠(yuǎn)程過程調(diào)用機(jī)制來交互。如下圖“基于對象的體系架構(gòu)”所示，大型軟件多采用本架構(gòu)。

基于對象的體系架構(gòu)

基于數(shù)據(jù)的體系架構(gòu)：組件間的通信通過一個(gè)公用的數(shù)據(jù)倉庫。如下圖“基于數(shù)據(jù)的體系架構(gòu)”所示，基于WEB的分布式系統(tǒng)大多數(shù)是以數(shù)據(jù)為中心的。

基于數(shù)據(jù)的體系架構(gòu)

基于事件的體系架構(gòu)：組件間的通信是通過事件來傳播的，進(jìn)程間是松耦合的。如下圖“基于事件的體系架構(gòu)”所示，通常的發(fā)布/訂閱系統(tǒng)都屬于這類。

基于事件的體系架構(gòu)

分布式系統(tǒng)演進(jìn)

最出名的分布式計(jì)算模型就是Internet，它是所有分布式技術(shù)的基礎(chǔ)，從電子商務(wù)到云計(jì)算到面向服務(wù)到虛擬化到大數(shù)據(jù)。所有的分布式計(jì)算模型都有一個(gè)相同的特性：他們是一群協(xié)同工作的網(wǎng)絡(luò)計(jì)算機(jī)。

總體上說，整體分布式系統(tǒng)的演進(jìn)是從封閉到開放的過程，是一個(gè)不斷標(biāo)準(zhǔn)化的過程。

早期是美國國防部先進(jìn)研究項(xiàng)目局（DARPA）的內(nèi)部網(wǎng)絡(luò)和一些私企的遠(yuǎn)程過程調(diào)用（RPC）系統(tǒng)，慢慢的TCP/IP協(xié)議的發(fā)展和被廣泛應(yīng)用。最終夯實(shí)了分布式系統(tǒng)的基礎(chǔ)。

每個(gè)廠商和標(biāo)準(zhǔn)組織都在發(fā)展自己的遠(yuǎn)程過程調(diào)用（RPC）系統(tǒng)，這使得任何一家公司都無法創(chuàng)建一個(gè)通用的分布式計(jì)算標(biāo)準(zhǔn)。1990年代中期，Internet協(xié)議替代了這些早期的嘗試，并成為今天分布式計(jì)算的基礎(chǔ)。整個(gè)演進(jìn)過程如下圖所示。

分布式計(jì)算演進(jìn)過程

典型的分布式系統(tǒng)案例如下：

電信通訊網(wǎng)絡(luò)：

• 電話網(wǎng)絡(luò)和蜂窩網(wǎng)絡(luò)

• 計(jì)算機(jī)網(wǎng)絡(luò)，諸如Internet

• 無線傳感器網(wǎng)絡(luò)

網(wǎng)絡(luò)應(yīng)用：

• 廣域網(wǎng)和點(diǎn)對點(diǎn)網(wǎng)絡(luò)

• 在線游戲和虛擬現(xiàn)實(shí)社區(qū)

• 分布式數(shù)據(jù)庫

• 網(wǎng)絡(luò)文件系統(tǒng)

實(shí)時(shí)控制系統(tǒng)：

• 飛機(jī)控制系統(tǒng)

• 工業(yè)控制系統(tǒng)

并行計(jì)算：

• 科學(xué)計(jì)算，包括集群計(jì)算和網(wǎng)格計(jì)算

• 計(jì)算機(jī)圖形的分布式渲染

分布式系統(tǒng)關(guān)鍵協(xié)議和算法

在分布式系統(tǒng)中計(jì)算節(jié)點(diǎn)和存儲節(jié)點(diǎn)可以在同一臺物理機(jī)器上，也可以位于不同的物理機(jī)器。如果計(jì)算節(jié)點(diǎn)和存儲節(jié)點(diǎn)位于不同的物理機(jī)器則計(jì)算的數(shù)據(jù)需要通過網(wǎng)絡(luò)傳輸，此種方式的開銷很大，甚至網(wǎng)絡(luò)帶寬會(huì)成為系統(tǒng)的總體瓶頸。另一種思路是，將計(jì)算盡量調(diào)度到與存儲節(jié)點(diǎn)在同一臺物理機(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ì)算”，通俗說就是計(jì)算跟著數(shù)據(jù)走。

當(dāng)數(shù)據(jù)分布到多個(gè)節(jié)點(diǎn)后，為了保證數(shù)據(jù)的安全和可靠性，必須對每份數(shù)據(jù)都有備份，也就是數(shù)據(jù)的副本。對分布式系統(tǒng)來說，副本數(shù)據(jù)的復(fù)制（維持多副本）和保證副本的一致性是其重點(diǎn)要解決的兩個(gè)問題。進(jìn)行數(shù)據(jù)復(fù)制主要是為了提升系統(tǒng)的可靠性和性能。如果一個(gè)文件系統(tǒng)已實(shí)現(xiàn)數(shù)據(jù)復(fù)制，則當(dāng)一個(gè)副本被破壞后，文件系統(tǒng)只需要轉(zhuǎn)換到另一個(gè)數(shù)據(jù)副本就可繼續(xù)運(yùn)轉(zhuǎn)，從而使得系統(tǒng)更加可靠。同樣，當(dāng)分布式系統(tǒng)需要在服務(wù)器數(shù)量和地理區(qū)域上進(jìn)行擴(kuò)展時(shí)，復(fù)制對于提高性能也是非常重要的，通過對服務(wù)器進(jìn)行復(fù)制，讓他們分擔(dān)工作負(fù)荷，就可以提高性能。雖然復(fù)制能提升系統(tǒng)可靠性和性能，但是復(fù)制是有代價(jià)的。首先，維持多副本需要更多的存儲空間，所有副本的更新需要更多的網(wǎng)絡(luò)帶寬，另外，多個(gè)副本可能導(dǎo)致一致性方面的問題，一旦某個(gè)副本被修改了，那么它將不同于其他所有的副本。因此，必須對所有副本進(jìn)行同樣的修改以確保一致性。

綜上，一個(gè)分布式系統(tǒng)的關(guān)鍵協(xié)議和算法主要有兩類：

1. 如何拆解分布式系統(tǒng)的輸入數(shù)據(jù)，即數(shù)據(jù)的分布方式；

2. 數(shù)據(jù)的副本是如何創(chuàng)建的，并且如何保證其一致性。

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

對系統(tǒng)的輸入數(shù)據(jù)進(jìn)行分解并分布到不同的節(jié)點(diǎn)的方式就是數(shù)據(jù)的分布方式，通常用下面的方法：

a） 哈希方式

哈希方式是最常見的數(shù)據(jù)分布方式，其方法是按照數(shù)據(jù)的某一特征計(jì)算哈希值，并將哈希值與機(jī)器中的機(jī)器建立映射關(guān)系，從而將不同哈希值的數(shù)據(jù)分布到不同的機(jī)器上。所謂數(shù)據(jù)特征可以是key-value 系統(tǒng)中的 key，也可以是其他與應(yīng)用業(yè)務(wù)邏輯相關(guān)的值。下圖“哈希算法數(shù)據(jù)分布示意圖”給出了哈希方式分?jǐn)?shù)據(jù)的一個(gè)例子，將數(shù)據(jù)按哈希值分配到3個(gè)節(jié)點(diǎn)上。

哈希算法數(shù)據(jù)分布示意圖

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

按數(shù)據(jù)范圍分布是另一個(gè)常見的數(shù)據(jù)分布式，將數(shù)據(jù)按特征值的值域范圍劃分為不同的區(qū)間，使得集群中每臺（組）服務(wù)器處理不同區(qū)間的數(shù)據(jù)。下圖“按數(shù)據(jù)范圍分布的示意圖”展示了這種數(shù)據(jù)發(fā)布方式。

按數(shù)據(jù)范圍分布的示意圖

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

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

按數(shù)據(jù)量分布的示意圖

d） 一致性哈希

使用一個(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ù)。下圖“一致性哈希分布示意圖”是一個(gè)簡單的示例。

一致性哈希分布示意圖

數(shù)據(jù)副本控制協(xié)議

副本控制協(xié)議指按一定的協(xié)議流程控制副本數(shù)據(jù)的讀寫行為，使得副本滿足一定的可用性和一致性要求的分布式協(xié)議。副本控制協(xié)議要具有一定的容錯(cuò)能力，從而保證系統(tǒng)具有一定的可用性。在分布式系統(tǒng)中通常有兩種方法：

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

中心化副本控制協(xié)議的基本思路是由一個(gè)中心節(jié)點(diǎn)協(xié)調(diào)副本數(shù)據(jù)的更新、維護(hù)副本之間的一致性。中心化副本控制協(xié)議的優(yōu)點(diǎn)是協(xié)議相對較為簡單，所有的副本相關(guān)的控制由中心節(jié)點(diǎn)完成，并發(fā)控制由中心節(jié)點(diǎn)完成，從而使得一個(gè)分布式并發(fā)控制問題，簡化為一個(gè)單機(jī)并發(fā)控制問題。中心化副本控制協(xié)議通用架構(gòu)如下圖“中心化副本控制協(xié)議示意圖”：這類協(xié)議優(yōu)點(diǎn)是設(shè)計(jì)簡單，但是存在中心節(jié)點(diǎn)使得有一定的中心節(jié)點(diǎn)異常造成的不可用問題。

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

最常用的中心化副本控制協(xié)議就是primary-secondary協(xié)議。類似通常的Master-Slave協(xié)議，Primary是主節(jié)點(diǎn)，Secondary是若干副節(jié)點(diǎn)。這種協(xié)議中，副本被分為兩種：Primary的副本，通常只有一個(gè)；除Primary 以外的副本都作為Secondary 副本。維護(hù)Primary副本的節(jié)點(diǎn)作為中心節(jié)點(diǎn)，中心節(jié)點(diǎn)負(fù)責(zé)維護(hù)數(shù)據(jù)的更新、并發(fā)控制、協(xié)調(diào)副本的一致性等控制管理工作。

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

去中心化副本控制協(xié)議沒有中心節(jié)點(diǎn)，協(xié)議中所有的節(jié)點(diǎn)都是完全對等的，節(jié)點(diǎn)之間通過平等協(xié)商達(dá)到一致。從而去中心化協(xié)議沒有因?yàn)橹行幕?jié)點(diǎn)異常而帶來的停服務(wù)等問題。去中心化協(xié)議的最大的缺點(diǎn)是協(xié)議過程通常比較復(fù)雜。不再就去中心化副本控制協(xié)議做進(jìn)一步詳細(xì)分析。去中心化副本控制協(xié)議通用架構(gòu)如下圖“去中心化副本控制協(xié)議示意圖”：這類協(xié)議的優(yōu)點(diǎn)是個(gè)別節(jié)點(diǎn)異常不影響整個(gè)系統(tǒng)，缺點(diǎn)是協(xié)議流程復(fù)雜，實(shí)現(xiàn)和處理效率均降低。

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

Paxos是唯一在工程中得到應(yīng)用的強(qiáng)一致性去中心化副本控制協(xié)議。Paxos協(xié)議算法是Lamport于1990年提出的一種基于消息傳遞的一致性算法。由于算法難以理解起初并沒有引起人們的重視。06年Google的三篇論文中的chubby鎖服務(wù)使用paxos作為chubby cell中的一致性算法，Paxos的人氣從此一路狂飆。Paxos 協(xié)議是少數(shù)在工程實(shí)踐中證實(shí)的強(qiáng)一致性、高可用的去中心化分布式協(xié)議。

Paxos 協(xié)議算法解決的問題是一個(gè)分布式系統(tǒng)如何就某個(gè)值（決議）達(dá)成一致。一個(gè)典型的場景是，在一個(gè)分布式數(shù)據(jù)庫系統(tǒng)中，如果各節(jié)點(diǎn)的初始狀態(tài)一致，每個(gè)節(jié)點(diǎn)都執(zhí)行相同的操作序列，那么他們最后能得到一個(gè)一致的狀態(tài)。為保證每個(gè)節(jié)點(diǎn)執(zhí)行相同的命令序列，需要在每一條指令上執(zhí)行一個(gè)“一致性算法”以保證每個(gè)節(jié)點(diǎn)看到的指令一致，是分布式計(jì)算中的重要問題。

基于Paxos 協(xié)議中，有一組完全對等的參與節(jié)點(diǎn)（稱為 accpetor），這組節(jié)點(diǎn)各自就某一事件做出決議，如果某個(gè)決議獲得了超過半數(shù)節(jié)點(diǎn)的同意則生效。Paxos 協(xié)議中只要有超過一半的節(jié)點(diǎn)正常，就可以工作，能很好對抗宕機(jī)、網(wǎng)絡(luò)分化等異常情況。

分布式系統(tǒng)和大數(shù)據(jù)

大數(shù)據(jù)作為分布式系統(tǒng)的最佳實(shí)踐，其核心是利用多臺計(jì)算機(jī)組成的分布式系統(tǒng)來協(xié)同解決單臺計(jì)算機(jī)所不能解決的大數(shù)據(jù)的計(jì)算、存儲等問題。大數(shù)據(jù)和傳統(tǒng)數(shù)據(jù)分析的最大的區(qū)別就在于問題的規(guī)模，即計(jì)算、存儲的數(shù)據(jù)量的區(qū)別。大數(shù)據(jù)將傳統(tǒng)的單機(jī)數(shù)據(jù)分析問題使用分布式來解決，首先要解決的就是如何將問題拆解為可以使用多機(jī)分布式解決，使得分布式系統(tǒng)中的每臺機(jī)器負(fù)責(zé)原問題的一個(gè)子集。由于無論是計(jì)算還是存儲，其問題輸入對象都是數(shù)據(jù)，所以如何拆解大數(shù)據(jù)依然是大數(shù)據(jù)系統(tǒng)的基本問題。

大數(shù)據(jù)系統(tǒng)采用的數(shù)據(jù)處理方式如下圖所示：

大數(shù)據(jù)系統(tǒng)的數(shù)據(jù)處理方式

對于開源大數(shù)據(jù)系統(tǒng)Hadoop的各個(gè)組件來說，其普遍采用中心化副本控制協(xié)議來簡化系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)，但是為了保證系統(tǒng)的可靠性，又在其分布式協(xié)調(diào)系統(tǒng)ZooKeeper中采用類似Paxos的去中心化協(xié)議選出Primary節(jié)點(diǎn)。在完成Primary節(jié)點(diǎn)的選舉后，系統(tǒng)就轉(zhuǎn)為中心化的副本控制協(xié)議，即由Primary節(jié)點(diǎn)負(fù)責(zé)同步更新操作到Secondary。這樣就保證了Primary節(jié)點(diǎn)的可靠性。

綜合起來，我們可以看到，無論是分布式系統(tǒng)還是大數(shù)據(jù)系統(tǒng)，其本質(zhì)都是如何對數(shù)據(jù)做合理和高效的處理。本文介紹了作為大數(shù)據(jù)基礎(chǔ)的分布式系統(tǒng)對數(shù)據(jù)的基本處理方法，包括數(shù)據(jù)的分布方式和對數(shù)據(jù)副本進(jìn)行控制的協(xié)議和算法。這些算法也是大數(shù)據(jù)各類組件技術(shù)的基礎(chǔ)。