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

關(guān)鍵詞：云計算;分布式算法;云平臺

中圖分類號：TP393.09;TP301.6? ? ? 文獻標識碼：A 文章編號：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? 引? 言

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

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

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

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

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

Amazon大量的用戶服務(wù)數(shù)據(jù)被存儲在Dynamo中?？梢哉f它為Amazon的電子商務(wù)平臺及其云計算服務(wù)提供了最基礎(chǔ)的支持。

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

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

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

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

（4）Gossip=>成員資格及錯誤檢測。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

如果在數(shù)據(jù)錯誤發(fā)生時針對所有數(shù)據(jù)進行恢復，因為需要更新一臺機器上的所有數(shù)據(jù)，必然導致大量且慢速的數(shù)據(jù)操作。Dynamo的做法是將每臺機器針對數(shù)據(jù)塊建立一棵Merkle Tree。

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

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

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

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

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

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

谷歌的騰飛不僅僅因為它的搜索引擎，事實上也不僅僅因為接下來要介紹的“三駕馬車”，但它在云計算上的“三駕馬車”確實功勛卓著。它們是：GFS、MapReduce、BigTable。

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

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

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

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

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

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

通過以上對四個典型云平臺的介紹，我們對云計算技術(shù)和它的一些基礎(chǔ)算法有了一定的了解?；诖耍疚膶ξ磥碓萍夹g(shù)的發(fā)展和應(yīng)用場景作了一些展望。

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

參考文獻：

[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.

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