分布式數(shù)據(jù)流處理的算子調(diào)度與負(fù)載平衡研究.pdf

1、數(shù)據(jù)流處理系統(tǒng)廣泛應(yīng)用在眾多領(lǐng)域，例如金融管理、網(wǎng)絡(luò)監(jiān)視、通信數(shù)據(jù)管理、Web應(yīng)用、傳感器網(wǎng)絡(luò)數(shù)據(jù)處理等。隨著計(jì)算機(jī)網(wǎng)絡(luò)、分布式計(jì)算技術(shù)的迅速發(fā)展，使得實(shí)時(shí)處理分布在網(wǎng)絡(luò)不同結(jié)點(diǎn)上的流數(shù)據(jù)成為可能，于是分布式流處理技術(shù)便應(yīng)運(yùn)而生。由于流數(shù)據(jù)源及應(yīng)用本身存在分布的特點(diǎn)，并且應(yīng)用規(guī)模不斷擴(kuò)大，分布式流處理系統(tǒng)成為流數(shù)據(jù)處理研究的必然趨勢(shì)。分布式數(shù)據(jù)流處理系統(tǒng)的研制在國(guó)際上也是剛剛起步，在軍事、網(wǎng)絡(luò)、金融等關(guān)系到國(guó)計(jì)民生的領(lǐng)域，將會(huì)有越來(lái)越廣

2、泛的用途。在分布式流處理系統(tǒng)中，算子調(diào)度策略的選取對(duì)系統(tǒng)內(nèi)存的消耗，輸出延遲的長(zhǎng)短等系統(tǒng)重要性能指標(biāo)有很大的影響。我們?cè)O(shè)計(jì)的GM調(diào)度策略綜合考慮了將來(lái)的負(fù)載變化、當(dāng)前的內(nèi)存消耗狀況以及用戶(hù)對(duì)于主要性能指標(biāo)的偏好與要求，在系統(tǒng)內(nèi)存最小化和結(jié)果輸出延遲方面取得平衡。在GM調(diào)度策略中，算子的執(zhí)行順序由一個(gè)評(píng)分函數(shù)統(tǒng)一決定?？梢酝ㄟ^(guò)設(shè)置評(píng)分函數(shù)的靜態(tài)參數(shù)來(lái)滿(mǎn)足不同應(yīng)用場(chǎng)景的需要，也可以自動(dòng)地調(diào)整評(píng)分函數(shù)的動(dòng)態(tài)參數(shù)來(lái)反映系統(tǒng)的工作狀態(tài)。另外，GM

3、調(diào)度策略可以保證查詢(xún)的優(yōu)先級(jí)。由于流處理應(yīng)用中需要實(shí)時(shí)處理大量具有相當(dāng)高的突發(fā)性的數(shù)據(jù)，系統(tǒng)可能不能及時(shí)處理。所以無(wú)論是集中式數(shù)據(jù)流處理系統(tǒng)還是分布式數(shù)據(jù)流處理系統(tǒng)，負(fù)載管理成為研究的熱點(diǎn)與重點(diǎn)。在傳統(tǒng)并行分布式系統(tǒng)領(lǐng)域，對(duì)負(fù)載管理問(wèn)題的研究，與數(shù)據(jù)流的負(fù)載管理有許多相似之處，但存在著本質(zhì)上的區(qū)別。負(fù)載平衡研究領(lǐng)域的大量算法可以大致分為靜態(tài)負(fù)載平衡和動(dòng)態(tài)負(fù)載平衡兩個(gè)方面。對(duì)系統(tǒng)負(fù)載的準(zhǔn)確預(yù)測(cè)往往是靜態(tài)負(fù)載平衡算法的基礎(chǔ)，對(duì)于改進(jìn)動(dòng)態(tài)負(fù)載

4、平衡的效果也很重要。在數(shù)據(jù)流系統(tǒng)中，對(duì)于數(shù)據(jù)的處理有實(shí)時(shí)性要求。我們提出以加權(quán)時(shí)間性能比來(lái)評(píng)價(jià)算法的優(yōu)劣，我們考察了效率很高的一些線(xiàn)性時(shí)間序列預(yù)測(cè)算法，如移動(dòng)平均法，指數(shù)平滑法和GM(1，1)法，并針對(duì)流處理的特點(diǎn)作了相應(yīng)的修改。這些算法在分布式流處理領(lǐng)域具有很好的時(shí)間性能比。
　　 本文設(shè)計(jì)了一種新的大規(guī)模分布式數(shù)據(jù)流處理系統(tǒng)的體系結(jié)構(gòu)，系統(tǒng)由一組異構(gòu)的服務(wù)器集群組成，負(fù)載在每個(gè)服務(wù)器集群內(nèi)部多臺(tái)同構(gòu)的服務(wù)器之間獲得平衡，從而

5、達(dá)到整個(gè)系統(tǒng)的負(fù)載平衡。集群設(shè)計(jì)的主要目標(biāo)之一是以資源換性能，服務(wù)器集群中服務(wù)器的最大數(shù)目足夠保證系統(tǒng)不再發(fā)生過(guò)載現(xiàn)象，不再需要會(huì)降低性能的卸載技術(shù)。而且投入運(yùn)行的服務(wù)器的數(shù)目根據(jù)實(shí)際的系統(tǒng)負(fù)載來(lái)決定，負(fù)載較輕時(shí)，一部分服務(wù)器可以進(jìn)入休眠狀態(tài)來(lái)減少能源的消耗。在系統(tǒng)靜態(tài)負(fù)載平衡方面，我們研究了很多相應(yīng)的啟發(fā)式方法，并在此基礎(chǔ)上提出了一種高效率、高性能的靜態(tài)平衡算法。首先根據(jù)一個(gè)初始化策略把任務(wù)分配到機(jī)器上，每臺(tái)機(jī)器的任務(wù)數(shù)目、負(fù)載大致相