[發(fā)明專利]分布式并行計(jì)算系統(tǒng)的數(shù)據(jù)分配方法及系統(tǒng)

在審

• 申請?zhí)枺?/td>: 201611042373.0
• 申請日: 2016-11-18
• 公開（公告）號: CN106598729A
• 公開（公告）日: 2017-04-26
• 發(fā)明（設(shè)計(jì)）人: 楊黎;付仲明
• 申請（專利權(quán)）人: 深圳市證通電子股份有限公司
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 深圳市世紀(jì)恒程知識(shí)產(chǎn)權(quán)代理事務(wù)所44287
• 代理人: 胡海國

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

本發(fā)明涉及計(jì)算機(jī)應(yīng)用技術(shù)領(lǐng)域，尤其涉及一種分布式并行計(jì)算系統(tǒng)的數(shù)據(jù)分配方法及系統(tǒng)。

背景技術(shù)

進(jìn)入21世紀(jì)以來，互聯(lián)網(wǎng)信息技術(shù)的革新發(fā)展進(jìn)入了快車道，一方面直接帶來了互聯(lián)網(wǎng)絡(luò)的速度傳輸不斷的提高，另一方面間接的帶來了世界各地使用互聯(lián)網(wǎng)的用戶呈現(xiàn)不斷的增加，最終帶來了數(shù)據(jù)量的大幅增加，呈現(xiàn)幾何數(shù)據(jù)量的增長。在2004年發(fā)表在OSDI(USENIX Symposium on Operating System Design and Implementation)會(huì)議上的關(guān)于分布式并行計(jì)算框架MapReduce，通過MapReduce可以實(shí)現(xiàn)對大數(shù)據(jù)高效地進(jìn)行處理。基于MapReduce的分布式并行計(jì)算平臺(tái)具有幾大優(yōu)勢特點(diǎn)，分別為：編程簡單、可靠性高、節(jié)點(diǎn)增減容易、并行化處理任務(wù)，價(jià)格低廉等特點(diǎn)，經(jīng)過幾年的發(fā)展和實(shí)踐，MapReduce的編程模型被證明是行之有效的處理大數(shù)據(jù)的方法。相比傳統(tǒng)的編程模型，可以使用MapReduce運(yùn)行多個(gè)并行化計(jì)算的映射任務(wù)map和歸約任務(wù)reduce在分布式數(shù)據(jù)自動(dòng)高效地跨多個(gè)機(jī)器。

在當(dāng)前流行的MapReduce實(shí)現(xiàn)上，比較Hadoop和其他分布式計(jì)算框架，Apache Spark對大規(guī)模數(shù)據(jù)處理有更高效的實(shí)現(xiàn)機(jī)制。在Spark中MapReduce的過程對待所有的中間數(shù)據(jù)看成<鍵,值>對，一個(gè)集群是所有成對的子集共享相同的鍵值。因?yàn)閙apper和reducer分別是map任務(wù)和reduce任務(wù)的容器，Spark實(shí)現(xiàn)集群分發(fā)標(biāo)準(zhǔn)，采用哈希算法去分配集群到reducers，所有集群被同一個(gè)reduce處理組成一個(gè)分區(qū)。分區(qū)的大小取決于相關(guān)的數(shù)量<鍵,值>對，對于傾斜數(shù)據(jù)，默認(rèn)的哈希分區(qū)不能很好地分配集群，這可能會(huì)導(dǎo)致不同reducers的工作負(fù)載有較大的差別。作為中間數(shù)據(jù)的鍵值傾斜總是存在的，增加了程序運(yùn)行的時(shí)間，作業(yè)效率低。

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

本發(fā)明的主要目的在于提出一種分布式并行計(jì)算系統(tǒng)的數(shù)據(jù)分配方法及系統(tǒng)，旨在平衡reduce任務(wù)的負(fù)載，從而提高作業(yè)執(zhí)行的效率，減少時(shí)間的損耗。

為實(shí)現(xiàn)上述目的，本發(fā)明提供的一種分布式并行計(jì)算系統(tǒng)的數(shù)據(jù)分配方法包括：

估算輸入數(shù)據(jù)集中的各個(gè)聚類的占用空間；

根據(jù)所述輸入數(shù)據(jù)集的各個(gè)聚類的占用空間以及預(yù)設(shè)的各個(gè)數(shù)據(jù)塊的剩余空間，建立各個(gè)聚類以及存儲(chǔ)所述聚類的各個(gè)數(shù)據(jù)塊的對應(yīng)關(guān)系；

根據(jù)各個(gè)聚類以及存儲(chǔ)所述聚類的各個(gè)數(shù)據(jù)塊的對應(yīng)關(guān)系，將各個(gè)所述聚類存儲(chǔ)于對應(yīng)的數(shù)據(jù)塊中。

優(yōu)選地，所述估算輸入數(shù)據(jù)集中的各個(gè)聚類的占用空間的步驟包括：

采用蓄水池抽樣算法抽取占所述輸入數(shù)據(jù)集總數(shù)據(jù)量預(yù)設(shè)比例的聚類作為數(shù)據(jù)集樣本；

統(tǒng)計(jì)所述數(shù)據(jù)集樣本的各個(gè)聚類的占用空間；

根據(jù)所述數(shù)據(jù)集樣本的各個(gè)聚類的占用空間以及所述預(yù)設(shè)比例確定輸入數(shù)據(jù)集的各個(gè)聚類的占用空間。

優(yōu)選地，所述根據(jù)所述輸入數(shù)據(jù)集的各個(gè)聚類的占用空間以及各個(gè)數(shù)據(jù)塊的空間，建立各個(gè)聚類以及存儲(chǔ)所述聚類的各個(gè)數(shù)據(jù)塊的對應(yīng)關(guān)系的步驟包括：

計(jì)算各個(gè)數(shù)據(jù)塊的額定容量，所述額定容量等于輸入數(shù)據(jù)集的各個(gè)聚類的占用空間的總和除以數(shù)據(jù)塊的數(shù)目，其中，各個(gè)所述數(shù)據(jù)塊的初始剩余空間等于所述數(shù)據(jù)塊的額定容量；

根據(jù)數(shù)據(jù)塊的額定容量，對聚類進(jìn)行分割組合后劃分到不同的數(shù)據(jù)塊中，建立分割組合后的聚類以及存儲(chǔ)所述分割組合后的聚類的數(shù)據(jù)塊的對應(yīng)關(guān)系。

優(yōu)選地，所述根據(jù)數(shù)據(jù)塊的額定容量，對聚類進(jìn)行分割組合后劃分到不同的數(shù)據(jù)塊中的步驟包括：

按照占用空間從大到小的順序依次調(diào)用各個(gè)聚類，以及按照剩余空間從大到小的順序調(diào)用各個(gè)數(shù)據(jù)塊；

在每次調(diào)用到聚類時(shí)，判斷當(dāng)前調(diào)用的聚類的占用空間是否大于當(dāng)前調(diào)用的所述數(shù)據(jù)塊的剩余空間；

在當(dāng)前調(diào)用的聚類的占用空間小于或等于當(dāng)前調(diào)用的所述數(shù)據(jù)塊的剩余空間時(shí)，將當(dāng)前調(diào)用的所述聚類劃分至當(dāng)前調(diào)用的所述數(shù)據(jù)塊中，并繼續(xù)調(diào)用下一所述聚類；

在當(dāng)前調(diào)用的聚類的占用空間大于當(dāng)前調(diào)用的所述數(shù)據(jù)塊的剩余空間時(shí)，根據(jù)當(dāng)前調(diào)用的所述數(shù)據(jù)塊的剩余空間對當(dāng)前調(diào)用的所述聚類進(jìn)行切割；

將切割得到的聚類劃分至當(dāng)前調(diào)用的所述數(shù)據(jù)塊，將切割剩余的聚類添加至未調(diào)用的聚類中，并調(diào)用下一數(shù)據(jù)塊。

優(yōu)選地，所述建立各個(gè)聚類以及存儲(chǔ)所述聚類的各個(gè)數(shù)據(jù)塊的對應(yīng)關(guān)系的步驟之后，所述分布式并行計(jì)算系統(tǒng)的數(shù)據(jù)分配方法還包括：

獲取各個(gè)聚類的實(shí)際占用空間；