分布式并行計(jì)算的算法應(yīng)用

feiyang10086

眾所周知MapReduce模型是Google公司在多臺(tái)普通機(jī)器，利用函數(shù)式的思想，提高程序執(zhí)行的性能，而Stanford的 Phoenix則是這一模型在多核時(shí)代的解決方案。作為Google MapReduce技術(shù)的開源實(shí)現(xiàn)，Hadoop借鑒了谷歌的Google File System文件系統(tǒng)、MapReduce并行算法以及BigT able。因此，Hadoop也是一個(gè)能夠分布式處理大規(guī)模海量數(shù)據(jù)的軟件框架，也是一個(gè)開源的分布式并行計(jì)算平臺(tái)，它主要由MapReduce的算法執(zhí) 行和一個(gè)分布式的文件系統(tǒng)等兩部分組成。

Hadoop是并行工作的，以加快任務(wù)處理速度。Hadoop的可擴(kuò)展依賴于部署Hadoop軟件框架計(jì)算集群的規(guī)模，Hadoop的運(yùn)算是可擴(kuò)展 的，具有處理PB級(jí)數(shù)據(jù)的能力。雖然Hadoop自身由Java語言開發(fā)， 但它除了使用Java語言進(jìn)行編程外， 同樣支持多種編程語言，如C++。

　 　與Hadoop不同的是微軟是通過DryadLINQ語言進(jìn)行編程與設(shè)計(jì)，它可以根據(jù)程序員給出的LINQ查詢生成可以在Dryad引擎上執(zhí)行的分布式 策略算法建模(運(yùn)算規(guī)則)，并負(fù)責(zé)任務(wù)的自動(dòng)并行處理及數(shù)據(jù)傳遞時(shí)所需要的序列化等操作。此外，它還提供了一系列易于使用的高級(jí)特性，如強(qiáng)類型數(shù) 據(jù)，Visual Studio集成調(diào)試，以及豐富的任務(wù)優(yōu)化策略(規(guī)則)算法等等。這種模型策略開發(fā)框架也比較適合采用領(lǐng)域驅(qū)動(dòng)開發(fā)設(shè)計(jì)(DDD)來構(gòu)建“云”平臺(tái)應(yīng)用， 并能夠較容易的做到自動(dòng)化分布式計(jì)算。

　　并行算法分治策略

　　Y=(A+B(C+DEF))+G，串行計(jì)算 需要6步。利用結(jié)合律和交換律，該式變?yōu)閅=Y + (分裂為兩個(gè)問題)，其中Y =A+G， =B (C+DEF)，在兩臺(tái)處理機(jī)的系統(tǒng)上只需5步并行計(jì)算。在用分配率，Y=(A+B(C+DEF))+G可變?yōu)閅= + ，其中 =A+G+BC， =BDEF，在兩臺(tái)處理機(jī)的系統(tǒng)上并行計(jì)算只需4步。如四臺(tái)處理機(jī)的系統(tǒng)，并行計(jì)算可進(jìn)一步減少為3步。兩臺(tái)處理機(jī)下的運(yùn)算分解樹和四臺(tái)處理機(jī)下的運(yùn)算分 解樹，如圖1所示。


圖1 DGA運(yùn)算分解樹

　　從上面分析我們可以看到，通過并行算法策略建模，可以有效的控制數(shù)據(jù)的顆粒度，當(dāng)程序運(yùn)行在Dryad分布式并行平臺(tái)時(shí)候，可最大化的提高分布式并行運(yùn)算效率。

　　分布式并行策略

　　在云計(jì)算的時(shí)代，Dynamo(Amazon 公司的一個(gè)分布式存儲(chǔ)引擎)可以說是一本實(shí)現(xiàn)分布式存儲(chǔ)的紅寶書，借鑒Dynamo實(shí)現(xiàn)的產(chǎn)品如雨后春筍般冒出。

　　我們經(jīng)常會(huì)遇到所開發(fā)的網(wǎng)站/系統(tǒng)，無法承載大規(guī)模用戶并發(fā)訪問的問題。解決該問題的傳統(tǒng)方法是使用數(shù)據(jù)庫，通過數(shù)據(jù)庫所提供的訪問操作接口來保證處理復(fù)雜的查詢能力。當(dāng)訪問量增大，單數(shù)據(jù)庫處理不過來時(shí)便增加數(shù)據(jù)庫服務(wù)器。如果增加了3臺(tái)服務(wù)器， 再把用戶分成了三類(關(guān)注：策略建模、顆粒度和映射)：A(學(xué)生)，B(老師)，C(程序員)。每次訪問的時(shí)候，Dryad會(huì)先查看用戶屬于哪一類，然后 直接訪問存儲(chǔ)那類用戶數(shù)據(jù)的數(shù)據(jù)庫，可能處理能力增加了三倍。這時(shí)我們已經(jīng)實(shí)現(xiàn)了一個(gè)分布式的存儲(chǔ)引擎過程，而Dryad與Dynamo具有相似的功能。 Dynamo分布式存儲(chǔ)引擎，如圖2所示。


▲圖2 Dynamo分布式存儲(chǔ)引擎

我們可以通過Dryad和Dynamo進(jìn)行分布式云平臺(tái)來解決云存儲(chǔ)擴(kuò)容困難問題。如果這3臺(tái)服務(wù)器也承載不了更大的數(shù)據(jù)要求時(shí)，需要增加到5臺(tái)服務(wù)器， 那必須更改分類方法把用戶分成5類，然后重新遷移已經(jīng)存在的數(shù)據(jù)，這時(shí)候就需要非常大的遷移工作，這種方法顯然不可取。另外，當(dāng)群集服務(wù)器進(jìn)行分布式計(jì)算 運(yùn)行的時(shí)候，每個(gè)資源節(jié)點(diǎn)處理能力可能有所不同(例如不同硬件配置的服務(wù)器等等)，如果只是簡單的把機(jī)器直接分布上去，性能高的機(jī)器得不到充分利用，性能 低的機(jī)器處理不過來。


圖3 通過Dryad DAG排列的節(jié)點(diǎn)(程序)擴(kuò)展性能

　　? P parses lines(解析線)

　　? D hash distribute(哈希分布)

　　? S quicksort(快速排序)

　　? C count occurrences(事件計(jì)算)

　　? MS merge sort(合并分類)

　　? M non-deterministic merge(未確定合并)

　 　Dryad和Dynamo解決此問題的方法是采用虛節(jié)點(diǎn)。把上面的A B C三類等用戶都想象成一個(gè)邏輯上的節(jié)點(diǎn)。一臺(tái)真實(shí)的物理節(jié)點(diǎn)可能會(huì)包含一個(gè)或者幾個(gè)虛節(jié)點(diǎn)(邏輯節(jié)點(diǎn))，看機(jī)器的性能而定。我們可以把那任務(wù)程序分成Q等 份(每一個(gè)等份就是一個(gè)虛節(jié)點(diǎn))，這個(gè)Q要遠(yuǎn)大于我們的資源數(shù)。現(xiàn)在假設(shè)我們有S個(gè)資源，那么每個(gè)資源就承擔(dān)Q/S個(gè)等份。 當(dāng)一個(gè)資源節(jié)點(diǎn)離開系統(tǒng)的時(shí)候，它所負(fù)責(zé)的等份要重新均分到其他資源節(jié)點(diǎn)上，一個(gè)新節(jié)點(diǎn)加入的時(shí)候，要從其他的節(jié)點(diǎn)“偷取”到一定數(shù)額的等份。

　 　在這個(gè)策略建模算法下，當(dāng)一個(gè)節(jié)點(diǎn)離開系統(tǒng)的時(shí)候，雖然需要影響到很多節(jié)點(diǎn)，但是遷移的數(shù)據(jù)總量只是離開那個(gè)節(jié)點(diǎn)的數(shù)據(jù)量。同樣，一個(gè)新節(jié)點(diǎn)的加入，遷 移的數(shù)據(jù)總量也只是一個(gè)新節(jié)點(diǎn)的數(shù)據(jù)量。之所以有這個(gè)效果是因?yàn)镼的存在，使得增加和減少機(jī)器的時(shí)候不需要對(duì)已有的數(shù)據(jù)做重新哈希(D)。這個(gè)策略的要求 是Q>>S(存儲(chǔ)備份上，假設(shè)每個(gè)數(shù)據(jù)存儲(chǔ)N個(gè)備份則要滿足Q>>S*N)。如果業(yè)務(wù)快速發(fā)展，使得不斷的增加主機(jī)，從而導(dǎo)致Q 不再滿足Q>>S，那么這個(gè)策略將重新變化。

　　通過上述的論述，我們可以看到Dryad通過一個(gè)有向無環(huán)圖的策略建模算法， 提供給用戶一個(gè)比較清晰的編程框架。在這個(gè)編程框架下，用戶需要將自己的應(yīng)用程序表達(dá)為有向無環(huán)圖的形式，節(jié)點(diǎn)程序則編寫為串行程序的形式，而后用 Dryad方法將程序組織起來。用戶不需要考慮分布式系統(tǒng)中關(guān)于節(jié)點(diǎn)的選擇，節(jié)點(diǎn)與通信的出錯(cuò)處理手段都簡單明確，內(nèi)建在Dryad框架內(nèi)部，滿足了分布 式程序的可擴(kuò)展性、可靠性和性能的要求。在云平臺(tái)分布式算法上Dryad與Dynamo分布式存儲(chǔ)引擎相似，并且有更好的創(chuàng)新。


本篇文章來源于 中間件技術(shù)社區(qū)(http://middleware123.com) 原文鏈接：http://middleware123.com/cloud/tech/683.html

dididimeme

最近也在研究并行計(jì)算與云處理，尤其是hadoop，就像你說的一樣，他分為MapReduce部分以及HDFS文件存儲(chǔ)部分，但是個(gè)人感覺它主用應(yīng)用于數(shù)據(jù)的分析處理上，但對(duì)頻繁寫的處理可能并不適用。其實(shí)，說白了它更像個(gè)可以并行數(shù)據(jù)分散存儲(chǔ)的數(shù)據(jù)庫，可以虛擬各個(gè)節(jié)點(diǎn)的數(shù)據(jù)為統(tǒng)一的邏輯文件適用。不知道我的理解是否真確，請指正。

zimo0125

今天賺到了，哈哈，謝謝樓主的分享，學(xué)到了很多~~頂http://www.itvcp.com/Lottery/Buy_SYYDJ.aspx期待樓主更精彩的文章！一定還要多多給我們分享分享哦！