Re: [閒聊] 雲端運算的應用

[tinlans ( )]

※ 引述《azai2008 (阿宅)》之銘言：
: 剛剛去逛了一下比賽的部落格
: 發現裡面有更新一個實作範例，是利用Apache hadoop進行google的mapreduce
: 這樣就可以把程式進行切割，在丟到每台電腦進行運算
: 還蠻有趣的範例
: 跟之前把資料丟到大型主機進行運算的方式完全相反~
: http://www.wretch.cc/blog/trendnop09/21085442

這個之前有玩過了，
不過它對 Java 的支援比較完善，
C++ 雖然有 API 但是一堆 Java 能用的 C++ 都沒得用，
譬如存取 HDFS 的部分都沒有文件，
只有內部隱藏的 API，
你想直接用 fopen() 或 ifstream 讀檔是讀不到東西的；
最重要的是它的 HDFS 慢到炸掉，
可是 process 之間並沒有類似 IPC 的東西，
如果你想讓 process 之間能互傳資料，
目前除了寫進慢到不行的 HDFS 裡再讀出來外沒有其它方法。

還有程式運算本身的性質是否適合 MapReduce 也很重要，
一般來說 map 的 process 數跟你寫入 input path 的檔案數量一致，
input file 的格式是 key/value values，
產生 input file 的方法可以用純文字檔，
或是它們提供的 SequenceFile.Writer，
它的運算結果也是 key/value pairs，
map class 會被呼叫到的 method 大概就長這樣：
public void map(InputKeyType key,
                InputValueType value,
                OutputCollector<OutputKeyType, OutputValueType> out,
                Reporter reporter) throws IOException
{
        ...
        out.collect(new OutputKeyType(...), new OutputValueType(...));
}
這是被動呼叫的 method，
你用來當作 input 的檔案會被分解成很多 key/value pairs，
然後一組一組的被傳進來跑你自訂的 code，
key 和 value 的 types 可以自己決定
(非基礎型別的話會比較複雜要用它們的 serialization 模型自己定義一份)，
input 和 output 的 key/value types 可以不同；
reduce 就像是把分散出去算的東西合併收集起來 (通常 task 數遠少於 map)，
有相同 key 的 values 會被 reduce task 併成一項，
比方說不同的 map tasks 丟出來的結果有 ("a", 1), ("a", 2), ("a", 3)
你可以設計 reduce task 把它們的 value 用加法合併成 ("a", 6)，
reduce class 被呼叫到的 method 大概長這樣：
public void reduce(InputKeyType key,
                   Iterator<InputValueType> values,
                   OutputCollector<OutputKeyType, OutputValueType> out,
                   Reporter reporter) throws IOException
{
        while(values.hasNext()) {
                ...
        }

        out.collect(new OutputKeyType(...), new OutputValueType(...));
}
看參數列應該就知道，
當資料傳進 reduce tasks 時，
背後已經有一個機制把具相同 key 的 values 收集起來了，
要單純把 values 加起來就是在上面的 while loop 寫個累加運算，
reduce tasks 輸出的 key/value pairs 會變成檔案存在 HDFS，
檔案的數量跟 reduce tasks 的數量一樣多，
要 parse 它們的話用它們提供的 SequenceFile.Reader 就可以了。

簡單來說這是沒有 global variable 的世界，
process 之間傳遞資料完全靠傳 function arguments 溝通
(僅限於 map 對 reduce，像 map 跟 map 之間只能靠讀寫 HDFS)，
arguments 的形式只能是 key/value pairs，
如果這樣無法滿足你的需求或是你想不到如何把程式模型轉成這樣
(轉換的方式通常是以完全不同角度思考，常讓人跌破眼鏡)，
一定要用到全域資料的話，
你寫出來的程式一定是用 100 台運算比用 1 台算還慢 100 倍以上，
因為全域資料只能透過讀寫 HDFS 來進行，
這種東西的 I/O 速度是用秒來當單位的，
人多的時候可能還要用分鐘當單位。

被拿來當範例用的 word count 剛好就適合這種設計模式，
搜尋引擎大部分的 algorithm 也是跟這種模式相契合，
但是否世界上所有的問題都適合以這種模式實作，
我個人覺得答案是否定的，
雖然一直看到很多人在推這東西，
不過實際上寫過用過就會發現沒有那麼好。

雖然講是這樣講，
不過應用範圍也沒想像中的窄就是了，
只是看範例學這東西很容易產生一種誤解，
就是把 reduce tasks 當成收破爛的阿嬤，
以為它單純只是被拿來收集和彙整結果用的東西，
結果把所有工作都設計成由 map tasks 處理
(這種問題的典型案例就是 reduce task 數永遠只有 1)；
其實 reduce tasks 可以跟 map tasks 同時進行，
要是沒辦法善用 reduce tasks 的話，
你程式的 critical path 就很難再縮短，
光是想到把運算責任全部塞在 map task 上，
結果跑出來的效能很爛的話，
先怪 MapReduce 的模型不適合也是有問題的。

--
Ling-hua Tseng ([email protected])
Department of Computer Science, National Tsing-Hua University
Interesting: C++, Compiler, PL/PD, OS, VM, Large-scale software design
Researching: Software pipelining for VLIW architectures
Homepage: https://www.tinlans.org

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.160.104.178
※ 編輯: tinlans         來自: 118.160.104.178      (04/12 03:54)
推 HARKER:哇塞 是高手耶@@ 推一下
推 csdcbiz:MR本質上就是data parallelism 這是非戰之罪吧
→ csdcbiz:其實Mapper的input跟Reducer的output format都沒限制
→ csdcbiz:只有intermediate的時候需要是key-value pair
→ csdcbiz:例如XML也是支援的mapper input format