面向傾斜數(shù)據(jù)的MapReduce連接算法研究.pdf

1、Google提出的MapReduce編程模型已發(fā)展成為最流行的并行計(jì)算框架之一。連接運(yùn)算是數(shù)據(jù)處理中非常重要的一種操作，然而MapReduce框架不能夠很好的支持連接操作，因此MapReduce上連接算法的研究是大數(shù)據(jù)領(lǐng)域一個(gè)重要的內(nèi)容。但是當(dāng)前大部分研究?jī)?nèi)容都是在數(shù)據(jù)均勻分布的情況下進(jìn)行連接算法優(yōu)化，而現(xiàn)實(shí)生活中的數(shù)據(jù)往往是分布不均勻的。MapReduce編程模型在處理傾斜數(shù)據(jù)時(shí)會(huì)導(dǎo)致Reduce任務(wù)的執(zhí)行時(shí)間差距很大，嚴(yán)重降低了資源

2、利用率。
　　基于以上背景，對(duì)于二元等值連接運(yùn)算，本文提出了基于抽樣技術(shù)和數(shù)據(jù)預(yù)劃分的連接算法，首先在MapReduce中通過(guò)蓄水池抽樣方法進(jìn)行并行的快速抽樣，然后根據(jù)樣本空間中數(shù)據(jù)的分布情況計(jì)算連接操作的I/O代價(jià)，并根據(jù)每個(gè)簇的I/O代價(jià)進(jìn)行數(shù)據(jù)劃分，提出簇組合連接算法，核心思想是總是選擇代價(jià)最大的簇并把它分配給當(dāng)前任務(wù)量最小的Reduce節(jié)點(diǎn);針對(duì)嚴(yán)重傾斜的數(shù)據(jù)，提出簇分割組合連接算法，目的是將非常大的簇均分到所有的Redu