基于OpenStack的Swift負載均衡算法①

徐 敏,李 明,鄭建忠,孫 強,管建超,羅華永,張 輝

1(國網安徽省電力公司信息通信分公司,合肥 230061)2(北京中電普華信息技術有限公司,北京 100192)

隨著互聯網技術的不斷發展,海量的視頻、圖像、電子商務、購物、游戲等平臺數據,現有的存儲模式和存儲格局已經滿足不了現狀需求.對云計算的存儲能力和網絡帶寬也提出了更高的要求.如何快速存儲大量數據、合理分發數據、動態平衡存儲節點負載以及有效管理和利用數據,對云存儲技術提出了巨大的挑戰.因此,當前的云存儲技術越來越受到更多人的關注、更多人追捧,造就云存儲技術成為熱點.

由于在現實的集群存儲生產環境中,經常出現一部分節點負載較輕甚至節點空運行,而另一部分節點的負載卻遠遠超出負荷,從而引發負載分布不均衡問題.由于負載不均衡問題會導致系統I/O讀寫性能下降,增加系統I/O響應時長,降低系統資源利用率,導致系統性能得不到充分發揮[1].存儲讀寫性能、存儲效率、響應時長等問題屢屢暴露出來,而負載均衡技術正是解決這類問題的關鍵所在[2-4].

近幾年一些研究者提出在云環境下的負載均衡算法.文獻[5]提出一種基于人工蜂群的負載均衡算法,選擇最佳虛擬機評估其負載狀態,然后將任務分發給該虛擬機,如果該虛擬機負載狀態依然最佳則接受分配任務,否則選擇下一個級別虛擬機;文獻[6]提出一種基于蜜蜂行為的負載均衡算法(HBB-LB),對任務按照優先級劃分對匹配虛擬機進行分配任務.優點響應快、增加吞吐量,但缺點是任務優先級的界定不準確;文獻[7]提出限制重定向率算法,限制向低負載節點轉發任務;文獻[8]提出周期性采集負載信息算法,將節點分為低、中、重三類負載,缺點是頻繁分類造成延時;文獻[9]提出基于粗糙集的負載均衡算法,將節點按照負載承載情況劃分為正域、負域和邊界三類.

本文在前人研究的基礎上結合swift的復本特性,提出一種改進的加權最小連接調度負載均衡算法解決負載不均衡導致系統I/O讀寫性能下降的問題.利用集群性能優勢[10],即改進負載均衡資源調度算法,通過采集存儲節點的CPU、內存、硬盤、I/O資源利用率等信息,計算存儲節點的負載能力,評估集群中存儲節點負載情況,合理調整任務分發數,平衡節點負載,從而解決了存儲節點負載分發數不均衡的問題,有效地提升了存儲I/O讀寫性能和數據吞吐率.

1 算法改進

1.1 算法改進分析及思想

選擇加權最小連接調度算法理由:首先提供存儲節點實時負載狀態和請求任務之間的依賴關系;其次在云環境中提供實時負載狀態橫向擴展的能力[11].盡管加權最小連接調度算法的負載均衡效果比較理想,但其也存在以下兩點缺陷.

(1)集群中存儲節點的權值存在靈活性差的缺陷,設置不夠靈活、不能準確反映各節點對負載的實時處理能力.每個節點權值是管理員根據以往經驗手動設置的.在負載隨著節點接收到的任務數量的增加而增加的同時,其權值也會出現較大的偏差,因此也應該對權值進行相應調整,但手動調整權值又很繁瑣,存在不能動態調整權值缺陷.不合理的權值分配將會影響負載均衡的效率和整個集群系統的性能[12].

(2)加權最小連接調度算法雖然通過任務連接數表示節點負載情況,但并不能準確反應當前任務負載的具體情況,比如讀與寫的任務不同,其處理能力也不同,就不能準確反應節點的具體負載情況.節點的負載情況還應該由節點的CPU、內存、硬盤、I/O等性能參數反映.由于每個存儲節點的處理能力和網絡帶寬性能差異比較大,因此僅通過節點的任務連接數量判斷節點的負載情況有點片面,要準確判斷節點的負載情況還需要參考節點的CPU利用率、內存性能、硬盤大小和I/O性能等參數[13].

綜合上述分析,在原有加權最小連接調度算法的基礎上,提出一種改進的加權最小連接調度算法,即增加CPU利用率、內存性能、硬盤大小和I/O吞吐率四個參數.CPU利用率、內存性能、硬盤大小和I/O性能也反映了節點的任務處理能力[14],如果將CPU利用率、內存性能、硬盤大小和I/O性能與任務連接數結合應用在改進的算法中,能夠更好地反映節點的具體負載情況.

算法思想如下:負載均衡器每隔一個周期向代理服務器節點發送一個CPU、內存、硬盤、I/O利用率的信息采集請求,代理服務器節點收到該任務請求后,會及時反饋當前存儲節點的CPU、內存、硬盤、I/O的利用率信息.負載均衡器會根據每個節點的CPU、內存、硬盤、I/O的利用率以及節點的任務連接數計算出每個節點的負載情況,評估集群中存儲節點負載能力,合理調整任務分發數,平衡節點負載,從而解決了存儲節點負載分發數不均衡的問題,有效地提升了存儲性能和數據吞吐率.如果節點CPU、內存、硬盤、I/O性能數據采樣周期值設置太短,會增加資源開銷過大[15],根據以往的經驗值建議采樣周期值設置在5-30秒為佳[16].

1.2 算法改進設計

本文對加權最小連接調度算法改進設計分四步:第一,通過命令分別采集存儲節點的CPU、內存、硬盤、I/O四個參數在空載時的最大可用資源能力和在負載時的資源利用率等信息,并建立空載資源性能模型和負載資源模型;第二,為每個模型參數分配相應的權重,權重優先級為:CPU＞內存＞硬盤＞I/O,且權重之和為1;第三,分別對每個模型參數加權求和,分別得出每個存儲節點的性能和負載能力;第四,計算每個存儲節點的負載權值,即負載能力除以性能.具體設計如下所示.

(1)建立模型

表1 空載資源模型

表2 負載資源模型

(2)性能計算

(3)負載能力計算

設計CPU、內存、硬盤、I/O等參數在存儲節點負載時的負載能力的權重為設計存儲節點負載能力的計算公式(2):

(4)負載權值計算

1.3 算法實現

實現改進的加權最小連接調度算法主要是利用計算節點通過調用linux命令令獲取CPU、內存、磁盤的利用率和I/O吞吐率等信息,并將信息更新到存儲節點的模型表1和表2,具體方法如下.

通過cat /proc/stat命令獲取CPU利用率;通過cat/proc/meminfo或free命令獲取內存利用率;通過time dd if=/dev/sda1 of=/temp/test.dbf bs=64k命令獲取I/O吞吐率;通過df -h命令獲取磁盤利用率.

存儲節點再調用getresource()函數訪問模型表1和表2分別采集每個存儲節點的CPU、內存、硬盤、I/O四個參數在空載時的性能資源變量F和負載時的資源變量L.然后根據公式(1)計算每個存儲節點空載性能,同理根據公式(2)計算每個存儲節點的負載能力,存儲節點再由公式(3)計算每個存儲節點權值負載均衡器根據每個存儲節點的權值大小判斷任務分發方向,如果值大則說明該節點正處于負荷較重狀態;如果值小則說明該節點正處于負荷較輕的狀態,此時負載均衡器應該將任務分發給較輕節點.實現改進后的加權最小連接調度算法的實現流程以及關鍵偽代碼如下所示:

步驟1.OpenStack計算節點nove讀取每個存儲節點的資源使用信息,包括CPU、內存、磁盤的利用率和I/O的吞吐率;

步驟2.分別調用每個存儲節點在空載情況的模型表1和負載情況的模型表2,并將步驟1讀取到的信息填寫到空載模型表1和負載模型表2中;

步驟3.存儲節點根據空載模型表和負載模型表數據計算每個存儲節點的負載能力、性能和權值;

步驟4.負載均衡器根據步驟3計算結果評估每個存儲節點的負載情況,并對負載按升序方式排序;

步驟5.負載均衡器偵聽是否有新的任務請求,并對新的任務占用資源進行評估,然后調用改進的算法將任務分發給負載最小的節點處理;

步驟6.待存儲節點處理完新的任務后,再評估該存儲節點是否超載,如果超載轉到步驟4;如果未超載則結束本次流程.

圖1 改進的加權最小連接調度算法流程圖

偽代碼說明:存儲節點定期調用getresource函數采集自身的資源使用率數據,如CPU、內存、硬盤和I/O信息,然后通過send()函數將采集到的數據發送給負載均衡器;負載均衡器再調用receive()函數接收存儲節點的資源信息,并調用update()函數更新數據.存儲節點調用負載性能函數和負載能力函數計算權值.

根據算法實現流程計算該算法空間復雜度和時間復雜度.在該算法中每次迭代空載模型表和負載模型表空間主要用來存放存儲節點的CPU、內存、磁盤和I/O使用率信息,由于存儲節點數量不多且每個存儲節點存儲兩張模型表,每張表存儲的四個參數的使用率數據不大,模型表中的記錄數量也不多,因此,改進后算法的空間復雜度為O(n),n為空載模型表和負載模型表空間,由于兩張模型表只存放四個參數的資源使用信息,且數據量少,相對于存儲設備而言,其占用的存儲空間可以忽略不計,故改進后算法的空間復雜度不大,不會產生較大存儲空間浪費現象.由于實現該算法流程較簡單,且遍歷每個存儲節點獲取CPU、內存、磁盤和I/O四個參數資源使用信息數據小、執行速度快,四個參數數量相對小于存儲節點數量n,故四個參數時間可以忽略不計,因此,該算法的時間復雜度為O(n),n為存儲節點數量,由于存儲節點數量不多,故改進后算法的時間復雜度不大,不會造成過多的時間開銷.

改進后的算法優化了原有算法的缺陷,解決了云環境下swift存儲負載不均衡的問題,有效地提升了存儲I/O讀寫性能和數據吞吐率,提升資源利用率和任務響應時間縮短最小化進程間的通信開銷[17],從而達到提高整體性能效果.

2 實驗

2.1 實驗環境搭建

為了驗證本文改進的負載均衡算法,搭建以下實驗環境進行集群環境的存儲性能測試,以驗證改進后的算法有效性.Swift負載均衡測試環境由4個壓力客戶端、1個負載均衡器、2個Proxy服務器以及4個存儲服務器組成,存儲單元為SATA磁盤以及Intel的萬兆網卡.壓力測試工具為COSBench.

2.1.1 部署圖

負載均衡實驗環境部署圖如圖2所示.

圖2 swift負載均衡實驗環境部署圖

2.1.2 硬件配置

實驗環境硬件配置如表3所示.

表3 服務器配置

2.2 實驗結果

本文算法與加權最小連接調度算法共進行8組實驗測試,分別測試讀小文件、讀大文件、寫小文件、寫大文件不同任務,并統計、記錄在執行相同的任務條件下采用不同的算法讀寫速度,為了提高實驗的準確性,每項實驗測試兩遍.在每組實驗傳輸大小相同文件的條件下,共采集2組測試數據,并對比算法改進前后的存儲節點讀寫速度,分析算法改進后的讀寫性能.算法改進前后的存儲讀寫速度對比見表4.

表4 算法改進前后的存儲節點讀寫速度對比

從表4可以看出,本文算法在存儲節點讀寫數據時其速度明顯高于加權最小連接調度算法,經驗證改進后的算法存儲節點讀寫速度比改進前的讀寫速度有明顯提升,能較好的地解決加權最小連接調度算法讀寫性能低、響應速度慢的問題.

當任務連接數比較小時本算法優勢不明顯,但任務連接數超過500時本算法優勢明顯高于其它算法,本算法能夠保障負載均衡趨于平衡,而其它算法促使負載失衡.根本原因本算法具有權值動態調整功能.

3 結束語

本文通過改進加權最小連接調度算法,周期性地采集存儲節點的CPU、內存、硬盤、I/O利用率信息,并結合節點的權值,計算出每個節點的當前負載情況,準確地選擇負載最輕的節點并分發任務,有效地避免了節點超載后,負載均衡器依然向節點發送服務連接請求,從而引發存儲讀寫速度下降的問題,也提升了存儲讀寫性能、數據吞吐率.

但是,由于節點的權值會隨著節點接收的任務數的增加而出現較大的偏差.當節點的CPU、內存、硬盤、I/O利用率與任務連接數的比例相當時,此時的負載均衡調整會重點根據權值選擇節點分發任務.如果權值有偏差可能會導致負載不均衡、調度算法循環調度等問題產生,造成資源浪費、時間開銷過大.

因此,在改進的加權最小連接數調度算法中如何根據CPU、內存、硬盤、I/O利用率與任務連接數的統計值更合理動態調整權值,以解決權值動態調整受限問題,需在今后的工作和學習中進一步研究與探索.

1 Zhao Y,Huang WL.Adaptive distributed load balancing algorithm based on live migration of virtual machines in cloud.Fifth International Joint Conference on INC,IMS and IDC,2009.Seoul,South Korea.2009.170–175.

2 胡麗聰,徐雅靜,徐惠民.基于動態反饋的一致性哈希負載均衡算法.微電子學與計算機,2012,29(1):177–180.

3 張玉芳,魏欽磊,趙膺.基于負載權值的負載均衡算法.計算機應用研究,2012,29(12):4711–4713.[doi:10.3969/j.issn.1001-3695.2012.12.080]

4 劉健,徐磊,張維明.基于動態反饋的負載均衡算法.計算機工程與科學,2003,25(5):65–68.

5 Pan JS,Wang HB,Zhao HN,et al.Interaction artificial bee colony based load balance method in cloud computing.Sun H,Yang CY,Lin CW,et al.Genetic and Evolutionary Computing.Cham:Springer International Publishing,2015.49–57.

6 楊石,王艷玲,王永利.云計算環境下基于蜜蜂覓食行為的任務負載均衡算法.計算機應用,2015,35(4):938–943.[doi:10.11772/j.issn.1001-9081.2015.04.0938]

7 Nakai AM,Madeira E,Buzato LE.Load balancing for internet distributed services using limited redirection rates.2011 5th Latin-American Symposium on Dependable Computing (LADC).Sao Jose dos Campos,Brazil.2011.156–165.

8 郭平,李琪.基于服務器負載狀況分類的負載均衡調度算法.華中科技大學學報(自然科學版),2012,40(S1):62–65.

9 陳亮,王加陽.基于粗糙集的負載均衡算法研究.計算機工程與科學,2010,32(1):101–104.

10 Rittinghouse JW.Ransome JF.云計算.田思源,趙學鋒譯.北京:機械工業出版社,2010.

11 趙丹丹.Swift的讀取負載均衡研究與實現[碩士學位論文].南京:東南大學,2016.

12 Azar Y,Broder AZ,Karlin AR.On-line load balancing.Theoretical Computer Science,1994,130(1):73–84.[doi:10.1016/0304-3975(94)90153-8]

13 Lee R,Jeng B.Load-balancing tactics in cloud.2011 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery (Cyber C).Beijing,China.2011.447–454.

14 Bunt RB,Eager DL,Oster GM.et al.Achieving load balance and effective caching in clustered web servers.Proceedings of the 4th International Web Caching Workshop.San Diego,CA,USA.1999.

15 楊錦,李肯立,吳帆.異構分布式系統的負載均衡調度算法.計算機工程,2012,38(2):166–168.

16 熊振華.基于OpenStack云存儲技術的研究[碩士學位論文].長春:吉林大學,2014.

17 Chang H,Tang XH.A load-balance based resourcescheduling algorithm under cloud computing environment.Proceedings of the 2010 International Conference on New Horizons in Web-Based Learning.Shanghai,China.2011.85–90.