交通信息分布式處理中的Hadoop調(diào)度算法優(yōu)化

孫衛(wèi)真，王秀錦，徐遠(yuǎn)超

（首都師范大學(xué)信息工程學(xué)院，北京100048）

0 引 言

隨著交通信息采集技術(shù)的改進(jìn)和發(fā)展，城市交通數(shù)據(jù)量迅速增長。經(jīng)過2008年奧運會，京交會及園博會等大型社團(tuán)活動的交通數(shù)據(jù)多年的積累，以及出租車行業(yè)，特種行業(yè)浮動車的數(shù)據(jù)匯集，交通數(shù)據(jù)量大且復(fù)雜，地理分布廣泛，數(shù)量已達(dá)到并超過PB級。因此，對這些交通數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘和建模、實時提取和處理進(jìn)而反饋誘導(dǎo)和交通控制已經(jīng)成為智慧城市的必需。利用分布式計算任務(wù)調(diào)度服務(wù)程序?qū)崿F(xiàn)計算機(jī)集群資源的統(tǒng)一調(diào)度是提高交通信息提取和分析準(zhǔn)確率以及信息實時性的有效方法。

Map Reduce（映射和化簡）［1］是分布式計算框架中最為通用和重要的一個，其開源實現(xiàn)Hadoop（分布式處理軟件框架計算平臺）技術(shù)自發(fā)布以來就得到廣泛的推廣和應(yīng)用。該平臺不僅開源而且適合將各種資源、數(shù)據(jù)等部署在廉價的計算機(jī)上進(jìn)行分布式存儲和分布式管理［1］。

城市智能交通系統(tǒng)要將海量的交通信息在數(shù)據(jù)處理平臺上快速地部署和任務(wù)調(diào)度，以便為出行者提供及時有效的交通信息，滿足用戶的實時性要求。Hadoop是用于對海量數(shù)據(jù)進(jìn)行分布式處理的并行系統(tǒng)，在大型集群上對數(shù)以萬計的作業(yè)和任務(wù)執(zhí)行調(diào)度，要想使得系統(tǒng)能夠高效完成用戶提交的任務(wù)，就需要對平臺的調(diào)度算法進(jìn)行優(yōu)化，以期獲得較好的運算效率。

為了提高Hadoop平臺對海量交通數(shù)據(jù)的處理能力，在開源框架Hadoop性能以及智能交通數(shù)據(jù)處理算法的基礎(chǔ)上，針對城市交通數(shù)據(jù)特點，提出了適合不同交通數(shù)據(jù)類型的改進(jìn)型計算能力調(diào)度算法，以期提高海量智能交通數(shù)據(jù)的處理效率。

1 分布式調(diào)度算法

當(dāng)前Hadoop平臺下最常用的作業(yè)調(diào)度算法有FIFO（先進(jìn)先出調(diào)度）算法、fair scheduler（公平調(diào)度）算法和capacity scheduler（計算能力調(diào)度）算法3種。在分布式系統(tǒng)中，作業(yè)的調(diào)度以及計算能力的均衡和計算節(jié)點的效率是衡量一個算法優(yōu)劣的主要指標(biāo)，提高分布式計算的效率也必然從這幾個方面對調(diào)度算法進(jìn)行改進(jìn)。Zaharia M等人針對多用戶并發(fā)作業(yè)提出了一種基于細(xì)粒度資源共享的公平調(diào)度算法——Quincy，在數(shù)據(jù)量減少一小部分的情況下可大幅度提升集群的吞吐率［2］；2010年Isard M等人使用600臺計算機(jī)組成的集群，通過處理Facebook數(shù)據(jù)證明公平調(diào)度與數(shù)據(jù)的本地化是一對矛盾體，并且在公平調(diào)度算法的基礎(chǔ)上加入了延時調(diào)度的思想，大幅度提升了數(shù)據(jù)的本地化比例［3］；Yahoo公司開發(fā)的“計算能力調(diào)度算法”模擬出具有指定計算能力的獨立的集群資源為不同用戶作業(yè)提供服務(wù)，此算法分為隊列間的調(diào)度和隊列內(nèi)調(diào)度［4，5］。多個隊列可以保證每個隊列的計算能力，并且計算能力調(diào)度是一種基于資源的調(diào)度，計算更具有靈活性。

但是計算能力調(diào)度算法沒有全面考慮用戶多樣性的特點，在單隊列中的調(diào)度仍然采用的是先進(jìn)先出的策略；另外交通信息的實時性和緊急性決定了在處理此類信息的算法中必須具有很強(qiáng)的交互性，并且算法的實時性與本地化計算比例密切相關(guān)。

所以針對交通信息數(shù)據(jù)的特殊性，調(diào)度隊列在分配作業(yè)時需要有更好的匹配策略［4，6］；交通數(shù)據(jù)短作業(yè)較多，作業(yè)類型不同，所以作業(yè)之間的相互依賴關(guān)系會變得更加復(fù)雜，這也勢必會增加計算中的延時［7］。因此在分布式系統(tǒng)中處理交通數(shù)據(jù)，需要根據(jù)城市交通的特點設(shè)計出適合其應(yīng)用的調(diào)度算法，從而提高資源的利用率，提高平臺的計算效率。

2 Hadoop調(diào)度算法及優(yōu)化

基于對分布式作業(yè)調(diào)度算法的研究以及對城市交通信息數(shù)據(jù)的分析，針對大規(guī)模分布式離散的交通信息處理提出了基于計算能力調(diào)度算法的改進(jìn)算法，即在原算法的基礎(chǔ)上加入了多種作業(yè)調(diào)度的策略，包括先進(jìn)先出結(jié)合短作業(yè)策略、緊急搶斷策略、作業(yè)隊列匹配策略和延時調(diào)度策略。改進(jìn)后的算法繼承了經(jīng)典計算能力調(diào)度算法多隊列作業(yè)調(diào)度模型所具有的穩(wěn)定性、擴(kuò)展性和并行性好的優(yōu)勢，并對交通信息數(shù)據(jù)的處理具有針對性。

計算能力調(diào)度算法支持多個隊列，以保證其計算能力，考慮到交通信息中用戶具有多樣性，設(shè)計隊列時按不同類型簡單劃分為長作業(yè)隊列和短作業(yè)隊列，長作業(yè)隊列專門處理大作業(yè)，短作業(yè)隊列可專門處理小作業(yè)，這樣對作業(yè)的處理針對性強(qiáng)，可提高作業(yè)處理效率。隊列劃分的實現(xiàn)需要額外設(shè)計一個作業(yè)篩選器，專門負(fù)責(zé)將作業(yè)劃分歸類，歸類流程如圖1所示。

圖1 隊列與作業(yè)劃分匹配篩選

篩選器在初始化隊列時將隊列根據(jù)需要劃分成長時作業(yè)隊列與短時作業(yè)隊列，作業(yè)調(diào)度器收納作業(yè)，將不同的作業(yè)類型分別排隊，形成不同類型的作業(yè)隊列。同時對隊列類型的屬性做一些配置上的優(yōu)化，比如短作業(yè)類型的隊列，此種作業(yè)規(guī)模比較小，但往往比較多且雜，可以在初始化時將min Map和min Reduce參數(shù)調(diào)整為較大值。針對交通數(shù)據(jù)而言，經(jīng)初步統(tǒng)計這樣的作業(yè)占據(jù)大多數(shù)，所以資源分配的比重相應(yīng)也較大。通過改變參數(shù)值和加權(quán)處理，不同類型的作業(yè)在執(zhí)行時變得有序、高效，而且能夠取得較好的交互性。

在經(jīng)典的計算能力調(diào)度中，在單個隊列中默認(rèn)采用的是先進(jìn)先出的調(diào)度策略，這雖然易于實現(xiàn)，但對于處理交通信息數(shù)據(jù)這一類的分布式數(shù)據(jù)并不適用。在海量交通信息中，數(shù)據(jù)量雖然龐大，但單個作業(yè)規(guī)模往往并不會呈現(xiàn)出大文件的趨勢，而是區(qū)域化的短作業(yè)會比較多，這時若有長作業(yè)一直占用系統(tǒng)資源運行會使得短作業(yè)遲遲得不到執(zhí)行而形成饑餓。所以針對特定的交通信息在這里將算法設(shè)計成“基于先進(jìn)先出原則的短作業(yè)優(yōu)先”策略，即在短作業(yè)優(yōu)先執(zhí)行的前提下，再按先進(jìn)先出算法進(jìn)行作業(yè)隊列排序，流程圖如圖2所示。

在單個作業(yè)隊列內(nèi)部，如果用戶提交的作業(yè)中有各種不同類型的作業(yè)，例如復(fù)雜計算的大作業(yè)，簡單處理的小作業(yè)，強(qiáng)數(shù)據(jù)依賴型作業(yè)，弱數(shù)據(jù)依賴型作業(yè)等。當(dāng)按照某一調(diào)度策略（如小作業(yè)優(yōu)先）時，往往小作業(yè)會出現(xiàn)在同一隊列的不同節(jié)點上，這個時候如果按照小作業(yè)隊列優(yōu)先執(zhí)行，那么可能會形成較大的網(wǎng)絡(luò)數(shù)據(jù)流量，造成網(wǎng)絡(luò)阻塞。所以在保證小作業(yè)優(yōu)先執(zhí)行的情況下，為了不影響網(wǎng)絡(luò)的負(fù)載能力，需要加入延時調(diào)度策略，將短作業(yè)優(yōu)先調(diào)度改進(jìn)策略與延時策略相結(jié)合，改善網(wǎng)絡(luò)間通信的質(zhì)量。程序設(shè)計見下列語句:

收納作業(yè)并將作業(yè)Job List初始化為隊列

if節(jié)點D發(fā)送HeartBeat到master then

if節(jié)點D釋放SparePool then

for作業(yè)（循環(huán)）

J＝Job List.get（n），0＝＜Job List.length（），n＋＋；

if作業(yè)J有一個在節(jié)點D上的本地性任務(wù)then

立即運行

elseif網(wǎng)絡(luò)負(fù)載＞＝M then

調(diào)用延時函數(shù)delaysometime（）；

if作業(yè)J.wait＜T then

立即執(zhí)行長任務(wù)或者強(qiáng)依賴型任務(wù)或者本地性較強(qiáng)的任務(wù)；

else

停止延時函數(shù)；

endif

endif

endfor

endif

endif

在上述調(diào)度策略下，如果出現(xiàn)較大的網(wǎng)絡(luò)流量負(fù)載，當(dāng)達(dá)到閾值M時，它會自動觸發(fā)延時調(diào)度函數(shù)，并且在延時調(diào)度期間計算機(jī)資源會轉(zhuǎn)向運行其它長作業(yè)或者依賴型作業(yè)以及其它數(shù)據(jù)本地性較強(qiáng)的作業(yè)。延時調(diào)度的時間有一個最大值T，可以根據(jù)網(wǎng)絡(luò)負(fù)載狀況做實時調(diào)整。延時策略有利于加強(qiáng)數(shù)據(jù)的本地性，有利于減小節(jié)點間網(wǎng)絡(luò)數(shù)據(jù)傳輸壓力，特別地對分布式計算系統(tǒng)有實際使用價值。

交通信息的實時性和突發(fā)性決定了在處理此類信息的算法中應(yīng)該具有很強(qiáng)的交互性，這時需要引入緊急作業(yè)搶斷資源的算法來實現(xiàn)。對于常規(guī)調(diào)度算法來說，如何選擇下一個合適的作業(yè)運行是其核心問題，所有隊列預(yù)先被初始化為一個資源量，如果有隊列處于空閑狀態(tài)，它的資源將被分配給當(dāng)前最忙的隊列。所謂忙，是指正在運行的作業(yè)數(shù)與分配所得資源的比BR

比值越大越忙。這表示計算能力調(diào)度算法所具有的特性。但是如果在所有隊列間的隊列都無空閑資源的情況下，遇到突發(fā)情況，某一作業(yè)需要緊急執(zhí)行，就需要把低優(yōu)先級的作業(yè)先掛起，暫時把系統(tǒng)資源讓給緊急性作業(yè)。等緊急作業(yè)執(zhí)行完畢，釋放資源后再根據(jù)當(dāng)時的優(yōu)先級情況判斷是否繼續(xù)執(zhí)行暫停的作業(yè)。改進(jìn)后的狀態(tài)轉(zhuǎn)換如圖3所示。

圖3 緊急作業(yè)搶斷資源下的狀態(tài)轉(zhuǎn)換

3 算法實現(xiàn)及實驗結(jié)論

改進(jìn)后的算法中依然是使用3種粒度的對象:queue（隊列）、job（作業(yè)）和task（任務(wù)），分別維護(hù)著相關(guān)作業(yè)的一些信息。基于改進(jìn)型計算能力算法是基于計算能力調(diào)度的改進(jìn)，所以基本上保持了計算能力調(diào)度算法的架構(gòu)。算法實現(xiàn)的代碼主要由5個java程序組成，改進(jìn)的算法結(jié)構(gòu)如圖4所示。

從圖4中可以看出，此改進(jìn)算法的核心類是ECapacity TaskSheduler，與之關(guān)聯(lián)的類主要有文件配置類ECapacityShedulerConf，初始化類EJobInitialzationPoller，隊列管理類EJob Queue Manager和內(nèi)存容量匹配類EMemory Matcher。

核心類ECapacity TaskSheduler中有各種不同功能的方法，其中有調(diào)度器初始化函數(shù)start（），該函數(shù)初始化各種對象和變量等并加載配置文件；當(dāng)其中有一個Task Tracker的HeartBeat到達(dá)Job Tracker時，如果有spare的slot，Job Tracker（作業(yè)追蹤器）會調(diào)用調(diào)度器ECapacityScheduler中的assign Task（），該方法會根據(jù)Task Tracker的需要找若干個合適的task。本文算法的改進(jìn)主要是在原計算能力調(diào)度算法框架下添加一些變量和函數(shù)，以達(dá)到提高處理交通信息數(shù)據(jù)效率的要求。添加的變量主要包括Task－Type、weigh、isShortJob等；添加的函數(shù)包括:優(yōu)先級設(shè)定與獲取函數(shù)setJobPriority（）/getJobPriority（），短作業(yè)判定函數(shù)isShortJob（），隊列類型作業(yè)類型匹配函數(shù)matchJoband Queue（），延時調(diào)度函數(shù)delaysometime（）。重新編寫了sort Queue（）方法，主要是在重新排序隊列時加入了短作業(yè)優(yōu)先級等屬性，還在配置文件conf中做了一些文件設(shè)定的參數(shù)配置與修改，包括map，reduce最大最小數(shù)目，隊列分配容量百分比，最大負(fù)載能力等。

實驗測試環(huán)境采用了3個數(shù)據(jù)節(jié)點，一個主節(jié)點，PC機(jī)的設(shè)置均對等相當(dāng)。Hadoop平臺搭建好之后，為保證新的改進(jìn)型調(diào)度算法的有效執(zhí)行需要從以下幾個方面進(jìn)行優(yōu)化:

（1）優(yōu)化應(yīng)用程序。由于Map Reduce的算法是逐行迭代來解析數(shù)據(jù)文件的，所以為提高程序的編寫效率，應(yīng)優(yōu)先設(shè)計優(yōu)化迭代算法。

（2）Hadoop系統(tǒng)參數(shù)的優(yōu)化。主要包括:Linux文件系統(tǒng)參數(shù)調(diào)整，文件掛載時設(shè)置noatime和nodiratime這兩個屬性可以明顯提高文件系統(tǒng)的性能，在可行的范圍內(nèi)調(diào)整Readahead buffer參數(shù)可以明顯改變文件順序讀取的性能，其實際上是修改Linux操作系統(tǒng)中文件緩沖區(qū)的容量。另外要避免在Task Tracker和Data Node節(jié)點上執(zhí)行RAID和LVM的操作；Hadoop通用參數(shù)調(diào)整，namenode、jobtracker、datanode中用于處理RPC（遠(yuǎn)程過程調(diào)用）的線程數(shù)的參數(shù)以及HTTP server上運行的線程數(shù)的參數(shù)，在針對不同規(guī)模的集群時需要做相應(yīng)的調(diào)整與設(shè)置；Hadoop作業(yè)調(diào)優(yōu)參數(shù)設(shè)置:主要包括Map（映射）階段的中間結(jié)果及最終結(jié)果的壓縮和Reduce（簡化）階段task的參數(shù)調(diào)優(yōu)。

為了測試改進(jìn)型算法的有效性，實驗?zāi)M交通信息數(shù)據(jù)的特點，采用兩種類型的測試場景及用例，I/O密集型WordCount和計算密集型Sort，采用控制變量法，分別統(tǒng)計多用戶多作業(yè)提交模式下，不同算法和不同數(shù)據(jù)規(guī)模的作業(yè)平均運行時間。

I/O密集型計算指的是系統(tǒng)的CPU多處于空閑狀態(tài)，而I/O（硬盤/內(nèi)存）的繁忙率較高，系統(tǒng)運行時往往呈現(xiàn)出CPU的利用率較低。在I/O密集型的測試中，本實驗采用了詞頻統(tǒng)計WordCount基準(zhǔn)測試樣例。采用該測試樣例的原因是詞頻統(tǒng)計的數(shù)據(jù)結(jié)構(gòu)與交通數(shù)據(jù)中離散分布的數(shù)據(jù)結(jié)構(gòu)十分類似，如統(tǒng)計某一段時間里各個路口小轎車，巴士，大貨車等各類型車輛的通過數(shù)量以及其速度等，這和WordCount的詞頻統(tǒng)計是十分類似的。其實驗結(jié)果如圖5所示。

圖5 I/O密集型計算不同調(diào)度算法效率對比

從圖5的統(tǒng)計圖可以看出，在多用戶多作業(yè)條件下，先進(jìn)先出算法對于I/O密集型的計算效率明顯不及公平調(diào)度、計算能力調(diào)度以及改進(jìn)型計算能力調(diào)度算法，在這種情況下，選用FIFO算法是非常不明智的做法，另外對于多用戶多作業(yè)情況下，數(shù)據(jù)規(guī)模越大，計算能力和改進(jìn)型計算能力調(diào)度算法為最優(yōu)算法，改進(jìn)的算法比原算法稍有提高。

計算密集型指的是系統(tǒng)的I/O（硬盤/內(nèi)存）繁忙率相對CPU的繁忙率要低，系統(tǒng)運作時，往往是I/O（硬盤/內(nèi)存）的讀/寫時間較短，需要等待CPU的處理。在計算密集型的測試中，實驗數(shù)據(jù)采用了一周的某出租汽車公司的GPS信息，提取其中的路徑和平均速度。分別測試了經(jīng)典算法以及改進(jìn)算法下的數(shù)據(jù)處理性能。其實驗結(jié)果如圖6所示。

圖6 計算密集型不同調(diào)度算法之間的效率對比

從圖6可以看出，此次實驗的執(zhí)行時間的增長幅度要大于I/O密集型計算。在多用戶多作業(yè)模式下，對于數(shù)據(jù)量小于5G的作業(yè)，4種算法執(zhí)行時間相當(dāng)；對于數(shù)據(jù)量大于5G的作業(yè)，改進(jìn)的計算能力調(diào)度算法的執(zhí)行時間相比其它3種算法較短，并且增長速度較緩慢，而先進(jìn)先出算法在此種情況下表現(xiàn)最不佳，公平算法次之。

兩次實驗結(jié)果均顯示改進(jìn)型的調(diào)度算法相較之前的計算能力調(diào)度算法性能有所提高，說明本文所述的改進(jìn)方向是可行的。

對于緊急作業(yè)搶斷資源的算法通常是通過設(shè)定作業(yè)優(yōu)先級的方法來實現(xiàn)的。在實驗中，不同優(yōu)先級下作業(yè)的運行時間是不同的，這主要是基于調(diào)度分配的隊列和該隊列所擁有的資源所決定的。實驗中采用改進(jìn)型計算能力算法為測試算法，初始資源分配百分比為40%，在單一緊急作業(yè)模式下（即只有一個緊急作業(yè)進(jìn)行資源搶斷），計算機(jī)三機(jī)集群分別運行在I/O密集型和計算密集型數(shù)據(jù)集上，測試用例數(shù)據(jù)規(guī)模為1GB，結(jié)果見表1和表2。

表1 緊急作業(yè)在不同優(yōu)先級下運行時間統(tǒng)計1

表2 緊急作業(yè)在不同優(yōu)先級下運行時間統(tǒng)計2

從表1和表2的結(jié)果中可以看出，優(yōu)先級分為5級，從1到5依次升高，最高優(yōu)先級為5。在各級不同的優(yōu)先級中，一般會在標(biāo)準(zhǔn)或以上優(yōu)先級時才執(zhí)行搶先策略。作業(yè)會搶占系統(tǒng)資源來運行優(yōu)先級高的作業(yè)。當(dāng)達(dá)到最高優(yōu)先級時，該作業(yè)所用時間最少，結(jié)果很明顯；對于低優(yōu)先級的作業(yè)，它們的運行時間凸顯出很長（如表1中優(yōu)先級值為1和2時），有時還不能確定（如表2中優(yōu)先級值為1和2時），原因是如果有高優(yōu)先級的作業(yè)在提交運行，且高優(yōu)先級作業(yè)源源不斷，則低優(yōu)先級的作業(yè)就難以得到運行，除非等到?jīng)]有高優(yōu)先級的作業(yè)提交，它才可以進(jìn)入隊列進(jìn)行排隊等待被調(diào)度。這種現(xiàn)象在計算密集型作業(yè)中特別明顯，各個隊列的資源幾乎被常規(guī)作業(yè)占用，緊急作業(yè)難以搶斷，呈現(xiàn)出一種“饑餓”的狀態(tài)。相對I/O密集型的作業(yè)，由于I/O切換期間會短暫出現(xiàn)隊列空閑的現(xiàn)象，所以呈現(xiàn)出來的運行時間可信，但也是大大高于標(biāo)準(zhǔn)或以上優(yōu)先級的運行時間。因此，對于緊急事件，一定首先賦予該作業(yè)較高的甚至是最高的優(yōu)先級，同時輔之以其它措施，例如，可以暫時延時其它作業(yè)的調(diào)度等，以保證緊急作業(yè)得到優(yōu)先執(zhí)行。

4 結(jié)束語

依據(jù)城市交通信息數(shù)據(jù)特點，對傳統(tǒng)計算能力調(diào)度算法進(jìn)行了優(yōu)化與實現(xiàn)，彌補(bǔ)了傳統(tǒng)算法的不足之處，使得優(yōu)化后的算法能夠適應(yīng)城市智能交通數(shù)據(jù)處理，實驗結(jié)果表明，改進(jìn)的計算能力調(diào)度算法無論是從交互性，還是從數(shù)據(jù)處理性能上，在處理大規(guī)模分布式的城市交通數(shù)據(jù)時都具有一定的優(yōu)勢。城市交通將會是未來海量數(shù)據(jù)研究的重點之一，下一步將使用該算法對城市交通數(shù)據(jù)進(jìn)行更深層次處理，探索更加實際的應(yīng)用，以滿足用戶的需求。

［1］XU Xiaolong，WU Jiaxing，YANG Geng，et al.Mass data processing system based on large－scale low－cost computing platform［J］.Application Research of Computers，2012，29（2）:582－585（in Chinese）.［徐小龍，吳家興，楊庚，等.基于大規(guī)模廉價計算平臺的海量數(shù)據(jù)處理系統(tǒng)的研究［J］.計算機(jī)應(yīng)用研究，2012，29（2）:582－585.］

［2］Zaharia M，Borthakur D，Sen Sarma J，et al.Delay scheduling:A simple technique for achieving locality and fairness in cluster scheduling［C］//Proceedings of the 5th European Conference on Computer Systems.New York:ACM，2010:265－278.

［3］Isard M，Prabhakaran V，Currey J，et al.Quincy:Fair scheduling for distributed computing clusters［C］//Proceedings of the 22nd Symposium on Operating Systems Principles.New York:ACM，2009:261－276.

［4］DENG Chuanhua，F(xiàn)AN Tongrang，GAO Feng.Resource scheduler algorithm based on statistical optimization under Hadoop［J］.Application Research of Computers，2013，30（2）:417－419（in Chinese）.［鄧傳華，范通讓，高峰.Hadoop下基于統(tǒng)計最優(yōu)的資源調(diào)度算法［J］.計算機(jī)應(yīng)用研究，2013，30（2）:417－419.］

［5］WANG Feng.Scheduling algorithm of Hadoop cluster job scheduling algorithm［J］.Programmer，2009，10（12）:1－19（in Chinese）.［王峰.Hadoop集群作業(yè)的調(diào)度算法［J］.程序員，2009，10（12）:1－19.］

［6］Dean J，Ghemawat S.MapReduce:Simplified data processing on large clusters［J］.Communications of the ACM，2008，51（1）:107－113.

［7］You H H，Yang C C，Huang J L.A load－aware scheduler for Map Reduce framework in heterogeneous cloud environments［C］//Proceedings of the 2011 ACM Symposium on Applied Computing.New York:ACM，2011:127－132.

［8］Fischer M J，Su X，Yin Y.Assigning tasks for efficiency in Hadoop［C］//Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures.New York:ACM，2010:30－39.

［9］Liu X，Lu F，Zhang H，et al.Estimating Beijing's travel de－lays at intersections with floating car data［C］//Proceedings of the 5th International Workshop on Computational Transportation Science.New York:ACM，2012:14－19.

［10］Edwards M，Rambani A，Zhu Y，et al.Design of Hadoopbased framework for analytics of large synchrophasor datasets［J］.Procedia Computer Science，2012，12:254－258.

［11］DING Yuguang，LIU Wenjie，WANG Weilin.Research on capacity scheduling algorithm based on QoS constraints［J］.Journal of Sichuan University of Science ＆Engineering（Na－tural Science Edition），2012，25（3）:47－50（in Chinese）.［丁宇光，劉文杰，王衛(wèi)林.基于QoS約束的計算能力調(diào)度算法研究［J］.四川理工學(xué)院學(xué)報（自然科學(xué)版），2012，25（3）:47－50.］