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

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

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

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

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

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

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

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

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

8 王

本文編號(hào)：2513492