并行大數(shù)據(jù)清洗過程優(yōu)化范文

本站小編為你精心準(zhǔn)備了并行大數(shù)據(jù)清洗過程優(yōu)化參考范文，愿這些范文能點燃您思維的火花，激發(fā)您的寫作靈感。歡迎深入閱讀并收藏。

《計算機學(xué)報》2016年第一期

摘要

數(shù)據(jù)質(zhì)量問題會對大數(shù)據(jù)的應(yīng)用產(chǎn)生致命影響，因此需要對存在數(shù)據(jù)質(zhì)量問題的大數(shù)據(jù)進(jìn)行清洗．MapReduce編程框架可以利用并行技術(shù)實現(xiàn)高可擴展性的大數(shù)據(jù)清洗，然而，由于缺乏有效的設(shè)計，在基于MapReduce的數(shù)據(jù)清洗過程中存在計算的冗余，導(dǎo)致性能降低．因此文中的目的是對并行數(shù)據(jù)清洗過程進(jìn)行優(yōu)化從而提高效率．通過研究，作者發(fā)現(xiàn)數(shù)據(jù)清洗中一些任務(wù)往往都運行在同一輸入文件上或者利用同樣的運算結(jié)果，基于該發(fā)現(xiàn)文中提出了一種新的優(yōu)化技術(shù)———基于任務(wù)合并的優(yōu)化技術(shù)．針對冗余計算和利用同一輸入文件的簡單計算進(jìn)行合并，通過這種合并可以減少MapReduce的輪數(shù)從而減少系統(tǒng)運行的時間，最終達(dá)到系統(tǒng)優(yōu)化的目標(biāo)．文中針對數(shù)據(jù)清洗過程中多個復(fù)雜的模塊進(jìn)行了優(yōu)化，具體來說分別對實體識別模塊、不一致數(shù)據(jù)修復(fù)模塊和缺失值填充模塊進(jìn)行了優(yōu)化．實驗結(jié)果表明，文中提出的策略可以有效提高數(shù)據(jù)清洗的效率．

關(guān)鍵詞

大數(shù)據(jù)；多任務(wù)優(yōu)化；海量數(shù)據(jù)；數(shù)據(jù)清洗；Hadoop；MapReduce

1引言

本節(jié)主要介紹研究背景及其意義、海量數(shù)據(jù)清洗系統(tǒng)、本文優(yōu)化方法的主要思想、本文的貢獻(xiàn)與結(jié)構(gòu)．

1．1研究背景及其意義現(xiàn)今企業(yè)的成功和社會的進(jìn)步，越來越依賴于數(shù)據(jù)和對其所做的分析．為了獲得競爭優(yōu)勢即使是小企業(yè)也會投入時間和精力來收集和分析數(shù)據(jù)．很多大公司都部署了自己的云服務(wù)平臺，國內(nèi)比較著名的有百度云、阿里云、天翼云①等．但是如果一味地將精力投入到對數(shù)據(jù)所做的分析而不關(guān)注數(shù)據(jù)本身，很可能產(chǎn)生災(zāi)難性的后果．統(tǒng)計表明，美國企業(yè)中1％～30％的數(shù)據(jù)存在各類錯誤和誤差［1］，醫(yī)療數(shù)據(jù)庫中13．6％～81％的關(guān)鍵數(shù)據(jù)不完整或陳舊［2］．根據(jù)市場研究公司Gartner的調(diào)查，全球財富1000強公司超過25％的關(guān)鍵數(shù)據(jù)不正確或不準(zhǔn)確［3］．?dāng)?shù)據(jù)質(zhì)量問題會使基于其的分析和研究毫無意義甚至還會產(chǎn)生災(zāi)難性的后果，在美國由于數(shù)據(jù)錯誤引起的醫(yī)療事故每年使98000名患者喪生［4］．上述實例表明數(shù)據(jù)質(zhì)量問題存在于社會生活的方方面面，數(shù)據(jù)清洗系統(tǒng)應(yīng)運而生．在海量數(shù)據(jù)處理領(lǐng)域，MapReduce編程框架作為當(dāng)下最流行的并行編程開發(fā)框架已被Google、Amazon、Yahoo！、Facebook以及國內(nèi)的騰訊、阿里巴巴等大型互聯(lián)網(wǎng)公司奉為至寶．將Hadoop用于海量數(shù)據(jù)處理主要有如下優(yōu)勢：易用性、高可擴展性、高容錯性．上述優(yōu)勢使得基于MapReduce的海量數(shù)據(jù)清洗順其自然的產(chǎn)生了．海量數(shù)據(jù)上的數(shù)據(jù)分析往往需要相對高昂的硬件成本和時間成本，這就引起了人們對優(yōu)化數(shù)據(jù)分析的興趣．當(dāng)前已經(jīng)有不少人開始研究大數(shù)據(jù)上的數(shù)據(jù)清洗系統(tǒng)，有對整個數(shù)據(jù)清洗系統(tǒng)進(jìn)行研究［5－7］，也有對其中的數(shù)據(jù)一致性［8－10］，實體識別如文獻(xiàn)［11－14］等問題進(jìn)行研究的．然而現(xiàn)在還沒有人對基于MapReduce的數(shù)據(jù)清洗系統(tǒng)的優(yōu)化進(jìn)行研究．現(xiàn)在幾乎所有的數(shù)據(jù)分析任務(wù)都可以用MapReduce編程框架來實現(xiàn)，但是在實現(xiàn)過程中往往會存在冗余的MapReduce，基于MapReduce的海量數(shù)據(jù)清洗系統(tǒng)也不例外．本文提出的基于任務(wù)合并的優(yōu)化方法著眼于系統(tǒng)中冗余的MapReduce，從細(xì)節(jié)和流程的各個方面實施．

1．2海量數(shù)據(jù)清洗系統(tǒng)海量數(shù)據(jù)清洗系統(tǒng)如圖1所示，它在Hadoop平臺上實施，以一個靈活的結(jié)構(gòu)來處理不同類型的數(shù)據(jù)質(zhì)量問題，每種類型的數(shù)據(jù)質(zhì)量問題都由一個或多個模塊來處理，由哈爾濱工業(yè)大學(xué)海量數(shù)據(jù)計算與研究中心提供源代碼．系統(tǒng)中的交互模塊提供一個輸入接口來輸入需要清洗的文件以及清洗數(shù)據(jù)的要求．結(jié)果展示模塊提供清潔數(shù)據(jù)的下載鏈接以及臟數(shù)據(jù)和清洗后的數(shù)據(jù)的對比情況．實體識別和真值發(fā)現(xiàn)模塊用于消冗，其中實體識別把指向同一現(xiàn)實世界實體的元組聚類，而真值發(fā)現(xiàn)用來在沖突中尋找出真實值．不一致檢測模塊發(fā)現(xiàn)數(shù)據(jù)中違反依賴規(guī)則的部分并且嘗試把數(shù)據(jù)修復(fù)到符合規(guī)則的狀態(tài)．?dāng)?shù)值填充部分檢測數(shù)據(jù)缺失部分并填充．用戶可以選擇合適的模塊來處理所遇到的數(shù)據(jù)質(zhì)量問題。

1．3本文優(yōu)化方法概要和其他優(yōu)化方法本節(jié)首先給出基于任務(wù)合并的優(yōu)化方法，然后對基于Hadoop平臺的海量數(shù)據(jù)清洗系統(tǒng)進(jìn)行優(yōu)化．一個實際的系統(tǒng)往往需要很多輪MapReduce來實現(xiàn)．有文獻(xiàn)表明，對于比較復(fù)雜的單一型人物，拆分開來執(zhí)行的話性能反而更好．但是根據(jù)MapReduce編程方式的特點，往往需要將一個問題分解成很多簡單的任務(wù)，每一個任務(wù)由一輪MapReduce實現(xiàn)．在大多數(shù)情況下，這種“分解”是過度的，由此而產(chǎn)生冗余的MapReduce．將可以合并的任務(wù)進(jìn)行適當(dāng)?shù)暮喜ⅲ⑶以诓桓淖冊到y(tǒng)的算法復(fù)雜度與迭代可終止性等前提下，滿足可以減少原系統(tǒng)的MapReduce輪數(shù)和IO次數(shù)等條件進(jìn)而達(dá)到優(yōu)化的目的．與本文研究方向相同的工作最杰出的優(yōu)化方法有MRShare［15－16］，后者是在前者的基礎(chǔ)上發(fā)展而來的優(yōu)化方法并且實現(xiàn)過程復(fù)雜，優(yōu)化效率提升不是很明顯．MRShare把多個共享相同的map輸入或輸出的任務(wù)合并成一個任務(wù)，減少掃描文件的次數(shù)，從而達(dá)到優(yōu)化的目的．但當(dāng)合并后的任務(wù)的較大的map輸出的sort代價高于合并之前的多個獨立的較小的map輸出的代價時，就不會有任何優(yōu)化效果．本文提出的基于任務(wù)合并的優(yōu)化技術(shù)針對冗余計算和利用同一輸入文件的簡單計算進(jìn)行合并，通過這種合并可以減少MapReduce的輪數(shù)從而減少系統(tǒng)運行的時間．通過對整個系統(tǒng)的框架與流程進(jìn)行優(yōu)化設(shè)計，有效地提高系統(tǒng)的效率．

1．4本文的貢獻(xiàn)本文的主要貢獻(xiàn)有：（1）提出一種基于MapReduce的應(yīng)用系統(tǒng)的優(yōu)化方法．（2）對海量數(shù)據(jù)清洗系統(tǒng)中計算較為復(fù)雜的3個模塊進(jìn)行討論并提出優(yōu)化方案．（3）對海量數(shù)據(jù)清洗系統(tǒng)的各個模塊優(yōu)化前后進(jìn)行了大量的對比實驗．

1．5本文的結(jié)構(gòu)本文第1節(jié)介紹背景、主要內(nèi)容和本文結(jié)構(gòu)；第2、3、4節(jié)詳細(xì)討論優(yōu)化方法與實施過程；第5節(jié)給出實驗結(jié)果和分析；最后在第6節(jié)給出結(jié)論．

2優(yōu)化的缺失值填充

在實際的生產(chǎn)生活中，數(shù)據(jù)缺失是一種不可避免的現(xiàn)象，尤其是在數(shù)據(jù)收集工作日趨自動化的今天．本模塊是一種利用樸素貝葉斯分類的缺失值填充機制．

2．1缺失值填充模塊介紹舉一個例子，假設(shè)一個學(xué)校有60％的男生和40％的女生．女生穿褲子的人數(shù)和穿裙子的人數(shù)相等，所有男生都穿褲子．一個人在遠(yuǎn)處隨機看到了一個穿褲子的學(xué)生，那么該學(xué)生的性別是什么？（1）參數(shù)估計模塊整個缺失值填充系統(tǒng)是用貝葉斯分類的思想來計算出概率最大的取值作為填充值．參數(shù)估計模塊的任務(wù)是利用式（1）計算出所有的概率，其中P（X）對所有取值為常數(shù)，所以只需要計算P（X｜Ci）×P（Ci）即可．在各個取值的先驗概率未知的情況下，不妨假設(shè)其是等概率的，因此只需計算P（X｜Ci）即可。（2）連接模塊系統(tǒng)在填充模塊會根據(jù)式（2）計算出含有缺失值的元組在它的依賴屬性取值確定的所確定的各個待填充值的概率．但是由于MapReduce函數(shù)在map階段和reduce階段一次只能處理一條記錄，所以系統(tǒng)必須使依賴屬性取值和其條件概率關(guān)聯(lián)起來，這就是連接模塊存在的必要性和需要解決的問題．連接模塊的輸入數(shù)據(jù)為參數(shù)估計模塊的輸出數(shù)據(jù)和原待填充數(shù)據(jù)，輸出數(shù)據(jù)是將含缺失數(shù)據(jù)的元組中依賴屬性取值與該取值條件概率相關(guān)聯(lián)的文件．此模塊的輸入數(shù)據(jù)為原待填充數(shù)據(jù)和連接模塊的輸出，輸出數(shù)據(jù)為經(jīng)過填充之后的數(shù)據(jù)．利用式（2）計算出每個Ci（待填充屬性可能的取值）對應(yīng)的條件概率，選擇其中P（Ci｜X）概率最大的Ci進(jìn)行填充．（3）填充模塊填充模塊由一輪MapReduce實現(xiàn)，首先將連接模塊的輸出結(jié)果和原始輸入數(shù)據(jù)以偏移量為鍵值進(jìn)行連接運算，map階段和連接模塊類似，在此不再說明．reduce階段利用式（2）計算出每個Ci（待填充屬性可能的取值）對應(yīng)的條件概率，選擇其中P（Ci｜X）概率最大的Ci進(jìn)行填充．填充效果見圖3．以上是對缺失值填充模塊的簡要介紹，詳細(xì)介紹參考文獻(xiàn)［17］，本文僅對其離散類型的缺失值填充做考慮．

2．2系統(tǒng)分析與優(yōu)化首先分析一下整個模塊各個子模塊之間的數(shù)據(jù)流和聯(lián)系紐帶．參數(shù)估計子模塊利用輸入數(shù)據(jù)中的不包含缺失數(shù)據(jù)元組來計算以依賴屬性的不同取值為條件的待填充屬性的各種取值的條件概率①．在計算填充值的過程中需要用到以各依賴屬性的當(dāng)前取值為條件的待填充屬性的各種可能取值的條件概率②，②是①中的一組特定的值，②和①的聯(lián)系紐帶是依賴屬性的取值．而②和原始數(shù)據(jù)中的待填充元組之間的聯(lián)系是該元組的偏移量．因此在參數(shù)估計模塊和填充模塊之間增加了連接模塊．仔細(xì)觀察系統(tǒng)各階段數(shù)據(jù)流可以發(fā)現(xiàn)，在參數(shù)估計的map輸入和map輸出數(shù)據(jù)中均包含元組的偏移量，但是reduce輸出數(shù)據(jù)中只有屬性值和②．這種情況使系統(tǒng)必須通過增加一個連接運算才能將②與待填充元組的偏移量結(jié)合在一起．針對上述情況本文提出了一種將參數(shù)估計模塊和連接模塊的任務(wù)合并的優(yōu)化方案，即在參數(shù)估計模塊就將輸出的條件概率與含有缺失值的元組偏移量關(guān)聯(lián)起來．其算法如下．下面舉例說明優(yōu)化后的算法流程，表1為包含缺失值的數(shù)據(jù)，缺失值可能為y或n．前兩條元組不含缺失值，故僅將其按屬性拆分；第3條元組含有缺失值，我們在每種可能取值的情況下按屬性拆分，Map階段輸出結(jié)果見表2．Reduce階段檢查所有輸入數(shù)據(jù)的前綴，若不包含缺失值則進(jìn)入條件概率計算環(huán)節(jié)；若包含缺失值則將其錄入likelihood（用于判定條件概率是否需要輸出）．最后選擇屬性值存在于likelihood中的條件概率進(jìn)行輸出，輸出結(jié)果見表3．優(yōu)化后的參數(shù)估計子模塊，Map階段的算法復(fù)雜度為O（n＋ML），其中n為不包含缺失值的元組的數(shù)量，M為包含缺失值的元組的數(shù)量，L為缺失值可能取值的數(shù)目．一般情況下Mn，故O（n＋ML）＝O（（1＋L）n）．因為L為一個遠(yuǎn)小于n的常數(shù)，所以Map階段的算法復(fù)雜度為O（n）．Reduce階段的算法復(fù)雜度為O（n）．故整個參數(shù)估計子模塊的算法復(fù)雜度為O（n）．優(yōu)化前后，參數(shù)估計子模塊的算法復(fù)雜度一直是O（n），填充子模塊未做優(yōu)化．整個缺失值填充模塊的MapReduce輪數(shù)和IO次數(shù)均由優(yōu)化前的3變?yōu)?，加速比為3／2，優(yōu)化效果明顯．

3優(yōu)化的實體識別

實體識別，就是識別出同一實體的不同表現(xiàn)形式．不同的數(shù)據(jù)來源對同一對象的表示形式往往有著不同的要求，并且在數(shù)據(jù)的存儲和傳遞過程中均會產(chǎn)生不可避免的錯誤，因此產(chǎn)生了同一實體的不同表現(xiàn)形式．關(guān)于MapReduce框架下的實體識別技術(shù)，現(xiàn)在已經(jīng)有了相關(guān)研究工作［18－19］，但是他們只解決了異名實體識別問題，對同名問題沒有進(jìn)行研究；而我們的工作可以同時解決了異名和同名問題．

3．1實體識別模塊介紹（1）預(yù)處理．系統(tǒng)讀入海量數(shù)據(jù)文件并進(jìn)行預(yù)處理，給每一條輸入元組加上一個唯一的序號———實體ID，方便后續(xù)處理．（2）初步聚類．讀取預(yù)處理模塊生成的數(shù)據(jù)，按照相同屬性值進(jìn)行初步聚類，生成屬性索引表．（3）實體識別．對實體進(jìn)行識別，對同一屬性索引表中的實體對計算相似度并與閾值進(jìn)行比較，大于閾值的相似對輸出成相似對集合文件．（4）實體劃分．依據(jù)相似對集合文件生成圖，通過對圖的劃分獲得實體劃分結(jié)果．以上是對實體識別模塊的簡要介紹，詳細(xì)介紹參考文獻(xiàn)［20］

3．2系統(tǒng)分析與優(yōu)化通過研究發(fā)現(xiàn)初步聚類模塊和實體識別模塊，對預(yù)處理結(jié)果重復(fù)利用了N次（N為待處理數(shù)據(jù)每條元組包含的屬性個數(shù)），而且后續(xù)的實體識別模塊也是在單一屬性上處理的．如果將預(yù)處理模塊和實體識別模塊看作一個整體（系統(tǒng)實際應(yīng)用中也是這樣的），那么就是對輸入數(shù)據(jù)文件掃描多次，并且只能利用輸入數(shù)據(jù)中的一部分，系統(tǒng)對輸入數(shù)據(jù)的利用率很低．此外系統(tǒng)每次分配任務(wù)都需要消耗額外的資源．我們需要將分開處理各個屬性的初步聚類和實體識別合并成一次能處理所有屬性進(jìn)而只運行一輪就能處理每條元組所有屬性的解決方案．為此本文針對實體識別模塊提出的優(yōu)化思想是：在初步聚類子模塊一次處理所有屬性，生成所有屬性值的屬性索引表．這樣就能將原來按屬性分開處理的預(yù)處理和實體識別合并起來．下面給出具體的優(yōu)化方案和算法．（1）初步聚類子模塊，map階段不是僅僅輸出第i個屬性值，而是將所有屬性值都輸出．但是為了區(qū)分初步聚類產(chǎn)生的結(jié)果———屬性索引表集合中的1101期楊東華等：基于任務(wù)合并的并行大數(shù)據(jù)清洗過程優(yōu)化實體ID是來自不同的屬性，系統(tǒng)在map輸出數(shù)據(jù)的key上做了一些改動，在原key前加上了一個前綴，由“屬性值”變成“屬性序號＄屬性值”．因為MapReduce是按照key進(jìn)行分類的，所以只有同一屬性的具有相同屬性值的實體才會進(jìn)入同一屬性索引表．reduce階段將屬性序號作為實體ID的前綴加在實體ID中．以下是優(yōu)化后的初步聚類算法．其中實體ID是每個元組的編號，在預(yù)處理階段為每一個元組（一行數(shù)據(jù)）設(shè)定唯一的實體ID．屬性ID是屬性在元組中的順序．下面舉例說明優(yōu)化后的算法流程，待識別數(shù)據(jù)如表4所示．Map階段將所有元組的按屬性拆分后輸出，結(jié)果如表5所示．屬性值相同的實體會進(jìn)入同一個reduce，并輸出成屬性索引表，如表6所示。優(yōu)化后的初步聚類模塊，map階段的算法復(fù)雜度為O（n（x＋x2）），其中x為屬性個數(shù)，實際應(yīng)用中x為一個很小的常數(shù)值，故其計算復(fù)雜度為O（n）．reduce階段除了在附加的讀取屬性序號外沒有任何改動，其計算復(fù)雜度為O（n）．綜上整個初步聚類模塊的算法復(fù)雜度為O（n）．（2）實體識別子模塊，因為整個實體識別模塊是在初步聚類生成的屬性索引表中進(jìn)行的，而初步聚類模塊的改動保證了同一屬性的具有相同屬性值的實體ID聚集在同一個屬性索引表中，所以這一模塊的算法不需要修改．除了在第3個MapReduce的reduce階段去除實體ID中包含的前綴外，沒有任何更改．這樣做的目的是為了使同一實體的相似度能夠在第4個MapReduce中匯合．整個實體識別模塊的算法沒有經(jīng)過改動，所以其算法的時間復(fù)雜度仍保持O（n）．由于本文只對系統(tǒng)Hadoop上運行部分進(jìn)行優(yōu)化處理，所以將實體劃分模塊視作常量．在時間復(fù)雜度方面，從上一小節(jié)對實體識別子系統(tǒng)的介紹和本小節(jié)前面的一部分的優(yōu)化方案中算法的計算復(fù)雜度可以看出，優(yōu)化前后沒有改變各個模塊以及各個模塊內(nèi)部的各個MapReduce的計算復(fù)雜度．優(yōu)化前的MapReduce輪數(shù)為1＋N（1＋4）＝5N＋1，優(yōu)化之后的MapReduce輪數(shù)為1＋1＋4＝6，加速比為（5N＋1）／6．正常情況下N大于1，所以加速比大于1，并且N越大加速效果越明顯．IO次數(shù)也由先前的5N＋1次變?yōu)?次，IO次數(shù)減少使得系統(tǒng)用于IO的時間減少．另外由于MapReduce的輪數(shù)減少，系統(tǒng)用于任務(wù)調(diào)度的時間和資源也相應(yīng)減少．綜上，從理論上講，通過本文的提供的優(yōu)化方案能產(chǎn)生明顯的優(yōu)化效果．

4優(yōu)化的不一致數(shù)據(jù)修復(fù)

在實際的數(shù)據(jù)庫系統(tǒng)及相關(guān)應(yīng)用中由于種種原因，其中包含的數(shù)據(jù)違反最初定義的完整性約束，所以存在大量不一致數(shù)據(jù)．本系統(tǒng)利用數(shù)據(jù)依賴?yán)碚撝械臈l件函數(shù)依賴原理，定義完整性約束，利用完整性約束進(jìn)行不一致數(shù)據(jù)修復(fù)．本文的重點在于提高不一致數(shù)據(jù)修復(fù)模塊的性能和效率，使之一致．至于如何保證這樣的修改過程是正確的，是由條件函數(shù)依賴?yán)碚撍鶝Q定的，本文相關(guān)的理論證明和推導(dǎo)詳見文獻(xiàn)［9－10］．

4．1不一致數(shù)據(jù)修復(fù)模塊介紹不一致數(shù)據(jù)修復(fù)模塊步驟的簡要介紹如下：（1）系統(tǒng)讀入待修復(fù)的海量數(shù)據(jù)文件和cfds文件并進(jìn)行預(yù)處理，將數(shù)據(jù)格式更改成符合系統(tǒng)要求的格式并對cfds進(jìn)行初步檢測，方便后續(xù)處理．（2）對預(yù)處理結(jié)果中的數(shù)據(jù)文件進(jìn)行檢測與修復(fù)，得到初次修復(fù)結(jié)果．（3）對初次修復(fù)結(jié)果進(jìn)行檢測，判斷修復(fù)工作是否引入了新的不一致．若引入了新的不一致則返回步驟（1），否則進(jìn)入步驟（3）．當(dāng)然為了避免系統(tǒng)陷入死循環(huán)，系統(tǒng)為檢測與修復(fù)的次數(shù)設(shè)置了一個上限．（4）對修復(fù)結(jié)果進(jìn)行后處理，將數(shù)據(jù)格式更改成數(shù)據(jù)的原始格式，使得修復(fù)結(jié)果能正常被其他系統(tǒng)使用．以上是對實體識別模塊的簡要介紹，詳細(xì)介紹見參考文獻(xiàn)［21］．

4．2系統(tǒng)分析與優(yōu)化不一致數(shù)據(jù)修復(fù)子系統(tǒng)的4個模塊中除第1個模塊的CFD一致性檢測子模塊外都是在MapReduce編程框架上實現(xiàn)的，在本文的研究范圍內(nèi)．本模塊的一個重要缺點是沒有掌握MapReduce編程“分解與合并”的精髓，將本來僅需要一個Map或者一輪MapReduce便可完成的任務(wù)拆分成一輪或多輪MapReduce，由此使系統(tǒng)效率下降．為此我們在不改變系統(tǒng)算法復(fù)雜度的條件下進(jìn)行任務(wù)合并．（1）預(yù)處理模塊預(yù)處理模塊的臟數(shù)據(jù)預(yù)處理子模塊功能很簡單，就是給輸入數(shù)據(jù)建立索引，實施過程中沒有涉及到數(shù)據(jù)的分解與合并，可以通過一個map函數(shù)實現(xiàn)．算法如下．（2）不一致數(shù)據(jù)檢測與修復(fù)模塊不一致數(shù)據(jù)的檢測與修復(fù)模塊中常量違反檢測與修復(fù)模塊通過一輪MapReduce實現(xiàn)，map階段將元組重新分發(fā)了M份（M為輸入元組發(fā)生常量違反的次數(shù)），盡管M實際值一般不大，對reduce階段的計算復(fù)雜度幾乎沒有影響．但是M的存在會使中間數(shù)據(jù)量擴大M倍，對系統(tǒng)通信造成很大負(fù)擔(dān)．更重要的是在系統(tǒng)計算出建議修復(fù)值的同時就可以將其修復(fù)，那么就沒有必要將找到建議修復(fù)值的過程和修復(fù)過程分開．為此本文提出的優(yōu)化方案是利用一個map函數(shù)實現(xiàn)常量違反檢測與修復(fù)子模塊．將常量違反與修復(fù)子模塊通過一個map函數(shù)實現(xiàn)之后，經(jīng)過常量違反修復(fù)的數(shù)據(jù)直接進(jìn)入變量違反修復(fù)環(huán)節(jié)．兩者輸入數(shù)據(jù)的格式是相同的，假如原始數(shù)據(jù)中不存在常量違反，那么兩者輸入文件就是完全相同的．基于上述觀點，本文提出了將常量違反修復(fù)與變量違反修復(fù)合并的優(yōu)化方案．在這個優(yōu)化方案中常量違反修復(fù)位于原變量違反修復(fù)的第1輪MapReduce的前端，讓常量違反的結(jié)果在Map函數(shù)內(nèi)部直接應(yīng)用于變量違反．算法如下．其中，offset為元組索引值，tuple表示該條元組，fix＿tag為修復(fù)標(biāo)志，用來區(qū)分是否發(fā)生違反需要修復(fù)，0表示發(fā)生違反需要修復(fù)，1表示不需要修復(fù)．cfdindex是tuple違反的CFD的序號，ptindex是該tuple違反的CFD的模式表中的模式元組序號，attrindex標(biāo)志該tuple的不一致數(shù)據(jù)項的屬性序號，fixvalue即為該屬性值應(yīng)修復(fù)的結(jié)果．下面舉例說明優(yōu)化后的算法流程，待修復(fù)數(shù)據(jù)如表7所示．為了便于說明，本例中僅使用1條cfd和一個tp，分別為1：（［CC，AC，PN］→［STR，CT，ST］）和T1：01，908，＿，＿，MH，＿．Map階段將每一條輸入的待修復(fù)元組與模式元組tp作比較，進(jìn)行常量違反修復(fù)，然后再進(jìn)行變量違反修復(fù)．第1條元組沒有發(fā)生常量違反，遂進(jìn)入變量違反修復(fù)環(huán)節(jié)，其map輸出為表8中第1行．第2條元組發(fā)生常量違反，經(jīng)常量違反修復(fù)進(jìn)入變量違反修復(fù)環(huán)節(jié)，其map輸出為表8中第2行．下同．在時間復(fù)雜度方面，從預(yù)處理小節(jié)和本小節(jié)優(yōu)化方案中算法的計算復(fù)雜度可以看出，優(yōu)化前后沒有改變各個模塊以及各個模塊內(nèi)部的各個MapReduce的計算復(fù)雜度．在MapReduce輪數(shù)和IO次數(shù)方面，系統(tǒng)的MapReduce輪數(shù)由優(yōu)化前的1＋1＋2＋1＋1＋1＝7變成優(yōu)化后的1＋2＋1＋1＝5．僅從MapReduce輪數(shù)來看系統(tǒng)的加速比為7／5．此外系統(tǒng)的優(yōu)化工作還使得預(yù)處理模塊的MapReduce變成了map，這也會相應(yīng)地減少系統(tǒng)的運行時間．隨著MapReduce輪數(shù)的減少，系統(tǒng)的IO次數(shù)也相應(yīng)地減少，這也使得系統(tǒng)的IO負(fù)擔(dān)減小。綜上所述，通過本文提供的優(yōu)化方案，不一致修復(fù)子系統(tǒng)會獲得理想的優(yōu)化效果．

5實驗結(jié)果

整個系統(tǒng)在Ubuntu12．04．1操作系統(tǒng)中的Hadoop1．2．1平臺上，用java語言實現(xiàn)，軟件開發(fā)環(huán)境為Eclipse．實驗運行的集群采用12個節(jié)點，1個tasktraker（namenode），11個jobtracker（data－node）．集群由12臺機器組成，硬件環(huán)境為Inteli73770處理器，主頻為3．4GHz，內(nèi)存8GB，1TB硬盤空間．

5．1實體識別優(yōu)化實驗為了使系統(tǒng)的優(yōu)化效果更有說服力，所有實驗數(shù)據(jù)是來自DBLP的真實數(shù)據(jù)集．針對系統(tǒng)的特點，實驗分別從擴展性、集群的并行化程度和數(shù)據(jù)的屬性個數(shù)3個方面驗證系統(tǒng)的優(yōu)化效果．DBLP的數(shù)據(jù)規(guī)模并不大，看似不需要在Hadoop上實現(xiàn)．但大家公認(rèn)的數(shù)據(jù)源往往數(shù)據(jù)量比較小，使用DBLP數(shù)據(jù)集的意義不是因為其規(guī)模而是在于DBLP數(shù)據(jù)集是真實數(shù)據(jù)，這樣做可以增加本文實驗結(jié)果的可信度．

5．1．1擴展性實驗本實驗考慮數(shù)據(jù)集合大小對優(yōu)化效果的影響，實驗采用由真實數(shù)據(jù)集DBLP數(shù)據(jù)集，選擇其中的title，authorandco－author，journalorurl這3個屬性，選擇大小分別為13．2MB、32．3MB、64．9MB、97．1MB、128．9MB的數(shù)據(jù)作為實驗數(shù)據(jù)．實驗中各屬性的權(quán)值分別為0．9、0．05、0．05，實驗結(jié)果如圖7所示．實驗中對比了基本的實現(xiàn)（Nave）、文獻(xiàn)［19］中的BlockSplit和PairRange與基于本文中任務(wù)合并的優(yōu)化方法優(yōu)化后的實體識別4種方法在不同數(shù)據(jù)集合大小下的運行結(jié)果．隨著數(shù)據(jù)集合的增大，優(yōu)化前后系統(tǒng)的運行時間都在增加，但是優(yōu)化前和優(yōu)化后系統(tǒng)運行時間的比值（加速比）均在2．3左右．這是因為本次實驗所使用的數(shù)據(jù)具有3個屬性，按照2．2節(jié)中對優(yōu)化效果的分析，應(yīng)具有的理論加速比為（5×3＋1）／6＝2．67與實驗結(jié)果一致．由于基于BlockSplit和Pair－Range方法的實體識別實現(xiàn)過程的運行時間比基于任務(wù)合并的優(yōu)化方法復(fù)雜，故其運行時間均比本文提出的優(yōu)化方法對應(yīng)的運行時間長．本實驗說明優(yōu)化設(shè)計方案有良好的擴展性．

5．1．2集群的并行化程度對優(yōu)化效果的影響實驗考慮集群中Reduce個數(shù)對優(yōu)化效果的影響，實驗采用由真實數(shù)據(jù)集DBLP數(shù)據(jù)集，選擇其中的title，authorandco－author，journalorurl這3個屬性，選擇大小分別為128．9MB含有100000條記錄的數(shù)據(jù)作為實驗數(shù)據(jù)．實驗中各屬性的權(quán)值分別為0．9、0．05、0．05，設(shè)置Reduce個數(shù)為2、4、6、8、10，實驗結(jié)果如圖8所示，在不同的并行化程度下優(yōu)化效果明顯．從圖8中可以看出系統(tǒng)運行時間隨并行化程度的增強而變長，這不符合大家普遍認(rèn)為的“并行化程度越高，系統(tǒng)運行時間越短”的常識．產(chǎn)生這一現(xiàn)象的原因是，實驗數(shù)據(jù)集數(shù)據(jù)量較小，增加系統(tǒng)的并行度給系統(tǒng)帶來的開銷要大于由此帶來的好處．無論如何，系統(tǒng)在不同的并行度下達(dá)到了大約2．3的加速比，優(yōu)化效果符合預(yù)期．5．1．3數(shù)據(jù)集的屬性個數(shù)對優(yōu)化效果的影響針對優(yōu)化方案的主要思想：充分利用輸入記錄中的所有屬性，設(shè)計了本實驗．實驗研究輸入元組中的屬性個數(shù)對優(yōu)化效果的影響．實驗結(jié)果如圖9所示，在處理同樣大小（記錄條數(shù)）的記錄時，隨著記錄中包含的屬性的增多，優(yōu)化效果越來越好．從上述數(shù)據(jù)可以看到：當(dāng)處理的元組包含一條屬性時，系統(tǒng)的優(yōu)化效果最差，比優(yōu)化前運行效率還要低；但是隨著屬性的增加優(yōu)化效果越來越好．本文的優(yōu)化工作針對的是系統(tǒng)在處理多屬性時不能充分利用輸入數(shù)據(jù)，并且通過循環(huán)處理每一個屬性增加了MapReduce輪數(shù)；但是處理單屬性元組時優(yōu)化后的方案產(chǎn)生的中間數(shù)據(jù)量多于優(yōu)化前，并且處理過程變得更加復(fù)雜，因此產(chǎn)生了上述實驗現(xiàn)象．

5．2不一致數(shù)據(jù)數(shù)據(jù)修復(fù)優(yōu)化實驗為了驗證系統(tǒng)在真實生產(chǎn)環(huán)境中的工作狀態(tài)，實驗采用來自真實數(shù)據(jù)集Adult的數(shù)據(jù)和由TPC－H生成的數(shù)據(jù)集．進(jìn)行了在Adult數(shù)據(jù)集上的加速比驗證實驗、在人工數(shù)據(jù)集上的擴展性和并行性驗證實驗．

5．2．1加速比實驗實驗采用條件函數(shù)依賴總共包含2條cfd，共有5條模式元組．根據(jù)cfd及其模式元組為來自Adult數(shù)據(jù)集中的無缺失值元組注入錯誤，使其違反一條或者多條約束．實驗條件和實驗結(jié)果如表9所示，通過實驗證明系統(tǒng)在真實數(shù)據(jù)集上的加速效果明顯，符合優(yōu)化方案設(shè)計預(yù)期．此次實驗加速比為1．39，理論加速比大于1．4，優(yōu)化效果符合預(yù)期．

5．2．2擴展性實驗為驗證優(yōu)化工作在不同大小的數(shù)據(jù)集上同樣有明顯的優(yōu)化效果設(shè)計了本實驗．實驗利用了由TPC－H生成的lineitem．tbl表中的5個屬性生成的數(shù)據(jù)集，CFDs由一條cfd包含2條tp構(gòu)成．實驗結(jié)果如圖9所示，可見隨著數(shù)據(jù)集合的增大優(yōu)化效果會變好，說明優(yōu)化設(shè)計方案有良好的擴展性．從圖9可以看出優(yōu)化前系統(tǒng)運行時間隨數(shù)據(jù)集增加呈線性增加，優(yōu)化后系統(tǒng)運行時間隨數(shù)據(jù)集的增加也呈線性增加，但前者的斜率更大．此外，系統(tǒng)優(yōu)化前后的加速比從1．59一直上升到2．20．一方面，優(yōu)化前各個模塊的計算任務(wù)相當(dāng)，但是優(yōu)化工作大大減輕了除不一致數(shù)據(jù)檢測與修復(fù)模塊之外各模塊的負(fù)載；另一方面，實驗中為了突出數(shù)據(jù)集的大小對系統(tǒng)運行時間的影響，僅設(shè)置Reduce個數(shù)為2，故隨著數(shù)據(jù)集的增大優(yōu)化前的系統(tǒng)率先滿負(fù)荷運行．從而出現(xiàn)了圖10中對比鮮明的實驗結(jié)果。

5．2．3并行性實驗為驗證并行程度對優(yōu)化效果的影響，設(shè)計了本實驗．實驗利用了由TPC－H生成的lineitem．tbl表中的5個屬性生成的數(shù)據(jù)集，CFDs由一條cfd包含2條tp構(gòu)成，詳見圖11．從圖10可以看出系統(tǒng)在并行度較低（Reduce個數(shù)為2）的情況下加速比最高達(dá)到2．20，之后隨著系統(tǒng)并行化程度增高優(yōu)化效果變差，加速比降低．并且優(yōu)化前的系統(tǒng)隨著系統(tǒng)的并行度的提高使得運行時間縮短，而優(yōu)化后的系統(tǒng)基本保持不變．這是因為優(yōu)化之前的系統(tǒng)處理數(shù)據(jù)的能力減弱，很容易滿負(fù)載運行，只能通過增加系統(tǒng)的并行化程度提高數(shù)據(jù)處理的效率，故隨著并行度增加系統(tǒng)運行時間減小；而優(yōu)化后的系統(tǒng)吞吐量大，與處理和前者相同的數(shù)據(jù)一直都沒有處于滿負(fù)載狀態(tài)運行，故增加系統(tǒng)的并行度帶來的好處不明顯．

5．3缺失值填充優(yōu)化實驗為了驗證系統(tǒng)在真實生產(chǎn)環(huán)境中的工作狀態(tài)，本文的實驗采用來自真實數(shù)據(jù)集Adult（www．a(chǎn)rchive．ics．uci．edu／ml／datasets．html）的數(shù)據(jù)和由TPC－H生成的數(shù)據(jù)集．進(jìn)行了在Adult數(shù)據(jù)集上的缺失率對優(yōu)化效果的驗證實驗、在人工數(shù)據(jù)集上的擴張性實驗和并行性驗證實驗．

5．3．1缺失率對優(yōu)化效果的影響實驗主要研究不同的數(shù)據(jù)缺失率對優(yōu)化結(jié)果的影響，通過將完整數(shù)據(jù)集按一定的比例（缺失率）隨機置空數(shù)據(jù)生成實驗所需的各種缺失率的數(shù)據(jù)．本文選取其中9個離散屬性，缺失屬性有7種取值，實驗結(jié)果見圖12．在圖中所示缺失率下，加速比穩(wěn)定在1．5左右，與本模塊的理論加速比3／2相吻合．

5．3．2擴展性驗證實驗本實驗利用由TPC－H生成的數(shù)據(jù)表lineitem．tbl選取其中5個屬性，分別選擇不同的記錄條數(shù)生成實驗所需的數(shù)據(jù)．圖13所示實驗結(jié)果表明，無論優(yōu)化前后，系統(tǒng)的運行時間均隨數(shù)據(jù)集的增大而增大，但是加速比均保持在1．5左右，與本模塊的理論加速比相吻合．

5．3．3并行性驗證實驗為了驗證系統(tǒng)在不同并行化程度下的優(yōu)化效果，設(shè)計了本實驗．實驗利用由TPC－H生成的lineitem．tbl數(shù)據(jù)表，數(shù)據(jù)表共包含5個屬性，3000000條元組．隨機置空數(shù)據(jù)表第1列5％的數(shù)據(jù)（缺失率5％），記錄在不同的并行化程度下系統(tǒng)的優(yōu)化效果．實驗結(jié)果見圖14．在給定數(shù)據(jù)集上，系統(tǒng)優(yōu)化前后的運行效率都未隨著并行化程度的提高而變好．這是因為對于特定大小的數(shù)據(jù)集最適宜的Reduce數(shù)目是確定的，一味地提高并行化程度只會給系統(tǒng)帶來更多地任務(wù)分配的開銷．無論如何，在不同的并行化程度下優(yōu)化效果明顯．

6結(jié)論

雖然整個行業(yè)對Hadoop的研究和使用已經(jīng)有了相當(dāng)?shù)姆e累，但是由于使用者對MapReduce編程框架理解不夠深刻，所以利用MapReduce設(shè)計的軟件系統(tǒng)大都效率低下．為此本文提出了一種針對MapReduce編程框架設(shè)計的系統(tǒng)的優(yōu)化方法，并通過了在海量數(shù)據(jù)清洗系統(tǒng)上的實施．本文提出的優(yōu)化方法僅需對原系統(tǒng)解決問題的思路稍作改動，幾乎不影響其算法復(fù)雜性，通過減少MapReduce輪數(shù)和IO次數(shù)達(dá)到優(yōu)化的目的．優(yōu)化方法簡單，實用性強．未來的工作包括將這種思想利用到更多基于MapReduce的系統(tǒng)中，對實驗結(jié)果進(jìn)行更為深入的分析以發(fā)現(xiàn)本文提供的優(yōu)化方法的不足從而提出更好的優(yōu)化方法．

作者：楊東華 李寧寧 王宏志 李建中 高宏 單位：哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院 哈爾濱工業(yè)大學(xué)基礎(chǔ)與交叉科學(xué)研究院