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