一、引言

    隨著信息技術(shù)的發(fā)展，人們對于大數(shù)據(jù)量的信息處理要求也越來越高，傳統(tǒng)的基于單機數(shù)據(jù)庫的處理方式已經(jīng)無法承擔(dān)大規(guī)模的數(shù)據(jù)量。尤其是手機產(chǎn)業(yè)的興起，網(wǎng)絡(luò)用戶的數(shù)量巨增，對信息的響應(yīng)速度和處理時間的要求也越來越苛刻。相比之下，對信息的準(zhǔn)確性的要求不再那么嚴(yán)格，比如實時路況的處理等等。

    MapReduce框架是一種成功的想法，它被Google提出并已經(jīng)被應(yīng)用于多種運用，比如網(wǎng)頁搜索和網(wǎng)頁排序。它類似于現(xiàn)在的數(shù)據(jù)庫系統(tǒng)，輸入是key／value對，通過用戶自定義一個map函數(shù)，將輸人數(shù)據(jù)進行預(yù)處理，將相同的key的value發(fā)送到reduce端，然后這些value進行排序，由reduce函數(shù)進行處理，最后輸出也是key／value對，這種編程模型現(xiàn)在很多應(yīng)用中得以實現(xiàn)，而且很多傳統(tǒng)的算法也可以通過變形在上面實現(xiàn)。

    MapReduce框架對處理傳統(tǒng)的大數(shù)據(jù)量的信息很有優(yōu)勢，比如網(wǎng)頁排序等。但隨著網(wǎng)絡(luò)用戶的增加和對及時信息的需求，框架本身的局限性就顯示出來，比如任務(wù)的準(zhǔn)備時間和reduce階段之前的排序時間太長等等，這些限制使得MapReduae不能夠勝任流式信息的處理，對于MapReduce框架的這些短處，我們設(shè)計了一種新的FastMR，它對MapReudce框架做了一些改變，并用。語言實現(xiàn)了一個雛形，使它能夠處理流式數(shù)據(jù)，性能優(yōu)于現(xiàn)在的MapReudce框架。

二、模型框架

    根據(jù)實際需要，我們設(shè)計了自己的MapReduce框架，即FasfMR。和Google的MapReduce框架類似，我們的從結(jié)點既是任務(wù)結(jié)點也是存儲結(jié)點。我們的設(shè)計的目的是完成流式信息的處理，所以和傳統(tǒng)的MapReduce框架有很大差別，主要體現(xiàn)在以下幾個方面:

    1.任務(wù)獲取方式

    在MapReduce模型中，采用的是主從式的任務(wù)獲取方式。在一個集群中，有一個Master結(jié)點用來管理任務(wù)的執(zhí)行，Master結(jié)點的負(fù)載相對較重，它需要負(fù)責(zé)接受客戶端的任務(wù)、調(diào)度任務(wù)的執(zhí)行。客戶端將任務(wù)代碼上傳到分布式文件系統(tǒng)，然后通知Mater結(jié)點有任務(wù)到來。Master將任務(wù)信息加入等待任務(wù)列表。集群中的結(jié)點采用Slave方式運行，定期以心跳的方式連接Master，報告任務(wù)運行情況和請求任務(wù)。心跳的過程是通過RPC方式連接到Master，在報告的同時順便請求任務(wù)。這種方式對于Slave來說，對任務(wù)的獲取是有延遲的，不能夠及時的得到任務(wù)執(zhí)行。首先，這種方式會有任務(wù)獲取的延遲。對于實時性要求非常苛刻的環(huán)境下，10秒種的獲取任務(wù)延遲是不被允許的。其次，影響Map任務(wù)的本地化執(zhí)行。例如，某一時刻，有一個Slave來請求任務(wù)，Master是不知道結(jié)點的情況的，只能根據(jù)這個結(jié)點的信息，給與該任務(wù)相應(yīng)的輸入數(shù)據(jù)，這個數(shù)據(jù)可能不在這個結(jié)點上，因為無法保證來請求的Slave結(jié)點都具有該任務(wù)的數(shù)據(jù)。

    FastMR的任務(wù)報告和任務(wù)獲取是分開的，任務(wù)報告保留以前的RPC方式，而任務(wù)的獲取采用阻塞方式，即Slave中有任務(wù)槽的結(jié)點與Master結(jié)點保持一個TCP連接，Master結(jié)點建立一個表，負(fù)責(zé)維護這些連接，當(dāng)有客戶端有作業(yè)提交的時候，Master結(jié)點通過配置的調(diào)度方式，分配任務(wù)給Slave結(jié)點。

    這種方式是FastMR針對云計算平臺的改進，它可以減少任務(wù)獲取的延遲和Map任務(wù)的本地化，因為在任務(wù)開始時，結(jié)點信息在Master中，Master對能夠執(zhí)行任務(wù)的結(jié)點不再是一無所知，它可以做到最大程度上的調(diào)度任務(wù)執(zhí)行，來滿足本地化要求。

    2．?dāng)?shù)據(jù)傳遞方式

    MapReduce模型中數(shù)據(jù)的傳遞有兩種方式。首先在任務(wù)剛開始執(zhí)行的時候，數(shù)據(jù)是通過分布式文件系統(tǒng)傳遞給Map任務(wù)，Map任務(wù)執(zhí)行完以后，會將數(shù)據(jù)在本地執(zhí)行Combine，在此過程中進行一個局部排序，然后保存到本地磁盤，等待其他Slave來取數(shù)據(jù)。當(dāng)任務(wù)中所有的Map任務(wù)都執(zhí)行完以后，Master統(tǒng)計任務(wù)中的執(zhí)行情況然后進人Shuffle階段，這時候Reduce任務(wù)的結(jié)點向Map任務(wù)結(jié)點獲取數(shù)據(jù)。Shuffle階段是MapReduce模型的核心，是保證并行性的關(guān)鍵。因為任務(wù)運行時，為了挖掘集群的潛力，需要將任務(wù)進行劃分，獲取最大程度上的并行眭。任務(wù)執(zhí)行過程中有兩次任務(wù)劃分，在任務(wù)開始的時候，是通過對輸入數(shù)據(jù)進行劃分來分配任務(wù)，而在Map執(zhí)行完以后reduce任務(wù)開始之前，是通過Shuffle方法進行劃分，Shuffle階段通常采用Hash的方式劃分任務(wù)，或者客戶端自己定義劃分的方法。Shuffle階段是Reduce任務(wù)結(jié)點向Map任務(wù)結(jié)點請求數(shù)據(jù)，采用Http請求的方式。這種方式對于注重吞吐率、穩(wěn)定性和整體效率的后臺是比較適宜的，但它不適合用于移動云計算平臺。因為同步以及拉的方式在時間性能上都遠(yuǎn)不如推的方式。

    FastMR的改進是將Map端的數(shù)據(jù)在執(zhí)行完以后直接推送出去，這種數(shù)據(jù)傳遞的方式可能要結(jié)合FastMR的另外兩個改進才能做到，它們分別是流水式的任務(wù)執(zhí)行方式和取消MapReduce中的排序階段，采用推的方式結(jié)合和FastMR的特點能夠很大程度上縮短任務(wù)的執(zhí)行時間。

    3．流水式的任務(wù)執(zhí)行

    MapReduce任務(wù)中的Map階段執(zhí)行完以后會有一段同步時間，同步完以后Map任務(wù)將開啟一個http端口供Reduce任務(wù)讀取數(shù)據(jù)， 同步在MapReduce任務(wù)中是必須的，因為Reduce任務(wù)在運行前有排序階段，需要得到完整的數(shù)據(jù)，這里就需要所有的map任務(wù)都運行結(jié)束才能得到。當(dāng)一個任務(wù)出現(xiàn)錯誤的時候，MapReduce模型需要將任務(wù)進行重新調(diào)度運行，其他結(jié)點需要等待這個任務(wù)運行完成才能再運行，這個作業(yè)就阻塞在這個需要重新運行的結(jié)點上，這樣非常影響作業(yè)的運行時間。

    FastMR的設(shè)想是將任務(wù)的運行看成是流水的方式，任務(wù)執(zhí)行的過程中沒有明的同步障。這種運行方式帶來的好處是提高了單一任務(wù)的執(zhí)行速度，符合移動云計算的需求。這種任務(wù)的運行類似與MapReduce Online的管道式的運行方式，在前一個任務(wù)還沒有運行完的時候后一個任務(wù)就開始運行，事前可以根據(jù)集群的具體情況配置流水線的級數(shù)，然后集群根據(jù)這個參數(shù)執(zhí)行，隨著流水線級數(shù)的增加，任務(wù)的執(zhí)行速度會提高很多，因為多級流水更加適合集群的任務(wù)調(diào)度，不過集群對任務(wù)的管理會增加復(fù)雜性。

    4．取消排序階段

    MapReduce模型在Map任務(wù)執(zhí)行完以后會在Map任務(wù)端執(zhí)行排序，然后傳到RedLIce任務(wù)端再進行歸并排序，這個階段對于Google的很多后臺應(yīng)用是非常有用的。同時，這個階段也是相當(dāng)耗時的，尤其是在超大規(guī)模的數(shù)據(jù)處理過程中更是如此。我們設(shè)想了很多移動云計算的應(yīng)用，發(fā)現(xiàn)較多的移動云計算的應(yīng)用對數(shù)據(jù)的排序基本沒有要求。于是基于這個設(shè)想，可以將復(fù)雜費時的排序選用或者取消(如果保留，需要改變先前的排序方式，因為任務(wù)是流水的方式運行，任務(wù)之間沒有同步)。我們的設(shè)想是如果保留排序，則進行局部排序，而且我們發(fā)現(xiàn)多數(shù)作業(yè)如果是由多個任務(wù)構(gòu)成，那么一個任務(wù)產(chǎn)生的中間結(jié)果不會影響最終結(jié)果(中間會產(chǎn)生一些沒有的輸出)。當(dāng)然也有例外的情況，所以流水線的方式不適合多有的應(yīng)用。

    5．細(xì)粒度的任務(wù)設(shè)定

    MapReduce編程模型中的錯誤恢復(fù)機制繼承了Google的一貫簡單高效的作風(fēng)，采用了最簡單的方式，如果錯誤發(fā)生，則重新運行作業(yè)的機制。這種錯誤恢復(fù)機制非常簡單，然而一旦發(fā)生錯誤，作業(yè)的執(zhí)行時間將會非常長。

    FastMR采用的方式是細(xì)化一個任務(wù)的顆粒度，劃分方式是通過輸入數(shù)據(jù)進行塊劃分和記錄數(shù)據(jù)偏移的方式。如果任務(wù)運行的結(jié)點出現(xiàn)異常，則錯誤恢復(fù)時只是將未處理的數(shù)據(jù)進行恢復(fù)。因為數(shù)據(jù)處理量不是實時記錄的，所以可能出現(xiàn)已經(jīng)處理過的數(shù)據(jù)重新處理一遍的情況，對于這種情況，對于集群來說并沒有太大的影響，因為在Reduce任務(wù)端對這種冗余的數(shù)據(jù)可以簡單的合并掉。

三、設(shè)計細(xì)節(jié)

    為了提高系統(tǒng)的運行效率，采用e語言來實現(xiàn)設(shè)計，采用主結(jié)點管理名字空間，數(shù)據(jù)結(jié)點采用redis數(shù)據(jù)庫模擬的方式，redis是一個高性能的數(shù)據(jù)庫，吞吐率較高，盡管redis的數(shù)據(jù)本身沒有標(biāo)簽，對于實驗環(huán)境，將不同的標(biāo)簽的數(shù)據(jù)作為不同的值存儲，能夠滿足實驗的要求。

    FastMR中的通信均采用了redis數(shù)據(jù)傳輸協(xié)議，比如“*3\r\n$3\r\nSET\r\n $5＼nmykey\r\n$8\r＼nmyvalue＼ne\r\n其中每個參數(shù)用＼r＼n分割，第一個 3說明有3個參數(shù)，后面一個$3說明這個參數(shù)有3個字節(jié)，這種通信協(xié)議容易實現(xiàn)并且易于解析。

    Master為Slave提供了多個遠(yuǎn)程調(diào)用的接口，比如SubmiOob，GetNewTask等等，這些接口均采用remote procedure calls的方式。利用redis通信協(xié)議，易于實現(xiàn)傳輸數(shù)據(jù)的序列化，每次RPC返回的數(shù)據(jù)也很容易實現(xiàn)反序列化。

四、性能分析

    為測試FastMR的性能，采用求無向圖中一個點到其他點最短路徑的算法。這個算法滿足編程模型的需要，有多輪并且每一輪的map和reduce函數(shù)是一樣的。

    算法設(shè)計思想

    該算法是Belman—F0rd算法的一種變形，在每輪開始信息的保存方式是這樣的：

    Key=結(jié)點，Value=距離+當(dāng)前最短路徑(沒有則為空)+鄰接點及距離列表

    系統(tǒng)運行的過程

    map端:對于每個鄰接點，最短路徑上添加一個邊，并修改最短路徑的距離值為其自反加距離，發(fā)送出去。

    Reduce端:收集相同Key的Value，獲取一個距離值最小的Value做為Reduce的結(jié)果，然后結(jié)束本輪。

    每輪總的時間復(fù)雜度是O(E)，分布在多臺機器上執(zhí)行，要求有多少個結(jié)點就要運行多少輪，所以不同量級的結(jié)點數(shù)和邊數(shù)將可能導(dǎo)致效率差別很大。

五、結(jié)論和未來工作

    我們設(shè)計并簡單實現(xiàn)了FastMR，通過實驗，發(fā)現(xiàn)FastMR對采用的算法的實現(xiàn)性能是高效的，認(rèn)為它可以滿足流式計算的需求。

    我們已經(jīng)證實了設(shè)想的正確性，現(xiàn)在開始實現(xiàn)完整的內(nèi)存文件系統(tǒng)，包括實現(xiàn)其動態(tài)擴展性、容錯性以及高吞吐率，下一步將改進FastMR的作業(yè)管理機制和實現(xiàn)錯誤恢復(fù)機制，準(zhǔn)備將調(diào)度從代碼中獨立出來，使多種應(yīng)用實現(xiàn)不同的任務(wù)和作業(yè)調(diào)度算法，類似Hadoop的那種由用戶自己配置調(diào)度策略等，進而實現(xiàn)由數(shù)據(jù)改變而觸發(fā)任務(wù)執(zhí)行的方式，類似與Google的Percolator。

核心關(guān)注：拓步ERP系統(tǒng)平臺是覆蓋了眾多的業(yè)務(wù)領(lǐng)域、行業(yè)應(yīng)用，蘊涵了豐富的ERP管理思想，集成了ERP軟件業(yè)務(wù)管理理念，功能涉及供應(yīng)鏈、成本、制造、CRM、HR等眾多業(yè)務(wù)領(lǐng)域的管理，全面涵蓋了企業(yè)關(guān)注ERP管理系統(tǒng)的核心領(lǐng)域，是眾多中小企業(yè)信息化建設(shè)首選的ERP管理軟件信賴品牌。

轉(zhuǎn)載請注明出處：拓步ERP資訊網(wǎng)http://www.guhuozai8.cn/

本文標(biāo)題：移動云計算的數(shù)據(jù)處理方法

本文網(wǎng)址：http://www.guhuozai8.cn/html/consultation/1083975494.html