前言

近年來隨著網際網路愈來愈普及與網路頻寬速度的增加，使得使用者越來愈習慣使用由網路服務業者所提供的服務，如Gmail、Google Docs、Google Calendar、無名小站、YouTube等。相對的因應該服務也產生了大量的資料，而這些資料應該如何處理，也著實成為各網路服務業者所困擾的問題。

當然美國網路搜尋的龍頭Google也遇到了相同的難題，因此開始著手研究應該如何處理以及儲存如此龐大的資料量。之後便分別在2003年提出分散式檔案系統架構Google File System(GFS)、2004年提出大規模資料處理的模型MapReduce架構以及2006年提出基於Google File System針對結構化資料儲存的分散式檔案系統BigTable，並在其論文中提出如何運用其架構以對於Google的各項服務增加了重大的效益。

而雲端運算(Cloud Computing)此一新興名詞也就產生了，該名稱源自於技術人員當在討論網際網路時皆會畫出一朵雲用來代表網際網路，因此雲朵也就變成的網際網路的代名詞了。而雲端運算簡單的說就是在網際網路上進行資料的儲存與運算。其所運用的技術，本質上來看也算是分散式運算的一種，其最基本的概念，就是希望能夠透過網際網路將大規模的資料量放置在雲端，並且將龐大的單一處理程序自動分拆成無數個較小的子程序，再交給雲端中的為數眾多的電腦來處理，以加快處理速度，最後再將處理的結果回傳給使用者。透過這樣的技術，企業可以在極短的時間內，處理數以千萬計的資料，達到類似超級電腦的處理能力，但其價格又不像超級電腦那般的昂貴以及難以維護。

Google File System(GFS)分散式檔案系統

GFS分散式檔案系統對於分散式計算非常的重要，因為當計算單元分散到各台電腦上時，通常都會需要讀取或是儲存資料，不管是讀取或是儲存的動作都需要有一個檔案系統來將資料作適當的存放與備份。

Google所提供的GFS是一種相當容易擴大檔案系統容量的架構，主要就是用在大規模、分散式以及需要對大量資料進行運算的應用。它能夠運行在像你我所使用的一般電腦上，並不需要企業等級的高階伺服器才能夠執行，雖然一般的電腦故障率較高，但是透過GFS內部預設的備份機制，能提供強大的容錯功能。而GFS與以往的檔案系統最大的不同之處在於：

• 硬體會經常性故障，因為系統是建立在大量的廉價電腦上，而這些電腦常常需要被大量的存取，因此硬體的錯誤不應該被視為異常，而是應該視為必定會發生的情況，系統需要能夠自動處理。也由於硬體會時常故障，系統必須這些電腦持續監測，當有問題發生，系統需要從故障中進行恢復。


• 由於系統需要存放大量的超大型檔案。可能會有數百萬個超過100MB的檔案。也有可能是數GB的檔案，因此應該要對這些大型檔案做有效的管理。但同時也必須要支援小型的檔案，但系統不必為小檔案進行特別的效能調校。


• 大部分對於存在GFS的處理模式為在檔案結尾處增加資料，比較少的情況是修改既有的資料。因為存在GFS檔案系統的資料通常都是很大的單一檔案，所以對一個檔案的隨機寫入操作通常是不存在的。取而代之的是大量的程式對單一檔案進行依序的讀取或是寫入動作，因此必須對此動作進行最佳化以及保證大量的程式同時寫入或是讀取時彼此之間不能混淆。


• GFS在寫入的資料完成時，通常是很少會對檔案進行更動，因此在依序讀取大量的資料時，必須要非常的有效率。但同時也需增加在隨機位置對寫入少量的資料的支援，只是不需要特別有效率。

如圖一，一個典型的GFS叢集是由一個master和多個chunkserver所組成，並且可能由多個用戶端程式所存取。每一個節點都是一個普通的Linux電腦環境，而GFS系統則是運行在該Linux系統下的程式。當然只要電腦的資源足夠chunkserver與client也可以運行在同一部機器上。


在GFS的檔案系統下，每一個存在GFS的檔案都會被master分割成固定大小的chunk。每一個chunk資料都由master根據建立的時間產生一個唯一並且無法改變的chunk handle名稱，長度為64位元，而該名稱其實就等同於檔名。一個大的檔案被分割成多個chunk之後，這些chunk就會被存放在多台chunkserver上，而且是用Linux本身的檔案系統所儲存。當需要存取檔案時，就需要先知道該資料是放在那個chunkserver並且透過chunk handle以及byte range來作讀取。而為了提供容錯機制，因此每個chunk檔預設都會有3個備份，並且放入不同的chunkserver上，以避免單一chunkserver毀損。但是使用者可以對不同namespace下的檔案設定不同的備份檔案數。

master會負責所有檔案系統的metadata，包括namespace資訊、檔案與chunk的對應關係、chunk所存放的實際位置以及該檔案的相關存取權限等等。除此之外master也負責GFS系統的相關活動，像是chunk的分割機制、已經失效的chunk檔案或是chunkserver之間的chunk備份管理。因此master和這些chunkserver彼此之間都會有定期的HeatBeat通訊，透過HeatBeat，master可以傳遞指令給chunkserver並且master亦可藉此知道chunkserver是否已經掛掉，當每chunkserver經過一段時間後沒有傳送HeartBeat給master，那麼master會將該chunkserver上的所儲存的檔案列出清單，逐一尋找其chunk的備份檔，另外複製到其它台chunkser上，以維持系統預設的備份個數。

各個應用系統則是透過GFS提供的檔案系統操作API，來與master或是chunkserver進行讀寫的互動。GFS client與master互動的資訊主要是metadata，而實際的檔案讀寫動作則是發生在chunkserver，藉此以避免掉master變成效能瓶頸的情況。無論是GFS client或是chunkserver都不需要cache檔案資料。因為在大部分的情況下所儲存的資料都非常的龐大，大到無法有足夠的容量可以cache，而也因為沒有cache所以不需要做同步的機制，使得整個系統設計也大大的簡化了。但是GFS client會cache metadata的資料，以減少master的負擔。而chunkserver當然也不需要cache資料，因為chunk是以檔案的形式儲存在Linux的檔案系統下，所以Linux的buffer cache就已經會將常用到的資料cache到記憶體了。

接下來就簡單的介紹圖一的讀取流程。

• 首先，GFS client會將Application所要讀取的檔名與byte offset，依據使用者或是系統內定的chunk大小，轉換成檔案的chunk index，也就是Application所要讀取的資料是在第幾個chunk中。


• 接著將file name與chunk index傳送給master。


• master就會回傳相關的chunk handle與實際儲存的chunkserver location資訊。然後GFS client會將該資訊以檔名+chunk index的格式當作cache的key，並且儲存起來。實際上，通常GFS client會在一次連線中要求多個chunk的資訊，master當然也會回應多個chunk資訊給GFS client。


• GFS client接著對chunkserver發出連線請求，由於同一份chunk會存在三台不同的chunkserver上，因此GFS會選擇離GFS client較近的chunkserver做連線。而連線的資料包含了chunk handle以及所要取得的byte rang，後續的讀取動作GFS client會透過已經cache起來的資訊，再去取的下一筆chunk的位置資訊，而不需再經由master以減少其負擔。除非cache資訊已經過期，那麼就需要再重新向master取出連線資訊。


• chunkserver傳回GFS client所要求的檔案資訊。

MapReduce運算模式

MapReduce對於Google來說相當的重要，這是為什麼Google的搜尋引擎可以這麼的有效率將我們想要的資料找出來的一個重要關鍵。當然不僅僅應用在改善搜尋引擎的準確度上，MapReduce已經應用在許多Google服務中，如Google Analytics、Google Earth、Orkut、Google Finance以及Personalized Search等等。因此站在教育與分享的角度上，Google將MapReduce的運算模式公開發表成論文。不過雖然Google公開了MapReduce的內部運作概念及模式，但是卻沒有公開所開發完成的系統。但是我們依然可以透過其論文一窺MapReduce的奧秘。

MapReduce其實就是一種容易撰寫的分散式與平行處理的程式設計模型，它主要運用在處理大規模的資料集。主要由Map與Reduce兩個動作組成，開發人員在撰寫程式時，僅需要對所要處理的資料，於Map的架構下撰寫商業邏輯(也就是資料運算的部分)，透過key/value pair取得輸入資料，運算完畢後一樣將運算結果透過key/value pair將資料輸出下一階段處理。而Reduce階段則是將上一階段傳送過來的資料依照相同的key值做合併簡化處理即可。

開發人員完全不需要有平行處理或是分散式系統的知識，包含了不需要知道程式是如何複製到各個電腦中、資料如何讓在各自電腦中的Map存取、機器如果掛掉工作應該如何重新執行以及各台機器中工作如何平行處理等等問題。因此開發人員只需將心力著重在真正要解決的事物上即可，這已經大大的減輕開發人員的負擔。而MapReduce強大之處，就是在於你僅須撰寫幾行程式就可以讓成千上萬台電腦為你的工作。

如圖二，是MapReduce架構的整個執行流程。當開發人員將其開發完成的程式丟到MapReduce去執行，就會產生如圖二的操作。流程說明如下：



一、MapReduce架構首先會將該程式所要處理的資料分割成M塊，每塊大小多為16~64MB之間(每塊的大小可以透過參數來指定)，接著MapReduce再將使用者所要執行的程式複製到需要執行的機器上，並且啟動該程式執行。其中會有一台機器負責監控各台機器的執行情況，稱之為Master。其餘的機器則稱之為worker。

二、Master負責將M個Map任務分派給空閒的worker，也負責將R個Reduce任務分配給空閒的worker。當然兩者的worker可以是同一台機器也可以是不同台機器。

三、其中一個被分配Map任務的worker從被分割的資料中讀取所需要處理的資料片段，從輸入資料中剖析出key/value pair並且傳送給使用者所撰寫的Map程式處理。Map程式再將產生出來的中間結果key/value pair存到緩衝記憶體。其他Map階段的機器也是如此處理。

四、這些緩衝到記憶體的中間結果將會被定時地寫入本機硬碟，並且透過partition機制分割R個區域。而這些中間結果所儲存的位置資訊將會被傳回Master，並且交由Master將此資訊遞送給執行Reduce的worker。

五、當Master通知Reduce的worker這些位置資訊時，worker便會使用RPC來讀取Map worker所產生的中間資料。當Reduce worker讀完所有的中間資料，就會使用key來進行排序，這樣會使得所有相同key的資料群聚在一起。但是若資料太大無法於記憶體中排序，那麼就必須要使用外部排序機制了。

六、Reduce worker會取出所有相同key的value傳送給開發人員所撰寫的Reduce程式進行處理。每個Reduce任務所處理完的結果將會輸出一個檔案，因此有多少個Reduce任務就會產生多少個檔案。

七、當所有的Map與Reduce任務都處理完了之後，Master會將執行的權限交給開發人員所撰寫的程式來繼續執行。

當這些任務都結束之後，MapReduce的執行結果就會存放在開發人員所指定的檔名中，在一般的情況下有R個Reduce任務就會有R個輸出檔。開發人員通常也不需要將R個輸出檔合併成一個檔案，而是將此資料在丟給下一個MapReduce程式處理。

由於MapReduce架構的主要概念是源自於函數語言，我們可以透過下列式子來簡單說明其概念。



k1與v1是指在執行map階段時的輸入key/value pair，而k2與v2則是當map階段執行完畢的結果，也是以key/value pair的形式輸出。而在reduce階段k2與list(v2)則是將map階段執行完畢的結果依照相同key的value集中起來處理，而list(v2)則是reduce階段最後處理完所產生的結果資料。

接下來透過WordCount這個常見的例子來做說明，這個例子主要的功能就是統計單一文字出現過的次數。以下為虛擬碼：

Map階段：



Reduce階段：



Map階段的key為文件名稱，value為文件的內容。檢查value中的每一個單字，並且以每個單字為key，其value皆是數值1。直到value中的所有內容處理完畢。最後輸出成中間資料。

Reduce階段的key為文件中出現過的單字，values為同一個單字的所有value集合。同一個單字的所有value作次數加總，最後輸出該單字的加總結果。

結語

以上所述是Google的搜尋速度與品質之所以可以如此快速與精準的重要武器，但有沒有什麼樣的Open Source軟體已經支援這樣的架構，讓我們不需閉門造車而可以站在巨人的肩膀上擁有更寬廣的視野?有的，Apache基金會所贊助的計畫Hadoop就擁有這樣的潛能。讀者有興趣不妨針對此再深入研究。

參考資料

1.Amazon Elastic Compute Cloud, http://aws.amazon.com/ec2
2.Amazon EC2 Instance Types, http://aws.amazon.com/ec2/instance-types/
3.Applications powered by Hadoop: http://aws.amazon.com/ec2/instance-types/
4.Dean, J., and Ghemawat, S., 2008, “MapReduce: Simplified Data Processing on Large Clusters”, Communications of the ACM, 51(1): p. 107-113.
5.Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber, 2006, “Bigtable: A Distributed Storage System for Structured Data”, 7th USENIX Symposium on Operating Systems Design and Implementation, pp.205-218.
6.Hadoop, http://hadoop.apache.org/
7.Nutch, http://nutch.apache.org/
8.Sanjay, Hgobioff, and Shuntak, 2003, “The Google File System”, 19th ACM Symposium on Operating Systems Principles(SOSP).
9.Scaling Hadoop to 4000 nodes at Yahoo!, http://developer.yahoo.net/blogs/hadoop/2008/09/scaling_hadoop_to_4000_nodes_a.html
10.Shadi Ibrahim, Hai Jin, Bin Cheng, Haijun Cao, Song Wu, 2009, “CLOUDLET: Towards MapReduce Implementation on Virtual Machines”, Proceedings of the 18th ACM international symposium on High performance distributed computing, Pages: 65-66.
11.Shadi Ibrahim, Hai Jin, Lu Lu, Li Qi, Song Wu, and Xuanhua Shi, 2009, “Evaluating MapReduce on Virtual Machines: The Hadoop Case”, Proceedings of the 1st International Conference on Cloud Computing, Pages: 519 - 528.
12.Spears, W. M., De Jong, K. A., Back, T., Fogel, D. B., and deGaris, H., 1993, "An overview of evolutionary computation", Proceedings of the 1993 European Conference on Machine Learning.
13.Welcome to NCHC Cloud Computing Research Group, http://trac.nchc.org.tw/cloud
14.Yahoo! Launches World's Largest Hadoop Production Application, http://developer.yahoo.net/blogs/hadoop/2008/02/yahoo-worlds-largest-production-hadoop.html