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

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

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