作者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