作者yauhh (喲)
看板Cloud
標題Re: [情報] 利用智慧型手機建構雲端
時間Mon Aug 23 11:31:08 2010
※ 引述《hilorrk (Cary)》之銘言：
: 不才第一次接觸到這種新穎的概念還是覺得挺特別的
: 也感慨自己對MapReduce的瞭解仍不夠深
: 不該把它局限在語言模式、multi-core、cluster
: 其實在雲端的領域中 仍有許多發揮想像力的空間!
: 消息來自MIT Tech. Review
: http://www.technologyreview.com/blog/mimssbits/25609/
: Misco網站
: http://www.cs.ucr.edu/~jdou/misco/
: 相關paper
: http://portal.acm.org/citation.cfm?id=1839294.1839332
: 如果對MapReduce不熟 可以查查wikipedia
: 或是看看google這篇paper(比起bigtable、GFS和chubby 它好讀多了)
: http://labs.google.com/papers/mapreduce.html
關於MapReduce,看了一篇用communicating sequential processes討論的文章,蠻好.
"Analyzing MapReduce with CSP"
http://www.iist.unu.edu/www/docs/techreports/reports/report421.pdf#page=95
裡頭主要用有名的C.A.R. Hoare给的語言來討論這個分散式計算架構.
可以看到一些式子,像
SYSTEM ::= MASTER || MAPPER || REDUCER || FS
表達系統為MASTER,MAPPER,REDUCER和FS(File system)平行計算組成.
然後,像MAPPER是
MAPPER ::=||_t Mapper_t, t in T
表示MAPPER是由幾個處理map工作的Mapper_t的集合.
須注意Map-Reduce分為幾個角色:
master, mapper, map task, reducer, reduce task, file system.
而mapper, reducer都是一個類別要分出好多instance的,
而不是一個單位就搞定.
然後,文章對訊息也有定義,像
Message ::= R
#FileName#ChunkIndex
是Master發送給Mapper的訊息,
包含R是Reducer的數目,FileName檔名,和ChunkIndex區塊編號.
一個Mapper除了要知道map task之外,還要知道它要讀哪個檔案,
然後要知道工作做完之後要將結果分解為R個部份,才能分送到R個Reducer.
Mapper的計算主體說是
cal(InputData) ::=
map(InputData); sort({<key,value>_n}); combine({<key,value>_n});
partition({<key,V>_n'}).
map(InputData) = {<key,value>_n}
sort({<key,value>_n}) = {<key',value'>_n}
combine({<key',value'>_n}) = {<key',V>_n'}
partition({<key',V}_n'}) = {Split_k}, k in R
主要是表達map task的進行是先map,把一堆key-value丟出來.
然後要排序(?),grouping (即combine),然後分割成 R 個部份.
這裡包含了map計算之後的輸出資料是local store的要點.
不過,在這邊我覺得應該可以不要做排序. 因為輸出資料分割成R段之後
分送到R個Reducer,每個Reducer應該是從T個Mapper得到各自分別排序好的資料段落.
T個資料段落雖然分別排序好,但是整體來看是沒排序的.
倒不如別排,就直接多個Grouper角色,用filter方式將資料整理成一群一群的.
在這裡可能有個題目,可以談一下(combine.sort)或是直接filter,哪個是較省事的方法.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 211.21.94.199