Hi Todd, I think you have mistaken my meaning. Splitting should achieve two goals: 1. All tasks are balanced 2. The bytes of a task are in the specified range
There are two cases: 1.A single key has too many values 2.Many different keys are hashed to a same partition By analogy we cut a cake, not only every piece is evenly, but also the piece size are in the specified range. There are several advantages: 1.The skew problem is soloved, becase every task is balanced 2. Scheduler can switch jobs by a task, becase the bytes are specified for every task In MR, a task looks like a sleep(N) call and N is not determinated, and M maybe is very larger. In MBR, a task looks like a sleep(M) call and M is determinated, and M is not larger. For lots of applications, a parallel scheduler is necessary based on priority. Exclusive priority is also necessary for emergency. Regards Jian Yi 2010/2/10 Todd Lipcon <[email protected]> > Hi Jian, > > Are you essentially proposing "work stealing"? That is to say, if a map > task > is taking longer than others, another map task will be able to grab some of > its work from it after the job is already under way? > > -Todd > > On Tue, Feb 9, 2010 at 1:23 AM, jian yi <[email protected]> wrote: > > > Just like cutting a cake, we will cut it again if the first is not > > balanced. > > If we can control the size of every task, system will become more simple > > and > > optimizing is possible. > > > > 2010/2/9 jian yi <[email protected]> > > > > > Hi Alan, > > > > > > In my opinion, MBR solves the skew problem with minimum cost. It is > > differ > > > with combiner. My English is poor, but I do my best to express myself > > > clearly. > > > > > > In MBR, we can set the size of a task, both map task and reduce task. > For > > > example, 120~150MB input for a task, the motive is that we can control > a > > > task's run-time to keep the size of every task is almost equal, which > is > > the > > > precondition that a task can be regarded as a timeslice switched. > > > > > > By hashing output of map to more splits, we can regroup smaller splits > to > > a > > > new split which size is specified and hash bigger spits to more small > > > splits, until the size of all splits is within the specified range. > > > > > > Balance interface is like map and reduce interface. Balance interface > > shoud > > > be implemented when a single key has too many values, because the key > > will > > > be hashed to more than one splits. In the case, we can't get the final > > > results in a MBR session, it is necessary to start a next MBR session. > > For a > > > same key, we can hash it with key+value, the action will be telled to > > > balance interface. > > > > > > Regards > > > Jian Yi > > > > > > 2010/2/9 Alan Gates <[email protected]> > > > > > > Jian, > > >> > > >> Sorry if any of my questions or comments would have been answered by > the > > >> diagrams, but apache lists don't allow attachments, so I can't see > your > > >> diagrams. > > >> > > >> If I understand correctly, your suggestion for balancing is to apply > > >> reduce on subsets of the hashed data, and then run reduce again on > this > > >> reduced data set. Is that correct? If so, how does this differ from > > the > > >> combiner? Second, some aggregation operations truly aren't algebraic > > (that > > >> is, they cannot be distributed across multiple iterations of reduce). > > An > > >> example of this is session analysis, where the algorithm truly needs > to > > see > > >> all operations together to analyze the user session. How do you > propose > > to > > >> handle that case? > > >> > > >> Alan. > > >> > > >> > > >> On Feb 7, 2010, at 11:25 PM, jian yi wrote: > > >> > > >> Two targets: > > >>> 1. Solving the skew problem > > >>> 2. Regarding a task as a timeslice to improve on scheduler, switching > a > > >>> job to another job by timeslice. > > >>> > > >>> In MR (Map-Reduce) model, reducings are not balanced, because the > scale > > >>> of partitiones are unbalanced. How to balance? We can control the > size > > of > > >>> partition, rehash the bigger parition and combine to the specified > > size. If > > >>> a key has many values, it's necessary to execute mapreduce twice.The > > >>> following is the model digram: > > >>> > > >>> Scheduler can regard a task as a timeslice similarly OS scheduler. > > >>> If a split is bigger than a specified size, it will be splitted > again. > > If > > >>> a split is smaller than a specified size, it will be combined with > > others, > > >>> we can name the combining procedure regroup. The combining is logic, > > it's > > >>> not necessay to combine these smaller splits to a disk file, which > will > > not > > >>> affect the performance.The target is that every task spent same time > > >>> running. > > >>> > > >>> > > >> > > > > > >
