一種改進的流媒體集群動態(tài)負載均衡調度算法?

王 釗 劉釗遠

（西安郵電大學計算機學院 西安 710061）

1 引言

隨著網(wǎng)絡的普及和高速發(fā)展，網(wǎng)絡服務在視頻監(jiān)控等領域已廣泛應用。如何在有限的資源條件下及時有效地處理海量用戶的并發(fā)訪問請求？采用流媒體服務器集群［1～2］是目前解決該問題的主要方法。流媒體服務器集群的核心是集群負載均衡?，F(xiàn)有的負載均衡算法可以分為靜態(tài)負載均衡算法和動態(tài)負載均衡算法。靜態(tài)負載均衡算法按照固定的方式進行分配，其算法簡單、運行速度快，但是條件過于理想化，不能用于復雜的應用場景。動態(tài)負載均衡算法通過在一定時間內，不斷更新集群各節(jié)點的狀態(tài)信息，通過一定方式計算其負載，根據(jù)負載均衡算法，選擇節(jié)點處理當前請求。

文獻［3～4］提出了動態(tài)反饋負載均衡算法，考慮了服務器的處理能力，同時實時計算服務器的負載，但是考慮了大量的負載因素，不重要的負載因素變化反而影響了最終負載均衡的準確性。文獻［5］提出了每隔固定周期T，采集各服務節(jié)點的負載性能參數(shù)，計算并更新各服務節(jié)點的負載權值，以提高負載均衡的準確性，但是負載權值的計算是按照一定的加權比例進行的，比較經(jīng)驗主義，而且該負載權值作為下一周期T的負載均衡標準，從而影響負載均衡的效果。

為此，本文提出一種改進的動態(tài)負載均衡算法，采用層次分析法確定初始的負載權值向量，然后通過實驗進行微調；根據(jù)每秒鐘節(jié)點任務數(shù)的變化量來動態(tài)調整反饋周期T，及時反饋節(jié)點的實時負載狀況；同時根據(jù)負載指標將集群節(jié)點劃分為三類（低負載、正常負載、高負載），解決突發(fā)大量并發(fā)連接請求導致的集群負載傾斜問題，提高集群負載均衡的效率。

2 現(xiàn)有負載均衡調度算法

2.1 輪詢調度算法

輪詢調度算法是一種靜態(tài)負載均衡算法。適用于集群中所有服務節(jié)點具有相同配置并且服務請求相對均衡的場景。該算法將集群中的n個服務節(jié)點依次編號為1，…，n。

當編號i的任務請求到達時，根據(jù)式（1）將該任務分配給編號為num的服務節(jié)點。

2.2 最小連接數(shù)算法

最小連接數(shù)算法是動態(tài)負載均衡算法。該算法以集群節(jié)點的任務連接數(shù)作為節(jié)點的性能指標來進行負載均衡。當有新的任務請求到達時，將該任務分配給集群中當前任務連接數(shù)最小的服務節(jié)點。該算法雖然考慮了任務連接數(shù)對節(jié)點負載的影響，但是沒有考慮集群中各服務節(jié)點的性能差異以及別的因素對節(jié)點負載的影響。

2.3 加權最小連接數(shù)算法

該算法是最小連接數(shù)算法的改進，屬于動態(tài)負載均衡算法，根據(jù)集群節(jié)點的處理性能設置對應的權值，集群節(jié)點分配的任務數(shù)與其權值成正比。該算法雖然改善了最小連接數(shù)算法對集群節(jié)點性能差異的適應性缺陷，但是仍然沒有考慮別的因素（如CPU利用率、帶寬利用率等）對集群節(jié)點性能的影響。

2.4 傳統(tǒng)的動態(tài)反饋算法

傳統(tǒng)的動態(tài)反饋算法［6～10］，通常會設定一個反饋周期T，每隔周期T各服務節(jié)點將自己的負載狀況上傳至中心服務器，中心服務器以此來計算并更新各服務節(jié)點的負載權值，然后將負載權值作為下一個周期T內任務分配的標準。當某一節(jié)點的負載突發(fā)較大變化時，并不能及時地通知中心服務器，只能等待反饋周期T到達時才上傳自己的負載變化狀況，更新負載權值，因此在當前周期T內可能導致集群負載傾斜。

3 改進的動態(tài)負載均衡算法

系統(tǒng)業(yè)務框架如圖1所示：

圖1 系統(tǒng)業(yè)務框架

在實際應用中，視頻采集設備不主動推送視頻數(shù)據(jù)，當用戶發(fā)起任務請求時，調度服務器為其分配流媒體服務器Easy Darwin Streaming Server（EDSS），并將結果發(fā)送給視頻采集設備，隨后視頻采集設備根據(jù)接收到EDSS的IP及端口推送視頻數(shù)據(jù)，最后用戶根據(jù)調度服務器返回的結果拉取視頻數(shù)據(jù)，并在本地播放，完成整個視頻監(jiān)控業(yè)務。

3.1 改進算法的設計思路

改進算法采用動態(tài)修改反饋周期T，同時將集群節(jié)點根據(jù)其負載狀況分為低負載、正常負載和高負載三類的方法，來提高集群的負載均衡效果。改進的負載均衡算法系統(tǒng)框架圖如圖2所示。

圖2 改進的動態(tài)反饋負載均衡算法系統(tǒng)框架圖

圖2從用戶、調度服務器及流媒體服務器集群三個方面描述了改進的動態(tài)反饋負載算法的兩個主要流程：

1）A1～A8：用戶任務請求的處理過程；

2）B1～B5：負載均衡器動態(tài)更新反饋周期T和集群節(jié)點分類的過程；

用戶任務請求處理過程：用戶發(fā)起任務請求，存入調度服務器的任務請求隊列，由調度服務器為其分配EDSS，完成之后將任務轉發(fā)到指定的EDSS執(zhí)行任務。

負載均衡器：當反饋周期T的定時器到期，負載均衡器向集群節(jié)點請求負載指標，隨后根據(jù)返回的負載指標更新其反饋周期T及所屬分類，最后重置定時器T。

改進的動態(tài)負載均衡調度算法為了提升以下兩個效率問題：1）集群節(jié)點返回其真實負載狀況的及時性；2）在反饋周期內，突發(fā)大量并發(fā)任務請求時集群的處理效率。

針對第一個問題，根據(jù)每秒鐘集群節(jié)點的任務總數(shù)的變化量來動態(tài)地修改反饋周期T，以確保集群節(jié)點及時反饋其實際負載。當連接數(shù)增大時，適當較小周期T，盡快反饋集群負載狀況；當連接數(shù)減小時，適當增大周期T，降低集群節(jié)點計算負載權值的資源消耗。針對第二個問題，根據(jù)集群節(jié)點的負載指標（CPU使用率、帶寬使用率、內存使用率、連接數(shù)）將集群節(jié)點分為三類，類之間根據(jù)各類的負載權值總和的比例進行任務分配，類中使用最小連接數(shù)算法進行任務分配，以此解決周期T內突發(fā)大量并發(fā)任務時導致集群中最優(yōu)節(jié)點分配大量任務，發(fā)生負載傾斜現(xiàn)象。

3.2 負載權值的計算

3.2.1 負載指標參數(shù)

1）CPU利用率θcpu

每隔1s通過cat/proc/stat獲取CPU從系統(tǒng)啟動到當前時刻處于idle狀態(tài)的總節(jié)拍數(shù)（jiffies），再通過式（2）計算CPU在1s之內的使用率：

其中，θcpu是1s內的CPU利用率；Cidle1、Cidle2分別是時間間隔1s開始與結束時刻CPU處于idle狀態(tài)的總節(jié)拍數(shù)；Δt取值為100，因為1s的節(jié)拍數(shù)是100。

2）內存利用率θmem

通過cat/proc/meminfo讀取當前時刻的內存使用狀況，得到內存總量以及內存剩余量，再通過式（3）計算當前時刻內存的利用率：

其中θmem為當前時刻的內存利用率；Mtotal為節(jié)點的內存總量；Mfree為該節(jié)點的內存剩余量。

3）網(wǎng)絡利用率θnet

每隔1s通過cat/proc/net/dev讀取節(jié)點從系統(tǒng)啟動到當前時刻接收到的數(shù)據(jù)量Rx以及發(fā)送的數(shù)據(jù)量Tx，再通過式（4）計算1s之內帶寬的使用率：

其中，θnet為1s之內的網(wǎng)絡利用率；Rx1、Tx1分別為時間間隔開始時節(jié)點接收和發(fā)送的數(shù)據(jù)量；Rx2、Tx2分別為時間間隔結束時節(jié)點接收和發(fā)送的數(shù)據(jù)量；Net為節(jié)點的總帶寬。

4）任務連接數(shù)θlinks

從調度服務器與流媒體服務器EDSS（EasyDar?win Streaming Server）的交互模塊中直接讀取節(jié)點當前時刻的任務連接數(shù)。當任務開始時θlinks+1，當任務結束時θlinks-1。

3.2.2 負載權值向量

傳統(tǒng)動態(tài)負載均衡算法負載權值的計算是按照一定的加權比例進行的，比較經(jīng)驗主義，可能影響負載權值計算的準確性。鑒此，采用層次分析法（AHP）［11～12］初步確定每個負載指標的系數(shù)，得到初始的負載權值向量，然后通過實驗調整以獲取最優(yōu)的負載權值向量。層次分析法的判斷矩陣如表1所示。

表1 判斷矩陣

根據(jù)判斷矩陣解出對應的特征向量ω：

其中，ωc，ωm，ωn，ωl分別為計算集群節(jié)點負載時CPU利用率θcpu、內存利用率θmem、帶寬利用率θnet、連接數(shù)θlinks等負載指標的系數(shù)。

表 1 的 特 征 向 量 為 ω=(0.44，0.22，0.22，0.12)t。即就是負載權值向量為 α=(0.44，0.22，0.22，0.12)t。

通過實驗，調整后的權值向量為α=(0.4，0.25，0.25，0.1)t

3.2.3 計算節(jié)點負載權值

通過上述方案可知：

負載指標向量為：

其中，α=ω=(ωc，ωm，ωn，ωl)t。使用式（8）計算集群節(jié)點i的負載權值L：

3.3 服務器節(jié)點分類

在集群運行的過程中，根據(jù)負載指標的狀況選取一些處于不同負載狀態(tài)的個例，構成進行分類的訓練集，然后基于分類算法，得到分類規(guī)則。在后期運行過程中，根據(jù)該規(guī)則對集群節(jié)點進行負載分類。部分訓練樣本如表2所示：

表2 訓練樣本集

用于分類的算法有很多，如FCM（模糊C均值聚類）、SVM［13～14］（支持向量機）、KNN（k-Nearest?Neighbor）等。KNN算法簡潔明了，適合于多分類問題，并且實驗樣本的屬性較少（只有4個），故選擇KNN分類算法。

KNN算法的基本思想：在已知樣本集中尋找與待分類樣本最相似的k個樣本，找出其中數(shù)量最多的一類，則該樣本也屬于這個類。KNN算法中，選擇的樣本都是已經(jīng)正確分類的對象。采用歐氏距離來確定樣本之間的相似度，歐氏距離的計算如式（9）所示：

其中，i為樣本的屬性個數(shù)；xi為待分類樣本的屬性；yi為對應訓練樣本的屬性。

每當調度服務器采集到集群節(jié)點的負載指標后，使用KNN算法依次計算節(jié)點到已知樣本間的歐氏距離，得到距離最近的K個樣本的類別，然后選擇數(shù)量最多的一類作為當前節(jié)點的類別。

3.4 反饋周期T的動態(tài)更新

反饋周期T的初始值為10s。

計算每秒鐘集群節(jié)點任務數(shù)的變化量Δlinks，按照表3動態(tài)地改變節(jié)點的反饋周期T，確保節(jié)點及時反饋其負載狀況。

表3 ΔT與Δlinks的對應關系

其中，Δlinks為每秒鐘集群節(jié)點任務數(shù)的變化量；ΔT為反饋周期T的變化量。任務數(shù)增加則T減小，反之增大。

當 Δlinks小于20時，周期T保持不變；當Δlinks小于40時，周期T的變化量為1s；當Δlinks小于60時，周期T的變化量為2s；以此類推。為防止頻繁計算負載權值，周期T的最小值設置為1s；為防止周期T過大，不能及時反饋節(jié)點負載狀況，周期T的最大值設置為20s。

4 改進的調度算法的實現(xiàn)

改進算法采用了：

1）動態(tài)改變負載反饋周期T；

圖3 改進的動態(tài)負載均衡調度算法總流程圖

2）按集群節(jié)點的負載狀況進行分類；

以此來提高集群負載均衡效率。改進的動態(tài)負載均衡算法的總流程如圖3所示。

集群節(jié)點分類的處理流程如圖4所示。

圖4 集群節(jié)點分類流程圖

對于集群節(jié)點分類的過程，主要是計算待分類節(jié)點與集群其余節(jié)點的歐氏距離，根據(jù)前K個距離最小的節(jié)點所屬類的情況確定待分節(jié)點屬于哪一類。若前K個節(jié)點中正常負載類的節(jié)點占多數(shù)，則待分節(jié)點就屬于正常負載類。

5 實驗及結果分析

5.1 實驗環(huán)境

為了驗證改進的動態(tài)負載均衡調度算法，搭建流媒體服務器集群來測試該算法性能。實驗環(huán)境設置如表4、表5所示。

表4 硬件配置表

表5 軟件配置表

5.2 實驗結果及分析

通過向調度服務器發(fā)送100、200、300、400個并發(fā)請求，比較最小連接數(shù)算法和改進算法的平均響應時間。測試結果如表6所示。

根據(jù)表6的數(shù)據(jù)，在并發(fā)任務數(shù)較少的情況下，兩種算法的平均響應時間相差不多；當并發(fā)數(shù)逐漸增大后，改進算法的效率明顯優(yōu)于最小連接數(shù)算法。

表6 平均響應時間結果

通過向調度服務器發(fā)送300個并發(fā)請求，每個請求運行時間隨機，并在45s時再發(fā)送100個并發(fā)請求，通過每隔30s定期采集集群各流媒體服務器節(jié)點的負載情況，來比較最小連接數(shù)算法和改進算法的優(yōu)劣性。

當采用最小連接數(shù)算法時，集群中每臺流媒體服務器的負載變化情況如圖5所示。

圖5 最小連接數(shù)算法負載變化圖

從圖5可以看出，在初始時刻（即0s），由于集群節(jié)點的處理性能不同，負載權值有差異；30s時，集群的負載并不均衡；60s時，突發(fā)大量并發(fā)連接，集群的負載也不均衡。

同樣條件下，采用改進算法，集群中的流媒體服務器負載變化情況如圖6所示。

圖6 改進算法負載變化圖

從圖6可以看出，初始時刻，由于集群節(jié)點的處理性能不同，集群的負載并不均衡；30s時，集群的負載比較均衡；60s時，突發(fā)大量并發(fā)連接，集群的負載仍然均衡。

對比圖5、圖6可以看出，由于最小連接數(shù)算法沒有考慮集群節(jié)點的處理性能，并不能很好的保證集群負載均衡，當突發(fā)大量任務請求時，集群發(fā)生負載傾斜；改進的負載均衡算法在通常情況下保證了集群負載均衡，同時也能很好地處理當大量突發(fā)任務請求到來時的情況，始終保證集群負載均衡。

6 結語

本文主要分析了提升負載均衡效率的兩個主要問題，并針對該問題提出了一種改進的動態(tài)負載均衡算法：通過動態(tài)修改反饋周期T以及對集群節(jié)點進行分類，來達到更好的負載均衡效果。通過實驗對比，可知改進的動態(tài)負載均衡算法具有更短的平均響應時間，也能保證集群長時間的負載均衡效果。

［1］柳艷茹.淺談流媒體技術的應用與發(fā)展［J］.赤峰學院學報（自然科學版），2012（11）：16-17.

LIU Yanru.The Application and Development of Stream?ing Media Technology［J］.Journal of Chifeng University（Natural Science Edition），2012（11）：16-17.

［2］龍著乾.流媒體服務器集群的負載均衡研究［J］.軟件，2013（4）：62-64.

LONG Zhuqian.Streaming Media Server Cluster Load Bal?ancing［J］.Software，2013（4）：62-64.

［3］寧國勤，朱光喜，彭烈新.異構分層無線網(wǎng)絡中的混合動態(tài)流量均衡算法研究［J］.通信學報，2007，28（1）：75-81.

NING Guoqin，ZHU Guangxi，PENG Liexin.Research on hybrid dynamic load balancing algorithm in heterogeneous hierarchical wireless networks［J］.Tongxin Xuebao/Jour?nal on Communications，2007，28（1）：75-81.

［4］王春娟，董麗麗，賈麗.Web集群系統(tǒng)的負載均衡算法［J］.計算機工程，2010（2）：102-104.

WANG Chunjuan，DONG Lili，JIA Li.Load Balance Algo?rithm for Web Cluster System［J］.Computer Engineering，2010（2）：102-104.

［5］高振斌，潘亞辰，華中，等.改進的基于加權最小連接數(shù)的負載均衡算法［J］.科學技術與工程，2016（6）：81-85.

GAO Zhenbin，PAN Yachen，HUA Zhong，et al.An Im?proved Load Balancing Algorithm Based on WLC［J］.Sci?ence Technology and Engineering，2016（6）：81-85.

［6］任俠.基于動態(tài)自適應負載均衡的服務器集群優(yōu)化策略［J］.工業(yè)控制計算機，2015（12）：38-39，41.

REN Xia.Load Balance Based Server Selection in Web Server Cluster System Scheme［J］.Industrial Control Com?puter，2015（12）：38-39，41.

［7］榮航.改進的動態(tài)負載均衡算法在集群中的應用［J］.無線通信技術，2015（3）：34-370.

RONG Hang.Improved Dynamic Load-balancing Algo?rithm in the Cluster［J］.Wireless Communication Technol?ogy，2015（3）：34-370.

［8］魏欽磊.基于集群的動態(tài)反饋負載均衡算法的研究［D］.重慶：重慶大學，2013.

WEI Qinlei.Study on Dynamic Feedback Load Balancing Algorithm Based on Cluster［D］.Chongqing：Chongqing University，2013.

［9］Zhang Qian，Ge Yufei，Liang Hong，Shi Jin.A Load Bal?ancing Task Scheduling Algorithm based on Feedback Mechanism for Cloud Computing［J］.International Jour?nal of Grid and Distributed Computing，2016，9（4）：41-52.

［10］陳偉，張玉芳，熊忠陽.動態(tài)反饋的異構集群負載均衡算法的實現(xiàn)［J］.重慶大學學報，2010，33（2）：73-78.

CHEN Wei，ZHANG Yufang，XIONG Zhongyang.Re?search and realization of the load balancing algorithm for heterogeneous cluster with dynamic feedback ［J］.Chongqing Daxue Xuebao/Journal of Chongqing Univer?sity，2010，33（2）：73-78.

［11］廖紅強，邱勇，楊俠，等.對應用層次分析法確定權重系數(shù)的探討［J］.機械工程師，2012（6）：22-25.

LIAO Hongqiang，QIU Yong，YANG Xia，et al.A Study of Weight Coefficient Computing Method Based on AHP［J］.Mechanical Engineer，2012（6）：22-25.

［12］朱曉妹，葉仁蓀，張重天，等.運用層次分析法確定崗位要素權重的技巧分析［J］.鐵道工程學報，2010（5）：87-90.

ZHU Xiaomei，YE Rensun，ZHANG Chongtian，et al.Analysis of Techniques for Determining Factor Weight in Job Evaluation with Analytic Hierarchy Process［J］.Jour?nal of Railway Engineering Society，2010（5）：87-90.

［13］袁玉萍.基于線性規(guī)劃的K-SVCR支持向量機［J］.山西大學學報（自然科學版），2009（2）：193-196.

YUAN Yuping.K-SVCR support vector machine based on linear programming［J］.Journal of Shanxi University（Nat.Sci.Ed.），2009（2）：193-196.

［14］翟嘉，胡毅慶，成小偉.基于三分類支持向量機的多分類算法的研究［J］.中北大學學報（自然科學版），2015（5）：520-525，532.

ZHAI Jia，HU Yiqing，CHENG Xiaowei.Study on Classi?fication Algorithm Based on Three Classification Support Vector Machine［J］.Journal of North University of China（Natural Science Edition），2015（5）：520-525，532.