海量數(shù)據(jù)分析及處理算法實(shí)現(xiàn)

朱德新，宋雅娟

(長春大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長春 130022)

0 引言

隨著互聯(lián)網(wǎng)的飛速發(fā)展，尤其是近幾年來人們所掌握的數(shù)據(jù)量爆炸式增長，如何高效的處理海量數(shù)據(jù)已經(jīng)得到了全世界的廣泛研究。海量數(shù)據(jù)是一個形容詞，它是用來形容空前浩瀚的、巨大的數(shù)據(jù)?，F(xiàn)在很多業(yè)務(wù)部門都需要操作海量數(shù)據(jù)，如水利部門水利的數(shù)據(jù)，規(guī)劃部門規(guī)劃的數(shù)據(jù)，氣象部門氣象的數(shù)據(jù)，這些處理的數(shù)據(jù)量都非常大。它包括各種報(bào)表統(tǒng)計(jì)數(shù)據(jù)、空間數(shù)據(jù)、聲音、文字、超文本、圖像等各種環(huán)境和文化數(shù)據(jù)的信息。而這些數(shù)據(jù)又具有相當(dāng)高的使用價值，高效合理地使用這些海量數(shù)據(jù)，不僅可以掌握更多用戶潛在的需求，同時還可以為滿足人們更多需求而開發(fā)出更好的應(yīng)用。然而當(dāng)人們面對具有如此龐大而且信息量繼續(xù)爆炸增長的數(shù)據(jù)，想要非常高效的利用這些海量數(shù)據(jù)時才發(fā)現(xiàn)困難重重。在網(wǎng)絡(luò)時代，如何對海量數(shù)據(jù)進(jìn)行操作，這樣越來越多的挑戰(zhàn)需要靠卓越的算法來解決。

1 海量數(shù)據(jù)的存儲

數(shù)據(jù)中蘊(yùn)含著企業(yè)的財(cái)富，但是因?yàn)閿?shù)據(jù)量的增長速度過快，所以首先在客觀上逼迫企業(yè)必須實(shí)施海量存儲的解決方案。在這個階段過程中很多企業(yè)已經(jīng)完成方案，或者正在實(shí)施。目前，各個企業(yè)對文件型數(shù)據(jù)推出了不同的存儲方案，而采用文件服務(wù)器進(jìn)行文件數(shù)據(jù)存儲的仍然占據(jù)最多數(shù)，在總體企業(yè)中占據(jù)32.9%比例;應(yīng)用服務(wù)器內(nèi)置存儲空間存儲文件數(shù)據(jù)的企業(yè)占據(jù)21.8%的比例;16.3%的企業(yè)選擇了通過NAS網(wǎng)關(guān)共享SAN網(wǎng)絡(luò)存儲空間進(jìn)行文件數(shù)據(jù)存儲;還有13.1%的企業(yè)通過NAS網(wǎng)絡(luò)存儲來進(jìn)行文件存儲;10.1%的企業(yè)通過集群NAS解決文件存儲問題;表示應(yīng)用分布式文件系統(tǒng)解決文件存儲的企業(yè)占總體企業(yè)的9.2%;選擇多協(xié)議支持的統(tǒng)一存儲系統(tǒng)的企業(yè)占總體企業(yè)的3.9%;此外，還有16.9%的企業(yè)表示目前正在解決文件數(shù)據(jù)存儲的問題。

2 海量數(shù)據(jù)處理的研究現(xiàn)狀

面對著蘊(yùn)藏企業(yè)財(cái)富的海量數(shù)據(jù)，在實(shí)現(xiàn)存儲和檢索之后，如何把這些有用的數(shù)據(jù)整合起來，并加以提煉和分析，最終形成支持企業(yè)業(yè)務(wù)發(fā)展的一個決策呢?這就是如何對海量數(shù)據(jù)進(jìn)行處理的過程。

在過去二十年中，單機(jī)的性能有了很大的發(fā)展變化，尤其是CPU、內(nèi)存等硬件技術(shù)。但是這些硬件技術(shù)在理論上的發(fā)展是有限度的。如果說硬件的發(fā)展在縱向上提高了系統(tǒng)的系能，那并行技術(shù)的發(fā)展就是從橫向上拓展了處理的方式，例如如今的多核技術(shù)就是并行技術(shù)發(fā)展的一個實(shí)例［1］。在海量數(shù)據(jù)分析和處理上，并行數(shù)據(jù)處理方式是必不可少的。因?yàn)樗奶幚聿呗允恰胺侄沃?，這樣對于性能的延伸在理論上是沒有邊界的。在實(shí)際應(yīng)用中，現(xiàn)今比較主流的兩種并行數(shù)據(jù)處理技術(shù)就是MapReduce技術(shù)和并行數(shù)據(jù)庫技術(shù)。

2.1 MapReduce技術(shù)

MapReduce是在2004年，Google公司的Jeffrey Dean和Sanjay Ghemawat提出來的［2－3］。谷歌的搜索引擎，每一天都要處理數(shù)量龐大的網(wǎng)絡(luò)數(shù)據(jù)。根據(jù)客戶的搜索條件將采集來的數(shù)據(jù)進(jìn)行篩選，要求在一定的時間內(nèi)完成。MapReduce將并行編程中復(fù)雜的業(yè)務(wù)邏輯進(jìn)行抽象化。它在前面展現(xiàn)用于簡單的計(jì)算的接口，而對負(fù)責(zé)的并行化處理、數(shù)據(jù)分布、容錯、負(fù)載平衡和數(shù)據(jù)分布均進(jìn)行了隱藏。這樣很大程度上簡化了程序員對于分布式這樣程序的開發(fā)難度，每個程序只要用自己最熟練的并且能夠?qū)崿F(xiàn)數(shù)據(jù)處理的接口就可以了，而不需要考慮并行處理的每一個細(xì)節(jié)。MapReduce主要是Reduce和Map這兩個操作上的概念。Reduce操作是針對鍵值進(jìn)行簡單匯總操作。通過這種方式，將現(xiàn)實(shí)生活中的許多任務(wù)都能描述出來。Map操作主要是對一組輸入記錄進(jìn)行處理，處理方式是基于典型的key/value鍵值的方式。

2.2 并行數(shù)據(jù)庫技術(shù)

并行數(shù)據(jù)庫(Parallel Database System)是并行計(jì)算和數(shù)據(jù)庫技術(shù)相結(jié)合的產(chǎn)物［4］。隨著并行計(jì)算技術(shù)的發(fā)展，人們逐漸的認(rèn)識到通過空間或時間上的并行處理，能夠大大提高對任務(wù)的處理效率。并行計(jì)算可以分為任務(wù)并行和數(shù)據(jù)并行。任務(wù)并行處理會將任務(wù)的協(xié)調(diào)和管理變得非常復(fù)雜。而數(shù)據(jù)并行則是將一個大任務(wù)分解成多個相同的子任務(wù)，對比任務(wù)并行來說要容易處理。并行數(shù)據(jù)庫實(shí)質(zhì)上就是將數(shù)據(jù)并行處理的一種形式。一個數(shù)據(jù)庫系統(tǒng)關(guān)注的更多的是吞吐量和響應(yīng)時間，這兩者也是衡量一個數(shù)據(jù)庫系統(tǒng)性能的關(guān)鍵指標(biāo)［5］。前者用于在給定的時間段里能夠完成的任務(wù)數(shù)量，后者表示單個的任務(wù)從提交到完成一共需要多少時間。并行數(shù)據(jù)庫主要用于提高這兩點(diǎn)的性能。

2.3 多種數(shù)據(jù)格式支持原則

在海量數(shù)據(jù)的處理當(dāng)中，對于數(shù)據(jù)格式的限制，不應(yīng)該存在。因?yàn)樵趯?shí)際應(yīng)用當(dāng)中，各種格式的數(shù)據(jù)都有可能存在，比較常用的格式有:數(shù)據(jù)庫、多媒體、網(wǎng)頁、文本以及由其他應(yīng)用程序生成的數(shù)據(jù)。而在海量數(shù)據(jù)的分析處理過程中，可能要面對一種或幾種格式的數(shù)據(jù)。

2.4 S處理海量數(shù)據(jù)語言的選擇

在實(shí)際應(yīng)用中，對于一般的數(shù)據(jù)處理，往往需要使用數(shù)據(jù)庫。但是如果要對復(fù)雜的數(shù)據(jù)處理，則必須要借助程序。而要在程序操作數(shù)據(jù)庫和文本之間選擇的話，則要選擇程序操作文本。原因是該處理方法速度快;對文本處理不容易出錯;文本的存儲不受限制于文本的格式等。例如一些海量的網(wǎng)絡(luò)日志都是文本或者csv格式，對它進(jìn)行處理則會涉及到多余數(shù)據(jù)清除，是需要利用程序進(jìn)行處理的，而不建議導(dǎo)入數(shù)據(jù)庫再做處理。

處理數(shù)據(jù)離不開好的程序代碼，尤其在處理復(fù)雜數(shù)據(jù)時，必須使用程序。程序代碼對數(shù)據(jù)的處理非常重要，這不僅是數(shù)據(jù)處理準(zhǔn)確性的問題，更是數(shù)據(jù)處理的效率問題。優(yōu)秀的程序代碼應(yīng)該包含好的處理流程、好的算法、好的異常處理機(jī)制、好的效率等。當(dāng)數(shù)據(jù)量非常大時，選擇語言就需要慎重了。因?yàn)槊糠N語言都有各自不同的特點(diǎn)，所以就需要在編程時間和運(yùn)行時間之間進(jìn)行權(quán)衡。遍歷處理所有數(shù)據(jù)時，腳本語言處理就不合適了。因?yàn)槟_本語言的運(yùn)行時間非常長，不能夠讓人接受。另外，對于內(nèi)存使用和文件讀寫，程序都沒法控制。不幸的是，很少語言會為處理海量文件做優(yōu)化。這時，C/C++是最好的選擇。

3 處理海量數(shù)據(jù)的算法實(shí)現(xiàn)

該算法中，處理海量數(shù)據(jù)主要分為兩部分。第一部分是對海量數(shù)據(jù)的讀取。該階段的算法可應(yīng)用于任何類型的文本文件中，數(shù)據(jù)以字符為單位從文件中讀取出來。第二部分是對海量數(shù)據(jù)的分析。而分析過程則需要根據(jù)文件的格式類型進(jìn)行不同的處理。筆者處理數(shù)據(jù)的文件是.csv格式，文件的大小至少在25M以上，共有152049行，81列，文件的內(nèi)容格式如圖1所示。該算法的執(zhí)行時間大約為7s。

圖1 文件內(nèi)容形式

3.1 海量數(shù)據(jù)的讀取

該階段將文件映射對象映射到當(dāng)前應(yīng)用程序的地址空間中，并根據(jù)文件的大小，將數(shù)據(jù)以字符為單位讀取出來。流程圖如圖2。

圖2 讀取海量數(shù)據(jù)

3.2 海量數(shù)據(jù)的分析

該階段是圖2中對視圖數(shù)據(jù)處理這個過程。處理文件的格式為.csv格式，該文件的特點(diǎn)是數(shù)據(jù)以逗號作為分隔符，每一行結(jié)束符為回車換行。處理過程將圖1中每一個時間戳內(nèi)有效數(shù)據(jù)(浮點(diǎn)數(shù))分析出來，并將有效數(shù)據(jù)時間戳數(shù)以及一個時間戳內(nèi)的行值、列值、最左點(diǎn)、最右點(diǎn)、最上點(diǎn)、最下點(diǎn)等信息提取出來。流程圖如圖3。

圖3 海量數(shù)據(jù)處理

該算法執(zhí)行海量數(shù)據(jù)的結(jié)果如圖4、圖5所示。

圖4 顯示執(zhí)行時間

圖5 提取有效數(shù)據(jù)結(jié)果

4 結(jié)語

本文從現(xiàn)實(shí)問題出發(fā)，就當(dāng)前海量數(shù)據(jù)分析處理難題，進(jìn)行了方法上的簡單探討。并根據(jù)存儲海量數(shù)據(jù)的文件格式，設(shè)計(jì)了算法。通過對算法在執(zhí)行效率和分析有效數(shù)據(jù)上的驗(yàn)證，該算法快捷有效，能夠比較好的對海量數(shù)據(jù)進(jìn)行處理。

［1］陳康，鄭緯民.云計(jì)算:系統(tǒng)實(shí)例與研究現(xiàn)狀［J］.軟件學(xué)報(bào)，2009，20(5):1337－1348.

［2］J.Dean and S.Ghemawat.MapReduce:Simplified data processing on largeclusters［M］.In Proc.OSDI，2004.

［3］David J.DeWitt，Jim Gray.Parallel Database Systems［M］.The Future of High Performance Database Processing，1992.

［4］Ben Lorica.HadoopDB［M］.An Open Source Parallel Database.2009.