移動(dòng)云計(jì)算的數(shù)據(jù)處理方法

一、引言

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

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

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

二、模型框架

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

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

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

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

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

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

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

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

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

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

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

    4．取消排序階段

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

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

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

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

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

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

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

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

四、性能分析

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

    算法設(shè)計(jì)思想

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

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

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

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

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

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

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

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

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

核心關(guān)注：拓步ERP系統(tǒng)平臺(tái)是覆蓋了眾多的業(yè)務(wù)領(lǐng)域、行業(yè)應(yīng)用，蘊(yùn)涵了豐富的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://m.hanmeixuan.com/

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

本文網(wǎng)址：http://m.hanmeixuan.com/html/consultation/1083975494.html