《云計(jì)算技術(shù)——分布式計(jì)算》由會員分享，可在線閱讀，更多相關(guān)《云計(jì)算技術(shù)——分布式計(jì)算（82頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、LOGO云 計(jì) 算 原 理 與 實(shí) 踐Principles and Practice of Cloud Computing LOGOOutlinel 2.1 分布式計(jì)算概述l 2.2 分布式計(jì)算的理論基礎(chǔ)l 2.3 分布式系統(tǒng)概述l 2.4 分布式系統(tǒng)的進(jìn)階l 2.5 典型的分布式系統(tǒng) Data Science StatisticsMachine Learning Domain expertiseMathematicsData engineering LOGO2.1 分布式計(jì)算概述2.1.1 基本概念2.1.2 分布式計(jì)算的原理 LOGO2.1.1 基本概念（1）集中式計(jì)算集中式計(jì)算完全依賴于

2、一臺大型的中心計(jì)算機(jī)的處理能力，這臺中心計(jì)算機(jī)稱為主機(jī)（Host或mainframe），與中心計(jì)算機(jī)相連的終端設(shè)備具有各不相同非常低的計(jì)算能力。實(shí)際上大多數(shù)終端完全不具有處理能力，僅作為輸入輸出設(shè)備使用。（2）分布式計(jì)算 與集中式計(jì)算相反，分布式計(jì)算中，多個(gè)通過網(wǎng)絡(luò)互聯(lián)的計(jì)算機(jī)都具有一定的計(jì)算能力，它們之間互相傳遞數(shù)據(jù)，實(shí)現(xiàn)信息共享，協(xié)作共同完成一個(gè)處理任務(wù)。 LOGO中科院的定義中國科學(xué)院對分布式計(jì)算有一個(gè)定義： 分布式計(jì)算就是在兩個(gè)或多個(gè)軟件互相共享信息，這些軟件既可以在同一臺計(jì)算機(jī)上運(yùn)行，也可以在通過網(wǎng)絡(luò)連接起來的多臺計(jì)算機(jī)上運(yùn)行。 LOGO分布式計(jì)算比起其他算法具有以下幾個(gè)優(yōu)點(diǎn)。 稀有

3、資源可以共享； 通過分布式計(jì)算可以在多臺計(jì)算機(jī)上平衡計(jì)算負(fù)載； 可以把程序放在最適合運(yùn)行它的計(jì)算機(jī)上。 LOGO2.1.2 分布式計(jì)算的原理l 分布式計(jì)算就是將計(jì)算任務(wù)分?jǐn)偟酱罅康挠?jì)算節(jié)點(diǎn)上，一起完成海量的計(jì)算任務(wù)。而分布式計(jì)算的原理和并行計(jì)算類似，就是將一個(gè)復(fù)雜龐大的計(jì)算任務(wù)適當(dāng)劃分為一個(gè)個(gè)小任務(wù)，任務(wù)并行執(zhí)行，只不過分布式計(jì)算會將這些任務(wù)分配到不同的計(jì)算節(jié)點(diǎn)上，每個(gè)計(jì)算節(jié)點(diǎn)只需要完成自己的計(jì)算任務(wù)即可，可以有效分擔(dān)海量的計(jì)算任務(wù)。而每個(gè)計(jì)算節(jié)點(diǎn)也可以并行處理自身的任務(wù)，更加充分利用機(jī)器的CPU資源。最后再將每個(gè)節(jié)點(diǎn)的計(jì)算結(jié)果匯總，得到最后的計(jì)算結(jié)果。 LOGO分布式計(jì)算一般分為以下幾步：1

4、設(shè)計(jì)分布式計(jì)算模型首先要規(guī)定分布式系統(tǒng)的計(jì)算模型。計(jì)算模型決定了系統(tǒng)中各個(gè)組件應(yīng)該如何運(yùn)行，組件之間應(yīng)該如何進(jìn)行消息通信，組件和節(jié)點(diǎn)應(yīng)該如何管理等。2分布式任務(wù)分配分布式算法不同于普通算法。普通算法通常是按部就班，一步接一步完成任務(wù)。而分布式計(jì)算中計(jì)算任務(wù)是分?jǐn)偟礁鱾€(gè)節(jié)點(diǎn)上的。該算法著重解決的是能否分配任務(wù)，或如何分配任務(wù)的問題。3編寫并執(zhí)行分布式程序使用特定的分布式計(jì)算框架與計(jì)算模型，將分布式算法轉(zhuǎn)化為實(shí)現(xiàn)，并盡量保證整個(gè)集群的高效運(yùn)行，難點(diǎn)：（1）計(jì)算任務(wù)的劃分（2）多節(jié)點(diǎn)之間的通信方式 LOGO2.2 分布式計(jì)算的理論基礎(chǔ)2.2.1 ACID 原則2.2.2 CAP理論2.2.3 BAS

5、E理論2.2.4 最終一致性2.2.5 一致性散列 LOGO2.2.1 ACID原則ACID是數(shù)據(jù)庫事務(wù)正常執(zhí)行的四個(gè)原則，分別指原子性、一致性、獨(dú)立性及持久性。 LOGO2.2.1 ACID原則1A（Atomicity）原子性原子性很容易理解，也就是說事務(wù)里的所有操作要么全部做完，要么都不做，事務(wù)成功的條件是事務(wù)里的所有操作都成功，只要有一個(gè)操作失敗，整個(gè)事務(wù)就失敗，需要回滾。例如銀行轉(zhuǎn)賬，從A賬戶轉(zhuǎn)100元至B賬戶，分為兩個(gè)步驟：從A賬戶取100元；存入100元至B賬戶。這兩步要么一起完成，要么一起不完成，如果只完成第一步，第二步失敗，錢會莫名其妙少了100元。 LOGO2.2.1 ACI

6、D原則2C（Consistency）一致性一致性也比較容易理解，也就是說數(shù)據(jù)庫要一直處于一致的狀態(tài)，事務(wù)的運(yùn)行不會改變數(shù)據(jù)庫原本的一致性約束。例如現(xiàn)有完整性約束a + b = 10，如果一個(gè)事務(wù)改變了a，那么必須得改變b，使得事務(wù)結(jié)束后依然滿足a + b = 10，否則事務(wù)失敗。 LOGO2.2.1 ACID原則3I（Isolation）獨(dú)立性所謂的獨(dú)立性是指并發(fā)的事務(wù)之間不會互相影響，如果一個(gè)事務(wù)要訪問的數(shù)據(jù)正在被另外一個(gè)事務(wù)修改，只要另外一個(gè)事務(wù)未提交，它所訪問的數(shù)據(jù)就不受未提交事務(wù)的影響。例如交易是從A賬戶轉(zhuǎn)100元至B賬戶，在這個(gè)交易還未完成的情況下，如果此時(shí)B查詢自己的賬戶，是看不到

7、新增加的100元的。 LOGO2.2.1 ACID原則4D（Durability）持久性持久性是指一旦事務(wù)提交后，它所做的修改將會永久保存在數(shù)據(jù)庫上，即使出現(xiàn)宕機(jī)也不會丟失。這些原則解決了數(shù)據(jù)的一致性、系統(tǒng)的可靠性等關(guān)鍵問題，為關(guān)系數(shù)據(jù)庫技術(shù)的成熟以及在不同領(lǐng)域的大規(guī)模應(yīng)用創(chuàng)造了必要的條件。 LOGO2.2.2 CAP理論1CAP理論定義 2000年7月，加州大學(xué)伯克利分校的埃里克布魯爾（Eric Brewer）教授在ACM PODC會議上提出CAP猜想。2年后，麻省理工學(xué)院的塞思吉爾伯符（Seth Gilbert）和南希林奇（Nancy Lynch）從理論上證明了CAP。之后，CAP理論正式

8、成為分布式計(jì)算領(lǐng)域的公認(rèn)定理。 一個(gè)分布式系統(tǒng)最多只能同時(shí)滿足一致性（Consistency）、可用性（Availability）和分區(qū)容錯(cuò)性（Partition tolerance）這三項(xiàng)中的兩項(xiàng)，如圖2.1所示。 LOGO一致性一致性指“All nodes see the same data at the same time”，即更新操作成功并返回客戶端完成后，所有節(jié)點(diǎn)在同一時(shí)間的數(shù)據(jù)完全一致。對于一致性，可以分為從客戶端和服務(wù)端兩個(gè)不同的視角來看。 從客戶端來看，一致性主要指多并發(fā)訪問時(shí)更新過的數(shù)據(jù)如何獲取的問題。 從服務(wù)端來看，則是如何將更新復(fù)制分布到整個(gè)系統(tǒng)，以保證數(shù)據(jù)的最終一致性問

9、題。 LOGO 可用性l 可用性是指“Reads and writes always succeed”，即服務(wù)一直可用，而且是在正常的響應(yīng)時(shí)間內(nèi)。對于一個(gè)可用性的分布式系統(tǒng)，每一個(gè)非故障的節(jié)點(diǎn)必須對每一個(gè)請求作出響應(yīng)。也就是該系統(tǒng)使用的任何算法必須最終終止。l 當(dāng)同時(shí)要求分區(qū)容錯(cuò)性時(shí)，這是一個(gè)很強(qiáng)的定義：即使是嚴(yán)重的網(wǎng)絡(luò)錯(cuò)誤，每個(gè)請求也必須終止。好的可用性主要是指系統(tǒng)能夠很好地為用戶服務(wù)，不出現(xiàn)用戶操作失敗或者訪問超時(shí)等用戶體驗(yàn)不好的情況。通常情況下可用性和分布式數(shù)據(jù)冗余、負(fù)載均衡等有著很大的關(guān)聯(lián)。 LOGO 分區(qū)容錯(cuò)性 l 分區(qū)容錯(cuò)性指“The system continues to ope

10、rate despite arbitrary message loss or failure of part of the system”，也就是指分布式系統(tǒng)在遇到某節(jié)點(diǎn)或網(wǎng)絡(luò)分區(qū)故障的時(shí)候，仍然能夠?qū)ν馓峁M足一致性和可用性的服務(wù)。l 分區(qū)容錯(cuò)性和擴(kuò)展性緊密相關(guān)。在分布式應(yīng)用中，可能因?yàn)橐恍┓植际降脑驅(qū)е孪到y(tǒng)無法正常運(yùn)轉(zhuǎn)。好的分區(qū)容錯(cuò)性要求應(yīng)用雖然是一個(gè)分布式系統(tǒng)，但看上去卻好像是一個(gè)可以運(yùn)轉(zhuǎn)正常的整體。例如現(xiàn)在的分布式系統(tǒng)中有某一個(gè)或者幾個(gè)機(jī)器宕掉了，其他剩下的機(jī)器還能夠正常運(yùn)轉(zhuǎn)滿足系統(tǒng)需求，或者是機(jī)器之間有網(wǎng)絡(luò)異常，將分布式系統(tǒng)分隔為獨(dú)立的幾個(gè)部分，各個(gè)部分還能維持分布式系統(tǒng)的運(yùn)作，這

11、樣就具有好的分區(qū)容錯(cuò)性。 LOGO2CAP理論的闡述與證明 圖 2.2 CAP的 基 本 場 景 LOGO圖 2.3 分 布 式 系 統(tǒng) 正 常 運(yùn) 轉(zhuǎn) 的 流 程 LOGO圖 2.4 斷 開 N1和 N2之 間 的 網(wǎng) 絡(luò) LOGO3CAP權(quán)衡通過CAP理論，知道無法同時(shí)滿足一致性、可用性和分區(qū)容錯(cuò)性這三個(gè)特性，那應(yīng)該如何取舍呢？（1）CA without P：如果不要求P（不允許分區(qū)），則C（強(qiáng)一致性）和A（可用性）是可以保證的。但其實(shí)分區(qū)始終會存在，因此CA的系統(tǒng)更多的是允許分區(qū)后各子系統(tǒng)依然保持CA。（2）CP without A：如果不要求A（可用），相當(dāng)于每個(gè)請求都需要在Serve

12、r之間強(qiáng)一致，而P（分區(qū)）會導(dǎo)致同步時(shí)間無限延長，如此CP也是可以保證的。很多傳統(tǒng)的數(shù)據(jù)庫分布式事務(wù)都屬于這種模式。（3）AP without C：要高可用并允許分區(qū)，則需放棄一致性。一旦分區(qū)發(fā)生，節(jié)點(diǎn)之間可能會失去聯(lián)系，為了高可用，每個(gè)節(jié)點(diǎn)只能用本地?cái)?shù)據(jù)提供服務(wù)，而這樣會導(dǎo)致全局?jǐn)?shù)據(jù)的不一致性。現(xiàn)在眾多的NoSQL都屬于此類。 LOGO2.2.3 BASE理論l 丹普里切特（Dan Pritchett）在對大規(guī)模分布式系統(tǒng)的實(shí)踐總結(jié)過程中，提出了BASE理論，BASE理論是對CAP理論的延伸，核心思想是即使無法做到強(qiáng)一致性（Strong Consistency，CAP的一致性就是強(qiáng)一致性），

13、但應(yīng)用可以采用適合的方式達(dá)到最終一致性（Eventual Consistency）。l BASE是指基本可用（Basically Available）、軟狀態(tài)（Soft State）、最終一致性（Eventual Consistency）。 LOGO1基本可用l 基本可用是指分布式系統(tǒng)在出現(xiàn)故障的時(shí)候，允許損失部分可用性，即保證核心可用。電商大促時(shí)，為了應(yīng)對訪問量激增，部分用戶可能會被引導(dǎo)到降級頁面，服務(wù)層也可能只提供降級服務(wù)。這就是損失部分可用性的體現(xiàn)。 LOGO2軟狀態(tài)l 軟狀態(tài)是指允許系統(tǒng)存在中間狀態(tài)，而該中間狀態(tài)不會影響系統(tǒng)整體可用性。l 分布式存儲中一般一份數(shù)據(jù)至少會有三個(gè)副本，允許

14、不同節(jié)點(diǎn)間副本同步的延時(shí)就是軟狀態(tài)的體現(xiàn)。例如MySQL replication的異步復(fù)制就是這種體現(xiàn)。 LOGO3最終一致性l 最終一致性是指系統(tǒng)中的所有數(shù)據(jù)副本經(jīng)過一定時(shí)間后，最終能夠達(dá)到一致的狀態(tài)。l 弱一致性和強(qiáng)一致性相反，最終一致性是弱一致性的一種特殊情況。l BASE和ACID的區(qū)別與聯(lián)系是什么呢？ACID是傳統(tǒng)數(shù)據(jù)庫常用的設(shè)計(jì)理念，追求強(qiáng)一致性模型。BASE支持的是大型分布式系統(tǒng)，提出通過犧牲強(qiáng)一致性獲得高可用性。ACID和BASE代表了兩種截然相反的設(shè)計(jì)哲學(xué)。在分布式系統(tǒng)設(shè)計(jì)的場景中，系統(tǒng)組件對一致性要求是不同的，因此ACID和BASE又會結(jié)合使用。 LOGO2.2.4 最終一

15、致性下面以上面的場景來描述下不同程度的一致性。強(qiáng)一致性（即時(shí)一致性）：假如A先寫入了一個(gè)值到存儲系統(tǒng)，存儲系統(tǒng)保證后續(xù)A、B、C的讀取操作都將返回最新值。弱一致性：假如A先寫入了一個(gè)值到存儲系統(tǒng)，存儲系統(tǒng)不能保證后續(xù)A、B、C的讀取操作能讀取到最新值。此種情況下有一個(gè)“時(shí)間窗口”的概念，它特指從A寫入值，到后續(xù)操作A、B、C讀取到最新值這一段時(shí)間?！皶r(shí)間窗口”類似時(shí)空穿梭門，不過穿梭門是可以穿越到過去的，而一致性窗口只能穿越到未來，方法很簡單，就是“等會兒”。最終一致性：是弱一致性的一種特例。假如A首先“寫”了一個(gè)值到存儲系統(tǒng)，存儲系統(tǒng)保證如果在A、B、C后續(xù)讀取之前沒有其他寫操作更新同樣的值

16、的話，最終所有的讀取操作都會讀取到A寫入的最新值。此種情況下，如果沒有失敗發(fā)生的話，“不一致性窗口”的大小依賴于以下的幾個(gè)因素：交互延遲，系統(tǒng)的負(fù)載，以及復(fù)制技術(shù)中復(fù)本的個(gè)數(shù)。最終一致性方面最出名的系統(tǒng)可以說是DNS系統(tǒng)，當(dāng)更新一個(gè)域名的IP以后，根據(jù)配置策略以及緩存控制策略的不同，最終所有的客戶都會看到最新的值。 LOGO2.2.4 最終一致性還有一些最終一致性的變體如下。 Causal consistency（因果一致性）：如果Process A通知Process B它已經(jīng)更新了數(shù)據(jù)，那么Process B的后續(xù)讀取操作則讀取A寫入的最新值，而與A沒有因果關(guān)系的C則可以最終一致性。 Rea

17、d-your-writes consistency：如果Process A寫入了最新的值，那么Process A的后續(xù)操作都會讀取到最新值。但是其他用戶可能要過一會才可以看到。 Session consistency：此種一致性要求客戶端和存儲系統(tǒng)交互的整個(gè)會話階段保證Read-your- writes consistency。Hibernate的session提供的一致性保證就屬于此種一致性。 Monotonic read consistency：此種一致性要求如果Process A已經(jīng)讀取了對象的某個(gè)值，那么后續(xù)操作將不會讀取到更早的值。 Monotonic write consisten

18、cy：此種一致性保證系統(tǒng)會序列化執(zhí)行一個(gè)Process中的所有寫操作。 LOGO2.2.5 一致性散列1基本概念一致性散列算法（Consistent Hashing）最早在論文Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web中被提出。簡單來說，一致性散列將整個(gè)散列值空間組織成一個(gè)虛擬的圓環(huán)。假設(shè)某散列函數(shù)H的值空間為02 321（即散列值是一個(gè)32位無符號整形），整個(gè)散列空間環(huán)如圖所示。 LOGO2容錯(cuò)性和擴(kuò)展性（1）容

19、錯(cuò)性現(xiàn)假設(shè)Node C不幸宕機(jī)，可以看到此時(shí)對象A、B、D不會受到影響，只有C對象被重定位到Node D。一般來說，在一致性散列算法中，如果一臺服務(wù)器不可用，則受影響的數(shù)據(jù)僅僅是此服務(wù)器到其環(huán)空間中前一臺服務(wù)器（即沿著逆時(shí)針方向行走遇到的第一臺服務(wù)器）之間的數(shù)據(jù)，其他不會受到影響，如圖所示。 LOGO2容錯(cuò)性和擴(kuò)展性（2）擴(kuò)展性如果在系統(tǒng)中增加一臺服務(wù)器Node X，如圖所示。此時(shí)對象A、B、D不受影響，只有對象C需要重定位到新的Node X。一般來說，在一致性散列算法中，如果增加一臺服務(wù)器，則受影響的數(shù)據(jù)僅僅是新服務(wù)器到其環(huán)空間中前一臺服務(wù)器（即沿著逆時(shí)針方向行走遇到的第一臺服務(wù)器）之間數(shù)據(jù)

20、，其他數(shù)據(jù)也不會受到影響。 LOGO2容錯(cuò)性和擴(kuò)展性（3）虛擬節(jié)點(diǎn)一致性散列算法在服務(wù)節(jié)點(diǎn)太少時(shí)，容易因?yàn)楣?jié)點(diǎn)分布不均勻而造成數(shù)據(jù)傾斜問題。例如系統(tǒng)中只有兩臺服務(wù)器，其環(huán)分布如圖所示。 LOGO2.3 分布式系統(tǒng)概述2.3.1 分布式系統(tǒng)的基礎(chǔ)知識2.3.2 分布式系統(tǒng)的特性2.3.3 分布式存儲系統(tǒng)實(shí)例：Apache Hadoop LOGO2.3.1 分布式系統(tǒng)的基礎(chǔ)知識l 大數(shù)據(jù)技術(shù)的需求是推動分布式系統(tǒng)發(fā)展的一大動力。大數(shù)據(jù)存儲技術(shù)的演變最初源于互聯(lián)網(wǎng)公司的大規(guī)模分布式存儲系統(tǒng)。與傳統(tǒng)的高端服務(wù)器、高端存儲器和高端處理器不同的是，互聯(lián)網(wǎng)公司的分布式存儲系統(tǒng)由數(shù)量眾多的、低成本和高性價(jià)比的

21、普通PC服務(wù)器通過網(wǎng)絡(luò)連接而成?；ヂ?lián)網(wǎng)的業(yè)務(wù)發(fā)展很快，而且注重成本，這就使得存儲系統(tǒng)不能依靠傳統(tǒng)的縱向擴(kuò)展的方式，即先買小型機(jī)，不夠時(shí)再買中型機(jī)，甚至大型機(jī)。互聯(lián)網(wǎng)后端的分布式系統(tǒng)要求支持橫向擴(kuò)展，即通過增加普通PC服務(wù)器來提高系統(tǒng)的整體處理能力。普通PC服務(wù)器性價(jià)比高，故障率也高，需要在軟件層面實(shí)現(xiàn)自動容錯(cuò)，保證數(shù)據(jù)的一致性。另外，隨著服務(wù)器的不斷加入，需要能夠在軟件層面實(shí)現(xiàn)自動負(fù)載均衡，使系統(tǒng)的處理能力得到線性擴(kuò)展。 LOGO2.3.2 分布式系統(tǒng)的特性l 喬治庫魯里斯（George Coulouris）是分布式系統(tǒng)：概念與設(shè)計(jì)（Distributed Systems:Concepts a

22、nd Design）一書的作者，曾是劍橋大學(xué)的高級研究員。他曾經(jīng)對分布式系統(tǒng)下了一個(gè)簡單的定義：你會知道系統(tǒng)當(dāng)中的某臺計(jì)算機(jī)崩潰或停止運(yùn)行了，但是你的軟件卻永遠(yuǎn)不會。這句話雖然簡單，但是卻道出了分布式系統(tǒng)的關(guān)鍵特性。分布式系統(tǒng)的特性包括容錯(cuò)性、高可擴(kuò)展性、開放性、并發(fā)處理能力和透明性。 LOGO2.3.3 分布式存儲系統(tǒng)實(shí)例：Apache Hadoopl Hadoop是由Apache基金會開發(fā)的分布式存儲與計(jì)算框架。用戶不需要了解底層的分布式計(jì)算原理就可以輕松開發(fā)出分布式計(jì)算程序，可以充分利用集群中閑置的計(jì)算資源，將集群的真正威力調(diào)動起來。l Hadoop由兩個(gè)重要模塊組成。一個(gè)是Hadoop

23、分布式文件系統(tǒng)（Hadoop Distributed File System），顧名思義，就是一個(gè)分布式的文件系統(tǒng)，可以將文件數(shù)據(jù)分布式地存儲在集群中的不同節(jié)點(diǎn)上。另一個(gè)是MapReduce系統(tǒng)，是一個(gè)針對大量數(shù)據(jù)的分布式計(jì)算系統(tǒng)。 LOGO圖2.13 Hadoop的核心組成 LOGO1關(guān)于Apache Hadoopl Hadoop的思路來自谷歌提出的MapReduce分布式計(jì)算框架。谷歌的MapReduce框架可以把一個(gè)應(yīng)用程序分解為許多并行計(jì)算指令，跨越大量的計(jì)算節(jié)點(diǎn)運(yùn)行非常巨大的數(shù)據(jù)集。而Hadoop的MapReduce則是對谷歌MapReduce的開源實(shí)現(xiàn)。另一方面其分布式文件系統(tǒng)則是

24、谷歌的GFS的開源實(shí)現(xiàn)。l Hadoop原本是Apache Nutch中的一個(gè)子項(xiàng)目。后來Apache將MapReduce模塊與Nutch Distributed File System（NDFS）單獨(dú)抽離出來成為一個(gè)頂級項(xiàng)目。l Hadoop已經(jīng)成為目前世界上最流行的分布式計(jì)算框架之一，Apache也建立了不少與Hadoop相關(guān)的項(xiàng)目，如HBase、Cassandra、Avro、Hive、Mahout等項(xiàng)目。 LOGO2HDFS分布式文件系統(tǒng)l Hadoop分布式文件系統(tǒng)（HDFS）是一個(gè)主從式的分布式文件系統(tǒng)，是GFS的一種開源實(shí)現(xiàn)。HDFS可以利用大量廉價(jià)存儲器組成分布式存儲集群，取代昂

25、貴的集中式磁盤存儲陣列。而HDFS集群由一個(gè)NameNode和多個(gè)DataNode組成，除此之外還有用于熱備份的Secondary NameNode，防止集群出現(xiàn)單點(diǎn)故障。 LOGO2HDFS分布式文件系統(tǒng)（1）NameNodel NameNode是整個(gè)集群的管理者。它并不存儲數(shù)據(jù)本身，而負(fù)責(zé)存儲文件系統(tǒng)的元數(shù)據(jù)。它負(fù)責(zé)管理文件系統(tǒng)名稱空間，并控制外部客戶端對文件系統(tǒng)的訪問。l NameNode決定如何將文件內(nèi)容映射到DataNode的數(shù)據(jù)塊上。此外，實(shí)際數(shù)據(jù)傳輸并不會經(jīng)過NameNode，而會讓對應(yīng)的DataNode接收實(shí)際數(shù)據(jù)，并處理分布式存儲系統(tǒng)的負(fù)載均衡問題。l 整個(gè)文件系統(tǒng)只有一個(gè)N

26、ameNode，因此很明顯集群可能會出現(xiàn)單點(diǎn)故障，這點(diǎn)需要利用Secondary NameNode來解決問題。 LOGO2HDFS分布式文件系統(tǒng)（2）Secondary NameNodel Secondary NameNode是NameNode的備份節(jié)點(diǎn)，HDFS會將NameNode的數(shù)據(jù)實(shí)時(shí)備份到Secondary NameNode上，當(dāng)NameNode宕機(jī)需要重啟時(shí)，則可以利用Secondary NameNode中的數(shù)據(jù)加快NameNode的重啟恢復(fù)速度。 LOGO2HDFS分布式文件系統(tǒng)（3）DataNodel DataNode是實(shí)際的數(shù)據(jù)存儲節(jié)點(diǎn)，負(fù)責(zé)相應(yīng)NameNode創(chuàng)建、刪除和復(fù)

27、制塊的命令。NameNode會讀取來自DataNode的心跳信息，以此判斷DataNode是否存活。同一份數(shù)據(jù)會以多份副本存儲在不同的DataNode上，一旦某一個(gè)DataNode宕機(jī)，NameNode會立即采取手段來處理問題。 LOGO2HDFS分布式文件系統(tǒng)（4）MapReduce模型l MapReduce既是Hadoop中的模塊，也是一個(gè)計(jì)算模型。用戶需要自己將算法劃分成Map和Reduce兩個(gè)階段。首先將數(shù)據(jù)劃分為小塊的數(shù)據(jù)，將數(shù)據(jù)分配到不同計(jì)算節(jié)點(diǎn)的Map任務(wù)中計(jì)算，然后將計(jì)算結(jié)果匯總到Reduce節(jié)點(diǎn)中進(jìn)行合并，得出最終結(jié)果。l MapReduce系統(tǒng)也是主從式的計(jì)算系統(tǒng)。在使用Y

28、ARN后，每個(gè)集群有一個(gè)Resource-Manager，用于管理整個(gè)集群。集群中每個(gè)計(jì)算節(jié)點(diǎn)都有一個(gè)NodeManager，負(fù)責(zé)管理某個(gè)節(jié)點(diǎn)的容器并監(jiān)視其資源使用。每個(gè)應(yīng)用程序由一個(gè)MRAppMaster進(jìn)行管理。 LOGO3Apache Hadoop特性（1）高可靠性：Apache Hadoop可以可靠地將數(shù)據(jù)存儲到節(jié)點(diǎn)上。（2）高可擴(kuò)展性：Apache Hadoop的存儲和計(jì)算節(jié)點(diǎn)可以快速擴(kuò)展，并自動進(jìn)行負(fù)載均衡。（3）高效性：一方面Apache Hadoop會自動在各個(gè)節(jié)點(diǎn)之間動態(tài)調(diào)動數(shù)據(jù)，保證每個(gè)節(jié)點(diǎn)存儲均衡，另一方面讀取數(shù)據(jù)時(shí)我們可以從不同節(jié)點(diǎn)并行讀取，提高數(shù)據(jù)讀取的速度。（4）高

29、容錯(cuò)性：Apache Hadoop會將數(shù)據(jù)冗余存儲在不同節(jié)點(diǎn)上，保證數(shù)據(jù)容錯(cuò)性，計(jì)算任務(wù)失敗時(shí)也會自動重新分配任務(wù)。（5）低成本：Apache Hadoop是開源軟件，可以節(jié)省商業(yè)軟件的購買成本。同時(shí)，Apache Hadoop可以用廉價(jià)節(jié)點(diǎn)組成的集群取代昂貴的超級計(jì)算機(jī)，從而可以節(jié)省硬件成本。 LOGO2.4 分布式系統(tǒng)的進(jìn)階2.4.1 分布式存儲系統(tǒng)2.4.2 分布式計(jì)算系統(tǒng)2.4.3 分布式資源管理系統(tǒng) LOGO2.4.1 分布式存儲系統(tǒng)l 分布式存儲系統(tǒng)大致可分為5個(gè)子方向：結(jié)構(gòu)化存儲、非結(jié)構(gòu)化存儲、半結(jié)構(gòu)化存儲、In-memory 存儲及NewSQL。l 除了這5個(gè)子方向之外，分布式

30、存儲系統(tǒng)還有一系列的理論、算法、技術(shù)作為支撐，例如 Paxos、CAP理論、一致性散列、時(shí)鐘技術(shù)、2PC、3PC等。 LOGO1結(jié)構(gòu)化存儲結(jié)構(gòu)化存儲的歷史非常古老，典型的場景就是事務(wù)處理系統(tǒng)或者關(guān)系型數(shù)據(jù)庫（RDBMS）。傳統(tǒng)的結(jié)構(gòu)化存儲都是從單機(jī)做起的，例如大家耳熟能詳?shù)腗ySQL。MySQL的成長史就是互聯(lián)網(wǎng)的成長史。除了MySQL之外，PostgreSQL也是近年來勢頭非常強(qiáng)勁的一個(gè)RDBMS。傳統(tǒng)的結(jié)構(gòu)化存儲系統(tǒng)強(qiáng)調(diào)以下內(nèi)容。 結(jié)構(gòu)化的數(shù)據(jù)（例如關(guān)系表）； 強(qiáng)一致性（例如銀行系統(tǒng)，電商系統(tǒng)等場景）； 隨機(jī)訪問（索引、增刪查改、SQL）。 LOGO2非結(jié)構(gòu)化存儲與結(jié)構(gòu)化存儲不同的是，非結(jié)

31、構(gòu)化存儲強(qiáng)調(diào)的是高可擴(kuò)展性，典型的系統(tǒng)就是分布式文件系統(tǒng)。分布式文件系統(tǒng)也是一個(gè)很老的研究話題，例如20世紀(jì)70年代的Xerox Alto，80年代的NFS、AFS，90年代的xFS等。然而，這些早期的分布式文件系統(tǒng)只是起到了網(wǎng)絡(luò)磁盤的作用，其最大的問題就是不支持容錯(cuò)和錯(cuò)誤恢復(fù)。而Google在2003年SOSP會議上推出的GFS（Google File System）則走出了里程碑的一步，其開源實(shí)現(xiàn)對應(yīng)為HDFS。 LOGO3半結(jié)構(gòu)化存儲l 半結(jié)構(gòu)化存儲的提出是為了解決結(jié)非結(jié)構(gòu)化存儲系統(tǒng)隨機(jī)訪問性能差的問題。我們通常會聽到一些流行的名詞，例如NoSQL、Key-Value Store，包括對

32、象存儲等。這些都屬于半結(jié)構(gòu)化存儲研究的領(lǐng)域，其中以NoSQL的發(fā)展勢頭最為強(qiáng)勁。NoSQL系統(tǒng)既有分布式文件系統(tǒng)所具有的可擴(kuò)展性，又有結(jié)構(gòu)化存儲系統(tǒng)的隨機(jī)訪問能力（例如隨機(jī)操作），系統(tǒng)在設(shè)計(jì)時(shí)通常選擇簡單鍵值（K-V）進(jìn)行存儲，拋棄了傳統(tǒng)RDBMS里復(fù)雜SQL查詢及ACID事務(wù)。 LOGO4In-memory存儲l 隨著業(yè)務(wù)的并發(fā)越來越高，存儲系統(tǒng)對低延遲的要求也越來越高。同時(shí)由于摩爾定律以及內(nèi)存的價(jià)格不斷下降，基于內(nèi)存的存儲系統(tǒng)也開始普及。顧名思義，In-memory存儲就是將數(shù)據(jù)存儲在內(nèi)存中，從而獲得讀寫的高性能。比較有名的系統(tǒng)包括Memcached和Redis。這些基于K-V鍵值系統(tǒng)的主

33、要目的是為基于磁盤的存儲系統(tǒng)做緩存。還有一些偏向于內(nèi)存計(jì)算的系統(tǒng)，例如Distributed shared memory、RamCloud、Tachyon（Alluxio）項(xiàng)目等。 LOGO5NewSQLl 前面介紹結(jié)構(gòu)化存儲時(shí)提到，單機(jī)RDBMS系統(tǒng)在可擴(kuò)展性上面臨著巨大的挑戰(zhàn)，然而NoSQL不能很好的支持關(guān)系模型。那有沒有一種系統(tǒng)能兼?zhèn)銻DBMS的特性（例如，完整的SQL支持、ACID事務(wù)支持），又能像NoSQL系統(tǒng)那樣具有強(qiáng)大的可擴(kuò)展能力呢？2012年Google在OSDI會議上發(fā)表的Spanner，以及2013年在SIGMOD會議上發(fā)表的F1，讓業(yè)界第一次看到了關(guān)系模型和NoSQL在超

34、大規(guī)模數(shù)據(jù)中心上融合的可能性。不過由于這些系統(tǒng)大都過于復(fù)雜，沒有工業(yè)界大公司的支持還是很難做出來的。 LOGO2.4.2 分布式計(jì)算系統(tǒng)分布式計(jì)算和并行計(jì)算一樣嗎？可以這樣認(rèn)為： 傳統(tǒng)的并行計(jì)算的要求：投入更多機(jī)器，數(shù)據(jù)大小不變，計(jì)算速度更快。 分布式計(jì)算的要求：投入更多的機(jī)器，能處理更大的數(shù)據(jù)。 LOGO1傳統(tǒng)基于消息的系統(tǒng)l 這類系統(tǒng)里比較有代表性的就是MPI（Message Passing Interface）。目前比較流行的兩個(gè)MPI實(shí)現(xiàn)是MPICH2和OpenMPI。MPI這個(gè)框架非常靈活，對程序的結(jié)構(gòu)幾乎沒有太多約束，以至于人們有時(shí)把MPI稱為一組接口API，而不是系統(tǒng)框架。MPI

35、除了提供消息傳遞接口之外，其框架還實(shí)現(xiàn)了資源管理和分配，以及調(diào)度的功能。除此之外，MPI在高性能計(jì)算里也被廣泛使用，通常可以和 Infiniband 這樣的高速網(wǎng)絡(luò)無縫結(jié)合。 LOGO2MapReduce家族系統(tǒng)l 這一類系統(tǒng)又稱作Dataflow系統(tǒng)，其中以Hadoop MapReduce和Spark為代表。其實(shí)在學(xué)術(shù)界有很多類似的系統(tǒng)，例如Dryad、Twister等。這一類系統(tǒng)的特點(diǎn)是將計(jì)算抽象成為高層操作，例如像Map、Reduce、Filter這樣的函數(shù)式算子，將算子組合成有向無環(huán)圖DAG，然后由后端的調(diào)度引擎進(jìn)行并行化調(diào)度。其中，MapReduce系統(tǒng)屬于比較簡單的DAG，只有Ma

36、p和reduce兩層節(jié)點(diǎn)。MapReduce這樣的系統(tǒng)之所以可以擴(kuò)展到超大規(guī)模的集群上運(yùn)行，就是因?yàn)槠渫陚涞娜蒎e(cuò)機(jī)制。在Hadoop社區(qū)還有很多基于MapReduce框架的衍生產(chǎn)品，例如Hive（一種并行數(shù)據(jù)庫OLAP）、Pig（交互式數(shù)據(jù)操作）等。 LOGO3圖計(jì)算系統(tǒng)l 圖計(jì)算系統(tǒng)是分布式計(jì)算的另一個(gè)分支，這些系統(tǒng)都是把計(jì)算過程抽象成圖，然后在不同節(jié)點(diǎn)分布式執(zhí)行，例如PageRank這樣的任務(wù)，很適合用圖計(jì)算系統(tǒng)來表示。l 大數(shù)據(jù)圖是無法使用單臺機(jī)器進(jìn)行處理的，如果對大圖數(shù)據(jù)進(jìn)行并行處理，對于每一個(gè)頂點(diǎn)之間都是連通的圖來講，難以分割成若干完全獨(dú)立的子圖進(jìn)行獨(dú)立的并行處理。即使可以分割，也會

37、面臨并行機(jī)器的協(xié)同處理，以及將最后的處理結(jié)果進(jìn)行合并等一系列問題。這需要圖數(shù)據(jù)處理系統(tǒng)選取合適的圖分割以及圖計(jì)算模型來迎接挑戰(zhàn)并解決問題。 LOGO4基于狀態(tài)的系統(tǒng)l 這一類系統(tǒng)主要包括2010年在OSDI會議上推出的Piccolo，以及后來2012年在NIPS會議上 Google推出的開源機(jī)器學(xué)習(xí)系統(tǒng)DistBelief，再到后來被機(jī)器學(xué)習(xí)領(lǐng)域廣泛應(yīng)用的參數(shù)服務(wù)器（Parameter Server）架構(gòu)。 LOGO5實(shí)時(shí)流處理系統(tǒng)l 實(shí)時(shí)流處理系統(tǒng)是為高效實(shí)時(shí)地處理流式數(shù)據(jù)而提供服務(wù)的，更關(guān)注數(shù)據(jù)處理的實(shí)時(shí)性，能夠更加快速地為決策提供支持。流處理是由復(fù)雜事件處理（CEP）發(fā)展而來的，流處理模

38、式包括兩種：連續(xù)查詢處理模式、可擴(kuò)展數(shù)據(jù)流模式。 LOGO2.4.3 分布式資源管理系統(tǒng) 從支持離線處理的MapReduce，到支持在線處理的Storm，從迭代式計(jì)算框架Spark到流式處理框架S4，各種框架誕生于不同的公司或者實(shí)驗(yàn)室，它們各有所長，各自解決了某一類應(yīng)用問題。而在大部分互聯(lián)網(wǎng)公司中，這幾種框架可能都會采用，例如對于搜索引擎公司，可能的技術(shù)方案如下：網(wǎng)頁建索引采用MapReduce框架，自然語言處理/數(shù)據(jù)挖掘采用Spark（網(wǎng)頁P(yáng)ageRank計(jì)算、聚類分類算法等），對性能要求很高的數(shù)據(jù)挖掘算法用MPI等?？紤]到資源利用率、運(yùn)維成本、數(shù)據(jù)共享等因素，公司一般希望將所有這些框架部署

39、到一個(gè)公共的集群中，讓它們共享集群的資源，并對資源進(jìn)行統(tǒng)一使用，這樣，便誕生了資源統(tǒng)一管理與調(diào)度平臺，典型的代表是Mesos和YARN。 LOGO資源統(tǒng)一管理和調(diào)度平臺具有以下特點(diǎn)：1支持多種計(jì)算框架2擴(kuò)展性3容錯(cuò)性4高資源利用率5細(xì)粒度的資源分配 LOGO2.5 典型的分布式系統(tǒng)2.5.1 網(wǎng)格系統(tǒng)2.5.2 P2P系統(tǒng)2.5.3 透明計(jì)算2.5.4 區(qū)塊鏈系統(tǒng) LOGO2.5.1 網(wǎng)格系統(tǒng)l 網(wǎng)格是一種能夠?qū)⒍嘟M織擁有和管理的計(jì)算機(jī)、網(wǎng)絡(luò)、數(shù)據(jù)庫和科學(xué)儀器綜合協(xié)同使用的基礎(chǔ)設(shè)施。網(wǎng)格應(yīng)用程序大多涉及需要跨越組織界限的可安全共享的大規(guī)模數(shù)據(jù)和/或計(jì)算資源。這使網(wǎng)格應(yīng)用程序的管理和部署成為一項(xiàng)

40、復(fù)雜的任務(wù)。在混雜的網(wǎng)格環(huán)境中，網(wǎng)格中間件為用戶提供了無縫的計(jì)算能力和統(tǒng)一訪問資源能力。目前，世界范圍內(nèi)已經(jīng)發(fā)展有數(shù)個(gè)工具包和系統(tǒng)，其中大部分是學(xué)術(shù)研究項(xiàng)目的成果。 LOGO1. 網(wǎng)格的概念l Globus定義網(wǎng)格為：一種能夠整合的合作使用的由多家組織所擁有和管理的高端計(jì)算機(jī)、網(wǎng)絡(luò)、數(shù)據(jù)庫、實(shí)驗(yàn)設(shè)備的基礎(chǔ)設(shè)施。l 由Gridbus提出一種基于效能的網(wǎng)格定義：網(wǎng)格是一類并行、分布系統(tǒng)，能夠在運(yùn)行時(shí)動態(tài)分享、選擇、聚合地理散布的自治資源，依據(jù)它們的可用性、能力、性能、代價(jià)以及用戶對服務(wù)質(zhì)量的需求。 LOGO2. 網(wǎng)格的組成 LOGO3Globus工具包l Globus是一種研究網(wǎng)格環(huán)境中互操作的中

41、間件技術(shù)，為科學(xué)和工程上的網(wǎng)格計(jì)算應(yīng)用程序提供基本的支撐環(huán)境。它定義了構(gòu)建計(jì)算網(wǎng)格的一組基本服務(wù)和功能，包括安全、資源管理、通信、目錄管理等基本服務(wù)，被許多應(yīng)用網(wǎng)格項(xiàng)目采用。 LOGO2.5.2 P2P系統(tǒng) 對等網(wǎng)絡(luò)系統(tǒng)（Peer-to-Peer），簡稱P2P系統(tǒng)，即媒體及公眾所稱的“點(diǎn)對點(diǎn)系統(tǒng)”，是一種應(yīng)用在對等者（Peer）之間分配任務(wù)和工作負(fù)載的分布式應(yīng)用架構(gòu)的系統(tǒng)。對等網(wǎng)絡(luò)的思想是：網(wǎng)絡(luò)的所有參與者共享他們所擁有的一部分硬件資源，包括處理器資源、存儲資源和網(wǎng)絡(luò)資源等，這些共享資源可以通過網(wǎng)絡(luò)被其他對等者直接訪問并為之提供服務(wù)和內(nèi)容。 LOGOP2P系統(tǒng)性質(zhì)（1）高度分散化（2）自組織性

42、（3）多管理域 LOGOP2P系統(tǒng)特點(diǎn)（1）部署低門檻（2）有機(jī)增長（3）對故障與攻擊的恢復(fù)力（4）資源的豐富性與多樣性 LOGO對等網(wǎng)絡(luò)應(yīng)用（1）共享及分發(fā)文件（2）流媒體（3）電話（4）志愿計(jì)算 LOGO2.5.3 透明計(jì)算透 明 計(jì) 算 是 一 種 用 戶 無 須 感 知 計(jì) 算 機(jī) 操 作 系統(tǒng) 、 中 間 件 、 應(yīng) 用 程 序 和 通 信 網(wǎng) 絡(luò) 的 具 體 所在 ， 只 需 根 據(jù) 自 己 的 需 求 ， 通 過 網(wǎng) 絡(luò) 從 所 使用 的 各 種 終 端 設(shè) 備 （ 包 括 固 定 、 移 動 及 家 庭中 的 各 類 終 端 設(shè) 備 ） 中 選 擇 并 使 用 相 應(yīng) 服 務(wù)（

43、 例 如 計(jì) 算 、 電 話 、 電 視 、 上 網(wǎng) 和 娛 樂 等 ）的 計(jì) 算 模 式 。 LOGO圖2.20 透明計(jì)算模式 LOGO透明計(jì)算核心技術(shù)（1）透明云架構(gòu) LOGO透明計(jì)算核心技術(shù)（2）元操作系統(tǒng)（Meta OS）（3）客戶端實(shí)現(xiàn) 圖 2.23 HTML5與 傳 統(tǒng) APP的 對 比 LOGO2.5.4 區(qū)塊鏈系統(tǒng)區(qū) 塊 鏈 （ Blockchain） 是 一 種 去 中 心 化 、 不 可 篡 改 、可 追 溯 、 多 方 共 同 維 護(hù) 的 分 布 式 數(shù) 據(jù) 庫 系 統(tǒng) ， 能 夠?qū)?傳 統(tǒng) 單 方 維 護(hù) 的 僅 涉 及 自 己 業(yè) 務(wù) 的 多 個(gè) 孤 立 數(shù) 據(jù)庫 整

44、 合 在 一 起 ， 分 布 式 地 存 儲 在 多 方 共 同 維 護(hù) 的 多個(gè) 節(jié) 點(diǎn) ， 任 何 一 方 都 無 法 完 全 控 制 這 些 數(shù) 據(jù) ， 只 能按 照 嚴(yán) 格 的 規(guī) 則 和 共 識 進(jìn) 行 更 新 ， 從 而 實(shí) 現(xiàn) 了 可 信的 多 方 間 的 信 息 共 享 和 監(jiān) 督 ， 避 免 了 煩 瑣 的 人 工 對賬 ， 提 高 了 業(yè) 務(wù) 處 理 效 率 ， 降 低 了 交 易 成 本 。 LOGO區(qū)塊鏈的核心特征 塊鏈結(jié)構(gòu)：每一塊有時(shí)間戳，每一塊都含有前面一塊的散列加密信息，對每個(gè)交易進(jìn)行驗(yàn)證。 多獨(dú)立拷貝存儲：區(qū)塊鏈系統(tǒng)的每個(gè)節(jié)點(diǎn)都存儲同樣信息。 拜占庭容錯(cuò)：容忍少

45、于1/3 節(jié)點(diǎn)惡意作弊或被黑客攻擊，系統(tǒng)仍然能夠正常工作。 LOGO區(qū)塊鏈模式（1）模式1：、+ P2P + 挖礦。（2）模式2：、+ P2P + 挖礦 + 默克爾-帕特里夏樹（Merkel Patricia tree） LOGO區(qū)塊鏈體系架構(gòu) LOGO區(qū)塊鏈應(yīng)用（1）數(shù)字創(chuàng)意的助推器（2）萬物互聯(lián)的萬物賬簿（3）供應(yīng)鏈端到端防偽（4）隱私數(shù)據(jù)保護(hù)的密碼機(jī)（5）互聯(lián)網(wǎng)新技術(shù) LOGO 分 布 式 計(jì) 算 概 述 分 布 式 計(jì) 算 的 理 論 基 礎(chǔ) 分 布 式 系 統(tǒng) 概 述 分 布 式 系 統(tǒng) 的 進(jìn) 階 典 型 的 分 布 式 系 統(tǒng)小 結(jié) LOGO課內(nèi)復(fù)習(xí)1分布式計(jì)算的定義和特征是什么

46、？2什么是ACID原則？3什么是CAP理論？4什么是BASE理論？5如何理解最終一致性？6分布式存儲與分布式計(jì)算的區(qū)別與聯(lián)系是什么？ LOGO課外思考1在日常生活中，為什么我們所接觸到的分布式系統(tǒng)越來越多了？2CAP定理中的幾個(gè)關(guān)鍵因素為什么不能同時(shí)保證？不同的組合有什么樣的應(yīng)用場景？3通過了解區(qū)塊鏈的背景，說說你所理解的區(qū)塊鏈作為一種分布式系統(tǒng)背后的全新理念。 LOGO動手實(shí)踐1Globus是一個(gè)開放源碼的網(wǎng)格的基礎(chǔ)平臺，Globus Toolkit工具包是一個(gè)構(gòu)筑網(wǎng)格計(jì)算環(huán)境的中間件，提供基本的資源定位、管理、通信和安全等服務(wù)。該計(jì)算工具包是模塊化的，允許用戶按自己的需要定制環(huán)境。利用這套工具可以建立計(jì)算網(wǎng)格，并可以進(jìn)行網(wǎng)格應(yīng)用的開發(fā)。任務(wù)：通過Globus Toolkit的官方網(wǎng)站下載并安裝使用Globus Toolkit。 LOGO動手實(shí)踐2HTCondor是一個(gè)專門用于計(jì)算密集型作業(yè)的負(fù)載管理系統(tǒng)，它為用戶提供了作業(yè)排隊(duì)機(jī)制、調(diào)度策略、優(yōu)先計(jì)劃、資源監(jiān)測和資源管理，誕生于美國威斯康星大學(xué)麥迪遜分校。任務(wù)：通過HTCondor的官方網(wǎng)站下載并安裝使用HTCondor，了解它是如何實(shí)現(xiàn)大吞吐量計(jì)算過程的。