mapreduce中連接優(yōu)化研究

1、學(xué)校代碼：10255學(xué)號：2121532碩士研究生學(xué)位論文碩士研究生學(xué)位論文MapReduce中連接優(yōu)化研究TTTTheheheheoptimizationoptimizationoptimizationoptimizationofofofofjoinjoinjoinjoinininininMapReduceMapReduceMapReduceMapReduce學(xué)科專業(yè)：軟件工程學(xué)科專業(yè)：軟件工程學(xué)號：學(xué)號：21215322121532

2、21215322121532作者作者::::翟紅敏翟紅敏指導(dǎo)教師：指導(dǎo)教師：劉國華劉國華萬方數(shù)據(jù)IMapReduce中連接優(yōu)化研究摘要數(shù)據(jù)分析和處理是大規(guī)模分布式數(shù)據(jù)處理應(yīng)用中的重要任務(wù)。由于簡單易用和具有靈活性，MapReduce編程模型逐漸成為大規(guī)模分布式數(shù)據(jù)處理系統(tǒng)（如Hadoop系統(tǒng)）的核心模型。由于MapReduce編程模型本身偏重于集群的可擴展性和靈活性，使得MapReduce在處理連接問題時存在兩方面問題：一方面MapRe

3、duce編程模型實現(xiàn)基本的二路等值連接，其處理思路：在mapreduce作業(yè)的數(shù)據(jù)分割階段基于連接key值哈希分割，將key值相同的數(shù)據(jù)傳送到同一個reduce節(jié)點，然后各個reduce節(jié)點對數(shù)據(jù)源不同、key值相同的數(shù)據(jù)執(zhí)行連接操作，在處理多路連接時，MapReduce編程模型最簡單的實現(xiàn)機制是通過連續(xù)的mapreduce二路連接作業(yè)隊列順序處理。這一處理過程中存在大量的數(shù)據(jù)重復(fù)讀入讀出，IO代價非常大，連接處理效率低；另一方面由于M

4、apReduce編程模型在數(shù)據(jù)分割階段使用基于key值哈希分割的分割方式，而進(jìn)行連接的數(shù)據(jù)集中數(shù)據(jù)key值可能不是均勻分布，MapReduce編程模型在處理連接操作時，會出現(xiàn)數(shù)據(jù)傾斜問題，當(dāng)數(shù)據(jù)傾斜度非常大時，數(shù)據(jù)傾斜問題嚴(yán)重降低MapReduce執(zhí)行連接操作的效率。本文對MapReduce中連接負(fù)載均衡、多路非等值連接優(yōu)化等一系列問題進(jìn)行了研究，主要研究內(nèi)容如下。針對MapReduce中連接操作的數(shù)據(jù)傾斜問題，分析了形成MapRedu

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