Google云计算技术MapReduce国外课件.ppt

MapReduce Jobs run in Aug, 2004 * * * * * * * * * * * * MapReduce: Refinements Locality Optimization Leverage GFS to schedule a map task on a machine that contains a replica of the corresponding input data. Thousands of machines read input at local disk speed Without this, rack switches limit read rate MapReduce: Refinements Redundant Execution Slow workers are source of bottleneck, may delay completion time. Near end of phase, spawn backup tasks, one to finish first wins. Effectively utilizes computing power, reducing job completion time by a factor. MapReduce: Refinements  Skipping Bad Records Map/Reduce functions sometimes fail for particular inputs. Fixing the Bug might not be possible : Third Party Libraries. On Error Worker sends signal to Master If multiple error on same record, skip record MapReduce: Refinements  Miscellaneous Combiner Function at Mapper Sorting Guarantees within each reduce partition. Local execution for debugging/testing User-defined counters MapReduce:  Walk through of One more Application MapReduce : PageRank PageRank models the behavior of a “random surfer”. C(t) is the out-degree of t, and (1-d) is a damping factor (random jump) The “random surfer” keeps clicking on successive links at random not taking content into consideration. Distributes its pages rank equally among all pages it links to. The dampening factor takes the surfer “getting bored” and typing arbitrary URL. Computing PageRank PageRank : Key Insights Effect at each iteration is local. i+1th iteration depends only on ith iteration At iteration i, PageRank for individual nodes can be computed independently PageRank using MapReduce Use Sparse matrix representation (M) Map each row of M to a list of PageRank “credit” to assign to out link neighbours. These prestige scores are reduced to a single PageRank value for a page by aggregating over them. PageRank using