基于分布式哈希表的p2p系統(tǒng)負(fù)載均衡算法

基于分布式哈希表的p2p系統(tǒng)負(fù)載均衡算法

負(fù)載平衡是dhs系統(tǒng)的核心問題之一。負(fù)載平衡的程度在一定程度上決定了系統(tǒng)性能的好壞。hlt系統(tǒng)負(fù)載不平衡的原因是哈希函數(shù)生成的特征，這導(dǎo)致了o（gln）不平衡的因素。由于系統(tǒng)中節(jié)點(diǎn)能力的差異，節(jié)點(diǎn)之間的不均勻負(fù)載問題變得更加嚴(yán)重。因此，許多研究人員提出了許多適用于dhs系統(tǒng)的負(fù)載補(bǔ)償策略。一些策略沒有考慮節(jié)點(diǎn)的異質(zhì)性，而某些策略會導(dǎo)致大量的負(fù)載轉(zhuǎn)移成本，或增加路徑復(fù)雜性和路徑維護(hù)成本。本文提出了SDYA負(fù)載均衡算法.該算法基于虛擬服務(wù)器策略,根據(jù)網(wǎng)絡(luò)負(fù)載情況,采用特殊的ID生成算法有效地均衡分配負(fù)載;采用特殊的動態(tài)負(fù)載調(diào)整算法保證了最小的轉(zhuǎn)移開銷.1dct節(jié)點(diǎn)負(fù)載均衡P2P系統(tǒng)中的每項(xiàng)資源都給系統(tǒng)造成了負(fù)載.SDYA可應(yīng)用于所有的DHT系統(tǒng),但應(yīng)包括2個(gè)假設(shè)條件.1)將影響節(jié)點(diǎn)能力的因素,如CPU、存儲容量、內(nèi)存、I/O響應(yīng)率、帶寬等統(tǒng)一視為一種資源.2)負(fù)載均衡分布在ID地址空間上.一般情況下,資源數(shù)據(jù)遠(yuǎn)遠(yuǎn)多于網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù),故資源數(shù)據(jù)在ID空間上分配均勻,或其不均衡度可以忽略不計(jì).1.1DHT系統(tǒng)中節(jié)點(diǎn)的負(fù)載在DHT系統(tǒng)中,節(jié)點(diǎn)的負(fù)載既包括其被占用的存儲空間,也包括處理消息所帶來的CPU開銷、傳輸數(shù)據(jù)和應(yīng)用層路由維護(hù)所帶來的帶寬消耗.故將DHT節(jié)點(diǎn)的負(fù)載抽象為3類.1)存儲負(fù)載.節(jié)點(diǎn)存儲所有資源占用的存儲空間.2)路由負(fù)載.節(jié)點(diǎn)路由維護(hù)、轉(zhuǎn)發(fā)消耗的帶寬.3)查詢負(fù)載.節(jié)點(diǎn)處理查詢請求的負(fù)載.在ID空間上資源均勻分布且不存在熱點(diǎn)資源的DHT系統(tǒng)中可用節(jié)點(diǎn)所負(fù)責(zé)地址空間的不均衡度來表示其負(fù)載的不均衡度.SDYA算法通過均衡節(jié)點(diǎn)地址空間達(dá)到負(fù)載均衡的目的.而對于存在熱點(diǎn)資源的情況,由于其具有獨(dú)立性和實(shí)時(shí)性,可以采用對熱點(diǎn)資源進(jìn)行備份或cache等方法.1.2負(fù)載度量的相關(guān)術(shù)語1)節(jié)點(diǎn)容量(C).表示節(jié)點(diǎn)的最大承載能力.2)虛擬ID(虛擬服務(wù)器)相當(dāng)于DHT系統(tǒng)中的節(jié)點(diǎn),每個(gè)物理節(jié)點(diǎn)對應(yīng)v個(gè)虛擬服務(wù)器.3)系統(tǒng)負(fù)載利用率,即系統(tǒng)總負(fù)載量與總?cè)萘康谋壤?定義下列參數(shù).L:整個(gè)網(wǎng)絡(luò)ID空間的大小.RSpace:節(jié)點(diǎn)實(shí)際負(fù)責(zé)的負(fù)載量,用變量R表示.OSpace:負(fù)載完全均衡情況下,節(jié)點(diǎn)應(yīng)該負(fù)責(zé)的負(fù)載量,用變量O表示.與節(jié)點(diǎn)容量成正比.節(jié)點(diǎn)的負(fù)載不均衡度(LB):節(jié)點(diǎn)實(shí)際負(fù)載與理想負(fù)載的偏差程度,用變量B表示.負(fù)載不均衡度的閾值(LN):負(fù)載均衡算法所要實(shí)現(xiàn)的均衡目標(biāo),即理想情況下,網(wǎng)絡(luò)中所有節(jié)點(diǎn)LB的絕對值都應(yīng)小于閾值LN,用變量Y表示.2節(jié)點(diǎn)負(fù)載分配算法本文所提出的SDYA算法是基于虛擬服務(wù)器策略的.在靜態(tài)負(fù)載分配算法中,利用特殊的ID生成算法可有效地為節(jié)點(diǎn)均衡分配負(fù)載;同時(shí),當(dāng)網(wǎng)絡(luò)發(fā)生動蕩時(shí),采用特殊的動態(tài)負(fù)載調(diào)整機(jī)制,以最快的速度和最小的轉(zhuǎn)移開銷可保證系統(tǒng)負(fù)載重新均衡.2.1種新保活機(jī)制SDYA算法利用引導(dǎo)服務(wù)器作為負(fù)載均衡策略的決策者,減少了均衡開銷,提高了系統(tǒng)的穩(wěn)定性.筆者在引導(dǎo)服務(wù)器和網(wǎng)絡(luò)節(jié)點(diǎn)之間設(shè)計(jì)了一種新穎的?；顧C(jī)制,保證了引導(dǎo)服務(wù)器最低的?；詈拓?fù)載均衡決策開銷,避免了單點(diǎn)失效的問題.1a.正常離節(jié)點(diǎn)①新節(jié)點(diǎn)加入時(shí),將自己的節(jié)點(diǎn)信息上報(bào)給引導(dǎo)服務(wù)器,引導(dǎo)服務(wù)器保存節(jié)點(diǎn)的信息;②節(jié)點(diǎn)離開時(shí),a.正常離開,離開節(jié)點(diǎn)自己通知引導(dǎo)服務(wù)器;b.異常離開,離開節(jié)點(diǎn)的鄰居節(jié)點(diǎn)探測到該節(jié)點(diǎn)離開后通知引導(dǎo)服務(wù)器,引導(dǎo)服務(wù)器檢測證實(shí).可以看出,?；顧C(jī)制不需要引導(dǎo)服務(wù)器實(shí)時(shí)探測節(jié)點(diǎn)的狀態(tài),故用于?；顧C(jī)制的開銷非常小.2基于sdra的負(fù)載均衡優(yōu)化①新節(jié)點(diǎn)加入,引導(dǎo)服務(wù)器評估得到新節(jié)點(diǎn)容量C,利用靜態(tài)負(fù)載分配算法為節(jié)點(diǎn)分配虛擬ID;②網(wǎng)絡(luò)發(fā)生動蕩時(shí),引導(dǎo)服務(wù)器通過?；顧C(jī)制檢測到節(jié)點(diǎn)加入或離開后,將運(yùn)行動態(tài)負(fù)載調(diào)整算法,調(diào)整網(wǎng)絡(luò)中極少部分的負(fù)載,使所有節(jié)點(diǎn)負(fù)載滿足閾值LN的要求.引導(dǎo)服務(wù)器用于負(fù)載均衡決策的開銷只與SDYA算法復(fù)雜度和運(yùn)行該算法的頻率有關(guān).而提出的SDYA算法簡單、復(fù)雜度低,引導(dǎo)服務(wù)器用于負(fù)載均衡的總體開銷小.2.2靜態(tài)負(fù)載分配算法傳統(tǒng)虛擬服務(wù)器負(fù)載均衡算法中,每個(gè)虛擬ID的生成是隨機(jī)的,虛擬ID數(shù)量必須足夠多,才能達(dá)到負(fù)載均衡,從而使系統(tǒng)中路由維護(hù)開銷增大.而本文提出的靜態(tài)負(fù)載分配算法,每個(gè)虛擬ID的生成都有針對性,用來分擔(dān)目前網(wǎng)絡(luò)中負(fù)載最重節(jié)點(diǎn)的部分負(fù)載,只需要運(yùn)行少量虛擬ID就可以達(dá)到負(fù)載均衡.初始節(jié)點(diǎn)在建立網(wǎng)絡(luò)時(shí)向引導(dǎo)服務(wù)器上報(bào)自己的各種參數(shù),引導(dǎo)服務(wù)器根據(jù)網(wǎng)絡(luò)應(yīng)用需求進(jìn)行評估得到節(jié)點(diǎn)的容量,并配置初始單位容量上運(yùn)行的虛擬ID個(gè)數(shù)V,最后通過隨機(jī)生成方式為初始節(jié)點(diǎn)分配「CV┐個(gè)虛擬ID.若節(jié)點(diǎn)不是網(wǎng)絡(luò)的初始節(jié)點(diǎn),假定網(wǎng)絡(luò)已存在N-1個(gè)節(jié)點(diǎn),則引導(dǎo)服務(wù)器收到新節(jié)點(diǎn)N的加入請求,將執(zhí)行靜態(tài)負(fù)載分配算法,其偽代碼如下:在靜態(tài)負(fù)載分配算法中,引導(dǎo)服務(wù)器根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)的負(fù)載信息計(jì)算各節(jié)點(diǎn)的LB;然后獲取負(fù)載最重節(jié)點(diǎn)x上負(fù)載量最大的虛擬節(jié)點(diǎn)VID;在VID負(fù)責(zé)的ID空間上隨機(jī)插入新虛擬節(jié)點(diǎn)xID,使得生成的新虛擬節(jié)點(diǎn)更有針對性、更有效.循環(huán)執(zhí)行該過程直到新節(jié)點(diǎn)的LB稍大于0為止.此查找過程復(fù)雜度為O(N+X),其中X指負(fù)載最重的節(jié)點(diǎn)x的虛擬ID個(gè)數(shù).2.3動態(tài)負(fù)載調(diào)整算法節(jié)點(diǎn)加入或退出網(wǎng)絡(luò)后,導(dǎo)致網(wǎng)絡(luò)中其他節(jié)點(diǎn)的負(fù)載發(fā)生變化.一旦網(wǎng)絡(luò)中存在節(jié)點(diǎn)的LB不滿足閾值要求,引導(dǎo)服務(wù)器將運(yùn)行動態(tài)負(fù)載調(diào)整算法,使得網(wǎng)絡(luò)中所有節(jié)點(diǎn)的LB滿足閾值LN的要求.動態(tài)負(fù)載調(diào)整算法是以均衡開銷最小和涉及的節(jié)點(diǎn)數(shù)最少為最優(yōu)目標(biāo)而設(shè)計(jì)的,它又可分為負(fù)載調(diào)配算法和負(fù)載轉(zhuǎn)移算法2部分.假設(shè)節(jié)點(diǎn)V離開了網(wǎng)絡(luò),引導(dǎo)服務(wù)器探測到節(jié)點(diǎn)離開后:1)計(jì)算所有節(jié)點(diǎn)的Bi=Ri/Oi-1,其中Oi從2)判斷網(wǎng)絡(luò)中各節(jié)點(diǎn)的負(fù)載不均衡度是否不滿足閾值LN要求,若不滿足要求,則運(yùn)行負(fù)載調(diào)配算法和負(fù)載轉(zhuǎn)移算法;若滿足要求,則動態(tài)負(fù)載調(diào)整算法運(yùn)行結(jié)束.2.3.1節(jié)點(diǎn)的lb分配及性能修改負(fù)載調(diào)配算法的偽代碼如下://按照Lt(N)的正序,依次將Lt>0節(jié)點(diǎn)的負(fù)載轉(zhuǎn)移到按Lt(N)逆序的那些Lt<0的節(jié)點(diǎn)上.算法首先將網(wǎng)絡(luò)節(jié)點(diǎn)的LB進(jìn)行降序排列,并計(jì)算為了滿足閾值LN要求各節(jié)點(diǎn)需要轉(zhuǎn)移的負(fù)載量Lt;再求出需要轉(zhuǎn)出和轉(zhuǎn)入的總負(fù)載量S和S′,而最終需要轉(zhuǎn)移的負(fù)載量Sm應(yīng)為二者中最大者;為了滿足Sm和LN的要求,需要修改節(jié)點(diǎn)的Lt:當(dāng)S>S′時(shí),需要輕載的節(jié)點(diǎn)多承擔(dān)一些負(fù)載,但仍保證其B≤0;當(dāng)S<S′時(shí),需要重載的節(jié)點(diǎn)多轉(zhuǎn)出一些負(fù)載,但仍保證其B≥0;最終得到各節(jié)點(diǎn)的轉(zhuǎn)移負(fù)載Lt.其算法復(fù)雜度為O(M),M為負(fù)載發(fā)生變化的節(jié)點(diǎn)數(shù).2.3.2虛擬id的選擇和加標(biāo)數(shù)負(fù)載轉(zhuǎn)移算法能保證找到合適的虛擬ID進(jìn)行轉(zhuǎn)移.假定節(jié)點(diǎn)a需要搬移Lt的負(fù)載到節(jié)點(diǎn)b上,負(fù)載搬移時(shí)要遵循2個(gè)原則.原則1搬移的數(shù)據(jù)量少.選擇要搬移的ID時(shí),搬移數(shù)據(jù)盡量少,盡量接近Lt;原則2搬移的ID數(shù)少.1)如果節(jié)點(diǎn)a存在某虛擬ID的負(fù)載與Lt很接近,則選擇該虛擬ID;2)如果節(jié)點(diǎn)a所有虛擬ID的負(fù)載都比Lt小,則要選擇多個(gè)虛擬ID進(jìn)行轉(zhuǎn)移,同樣遵循搬移數(shù)據(jù)和ID數(shù)最少的原則選擇虛擬ID;3)如果節(jié)點(diǎn)a所有虛擬ID的負(fù)載都比Lt大,則節(jié)點(diǎn)a選擇某個(gè)虛擬ID與節(jié)點(diǎn)b某個(gè)虛擬ID交換,使之負(fù)載的差值盡量接近Lt.3模擬實(shí)驗(yàn)與性能分析3.1生成的負(fù)載均衡算法仿真實(shí)驗(yàn)仿真實(shí)驗(yàn)是在仿真工具Oversim上進(jìn)行的,它是一種在OMNeT++/OMNEST仿真環(huán)境下的開源仿真框架,包括多種P2P協(xié)議,仿真是基于其下的Chord協(xié)議進(jìn)行的.仿真中,資源在ID空間上是均勻分布的,其他仿真環(huán)境參數(shù)如表1所示.在資源數(shù)遠(yuǎn)遠(yuǎn)大于節(jié)點(diǎn)數(shù)的應(yīng)用場景中,實(shí)際系統(tǒng)中的網(wǎng)絡(luò)規(guī)模是千數(shù)量級到萬數(shù)量級,故本實(shí)驗(yàn)中網(wǎng)絡(luò)規(guī)模取1萬.另外,在該應(yīng)用場景中,節(jié)點(diǎn)運(yùn)行單ID的負(fù)載均衡算法,其數(shù)據(jù)搬移開銷過大.鑒于此,本文的仿真實(shí)驗(yàn)主要目的是將SDYA負(fù)載均衡算法與傳統(tǒng)虛擬服務(wù)器負(fù)載均衡算法進(jìn)行比較,在負(fù)載均衡的效果和均衡開銷方面來驗(yàn)證SDYA算法.3.2算法的性能分析1sda算法仿真本文從網(wǎng)絡(luò)的負(fù)載不均衡度的概率分布,針對SDYA算法中的靜態(tài)分配ID與傳統(tǒng)算法中的隨機(jī)分配ID方式進(jìn)行了仿真比較,仿真結(jié)果如圖1所示.可以看出,SDYA算法中幾乎所有節(jié)點(diǎn)的LB都在±0.1之間,并且99%的節(jié)點(diǎn)其LB位于±0.02之間;而傳統(tǒng)算法中,50%的節(jié)點(diǎn)其LB位于±0.1之間,而僅有20%的節(jié)點(diǎn)其LB位于±0.02之間.SDYA算法可以獲得的負(fù)載均衡程度是傳統(tǒng)算法的2.5～5倍,負(fù)載均衡效果顯著.2sdra算法與傳統(tǒng)算法性能比較基于虛擬服務(wù)器的負(fù)載均衡算法中,最大的問題是虛擬服務(wù)器參與路由維護(hù)所帶來的開銷,故本文依據(jù)網(wǎng)絡(luò)單位容量上平均運(yùn)行的虛擬服務(wù)器數(shù)量對SDYA算法與傳統(tǒng)算法的路由維護(hù)開銷進(jìn)行了比較.圖2所示為系統(tǒng)中所有節(jié)點(diǎn)單位容量上需要運(yùn)行虛擬ID數(shù)的均值PID.可以看出,SDYA算法的PID是傳統(tǒng)算法的40%左右,因此,SDYA算法用于路由維護(hù)的開銷與傳統(tǒng)算法相比開銷減少了60%.3傳統(tǒng)算法中dv的模擬本文從需要動態(tài)調(diào)整時(shí)轉(zhuǎn)移的負(fù)載量占系統(tǒng)總負(fù)載量的比例對SDYA算法和傳統(tǒng)算法進(jìn)行了比較,如圖3所示.傳統(tǒng)算法在V取lbN、2lbN、4lbN時(shí),DV分別在4%、2%、1%左右;而SDYA算法在V取lbN時(shí),DV為0.1%;V取2lbN、4lbN時(shí),DV接近于0.從而可以看出,SDYA算法用于動態(tài)負(fù)載調(diào)整的開銷與傳統(tǒng)算法相比減少了70%以上