Spark計(jì)算環(huán)境中的種間數(shù)據(jù)均衡放置算法研究.pdf

1、隨著網(wǎng)絡(luò)信息技術(shù)的不斷發(fā)展，全球使用互聯(lián)網(wǎng)的人數(shù)在持續(xù)的增加，互聯(lián)網(wǎng)已經(jīng)在很多行業(yè)進(jìn)行實(shí)踐和應(yīng)用，帶來(lái)了互聯(lián)網(wǎng)數(shù)據(jù)的批量式增加，分析處理這些海量的互聯(lián)網(wǎng)數(shù)據(jù)是一個(gè)至關(guān)重要的現(xiàn)實(shí)問(wèn)題，同時(shí)也給分布式計(jì)算提供了新的發(fā)展機(jī)遇。Google提出的MapReduce，它的特點(diǎn)是可靠性高、編程簡(jiǎn)單、能自動(dòng)并行處理作業(yè)，是一種用于處理大數(shù)據(jù)的分布式并行編程模型。Spark是基于內(nèi)存計(jì)算的分布式并行計(jì)算框架，Spark通過(guò)引入RDD數(shù)據(jù)模型及基于內(nèi)存的

2、運(yùn)算模式，使其能很好地適應(yīng)大數(shù)據(jù)的數(shù)據(jù)挖掘這中場(chǎng)景，并且在迭代計(jì)算方面優(yōu)于Hadoop，迅速成為了廣大企業(yè)、學(xué)者的研究重點(diǎn)。此外，很多科研單位和企業(yè)開(kāi)始在海量數(shù)據(jù)的處理和研究中開(kāi)始應(yīng)用Spark。
　　自MapReduce變成一個(gè)高效的和流行的并行數(shù)據(jù)處理編程框架，中間數(shù)據(jù)key值的偏斜成為影響系統(tǒng)性能的一個(gè)重要瓶頸。當(dāng)MapReduce處理的數(shù)據(jù)分布不均勻時(shí)，會(huì)造成有些任務(wù)比其他任務(wù)運(yùn)行較慢的情況，而整個(gè)作業(yè)的執(zhí)行時(shí)間是由最慢的

3、那個(gè)任務(wù)決定的，當(dāng)處理數(shù)據(jù)存在傾斜會(huì)導(dǎo)致處理數(shù)據(jù)分布不平衡從而產(chǎn)生“短腿”作業(yè)，最終影響整體的運(yùn)行效果。因此增加了整個(gè)作業(yè)的完成時(shí)間，使系統(tǒng)性能下降。MapReduce中數(shù)據(jù)傾斜問(wèn)題可以通過(guò)統(tǒng)計(jì)key值頻率提前制定分配方案的方法來(lái)解決。
　　為解決在Spark計(jì)算框架下shuffle過(guò)程中的buckets容器負(fù)載不平衡問(wèn)題。本文提出了對(duì)中間數(shù)據(jù)塊分割和組合算法SCID(segmentation and combinationalg

4、orithm for skew intermediate data)。由于keys值的數(shù)量不可統(tǒng)計(jì)，除非輸入數(shù)據(jù)被map任務(wù)處理，因此本文基于蓄水池的采樣算法以得到中間key值的分布數(shù)據(jù)。對(duì)比原始buckets中數(shù)據(jù)加載機(jī)制，SCID根據(jù)每個(gè)map任務(wù)的鍵/值元組的數(shù)據(jù)大小進(jìn)行排序，并有序的填充到相關(guān)buckets中。如果一個(gè)cluster超過(guò)當(dāng)前的buckets容量將被分割。在填充滿這個(gè)buckets后，其余clusters將進(jìn)入下一

5、次迭代，通過(guò)這種方式，數(shù)據(jù)的總大小在每個(gè)bucket大約是相等的。對(duì)于每一個(gè)map任務(wù)，每個(gè)reduce任務(wù)會(huì)從一個(gè)特定的buckets獲取到中間結(jié)果，這樣每個(gè)bucket中map的任務(wù)數(shù)量在reduce任務(wù)端達(dá)到負(fù)載均衡。我們?cè)赟park1.1.0上運(yùn)行SCID算法并通過(guò)廣泛使用的標(biāo)準(zhǔn)Benchmark評(píng)估其性能，比如:Sort，TextSearch，Word Count。實(shí)驗(yàn)結(jié)果表明，我們的算法不僅可以實(shí)現(xiàn)更高的總體平均負(fù)載平衡性能