一、引言

    隨著信息技術的發展，人們對于大數據量的信息處理要求也越來越高，傳統的基于單機數據庫的處理方式已經無法承擔大規模的數據量。尤其是手機產業的興起，網絡用戶的數量巨增，對信息的響應速度和處理時間的要求也越來越苛刻。相比之下，對信息的準確性的要求不再那么嚴格，比如實時路況的處理等等。

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

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

二、模型框架

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

    1.任務獲取方式

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

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

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

    2．數據傳遞方式

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

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

    3．流水式的任務執行

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

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

    4．取消排序階段

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

    5．細粒度的任務設定

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

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

三、設計細節

    為了提高系統的運行效率，采用e語言來實現設計，采用主結點管理名字空間，數據結點采用redis數據庫模擬的方式，redis是一個高性能的數據庫，吞吐率較高，盡管redis的數據本身沒有標簽，對于實驗環境，將不同的標簽的數據作為不同的值存儲，能夠滿足實驗的要求。

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

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

四、性能分析

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

    算法設計思想

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

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

    系統運行的過程

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

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

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

五、結論和未來工作

    我們設計并簡單實現了FastMR，通過實驗，發現FastMR對采用的算法的實現性能是高效的，認為它可以滿足流式計算的需求。

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

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

轉載請注明出處：拓步ERP資訊網http://www.guhuozai8.cn/

本文標題：移動云計算的數據處理方法

本文網址：http://www.guhuozai8.cn/html/consultation/1083975494.html