PTT數位生活區 / Cloud

Re: [問題] 關於stragglers的Backup task

看板Cloud作者 (下班後才下棋)時間13年前 (2010/09/07 16:19), 編輯推噓1(1推 0噓 49→)
留言50則, 4人參與, 最新討論串3/3 (看更多)
※ 引述《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)
推
09/07 16:58, , 1F
感謝:)
09/07 16:58, 1F
→
09/07 20:10, , 2F
出處在哪?
09/07 20:10, 2F
→
09/07 20:20, , 3F
你跳出來說他們做的仍然慢,但卻沒有相對快的方案,有何意義?
09/07 20:20, 3F
→
09/07 20:49, , 4F
y大的意思是@@?　l大說的這些在MapReduce paper裡都有解釋
09/07 20:49, 4F
→
09/07 20:50, , 5F
吧..而且不太懂您第二句話是質疑哪一點||?
09/07 20:50, 5F
→
09/07 21:10, , 6F
因為這些都是用想出來的不是嗎? 根本沒有很明確知道node的性
09/07 21:10, 6F
→
09/07 21:10, , 7F
質是如何,就一定要說這種計算一定有這種狀況.那這話聽聽就好
09/07 21:10, 7F
→
09/07 21:11, , 8F
等哪位真的有在用的,有明確的經驗分享,再聽聽看有沒有道理.
09/07 21:11, 8F
→
09/07 21:12, , 9F
像第二點說"很可能算回來的資料也不一定對",要講為什麼他也
09/07 21:12, 9F
→
09/07 21:13, , 10F
不見得講得出所以然.
09/07 21:13, 10F
→
09/07 21:13, , 11F
程式你自己寫的,放出去算卻擔心不一定對?? 當做是Java2K嗎?
09/07 21:13, 11F
→
09/07 21:25, , 12F
hilorrk我想你指的是他第一段,paper有解釋. 但我吐槽的是第
09/07 21:25, 12F
→
09/07 21:27, , 13F
二段之後的部份,看起來是自己延伸出來的.
09/07 21:27, 13F
→
09/07 21:42, , 14F
在redundant storage裡是有verification的機制啦...
09/07 21:42, 14F
→
09/07 21:43, , 15F
不過在straggler裡的確沒有看到類似的東西@@
09/07 21:43, 15F
→
09/07 22:12, , 16F
不過我想l大主要是想說"straggler"不一定是machine crash
09/07 22:12, 16F
→
09/07 22:12, , 17F
只要是超出預定時間 (其他worker做完的正常時間)都算是
09/07 22:12, 17F
→
09/07 22:33, , 18F
MapReduce並沒有說要把產出資料的複本彼此比對. 加入彼此比
09/07 22:33, 18F
→
09/07 22:33, , 19F
對就變成另一種大量工作,而如此會做不完.
09/07 22:33, 19F
→
09/07 22:34, , 20F
MapReduce也沒有說給straggler定一個預期時間去估喔,他們只
09/07 22:34, 20F
→
09/07 22:35, , 21F
說,送出去結果節點不能工作了,就重送到別的活動節點. 在文章
09/07 22:35, 21F
→
09/07 22:35, , 22F
中,你也看過,並沒有提到對任何指派有個預估的時間. 事實上,
09/07 22:35, 22F
→
09/07 22:36, , 23F
對一份工作開始要預估時,那就麻煩了---這可是親身體驗.
09/07 22:36, 23F
→
09/07 22:41, , 24F
然後,"複本彼此比對"這個延伸概念很荒謬.原典並沒有這樣講,
09/07 22:41, 24F
→
09/07 22:41, , 25F
他自己生出這個有問題的概念,接著因為生出的問題而卡住,又
09/07 22:41, 25F
→
09/07 22:42, , 26F
反過來說是MapReduce的問題. 這種思考過程不對的.
09/07 22:42, 26F
→
09/07 22:53, , 27F
而且至少有二個複本拿出來比對,一比對有差錯,誰是真的??
09/07 22:53, 27F
→
09/07 22:59, , 28F
我不是說要去做估計的動作啦 我的意思是straggler是相對於
09/07 22:59, 28F
→
09/07 23:00, , 29F
在正常時間完成的task 不一定是crash的machine...
09/07 23:00, 29F
→
09/07 23:01, , 30F
我記得實作的方法是在MapReduce快結束的時候把剩下還沒結
09/07 23:01, 30F
→
09/07 23:01, , 31F
straggler如果不是當機而是其他情況,有何差別? 對主控端來說
09/07 23:01, 31F
→
09/07 23:02, , 32F
束的task(有可能是straggler的)backup一份到好的worker上
09/07 23:02, 32F
→
09/07 23:02, , 33F
最明確的狀況是發現node當掉了,不管怎樣的情況.
09/07 23:02, 33F
→
09/07 23:03, , 34F
我可以告訴你,你現在說的"未結束的task"backup一份到好的
09/07 23:03, 34F
→
09/07 23:03, , 35F
原paper有提到一個情形是該worker上有另外一個程式在執行
09/07 23:03, 35F
→
09/07 23:03, , 36F
worker上,不可能. 每一台電腦的行程代號都不一樣. 他們是
09/07 23:03, 36F
→
09/07 23:04, , 37F
那個程式會關掉catch..所以造成task執行變慢 但基本上
09/07 23:04, 37F
→
09/07 23:04, , 38F
worker並沒有損壞..
09/07 23:04, 38F
→
09/07 23:04, , 39F
發現遠端工作不會完成時,把同樣的工作按照spec重新派到好的
09/07 23:04, 39F
→
09/07 23:04, , 40F
node去做.
09/07 23:04, 40F
→
09/07 23:05, , 41F
另外,請舉例說,在遠端電腦好的情況下,你怎麼知道task損壞?
09/07 23:05, 41F
→
09/07 23:07, , 42F
不太懂耶..task損壞?基本上backup時不知道該task是不是
09/07 23:07, 42F
→
09/07 23:07, , 43F
straggler 是啟動backup後看原本的和backup哪個先做完吧?
09/07 23:07, 43F
→
09/07 23:08, , 44F
如果原本的真的是straggler 那backup自然會有加速效果囉
09/07 23:08, 44F
→
09/07 23:08, , 45F
如果不是那也是損失些計算能力..在cluster裡這不算什麼吧
09/07 23:08, 45F
→
09/08 15:29, , 46F
hilorrk 何必多費唇舌, 這好幾年前就一直再用的東西
09/08 15:29, 46F
→
09/08 15:30, , 47F
現在問我到底根據再哪, 我也只能指著那些 data center
09/08 15:30, 47F
→
09/08 15:30, , 48F
當證據了 囧
09/08 15:30, 48F
→
09/08 18:38, , 49F
呃..l大也別這麼說嘛　大家討論討論　互補一下不足囉@@
09/08 18:38, 49F
→
09/08 18:39, , 50F
我也能從y大那得到一些啟發　瞭解自己理解錯誤的地方啦
09/08 18:39, 50F
‣ 更多 ledia 的文章
文章代碼(AID): #1CXVM82x (Cloud)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 3 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共3篇)
Cloud 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 ledia 的文章
文章代碼(AID): #1CXVM82x (Cloud)