MapReduce中連接優(yōu)化研究.pdf

1、數(shù)據(jù)分析和處理是大規(guī)模分布式數(shù)據(jù)處理應(yīng)用中的重要任務(wù)。由于簡(jiǎn)單易用和具有靈活性，MapReduce編程模型逐漸成為大規(guī)模分布式數(shù)據(jù)處理系統(tǒng)（如Hadoop系統(tǒng)）的核心模型。由于MapReduce編程模型本身偏重于集群的可擴(kuò)展性和靈活性，使得MapReduce在處理連接問題時(shí)存在兩方面問題：一方面MapReduce編程模型實(shí)現(xiàn)基本的二路等值連接，其處理思路：在mapreduce作業(yè)的數(shù)據(jù)分割階段,基于連接key值哈希分割，將key值相同的

2、數(shù)據(jù)傳送到同一個(gè)reduce節(jié)點(diǎn)，然后各個(gè)reduce節(jié)點(diǎn)對(duì)數(shù)據(jù)源不同、key值相同的數(shù)據(jù)執(zhí)行連接操作，在處理多路連接時(shí)，MapReduce編程模型最簡(jiǎn)單的實(shí)現(xiàn)機(jī)制是通過連續(xù)的mapreduce二路連接作業(yè)隊(duì)列順序處理。這一處理過程中存在大量的數(shù)據(jù)重復(fù)讀入讀出，I/O代價(jià)非常大，連接處理效率低；另一方面由于MapReduce編程模型在數(shù)據(jù)分割階段使用基于key值哈希分割的分割方式，而進(jìn)行連接的數(shù)據(jù)集中數(shù)據(jù)key值可能不是均勻分布，Map

3、Reduce編程模型在處理連接操作時(shí)，會(huì)出現(xiàn)數(shù)據(jù)傾斜問題，當(dāng)數(shù)據(jù)傾斜度非常大時(shí)，數(shù)據(jù)傾斜問題嚴(yán)重降低MapReduce執(zhí)行連接操作的效率。
　　本文對(duì)MapReduce中連接負(fù)載均衡、多路非等值連接優(yōu)化等一系列問題進(jìn)行了研究，主要研究?jī)?nèi)容如下。
　　針對(duì)MapReduce中連接操作的數(shù)據(jù)傾斜問題，分析了形成MapReduce連接性能瓶頸的原因并建立負(fù)載均衡代價(jià)模型，提出了用范圍分割（Greedyrangepartitione

4、r）貪心算法控制連接過程中的數(shù)據(jù)傾斜問題實(shí)現(xiàn)負(fù)載均衡的策略。
　　在此基礎(chǔ)上，針對(duì)MapReduce中的多路非等值連接問題，分析了形成MapReduce多路連接性能瓶頸的原因，提出了利用建立多維空間模型來實(shí)現(xiàn)在單個(gè) mapreduce處理任務(wù)中完成多路任意連接的方法，并用范圍分割（Greedyrangepartitioner）貪心算法和抽樣范圍分割（Samplerangepartitioner）來控制多路連接過程中的數(shù)據(jù)傾斜問題。