李　哲，李虎俊，張?zhí)旆?/p>

(1.湖北工程學院 新技術(shù)學院，湖北 孝感 432000; 2. 湖北職業(yè)技術(shù)學院 繼續(xù)教育學院，湖北 孝感 432000；

3.西北工業(yè)大學 自動化學院，陜西 西安 710072)

基于MapReduce海量視頻數(shù)據(jù)并行計算系統(tǒng)的設(shè)計

李哲1，3，李虎俊2，張?zhí)旆?，3

(1.湖北工程學院 新技術(shù)學院，湖北 孝感 432000; 2. 湖北職業(yè)技術(shù)學院 繼續(xù)教育學院，湖北 孝感 432000；

3.西北工業(yè)大學 自動化學院，陜西 西安 710072)

摘要：在總結(jié)視頻圖像數(shù)據(jù)處理現(xiàn)狀的基礎(chǔ)上，針對海量視頻數(shù)據(jù)的并行化處理問題，提出一種基于MapReduce的并行計算系統(tǒng)設(shè)計方法。該系統(tǒng)使用NVIDIA JETSON TK1搭建并行計算集群，在此基礎(chǔ)上利用Hadoop實現(xiàn)了MapReduce。 在此平臺上設(shè)計基于CUDA的并行數(shù)據(jù)處理算法對千萬條文本數(shù)據(jù)進行處理，分析了其數(shù)據(jù)裝載時間、處理時間和全部任務(wù)處理時間。結(jié)果表明，該系統(tǒng)當前加速比約為4.73，與C/S單機相比，處理速度有較大程度的提高，為實現(xiàn)實時海量視頻圖像處理奠定了良好基礎(chǔ)。

關(guān)鍵詞：并行計算；海量視頻數(shù)據(jù)；MapReduce；Hadoop

中圖分類號：TP311.11

文獻標志碼：碼：A

文章編號：號：2095-4824(2015)06-0026-06

收稿日期：2015-09-17

基金項目：湖北工程學院自然科學基金(2013016,201515)；湖北工程學院新技術(shù)學院自然科學基金(Hgxky14)；湖

作者簡介：李哲(1986-)，男，湖北漢川人，湖北工程學院新技術(shù)學院講師，博士研究生。

Abstract：On the summary of the status of video image processing, this paper proposes a parallel processing method for the parallel processing of massive video data which is based on parallel processing system by using the MapReduce technique. This system utilizes the NVIDIA JETSON TK1 to build parallel computation clusters and employs the Hadoop to perform the MapReduce. With the developed platform, a CUDA based parallel processing algorithm is designed to process tens of millions of text data for the analysis of the data loading time, the processing time of each task and the processing time of all tasks. The test results indicate that the acceleration rate of the system is about 4.73, which is much higher than the C/S mode in a single computer and offers a good foundation for the implementation of real-time massive video data processing.

當今，世界范圍的信息化變革幾乎使每個行業(yè)都面臨著大數(shù)據(jù)(Big Data)問題[1]。大數(shù)據(jù)及其應(yīng)用也一直是學術(shù)界關(guān)注的熱點問題。由于大數(shù)據(jù)具有體量大、速度快和異構(gòu)性的特點，給數(shù)據(jù)的存儲、管理和分析帶來了巨大挑戰(zhàn)。特別在處理視頻圖像等非結(jié)構(gòu)化數(shù)據(jù)方面上述問題尤為突出。因此，如何處理好視頻圖像數(shù)據(jù)對于大數(shù)據(jù)應(yīng)用具有相當重要的意義。

1視頻圖像數(shù)據(jù)處理的現(xiàn)狀分析

(1)數(shù)據(jù)存儲密度不強，圖像壓縮算法適用性低。由于圖像和視頻屬于非結(jié)構(gòu)化數(shù)據(jù)，因此無法采用類似結(jié)構(gòu)化數(shù)據(jù)的方法進行壓縮。特別是視頻數(shù)據(jù)帶有時間三維結(jié)構(gòu)，在某些應(yīng)用必須保證足夠的數(shù)據(jù)有效性[2]。如視頻監(jiān)控數(shù)據(jù)必須保證足夠的清晰度，以便后期對監(jiān)控內(nèi)容和細節(jié)信息(如車牌號、人物特征等)進行追蹤挖掘。因此，如何在保證足夠清晰度及時間維度的前提下，高效存儲海量視頻數(shù)據(jù)一直是人們的研究熱點。盡管出現(xiàn)了MPEG等動態(tài)圖像壓縮算法，但面對如“天網(wǎng)”工程所涉及的公共安全視頻數(shù)據(jù)而言，常規(guī)的數(shù)據(jù)壓縮算法仍存在明顯不足。

(2)數(shù)據(jù)運算量巨大，常規(guī)CPU計算不足。圖像視頻數(shù)據(jù)量巨大，常規(guī)CPU面向的是通用性任務(wù)處理[3]，其在處理圖像視頻這樣密集性浮點運算時表現(xiàn)遠不如GPU。根據(jù)文獻[1]的分析表明，早在2012年，GPU的計算能力已經(jīng)達到了3 gigaFLOPS，遠遠超出CPU的計算能力。因此，當前及未來圖像數(shù)據(jù)處理的發(fā)展向著CPU-GPU混合計算方向發(fā)展。CPU與GPU計算能力的發(fā)展如圖1所示。

(3)常規(guī)系統(tǒng)建設(shè)成本高，功耗大，使用率低。雖然如美國橡樹嶺實驗室的“泰坦”以及我國的“天河二號”是世界最強超級計算機的代表，具有

北省公安廳自主科研項目(鄂公傳發(fā)【2015】70號)

李虎俊(1958-)，男，湖北漢川人，湖北職業(yè)技術(shù)學院繼續(xù)教育學院副教授。

張?zhí)旆?1982-)，男，湖北孝感人，湖北工程學院新技術(shù)學院講師，博士研究生。

無與倫比的運算能力，能夠滿足海量數(shù)據(jù)的處理要求，但是這類超算系統(tǒng)往往建造成本巨大(僅“泰坦”二期升級就花費了9 000萬美元)，而且功耗巨大(“泰坦”全速運轉(zhuǎn)功耗約為900 MW)[4]，一般企業(yè)及個人用戶不太可能承受如此高昂的建造和運行成本。

圖1　CPU&&GPU計算能力發(fā)展

針對典型視頻格式主要有三種處理平臺，分別是Intel的Quick Sync Video，ADM的APP和NVIDIA的CUDA。對這三個平臺進行基礎(chǔ)的性能測試，測試結(jié)果如表1所示。

表1　視頻處理加速平臺常規(guī)指標測試表

注：視頻源規(guī)格：1080P、H.263、碼率28 Mbps、文件大小3579 MB，目標格式MP4、H.264碼率4 Mbps

根據(jù)對某市“天網(wǎng)工程”視頻監(jiān)控系統(tǒng)的詳細調(diào)查，發(fā)現(xiàn)每天產(chǎn)生的數(shù)據(jù)峰值為33TB，按上述三個方案分別需要77套、106套和160套系統(tǒng)以并行方式處理才能滿足實時處理的要求，而所需建造系統(tǒng)的成本分別為37、30、75萬元，總功耗方面分別為12 kW.h、9 kW.h和27 kW.h。不難看出Intel和NVIDIA具有較明顯的優(yōu)勢，但從實際中Intel的報價來看，其建造成本相比TK1系統(tǒng)要高出不少，這也是本項目選用NVIDIA JETSON TK1構(gòu)建計算集群的重要原因。

根據(jù)以上問題，本文研究海量數(shù)據(jù)(圖像/視頻)的存儲和管理，為后期研究基于視頻的內(nèi)容分析與挖掘建立相應(yīng)的技術(shù)平臺。其中并行計算模型系統(tǒng)軟件部分選擇MapReduce，具體計算框架為Hadoop，硬件部分選用NVIDIA JETSON TK1(ARM處理器+NVIDIA GPU)構(gòu)建并行計算集群。最后，利用CUDA技術(shù)優(yōu)化海量視頻數(shù)據(jù)的壓縮過程。經(jīng)過測試，該系統(tǒng)與C/S單機處理相比，能明顯提高海量數(shù)據(jù)的處理速度，為后期實現(xiàn)實時海量視頻圖像處理奠定了良好基礎(chǔ)。

2MapReduce相關(guān)技術(shù)

2.1MapReduce并行計算模型

Google于2004年提出了MapReduce，用于在大規(guī)模計算機集群上處理海量數(shù)據(jù)的并行計算[5-6]。MapReduce是一種基于鍵/值對的數(shù)據(jù)模型，該模型將復雜的分布式計算歸結(jié)為兩個階段：Map階段和Reduce階段。Map階段通常在數(shù)據(jù)存放本地進行計算，然后將Map輸出結(jié)果按鍵值映射到相應(yīng)的Reduce 任務(wù)中。Reduce 階段對Map 階段結(jié)果匯總計算，從而得出最終計算結(jié)果。MapReduce 模型優(yōu)勢在于簡單易用，靈活性高，獨立于云數(shù)據(jù)庫系統(tǒng)，且容錯能力強[7]。MapReduce設(shè)計了分布式文件系統(tǒng)DFS(Distributed File System)，將數(shù)據(jù)分割成特定大小的數(shù)據(jù)塊，計算節(jié)點則處理距離其最近的數(shù)據(jù)塊，從而能獲得更高的數(shù)據(jù)可靠性和更快的數(shù)據(jù)訪問速度。MapReduce典型應(yīng)用流程圖如圖2所示。

圖2　典型的MapReduce應(yīng)用流程圖

2.2HDFS分布式存儲系統(tǒng)

作為MapReduce的具體實現(xiàn)，Hadoop分別實現(xiàn)了分布式文件管理系統(tǒng)對應(yīng)的Google文件系統(tǒng)(Google File System)、映射/規(guī)約模型、混合性大數(shù)據(jù)庫系統(tǒng)。Hadoop的實現(xiàn)得到廣大開源用戶的支持，本系統(tǒng)選用了Hadoop作為MapReduce的具體實現(xiàn)。

盡管Hadoop實現(xiàn)了MapReduce，并且能夠?qū)?shù)據(jù)和任務(wù)進行分布式部署，但分布后的任務(wù)與具體算法實現(xiàn)仍然需要程序員編寫，因此需要在“微觀“層面開發(fā)具體的數(shù)據(jù)處理程序。由于典型的處理程序要么是單線程的，要么利用多線程技術(shù)發(fā)揮多核CPU的運算能力。但面對如視頻等數(shù)據(jù)密集型的非結(jié)構(gòu)化數(shù)據(jù)處理，CPU的處理效率明顯降低。在圖像處理領(lǐng)域NVIDIA推出了統(tǒng)一計算設(shè)備架構(gòu)(Compute Unified Device Architecture，CUDA)，這是一種通用并行計算架構(gòu)，該架構(gòu)使得GPU能夠解決類似圖像處理等復雜的計算問題。因此在CUDA的基礎(chǔ)上優(yōu)化海量視頻數(shù)據(jù)的壓縮過程，能夠有效應(yīng)對海量視頻數(shù)據(jù)的管理和壓縮存儲要求。

3系統(tǒng)設(shè)計

3.1系統(tǒng)框架設(shè)計

選用NVIDIA JETSON TK1搭建并行計算集群，系統(tǒng)硬件結(jié)構(gòu)總體框架圖如圖3所示。

圖3　系統(tǒng)硬件結(jié)構(gòu)總體框架圖

在系統(tǒng)硬件結(jié)構(gòu)中，每個節(jié)點的核心TK1處理器部分包含四個ARM-A15內(nèi)核，而GPU部分由192個CUDA組成，并且使用了與“泰坦”相同的“Kepler”超算架構(gòu)。而單個TK1節(jié)點的零售價格僅為1600元，功耗低至10 W，完全滿足系統(tǒng)設(shè)定的視頻數(shù)據(jù)處理與分析的基本要求。多個節(jié)點配合監(jiān)控主機和網(wǎng)絡(luò)通訊設(shè)備構(gòu)成并行計算集群，最終系統(tǒng)由兩個子集群構(gòu)成，每個集群擁有48個節(jié)點，其部署示意圖如圖4所示。

圖4　“天網(wǎng)”工程雙集群系統(tǒng)部署示意圖

該系統(tǒng)能夠有效地對視頻任務(wù)進行處理，根據(jù)示范應(yīng)用單位具體需求，該系統(tǒng)原型機已于2015年5月裝配完畢，系統(tǒng)實物如圖5所示。

圖5　嵌入式并行計算系統(tǒng)“Medusa”原型機

為了對海量數(shù)據(jù)以及并行計算系統(tǒng)集群進行有效管理，該系統(tǒng)上選用了Google的MapReduce作為全局分布式任務(wù)管理框架，使用Hadoop的HDFS分布式文件管理系統(tǒng)實現(xiàn)海量數(shù)據(jù)的可靠存儲，在該基礎(chǔ)上編寫了基于CUDA的并行數(shù)據(jù)處理算法，系統(tǒng)文件存儲框架圖如圖6所示。

圖6　基于HDFS的分布式數(shù)據(jù)存儲框架圖

3.2系統(tǒng)處理流程

對系統(tǒng)原型機基本功能進行測試，測試數(shù)據(jù)選用20 GB文本數(shù)據(jù)進行排序，排序過程在嵌入式系統(tǒng)上部署Hadoop的方式來進行處理。

首先，通過NameNode或者外部分發(fā)數(shù)據(jù)，將數(shù)據(jù)分發(fā)到各個處理單元。從邏輯上而言，采用從NameNode上傳數(shù)據(jù)到虛擬的共享空間HDFS中；從物理上而言，實際的文件存儲機器為Slave l～Slave N，namenode僅負責對整個HDFS邏輯空間的維護，并不參與存儲。數(shù)據(jù)的分發(fā)存儲如圖7所示。

圖7　數(shù)據(jù)分發(fā)存儲

在數(shù)據(jù)分發(fā)過程中，將會產(chǎn)生兩個方面的時間損耗。一是傳輸時間，另一個是將數(shù)據(jù)寫入到每個Node的時間。但在傳輸?shù)牡谝粋€時間周期過后，傳輸與數(shù)據(jù)寫入是并行的，之后利用MapReduce框架對數(shù)據(jù)進行排序。

在Map端，結(jié)果文件優(yōu)先存儲在默認大小為100 MB的內(nèi)存緩沖區(qū)，通過減少磁盤IO提高整體性能，直到該區(qū)溢出后才將溢出數(shù)據(jù)存放到磁盤中(見圖9中雙緩存機制是該機制的擴展)。當整個map過程完成后，緩沖區(qū)與磁盤中的所有臨時文件將合并生成最終的結(jié)果文件，而reduce task則負責對這些以key-value形式組織的結(jié)果文件進行最終匯總。

每當緩沖區(qū)收集默認為100 MB的數(shù)據(jù)時，緩沖區(qū)的數(shù)據(jù)將會寫入磁盤，然后重新利用這塊緩沖區(qū)進行，這個過程被稱為Spill(也叫做溢寫)。該過程是一個新的線程，與原有的Map線程并行進行。默認的溢寫閥值為0.8，即在默認配置下當緩沖區(qū)寫入80 MB數(shù)據(jù)后，就由溢寫線程將該組數(shù)據(jù)進行排序，而map task則繼續(xù)使用剩余的空間。MapReduce提供了默認的排序算法，在后正理中本文將利用如Apriori算法和并行SON算法提高系統(tǒng)相關(guān)性能。

當Map端任務(wù)完成且將結(jié)果存放于Slave中指定的目錄后，所有的reduce task將通過Job Tracker進行map task的完整性驗證。如果完整，則執(zhí)行merge文件合并過程，如果驗證失敗，則要求該Map將該任務(wù)分配給其他節(jié)點重新執(zhí)行任務(wù)，直到所有任務(wù)完成。整個map-shuffer過程如圖8所示。

圖8　map shuffer過程

4系統(tǒng)測試及結(jié)果分析

4.1系統(tǒng)測試

(1)準備數(shù)據(jù)。原型機完成后使用千萬條文本數(shù)據(jù)(約20 GB)進行全文分析。編寫基于MapReduce框架下分布式數(shù)據(jù)處理程序。該程序的算法由RandomSelectMapper和RandomSelectReducer完成數(shù)據(jù)抽取，由ReudcerPatition完成數(shù)據(jù)劃分，由SortMapper和SortReducer用于數(shù)據(jù)結(jié)果的輸出。并行處理模型與基礎(chǔ)模型最大的區(qū)別在于并行處理模型在接收數(shù)據(jù)的同時，就可以開始(在雙緩沖數(shù)據(jù)處理功能支持下)排序(內(nèi)部排序)，其結(jié)構(gòu)如圖9所示。

圖9　并行處理模型

由圖9可以看出，將原有的B3、B4步驟去掉，轉(zhuǎn)而將B2通過B3X直接鏈接到B5過程，那么B1～B3X～B6就構(gòu)成一個新處理步驟，此部分速率關(guān)系為B3X=B5>B1>B6>B2，時間基準為B2，也可以得到該模型的整體時間公式為：

TD=B2+B9

(1)

根據(jù)數(shù)學模型定義式(1)可改寫為：

(2)

(2)搭建嵌入式系統(tǒng)集群環(huán)境。當主機啟動后，需在主機端使用start-all.sh命令開啟hadoop分布式集群系統(tǒng)，當節(jié)點初始化完畢后，將逐個加入到主節(jié)點中監(jiān)管，當有31個節(jié)點接入集群中時，主節(jié)點監(jiān)管結(jié)果如圖10所示。

圖10　Hadoop Master Map/Reduce Administration

每個節(jié)點剩余外部存儲空間映射到的Linux系統(tǒng)/usr/hadoop/tmp/dfs路徑下，以分布式方式構(gòu)成了56.26 GB的全局訪問空間，如圖11所示。

(3)任務(wù)運行監(jiān)視。使用活動任務(wù)監(jiān)視工具(Running Job)在主節(jié)點或監(jiān)控終端的瀏覽器中查看當前任務(wù)執(zhí)行的狀態(tài)(在瀏覽器192.168.1.132:50070上運行Running Job)，如圖12所示。

圖11　NameNode’Master.Hadoop:9000’

圖12　主節(jié)點(Master)上查看任務(wù)執(zhí)行狀態(tài)

最后，當數(shù)據(jù)處理完畢后，從節(jié)點將退出處理過程并在監(jiān)視終端中顯示其執(zhí)行結(jié)果，當Map-Reduce過程完畢后，分節(jié)點的結(jié)果數(shù)據(jù)將會匯總到主節(jié)點的output目下，如圖13所示。

圖13　從節(jié)點運行結(jié)果在主節(jié)點匯聚為一個結(jié)果文件

在圖13中part-r-00000文件為最終結(jié)果匯總文件，而part-r-00001～00008文件是從節(jié)點文件，當數(shù)據(jù)匯總完成后從節(jié)點文件將清空，顯示為0 Byte。

4.2結(jié)果分析

在C/S構(gòu)架和Hadoop集群兩種模型下測試，分別對三類測試數(shù)據(jù)進行測試，并通過比較數(shù)據(jù)裝載時間、處理時間和全部任務(wù)處理時間進行性能分析，其中測試數(shù)據(jù)如表2所示。

表2　兩類系統(tǒng)模型測試結(jié)果一覽表

圖14是數(shù)據(jù)裝載時間、處理時間以及全部任務(wù)耗時對比結(jié)果。

圖14　數(shù)據(jù)裝載時間對比圖

由圖14的對比結(jié)果可知：

1)兩種模式在數(shù)據(jù)傳輸上消耗的時間均比理想時間要多，其中C/S模型消耗的時間主要開銷為網(wǎng)絡(luò)帶寬及傳輸控制協(xié)議的損失，而Hadoop集群在數(shù)據(jù)分割和任務(wù)分派方面消耗了較多時間；

2)在數(shù)據(jù)處理過程中，由于Hadoop采用的是并行結(jié)構(gòu)，而C/S模型是單機四核四線程并行方式，Hadoop總體上要比C/S單機方式運行速度快，根據(jù)測試數(shù)據(jù)表2可得加速比如表3所示。采用Hadoop集群處理平均加速比約為4.73，與理論加速比為31/4=7.75仍有較大差距，這也是未來對算法進行改進的重要性能指標。

3)任務(wù)處理所占時間非常小，僅為整個任務(wù)處理的1%左右，因此將數(shù)據(jù)駐留在節(jié)點重復利用，可大幅度提高系統(tǒng)的運行效率。

4)在進行視頻處理時，在任務(wù)級并行處理模式下無需將處理后的數(shù)據(jù)回傳給監(jiān)控主節(jié)點，從而減少數(shù)據(jù)回傳給主節(jié)點造成的通信擁塞。

表3　C/S模型與Hadoop集群的加速比

5總結(jié)

本文詳細闡述了組建基于MapReduce計算框架并通過Hadoop具體實現(xiàn)并行計算集群的過程，實現(xiàn)了HDFS有效將數(shù)據(jù)和數(shù)據(jù)程序分布到各節(jié)點進行處理并將處理結(jié)果反饋給主機并行處理算法，通過海量文本數(shù)據(jù)全文分析對該分布式處理模型的有效性進行了驗證。結(jié)果表明，該系統(tǒng)加速比約為4.73，與單機處理方式相比，處理速度有較大程度的提高，為后期實現(xiàn)實時海量圖像處理奠定了基礎(chǔ)。

[參考文獻]

[1]CCF 大數(shù)據(jù)專家委員會. 大數(shù)據(jù)熱點問題與2013 年發(fā)展趨勢分析[J].中國計算機學會通訊, 2012, 8(12): 40-44.

[2]于戈, 谷峪, 鮑玉斌, 等. 云計算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)[J].計算機學報, 2011, 34 (10): 1753-1767.

[3]孟小峰，余力.用社會化方法計算社會[J].中國計算機學會通訊, 2011, 7(12): 25-30.

[4]李哲，慕德俊，郭藍天，等.嵌入式多處理器系統(tǒng)混合調(diào)度機制的研究[J].西北工業(yè)大學學報，2014，33(1)：50-56.

[5]Lee K H, Lee Y J, Choi H, et al. Parallel data processing with MapReduce: a survey[C]//Proceedings of the ACM SIGMOD Record, 2012, 40(4): 11-20.

[6]肖韜.基于MapReduce的信息檢索相關(guān)算法[D].南京：南京大學，2012.

[7]覃雄派, 王會舉, 杜小勇, 等. 大數(shù)據(jù)分析——RDBMS 與 MapReduce 的競爭與共生[J].軟件學報, 2012, 23(1): 32-45.

Research and Design of MapReduce Based Massive

Video Data Parallel Processing System

Li Zhe1,3，Li Hujun2,Zhang Tianfan1,3

(1.CollegeofTechnology，HubeiEngineeringUniversity,Xiaogan,Hubei432000,China；

2.SchoolofContinuingEducation,HubeiPolytechnicInstitute,Xiaogan,Hubei432000,China;

3.SchoolofAutomation,NorthwesternPolytechnicalUniversity,Xi'an,Shaanxi710072,China)

Key Words：parallel computing; massive video data; MapReduce; Hadoop

(責任編輯：張凱兵)