VMWare虛擬化叢集建置 科學與計算
3月 03

Google App Engine, MapReduce與資料處理

Web程式設計(PHP,Ajax,PostgreSQL), 高效能及格網運算 Add comments

去年夏天的時候，Google大肆炒熱AppEngine的平台，讓使用者能夠撰寫自己的程式，並且放在Google的雲端計算環境上執行。

Google AppEngine的好處我們都曉得，尤其對於應用的角度來說，無非就是可以讓很多有想法的網路創業族群能夠以極少的成本自行開發軟體並且供人使用。但從學術角度及高效能計算的觀點，Google的運算資源極為龐大，如果只是單拿來跑應用程式，有點可惜。

於是有了這個HTTPMR。

  1. 介紹

    1. Funcitonal Programming
    2. Parallel Data Analysis Language
  2. HTTPMR
  3. 結論


http://code.google.com/p/httpmr/

介紹

我稍後解說一下一個簡單的範例，先簡介一下MapReduce。

如同我在MapReduce是開技術倒車？所提及的一樣：

MapRedurce是一個parallel data processing framework，根據程式設計師撰寫的Mapper/Reducer Function，搭配合併於framework內的checkpoint技術，而進行平行化的資料分析及處理。

MapReduce其實是支撐Google背後一個重要技術之一。儘管他的作法簡單，但loosily couple能夠達成的可能性，也會在群聚之下發會出很驚人的能量。儘管在學術界對於MapReduce的本質所能做到的也有許多論文爭相討論，但絲毫無法改變這個簡單的技術已經爲Google服務了能以想像的計算量。我在今年初的時候終於回到我的老本行，做高效能計算，也因此MapReduce到底發展成怎樣我也是相當關心。我想未來的運算，應該是要大家互相使用彼此的資源才行，而程式設計師也要更能清楚運算對於資訊領域的價值。

Funcitonal Programming

基本上對於Functional Programming的語言來說，任何function應該要被設計成為管線化(或者也可以說是像filter)。上一個function的輸出，要成回下一個function的輸入。相似的語言如同著名的LISP，及在分散式計算裡會看到的erlang，比較不常見的如F#。這些語言都有一個共同的特徵，就是語法本身具有前接後，上接下的特性。

%% quicksort:quicksort(List)
%% Sort a list of items
-module(quicksort). % This is the file 'quicksort.erl'
-export([quicksort/1]). % A function 'quicksort' with 1 parameter is exported (no type, no name)

quicksort([]) -> []; % If the list [] is empty, return an empty list (nothing to sort)
quicksort([Pivot|Rest]) -> % Compose recursively a list with 'Front'
                           % from 'Rest' and 'Back' from 'Rest'
    quicksort([Front || Front <- Rest, Front < Pivot])
    ++ [Pivot] ++
    quicksort([Back || Back <- Rest, Back >= Pivot]).

上面是一個erlang的quicksort程式，可以看見其極精簡化的語法(從第六行開始才是程式的主體，%是註解)，也就是說一個qsort指需要五行。

管線化的設計，在編譯器的背後，會最佳化成較符合CPU跳躍邏輯的程式，也因此我們可以想像functional programming paradigm的程式語言會較有效能上的優勢。

但另一點這也關係到另一種層面，有某些我們常見的工作，與這種管線化的行為非常相似。在資訊領域的其中一個項目，就叫做「資料處理」。這個並不是指一些高中學習資訊的資料處理科，而是如果有大量資料，如何進行平行化的切割，計算，合併，以便讓資訊研究人員可以直接獲取這些大量資料的總結。相關的領域包括DataGrid，或者是生物，物理，化學等需要計算並求解的領域。而Google使用MapReduce很成功地將它建置成一個大量分析網頁的平台，所以初期MapReduce基本上被利用來跑PageRank。但他們很快就發現合併上一些技巧，MapReduce可以搖身一便成為一個資料儲存的平台，也就是BigTable。BigTable就是現在AppEngine使用作為資料儲存的核心技術。

在GDD2008的時候，我親自問過Pete Koomen(AppEngine的PM)，他們要怎樣讓使用者接受Object-based Storage？有沒有類似像SQL的東西？我得到的答案是"We are working on it, but your know it's very hard"。我想，儘管使用者非常難以理解怎樣在AppEngine的DataStore(BigTable)設計好他們的資料結構，並且得到一定的加速，但AppEngine其他的功能依然非常出色。

使用者並不清楚他們所使用的是資料處理領域的觀念，或是object-base database，column- based database，儘管概念封裝了，但如果將使用者導入致錯誤的觀念，只會更讓他們將來難以接受其本質而使用錯誤，那等到系統擴大(scaled up)了，那就會導致難以想像的災難。所以趕快出書吧！AppEngine！好好教育使用者！(好像有個人已經在寫了？)

Parallel Data Analysis Language

另一方面，在資料處理的領域，也同時地有這個問題。相關領域的程式設計師(例如生物)必須去學習平行處理領域的程式設計方式，直到學成後，又得了解系統的瓶頸所在，來增加計算量。那說真的學這些雜七雜八的還真花時間！

也因此Google及Yahoo很久之前就在開始發展Sawzall及Pig，他們都是parallel data process/analysis language。其中當然也包含了functional language的特色，我想這能夠成為新一代的資料庫設計路線。以往資料庫是從簡單的CRUD，直到複雜的T-SQL來進行資料的分析，後來發現不夠用，所以又有了OLAP(或是Data Mining)。在資訊爆炸的時代，這一塊地可以說是有許多做資料庫的大廠必爭之地。我覺得未來很有可能會被這種分散式且高效能的資料分析方式所取代，而這裡就是最欠缺一個好的語言。

HTTPMR

在官方的範例我們可以體驗到MapReduce輕鬆進行字串分析的特性，這個範例最主要把一連串用空白分隔的字串拆開(等於是call .split(" "))，並且使用字串建立起索引
在這一段

PLAIN TEXT
PYTHON:
  1. def Map(self, document_title, document):
  2.   for token in list(set(document.contents.split(" "))):
  3.     if token:
  4.       yield token, document_title

定義了一個Map Function，目的是在拆開字串。
而在這一段，

PLAIN TEXT
PYTHON:
  1. def Reduce(self, token, document_titles):
  2.   yield None, DocumentIndex(token=token,
  3.     document_titles=document_titles)

定義了Reduce Function，目的是在於利用剛剛拆開的字串建立起索引，存回DBStore裡去。
原本還附了一支小程式，讓它看起來有點像是可以在unix shell submit job。
http://code.google.com/p/httpmr/source/browse/trunk/src/construct_document_index.sh
但其實當你deploy到AppEngine後，也就等於隨時可以執行了。

結論

這個HTTPMR工具基本上地實現了MapReduce的可能性；換句話說它把google工程師們本來就在用的功能從內部能還原出來，並且讓大家可以試著去執行看看。

但從高效能計算的角度，這樣還不足以能夠成為一個很好的計算環境。除了改善這個函式庫所提供的功能以外，也必須有更多參考讓科學家們知道怎樣做會比較簡單。

written by Kiwi


Leave a Reply