基于MapReduce數(shù)據(jù)傾斜的負(fù)載均衡算法研究.pdf

1、MapReduce作為一種分布式編程模型，被廣泛應(yīng)用于大規(guī)模和高維度數(shù)據(jù)集的處理，在海量數(shù)據(jù)處理中顯示出較好的并行性以及擴(kuò)展性。其采用簡(jiǎn)單通用的Hash函數(shù)對(duì)數(shù)據(jù)進(jìn)行劃分，當(dāng)數(shù)據(jù)分布不均勻時(shí)，常會(huì)出現(xiàn)數(shù)據(jù)傾斜的問題。現(xiàn)有的解決數(shù)據(jù)傾斜方法多是增添一輪采樣操作，確定key值頻率再重新執(zhí)行數(shù)據(jù)分區(qū)。但是增加的采樣作業(yè)會(huì)延遲原作業(yè)的運(yùn)行，例如基于MapReduce實(shí)現(xiàn)的并行聚類算法需要進(jìn)行多次迭代運(yùn)算，且對(duì)于各輪計(jì)算，reducer的數(shù)據(jù)分布

2、情況不盡相同，現(xiàn)有的方法將增加多輪采樣作業(yè)。
　　針對(duì)該問題，本文提出一種動(dòng)態(tài)分區(qū)策略，當(dāng)發(fā)生數(shù)據(jù)傾斜時(shí)，更改剩余數(shù)據(jù)分區(qū)函數(shù)以解決數(shù)據(jù)劃分的不均衡。
　　首先，在Map運(yùn)行過程中增加計(jì)數(shù)器，統(tǒng)計(jì)經(jīng)Hash法分到各reducer的數(shù)據(jù)量或記錄數(shù)，并將這些消息通過心跳機(jī)制發(fā)送到JobTrackcr;
　　然后，JobTrackcr根據(jù)全局的分區(qū)信息建立數(shù)據(jù)傾斜模型，得出各reducer負(fù)載情況用以判斷存在數(shù)據(jù)傾斜的red

3、ucer;
　　最后，JobTrackcr計(jì)算傾斜reducer與負(fù)載較輕reducer的hash差值，即分區(qū)偏移值，并將它發(fā)送到Partitioner用來在分區(qū)過程中動(dòng)態(tài)修改原分區(qū)函數(shù)。該函數(shù)中剩余分區(qū)的hash結(jié)果將加上其對(duì)應(yīng)的偏移值，傾斜數(shù)據(jù)就會(huì)發(fā)送到負(fù)載較輕的reducer上處理，使各節(jié)點(diǎn)的負(fù)載達(dá)到均衡。
　　此外，本文考慮集群中節(jié)點(diǎn)的軟硬件異構(gòu)性，在數(shù)據(jù)傾斜模型中加入各reducer性能參數(shù)，使本文方法在異構(gòu)的集群