基于弗洛伊得算法的云端文件存儲負載平衡算法研究

陳 園，劉軍華，雷超陽

（湖南郵電職業技術學院 互聯網工程系，湖南 長沙 410015）

基于弗洛伊得算法的云端文件存儲負載平衡算法研究

陳 園，劉軍華，雷超陽

（湖南郵電職業技術學院 互聯網工程系，湖南 長沙 410015）

文章提出了基于弗洛伊得算法的云端文件儲存負載平衡算法，依據客戶端對文件的存取頻率與文件大小，綜合最短網絡距離的計算來優選文件存放位置,且依據所有客戶端與所有服務節點間的跳躍計數與網絡頻寬視作其網絡距離。仿真實驗表明:本文研究方法其文件平均存取成本較隨機與輪轉兩種方法明顯要低，對所有使用者公平存放文件位置，讓使用者能以最少的跳轉次數或最佳的頻寬路徑進行存取，提升了客戶端文件存取效率。且當多數叢集空間滿載時本研究方法仍可計算出較佳的存放位置。

弗洛伊得算法；云端文件；負載平衡；算法

0 引言

隨著云計算相關技術的普及以及用云技術應用的越來越廣泛，如將不同云文件合理存放于不同云服務器，以滿足大量用戶快速存取、高吞吐量及大儲存空間需求。因而，怎樣合理安排文件的云存放位置，使客戶端獲取時響應時間較短非常重要。通常的思路是每隔一段時間周期性的收集云端系統內文件的存取需求作為負載平衡的依據，依此分析當前時間段文件的合適存放位置，即通過周期性的收集與分析云系統信息使近階段文件的存放位置接近最佳化[1-5]。而判斷文件存放的位置考慮因素既可以是存放在較空閑服務器來降低客戶端的等待時間，也可以是存放在距離客戶端較近的位置來降低傳輸成本[6-8]。

本文提出的弗洛伊得算法的云端文件存儲負載平衡算法，以弗洛伊得算法計算出客戶端至所有服務節點的最短網絡路徑，同時考慮不同客戶端對同文件存取需求，不只將文件存放在離單一客戶端最近位置，即不同客戶端存取文件次數及大小也是考慮要素。對于較大文件即使被存取次數較少，也要考慮將其存放在較近位置，以避免存取該文件的客戶端因傳輸所需文件而造成較大延遲。而對于存取次數較多但較小文件，即使存放在離其較遠位置也不至于造成太大延遲。且當計算出適合存放的服務節點滿載時，通過設計好的滿載文件遷移規則，使服務節點中的文件遷移調整后對客戶端造成的影響最低。

1 弗洛伊得算法思路

弗洛伊得算法（Floyd）是一種在有向加權圓中尋找任意兩點間最短路徑的算法[9-12]。其思路是如果一個問題存在最佳解則其子問題必有最佳解，將有向加權圓中的任意兩點間所有可經過點間最短距離作為子問題，先分別解出各子問題最佳解，最后將子問題解進行最佳組合從而得到問題的最佳解。其算法描述為：設Di,j,k為某圖從點i到點j經由（1~k）集合點為中間節點的路徑長度為子問題，則子問題可分兩種情況。

（1）經過中間k節點的路徑距離Di,j,k=Di,k,k-1+

（2）不經過中間k節點的路徑距離Di,j,k=Di,j,k-1

這樣子問題最短路徑變為：Di,j,k= min（Di,k,k-1+Dk,j,k-1, Di,j,k-1），即取經過中間k節點路徑距離與不經過中間k節點路徑距離（即直接相連節點）兩者的較小值。若經過中間節點距離較短，則以此距離取代原本兩點直連的距離，依此不斷的比較與取代將加權圓中任意兩節點間的最短路徑距離計算出來。

2 網絡距離計算

網絡距離通常是計算云端文件儲存位置的主要評估要素，其計算方式是以客戶端入口點與文件服務器叢集之間的跳躍計數及頻寬來計算，如圖1所示。

圖1 服務器叢集與入口點連線頻寬示意圖Fig.1 Bandwidth map of the server cluster and the entry point

圖1中沒帶箭頭線段上的數字表示叢集間的頻寬，帶箭頭線段上的數字表示入口點到直連叢集間的頻寬，入口點到叢集為有向，叢集間為無向且互相連通，但不一定直連。取頻寬的倒數來表示叢集間的相連傳輸延遲（即時間距離），頻寬數值與時間距離成反比，以下公式1為點x到點y的時間距離計算方法。

由圖1計算出的時間距離結果如表1所示。

表1 服務器叢集直接相連網絡距離表Tab.1 Network distance table of server cluster directly connected

可知有些叢集間無直接連接，需經其他叢集轉連，此轉連所經過的叢集數即為跳躍計數。此跳躍路徑不一定為唯一路徑，有時直連的距離較近，有時經由別的叢集路徑較近，且選擇頻寬總和最小跳躍路徑，這時需根據弗洛伊得算法尋找任意兩點最短路徑的特性，以叢集為點計算出任意兩點的最短路徑，計算結果為兩點間跳躍計數的時間距離綜合。最短距離計算方法如公式（2）。

公式2中j為兩點間可經過的點集合。將頻寬倒數的時間距離計算方法套用到弗洛伊得算法中，最短距離為直接相連時間距離與有經由中間點時間距離的較小值。表1加上入口時間距離后通過公式2計算的結果如表2所示。

表2 弗洛伊得算法計算網絡距離表Tab.2 Floyd algorithm to compute the network distance table

由表 2可知，入口點 P1與叢集 SA、SB的連接速度較快，而入口點 P2與叢集 SC、SD的連接速度較快。但當需確定文件存放至哪個叢集時不能僅以連接速度來評估，因如果有兩個入口點都要存取同一文件，如將文件存放在離入口點P1較近叢集SB，則會對入口點P2造成較遠網絡距離存取。所以需考慮多方面因素來計算每個入口點的存取成本，以便將文件存放在更合適的叢集。

3 文件存取成本計算

文件存取成本的計算需針對單獨文件分別計算，考慮的要素有距離、各入口點文件存取次數及文件大小。通過計算各入口點對某文件的需求量，從而分別計算出每個叢集存放此文件對所有入口點造成的影響。

以下以文件f的存取成本來說明其計算步驟。

（1）先分別計算每入口點對文件f的存取需求量 ATp,f×FSf；

（2）再乘以該入口點至叢集距離 ATp,f×FSf×Dp,S；

此計算結果為單一入口點由叢集 S存取文件 f所需成本，將所有入口點的存取成本求和得TACs,f，求和計算公式3如下。

TACS,f表示所有入口點 p從叢集 S存取文件 f的成本總和。公式（3）中各代號含義如下：

P：入口點（Portal），p=1…n

S：服務器叢集（Server Cluster），S=1…m

ATp,f：文件 f從入口點 p的存取次數（Access Times）

FSf：文件f的大?。‵ile Size）

Dp,s：入口點p到叢集s的距離

TACs,f：所有入口點由存取叢集s中文件f的總存取成本

將此公式代入不同叢集 s的距離，就能計算出文件f存放到不同叢集對應的TACs,f值，TACs,f值越小表示文件f越適合存放于叢集s。計算TACs,f值目的在于得到存取需求量與各入口點跟叢集的距離關系，計算存取文件所需成本，依照各入口點存取成本來比較，使每個入口點公平，避免只針對單一存取成本較低的入口點文件來決定最佳存放位置。即使每個文件都計算出最小 TACs,f值決定文件的存放叢集，仍可能出現多個文件存放于同一叢集情況，而叢集空間有限，這就涉及到將部分文件遷移到其他服務器的處理。

4 文件存放策略

本文所研究的文件存放策略是讓每個叢集分別對所有文件中進行挑選。其挑選方式為：選出所有存放于某叢集時存取成本最低的文件。如果叢集挑選的文件大小總和超出了其儲存空間，則從所有存放于該叢集的文件中選出一個移至別的服務器，直到空間足夠。本算法的中止條件為所有文件都確定存放的叢集不再變動。由存取成本計算后可得到每個文件在不同叢集的存取成本，假設為TAC，并將TAC數值以矩陣編排，如表3案例所示，其中橫排表示叢集編號，縱排表示文件編號，中間數值表示如文件存放在此叢集時的TAC值。

表3 文件存放成本矩陣案例Tab.3 Study of file storage cost matrix

接著先將TAC矩陣轉換成相對成本矩陣，因每個文件的TAC值都是針對個別情況計算出來的，文件間的TAC值無法相互比較，所以叢集無法以TAC值確定哪個文件更適合保留。這時只能根據文件被移至別的叢集時分別增加了多少TAC值，即相對成本，相對成本計算程序如下：

Compute-relative-cost（）

for i=1 to m

for j=1 to n

Ri,j=TACi,j—min{TACk,j|k=1-m, TACk,j> 0}

相對成本算法程序

以上相對成本算法程序中 i表示服務器叢集編號 1~m，j表示文件編號 1~n，Ri,j表示文件存放于叢集i的相對成本。每個文件都將其對應TAC數值減去最小TAC值，以表3案例中的文件f1為例，其最小TAC值為2，將其對應TAC值減去2，其他文件依此類推，結果如表4所示。

表4 相對成本計算結果案例Tab.4 Relative cost calculation case

由表4可看出最佳叢集為TAC增長為 0的叢集，當需選擇移至別的叢集文件時就可選擇TAC增長較少的文件。依照相對成本矩陣，叢集進行本身文件篩選，其文件篩選算法程序如下：

Main

-function（）

for j =1 to n

FStatusj=false

While（?false∈{FStatusj| j=1~n}）

Compute-relative-cost（）

for i=1 to m

if（Spi>0）

For j=1 to n

if（Ri,j=0 and FStatusj=false）

add j in FileListi

Spi=Spi-Fsj

FStatusj=true

end for

end for

for i=1 to m

if（Spi<0）

File-Transfer（i）

end

文件篩選算法程序

以上文件篩選算法程序中，FStatusj表示文件 j是否已決定存放位置的狀態，FileListi表示服務器叢集i的文件存放列表，Spi表示服務器叢集i的剩余空間，Fsj表示文件j的大小。依據相對成本矩陣，叢集分別挑選出成本為0且還沒決定存放位置的文件，并將叢集空間扣除文件大小，最后每個叢集檢查其剩余空間是否為負值，如果是則表示此叢集空間不足，需要將部分文件移至別的叢集存放。將文件移出的相對成本比較算法程序如下：

File-Site（i）

for each filejin FileListi

MoveCostj=min｛Ri,j｜i=1~n，Ri,j>0

While（Spi<0）

j=min｛MoveCostj｝

Delete j from FileListi

Spi=Spi+ Fsj

FStatusj=false

Ri,j= —1

delete j from｛MoveCostj｝

end

服務器叢集滿載文件移動算法程序

上述服務器叢集滿載文件移動算法程序中，File-Transfer（i）表示服務器叢集i的文件移動設置，MoveCostj表示文件編號j的移出成本。

相對成本矩陣表示文件被移至其他叢集時其增加的TAC數值有多少。通過上述算法，首先將欲存放此叢集的文件分別找出其在其他叢集時最小的相對成本，也就是第二個適合存放此文件的叢集。將每個文件相對成本比較并選出最小的，表示此文件被移出時增加的TAC最少，影響也最小。所以可決定將其移至別的服務器，如此重復挑選直到叢集空間足夠。如由表4來計算結果如表5所示，可看出在叢集S2所有文件中，f3從叢集S2移至叢集所造成S3所造成的 TAC增長最少。所以在 S2滿載時在移動文件檔案會優先選擇f3移出。

表5 文件移動增長成本Tab.5 Mobile cost of file growth

文件移出結束后回到主程序將會把相對矩陣重新計算一次，此時被移出的文件其存在第二個合適叢集的相對成本會變為 0，在下次重復挑選便會被第二合適的叢集選擇。如此不斷重復的選擇、比較，直到所有文件都決定存放位置為止，完成文件最佳存放位置的近似解。

5 實驗仿真

5.1 叢集數與分支度及文件數對存取成本影響仿真

在叢集數量與分支度對存取成本影響實驗仿真中，分4種不同的叢集數及分支度進行交叉測試，叢集數分別為30/40/50/60，每個服務器叢集總空間為1000位元單位，叢集的連外分支數為1/2/3/4四種，入口點數固定為10，文件數固定為2000，每個文件的大小為3~5位元單位隨機，使用者數為3000。圖2為叢集數與分支度對存取成本影響的實驗仿真結果。

叢集數與文件數對存取成本影響實驗仿真中，以2種不同的叢集數與1000到4600文件數進行交叉測試，叢集數為30/60，每個服務器叢集總空間為1000，叢集的連外支數固定為 3，入口點數固定為10，文件數從1000到4600每次增加50個，每個文件的大小為3~6隨機，使用者數為3000，圖3為叢集數與文件數對存取成本影響的實驗仿真結果。

圖2 叢集數與分支度對存取成本影響Fig.2 The influence of cluster Number and branch degree on access cost

圖3 叢集數量與文件數對存取成本影響Fig.3 The impact of the number of clusters and the number of files on the access cost

從圖2可看出，四種分支度在不同服務器叢集數各進行10次的平均結果，在固定的文件與入口點數下，叢集數越多反而會增加存取成本。因為在沒有相對提升分支度即提高每個叢集連外數情況下，增加叢集數同樣會增加叢集間的跳躍計數從而增加了路徑長度。提升分支度數后當叢集數增加時，因跳躍路徑減少使存取成本增高率也相對下降，圖 2中分支度到達 3時平均存取成本才約文件大小的3~4間，分支度到4時平均存取成本才在2~3間。

從圖3中可看出，當文件數增加時，叢集數越多對存取成本的影響越低。當叢集數為30，當文件數增加時因叢集空間有限且叢集數較少，則必須將部分文件存放于距離較遠的叢集，無法完全針對入口點需求量來存放文件，因此平均存取成本隨文件數增加逐漸上升。而當叢集數為60時，平均存取成本在文件數增加時卻逐漸下降，因為服務器較多則表示網絡距離分布較遠，入口點間的距離也會增加。而在文件少量時多數使用者會選擇相同文件，所以文件便會被存放離多個入口點都不至于過遠的中間叢集位置，則在網絡結構分布較廣狀態下對每個入口點的距離都會多少增加，但當文件數增多會分散使用者選擇的文件。部分用者選擇的文件不一定為熱門文件，不必存放于中間位置，可存放于針對存放該文件較多的入口點附近。而叢集數較多狀態下，文件因空間不足被迫移至較遠叢集的情況減少，相對的存取成本也會降低。因此文件數多時所有使用者的平均存取成本相對于文件數少時會較低。

5.2 隨機和輪轉存放方式對存取成本影響仿真

（1）叢集數對存取成本影響實驗仿真

叢集數對存取成本影響實驗仿真參數設定分為叢集數為30/60兩種情況，叢集數為30/60的入口點數分別設定為5/15，服務器叢集總空間都設為1000位元單位，節點分支度都設為 3，頻寬數值都設為2~8，文件數都設為1000~4600，文件大小都設為3~6位元單位，使用者數都設為3000。因叢集數多時叢集間的跳躍計數會增加，如入口點數與叢集少時設定相同，則入口點間的距離也會相對增加。所以在叢集數較多的實驗仿真中設定有較多的入口以保證距離的公平性，仿真結果如圖4所示。

圖4 叢集數對存取成本影響Fig.4 The impact of cluster numbers on access costs

由圖4可知，隨機與輪轉兩種文件存放方法平均成本差距不大，且兩種方法的存取成本與文件數沒太多影響，而本文研究方法其平均存取成本相較于以上兩種方法明顯要低。且在文件總數相同條件下，叢集數為60時本文研究方法的平均存取成本與其他兩種方法的差距大于叢集數為30時對應情況。即在儲存空間充裕狀態下本文研究方法能更有效安排文件的存放，而其他兩種方法當叢集數增加后，因結構范圍擴大提高了距離，從而使得平均存取成本大幅增高，由此可見本文研究方法在文件數與叢集數均衡情況下，更能將每個文件存放在有利于所有使用者的叢集位置。

（2）文件大小范圍對存取成本影響實驗仿真

仿真時文件大小隨機范圍分別設為4~6與1~9，叢集數都設為30，節點分支度都設為3，服務器叢集空間都設為1000位元單位，入口點數都設為5，頻寬數值設為2~8，文件數設為1000~4600，使用者數設為3000，仿真結果如下圖5所示。

由圖5可知，本文研究方法與隨機、輪轉兩方法當文件范圍增加時，平均存取成本總體都有相對增加現象，且不管哪種文件大小范圍，其平均存取成本數均大于文件大小范圍。而本文研究方法當范圍增加時，且文件數為1000~2350時因文件數較少易產生部分極端大小的文件，造成存取成本變異數較大；而當文件數超過2800后，存取成本變動范圍明顯縮小。表示即使文件大小的差異較大，本文研究方法仍然視使用者的使用情況處理極端大小的文件，不會造成因極度偏袒部分使用者而使整體平均存取成本降低。

圖5 文件范圍對存取成本影響Fig.5 Scope of the file affects access costs

6 總結

本文所設計的云文件存放策略算法，針對客戶端對文件的存取頻率與文件大小，綜合最短網絡距離的計算來優選文件存放位置。通過弗洛伊得算法計算出任兩點最短距離的特性，計算入口點至任意叢集的最短網絡距離，讓使用者能以最少的跳轉次數或最佳的頻寬路徑進行存取，提升了效率。在分支度數實驗中，當分支度增加使得路徑選擇變多時能計算出更佳路徑，效率也相對提升。當多個使用者存取相同文件時，算法依據不同使用者存取入口點位置、存取文件大小、存取頻率來計算出對所有使用者公平的存放位置，避免了文件只針對單一使用者情況來計算存放位置，造成其他多數使用者存取成本的增加。在叢集數與文件數實驗中，本文研究的存放策略考慮到了所有使用者。當叢集存放空間滿載時，本文研究的算法選出對使用者影響最低文件并移到別的叢集存放。當叢集數較少，且多數叢集空間都滿載情況下，本研究方法仍然能夠與其他兩種方法有明顯差距，證實本文研究算法能在叢集滿載時，仍可計算出較佳的存放位置。

[1] 馬小龍, 劉蘭娟. 基于在線機制設計的私有云資源分配研究[J]. 計算機應用研究. 2015(2): 539-542.

[2] 徐曉斌, 張光衛, 孫其博, 楊放春. 一種誤差可控傳輸均衡的WSN數據融合算法[J]. 電子學報. 2014(06): 1205-1209.

[3] 朱志祥, 許輝輝, 王雄. 基于云計算的彈性負載均衡方案[J]. 西安郵電大學學報. 2013(6): 43-47.

[4] 馮小靖, 潘郁. 云計算環境下的DPSO資源負載均衡算法[J]. 計算機工程與應用. 2013(6): 105-108.

[5] 裴養, 吳杰, 王鑫. 基于粒子群優化算法的虛擬機放置策略[J]. 計算機工程. 2012(16): 291-293.

[6] 劉媛媛, 高慶一, 陳陽. 虛擬計算環境下虛擬機資源負載均衡方法[J]. 計算機工程. 2010(16): 30-32.

[7] 劉春波, 陳建業. 基于SDN的虛擬網絡重映射方法研究[J].軟件. 2016(10): 82-88.

[8] 齊小航, 田清華. 空間信息網中面向任務的多拓撲路由算法[J]. 軟件. 2014(9): 49-56.

[9] 趙禮峰, 梁娟. 最短路問題的Floyd改進算法[J]. 計算機技術與發展. 2014(8): 31-34.

[10] 陳雅良, 溫朝暉, 周浩然, 王甜甜. 基于Floyd算法對交通流最優路徑選擇的研究[J]. 佳木斯大學學報(自然科學版).2016(6): 917-919+942.

[11] 許克平, 曾明月, 鄢好, 袁麗娟, 彭圓紅. 基于不確定因素下的Floyd算法改進[J]. 中國科技信息. 2016(18): 49-50+14.

[12] 左秀峰, 沈萬杰. 基于Floyd算法的多重最短路問題的改進算法[J]. 計算機科學. 2017(5): 232-234+267.

Research on Cloud File Storage Load Balancing Algorithm based on Floyd Algorithm

CHEN Yuan, LIU Jun-hua, LEI Chao-yang
(Internet engineering department, Hunan Post and Telecommunication College, Changsha 410015 China)

This paper proposes the cloud file storage load balancing algorithm based on Floydalgorithm, Based on the client′s access frequency and file size, the calculation of the shortest network distance to optimize the file storage location, and the hop count and network bandwidth between all clients and all service nodes are considered to be their network distance. The simulation results show that: In this paper, the average access cost of the paper is significantly lower than that of random and rotary methods, to place the file location fairly for all users, Allows users to access at least the number of hops or the best bandwidth path, improves the access efficiency of client file. And when most of the cluster space is full, the research methodcan still calculate the better storage location.

: Floydalgorithm; Cloud files; Load balancing; Algorithm

TP301

A

10.3969/j.issn.1003-6970.2017.10.012

本文著錄格式：陳園，劉軍華，雷超陽. 基于弗洛伊得算法的云端文件存儲負載平衡算法研究[J]. 軟件，2017，38（10）：67-72

湖南省教育廳科研項目(編號：16C720)

陳園(1983-），女，湖南長沙人，講師，碩士研究生，研究方向：圖像處理、計算機網絡；劉軍華(1979-)，男，湖南衡陽人，副教授，碩士，研究方向：移動互聯網應用技術、軟件工程；雷超陽(1971-)，男，湖南耒陽人，教授，博士，研究方向：圖像處理、計算機網絡。