作者ledia (下班後才下棋)
看板Cloud
標題Re: [問題] 關於stragglers的Backup task
時間Tue Sep 7 16:19:18 2010
※ 引述《gmoz ( This can't do that. )》之銘言：
: 這幾天在對MapReduce做一些survey
: 不過有個地方我不太了解細節 o.o
: 就是google用來解決starggles的Backup Task
: 原文如下：
: We have a general mechanism to alleviate the problem
: of stragglers. When a MapReduce operation is close
: to completion, the master schedules backup executions
: of the remaining in-progress tasks. The task is marked
: as completed whenever either the primary or the backup
: execution completes.
: 請問有人知道這個實際運作的細節
: 或是哪邊有資料可以看嗎?
這要先了解到 Google 很多機器都是用便宜的硬體所組成
因此經驗告訴我們, 如果某個 node 如果執行太久, 可能是因為他的硬體出問題
無論是原本 computation 能力就比其他機器低階
或者是硬碟快升天了, 卡卡讓 I/O 變得特別慢
或者 RAM 偵測不到了, node 以為記憶體不夠讓 task 很開心的開始 swap
為了不要讓動作特別慢的機器拖累整個效能
當有一定比例的 task 都做完之後
MapReduce 機制會再把還沒算好的 task 重複發包給先算好的 node
(因為他們先算好, 是好學生, 能者多勞)
一般來說 redundant task 用意有二
1. 讓這種拖累大家進度的 node 不會有太大的影響
2. 如果有硬體有問題, 很可能算回來的資料也不一定對
如果沒辦法單獨 verify 時, 可以用來互相對答案
至於機器死掉只是其中的特例
這個做法的精神並不一定要知道 node 是不是死掉了
畢竟就算 node 沒死, 也是很有可能用掉幾倍的時間
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.49
※ 編輯: ledia 來自: 140.112.30.49 (09/07 16:27)
1F：推 gmoz:感謝:) 09/07 16:58
2F：→ yauhh:出處在哪? 09/07 20:10
3F：→ yauhh:你跳出來說他們做的仍然慢,但卻沒有相對快的方案,有何意義? 09/07 20:20
4F：→ hilorrk:y大的意思是@@? l大說的這些在MapReduce paper裡都有解釋 09/07 20:49
5F：→ hilorrk:吧..而且不太懂您第二句話是質疑哪一點||? 09/07 20:50
6F：→ yauhh:因為這些都是用想出來的不是嗎? 根本沒有很明確知道node的性 09/07 21:10
7F：→ yauhh:質是如何,就一定要說這種計算一定有這種狀況.那這話聽聽就好 09/07 21:10
8F：→ yauhh:等哪位真的有在用的,有明確的經驗分享,再聽聽看有沒有道理. 09/07 21:11
9F：→ yauhh:像第二點說"很可能算回來的資料也不一定對",要講為什麼他也 09/07 21:12
10F：→ yauhh:不見得講得出所以然. 09/07 21:13
11F：→ yauhh:程式你自己寫的,放出去算卻擔心不一定對?? 當做是Java2K嗎? 09/07 21:13
12F：→ yauhh:hilorrk我想你指的是他第一段,paper有解釋. 但我吐槽的是第 09/07 21:25
13F：→ yauhh:二段之後的部份,看起來是自己延伸出來的. 09/07 21:27
14F：→ hilorrk:在redundant storage裡是有verification的機制啦... 09/07 21:42
15F：→ hilorrk:不過在straggler裡的確沒有看到類似的東西@@ 09/07 21:43
16F：→ hilorrk:不過我想l大主要是想說"straggler"不一定是machine crash 09/07 22:12
17F：→ hilorrk:只要是超出預定時間 (其他worker做完的正常時間)都算是 09/07 22:12
18F：→ yauhh:MapReduce並沒有說要把產出資料的複本彼此比對. 加入彼此比 09/07 22:33
19F：→ yauhh:對就變成另一種大量工作,而如此會做不完. 09/07 22:33
20F：→ yauhh:MapReduce也沒有說給straggler定一個預期時間去估喔,他們只 09/07 22:34
21F：→ yauhh:說,送出去結果節點不能工作了,就重送到別的活動節點. 在文章 09/07 22:35
22F：→ yauhh:中,你也看過,並沒有提到對任何指派有個預估的時間. 事實上, 09/07 22:35
23F：→ yauhh:對一份工作開始要預估時,那就麻煩了---這可是親身體驗. 09/07 22:36
24F：→ yauhh:然後,"複本彼此比對"這個延伸概念很荒謬.原典並沒有這樣講, 09/07 22:41
25F：→ yauhh:他自己生出這個有問題的概念,接著因為生出的問題而卡住,又 09/07 22:41
26F：→ yauhh:反過來說是MapReduce的問題. 這種思考過程不對的. 09/07 22:42
27F：→ yauhh:而且至少有二個複本拿出來比對,一比對有差錯,誰是真的?? 09/07 22:53
28F：→ hilorrk:我不是說要去做估計的動作啦 我的意思是straggler是相對於 09/07 22:59
29F：→ hilorrk:在正常時間完成的task 不一定是crash的machine... 09/07 23:00
30F：→ hilorrk:我記得實作的方法是在MapReduce快結束的時候把剩下還沒結 09/07 23:01
31F：→ yauhh:straggler如果不是當機而是其他情況,有何差別? 對主控端來說 09/07 23:01
32F：→ hilorrk:束的task(有可能是straggler的)backup一份到好的worker上 09/07 23:02
33F：→ yauhh:最明確的狀況是發現node當掉了,不管怎樣的情況. 09/07 23:02
34F：→ yauhh:我可以告訴你,你現在說的"未結束的task"backup一份到好的 09/07 23:03
35F：→ hilorrk:原paper有提到一個情形是該worker上有另外一個程式在執行 09/07 23:03
36F：→ yauhh:worker上,不可能. 每一台電腦的行程代號都不一樣. 他們是 09/07 23:03
37F：→ hilorrk:那個程式會關掉catch..所以造成task執行變慢 但基本上 09/07 23:04
38F：→ hilorrk:worker並沒有損壞.. 09/07 23:04
39F：→ yauhh:發現遠端工作不會完成時,把同樣的工作按照spec重新派到好的 09/07 23:04
40F：→ yauhh:node去做. 09/07 23:04
41F：→ yauhh:另外,請舉例說,在遠端電腦好的情況下,你怎麼知道task損壞? 09/07 23:05
42F：→ hilorrk:不太懂耶..task損壞?基本上backup時不知道該task是不是 09/07 23:07
43F：→ hilorrk:straggler 是啟動backup後看原本的和backup哪個先做完吧? 09/07 23:07
44F：→ hilorrk:如果原本的真的是straggler 那backup自然會有加速效果囉 09/07 23:08
45F：→ hilorrk:如果不是那也是損失些計算能力..在cluster裡這不算什麼吧 09/07 23:08
46F：→ ledia:hilorrk 何必多費唇舌, 這好幾年前就一直再用的東西 09/08 15:29
47F：→ ledia:現在問我到底根據再哪, 我也只能指著那些 data center 09/08 15:30
48F：→ ledia:當證據了 囧 09/08 15:30
49F：→ hilorrk:呃..l大也別這麼說嘛 大家討論討論 互補一下不足囉@@ 09/08 18:38
50F：→ hilorrk:我也能從y大那得到一些啟發 瞭解自己理解錯誤的地方啦 09/08 18:39