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