云計算技術(shù)-分布式計算課件

云計算原理與實踐

PrinciplesandPracticeofCloudComputing1BG云計算原理與實踐

PrinciplesandPractiOutline2.1分布式計算概述

2.2分布式計算的理論基礎2.3分布式系統(tǒng)概述2.4分布式系統(tǒng)的進階2.5典型的分布式系統(tǒng)DataScienceStatisticsMachineLearningDomainexpertiseMathematicsDataengineering2BGOutline2.1分布式計算概述 DataScien2.1分布式計算概述

2.1.1基本概念2.1.2分布式計算的原理3BG2.1分布式計算概述 2.1.1基本概念3BG2.1.1基本概念（1）集中式計算集中式計算完全依賴于一臺大型的中心計算機的處理能力，這臺中心計算機稱為主機（Host或mainframe），與中心計算機相連的終端設備具有各不相同非常低的計算能力。實際上大多數(shù)終端完全不具有處理能力，僅作為輸入輸出設備使用。（2）分布式計算

與集中式計算相反，分布式計算中，多個通過網(wǎng)絡互聯(lián)的計算機都具有一定的計算能力，它們之間互相傳遞數(shù)據(jù)，實現(xiàn)信息共享，協(xié)作共同完成一個處理任務。4BG2.1.1基本概念（1）集中式計算4BG中科院的定義中國科學院對分布式計算有一個定義：

分布式計算就是在兩個或多個軟件互相共享信息，這些軟件既可以在同一臺計算機上運行，也可以在通過網(wǎng)絡連接起來的多臺計算機上運行。5BG中科院的定義中國科學院對分布式計算有一個定義：5BG分布式計算比起其他算法具有以下幾個優(yōu)點。

稀有資源可以共享；

通過分布式計算可以在多臺計算機上平衡計算負載；

可以把程序放在最適合運行它的計算機上。6BG分布式計算比起其他算法具有以下幾個優(yōu)點。6BG2.1.2分布式計算的原理分布式計算就是將計算任務分攤到大量的計算節(jié)點上，一起完成海量的計算任務。而分布式計算的原理和并行計算類似，就是將一個復雜龐大的計算任務適當劃分為一個個小任務，任務并行執(zhí)行，只不過分布式計算會將這些任務分配到不同的計算節(jié)點上，每個計算節(jié)點只需要完成自己的計算任務即可，可以有效分擔海量的計算任務。而每個計算節(jié)點也可以并行處理自身的任務，更加充分利用機器的CPU資源。最后再將每個節(jié)點的計算結(jié)果匯總，得到最后的計算結(jié)果。7BG2.1.2分布式計算的原理分布式計算就是將計算任務分攤到分布式計算一般分為以下幾步：1．設計分布式計算模型首先要規(guī)定分布式系統(tǒng)的計算模型。計算模型決定了系統(tǒng)中各個組件應該如何運行，組件之間應該如何進行消息通信，組件和節(jié)點應該如何管理等。2．分布式任務分配分布式算法不同于普通算法。普通算法通常是按部就班，一步接一步完成任務。而分布式計算中計算任務是分攤到各個節(jié)點上的。該算法著重解決的是能否分配任務，或如何分配任務的問題。3．編寫并執(zhí)行分布式程序使用特定的分布式計算框架與計算模型，將分布式算法轉(zhuǎn)化為實現(xiàn)，并盡量保證整個集群的高效運行，難點：（1）計算任務的劃分（2）多節(jié)點之間的通信方式8BG分布式計算一般分為以下幾步：8BG2.2分布式計算的理論基礎2.2.1ACID原則2.2.2CAP理論2.2.3BASE理論2.2.4最終一致性2.2.5一致性散列9BG2.2分布式計算的理論基礎2.2.1ACID原則9B2.2.1ACID原則ACID是數(shù)據(jù)庫事務正常執(zhí)行的四個原則，分別指原子性、一致性、獨立性及持久性。10BG2.2.1ACID原則ACID是數(shù)據(jù)庫事務正常執(zhí)行的四個2.2.1ACID原則1．A（Atomicity）—原子性原子性很容易理解，也就是說事務里的所有操作要么全部做完，要么都不做，事務成功的條件是事務里的所有操作都成功，只要有一個操作失敗，整個事務就失敗，需要回滾。例如銀行轉(zhuǎn)賬，從A賬戶轉(zhuǎn)100元至B賬戶，分為兩個步驟：①從A賬戶取100元；②存入100元至B賬戶。這兩步要么一起完成，要么一起不完成，如果只完成第一步，第二步失敗，錢會莫名其妙少了100元。11BG2.2.1ACID原則1．A（Atomicity）—原子2.2.1ACID原則2．C（Consistency）—一致性一致性也比較容易理解，也就是說數(shù)據(jù)庫要一直處于一致的狀態(tài)，事務的運行不會改變數(shù)據(jù)庫原本的一致性約束。例如現(xiàn)有完整性約束a+b=10，如果一個事務改變了a，那么必須得改變b，使得事務結(jié)束后依然滿足a+b=10，否則事務失敗。12BG2.2.1ACID原則2．C（Consistency）—2.2.1ACID原則3．I（Isolation）—獨立性所謂的獨立性是指并發(fā)的事務之間不會互相影響，如果一個事務要訪問的數(shù)據(jù)正在被另外一個事務修改，只要另外一個事務未提交，它所訪問的數(shù)據(jù)就不受未提交事務的影響。例如交易是從A賬戶轉(zhuǎn)100元至B賬戶，在這個交易還未完成的情況下，如果此時B查詢自己的賬戶，是看不到新增加的100元的。13BG2.2.1ACID原則3．I（Isolation）—獨立2.2.1ACID原則4．D（Durability）—持久性持久性是指一旦事務提交后，它所做的修改將會永久保存在數(shù)據(jù)庫上，即使出現(xiàn)宕機也不會丟失。這些原則解決了數(shù)據(jù)的一致性、系統(tǒng)的可靠性等關(guān)鍵問題，為關(guān)系數(shù)據(jù)庫技術(shù)的成熟以及在不同領(lǐng)域的大規(guī)模應用創(chuàng)造了必要的條件。14BG2.2.1ACID原則14BG2.2.2CAP理論1．CAP理論定義

2000年7月，加州大學伯克利分校的埃里克·布魯爾（EricBrewer）教授在ACMPODC會議上提出CAP猜想。2年后，麻省理工學院的塞思·吉爾伯符（SethGilbert）和南?！ち制妫∟ancyLynch）從理論上證明了CAP。之后，CAP理論正式成為分布式計算領(lǐng)域的公認定理。一個分布式系統(tǒng)最多只能同時滿足一致性（Consistency）、可用性（Availability）和分區(qū)容錯性（Partitiontolerance）這三項中的兩項，如圖2.1所示。15BG2.2.2CAP理論1．CAP理論定義

15BG一致性一致性指“Allnodesseethesamedataatthesametime”，即更新操作成功并返回客戶端完成后，所有節(jié)點在同一時間的數(shù)據(jù)完全一致。對于一致性，可以分為從客戶端和服務端兩個不同的視角來看。

從客戶端來看，一致性主要指多并發(fā)訪問時更新過的數(shù)據(jù)如何獲取的問題。

從服務端來看，則是如何將更新復制分布到整個系統(tǒng)，以保證數(shù)據(jù)的最終一致性問題。16BG一致性一致性指“Allnodesseethesame

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

分區(qū)容錯性

分區(qū)容錯性指“Thesystemcontinuestooperatedespitearbitrarymessagelossorfailureofpartofthesystem”，也就是指分布式系統(tǒng)在遇到某節(jié)點或網(wǎng)絡分區(qū)故障的時候，仍然能夠?qū)ν馓峁M足一致性和可用性的服務。分區(qū)容錯性和擴展性緊密相關(guān)。在分布式應用中，可能因為一些分布式的原因?qū)е孪到y(tǒng)無法正常運轉(zhuǎn)。好的分區(qū)容錯性要求應用雖然是一個分布式系統(tǒng)，但看上去卻好像是一個可以運轉(zhuǎn)正常的整體。例如現(xiàn)在的分布式系統(tǒng)中有某一個或者幾個機器宕掉了，其他剩下的機器還能夠正常運轉(zhuǎn)滿足系統(tǒng)需求，或者是機器之間有網(wǎng)絡異常，將分布式系統(tǒng)分隔為獨立的幾個部分，各個部分還能維持分布式系統(tǒng)的運作，這樣就具有好的分區(qū)容錯性。18BG分區(qū)容錯性分區(qū)容錯性指“Thesystemcont2．CAP理論的闡述與證明圖2.2CAP的基本場景19BG2．CAP理論的闡述與證明圖2.2CAP的基本場景19圖2.3分布式系統(tǒng)正常運轉(zhuǎn)的流程20BG圖2.3分布式系統(tǒng)正常運轉(zhuǎn)的流程20BG圖2.4斷開N1和N2之間的網(wǎng)絡21BG圖2.4斷開N1和N2之間的網(wǎng)絡21BG3．CAP權(quán)衡通過CAP理論，知道無法同時滿足一致性、可用性和分區(qū)容錯性這三個特性，那應該如何取舍呢？（1）CAwithoutP：如果不要求P（不允許分區(qū)），則C（強一致性）和A（可用性）是可以保證的。但其實分區(qū)始終會存在，因此CA的系統(tǒng)更多的是允許分區(qū)后各子系統(tǒng)依然保持CA。（2）CPwithoutA：如果不要求A（可用），相當于每個請求都需要在Server之間強一致，而P（分區(qū)）會導致同步時間無限延長，如此CP也是可以保證的。很多傳統(tǒng)的數(shù)據(jù)庫分布式事務都屬于這種模式。（3）APwithoutC：要高可用并允許分區(qū)，則需放棄一致性。一旦分區(qū)發(fā)生，節(jié)點之間可能會失去聯(lián)系，為了高可用，每個節(jié)點只能用本地數(shù)據(jù)提供服務，而這樣會導致全局數(shù)據(jù)的不一致性?，F(xiàn)在眾多的NoSQL都屬于此類。22BG3．CAP權(quán)衡通過CAP理論，知道無法同時滿足一致性、可用性2.2.3BASE理論丹·普里切特（DanPritchett）在對大規(guī)模分布式系統(tǒng)的實踐總結(jié)過程中，提出了BASE理論，BASE理論是對CAP理論的延伸，核心思想是即使無法做到強一致性（StrongConsistency，CAP的一致性就是強一致性），但應用可以采用適合的方式達到最終一致性（EventualConsistency）。BASE是指基本可用（BasicallyAvailable）、軟狀態(tài)（SoftState）、最終一致性（EventualConsistency）。23BG2.2.3BASE理論丹·普里切特（DanPritch1．基本可用基本可用是指分布式系統(tǒng)在出現(xiàn)故障的時候，允許損失部分可用性，即保證核心可用。電商大促時，為了應對訪問量激增，部分用戶可能會被引導到降級頁面，服務層也可能只提供降級服務。這就是損失部分可用性的體現(xiàn)。24BG1．基本可用基本可用是指分布式系統(tǒng)在出現(xiàn)故障的時候，允許損失2．軟狀態(tài)軟狀態(tài)是指允許系統(tǒng)存在中間狀態(tài)，而該中間狀態(tài)不會影響系統(tǒng)整體可用性。分布式存儲中一般一份數(shù)據(jù)至少會有三個副本，允許不同節(jié)點間副本同步的延時就是軟狀態(tài)的體現(xiàn)。例如MySQLreplication的異步復制就是這種體現(xiàn)。25BG2．軟狀態(tài)軟狀態(tài)是指允許系統(tǒng)存在中間狀態(tài)，而該中間狀態(tài)不會影3．最終一致性最終一致性是指系統(tǒng)中的所有數(shù)據(jù)副本經(jīng)過一定時間后，最終能夠達到一致的狀態(tài)。弱一致性和強一致性相反，最終一致性是弱一致性的一種特殊情況。BASE和ACID的區(qū)別與聯(lián)系是什么呢？ACID是傳統(tǒng)數(shù)據(jù)庫常用的設計理念，追求強一致性模型。BASE支持的是大型分布式系統(tǒng)，提出通過犧牲強一致性獲得高可用性。ACID和BASE代表了兩種截然相反的設計哲學。在分布式系統(tǒng)設計的場景中，系統(tǒng)組件對一致性要求是不同的，因此ACID和BASE又會結(jié)合使用。26BG3．最終一致性最終一致性是指系統(tǒng)中的所有數(shù)據(jù)副本經(jīng)過一定時間2.2.4最終一致性下面以上面的場景來描述下不同程度的一致性。

強一致性（即時一致性）：假如A先寫入了一個值到存儲系統(tǒng)，存儲系統(tǒng)保證后續(xù)A、B、C的讀取操作都將返回最新值。

弱一致性：假如A先寫入了一個值到存儲系統(tǒng)，存儲系統(tǒng)不能保證后續(xù)A、B、C的讀取操作能讀取到最新值。此種情況下有一個“時間窗口”的概念，它特指從A寫入值，到后續(xù)操作A、B、C讀取到最新值這一段時間?！皶r間窗口”類似時空穿梭門，不過穿梭門是可以穿越到過去的，而一致性窗口只能穿越到未來，方法很簡單，就是“等會兒”。

最終一致性：是弱一致性的一種特例。假如A首先“寫”了一個值到存儲系統(tǒng)，存儲系統(tǒng)保證如果在A、B、C后續(xù)讀取之前沒有其他寫操作更新同樣的值的話，最終所有的讀取操作都會讀取到A寫入的最新值。此種情況下，如果沒有失敗發(fā)生的話，“不一致性窗口”的大小依賴于以下的幾個因素：交互延遲，系統(tǒng)的負載，以及復制技術(shù)中復本的個數(shù)。最終一致性方面最出名的系統(tǒng)可以說是DNS系統(tǒng)，當更新一個域名的IP以后，根據(jù)配置策略以及緩存控制策略的不同，最終所有的客戶都會看到最新的值。27BG2.2.4最終一致性下面以上面的場景來描述下不同程度的一2.2.4最終一致性還有一些最終一致性的變體如下。

Causalconsistency（因果一致性）：如果ProcessA通知ProcessB它已經(jīng)更新了數(shù)據(jù)，那么ProcessB的后續(xù)讀取操作則讀取A寫入的最新值，而與A沒有因果關(guān)系的C則可以最終一致性。

Read-your-writesconsistency：如果ProcessA寫入了最新的值，那么ProcessA的后續(xù)操作都會讀取到最新值。但是其他用戶可能要過一會才可以看到。

Sessionconsistency：此種一致性要求客戶端和存儲系統(tǒng)交互的整個會話階段保證Read-your-writesconsistency。Hibernate的session提供的一致性保證就屬于此種一致性。

Monotonicreadconsistency：此種一致性要求如果ProcessA已經(jīng)讀取了對象的某個值，那么后續(xù)操作將不會讀取到更早的值。

Monotonicwriteconsistency：此種一致性保證系統(tǒng)會序列化執(zhí)行一個Process中的所有寫操作。28BG2.2.4最終一致性還有一些最終一致性的變體如下。28B2.2.5一致性散列1．基本概念一致性散列算法（ConsistentHashing）最早在論文ConsistentHashingandRandomTrees:DistributedCachingProtocolsforRelievingHotSpotsontheWorldWideWeb中被提出。簡單來說，一致性散列將整個散列值空間組織成一個虛擬的圓環(huán)。假設某散列函數(shù)H的值空間為0～232－1（即散列值是一個32位無符號整形），整個散列空間環(huán)如圖所示。29BG2.2.5一致性散列1．基本概念29BG2．容錯性和擴展性（1）容錯性現(xiàn)假設NodeC不幸宕機，可以看到此時對象A、B、D不會受到影響，只有C對象被重定位到NodeD。一般來說，在一致性散列算法中，如果一臺服務器不可用，則受影響的數(shù)據(jù)僅僅是此服務器到其環(huán)空間中前一臺服務器（即沿著逆時針方向行走遇到的第一臺服務器）之間的數(shù)據(jù)，其他不會受到影響，如圖所示。30BG2．容錯性和擴展性（1）容錯性30BG2．容錯性和擴展性（2）擴展性如果在系統(tǒng)中增加一臺服務器NodeX，如圖所示。此時對象A、B、D不受影響，只有對象C需要重定位到新的NodeX。一般來說，在一致性散列算法中，如果增加一臺服務器，則受影響的數(shù)據(jù)僅僅是新服務器到其環(huán)空間中前一臺服務器（即沿著逆時針方向行走遇到的第一臺服務器）之間數(shù)據(jù)，其他數(shù)據(jù)也不會受到影響。31BG2．容錯性和擴展性（2）擴展性31BG2．容錯性和擴展性（3）虛擬節(jié)點一致性散列算法在服務節(jié)點太少時，容易因為節(jié)點分布不均勻而造成數(shù)據(jù)傾斜問題。例如系統(tǒng)中只有兩臺服務器，其環(huán)分布如圖所示。32BG2．容錯性和擴展性（3）虛擬節(jié)點32BG2.3分布式系統(tǒng)概述2.3.1分布式系統(tǒng)的基礎知識

2.3.2分布式系統(tǒng)的特性

2.3.3分布式存儲系統(tǒng)實例：ApacheHadoop

33BG2.3分布式系統(tǒng)概述2.3.1分布式系統(tǒng)的基礎知識 32.3.1分布式系統(tǒng)的基礎知識

大數(shù)據(jù)技術(shù)的需求是推動分布式系統(tǒng)發(fā)展的一大動力。大數(shù)據(jù)存儲技術(shù)的演變最初源于互聯(lián)網(wǎng)公司的大規(guī)模分布式存儲系統(tǒng)。與傳統(tǒng)的高端服務器、高端存儲器和高端處理器不同的是，互聯(lián)網(wǎng)公司的分布式存儲系統(tǒng)由數(shù)量眾多的、低成本和高性價比的普通PC服務器通過網(wǎng)絡連接而成?；ヂ?lián)網(wǎng)的業(yè)務發(fā)展很快，而且注重成本，這就使得存儲系統(tǒng)不能依靠傳統(tǒng)的縱向擴展的方式，即先買小型機，不夠時再買中型機，甚至大型機。互聯(lián)網(wǎng)后端的分布式系統(tǒng)要求支持橫向擴展，即通過增加普通PC服務器來提高系統(tǒng)的整體處理能力。普通PC服務器性價比高，故障率也高，需要在軟件層面實現(xiàn)自動容錯，保證數(shù)據(jù)的一致性。另外，隨著服務器的不斷加入，需要能夠在軟件層面實現(xiàn)自動負載均衡，使系統(tǒng)的處理能力得到線性擴展。34BG2.3.1分布式系統(tǒng)的基礎知識 大數(shù)據(jù)技術(shù)的需求是推動分2.3.2分布式系統(tǒng)的特性

喬治·庫魯里斯（GeorgeCoulouris）是《分布式系統(tǒng)：概念與設計》（DistributedSystems:ConceptsandDesign）一書的作者，曾是劍橋大學的高級研究員。他曾經(jīng)對分布式系統(tǒng)下了一個簡單的定義：你會知道系統(tǒng)當中的某臺計算機崩潰或停止運行了，但是你的軟件卻永遠不會。這句話雖然簡單，但是卻道出了分布式系統(tǒng)的關(guān)鍵特性。分布式系統(tǒng)的特性包括容錯性、高可擴展性、開放性、并發(fā)處理能力和透明性。35BG2.3.2分布式系統(tǒng)的特性 喬治·庫魯里斯（George2.3.3分布式存儲系統(tǒng)實例：ApacheHadoop

Hadoop是由Apache基金會開發(fā)的分布式存儲與計算框架。用戶不需要了解底層的分布式計算原理就可以輕松開發(fā)出分布式計算程序，可以充分利用集群中閑置的計算資源，將集群的真正威力調(diào)動起來。Hadoop由兩個重要模塊組成。一個是Hadoop分布式文件系統(tǒng)（HadoopDistributedFileSystem），顧名思義，就是一個分布式的文件系統(tǒng)，可以將文件數(shù)據(jù)分布式地存儲在集群中的不同節(jié)點上。另一個是MapReduce系統(tǒng)，是一個針對大量數(shù)據(jù)的分布式計算系統(tǒng)。36BG2.3.3分布式存儲系統(tǒng)實例：ApacheHadoop圖2.13Hadoop的核心組成37BG圖2.13Hadoop的核心組成37BG1．關(guān)于ApacheHadoopHadoop的思路來自谷歌提出的MapReduce分布式計算框架。谷歌的MapReduce框架可以把一個應用程序分解為許多并行計算指令，跨越大量的計算節(jié)點運行非常巨大的數(shù)據(jù)集。而Hadoop的MapReduce則是對谷歌MapReduce的開源實現(xiàn)。另一方面其分布式文件系統(tǒng)則是谷歌的GFS的開源實現(xiàn)。Hadoop原本是ApacheNutch中的一個子項目。后來Apache將MapReduce模塊與NutchDistributedFileSystem（NDFS）單獨抽離出來成為一個頂級項目。Hadoop已經(jīng)成為目前世界上最流行的分布式計算框架之一，Apache也建立了不少與Hadoop相關(guān)的項目，如HBase、Cassandra、Avro、Hive、Mahout等項目。38BG1．關(guān)于ApacheHadoopHadoop的思路來自谷歌2．HDFS分布式文件系統(tǒng)Hadoop分布式文件系統(tǒng)（HDFS）是一個主從式的分布式文件系統(tǒng)，是GFS的一種開源實現(xiàn)。HDFS可以利用大量廉價存儲器組成分布式存儲集群，取代昂貴的集中式磁盤存儲陣列。而HDFS集群由一個NameNode和多個DataNode組成，除此之外還有用于熱備份的SecondaryNameNode，防止集群出現(xiàn)單點故障。39BG2．HDFS分布式文件系統(tǒng)Hadoop分布式文件系統(tǒng)（HDF2．HDFS分布式文件系統(tǒng)（1）NameNodeNameNode是整個集群的管理者。它并不存儲數(shù)據(jù)本身，而負責存儲文件系統(tǒng)的元數(shù)據(jù)。它負責管理文件系統(tǒng)名稱空間，并控制外部客戶端對文件系統(tǒng)的訪問。NameNode決定如何將文件內(nèi)容映射到DataNode的數(shù)據(jù)塊上。此外，實際數(shù)據(jù)傳輸并不會經(jīng)過NameNode，而會讓對應的DataNode接收實際數(shù)據(jù)，并處理分布式存儲系統(tǒng)的負載均衡問題。整個文件系統(tǒng)只有一個NameNode，因此很明顯集群可能會出現(xiàn)單點故障，這點需要利用SecondaryNameNode來解決問題。40BG2．HDFS分布式文件系統(tǒng)（1）NameNode40BG2．HDFS分布式文件系統(tǒng)（2）SecondaryNameNodeSecondaryNameNode是NameNode的備份節(jié)點，HDFS會將NameNode的數(shù)據(jù)實時備份到SecondaryNameNode上，當NameNode宕機需要重啟時，則可以利用SecondaryNameNode中的數(shù)據(jù)加快NameNode的重啟恢復速度。41BG2．HDFS分布式文件系統(tǒng)（2）SecondaryName2．HDFS分布式文件系統(tǒng)（3）DataNodeDataNode是實際的數(shù)據(jù)存儲節(jié)點，負責相應NameNode創(chuàng)建、刪除和復制塊的命令。NameNode會讀取來自DataNode的心跳信息，以此判斷DataNode是否存活。同一份數(shù)據(jù)會以多份副本存儲在不同的DataNode上，一旦某一個DataNode宕機，NameNode會立即采取手段來處理問題。42BG2．HDFS分布式文件系統(tǒng)（3）DataNode42BG2．HDFS分布式文件系統(tǒng)（4）MapReduce模型MapReduce既是Hadoop中的模塊，也是一個計算模型。用戶需要自己將算法劃分成Map和Reduce兩個階段。首先將數(shù)據(jù)劃分為小塊的數(shù)據(jù)，將數(shù)據(jù)分配到不同計算節(jié)點的Map任務中計算，然后將計算結(jié)果匯總到Reduce節(jié)點中進行合并，得出最終結(jié)果。MapReduce系統(tǒng)也是主從式的計算系統(tǒng)。在使用YARN后，每個集群有一個Resource-Manager，用于管理整個集群。集群中每個計算節(jié)點都有一個NodeManager，負責管理某個節(jié)點的容器并監(jiān)視其資源使用。每個應用程序由一個MRAppMaster進行管理。43BG2．HDFS分布式文件系統(tǒng)（4）MapReduce模型43B3．ApacheHadoop特性（1）高可靠性：ApacheHadoop可以可靠地將數(shù)據(jù)存儲到節(jié)點上。（2）高可擴展性：ApacheHadoop的存儲和計算節(jié)點可以快速擴展，并自動進行負載均衡。（3）高效性：一方面ApacheHadoop會自動在各個節(jié)點之間動態(tài)調(diào)動數(shù)據(jù)，保證每個節(jié)點存儲均衡，另一方面讀取數(shù)據(jù)時我們可以從不同節(jié)點并行讀取，提高數(shù)據(jù)讀取的速度。（4）高容錯性：ApacheHadoop會將數(shù)據(jù)冗余存儲在不同節(jié)點上，保證數(shù)據(jù)容錯性，計算任務失敗時也會自動重新分配任務。（5）低成本：ApacheHadoop是開源軟件，可以節(jié)省商業(yè)軟件的購買成本。同時，ApacheHadoop可以用廉價節(jié)點組成的集群取代昂貴的超級計算機，從而可以節(jié)省硬件成本。44BG3．ApacheHadoop特性（1）高可靠性：Apach2.4分布式系統(tǒng)的進階2.4.1分布式存儲系統(tǒng)2.4.2分布式計算系統(tǒng)2.4.3分布式資源管理系統(tǒng)45BG2.4分布式系統(tǒng)的進階2.4.1分布式存儲系統(tǒng)45B2.4.1分布式存儲系統(tǒng)分布式存儲系統(tǒng)大致可分為5個子方向：結(jié)構(gòu)化存儲、非結(jié)構(gòu)化存儲、半結(jié)構(gòu)化存儲、In-memory存儲及NewSQL。除了這5個子方向之外，分布式存儲系統(tǒng)還有一系列的理論、算法、技術(shù)作為支撐，例如Paxos、CAP理論、一致性散列、時鐘技術(shù)、2PC、3PC等。46BG2.4.1分布式存儲系統(tǒng)分布式存儲系統(tǒng)大致可分為5個子1．結(jié)構(gòu)化存儲結(jié)構(gòu)化存儲的歷史非常古老，典型的場景就是事務處理系統(tǒng)或者關(guān)系型數(shù)據(jù)庫（RDBMS）。傳統(tǒng)的結(jié)構(gòu)化存儲都是從單機做起的，例如大家耳熟能詳?shù)腗ySQL。MySQL的成長史就是互聯(lián)網(wǎng)的成長史。除了MySQL之外，PostgreSQL也是近年來勢頭非常強勁的一個RDBMS。傳統(tǒng)的結(jié)構(gòu)化存儲系統(tǒng)強調(diào)以下內(nèi)容。

結(jié)構(gòu)化的數(shù)據(jù)（例如關(guān)系表）；

強一致性（例如銀行系統(tǒng)，電商系統(tǒng)等場景）；

隨機訪問（索引、增刪查改、SQL）。47BG1．結(jié)構(gòu)化存儲結(jié)構(gòu)化存儲的歷史非常古老，典型的場景就是事務處2．非結(jié)構(gòu)化存儲與結(jié)構(gòu)化存儲不同的是，非結(jié)構(gòu)化存儲強調(diào)的是高可擴展性，典型的系統(tǒng)就是分布式文件系統(tǒng)。分布式文件系統(tǒng)也是一個很老的研究話題，例如20世紀70年代的XeroxAlto，80年代的NFS、AFS，90年代的xFS等。然而，這些早期的分布式文件系統(tǒng)只是起到了網(wǎng)絡磁盤的作用，其最大的問題就是不支持容錯和錯誤恢復。而Google在2003年SOSP會議上推出的GFS（GoogleFileSystem）則走出了里程碑的一步，其開源實現(xiàn)對應為HDFS。

48BG2．非結(jié)構(gòu)化存儲與結(jié)構(gòu)化存儲不同的是，非結(jié)構(gòu)化存儲強調(diào)的是高3．半結(jié)構(gòu)化存儲半結(jié)構(gòu)化存儲的提出是為了解決結(jié)非結(jié)構(gòu)化存儲系統(tǒng)隨機訪問性能差的問題。我們通常會聽到一些流行的名詞，例如NoSQL、Key-ValueStore，包括對象存儲等。這些都屬于半結(jié)構(gòu)化存儲研究的領(lǐng)域，其中以NoSQL的發(fā)展勢頭最為強勁。NoSQL系統(tǒng)既有分布式文件系統(tǒng)所具有的可擴展性，又有結(jié)構(gòu)化存儲系統(tǒng)的隨機訪問能力（例如隨機操作），系統(tǒng)在設計時通常選擇簡單鍵值（K-V）進行存儲，拋棄了傳統(tǒng)RDBMS里復雜SQL查詢及ACID事務。49BG3．半結(jié)構(gòu)化存儲半結(jié)構(gòu)化存儲的提出是為了解決結(jié)非結(jié)構(gòu)化存儲系4．In-memory存儲隨著業(yè)務的并發(fā)越來越高，存儲系統(tǒng)對低延遲的要求也越來越高。同時由于摩爾定律以及內(nèi)存的價格不斷下降，基于內(nèi)存的存儲系統(tǒng)也開始普及。顧名思義，In-memory存儲就是將數(shù)據(jù)存儲在內(nèi)存中，從而獲得讀寫的高性能。比較有名的系統(tǒng)包括Memcached和Redis。這些基于K-V鍵值系統(tǒng)的主要目的是為基于磁盤的存儲系統(tǒng)做緩存。還有一些偏向于內(nèi)存計算的系統(tǒng)，例如Distributedsharedmemory、RamCloud、Tachyon（Alluxio）項目等。50BG4．In-memory存儲隨著業(yè)務的并發(fā)越來越高，存儲系統(tǒng)對5．NewSQL前面介紹結(jié)構(gòu)化存儲時提到，單機RDBMS系統(tǒng)在可擴展性上面臨著巨大的挑戰(zhàn)，然而NoSQL不能很好的支持關(guān)系模型。那有沒有一種系統(tǒng)能兼?zhèn)銻DBMS的特性（例如，完整的SQL支持、ACID事務支持），又能像NoSQL系統(tǒng)那樣具有強大的可擴展能力呢？2012年Google在OSDI會議上發(fā)表的Spanner，以及2013年在SIGMOD會議上發(fā)表的F1，讓業(yè)界第一次看到了關(guān)系模型和NoSQL在超大規(guī)模數(shù)據(jù)中心上融合的可能性。不過由于這些系統(tǒng)大都過于復雜，沒有工業(yè)界大公司的支持還是很難做出來的。51BG5．NewSQL前面介紹結(jié)構(gòu)化存儲時提到，單機RDBMS系統(tǒng)2.4.2分布式計算系統(tǒng)分布式計算和并行計算一樣嗎？可以這樣認為：

傳統(tǒng)的并行計算的要求：投入更多機器，數(shù)據(jù)大小不變，計算速度更快。

分布式計算的要求：投入更多的機器，能處理更大的數(shù)據(jù)。52BG2.4.2分布式計算系統(tǒng)分布式計算和并行計算一樣嗎？521．傳統(tǒng)基于消息的系統(tǒng)這類系統(tǒng)里比較有代表性的就是MPI（MessagePassingInterface）。目前比較流行的兩個MPI實現(xiàn)是MPICH2和OpenMPI。MPI這個框架非常靈活，對程序的結(jié)構(gòu)幾乎沒有太多約束，以至于人們有時把MPI稱為一組接口API，而不是系統(tǒng)框架。MPI除了提供消息傳遞接口之外，其框架還實現(xiàn)了資源管理和分配，以及調(diào)度的功能。除此之外，MPI在高性能計算里也被廣泛使用，通?？梢院虸nfiniband這樣的高速網(wǎng)絡無縫結(jié)合。53BG1．傳統(tǒng)基于消息的系統(tǒng)這類系統(tǒng)里比較有代表性的就是MPI（M2．MapReduce家族系統(tǒng)這一類系統(tǒng)又稱作Dataflow系統(tǒng)，其中以HadoopMapReduce和Spark為代表。其實在學術(shù)界有很多類似的系統(tǒng)，例如Dryad、Twister等。這一類系統(tǒng)的特點是將計算抽象成為高層操作，例如像Map、Reduce、Filter這樣的函數(shù)式算子，將算子組合成有向無環(huán)圖DAG，然后由后端的調(diào)度引擎進行并行化調(diào)度。其中，MapReduce系統(tǒng)屬于比較簡單的DAG，只有Map和reduce兩層節(jié)點。MapReduce這樣的系統(tǒng)之所以可以擴展到超大規(guī)模的集群上運行，就是因為其完備的容錯機制。在Hadoop社區(qū)還有很多基于MapReduce框架的衍生產(chǎn)品，例如Hive（一種并行數(shù)據(jù)庫OLAP）、Pig（交互式數(shù)據(jù)操作）等。54BG2．MapReduce家族系統(tǒng)這一類系統(tǒng)又稱作Dataflo3．圖計算系統(tǒng)圖計算系統(tǒng)是分布式計算的另一個分支，這些系統(tǒng)都是把計算過程抽象成圖，然后在不同節(jié)點分布式執(zhí)行，例如PageRank這樣的任務，很適合用圖計算系統(tǒng)來表示。大數(shù)據(jù)圖是無法使用單臺機器進行處理的，如果對大圖數(shù)據(jù)進行并行處理，對于每一個頂點之間都是連通的圖來講，難以分割成若干完全獨立的子圖進行獨立的并行處理。即使可以分割，也會面臨并行機器的協(xié)同處理，以及將最后的處理結(jié)果進行合并等一系列問題。這需要圖數(shù)據(jù)處理系統(tǒng)選取合適的圖分割以及圖計算模型來迎接挑戰(zhàn)并解決問題。55BG3．圖計算系統(tǒng)圖計算系統(tǒng)是分布式計算的另一個分支，這些系統(tǒng)都4．基于狀態(tài)的系統(tǒng)這一類系統(tǒng)主要包括2010年在OSDI會議上推出的Piccolo，以及后來2012年在NIPS會議上Google推出的開源機器學習系統(tǒng)DistBelief，再到后來被機器學習領(lǐng)域廣泛應用的參數(shù)服務器（ParameterServer）架構(gòu)。56BG4．基于狀態(tài)的系統(tǒng)這一類系統(tǒng)主要包括2010年在OSDI會議5．實時流處理系統(tǒng)實時流處理系統(tǒng)是為高效實時地處理流式數(shù)據(jù)而提供服務的，更關(guān)注數(shù)據(jù)處理的實時性，能夠更加快速地為決策提供支持。流處理是由復雜事件處理（CEP）發(fā)展而來的，流處理模式包括兩種：連續(xù)查詢處理模式、可擴展數(shù)據(jù)流模式。57BG5．實時流處理系統(tǒng)實時流處理系統(tǒng)是為高效實時地處理流式數(shù)據(jù)而2.4.3分布式資源管理系統(tǒng)

從支持離線處理的MapReduce，到支持在線處理的Storm，從迭代式計算框架Spark到流式處理框架S4，各種框架誕生于不同的公司或者實驗室，它們各有所長，各自解決了某一類應用問題。而在大部分互聯(lián)網(wǎng)公司中，這幾種框架可能都會采用，例如對于搜索引擎公司，可能的技術(shù)方案如下：網(wǎng)頁建索引采用MapReduce框架，自然語言處理/數(shù)據(jù)挖掘采用Spark（網(wǎng)頁PageRank計算、聚類分類算法等），對性能要求很高的數(shù)據(jù)挖掘算法用MPI等。考慮到資源利用率、運維成本、數(shù)據(jù)共享等因素，公司一般希望將所有這些框架部署到一個公共的集群中，讓它們共享集群的資源，并對資源進行統(tǒng)一使用，這樣，便誕生了資源統(tǒng)一管理與調(diào)度平臺，典型的代表是Mesos和YARN。58BG2.4.3分布式資源管理系統(tǒng)從支持離線處理資源統(tǒng)一管理和調(diào)度平臺具有以下特點：1．支持多種計算框架2．擴展性3．容錯性4．高資源利用率5．細粒度的資源分配59BG資源統(tǒng)一管理和調(diào)度平臺具有以下特點：59BG2.5典型的分布式系統(tǒng)2.5.1網(wǎng)格系統(tǒng)2.5.2P2P系統(tǒng)2.5.3透明計算2.5.4區(qū)塊鏈系統(tǒng)60BG2.5典型的分布式系統(tǒng)2.5.1網(wǎng)格系統(tǒng)60BG2.5.1網(wǎng)格系統(tǒng)網(wǎng)格是一種能夠?qū)⒍嘟M織擁有和管理的計算機、網(wǎng)絡、數(shù)據(jù)庫和科學儀器綜合協(xié)同使用的基礎設施。網(wǎng)格應用程序大多涉及需要跨越組織界限的可安全共享的大規(guī)模數(shù)據(jù)和/或計算資源。這使網(wǎng)格應用程序的管理和部署成為一項復雜的任務。在混雜的網(wǎng)格環(huán)境中，網(wǎng)格中間件為用戶提供了無縫的計算能力和統(tǒng)一訪問資源能力。目前，世界范圍內(nèi)已經(jīng)發(fā)展有數(shù)個工具包和系統(tǒng)，其中大部分是學術(shù)研究項目的成果。61BG2.5.1網(wǎng)格系統(tǒng)網(wǎng)格是一種能夠?qū)⒍嘟M織擁有和管理的計算1.網(wǎng)格的概念Globus定義網(wǎng)格為：一種能夠整合的合作使用的由多家組織所擁有和管理的高端計算機、網(wǎng)絡、數(shù)據(jù)庫、實驗設備的基礎設施。由Gridbus提出一種基于效能的網(wǎng)格定義：網(wǎng)格是一類并行、分布系統(tǒng)，能夠在運行時動態(tài)分享、選擇、聚合地理散布的自治資源，依據(jù)它們的可用性、能力、性能、代價以及用戶對服務質(zhì)量的需求。

62BG1.網(wǎng)格的概念Globus定義網(wǎng)格為：一種能夠整合的合作使2.網(wǎng)格的組成63BG2.網(wǎng)格的組成63BG3．Globus工具包Globus是一種研究網(wǎng)格環(huán)境中互操作的中間件技術(shù)，為科學和工程上的網(wǎng)格計算應用程序提供基本的支撐環(huán)境。它定義了構(gòu)建計算網(wǎng)格的一組基本服務和功能，包括安全、資源管理、通信、目錄管理等基本服務，被許多應用網(wǎng)格項目采用。64BG3．Globus工具包Globus是一種研究網(wǎng)格環(huán)境中互操作2.5.2P2P系統(tǒng)

對等網(wǎng)絡系統(tǒng)（Peer-to-Peer），簡稱P2P系統(tǒng)，即媒體及公眾所稱的“點對點系統(tǒng)”，是一種應用在對等者（Peer）之間分配任務和工作負載的分布式應用架構(gòu)的系統(tǒng)。對等網(wǎng)絡的思想是：網(wǎng)絡的所有參與者共享他們所擁有的一部分硬件資源，包括處理器資源、存儲資源和網(wǎng)絡資源等，這些共享資源可以通過網(wǎng)絡被其他對等者直接訪問并為之提供服務和內(nèi)容。65BG2.5.2P2P系統(tǒng)對等網(wǎng)絡系統(tǒng)（Peer-P2P系統(tǒng)性質(zhì)（1）高度分散化（2）自組織性（3）多管理域66BGP2P系統(tǒng)性質(zhì)（1）高度分散化66BGP2P系統(tǒng)特點（1）部署低門檻（2）有機增長（3）對故障與攻擊的恢復力（4）資源的豐富性與多樣性67BGP2P系統(tǒng)特點（1）部署低門檻67BG對等網(wǎng)絡應用（1）共享及分發(fā)文件（2）流媒體（3）電話（4）志愿計算68BG對等網(wǎng)絡應用（1）共享及分發(fā)文件68BG2.5.3透明計算透明計算是一種用戶無須感知計算機操作系統(tǒng)、中間件、應用程序和通信網(wǎng)絡的具體所在，只需根據(jù)自己的需求，通過網(wǎng)絡從所使用的各種終端設備（包括