分布式并行數(shù)據(jù)庫系統(tǒng)中任務(wù)分配算法的設(shè)計

1、第35卷第6期電子科技大學(xué)學(xué)報V ol.35 No.62006年12月 Journal of University of Electronic Science and Technology of China Dec. 2006 ·計算機(jī)工程與應(yīng)用·分布式并行數(shù)據(jù)庫系統(tǒng)中任務(wù)分配算法的設(shè)計顧攀,劉心松,陳小輝,邱元杰,左朝樹(電子科技大學(xué)計算機(jī)科學(xué)與工程學(xué)院成都 610054【摘要】在分析傳統(tǒng)任務(wù)分配算法的基礎(chǔ)上,設(shè)計了一種改進(jìn)的混合啟動自適應(yīng)任務(wù)分配算法。該算法根據(jù)系統(tǒng)總體負(fù)載變化自適應(yīng)地選擇啟動策略,考慮任務(wù)對資源的需求和系統(tǒng)中的數(shù)據(jù)分布,有效地選擇節(jié)點(diǎn)進(jìn)行探詢,使任務(wù)分

2、配的開銷最小化。在分布式并行數(shù)據(jù)庫系統(tǒng)DPSQL中的使用表明,該算法比傳統(tǒng)算法提供更高的任務(wù)執(zhí)行效率和更好的系統(tǒng)穩(wěn)定性。關(guān)鍵詞分布式并行數(shù)據(jù)庫系統(tǒng); 任務(wù)分配; 自適應(yīng); 混合啟動Design of an Algorithm for Task Assignment inDistributed Parallel Database SystemGU Pan,LIU Xin-song,CHEN Xiao-hui,QIU Yuan-jie,ZUO Chao-shu(School of Computer Science & Engineering, Univ. of Electron. Sci.

3、 & Tech. of China Chengdu 610054 Abstract Based on the analysis of the algorithms commonly used for task assignment, this paper puts forward an improved both-initiated adaptive algorithm for task assignment. This algorithm adaptively determines initiated strategy according to the system load. In

4、 the system, the data requirement of each task and the data distribution are considered.The nodes are effectively chosen so as to minimize the costs for task assignment. This algorithm has been successfully applied in distributed parallel database system DPSQL. It has been shown that the method has

5、better efficiency and stability than the common algorithms for task assignment.Key words distributed parallel database system; task assignment; adaptive; both-initiated strategy 在分布式并行系統(tǒng)中的任務(wù)分配算法可廣義地劃分為動態(tài)、靜態(tài)和自適應(yīng)三種1。動態(tài)任務(wù)分配在啟動策略上可分為發(fā)送者啟動、接收者啟動和混合啟動2。自適應(yīng)算法是一類特殊的動態(tài)任務(wù)分配算法,根據(jù)系統(tǒng)狀態(tài)信息動態(tài)選擇任務(wù)分配所采用的啟動策略、轉(zhuǎn)移策略及選擇策

6、略3。文獻(xiàn)4提出了一種啟發(fā)式穩(wěn)定算法,刻意忽略了訪問遠(yuǎn)程數(shù)據(jù)與本地數(shù)據(jù)的差別。文獻(xiàn)5明確了應(yīng)考慮各節(jié)點(diǎn)資源分布情況和任務(wù)對資源的需求,避免資源的遠(yuǎn)程訪問,卻沒有根據(jù)這一原則提出具體的分配算法。文獻(xiàn)6提出應(yīng)任務(wù)要求轉(zhuǎn)移和復(fù)制數(shù)據(jù),當(dāng)數(shù)據(jù)副本較大時,付出的代價很大。文獻(xiàn)6還在算法中考慮了系統(tǒng)負(fù)載狀況,由于負(fù)載輕重的劃分未針對平均負(fù)載進(jìn)行,使接收者啟動在欠載時延遲過大,發(fā)送者啟動在超載時效率太低。本文設(shè)計了一種改進(jìn)的混合啟動自適應(yīng)任務(wù)分配算法,通過系統(tǒng)平均負(fù)載來確定各節(jié)點(diǎn)狀態(tài),自適應(yīng)地選擇啟動策略;并根據(jù)數(shù)據(jù)分布情況對任務(wù)進(jìn)行分配,減少了數(shù)據(jù)訪問的代價,克服了盲目探詢引起的不穩(wěn)定性。該算法已運(yùn)用于自

7、主研發(fā)的分布式并行數(shù)據(jù)庫系統(tǒng)DPSQL中,具有良好的效果。1 分布式并行數(shù)據(jù)庫系統(tǒng)DPSQL概述分布式并行數(shù)據(jù)庫系統(tǒng)DPSQL是由多臺高性能PC通過高速網(wǎng)絡(luò)連接在一起構(gòu)成數(shù)據(jù)庫服務(wù)器群,為大量用戶提供高性能、高可靠、大數(shù)據(jù)量數(shù)據(jù)庫服務(wù)的分布式并行系統(tǒng)。系統(tǒng)中的各節(jié)點(diǎn)協(xié)同完成全局?jǐn)?shù)據(jù)目錄維護(hù)、數(shù)據(jù)副本智能控制、節(jié)點(diǎn)狀態(tài)切換等系統(tǒng)管理工作。對客戶端而言,它是一個單一映象的數(shù)據(jù)庫服務(wù)器群,隱藏了數(shù)據(jù)冗余和分布信息。任一節(jié)點(diǎn)均可代表服務(wù)器群接收用戶請求,此后該節(jié)點(diǎn)(稱為協(xié)調(diào)節(jié)點(diǎn)根據(jù)用戶的操作類型、數(shù)據(jù)的分布情況和系統(tǒng)的負(fù)載信息,將待執(zhí)行的用戶任務(wù)分配到最合適的節(jié)收稿日期:2004 04 15作者簡介:

8、顧攀(1980 ,男,碩士,主要從事分布式數(shù)據(jù)庫系統(tǒng)等方面的研究.第6期 顧 攀 等: 分布式并行數(shù)據(jù)庫系統(tǒng)中任務(wù)分配算法的設(shè)計 947 點(diǎn)(稱為執(zhí)行節(jié)點(diǎn)。執(zhí)行節(jié)點(diǎn)在完成任務(wù)后,將執(zhí)行響應(yīng)傳遞給協(xié)調(diào)節(jié)點(diǎn),最后將結(jié)果返回給客戶。從上述系統(tǒng)結(jié)構(gòu)及執(zhí)行過程可以看出,執(zhí)行節(jié)點(diǎn)的選擇好壞對于用戶任務(wù)的執(zhí)行效率和整個系統(tǒng)的處理開銷影響極大。因此,為了高效低價地將協(xié)調(diào)節(jié)點(diǎn)上的任務(wù)分配到執(zhí)行節(jié)點(diǎn),減少任務(wù)的執(zhí)行時間,本文設(shè)計了改進(jìn)的混合啟動自適應(yīng)任務(wù)分配算法。2 改進(jìn)的混合啟動自適應(yīng)任務(wù)分配算法2.1 相關(guān)定義設(shè)服務(wù)器系統(tǒng)S 由n 個可用的節(jié)點(diǎn)構(gòu)成,S =S 1,S 2,",S n ;系統(tǒng)中的數(shù)據(jù)劃

9、分為p 個數(shù)據(jù)分片,D =D 1,D 2, ,D "p ;系統(tǒng)中共有m 個任務(wù),T =T 1,T 2,",T m ;系統(tǒng)中任務(wù)等待隊(duì)列W 的長度為Q ;W i 對應(yīng)第i 個節(jié)點(diǎn)待處理任務(wù)組成的隊(duì)列,其長度為Q i ,W =W 1W 2"W n ,Q =Q 1+Q 2+"+Q n 。定義 1 節(jié)點(diǎn)負(fù)載L i :某一節(jié)點(diǎn)的CPU 隊(duì)列長度與系統(tǒng)中所有節(jié)點(diǎn)的平均CPU 隊(duì)列長度的比值。設(shè)節(jié)點(diǎn)S i (i =1,2,",n 的CPU 隊(duì)列長度為l i ,則節(jié)點(diǎn)S i 的負(fù)載為:111/(/n i i i j i j j L l l l l nl l n

10、 =n j (1定義 2 節(jié)點(diǎn)類型向量T V :根據(jù)節(jié)點(diǎn)負(fù)載L 確定其取值,記錄各節(jié)點(diǎn)類型的一維向量,其大小為n 。1101111i V i i L f T i f L f f L <=+<節(jié)點(diǎn)S i 處于欠載,為接收節(jié)點(diǎn)節(jié)點(diǎn)S i 處于平衡,其負(fù)載適中節(jié)點(diǎn)S i 處于超載,為發(fā)磅節(jié)點(diǎn)閾值f 根據(jù)系統(tǒng)處理能力和資源配置等條件設(shè)置i =1,2,n (2 定義 3 數(shù)據(jù)分布矩陣D M :記錄數(shù)據(jù)分片在系統(tǒng)各節(jié)點(diǎn)分布情況的矩陣,其大小為n × p 。1,0M D i k =節(jié)點(diǎn)S i 上有數(shù)據(jù)分片D k 的副本分布節(jié)點(diǎn)S i 上無數(shù)據(jù)分片D k 的副本分布1,1i n k p

11、(3 定義 4 數(shù)據(jù)分片冗余等級向量R V :記錄各個數(shù)據(jù)分片在系統(tǒng)中冗余等級的一維向量,其大小為p 。1,1,2,n M i R k D i k k p ="V (4定義 5 任務(wù)執(zhí)行開銷矩陣A M :記錄任務(wù)在節(jié)點(diǎn)執(zhí)行所產(chǎn)生開銷的矩陣,其大小為m × n 。,|1,1M M ,A g i g m i n =A A M g ,i 為任務(wù)T g 在節(jié)點(diǎn)S i 上的執(zhí)行開銷 (5定義 6 任務(wù)分配矩陣X M :記錄任務(wù)在節(jié)點(diǎn)中分配情況的矩陣,其大小為m × n 。1,0M X g i =任務(wù)T g 已分配給節(jié)點(diǎn)S i 任務(wù)T g 未分配給節(jié)點(diǎn)S i 1,1g m i

12、 n (6定義 7 節(jié)點(diǎn)任務(wù)執(zhí)行開銷數(shù)組A A :記錄節(jié)點(diǎn)所有任務(wù)執(zhí)行開銷之和的一維數(shù)組,其大小為n 。1(,1,2,m A M M g A i X g i A g i i ="n =,= (7定義 8 任務(wù)間通訊開銷矩陣T M :記錄分配于不同節(jié)點(diǎn)執(zhí)行的兩個任務(wù)間進(jìn)行信息交換所產(chǎn)生通訊開銷的矩陣,其大小為m × m 。,|1,M M T g h g h m =T T M g ,h 為任務(wù)T g 和任務(wù)T h 被分配于不同節(jié)點(diǎn)執(zhí)行的通訊開銷 (8 定義 9 節(jié)點(diǎn)任務(wù)通訊開銷數(shù)組C A :記錄節(jié)點(diǎn)所有任務(wù)與其他節(jié)點(diǎn)任務(wù)通訊開銷之和的一維數(shù)組,其大小為n 。,1(,(1,1,2

13、,m A M M M g h C i T g h X g i X h i i n =" (9 定義 10 節(jié)點(diǎn)任務(wù)總開銷數(shù)組F A :記錄節(jié)點(diǎn)計算開銷與通訊開銷之和的一維數(shù)組,其大小為n 。 1,1(,(1,1,2,m m A A A M M M M M g g h F i A i C i X g i A g i T g h X g i X h i i n =+=+=" (10定義 11 節(jié)點(diǎn)間通訊開銷矩陣C M :記錄節(jié)點(diǎn)間傳送單位信息產(chǎn)生通訊開銷的矩陣,其大小為n × n 。,|1,M M M C i j i j n C i j =C 為節(jié)點(diǎn)S i 和節(jié)點(diǎn)S

14、j 間傳送單位信息產(chǎn)生的通訊開銷 (11電 子 科 技 大 學(xué) 學(xué) 報 第35卷948 定義 12 節(jié)點(diǎn)間任務(wù)轉(zhuǎn)移開銷P g(i ,j :某一任務(wù)在系統(tǒng)中的任意兩點(diǎn)間轉(zhuǎn)移所產(chǎn)生的開銷。設(shè)任務(wù)T g (g =1,2,",m 執(zhí)行代碼的數(shù)據(jù)量為C size (T g ,任務(wù)T g 執(zhí)行后響應(yīng)和結(jié)果信息的數(shù)據(jù)量為R size (T g ,則T g 從節(jié)點(diǎn)S i 轉(zhuǎn)移到節(jié)點(diǎn)S j (1i ,j n 所產(chǎn)生的開銷P g (i ,j 為:(,size size ,(g i j M g g P C i j C T R T =+ (122.2 算法描述傳統(tǒng)的混合啟動自適應(yīng)任務(wù)分配算法在系統(tǒng)超載時,發(fā)

15、送者啟動部分的探詢可能導(dǎo)致系統(tǒng)的不穩(wěn)定性;在進(jìn)行任務(wù)分配時,未考慮任務(wù)對于資源的需求,且未考慮任務(wù)分配時的開銷最小化問題,容易導(dǎo)致任務(wù)的執(zhí)行效率降低。為此,對混合啟動自適應(yīng)任務(wù)分配算法進(jìn)行改進(jìn),改進(jìn)的算法有以下特點(diǎn):(1 結(jié)合數(shù)據(jù)分布信息進(jìn)行任務(wù)分配,滿足其對資源的需求;(2 任務(wù)轉(zhuǎn)移后所產(chǎn)生的開銷最小,提高了任務(wù)執(zhí)行的效率;(3 根據(jù)系統(tǒng)總負(fù)載來控制發(fā)送者啟動,避免了在高負(fù)載時帶來的系統(tǒng)不穩(wěn)定;(4 利用節(jié)點(diǎn)任務(wù)等待隊(duì)列和系統(tǒng)平均任務(wù)等待量的關(guān)系,使接收者找到更合適的任務(wù);(5 依據(jù)數(shù)據(jù)分布有選擇地探詢節(jié)點(diǎn),避免盲目探詢帶來的開銷;(6 由數(shù)據(jù)分片的冗余等級靈活確定探詢次數(shù)上限,防止系統(tǒng)崩潰

16、。本文設(shè)計了發(fā)送者啟動和接收者啟動2個子模塊:1 發(fā)送者啟動子模塊的詳細(xì)流程發(fā)送方:(1 T V i >0,節(jié)點(diǎn)S i 變?yōu)榘l(fā)送者,待分配任務(wù)為T g ,需訪問數(shù)據(jù)分片D k 。(2 在S 中查找所有T V j <0,且D M j ,k =1的節(jié)點(diǎn)S j ,計算待分配任務(wù)T g 從節(jié)點(diǎn)S i 分配到節(jié)點(diǎn)S j 后產(chǎn)生的代價為:(,size size 1,1(,(1,(,(m mj A g i j M M M M M M g g h e h C F j P X h j A h j T e h X e j X h j C i j C T R T =+=+ (13 根據(jù)C j 的大小選擇

17、探詢節(jié)點(diǎn),找到其任務(wù)總開銷較小、在系統(tǒng)中引起的通訊開銷較小的節(jié)點(diǎn)作為接收節(jié)點(diǎn)候選者,加快任務(wù)執(zhí)行速度,減少系統(tǒng)開銷。(3 取符合條件的各個節(jié)點(diǎn)中代價數(shù)C j 最小的節(jié)點(diǎn)S j 作為探詢節(jié)點(diǎn),發(fā)送探詢消息,若從節(jié)點(diǎn)S j 返回的響應(yīng)為T V j <0,執(zhí)行(4;否則執(zhí)行(5。(4 將任務(wù)T g 從節(jié)點(diǎn)S i 轉(zhuǎn)移到節(jié)點(diǎn)S j ,重新計算L i 、Q i 、T V i ,算法結(jié)束。(5 根據(jù)節(jié)點(diǎn)S j 的響應(yīng)同步更新所有其他節(jié)點(diǎn)中節(jié)點(diǎn)類型向量T V j ,重復(fù)(2和(3;選擇另一節(jié)點(diǎn)作為探詢節(jié)點(diǎn),直至滿足以下條件之一: h 1,2,",n ,T V h >1; 探詢次數(shù)2&#

18、215;R V k 次; T V i <1。接收方:(1 節(jié)點(diǎn)S j 接收到節(jié)點(diǎn)S i 發(fā)送的探詢消息后,同步更新節(jié)點(diǎn)類型向量中T V i 的取值。(2 S j 計算節(jié)點(diǎn)負(fù)載L j ,并取節(jié)點(diǎn)類型向量T V j 返回給探詢節(jié)點(diǎn)S i ;若T V j <0,執(zhí)行(3;否則算法結(jié)束。(3 準(zhǔn)備執(zhí)行轉(zhuǎn)移的任務(wù)T g ,置X M g ,j =1,重新計算L j 、Q j 、T V j 、A A (j 、C A (j 、F A (j ,算法結(jié)束。2 接收者啟動子模塊的詳細(xì)流程接收方:(1 T V j <0,節(jié)點(diǎn)S j 變?yōu)榻邮照摺?2 在S 中查找所有T V i >0的節(jié)點(diǎn)S i

19、 作為探詢節(jié)點(diǎn),分別發(fā)送探詢消息,若從節(jié)點(diǎn)S i 返回的響應(yīng)為T V i >0,執(zhí)行(3;否則執(zhí)行(6。(3 向節(jié)點(diǎn)S i 探詢是否有合適的任務(wù)T g 從節(jié)點(diǎn)S i 轉(zhuǎn)移到節(jié)點(diǎn)S j ,若節(jié)點(diǎn)S i 返回有任務(wù)T g 可轉(zhuǎn)移且代價最小,執(zhí)行(4;否則執(zhí)行(5。(4 準(zhǔn)備執(zhí)行轉(zhuǎn)移的任務(wù)T g ,置X M g , j =1,重新計算L j 、Q j 、T V j 、A A (j 、C A (j 、F A (j ,算法結(jié)束。(5 重復(fù)(2,選擇另一個節(jié)點(diǎn)作為探詢節(jié)點(diǎn),直至滿足以下條件之一: h 1,2,",n ,T V h <1; 探詢次數(shù)達(dá)到n 次; T V j >1。

20、(6 根據(jù)節(jié)點(diǎn)S i 的響應(yīng),同步更新所有其他節(jié)點(diǎn)中節(jié)點(diǎn)類型向量關(guān)于T V i 的取值,重復(fù)(2,選擇另一節(jié)點(diǎn)作為探詢節(jié)點(diǎn),直至滿足以下條件之一:h 1,2,",n ,T V h <1; 探詢次數(shù)n 次; T V j >1。發(fā)送方:第6期顧攀等: 分布式并行數(shù)據(jù)庫系統(tǒng)中任務(wù)分配算法的設(shè)計949(1 節(jié)點(diǎn)S i接收到節(jié)點(diǎn)S j的探詢消息后,同步更新節(jié)點(diǎn)類型向量中T Vj的取值。(2 S i計算節(jié)點(diǎn)負(fù)載L i,取節(jié)點(diǎn)類型向量T Vi的值返回給探詢節(jié)點(diǎn)S j,若T Vi>0,執(zhí)行(3;否則算法結(jié)束。(3 在節(jié)點(diǎn)S i的任務(wù)等待隊(duì)列W i中查找訪問數(shù)據(jù)分片D k的任務(wù)T g

21、,使D Mj,k=1,由式(13計算將任務(wù)T g從節(jié)點(diǎn)S i轉(zhuǎn)移到節(jié)點(diǎn)S j后產(chǎn)生的代價數(shù)C j,根據(jù)C j的大小選擇轉(zhuǎn)移任務(wù),將轉(zhuǎn)移后節(jié)點(diǎn)S j的任務(wù)總開銷較小、引起的通訊開銷較小的任務(wù)T g作為可轉(zhuǎn)移任務(wù),若在節(jié)點(diǎn)S i查找可轉(zhuǎn)移任務(wù)T g成功,執(zhí)行(4;否則執(zhí)行(5。(4 向節(jié)點(diǎn)S j發(fā)送任務(wù)T g可轉(zhuǎn)移的消息后,任務(wù)T g從節(jié)點(diǎn)S i轉(zhuǎn)移到節(jié)點(diǎn)S j,重新計算L i、Q i、T Vi,算法結(jié)束。(5 向節(jié)點(diǎn)S j發(fā)送無滿足條件任務(wù)可轉(zhuǎn)移的消息,算法結(jié)束。根據(jù)系統(tǒng)總負(fù)載和任務(wù)等待量來進(jìn)行選擇。當(dāng)節(jié)點(diǎn)接收一個新任務(wù)時,首先根據(jù)數(shù)據(jù)的分布情況和節(jié)點(diǎn)的當(dāng)前狀態(tài),判斷是否需要轉(zhuǎn)移任務(wù)。如果不需轉(zhuǎn)

22、移就在本地進(jìn)行處理,否則查看系統(tǒng)的總體負(fù)載情況。當(dāng)系統(tǒng)中接收者數(shù)目比發(fā)送者多時,算法自動調(diào)用發(fā)送者啟動子模塊,否則等待接收者啟動子模塊來匹配任務(wù)。當(dāng)節(jié)點(diǎn)的任務(wù)等待隊(duì)列長度不小于系統(tǒng)平均等待隊(duì)長時,強(qiáng)制調(diào)用發(fā)送者啟動子模塊一次。另一方面,當(dāng)節(jié)點(diǎn)完成一個任務(wù)時,首先判斷節(jié)點(diǎn)的當(dāng)前狀態(tài),只有當(dāng)節(jié)點(diǎn)變?yōu)榻邮照邥r,才考慮申請新的任務(wù)。當(dāng)該節(jié)點(diǎn)的任務(wù)等待隊(duì)列長度超過系統(tǒng)平均等待隊(duì)長時,依據(jù)數(shù)據(jù)的分布情況在等待隊(duì)列中尋找一個本節(jié)點(diǎn)能滿足其資源需求的任務(wù),否則調(diào)用接收者啟動子模塊從其他節(jié)點(diǎn)的等待隊(duì)列中申請一個合適的任務(wù)。2.3 性能測試為測試算法性能,從客戶機(jī)連接到DPSQL服務(wù)器,動態(tài)增減用戶數(shù)量,并對其中一些用戶的SQL語句平均執(zhí)行時間進(jìn)行記錄。設(shè)定具體測試環(huán)境為:9臺P4 2G、512 M內(nèi)存的PC作為DPSQL服務(wù)器;15臺P3 600 M、128 M內(nèi)存的PC作為DPSQL客戶機(jī);100 M交換機(jī)和100 M網(wǎng)卡;測試數(shù)據(jù)庫共10個,以庫為單位進(jìn)行數(shù)據(jù)分片,每個數(shù)據(jù)分片的冗余等級為35;每個庫中有10 000個表,最大表共有5萬條記錄,每條記錄共20個字段,每個字段的平均長度為300B。根據(jù)系統(tǒng)情況,設(shè)置算法中的閾值f為0.2。測試結(jié)果如表1所示,系