SALA：一種避免傾斜、位置感知的基于MapReduce的連接算法.pdf

1、MapReduce是由Google提出的并行計(jì)算框架，具備高可擴(kuò)展性、高可用性和良好的容錯(cuò)性，現(xiàn)已廣泛應(yīng)用于處理大規(guī)模數(shù)據(jù)。連接操作是大數(shù)據(jù)分析中的一個(gè)常見(jiàn)運(yùn)算，隨著數(shù)據(jù)規(guī)模的進(jìn)一步增大，如何有效處理基于MapReduce的連接操作成為學(xué)術(shù)界與工業(yè)界的一個(gè)研究熱點(diǎn)。
　　然而，傳統(tǒng)的基于MapReduce的連接算法在處理傾斜數(shù)據(jù)時(shí)效率不高，主要存在兩個(gè)問(wèn)題:(1)傳統(tǒng)算法采用的哈希分區(qū)模式在劃分?jǐn)?shù)據(jù)時(shí)容易發(fā)生分區(qū)傾斜，從而導(dǎo)致負(fù)載

2、不均，最終延長(zhǎng)了整個(gè)連接操作的完成時(shí)間;(2)連接操作在Map階段產(chǎn)生了大量中間結(jié)果，傳統(tǒng)算法沒(méi)有考慮數(shù)據(jù)局部性，因此需要消耗較多時(shí)間在網(wǎng)絡(luò)中傳輸中間結(jié)果。傳統(tǒng)的基于MapReduce的連接算法如重分區(qū)連接算法、復(fù)制連接算法都沒(méi)有考慮負(fù)載均衡與網(wǎng)絡(luò)傳輸代價(jià)問(wèn)題，因此無(wú)法獲得較好的整體性能。
　　本文提出了一種新穎的基于MapReduce的連接算法——SALA連接算法，該算法采用VLA分區(qū)模式替代傳統(tǒng)的哈希分區(qū)模式，在處理傾斜數(shù)據(jù)時(shí)

3、不僅能保證負(fù)載均衡，也能有效減少網(wǎng)絡(luò)傳輸代價(jià)。與其他現(xiàn)有的基于MapReduce的連接算法相比，SALA連接算法具有如下優(yōu)勢(shì):(1)確保數(shù)據(jù)能均勻地劃分到各個(gè)Reduce工作節(jié)點(diǎn)中，即使輸入數(shù)據(jù)集是傾斜的;(2)充分利用數(shù)據(jù)局部性，大大減少需要經(jīng)過(guò)網(wǎng)絡(luò)進(jìn)行傳輸?shù)闹虚g結(jié)果數(shù)據(jù)量;(3)不需要對(duì)MapReduce框架進(jìn)行修改，實(shí)現(xiàn)容易。本文對(duì)SALA連接算法進(jìn)行了大量實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，SALA連接算法不僅能達(dá)到更好的負(fù)載平衡，且有效減少了