【摘要】：MapReduce分布式計算框架有助于提升大規(guī)模數(shù)據(jù)連接查詢的效率,但當連接屬性分布不均勻時,其簡單的散列策略容易導致計算節(jié)點間負載不均衡,影響作業(yè)的整體性能。針對連接查詢操作中的數(shù)據(jù)傾斜問題,研究了MapReduce框架下大規(guī)模數(shù)據(jù)連接查詢操作的優(yōu)化算法。首先對經(jīng)典的改進重分區(qū)連接查詢算法進行實驗分析,研究了傳統(tǒng)MapReduce計算框架下連接查詢操作的執(zhí)行流程,找出了基于MapReduce計算框架的連接查詢算法在數(shù)據(jù)分布不均勻時的性能瓶頸;進而提出了組合分割平衡分區(qū)優(yōu)化策略,設計并實現(xiàn)了基于組合分割平衡分區(qū)優(yōu)化策略的改進型連接查詢算法。實驗結(jié)果表明,提出的優(yōu)化策略在大規(guī)模數(shù)據(jù)的連接查詢處理上很好地解決了數(shù)據(jù)傾斜帶來的性能影響,具有好的時間性能和可擴展性。
文內(nèi)圖片：
圖片說明： 耗，使得它被廣泛地應用于大規(guī)模數(shù)據(jù)分析中。在Map階段完成對連接屬性的解析和標記，以HashPartition為核心完成Shuffle過程，在Reduce階段完成連接操作。圖1給出了IRJQ算法的計算框架和執(zhí)行流程。IRJQ算法的運行過程主要分為Map、Shuffle和Reduce共3個階段。其中Map階段完成兩表的連接屬性的解析和標記操作，以及查詢屬性的解析；Shuffle階段負責相同hash值分組從Map端到Reduce端的傳遞；Reduce階段則將來自不同表的連接屬性和查詢值進行連接。Fig.1ComputationframeworkandimplementationprocessofIRJQalgorithm圖1IRJQ算法的計算框架和執(zhí)行流程755
文內(nèi)圖片：
圖片說明： JournalofFrontiersofComputerScienceandTechnology計算機科學與探索2017,11(5)20億、30億、40億、50億、60億、70億和80億，傾斜率分別取0.2、0.5和0.8。實驗結(jié)果如圖2所示。實驗結(jié)果表明，ORDERS中的連接屬性不均勻分布對IRJQ算法時間性能影響較大，隨著ORDERS中的數(shù)據(jù)量及傾斜率增大，其時間性能大幅度下降。這主要是因為傳統(tǒng)MapReduce框架為了保證所有的分區(qū)有相同數(shù)目的分組，以哈希分區(qū)策略完成對分組的劃分。假設ORDERS共有m條記錄，傾斜率為α，且傾斜分組數(shù)目為1；CUSTOMER共有n條記錄，連接率為β；Reduce階段共有k個分區(qū)。則每個分區(qū)的分組數(shù)目為n×βk，傾斜分組中的記錄數(shù)目為m×α，非傾斜分組中的記錄數(shù)目約為m×(1-α)n×β-1，傾斜分區(qū)中的記錄數(shù)目約為m×α+m×(1-α)n×β-1×è÷n×βk-1，，非傾斜分區(qū)中的記錄數(shù)目約為m×(1-α)n×β-1×n×βk，傾斜分區(qū)與非傾斜分區(qū)間的記錄數(shù)目差約為m×α+m×(1-α)n×β-1×è÷nβk-1-m×(1-α)n×β-1×n×βk=m×(n×α×β-1)n×β-1�？梢院芮宄乜闯�，隨著ORDERS中記錄數(shù)目m或者傾斜率α的增加，傾斜分組的記錄數(shù)目m×α變得越來越大，傾斜分組和非傾斜分組間的數(shù)據(jù)量差m×(n×α×β-1)n×β-1也會越來越大。當α→1或者m→∞時，limm→∞m×(n×α×β-1)n×β-1→∞，即ORDERS中數(shù)據(jù)分布嚴重不均勻或者數(shù)據(jù)量較大會導致多個分區(qū)間的數(shù)據(jù)量相差巨大，造成Reduce階段負載嚴重不均衡，最終影響整個作業(yè)的時間性能。4.2基于改進型MapReduce連接查詢算法IRJQ算法在數(shù)據(jù)分布均勻的情況下?lián)碛休^好的時間性能和穩(wěn)定性，然而?
【作者單位】： 桂林電子科技大學廣西可信軟件重點實驗室;桂林電子科技大學廣西云計算與大數(shù)據(jù)協(xié)同創(chuàng)新中心;桂林電子科技大學廣西自動檢測技術與儀器重點實驗室;
【基金】：國家自然科學基金Nos.U1501252,61363005,61462017 廣西自然科學基金Nos.2014GXNSFAA118353,2014GXNSFAA118390,2014GXNSFDA118036 廣西高等學校高水平創(chuàng)新團隊及卓越學者計劃 廣西云計算與大數(shù)據(jù)協(xié)同創(chuàng)新中心基金項目 廣西物聯(lián)網(wǎng)技術與產(chǎn)業(yè)化推進協(xié)同創(chuàng)新中心資助項目~~
【分類號】：TP311.13

【相似文獻】

相關期刊論文 前10條

1 徐帆;匯總型多表連接查詢的一種優(yōu)化方法[J];計算機工程與設計;2002年10期

2 張雷;唐桂芬;蘇冉冉;;基于通用空間連接圖的適應性多元空間連接查詢[J];計算機光盤軟件與應用;2013年13期

3 彭建平,王變琴;再探多連接查詢優(yōu)化方法[J];中山大學學報(自然科學版);2001年02期

4 劉宇,孫莉,田永青;并行空間連接查詢處理[J];上海交通大學學報;2002年04期

5 王果,徐仁佐;結(jié)合哈希過濾的一種改進多連接查詢優(yōu)化算法[J];計算機工程;2004年07期

6 陳恕勝;劉衛(wèi)東;;基于圖的適應性多連接查詢優(yōu)化算法[J];計算機工程;2009年10期

7 郭聰莉;朱莉;李向;;基于蟻群算法的多連接查詢優(yōu)化方法[J];計算機工程;2009年10期

8 王

本文編號：2513492