[發(fā)明專利]多路數(shù)據(jù)流θ連接優(yōu)化方法及系統(tǒng)

在審

• 申請?zhí)枺?/td>: 201910774187.3
• 申請日: 2019-08-21
• 公開（公告）號: CN110489452A
• 公開（公告）日: 2019-11-22
• 發(fā)明（設(shè)計(jì)）人: 胡紫玥;范小朋;須成忠
• 申請（專利權(quán)）人: 中國科學(xué)院深圳先進(jìn)技術(shù)研究院
• 主分類號: G06F16/2455
• 分類號: G06F16/2455;G06F16/182
• 代理公司: 44316 深圳市科進(jìn)知識產(chǎn)權(quán)代理事務(wù)所(普通合伙)
• 代理人: 曹衛(wèi)良<國際申請>=<國際公布>=<進(jìn)入

本發(fā)明涉及一種多路數(shù)據(jù)流θ連接優(yōu)化方法，包括：從每個原始數(shù)據(jù)流中取出待處理數(shù)據(jù)分別緩存至該原始數(shù)據(jù)流對應(yīng)的一個緩存器；所述緩存器將取出的待處理數(shù)據(jù)按照指定屬性值范圍進(jìn)行分區(qū)存儲；對上述分區(qū)存儲的待處理數(shù)據(jù)進(jìn)行粗過濾；對上述粗過濾或者重新分區(qū)后的數(shù)據(jù)進(jìn)行連接操作；剔除連接操作后數(shù)據(jù)中不滿足條件的數(shù)據(jù)，得到最終連接結(jié)果。本發(fā)明還涉及一種多路數(shù)據(jù)流θ連接優(yōu)化系統(tǒng)。本發(fā)明能夠有效減少多路數(shù)據(jù)流θ連接次數(shù)，提高θ連接的效率，尤其是當(dāng)數(shù)據(jù)流數(shù)量越多，建立在這些數(shù)據(jù)流上的θ連接效率提升越明顯。

技術(shù)領(lǐng)域

本發(fā)明涉及一種多路數(shù)據(jù)流θ連接優(yōu)化方法及系統(tǒng)。

背景技術(shù)

在分布式數(shù)據(jù)處理環(huán)境中，數(shù)據(jù)的爆炸式增長帶來了大數(shù)據(jù)分析的新挑戰(zhàn)。連接運(yùn)算(Join)是對海量數(shù)據(jù)進(jìn)行分析處理的核心內(nèi)容之一。然而，由于連接操作的代價較高，如何提高連接操作的執(zhí)行性能一直是研究和開發(fā)的熱點(diǎn)問題。在連接操作中，θ連接是關(guān)系R與關(guān)系S的一種連接運(yùn)算，是從兩個關(guān)系的廣義笛卡爾積中選取屬性間滿足一定條件的元組形成一個新的連接：記作其中：A為數(shù)據(jù)集R中的屬性，B為數(shù)據(jù)集S中的屬性，θ為關(guān)系比較符，包含<，>，＝，≤，≥，≠，其中θ在“＝”時的連接為等值連接。

目前的主流研究中主要利用MapReduce框架來處理連接操作，該框架主要考慮網(wǎng)絡(luò)中負(fù)載平衡的開銷，當(dāng)數(shù)據(jù)集變大時，大量的中間結(jié)果會導(dǎo)致很高的通信開銷。在迭代式計(jì)算中，MapReduce把每一個中間結(jié)果存于HDFS上，下次計(jì)算需要在從HDFS讀取再計(jì)算，造成了很多不必要的I/O操作。

為了解決這一問題，一些技術(shù)基于Mapreduce做了一些優(yōu)化，盡可能使用一個MapReduce任務(wù)來計(jì)算。但是，現(xiàn)有技術(shù)的缺點(diǎn)主要體現(xiàn)在兩個方面：一是主要針對等值連接；二是大多數(shù)使用Mapreduce框架。

現(xiàn)有研究中絕大多數(shù)都是只關(guān)注等值連接，即特定屬性值相等時才進(jìn)行連接。θ連接除包含等于之外，還包含大于、大于等于、小于、小于等于、不等于等多種情況，相比等值連接，在對數(shù)據(jù)的分析處理上，θ連接適用范圍更加廣泛，但同時也意味著時間復(fù)雜度以及計(jì)算復(fù)雜度增加，尤其是海量數(shù)據(jù)的操作時，提高θ連接的效率顯得尤為重要。

此外，當(dāng)前多數(shù)研究基于Mapreduce計(jì)算框架，把數(shù)據(jù)全部發(fā)到Reduce任務(wù)里面。這種方法需要大幅修改Mapreduce框架。在迭代式計(jì)算中，Mapreduce框架劣勢更為明顯。Mapreduce作業(yè)默認(rèn)調(diào)度方式是FIFO，一次只運(yùn)行一個作業(yè)。Mapreduce需要將中間數(shù)據(jù)輸出到HDFS,在迭代式操作中，需要將中間數(shù)據(jù)從HDFS中先取出，再進(jìn)行下一步操作，當(dāng)?shù)螖?shù)多的時候，Mapreduce框架會造成很多不必要的I/O浪費(fèi)，在這一方面上也會導(dǎo)致連接時間長，效率低。例如：四個數(shù)據(jù)集的連接任務(wù)大多數(shù)基于Mapreduce系統(tǒng)將該作業(yè)分解為三個順序鏈接的Mapreduce子任務(wù)：第一個子任務(wù)負(fù)責(zé)數(shù)據(jù)集R和S的連接工作，得到中間結(jié)果集U₁輸出到分布式文件系統(tǒng)HDFS中，第二個子任務(wù)再從HDFS中讀出U₁與T進(jìn)行關(guān)聯(lián)連接得到中間結(jié)果U₂寫入HDFS文件中，第三個任務(wù)是將第二個子任務(wù)得到的結(jié)果U₂與N進(jìn)行關(guān)聯(lián)連接得到最終結(jié)果U₃寫入HDFS文件中。

但如果使用spark框架，則計(jì)算順序?qū)l(fā)生如下改變。spark系統(tǒng)根據(jù)任務(wù)創(chuàng)建DAG圖，stage1負(fù)責(zé)數(shù)據(jù)集R和S的連接工作，得到中間結(jié)果RDD₁并存到內(nèi)存中；stage2負(fù)責(zé)數(shù)據(jù)集T和N的連接工作，得到中間結(jié)果RDD₂并存到內(nèi)存中。stage1和stage2并發(fā)執(zhí)行。Stage3負(fù)責(zé)RDD₁和RDD₂的連接，其結(jié)果RDD₃為最終結(jié)果，存放于內(nèi)存中。可以發(fā)現(xiàn)如果連接的數(shù)據(jù)集足夠多或者中間結(jié)果集數(shù)據(jù)量很大則會帶來巨大的磁盤I/O浪費(fèi)。

發(fā)明內(nèi)容

有鑒于此，有必要提供一種多路數(shù)據(jù)流θ連接優(yōu)化方法及系統(tǒng)。