星期五, 6月 25, 2010

雲端運算Cloud Computing學習心得筆記(四) MapReduce

  前幾回學習到硬體虛擬化及資料叢集平行運算的概念,整個infrastructure建立後,要怎麼開發平行運算的程式呢? 最著名的應用就是MapReduce了,MapReduce的概念並不新穎,甚至還有人提出他是一種倒退[1],是的,這種處理方式不會有關聯性資料庫常用的特性, 如:

資料型別 :  int varchar …等

更新 Update : 更新某筆資料

索引(index) : PK 及 FK

資料關聯性及一致性

交易Transcation : 每個Transcation 可以在資料受損時rollback

視圖View : 改變View 不用更新資料結構

 

MapReduce 本來就不是來取代關聯性資料庫的,他是用來處理大型的資料分析,他不太需要上述的特性,舉個例來說,Google每天去Crawl 上億的網站資料,如果全存在資料庫裡來分析,還要同時應付全球用戶的搜尋,用過DBMS的都知道,整個系統只會越來越慢,花大錢擴充資料庫的話是相當高額的成本。因此MaprReduce是有存在的必要的。

 

MapReduce 怎麼運做呢?以下圖[2]為例

 

 

 

 

1. 用戶程式裡的MapReduce Libary 會先把輸入的檔案資料切成M等份,每個等份16 MB-64MB , 然後會複製好幾份存在整個機器叢集

 

2. 其中一份特別的資料會指派給Master. 再由Master主機去找閒置的機器當Worker機,會指派M個Map task 和 R個Reduce task到worker主機,至於哪些Worker機做Map哪些做Reduce,也是由Master機來指派 。

 

3. 負責做Map的Worker機,會根據input資料的 key/value 的配對傳到開發者設計的Map function並將其Map結果存在暫存記憶體裡

 

4. 由Map function做出的暫存資料存在本機的 Intermediate file,由Partition function 分割成R 個區塊後把區塊位址交還給Master主機

 

5. 負責執行reduce 的Worker 接到由Mater傳來的Map處理完的資料位址後,會遠端讀取這些資料並依照key做排序,把相同的Key再群組(Group)起來.

 

6. Reduce worker 會計算sort 和 group 後的單一key的數量,在把這些直丟給用戶定義的Reduce function處理,處理後的資料會附加(append)到reduce 區的output 檔案。

 

7. 全部處理完後,Master主機會叫醒用戶程式

 

以上是流程圖,如果再參考資料流成圖[3]會更清楚

原本的資料

 

Deer Bear River

Car Car River

Deer Car Bear

 

經過MapReduce 後就變成

 

Bear,2

Car,3

Deer,2

River,2

這部分的應用,我直覺的想到,要做熱門關鍵字排行,只要將一段時間的大量查詢輸入的資料丟進此系統,很快的就可排出結果。

 

其他的應用為:

1 分散式的Grep : 做分散式的關鍵字搜尋

 

2. 計算某個URL被執行的頻率 : Key/value 在Map是<URL,1> , Reduce 後就是<URL,total count>

 

3. 反向網路連結圖 : 由<target, source> 去推出連到這個網站的連結量 <target,list(source)>

 

如果要直接測試MapReduce 程式,Amazon Elastic MapReduce似乎是不錯的選擇,試玩過在跟大家分享 http://aws.amazon.com/elasticmapreduce/

 

 

參考資料

[1] MapReduce: 一个巨大的倒退

[2]Introduction to Parallel Programming and MapReduce

[3] http://blog.jteam.nl/wp-content/uploads/2009/08/MapReduceWordCountOverview1.png

其他:

     Dean, Jeff and Ghemawat, Sanjay. MapReduce: Simplified Data Processing on Large Clusters http://labs.google.com/papers/mapreduce-osdi04.pdf

     Lammal, Ralf. Google's MapReduce Programming Model Revisited. http://www.cs.vu.nl/~ralf/MapReduce/paper.pdf

    Open Source MapReduce: http://lucene.apache.org/hadoop/

星期一, 6月 21, 2010

雲端運算Cloud computing學習心得筆記(三) Yahoo的架構

  提到Hadoop其實就會想到Yahoo, Yahoo 目前是最大的Hadoop使用者,於2009年10月公佈的數字,已有4000個node clusters在運作

為何Yahoo要改用Hadoop呢

Yahoo 提出的理由如下[1] :

image

 

的確, 如果Yahoo在以前是使用傳統N-tiers 的方式,在維護及擴充方面會比較困難,而且成本較高,我想這也是為何Yahoo在服務上的擴展一直不如Google迅速有效率的原因,看來這幾年Yahoo花了不少功夫在改變核心架構以提升競爭力,還於2006年聘顧了Hadoop 之父Doug Cutting來主持Hadoop計劃.

 

  我們再來看看 Yahoo從2006年以後 Hadoop 硬體上的成長曲線[2],已經到了25000 nodes ,82Peta的Disk,成長速度相當驚人,這也讓我們了解到,要長期維持在全球流量第一,就必須持續的擴充及成長,而不是停在原地。

image

Yahoo 的Hadoop架構用在哪些方面呢?

以Yahoo首頁為例[3]

image 

傳統的網頁是靜態的,也就是說內容都是由編輯人員事先設定完成,但新型態的網頁內容都傾向由用戶行為去分析哪些資料是重要的,也就是說,在Yahoo首頁會根據用戶的點選及搜尋行為,去做內容的優化,也可以根據mail上用戶的行為來判斷垃圾信,傳統網站的做法會把這些網站內容的用戶使用記錄存放在資料庫裡分析,這樣的成本相當額貴而且沒效率。

 

Yahoo 導入Hadoop後增加多少效率呢?

以Search assist 為例 :

 image

我們每次利用關鍵字搜尋資料,在Search box下方會有些推薦的關鍵字,這些資料的產生若用以前傳統的架構,要26天才分析完成3年的資料再更新到網站,光開發這個功能就要3周的時間,但利用Hadoop架構只要2-3天就開發完成,而且可以每20分鐘就分析完資料並更新,一些熱門的關鍵字都可以很快的被顯示在Search assist上,帶給用戶更好的使用體驗。

 

開發流程管理

Hadoop Development Workflow with Gridmix3

Yahoo 目前是用Gridmix3及Rumen 來管理布署及監控Hadoop架構[4]

 

未來發展

我們可以參考Hadoop summit 2010 會議 ,Hbase、 Pig、 Hive、 Cascalog 、ZooKeeper 等相關技術持續在討論,流程管理工具Oozie還在發展中,有興趣的人可以報名參加。

Agenda 在 http://developer.yahoo.com/events/hadoopsummit2010/agenda.html#71

 

 

資料來源:

[1]Yahoo!Webmap ,Christian Kunz, March 25, 2008

[2][3]Hadoop at Yahoo, Eric Baldeschwieler ,VP Hadoop Software Development, Yahoo!

[4] http://developer.yahoo.net/blogs/hadoop/2010/04/gridmix3_emulating_production.html

http://www-07.ibm.com/tw/imc/igs/article/2_1/3.html

http://developer.yahoo.net/blogs/hadoop/

Hadoop at yahoo https://opencirrus.org/system/files/OpenCirrusHadoop2009.ppt

http://research.yahoo.com/node/2104

星期一, 6月 14, 2010

雲端運算Cloud Computing學習心得筆記(二) Facebook的雲端架構

傳統的網頁通常是用戶主動在Browser上refresh頁面才會更新資料,一般節省資源的方式為把動態網頁(asp,php,jsp..)轉靜態頁面(html),並利用Trigger的方式更新資料庫資料及網頁資料,但隨著AJAX技術普及化,許多網站加入了即時更新內容的機制,如 Facebook 的 news feed 或status update ,由於每個人本身都是訊息發佈者及訂閱者,因此當用戶的關係越密切,讀寫的資料就越龐大,就Facebook 2009年公布的數據為:


 


資料產生:


超過3億位有效用戶


每天有3000萬個用戶至少會更新一次自己的狀態


每個月有超過10億張的照片上傳


每個月有超過1000萬的影片上傳


每周新增超過10億種的內容(網站連結,新聞,部落格文章,記事本,照片..等)


 


資料用量為:


每天產生4TB的已壓縮資料


每天有135T的已壓縮資料被掃描檢視


每天8萬小時的運算時間


 


由於資料量相當大,如果要購置可以支援的高階超級伺服器將會相當額貴,因此Facebook採用Hadoop架構,用大量的PC去取代高階伺服器,既省錢又因平行運算的架構及高容錯性,對於Peta級資料量其查詢效能相當好,其所規畫出來的儲存的空間為


4800台cores (虛擬server), 5.5 PB (Peta=1015)


每個node配置 12TB空間


 


硬體架構如下:


image


Facebook Datacenter 影片 :



 






由於Facebook 上需要分析用戶資料來做相關的推薦,因此他們還使用了HIVE來當資料庫倉儲系統,其架構如下:


image


Scribe 是蒐集Log 的 server , 將蒐集到的log 往 Hadoop Hive warehouse丟, 即可用近似SQL的語法來做分析,一些推薦的內容如 朋友、社團、專頁、廣告..等應該都是透過這樣的機制產生。


 


由Facebook公開的資料可以得知,經營一個全球化的SNS網站絕不能用一般的思維來設計,看似簡單的網站,若架設在單一Server上給少數使用者用,一樣可以運作,但到了要服務3億人時,網站看似沒變但整個架構就都不一樣了,要如何彈性有效率,可以參考一下Facebook 的架構。


 


資料來源:


Facebook Tech Talk: Rethinking Servers & Datacenters http://www.facebook.com/techtalks?v=wall#!/video/video.php?v=208561675468&ref=mf

Hadoop & its usage in facebook http://www.snia.org/events/storage-developer2009/presentations/keynotes/DhrubaBorthakur-Hadoop_File_System_Architecture_Facebook.pdf


Hadoop and Hive Development at facebook http://www.borthakur.com/ftp/hadoopworld.pdf

星期六, 6月 05, 2010

雲端運算Cloud computing學習心得筆記(一)

  最近常被一些媒體拿雲端出來亂炒,把所有網路服務都試為雲端服務,所有傳統網站突然就變成雲端網站,大家都號稱自己擁有雲端技術,然後大幅報導全球將引爆雲端商機,我看了是一頭霧水,在這裡分享一下個人所知道的雲端運算.

 

緣由

在雲端運算發展以前,其實已有Grid computing , Utility computing 等架構,因此平行運算、on demand service的概念早就存在,但以前的系統大都為企業和組織內部使用,直到雲端運算才開始有對外完全開放且統一的架構.

而雲端運算的技術是始於Google、Yahoo、Amazon這類超大型網站服務公司在想解決大型網路架構效能所演進而成的技術,追朔其歷史,應該始於2007年10月,GoogleIBM開始在美國大學校園,包括卡內基美隆大學麻省理工學院史丹佛大學加州大學柏克萊分校馬里蘭大學等,推廣雲端運算的計畫,這項計劃希望能降低分散式運算技術在學術研究方面的成本,並為這些大學提供相關的軟硬體設備及技術支援(包括數百台個人電腦BladeCenterSystem x伺服器,這些運算平台將提供1600個處理器,支援包括LinuxXenHadoop等開放原始碼平台)。而學生則可以透過網路開發各項以大規模運算為基礎的研究計畫。[1]

 

大型網站面臨的問題

在2000年左右,絕大部分的網站用的都是three tiers architecture,大型網站則是N tiers,其概念還是把各網站功能拆解成一台台的伺服器,一般基本的規劃如下:

 

Web server  2台 , 2 CPU ,4 G RAM

AP server   2台  , 2 CPU , 4G RAM

Mail server  2台 , 2 CPU,4 G RAM

Database  2台, 4 CPU , 8G RAM

File server  2台

Storage : NAS / SAN 5T

 

一次購買2台主要是要做load balance 及 Cluster,來提高網站的stability、 avalibility與scalability.

若再加上Firewall 、DNS server、 Switch、 router 等網路設備,一開始就得投入不少資金購買設備。

隨著網站會員增加,主要的server loading不勝負荷,通常就會開始購買額外的Server,而Database就要看需求增加CPU或採分散式資料庫架構,並增加許多Cache的function 來降低Loading

因此一般中型網站經拆解後,其伺服器數量可能變成如下:

 

Web server  10台

AP server  8台

Mail server  2台

Master Database  2台(8 CPU) + sub-Database X 4台 (2 CPU)

File server  4台

Storage : SAN 20T

 

這時問題就發生了

1. 各Server 資源使用不均

透過監控軟體可以發現,80%的server CPU loading 低於 30% 但 20%的 Server CPU 大都維持在60%

2. Database Cost過高

把所有網站的資料都存在資料庫在初期ok,但一旦資料一多,每個存取都相當耗系統資源,當然可以做資料庫效能調校、資料表切割、資料快取、分散式架構,但由於Database的license 通常不便宜,這樣的擴增相當燒錢。

3. Storage 的效能不足

在大量的資料存取下,Storage Disk I/O 居然也吃緊,必須準備更多的Storage 來分散存放資料

 

問題解決方式

我想這類問題在超大型網站Google Yahoo 上早就發生,看看他們是怎麼解決的

 

1. 將硬體虛擬化,導入平行運算

虛擬化的好處是可以讓一些閒置Server也可以運用,而且維護方便,不用停機。目前常看到的解決方案為 : XENVMwareHyper-V

平行運算可以讓一些複雜吃資源的運算在短時間完成,不會讓某特定做運算的Server lock住導致整體效能變差,目前常用的解決方案 : Hadoop MapReduce、 Sectorgoogle Mapreduce

由於伺服器虛擬化且可以平行運算,Google 早期都採用PC等級的電腦充當伺服器,大家可參考下列影片,很難想像這就是雲端的前身





2.  分散式資料及noSQL 架構

主流資料庫大都為RDBMS關聯性資料庫架構,其好處式資料易於維護、有Transaction Rollback功能、可以有多重索引、資料完整性及準確性高,但缺點是擴增不易、成本高、對於大量存取資料效能不佳,因此RDBMS比較適合在金融、EC、Dataware house、ERP…等商業應用上,而網頁的資料,並不需要那麼精準,但非常需要效率,所以衍生出下列分散式資料架構及noSQL資料庫

 

分散式檔案架構

Google File system :

        Goolge 於2003年發表的一篇論文,使用分散容錯的架構在許多便宜的HDD上取代當時昂貴的Storage,並大幅提升存取效率 [2]

Hadoop HDFS :

       Apache Hadoop架構下的分散式檔案架構,可以搭配HivePig 來存取資料[3][4]

 

noSQL Database:

Google Bigtable :

       為了能高速讀取及搜尋Peta Bytes級資料而研發出的資料庫架構[5]

Hadoop Hbase :

      Hadoop架構下的資料庫架構,可搭配Hive或Pig[6]

Apache Cassandra :

      由facebook 開發並釋出的open source NoSQL 資料庫架構, Twitter 與Digg 也都採用此架構 [7]

Hypertable :

     也是一個open source 的noSQL database[8]

當然分散式檔案架構也有其致命缺點,其耗用原始資料3倍的空間儲存資料,可謂用空間換取時間,但卻有效的改善了網站的效率及擴充性,更重要的是這樣的架構只要在PC及一般的硬碟上跑就可以,相當經濟

而雲端運算平台的選用,個人看來以Hadoop為首選,但並竟是開放源碼的架構,在安裝及設定上都頗麻煩,目前有商業化套件 Cloudera http://www.cloudera.com/ 可供選用,目前還是免費下載的喔

 

如果對RDBMS及HDFS的效能比較有興趣,可以參考這篇文章,10 Ways To Complement the Enterprise RDBMS Using Hadoop

演化- 雲端服務

 

既然雲端運算的架構如此強大又容易擴充,若將其商業化建立雲端中心共企業或ISV使用,勢必有一定的商機,因此演化出3種營運模式

1. IaaS : 可以視為虛擬主機租用,但由於彈性高,可以根據CPU使用率來計價,可以細到以使用小時來計價,如Amazon EC2.

2. PaaS : 在雲端架構下建立的Platform, 提供ISV來上傳在平台規範下開發的軟體

3. SaaS : 即以前的ASP,但建構在雲端架構下

 

原本以經濟與效率為取向的雲端運算,轉為商用後,變成了雲端資料中心,提共更穩定更省電更高效能的環境,目前還有雲端貨櫃中心(Container Computer)[9][圖一]的產品,以低耗能高密度高校能為訴求,一個貨櫃可以擺放576台Server,販售對象為想建立私有雲應付大量運算的大型企業、醫院、國家組織、研究單位…等,但如果是一般網站經營者,可以思考改租用雲端服務或架設分散式架構來節省營運成本,個人建議先從VMware及Hadoop著手研究吧!!

 

圖一: 可以擺放576台server的貨櫃 圖片來源 : iThome

 

[1]Wiki : http://zh.wikipedia.org/zh-tw/雲端運算

[2]GFS 論文 http://labs.google.com/papers/gfs.html

[3] HDFS http://hadoop.apache.org/hdfs/

[4] Run PC 初探Hadoop開放原始碼平台環境 http://www.runpc.com.tw/content/cloud_content.aspx?id=105318

[5]Bigtable http://labs.google.com/papers/bigtable.html

[6]Hbase http://hbase.apache.org/

[7]Cassandra http://zh.wikipedia.org/zh-tw/Cassandra

[8]HyperTable http://trac.nchc.org.tw/cloud/wiki/HyperTable

[9]雲端貨櫃 http://www.ithome.com.tw/itadm/article.php?c=58652

延伸閱讀

Baseline “How Google work”http://www.baselinemag.com/c/a/Infrastructure/How-Google-Works-1/e

ebiz “10 Ways To Complement the Enterprise RDBMS Using Hadoop”http://www.ebizq.net/blogs/enterprise/2009/09/10_ways_to_complement_the_ente.php