摘? 要：云計(jì)算是一種基于互聯(lián)網(wǎng)的計(jì)算方式。它通過互聯(lián)網(wǎng)上異構(gòu)、自治的服務(wù)為個(gè)人和企業(yè)用戶提供按需即取的計(jì)算。云計(jì)算平臺(tái)，是指平臺(tái)通過一套軟件系統(tǒng)把分布式部署的資源集中調(diào)度使用。本文針對(duì)亞馬遜的Dynamo，以及谷歌的GFS、BigTable和MapReduce，這四個(gè)典型的云計(jì)算平臺(tái)進(jìn)行項(xiàng)目研究，對(duì)其設(shè)計(jì)思想和實(shí)現(xiàn)的關(guān)鍵算法原理進(jìn)行了闡述。并基于此，提出了對(duì)未來云計(jì)算技術(shù)和云平臺(tái)的進(jìn)一步發(fā)展的展望。

關(guān)鍵詞：云計(jì)算;分布式算法;云平臺(tái)

中圖分類號(hào)：TP393.09;TP301.6? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2019）08-0096-03

Abstract：Cloud computing is an internet-based computing method. It provides on-demand computing for individual and enterprise users through heterogeneous and autonomous services on the internet. Cloud computing platform refers to the centralized scheduling of distributed deployed resources through a software system. This paper focuses on the project research of Amazon’s Dynamo，Google’s GFS，BigTable and MapReduce，which are four typical cloud computing platforms，and elaborates on their design ideas and key algorithmic principles. Based on this，the future development prospects of cloud computing technology and cloud platform are put forward.

Keywords：cloud computing;distributed algorithms;cloud platform

0? 引? 言

云計(jì)算是一種基于互聯(lián)網(wǎng)的計(jì)算方式。它可以為個(gè)人和企業(yè)用戶提供按需即取的計(jì)算，并天然帶有異構(gòu)、自治的性質(zhì)。它的特點(diǎn)有：超大規(guī)模、虛擬化、按需服務(wù)、可伸縮性、服務(wù)可度量。它對(duì)整個(gè)IT產(chǎn)業(yè)帶來非常深遠(yuǎn)的影響，其中包括軟件開發(fā)商、服務(wù)器供應(yīng)商和云終端供應(yīng)商這三個(gè)云計(jì)算建設(shè)者和作為云計(jì)算運(yùn)維者的云供應(yīng)商。

當(dāng)前世界的云計(jì)算規(guī)模在不斷擴(kuò)大，在未來幾年，全球云計(jì)算服務(wù)市場(chǎng)仍有較大概率保持在15%左右的增長(zhǎng)率平穩(wěn)增長(zhǎng)。中國(guó)互聯(lián)網(wǎng)公司三巨頭（BAT）、華為等中國(guó)企業(yè)將持續(xù)發(fā)力云的基礎(chǔ)設(shè)施建設(shè)和相關(guān)技術(shù)的迭代更新。根據(jù)公開資料顯示的趨勢(shì)來看，預(yù)計(jì)到2020年，云服務(wù)市場(chǎng)規(guī)模將達(dá)到4114億美元。

盡管如此，這種方興未艾的計(jì)算模型在技術(shù)上仍然需要面對(duì)諸多挑戰(zhàn)。如：用戶隱私安全、云服務(wù)標(biāo)準(zhǔn)缺失，等等。在云計(jì)算充滿機(jī)遇和挑戰(zhàn)的今天，我們有必要去探討和回顧一些較為成功的、影響力較大的幾個(gè)云計(jì)算平臺(tái)的設(shè)計(jì)模式，并從中汲取養(yǎng)分。

1? 亞馬遜的Dynamo及其算法原理

Dynamo是Amazon的Key-Value模式的存儲(chǔ)平臺(tái)。它是一個(gè)具有鍵值結(jié)構(gòu)的分布式存儲(chǔ)系統(tǒng)，至今已有諸多應(yīng)用。Dynamo使用了分布式哈希表（DHT），這可以讓數(shù)據(jù)在環(huán)中均勻存儲(chǔ)，并保證各節(jié)點(diǎn)相互獨(dú)立，不需要主節(jié)點(diǎn)進(jìn)行統(tǒng)一的調(diào)控，從而令發(fā)生單節(jié)點(diǎn)故障的風(fēng)險(xiǎn)大大地降低。

Amazon大量的用戶服務(wù)數(shù)據(jù)被存儲(chǔ)在Dynamo中。可以說它為Amazon的電子商務(wù)平臺(tái)及其云計(jì)算服務(wù)提供了最基礎(chǔ)的支持。

Dynamo中應(yīng)用了諸多算法去解決數(shù)據(jù)存儲(chǔ)和處理的各種難題，這些算法很多都是分布式算法中的經(jīng)典。下面是其使用的最主要的一些算法，以及對(duì)應(yīng)解決的問題。

（1）改進(jìn)的一致性哈希算法=>數(shù)據(jù)均衡分布。

（2）參數(shù)可調(diào)的弱quorum機(jī)制=>數(shù)據(jù)備份。

（3）向量時(shí)鐘=>數(shù)據(jù)沖突處理。

（4）Gossip=>成員資格及錯(cuò)誤檢測(cè)。

（5）Hinted Handoff（數(shù)據(jù)回傳機(jī)制）=>臨時(shí)故障處理。

（6）Merkle哈希樹=>永久故障處理。

本文對(duì)其中的一些算法和模型的主要思想進(jìn)行介紹，這里將忽略算法細(xì)節(jié)。

1.1? 使用改進(jìn)的一致性哈希算法解決Dynamo中的數(shù)據(jù)均衡分布問題

哈希函數(shù)經(jīng)常用于常數(shù)時(shí)間的數(shù)據(jù)查找。通常意義上看，哈希查找有以下兩個(gè)主要的步驟。

（1）使用哈希函數(shù)將想要查找的鍵映射成數(shù)組或物理存儲(chǔ)地址的索引。這么做的意義在于，我們?cè)诓檎夷硞€(gè)鍵時(shí)，可以使用同一個(gè)哈希函數(shù)將其迅速映射到它的存儲(chǔ)位置，從而實(shí)現(xiàn)常數(shù)時(shí)間的查找。

（2）處理哈希碰撞沖突。由于第一個(gè)步驟中的映射方式可能導(dǎo)致不同數(shù)據(jù)映射到同一個(gè)地址，我們需要處理這種“哈希碰撞沖突”。實(shí)際應(yīng)用中常見的方法有拉鏈法、線性探測(cè)法等等。

哈希函數(shù)的確可以做到數(shù)據(jù)的快速查找，但這對(duì)于一個(gè)合格的云平臺(tái)卻遠(yuǎn)遠(yuǎn)不夠。在新增存儲(chǔ)機(jī)器的情況下，由于物理地址索引范圍的變化，哈希函數(shù)必須重新調(diào)整，這使得我們必須迅速將所有數(shù)據(jù)按照新的哈希函數(shù)重新計(jì)算并存儲(chǔ)。

為了解決這個(gè)問題，一致性哈希算法引入了環(huán)的概念。我們將存儲(chǔ)數(shù)據(jù)的機(jī)器抽象為一個(gè)個(gè)node，切分成的數(shù)據(jù)塊稱為block。一致性哈希算法中的哈希值的范圍是一定的，將這個(gè)范圍抽象成一個(gè)環(huán)，每個(gè)node并不是對(duì)應(yīng)一個(gè)確定的哈希值，而是一個(gè)哈希值范圍。當(dāng)前node的哈希值范圍就是它的哈希值和在環(huán)上的前一個(gè)節(jié)點(diǎn)的哈希值。只要block的哈希值落在了這個(gè)范圍內(nèi)，它就將被存儲(chǔ)在這個(gè)node上。換句話說，block要存儲(chǔ)在它的哈希值順時(shí)針繞環(huán)遇見的第一個(gè)node上。一致性哈希算法在減少或者添加node時(shí)，可以盡可能地保證數(shù)據(jù)的較少遷移。數(shù)據(jù)只有一個(gè)備份的時(shí)候是危險(xiǎn)的。因此，Dynamo對(duì)一致性哈希算法的進(jìn)一步改進(jìn)是：它放在環(huán)上作為一個(gè)node的是多臺(tái)機(jī)器，這一組機(jī)器通過Dynamo獨(dú)特的數(shù)據(jù)同步機(jī)制來保證數(shù)據(jù)的一致性。這就通過增加數(shù)據(jù)的備份更大地保證了數(shù)據(jù)安全。我們?cè)谙旅娴奈淖种薪榻B屬于一個(gè)node的機(jī)器之間所使用的數(shù)據(jù)同步機(jī)制。

1.2? （N，R，W）模型解決Dynamo中的數(shù)據(jù)備份及一致性問題

Dynamo使用的方法是（N，R，W）模型。這個(gè)模型解決了同一個(gè)node內(nèi)的不同機(jī)器上數(shù)據(jù)的不一致可能造成的讀寫問題。它讓用戶確定云平臺(tái)以何種方式去存儲(chǔ)、讀和寫數(shù)據(jù)。用戶可以根據(jù)自己的需求，通過設(shè)定參數(shù)，在較高的讀寫性能與數(shù)據(jù)的高一致性之間進(jìn)行取舍。

（N，R，W）模型需要客戶端設(shè)定三個(gè)參數(shù)，即N、R、W。云平臺(tái)將按照這三個(gè)參數(shù)來調(diào)整數(shù)據(jù)的讀寫操作。N表示數(shù)據(jù)復(fù)制的次數(shù)，當(dāng)N越大時(shí)，用戶的數(shù)據(jù)備份就越多;R表示讀數(shù)據(jù)時(shí)候所需要參與的最小節(jié)點(diǎn)數(shù)，當(dāng)R越大時(shí)，用戶讀取數(shù)據(jù)時(shí)需要參與的機(jī)器數(shù)就越多;W表示數(shù)據(jù)寫成功所需要的最小分區(qū)數(shù)，當(dāng)W越大時(shí)，用戶寫入數(shù)據(jù)時(shí)需要參與的機(jī)器數(shù)越多。因此，當(dāng)我們將這三個(gè)參數(shù)都設(shè)置成很大的數(shù)字時(shí)，顯然，系統(tǒng)的可用性就會(huì)減弱，但數(shù)據(jù)一致性會(huì)增強(qiáng);當(dāng)三者都很小時(shí)，就不能保證數(shù)據(jù)的安全備份。一般情況下，需要讓“R+W>N”，這是為了保證用戶讀取的數(shù)據(jù)中至少有一份是正確的。

Dynamo使用（N，R，W）模型靈活地調(diào)整用戶對(duì)數(shù)據(jù)的可用性與一致性的要求。而Dynamo的擴(kuò)展性是其數(shù)據(jù)分區(qū)數(shù)所決定的，它通常是已經(jīng)被設(shè)定好的。

1.3? 使用Merkle Tree解決Dynamo中的數(shù)據(jù)恢復(fù)問題

以上兩個(gè)算法基本解決了Dynamo平臺(tái)的數(shù)據(jù)均衡存儲(chǔ)和數(shù)據(jù)安全備份的問題。盡管（N，R，W）模型可以保證在正確設(shè)置了參數(shù)的情況下，我們拿到的數(shù)據(jù)至少有一份是正確的，但這并不意味著我們對(duì)錯(cuò)誤的數(shù)據(jù)不進(jìn)行修正和恢復(fù)。因此，我們現(xiàn)在考慮的是假如發(fā)生了兩臺(tái)機(jī)器的數(shù)據(jù)不一致，Dynamo如何根據(jù)其中存儲(chǔ)正確數(shù)據(jù)的一臺(tái)機(jī)器來對(duì)另一臺(tái)機(jī)器中的數(shù)據(jù)進(jìn)行恢復(fù)。

如果在數(shù)據(jù)錯(cuò)誤發(fā)生時(shí)針對(duì)所有數(shù)據(jù)進(jìn)行恢復(fù)，因?yàn)樾枰乱慌_(tái)機(jī)器上的所有數(shù)據(jù)，必然導(dǎo)致大量且慢速的數(shù)據(jù)操作。Dynamo的做法是將每臺(tái)機(jī)器針對(duì)數(shù)據(jù)塊建立一棵Merkle Tree。

Merkle Tree又叫Hash Tree，它把一臺(tái)機(jī)器上的數(shù)據(jù)塊細(xì)分成幾個(gè)更小的數(shù)據(jù)區(qū)塊，每個(gè)數(shù)據(jù)區(qū)塊計(jì)算出一個(gè)hash值，作為整棵樹的葉子節(jié)點(diǎn)，被一層層合并計(jì)算上去，最終得到root節(jié)點(diǎn)的hash值。當(dāng)數(shù)據(jù)發(fā)生錯(cuò)誤時(shí)，我們只需要從root開始比較兩棵Merkle Tree的hash值，就可以在對(duì)數(shù)時(shí)間內(nèi)快速找到哪一段或幾段數(shù)據(jù)中的hash值變化了。之后只要針對(duì)找出錯(cuò)誤的數(shù)據(jù)區(qū)塊進(jìn)行更新就可以實(shí)現(xiàn)整臺(tái)錯(cuò)誤機(jī)器上的數(shù)據(jù)恢復(fù)了。這大大降低了數(shù)據(jù)恢復(fù)的代價(jià)。

1.4? 使用Gossip Protocol解決Dynamo中的分布式的消息傳播問題

Gossip Protocol也叫Epidemic Protocol（流行病協(xié)議），也叫“流言算法”“疫情傳播算法”等。它解決的是在分布式集群中的消息傳播問題。舉個(gè)例子，假定三臺(tái)機(jī)器存儲(chǔ)的是相同的數(shù)據(jù)，現(xiàn)在我們將數(shù)據(jù)的一部分進(jìn)行修改，在沒有中心服務(wù)器的情況下，這條修改消息如何傳遞給另外的兩臺(tái)機(jī)器，就需要一種算法或協(xié)議進(jìn)行確定。Gossip Protocol被實(shí)際應(yīng)用在了Dynamo的成員資格及錯(cuò)誤檢測(cè)中。

Gossip過程是由種子節(jié)點(diǎn)發(fā)起，當(dāng)一個(gè)種子節(jié)點(diǎn)有狀態(tài)需要更新到網(wǎng)絡(luò)中的其他節(jié)點(diǎn)時(shí)，它會(huì)隨機(jī)地選擇周圍幾個(gè)節(jié)點(diǎn)散播消息，收到消息的節(jié)點(diǎn)也會(huì)重復(fù)該過程，直至最終網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都收到了消息。這個(gè)過程可能需要一定的時(shí)間，由于不能保證某個(gè)時(shí)刻所有節(jié)點(diǎn)都收到消息，但是理論上最終所有節(jié)點(diǎn)都會(huì)收到消息，因此它是一個(gè)最終一致性協(xié)議。

本文使用Java語言模擬了Gossip協(xié)議下的消息傳播過程，鏈接地址如下：https：//gitee.com/willfree/antiEntropy_Gossip/blob/master/gossip.java。

2? 谷歌的“三駕馬車”和它們的設(shè)計(jì)思想

谷歌的騰飛不僅僅因?yàn)樗乃阉饕?，事?shí)上也不僅僅因?yàn)榻酉聛硪榻B的“三駕馬車”，但它在云計(jì)算上的“三駕馬車”確實(shí)功勛卓著。它們是：GFS、MapReduce、BigTable。

GFS，谷歌文件系統(tǒng)，是一個(gè)可擴(kuò)展的大型數(shù)據(jù)密集型應(yīng)用的分布式文件系統(tǒng)。它具有很強(qiáng)的數(shù)據(jù)容錯(cuò)能力，可以提供極高的計(jì)算性能，更令人興奮的是，由于可以被部署在相對(duì)廉價(jià)的機(jī)器上，其硬件投資和運(yùn)營(yíng)成本變得很低。GFS的架構(gòu)由一臺(tái)Master服務(wù)器和許多臺(tái)文件服務(wù)器（chunk server）構(gòu)成，并且有若干客戶端（client）與之交互。它采用中心服務(wù)器模式。

MapReduce是一個(gè)超大集群的簡(jiǎn)單數(shù)據(jù)處理系統(tǒng)。Map函數(shù)是將輸入?yún)?shù)映射到Worker;Reduce函數(shù)是將Worker歸約，成為輸出參數(shù)。其主要思想來源于函數(shù)式編程和分治思想。它將所有服務(wù)器中的處理器有效地利用起來計(jì)算保存在GFS中的海量數(shù)據(jù)并得到想要的結(jié)果?；贛apReduce編寫的程序可以在相當(dāng)多的普通PC機(jī)上被并行執(zhí)行，這是MapReduce的最大魅力所在。

BigTable是一個(gè)結(jié)構(gòu)化數(shù)據(jù)的分布式存儲(chǔ)系統(tǒng)。它在其他的幾個(gè)Google基礎(chǔ)構(gòu)件提供的服務(wù)之上被構(gòu)建。例如：它實(shí)際使用了GFS來存儲(chǔ)它的日志文件和數(shù)據(jù)文件。BigTable不僅僅帶有分布式的特點(diǎn)，在GFS的基礎(chǔ)上，正如其名稱所講，它實(shí)際對(duì)結(jié)構(gòu)化數(shù)據(jù)進(jìn)行了高效的存儲(chǔ)和處理。它一般運(yùn)行在一個(gè)共享的機(jī)器池中，這些機(jī)器會(huì)同時(shí)運(yùn)行著其他的分布式應(yīng)用程序，這種共享機(jī)器的狀態(tài)也是BigTable的一大特色。BigTable有著自己的集群管理系統(tǒng)，用以監(jiān)視集群中各個(gè)機(jī)器的狀態(tài)、處理機(jī)器的故障、調(diào)度任務(wù)和管理資源。

谷歌的“三駕馬車”直接為谷歌的一些應(yīng)用提供了基礎(chǔ)的分布式數(shù)據(jù)存儲(chǔ)和處理服務(wù)。它們并非完全獨(dú)立，比如MapReduce和BigTable都調(diào)用了GFS所提供的大量數(shù)據(jù)存儲(chǔ)服務(wù)。此外，他們也并非僅僅是平臺(tái)或系統(tǒng)的名稱，MapReduce也代指了它所使用的云編程模式。它們不僅僅啟發(fā)和推動(dòng)了Hadoop的建立和崛起，也對(duì)后Hadoop時(shí)代的新“三駕馬車”——Caffeine、Pregel、Dremel，有著深遠(yuǎn)的影響。

3? 基于云計(jì)算技術(shù)的未來展望

云計(jì)算在不遠(yuǎn)的曾經(jīng)是計(jì)算機(jī)學(xué)界一個(gè)火爆的名詞，即使在現(xiàn)在，它的基礎(chǔ)算法、技術(shù)和平臺(tái)也在推陳出新。這很大程度上源自人們對(duì)于云計(jì)算發(fā)展到極致的美好時(shí)代的遐想。

通過以上對(duì)四個(gè)典型云平臺(tái)的介紹，我們對(duì)云計(jì)算技術(shù)和它的一些基礎(chǔ)算法有了一定的了解。基于此，本文對(duì)未來云技術(shù)的發(fā)展和應(yīng)用場(chǎng)景作了一些展望。

在未來，在解決了云計(jì)算技術(shù)上的諸多痛點(diǎn)，出現(xiàn)了高質(zhì)量、統(tǒng)一標(biāo)準(zhǔn)的云服務(wù)之后，將會(huì)出現(xiàn)這樣一種美好的生活圖景：算力和數(shù)據(jù)存儲(chǔ)空間就像生活中的水和電一樣，只需要按規(guī)定付費(fèi)，打開“開關(guān)”就能隨時(shí)隨地方便的被使用。人們只需要一個(gè)支持高分辨率顯示屏渲染的GPU，以及顯示屏、音響設(shè)備等簡(jiǎn)單的I/O設(shè)備共同組成的“電腦”，就可以通過超高帶寬的網(wǎng)絡(luò)連接進(jìn)行學(xué)習(xí)、辦公等所有操作。不僅如此，除非地球爆炸這樣大的災(zāi)難，人們幾乎不用擔(dān)心數(shù)據(jù)的丟失或者錯(cuò)誤，因?yàn)樵破脚_(tái)已經(jīng)幫他們備份了足夠多的數(shù)據(jù)，并通過一致性算法、同步算法來保證他們寶貴數(shù)據(jù)的絕對(duì)正確。

參考文獻(xiàn)：

[1] Decandia G，Hastorun D，Jampani M，et al. Dynamo：amazon’s highly available key-value store [J]. ACM SIGOPS Operating Systems Review，2007，41（6）：205-220.

[2] Ghemawat S ，Gobioff H ，Leung S T. [ACM Press the nineteenth ACM symposium - Bolton Landing，NY，USA （2003，10，19-2003，10，22）] Proceedings of the nineteenth ACM symposium on Operating systems principles，- SOSP ＼"03 - The Google file system [C].// ACM，2003：29-43.

[3] Dean J ，Ghemawat S. MapReduce：Simplified Data Processing on Large Clusters [C].// Proceedings of Sixth Symposium on Operating System Design and Implementation （OSD2004），USENIX Association，2004.

[4] Chang F，Dean J，Ghemawat S，et al. Bigtable：A Distributed Storage System for Structured Data [J].ACM Transactions on Computer Systems，2008，26（2）：1-26.

作者簡(jiǎn)介：王鋒（1998.09-），男，漢族，河南濮陽人，本科在讀，主要研究方向：云計(jì)算、數(shù)據(jù)挖掘、計(jì)算機(jī)視覺。