云計算技術(shù)——分布式計算

LOGO云 計 算 原 理 與 實 踐Principles and Practice of Cloud Computing LOGOOutlinel 2.1 分布式計算概述l 2.2 分布式計算的理論基礎(chǔ)l 2.3 分布式系統(tǒng)概述l 2.4 分布式系統(tǒng)的進階l 2.5 典型的分布式系統(tǒng) Data Science StatisticsMachine Learning Domain expertiseMathematicsData engineering LOGO2.1 分布式計算概述2.1.1 基本概念2.1.2 分布式計算的原理 LOGO2.1.1 基本概念（1）集中式計算集中式計算完全依賴于一臺大型的中心計算機的處理能力，這臺中心計算機稱為主機（Host或mainframe），與中心計算機相連的終端設(shè)備具有各不相同非常低的計算能力。實際上大多數(shù)終端完全不具有處理能力，僅作為輸入輸出設(shè)備使用。（2）分布式計算 與集中式計算相反，分布式計算中，多個通過網(wǎng)絡(luò)互聯(lián)的計算機都具有一定的計算能力，它們之間互相傳遞數(shù)據(jù)，實現(xiàn)信息共享，協(xié)作共同完成一個處理任務(wù)。 LOGO中科院的定義中國科學院對分布式計算有一個定義： 分布式計算就是在兩個或多個軟件互相共享信息，這些軟件既可以在同一臺計算機上運行，也可以在通過網(wǎng)絡(luò)連接起來的多臺計算機上運行。 LOGO分布式計算比起其他算法具有以下幾個優(yōu)點。 稀有資源可以共享； 通過分布式計算可以在多臺計算機上平衡計算負載； 可以把程序放在最適合運行它的計算機上。 LOGO2.1.2 分布式計算的原理l 分布式計算就是將計算任務(wù)分攤到大量的計算節(jié)點上，一起完成海量的計算任務(wù)。而分布式計算的原理和并行計算類似，就是將一個復(fù)雜龐大的計算任務(wù)適當劃分為一個個小任務(wù)，任務(wù)并行執(zhí)行，只不過分布式計算會將這些任務(wù)分配到不同的計算節(jié)點上，每個計算節(jié)點只需要完成自己的計算任務(wù)即可，可以有效分擔海量的計算任務(wù)。而每個計算節(jié)點也可以并行處理自身的任務(wù)，更加充分利用機器的CPU資源。最后再將每個節(jié)點的計算結(jié)果匯總，得到最后的計算結(jié)果。 LOGO分布式計算一般分為以下幾步：1設(shè)計分布式計算模型首先要規(guī)定分布式系統(tǒng)的計算模型。計算模型決定了系統(tǒng)中各個組件應(yīng)該如何運行，組件之間應(yīng)該如何進行消息通信，組件和節(jié)點應(yīng)該如何管理等。2分布式任務(wù)分配分布式算法不同于普通算法。普通算法通常是按部就班，一步接一步完成任務(wù)。而分布式計算中計算任務(wù)是分攤到各個節(jié)點上的。該算法著重解決的是能否分配任務(wù)，或如何分配任務(wù)的問題。3編寫并執(zhí)行分布式程序使用特定的分布式計算框架與計算模型，將分布式算法轉(zhuǎn)化為實現(xiàn)，并盡量保證整個集群的高效運行，難點：（1）計算任務(wù)的劃分（2）多節(jié)點之間的通信方式 LOGO2.2 分布式計算的理論基礎(chǔ)2.2.1 ACID 原則2.2.2 CAP理論2.2.3 BASE理論2.2.4 最終一致性2.2.5 一致性散列 LOGO2.2.1 ACID原則ACID是數(shù)據(jù)庫事務(wù)正常執(zhí)行的四個原則，分別指原子性、一致性、獨立性及持久性。 LOGO2.2.1 ACID原則1A（Atomicity）原子性原子性很容易理解，也就是說事務(wù)里的所有操作要么全部做完，要么都不做，事務(wù)成功的條件是事務(wù)里的所有操作都成功，只要有一個操作失敗，整個事務(wù)就失敗，需要回滾。例如銀行轉(zhuǎn)賬，從A賬戶轉(zhuǎn)100元至B賬戶，分為兩個步驟：從A賬戶取100元；存入100元至B賬戶。這兩步要么一起完成，要么一起不完成，如果只完成第一步，第二步失敗，錢會莫名其妙少了100元。 LOGO2.2.1 ACID原則2C（Consistency）一致性一致性也比較容易理解，也就是說數(shù)據(jù)庫要一直處于一致的狀態(tài)，事務(wù)的運行不會改變數(shù)據(jù)庫原本的一致性約束。例如現(xiàn)有完整性約束a + b = 10，如果一個事務(wù)改變了a，那么必須得改變b，使得事務(wù)結(jié)束后依然滿足a + b = 10，否則事務(wù)失敗。 LOGO2.2.1 ACID原則3I（Isolation）獨立性所謂的獨立性是指并發(fā)的事務(wù)之間不會互相影響，如果一個事務(wù)要訪問的數(shù)據(jù)正在被另外一個事務(wù)修改，只要另外一個事務(wù)未提交，它所訪問的數(shù)據(jù)就不受未提交事務(wù)的影響。例如交易是從A賬戶轉(zhuǎn)100元至B賬戶，在這個交易還未完成的情況下，如果此時B查詢自己的賬戶，是看不到新增加的100元的。 LOGO2.2.1 ACID原則4D（Durability）持久性持久性是指一旦事務(wù)提交后，它所做的修改將會永久保存在數(shù)據(jù)庫上，即使出現(xiàn)宕機也不會丟失。這些原則解決了數(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月，加州大學伯克利分校的埃里克布魯爾（Eric Brewer）教授在ACM PODC會議上提出CAP猜想。2年后，麻省理工學院的塞思吉爾伯符（Seth Gilbert）和南希林奇（Nancy Lynch）從理論上證明了CAP。之后，CAP理論正式成為分布式計算領(lǐng)域的公認定理。 一個分布式系統(tǒng)最多只能同時滿足一致性（Consistency）、可用性（Availability）和分區(qū)容錯性（Partition tolerance）這三項中的兩項，如圖2.1所示。 LOGO一致性一致性指“All nodes see the same data at the same time”，即更新操作成功并返回客戶端完成后，所有節(jié)點在同一時間的數(shù)據(jù)完全一致。對于一致性，可以分為從客戶端和服務(wù)端兩個不同的視角來看。 從客戶端來看，一致性主要指多并發(fā)訪問時更新過的數(shù)據(jù)如何獲取的問題。 從服務(wù)端來看，則是如何將更新復(fù)制分布到整個系統(tǒng)，以保證數(shù)據(jù)的最終一致性問題。 LOGO 可用性l 可用性是指“Reads and writes always succeed”，即服務(wù)一直可用，而且是在正常的響應(yīng)時間內(nèi)。對于一個可用性的分布式系統(tǒng)，每一個非故障的節(jié)點必須對每一個請求作出響應(yīng)。也就是該系統(tǒng)使用的任何算法必須最終終止。l 當同時要求分區(qū)容錯性時，這是一個很強的定義：即使是嚴重的網(wǎng)絡(luò)錯誤，每個請求也必須終止。好的可用性主要是指系統(tǒng)能夠很好地為用戶服務(wù)，不出現(xiàn)用戶操作失敗或者訪問超時等用戶體驗不好的情況。通常情況下可用性和分布式數(shù)據(jù)冗余、負載均衡等有著很大的關(guān)聯(lián)。 LOGO 分區(qū)容錯性 l 分區(qū)容錯性指“The system continues to operate despite arbitrary message loss or failure of part of the system”，也就是指分布式系統(tǒng)在遇到某節(jié)點或網(wǎng)絡(luò)分區(qū)故障的時候，仍然能夠?qū)ν馓峁M足一致性和可用性的服務(wù)。l 分區(qū)容錯性和擴展性緊密相關(guān)。在分布式應(yīng)用中，可能因為一些分布式的原因?qū)е孪到y(tǒng)無法正常運轉(zhuǎn)。好的分區(qū)容錯性要求應(yīng)用雖然是一個分布式系統(tǒng)，但看上去卻好像是一個可以運轉(zhuǎn)正常的整體。例如現(xiàn)在的分布式系統(tǒng)中有某一個或者幾個機器宕掉了，其他剩下的機器還能夠正常運轉(zhuǎn)滿足系統(tǒng)需求，或者是機器之間有網(wǎng)絡(luò)異常，將分布式系統(tǒng)分隔為獨立的幾個部分，各個部分還能維持分布式系統(tǒng)的運作，這樣就具有好的分區(qū)容錯性。 LOGO2CAP理論的闡述與證明 圖 2.2 CAP的 基 本 場 景 LOGO圖 2.3 分 布 式 系 統(tǒng) 正 常 運 轉(zhuǎn) 的 流 程 LOGO圖 2.4 斷 開 N1和 N2之 間 的 網(wǎng) 絡(luò) LOGO3CAP權(quán)衡通過CAP理論，知道無法同時滿足一致性、可用性和分區(qū)容錯性這三個特性，那應(yīng)該如何取舍呢？（1）CA without P：如果不要求P（不允許分區(qū)），則C（強一致性）和A（可用性）是可以保證的。但其實分區(qū)始終會存在，因此CA的系統(tǒng)更多的是允許分區(qū)后各子系統(tǒng)依然保持CA。（2）CP without A：如果不要求A（可用），相當于每個請求都需要在Server之間強一致，而P（分區(qū)）會導(dǎo)致同步時間無限延長，如此CP也是可以保證的。很多傳統(tǒng)的數(shù)據(jù)庫分布式事務(wù)都屬于這種模式。（3）AP without C：要高可用并允許分區(qū)，則需放棄一致性。一旦分區(qū)發(fā)生，節(jié)點之間可能會失去聯(lián)系，為了高可用，每個節(jié)點只能用本地數(shù)據(jù)提供服務(wù)，而這樣會導(dǎo)致全局數(shù)據(jù)的不一致性。現(xiàn)在眾多的NoSQL都屬于此類。 LOGO2.2.3 BASE理論l 丹普里切特（Dan Pritchett）在對大規(guī)模分布式系統(tǒng)的實踐總結(jié)過程中，提出了BASE理論，BASE理論是對CAP理論的延伸，核心思想是即使無法做到強一致性（Strong Consistency，CAP的一致性就是強一致性），但應(yīng)用可以采用適合的方式達到最終一致性（Eventual Consistency）。l BASE是指基本可用（Basically Available）、軟狀態(tài)（Soft State）、最終一致性（Eventual Consistency）。 LOGO1基本可用l 基本可用是指分布式系統(tǒng)在出現(xiàn)故障的時候，允許損失部分可用性，即保證核心可用。電商大促時，為了應(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ù)至少會有三個副本，允許不同節(jié)點間副本同步的延時就是軟狀態(tài)的體現(xiàn)。例如MySQL replication的異步復(fù)制就是這種體現(xiàn)。 LOGO3最終一致性l 最終一致性是指系統(tǒng)中的所有數(shù)據(jù)副本經(jīng)過一定時間后，最終能夠達到一致的狀態(tài)。l 弱一致性和強一致性相反，最終一致性是弱一致性的一種特殊情況。l BASE和ACID的區(qū)別與聯(lián)系是什么呢？ACID是傳統(tǒng)數(shù)據(jù)庫常用的設(shè)計理念，追求強一致性模型。BASE支持的是大型分布式系統(tǒng)，提出通過犧牲強一致性獲得高可用性。ACID和BASE代表了兩種截然相反的設(shè)計哲學。在分布式系統(tǒng)設(shè)計的場景中，系統(tǒng)組件對一致性要求是不同的，因此ACID和BASE又會結(jié)合使用。 LOGO2.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)的負載，以及復(fù)制技術(shù)中復(fù)本的個數(shù)。最終一致性方面最出名的系統(tǒng)可以說是DNS系統(tǒng)，當更新一個域名的IP以后，根據(jù)配置策略以及緩存控制策略的不同，最終所有的客戶都會看到最新的值。 LOGO2.2.4 最終一致性還有一些最終一致性的變體如下。 Causal consistency（因果一致性）：如果Process A通知Process B它已經(jīng)更新了數(shù)據(jù)，那么Process B的后續(xù)讀取操作則讀取A寫入的最新值，而與A沒有因果關(guān)系的C則可以最終一致性。 Read-your-writes consistency：如果Process A寫入了最新的值，那么Process A的后續(xù)操作都會讀取到最新值。但是其他用戶可能要過一會才可以看到。 Session consistency：此種一致性要求客戶端和存儲系統(tǒng)交互的整個會話階段保證Read-your- writes consistency。Hibernate的session提供的一致性保證就屬于此種一致性。 Monotonic read consistency：此種一致性要求如果Process A已經(jīng)讀取了對象的某個值，那么后續(xù)操作將不會讀取到更早的值。 Monotonic write consistency：此種一致性保證系統(tǒng)會序列化執(zhí)行一個Process中的所有寫操作。 LOGO2.2.5 一致性散列1基本概念一致性散列算法（Consistent Hashing）最早在論文Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web中被提出。簡單來說，一致性散列將整個散列值空間組織成一個虛擬的圓環(huán)。假設(shè)某散列函數(shù)H的值空間為02 321（即散列值是一個32位無符號整形），整個散列空間環(huán)如圖所示。 LOGO2容錯性和擴展性（1）容錯性現(xiàn)假設(shè)Node C不幸宕機，可以看到此時對象A、B、D不會受到影響，只有C對象被重定位到Node D。一般來說，在一致性散列算法中，如果一臺服務(wù)器不可用，則受影響的數(shù)據(jù)僅僅是此服務(wù)器到其環(huán)空間中前一臺服務(wù)器（即沿著逆時針方向行走遇到的第一臺服務(wù)器）之間的數(shù)據(jù)，其他不會受到影響，如圖所示。 LOGO2容錯性和擴展性（2）擴展性如果在系統(tǒng)中增加一臺服務(wù)器Node X，如圖所示。此時對象A、B、D不受影響，只有對象C需要重定位到新的Node X。一般來說，在一致性散列算法中，如果增加一臺服務(wù)器，則受影響的數(shù)據(jù)僅僅是新服務(wù)器到其環(huán)空間中前一臺服務(wù)器（即沿著逆時針方向行走遇到的第一臺服務(wù)器）之間數(shù)據(jù)，其他數(shù)據(jù)也不會受到影響。 LOGO2容錯性和擴展性（3）虛擬節(jié)點一致性散列算法在服務(wù)節(jié)點太少時，容易因為節(jié)點分布不均勻而造成數(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)實例：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ù)量眾多的、低成本和高性價比的普通PC服務(wù)器通過網(wǎng)絡(luò)連接而成?；ヂ?lián)網(wǎng)的業(yè)務(wù)發(fā)展很快，而且注重成本，這就使得存儲系統(tǒng)不能依靠傳統(tǒng)的縱向擴展的方式，即先買小型機，不夠時再買中型機，甚至大型機?；ヂ?lián)網(wǎng)后端的分布式系統(tǒng)要求支持橫向擴展，即通過增加普通PC服務(wù)器來提高系統(tǒng)的整體處理能力。普通PC服務(wù)器性價比高，故障率也高，需要在軟件層面實現(xiàn)自動容錯，保證數(shù)據(jù)的一致性。另外，隨著服務(wù)器的不斷加入，需要能夠在軟件層面實現(xiàn)自動負載均衡，使系統(tǒng)的處理能力得到線性擴展。 LOGO2.3.2 分布式系統(tǒng)的特性l 喬治庫魯里斯（George Coulouris）是分布式系統(tǒng)：概念與設(shè)計（Distributed Systems:Concepts and Design）一書的作者，曾是劍橋大學的高級研究員。他曾經(jīng)對分布式系統(tǒng)下了一個簡單的定義：你會知道系統(tǒng)當中的某臺計算機崩潰或停止運行了，但是你的軟件卻永遠不會。這句話雖然簡單，但是卻道出了分布式系統(tǒng)的關(guān)鍵特性。分布式系統(tǒng)的特性包括容錯性、高可擴展性、開放性、并發(fā)處理能力和透明性。 LOGO2.3.3 分布式存儲系統(tǒng)實例：Apache Hadoopl Hadoop是由Apache基金會開發(fā)的分布式存儲與計算框架。用戶不需要了解底層的分布式計算原理就可以輕松開發(fā)出分布式計算程序，可以充分利用集群中閑置的計算資源，將集群的真正威力調(diào)動起來。l Hadoop由兩個重要模塊組成。一個是Hadoop分布式文件系統(tǒng)（Hadoop Distributed File System），顧名思義，就是一個分布式的文件系統(tǒng)，可以將文件數(shù)據(jù)分布式地存儲在集群中的不同節(jié)點上。另一個是MapReduce系統(tǒng)，是一個針對大量數(shù)據(jù)的分布式計算系統(tǒng)。 LOGO圖2.13 Hadoop的核心組成 LOGO1關(guān)于Apache Hadoopl Hadoop的思路來自谷歌提出的MapReduce分布式計算框架。谷歌的MapReduce框架可以把一個應(yīng)用程序分解為許多并行計算指令，跨越大量的計算節(jié)點運行非常巨大的數(shù)據(jù)集。而Hadoop的MapReduce則是對谷歌MapReduce的開源實現(xiàn)。另一方面其分布式文件系統(tǒng)則是谷歌的GFS的開源實現(xiàn)。l Hadoop原本是Apache Nutch中的一個子項目。后來Apache將MapReduce模塊與Nutch Distributed File System（NDFS）單獨抽離出來成為一個頂級項目。l Hadoop已經(jīng)成為目前世界上最流行的分布式計算框架之一，Apache也建立了不少與Hadoop相關(guān)的項目，如HBase、Cassandra、Avro、Hive、Mahout等項目。 LOGO2HDFS分布式文件系統(tǒng)l Hadoop分布式文件系統(tǒng)（HDFS）是一個主從式的分布式文件系統(tǒng)，是GFS的一種開源實現(xiàn)。HDFS可以利用大量廉價存儲器組成分布式存儲集群，取代昂貴的集中式磁盤存儲陣列。而HDFS集群由一個NameNode和多個DataNode組成，除此之外還有用于熱備份的Secondary NameNode，防止集群出現(xiàn)單點故障。 LOGO2HDFS分布式文件系統(tǒng)（1）NameNodel NameNode是整個集群的管理者。它并不存儲數(shù)據(jù)本身，而負責存儲文件系統(tǒng)的元數(shù)據(jù)。它負責管理文件系統(tǒng)名稱空間，并控制外部客戶端對文件系統(tǒng)的訪問。l NameNode決定如何將文件內(nèi)容映射到DataNode的數(shù)據(jù)塊上。此外，實際數(shù)據(jù)傳輸并不會經(jīng)過NameNode，而會讓對應(yīng)的DataNode接收實際數(shù)據(jù)，并處理分布式存儲系統(tǒng)的負載均衡問題。l 整個文件系統(tǒng)只有一個NameNode，因此很明顯集群可能會出現(xiàn)單點故障，這點需要利用Secondary NameNode來解決問題。 LOGO2HDFS分布式文件系統(tǒng)（2）Secondary NameNodel Secondary NameNode是NameNode的備份節(jié)點，HDFS會將NameNode的數(shù)據(jù)實時備份到Secondary NameNode上，當NameNode宕機需要重啟時，則可以利用Secondary NameNode中的數(shù)據(jù)加快NameNode的重啟恢復(fù)速度。 LOGO2HDFS分布式文件系統(tǒng)（3）DataNodel DataNode是實際的數(shù)據(jù)存儲節(jié)點，負責相應(yīng)NameNode創(chuàng)建、刪除和復(fù)制塊的命令。NameNode會讀取來自DataNode的心跳信息，以此判斷DataNode是否存活。同一份數(shù)據(jù)會以多份副本存儲在不同的DataNode上，一旦某一個DataNode宕機，NameNode會立即采取手段來處理問題。 LOGO2HDFS分布式文件系統(tǒng)（4）MapReduce模型l MapReduce既是Hadoop中的模塊，也是一個計算模型。用戶需要自己將算法劃分成Map和Reduce兩個階段。首先將數(shù)據(jù)劃分為小塊的數(shù)據(jù)，將數(shù)據(jù)分配到不同計算節(jié)點的Map任務(wù)中計算，然后將計算結(jié)果匯總到Reduce節(jié)點中進行合并，得出最終結(jié)果。l MapReduce系統(tǒng)也是主從式的計算系統(tǒng)。在使用YARN后，每個集群有一個Resource-Manager，用于管理整個集群。集群中每個計算節(jié)點都有一個NodeManager，負責管理某個節(jié)點的容器并監(jiān)視其資源使用。每個應(yīng)用程序由一個MRAppMaster進行管理。 LOGO3Apache Hadoop特性（1）高可靠性：Apache Hadoop可以可靠地將數(shù)據(jù)存儲到節(jié)點上。（2）高可擴展性：Apache Hadoop的存儲和計算節(jié)點可以快速擴展，并自動進行負載均衡。（3）高效性：一方面Apache Hadoop會自動在各個節(jié)點之間動態(tài)調(diào)動數(shù)據(jù)，保證每個節(jié)點存儲均衡，另一方面讀取數(shù)據(jù)時我們可以從不同節(jié)點并行讀取，提高數(shù)據(jù)讀取的速度。（4）高容錯性：Apache Hadoop會將數(shù)據(jù)冗余存儲在不同節(jié)點上，保證數(shù)據(jù)容錯性，計算任務(wù)失敗時也會自動重新分配任務(wù)。（5）低成本：Apache Hadoop是開源軟件，可以節(jié)省商業(yè)軟件的購買成本。同時，Apache Hadoop可以用廉價節(jié)點組成的集群取代昂貴的超級計算機，從而可以節(jié)省硬件成本。 LOGO2.4 分布式系統(tǒng)的進階2.4.1 分布式存儲系統(tǒng)2.4.2 分布式計算系統(tǒng)2.4.3 分布式資源管理系統(tǒng) LOGO2.4.1 分布式存儲系統(tǒng)l 分布式存儲系統(tǒng)大致可分為5個子方向：結(jié)構(gòu)化存儲、非結(jié)構(gòu)化存儲、半結(jié)構(gòu)化存儲、In-memory 存儲及NewSQL。l 除了這5個子方向之外，分布式存儲系統(tǒng)還有一系列的理論、算法、技術(shù)作為支撐，例如 Paxos、CAP理論、一致性散列、時鐘技術(shù)、2PC、3PC等。 LOGO1結(jié)構(gòu)化存儲結(jié)構(gòu)化存儲的歷史非常古老，典型的場景就是事務(wù)處理系統(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）。 LOGO2非結(jié)構(gòu)化存儲與結(jié)構(gòu)化存儲不同的是，非結(jié)構(gòu)化存儲強調(diào)的是高可擴展性，典型的系統(tǒng)就是分布式文件系統(tǒng)。分布式文件系統(tǒng)也是一個很老的研究話題，例如20世紀70年代的Xerox Alto，80年代的NFS、AFS，90年代的xFS等。然而，這些早期的分布式文件系統(tǒng)只是起到了網(wǎng)絡(luò)磁盤的作用，其最大的問題就是不支持容錯和錯誤恢復(fù)。而Google在2003年SOSP會議上推出的GFS（Google File System）則走出了里程碑的一步，其開源實現(xiàn)對應(yīng)為HDFS。 LOGO3半結(jié)構(gòu)化存儲l 半結(jié)構(gòu)化存儲的提出是為了解決結(jié)非結(jié)構(gòu)化存儲系統(tǒng)隨機訪問性能差的問題。我們通常會聽到一些流行的名詞，例如NoSQL、Key-Value Store，包括對象存儲等。這些都屬于半結(jié)構(gòu)化存儲研究的領(lǐng)域，其中以NoSQL的發(fā)展勢頭最為強勁。NoSQL系統(tǒng)既有分布式文件系統(tǒng)所具有的可擴展性，又有結(jié)構(gòu)化存儲系統(tǒng)的隨機訪問能力（例如隨機操作），系統(tǒng)在設(shè)計時通常選擇簡單鍵值（K-V）進行存儲，拋棄了傳統(tǒng)RDBMS里復(fù)雜SQL查詢及ACID事務(wù)。 LOGO4In-memory存儲l 隨著業(yè)務(wù)的并發(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)，例如Distributed shared memory、RamCloud、Tachyon（Alluxio）項目等。 LOGO5NewSQLl 前面介紹結(jié)構(gòu)化存儲時提到，單機RDBMS系統(tǒng)在可擴展性上面臨著巨大的挑戰(zhàn)，然而NoSQL不能很好的支持關(guān)系模型。那有沒有一種系統(tǒng)能兼?zhèn)銻DBMS的特性（例如，完整的SQL支持、ACID事務(wù)支持），又能像NoSQL系統(tǒng)那樣具有強大的可擴展能力呢？2012年Google在OSDI會議上發(fā)表的Spanner，以及2013年在SIGMOD會議上發(fā)表的F1，讓業(yè)界第一次看到了關(guān)系模型和NoSQL在超大規(guī)模數(shù)據(jù)中心上融合的可能性。不過由于這些系統(tǒng)大都過于復(fù)雜，沒有工業(yè)界大公司的支持還是很難做出來的。 LOGO2.4.2 分布式計算系統(tǒng)分布式計算和并行計算一樣嗎？可以這樣認為： 傳統(tǒng)的并行計算的要求：投入更多機器，數(shù)據(jù)大小不變，計算速度更快。 分布式計算的要求：投入更多的機器，能處理更大的數(shù)據(jù)。 LOGO1傳統(tǒng)基于消息的系統(tǒng)l 這類系統(tǒng)里比較有代表性的就是MPI（Message Passing Interface）。目前比較流行的兩個MPI實現(xiàn)是MPICH2和OpenMPI。MPI這個框架非常靈活，對程序的結(jié)構(gòu)幾乎沒有太多約束，以至于人們有時把MPI稱為一組接口API，而不是系統(tǒng)框架。MPI除了提供消息傳遞接口之外，其框架還實現(xiàn)了資源管理和分配，以及調(diào)度的功能。除此之外，MPI在高性能計算里也被廣泛使用，通?？梢院?Infiniband 這樣的高速網(wǎng)絡(luò)無縫結(jié)合。 LOGO2MapReduce家族系統(tǒng)l 這一類系統(tǒng)又稱作Dataflow系統(tǒng)，其中以Hadoop MapReduce和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ù)操作）等。 LOGO3圖計算系統(tǒng)l 圖計算系統(tǒng)是分布式計算的另一個分支，這些系統(tǒng)都是把計算過程抽象成圖，然后在不同節(jié)點分布式執(zhí)行，例如PageRank這樣的任務(wù)，很適合用圖計算系統(tǒng)來表示。l 大數(shù)據(jù)圖是無法使用單臺機器進行處理的，如果對大圖數(shù)據(jù)進行并行處理，對于每一個頂點之間都是連通的圖來講，難以分割成若干完全獨立的子圖進行獨立的并行處理。即使可以分割，也會面臨并行機器的協(xié)同處理，以及將最后的處理結(jié)果進行合并等一系列問題。這需要圖數(shù)據(jù)處理系統(tǒng)選取合適的圖分割以及圖計算模型來迎接挑戰(zhàn)并解決問題。 LOGO4基于狀態(tài)的系統(tǒng)l 這一類系統(tǒng)主要包括2010年在OSDI會議上推出的Piccolo，以及后來2012年在NIPS會議上 Google推出的開源機器學習系統(tǒng)DistBelief，再到后來被機器學習領(lǐng)域廣泛應(yīng)用的參數(shù)服務(wù)器（Parameter Server）架構(gòu)。 LOGO5實時流處理系統(tǒng)l 實時流處理系統(tǒng)是為高效實時地處理流式數(shù)據(jù)而提供服務(wù)的，更關(guān)注數(shù)據(jù)處理的實時性，能夠更加快速地為決策提供支持。流處理是由復(fù)雜事件處理（CEP）發(fā)展而來的，流處理模式包括兩種：連續(xù)查詢處理模式、可擴展數(shù)據(jù)流模式。 LOGO2.4.3 分布式資源管理系統(tǒng) 從支持離線處理的MapReduce，到支持在線處理的Storm，從迭代式計算框架Spark到流式處理框架S4，各種框架誕生于不同的公司或者實驗室，它們各有所長，各自解決了某一類應(yīng)用問題。而在大部分互聯(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。 LOGO資源統(tǒng)一管理和調(diào)度平臺具有以下特點：1支持多種計算框架2擴展性3容錯性4高資源利用率5細粒度的資源分配 LOGO2.5 典型的分布式系統(tǒng)2.5.1 網(wǎng)格系統(tǒng)2.5.2 P2P系統(tǒng)2.5.3 透明計算2.5.4 區(qū)塊鏈系統(tǒng) LOGO2.5.1 網(wǎng)格系統(tǒng)l 網(wǎng)格是一種能夠?qū)⒍嘟M織擁有和管理的計算機、網(wǎng)絡(luò)、數(shù)據(jù)庫和科學儀器綜合協(xié)同使用的基礎(chǔ)設(shè)施。網(wǎng)格應(yīng)用程序大多涉及需要跨越組織界限的可安全共享的大規(guī)模數(shù)據(jù)和/或計算資源。這使網(wǎng)格應(yīng)用程序的管理和部署成為一項復(fù)雜的任務(wù)。在混雜的網(wǎng)格環(huán)境中，網(wǎng)格中間件為用戶提供了無縫的計算能力和統(tǒng)一訪問資源能力。目前，世界范圍內(nèi)已經(jīng)發(fā)展有數(shù)個工具包和系統(tǒng)，其中大部分是學術(shù)研究項目的成果。 LOGO1. 網(wǎng)格的概念l Globus定義網(wǎng)格為：一種能夠整合的合作使用的由多家組織所擁有和管理的高端計算機、網(wǎng)絡(luò)、數(shù)據(jù)庫、實驗設(shè)備的基礎(chǔ)設(shè)施。l 由Gridbus提出一種基于效能的網(wǎng)格定義：網(wǎng)格是一類并行、分布系統(tǒng)，能夠在運行時動態(tài)分享、選擇、聚合地理散布的自治資源，依據(jù)它們的可用性、能力、性能、代價以及用戶對服務(wù)質(zhì)量的需求。 LOGO2. 網(wǎng)格的組成 LOGO3Globus工具包l Globus是一種研究網(wǎng)格環(huán)境中互操作的中間件技術(shù)，為科學和工程上的網(wǎng)格計算應(yīng)用程序提供基本的支撐環(huán)境。它定義了構(gòu)建計算網(wǎng)格的一組基本服務(wù)和功能，包括安全、資源管理、通信、目錄管理等基本服務(wù)，被許多應(yīng)用網(wǎng)格項目采用。 LOGO2.5.2 P2P系統(tǒng) 對等網(wǎng)絡(luò)系統(tǒng)（Peer-to-Peer），簡稱P2P系統(tǒng)，即媒體及公眾所稱的“點對點系統(tǒng)”，是一種應(yīng)用在對等者（Peer）之間分配任務(wù)和工作負載的分布式應(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）自組織性（3）多管理域 LOGOP2P系統(tǒng)特點（1）部署低門檻（2）有機增長（3）對故障與攻擊的恢復(fù)力（4）資源的豐富性與多樣性 LOGO對等網(wǎng)絡(luò)應(yīng)用（1）共享及分發(fā)文件（2）流媒體（3）電話（4）志愿計算 LOGO2.5.3 透明計算透 明 計 算 是 一 種 用 戶 無 須 感 知 計 算 機 操 作 系統(tǒng) 、 中 間 件 、 應(yīng) 用 程 序 和 通 信 網(wǎng) 絡(luò) 的 具 體 所在 ， 只 需 根 據(jù) 自 己 的 需 求 ， 通 過 網(wǎng) 絡(luò) 從 所 使用 的 各 種 終 端 設(shè) 備 （ 包 括 固 定 、 移 動 及 家 庭中 的 各 類 終 端 設(shè) 備 ） 中 選 擇 并 使 用 相 應(yīng) 服 務(wù)（ 例 如 計 算 、 電 話 、 電 視 、 上 網(wǎng) 和 娛 樂 等 ）的 計 算 模 式 。 LOGO圖2.20 透明計算模式 LOGO透明計算核心技術(shù)（1）透明云架構(gòu) LOGO透明計算核心技術(shù)（2）元操作系統(tǒng)（Meta OS）（3）客戶端實現(xiàn) 圖 2.23 HTML5與 傳 統(tǒng) APP的 對 比 LOGO2.5.4 區(qū)塊鏈系統(tǒng)區(qū) 塊 鏈 （ Blockchain） 是 一 種 去 中 心 化 、 不 可 篡 改 、可 追 溯 、 多 方 共 同 維 護 的 分 布 式 數(shù) 據(jù) 庫 系 統(tǒng) ， 能 夠?qū)?傳 統(tǒng) 單 方 維 護 的 僅 涉 及 自 己 業(yè) 務(wù) 的 多 個 孤 立 數(shù) 據(jù)庫 整 合 在 一 起 ， 分 布 式 地 存 儲 在 多 方 共 同 維 護 的 多個 節(jié) 點 ， 任 何 一 方 都 無 法 完 全 控 制 這 些 數(shù) 據(jù) ， 只 能按 照 嚴 格 的 規(guī) 則 和 共 識 進 行 更 新 ， 從 而 實 現(xiàn) 了 可 信的 多 方 間 的 信 息 共 享 和 監(jiān) 督 ， 避 免 了 煩 瑣 的 人 工 對賬 ， 提 高 了 業(yè) 務(wù) 處 理 效 率 ， 降 低 了 交 易 成 本 。 LOGO區(qū)塊鏈的核心特征 塊鏈結(jié)構(gòu)：每一塊有時間戳，每一塊都含有前面一塊的散列加密信息，對每個交易進行驗證。 多獨立拷貝存儲：區(qū)塊鏈系統(tǒng)的每個節(jié)點都存儲同樣信息。 拜占庭容錯：容忍少于1/3 節(jié)點惡意作弊或被黑客攻擊，系統(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ù)保護的密碼機（5）互聯(lián)網(wǎng)新技術(shù) LOGO 分 布 式 計 算 概 述 分 布 式 計 算 的 理 論 基 礎(chǔ) 分 布 式 系 統(tǒng) 概 述 分 布 式 系 統(tǒng) 的 進 階 典 型 的 分 布 式 系 統(tǒng)小 結(jié) LOGO課內(nèi)復(fù)習1分布式計算的定義和特征是什么？2什么是ACID原則？3什么是CAP理論？4什么是BASE理論？5如何理解最終一致性？6分布式存儲與分布式計算的區(qū)別與聯(lián)系是什么？ LOGO課外思考1在日常生活中，為什么我們所接觸到的分布式系統(tǒng)越來越多了？2CAP定理中的幾個關(guān)鍵因素為什么不能同時保證？不同的組合有什么樣的應(yīng)用場景？3通過了解區(qū)塊鏈的背景，說說你所理解的區(qū)塊鏈作為一種分布式系統(tǒng)背后的全新理念。 LOGO動手實踐1Globus是一個開放源碼的網(wǎng)格的基礎(chǔ)平臺，Globus Toolkit工具包是一個構(gòu)筑網(wǎng)格計算環(huán)境的中間件，提供基本的資源定位、管理、通信和安全等服務(wù)。該計算工具包是模塊化的，允許用戶按自己的需要定制環(huán)境。利用這套工具可以建立計算網(wǎng)格，并可以進行網(wǎng)格應(yīng)用的開發(fā)。任務(wù)：通過Globus Toolkit的官方網(wǎng)站下載并安裝使用Globus Toolkit。 LOGO動手實踐2HTCondor是一個專門用于計算密集型作業(yè)的負載管理系統(tǒng)，它為用戶提供了作業(yè)排隊機制、調(diào)度策略、優(yōu)先計劃、資源監(jiān)測和資源管理，誕生于美國威斯康星大學麥迪遜分校。任務(wù)：通過HTCondor的官方網(wǎng)站下載并安裝使用HTCondor，了解它是如何實現(xiàn)大吞吐量計算過程的。