作者yauhh (哟)
看板Cloud
标题MapReduce (Re: [情报] 利用智慧型手机建构云端
时间Thu Aug 19 04:25:58 2010
※ 引述《hilorrk (Cary)》之铭言：
: 如果对MapReduce不熟 可以查查wikipedia
: 或是看看google这篇paper(比起bigtable、GFS和chubby 它好读多了)
: http://labs.google.com/papers/mapreduce.html
以前看到MapReduce,的确不可否认是很棒的计算组织方式.
借用了函数语言的特色,最棒的就是在把工作拆成几个简单的部份,
让几个简单的工作衔接,而达成原来整个工作的目标.
Map和Reduce二方都很好懂.接着,就会想到,
那worker呢? mater要怎麽将资料妥善分配到每个worker?
以论文第一个例子来看:
takeWord(doc, word):
for each term in doc
if term = word, emit(word, "1")
这是map,只要知道一份文件和一个词,就从文件中抓出词的出现次.
於是,处理map的workder一定要知道要处理哪个文件和哪个词.
问题来了,在文件资料库中有那麽多文件,要找那麽多词,
master应该要先整理许多文件与词的配对:例如,
("doc1", "hello") ("doc1", "world") ("doc2", "foo") ("doc2", "bar") ...
不晓得这方面有没有人有何见解?
我想可能是用map分别取每个档案名和每个词汇,然後用reduce合并成配对.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.160.211.76
1F：推 ledia:如果是 search engine 的话, 一般的 key 是 url or path 08/19 10:10
2F：→ ledia:但是会经过 inverted index 变成 term -> url 08/19 10:11
3F：→ ledia:再 group by term, url 反而变成了 value 08/19 10:11
4F：→ ledia:以这边来说就是 for each $term in $doc, emit($term, $doc) 08/19 10:12
5F：→ ledia:最後会得到 $term -> $doc1 $doc2 ... 08/19 10:12
6F：→ ledia:想要的话也可以 emit($term, ($doc, $offset)) 08/19 10:13
7F：→ ledia:次数比较不重要, 因为可以用最後的 list 算出来的 08/19 10:14
8F：→ yauhh:你说的是map或reduce工作内容中做的事情. 但我问的不是这个. 08/19 14:25
9F：→ yauhh:问的是master分配资源给mapper或reducer的方面. 08/19 14:25
10F：推 ledia:我不知道所谓的分配资源指的是什麽? 08/19 14:32
11F：→ ledia:如果说是分配工作的话, 应该就是先把切好的 task 比如说 url 08/19 14:33
12F：→ ledia:list, 丢给最闲的, 或是想做事的 node 吧 08/19 14:34
13F：推 hilorrk:还有在DFS上的data locality问题...详细实作可能dependant 08/19 15:40
14F：→ hilorrk:on DFS吧? 08/19 15:40
15F：→ hilorrk:不过像是Hadoop替DFS定了一些interface 只要遵循这个规则 08/19 15:44
16F：→ hilorrk:的DFS都能套它的MapReduce 就能用像是KFS取代原有的HDFS 08/19 15:46
17F：→ yauhh:对啊,分配工作就是分配资源. 请想想第一个例子,要给一个文件 08/19 19:41
18F：→ yauhh:和一个词,然後它可以做map. 问题是这个文件跟这个词是谁喂的 08/19 19:41
19F：→ yauhh:Google处理的可是一大堆文件啊,这一大堆文件如果是用回圈 08/19 19:42
20F：→ yauhh:一个一个指派给各个map,基本上还是有大量资料塞车的问题. 08/19 19:43
21F：推 ledia:这个你可能就要去看一些 message queue 的 service 了 08/20 09:53
22F：→ ledia:算是 distributed 环境传递讯息的方式 08/20 09:54
23F：→ ledia:cralwer 也都不只一个, 所以需要一些 MQ server 08/20 09:54
24F：→ gmoz:关於回圈方式已经有解了 也有人实作出来了 08/20 10:06
25F：→ gmoz:阿 误解意思了 我说的回圈和你说的不一样XD 08/20 10:07
26F：→ yauhh:对啊,我指的是map-reduce系统最开端到底要从哪里开始. 08/20 10:48