自適應的集群流媒體文件副本放置策略

摘要:提出了資源負載的三種負載均衡狀態，分析了這三種狀態的均衡程度，并據此提出一種自適應的副本放置算法，成功地應用于集群VOD系統中，彈性地解決負載均衡與后端存儲帶寬的矛盾。通過仿真證明，該算法在不同數據量的情況下均具有很好的負載均衡性和優異的整體性能。

關鍵詞:流媒體; 集群; 副本; 負載均衡

中圖分類號:TP37文獻標志碼:A

文章編號:1001－3695(2008)02－0594－03

隨著流媒體在互聯網上的普及，眾多寬帶運營商正在積極地建設寬帶流媒體平臺，如在線音樂收費服務#65380;網絡電視(IPTV)#65380;視頻會議#65380;遠程教育#65380;遠程醫療#65380;VOD等增值電信服務。隨著寬帶的普及#65380;用戶的增長以及多媒體信息的膨脹，流媒體服務器正在成為整體服務的瓶頸。越來越多的流媒體服務器采用了集群的體系結構，以解決單個服務器I/O能力有限#65380;硬件昂貴等問題。在集群VOD系統中，最為常見的一種系統結構就是前端機作為訪問的單一入口點，客戶提交請求到前端機，前端機將該請求調度到提供服務器的媒體服務器，媒體服務器讀取存儲介質上的媒體數據，發送給客戶端。其中，存儲介質可以是RAID#65380;SAN。在這兩種存儲介質中，SAN是性能最好的一種，但是價格太貴。所以本文選擇RAID作為存儲介質。

在沒有緩存的情況下，所有服務器的I/O負載均聚集到RAID上，造成很大的I/O壓力，同時，網絡文件系統也難以支持。因此，許多系統均使用了服務器的本地磁盤作為緩存，以減輕后端的壓力。例如，文獻[1]提出間隔緩存策略，以減少服務器從存儲節點取數據的頻度;文獻[2]通過對文件片段的訪問規律分析，提出分片存儲的方式以利用單部影片的內部熱度不一致性來提高對熱點的預測能力;文獻[3]提出一種根據熱度將影片均勻放置的策略。這三種方式分別以三個層次，即服務器層#65380;影片內部層和影片層來減少存儲服務器的I/O負載。其中均勻副本放置策略主要是指媒體文件副本的放置策略，因而是影片層的算法。這類算法普遍依賴于影片的熱度統計以及擬合的正確性。

許多文章分析了影片的熱度分布#65380;點播曲線等。例如，文獻[5]考察了媒體文件之間的點播曲線的不同，發現影片的點播分布服從Zipf分布;10%的影片點播次數占所有影片點播數的73%。這表明媒體服務器只要有存儲服務器10%的存儲能力，就能夠分擔73%的I/O壓力。文獻[4]根據點播的TRACE得到了單個媒體文件的點播曲線，將單個媒體文件的生命周期分為上升#65380;平穩和下降階段，并給出了各階段熱度的預測曲線。文獻[6]考察了媒體文件在各時間段的退出概率。

1體系結構

整個集群流媒體服務分為調度#65380;流媒體服務#65380;副本管理#65380;文件系統四個主要部分。其系統結構如圖1所示。

調度器負責接收來自客戶端的請求，查詢數據庫。如果請求的媒體文件存在于某個節點的本地磁盤，則調度到該節點上;如不存在，則調度到負載較輕的服務器，服務器通過網絡文件系統獲取存儲池中的文件來提供服務。

流媒體服務器接收來自客戶的RTSP請求，讀取本地磁盤或存儲池中的媒體數據，發送到請求的客戶。

副本管理包括一個刷新計算模塊和一個本地的副本管理模塊。刷新計算需要定時刷新影片的點擊信息。每過一天，該模塊需要保存前一天的點擊數，并將今天的點擊數置零。另外，該模塊也需要計算在本地副本管理用到的一些信息。本地副本管理則根據數據庫中的信息來判斷哪些影片應該保存在本地。

存儲池中存放了所有影片，并通過網絡文件系統共享給每一個流媒體服務器。

2副本放置策略

在上面所示的系統結構中，有兩點對系統的整體性能影響非常大:

a)負載均衡度。當服務器均能發揮自己的最大性能時，系統整體的性能是各服務器性能之和。在圖1的體系結構中，負載均衡程度取決于本地磁盤中的影片放置方式。如果每個服務器上均存放相同的影片，調度算法會選擇負載較小的服務器來響應請求。但是如果存放的影片不同，則存放熱點電影較多的服務器負載會比較高，而其他服務器則達不到這樣的負載。

b)存儲池與流媒體服務器之間的帶寬。根據測試，NFS在100 Mbps以太網環境下能達到的帶寬為34 Mbps，這樣的帶寬在流媒體高的I/O服務下是遠遠不夠的。即使采用千兆以太網，帶寬最多達到340 Mbps，存儲將成為系統的瓶頸。可以通過增加本地磁盤上放置的影片數量，降低存儲負載。

只有在各服務器上放置不同的影片，才能提高本地放置的影片數量。但是這樣又會影響到服務器的負載均衡性。因此，下面分析在不同放置方式下服務器的負載均衡性，希望能在影片放置數量和負載均衡上取得一個合適的折中方案，以使系統的整體性能達到最大。

2.1放置策略對負載均衡的影響

集群在VOD上的應用是典型的負載均衡集群。對于集群的負載均衡特性，一般地，服務器達到相同負載，如CPU#65380;I/O#65380;內存的負載相同，就認為具有很好的負載均衡特性。但這些均集中在服務器的CPU#65380;內存#65380;I/O等硬件指標上，很少考慮針對服務器所具有的信息#65380;軟件等資源的負載均衡。

在此，將VOD集群的負載均衡特性劃分為三種特性:

a)完全負載均衡，即服務器完全同構，調度器可以完全根據服務器的負載調度到各節點。此時各服務器上的文件完全一致，因而前端調度器可選擇負載最低的服務器來調度任一請求。

b)比例負載均衡，即資源放置的節點數量與資源的請求數量成正比。

對于資源S，設Q(i)為S(i)的請求數量，若對于每部影片S(i)，均有Q(i)/S(i)=K(K為一常數)。在這種方式下，資源的請求量越大，則副本數越多。例如M1的請求概率為0.4，M2的請求概率為0.2，M3的請求概率為0.4，則M1#65380;M2#65380;M3的可能副本放置如圖2所示。

如圖2所示，請求概率為0.4的文件M1#65380;M3放置數量均為2;請求概率為0.2的文件放置數量為1，即請求概率/放置數量=常數。c)概率負載均衡，即按照資源的請求概率，任意節點上的資源請求概率總和相等。概率負載均衡指對于下一時刻到達的請求，每一個服務器均能以相同的概率服務該請求。在1－1文件放置中，對于任一服務器Sj，其上的影片集合為{M1，M2，…，Mi}，每部影片的訪問概率為P(Mi)。如果滿足P(M，Si)=P(M，Sj)，則稱滿足概率負載均衡。概率負載均衡的意義在于即使服務器所能服務的請求完全不同時，仍然會由于請求的分布規律，使服務器達到一定的均衡程度。

對于服務器S1#65380;S2，如S1上存放的影片為M1#65380;M2#65380;M3，訪問概率依次為0.02#65380;0.09#65380;0.14;S2上存放的影片為M4#65380;M5#65380;M6，訪問概率依次為0.05#65380;0.06#65380;0.14。此時P(S1)=P(S2)。據此可認為此時S1與S2之間滿足概率負載均衡。

在這三種負載均衡能力中，均衡度依次遞減。其相應的放置策略適應于不同的LD/ND(即本地磁盤容量與存儲服務器容量之比)。當LD/ND較大時，適用完全負載均衡;中等時，適用比例負載均衡;較小時，則適宜結合比例負載均衡和概率負載均衡。

2.2放置策略的目標

根據上面的分析，當服務器能夠同時滿足比例負載均衡和概率負載均衡時，其真實負載均衡能力接近于完全負載均衡，而對磁盤的利用率要遠高于完全負載均衡。據此，本文提出的放置策略同時滿足以下要求:

a)近似的比例負載均衡。在上一節中描述的比例負載均衡特性過于理想化，在實際的系統中不可能達到。另外，比例負載均衡的性能并不是局部最優點，所以，完美的比例負載均衡也不是必要的。

b)近似的概率負載均衡。同樣，達到完美的概率負載均衡也是不可能的，這是由于:(a)熱點統計及預測的誤差;(b)各服務器概率總和也只能達到近似的相等。要做的是將此偏差控制在一定范圍內。

c)自適應能力。在影片數量較少的情況下，放置策略具有完全負載均衡的效果，隨著影片數量的增加，能平滑過渡到比例負載均衡和概率負載均衡。

2.3熱度預測到放置價值的映射

熱度預測值反映了影片受關注程度，其具有的特點是:a)量的不確定性。熱度預測值的范圍分布廣泛，可以是0~100，甚至10 000。b)不具有對比性。熱度預測值并不能衡量對象受歡迎的相對程度。因此，簡單的熱度預測值并不能作為副本放置的依據，而需要通過一些變換使其具有相對性的特征，并具有可比較性。這里的方法是通取其中熱度預測值最大的一個max(H)，計算100×H(Mi)/max(H)，將預測的熱度值全部轉換為0~100的整數;同時，引入放置價值的概念，影片的放置價值與熱度值成正比，而與副本數量成反比。

2.4放置價值評估agent

上文提到，影片級的緩存強烈地依賴于對影片點播的統計和預測。影片復制程序根據影片的點播預測值來確定該影片的拷貝價值，根據拷貝價值來執行相應的動作。拷貝價值的評估發起者決定了整體的結構。內部C/S模式的發起者為server端，分布式 agent的發起者為每一個提供服務的服務器。

采用內部C/S模式的好處是，對于每一次的copy#65380;replace操作只需要查詢一次數據庫。壞處則是提供服務的服務器，也就是C/S中的client要花費很大的代價保證自己的緩存與數據庫中的信息一致，因為一致性的檢查需要C~S，S~database兩步大數據量的通信。

采用agent更容易保證一致性，而且避免單一失效的故障，從結構上來說更為簡單高效。但是帶來的問題是如何在無統一管理下，各agent僅僅通過數據庫的信息，就能夠以一定行為從整體上達到概率和比例負載均衡。

對此，分別采取兩種辦法，即復制更新和輪換概率。

1)復制更新該基本思想是每次從確定復制#65380;替換或刪除操作之后，不僅要修改副本的存放信息，也要修改該影片的放置價值。

2)輪換概率該方法是每次agent依自身概率總和的高低依次運行，所獲取的影片是按照請求概率從高到低排列，然后與緩存中的影片比較，符合替換條件的，則進行替換。

復制更新解決分布式agent比例負載均衡的問題;輪換概率則解決了概率負載均衡的問題。

3模擬與運行結果

在模擬過程中load使用Zipf分布請求資源，到達率服從Possion分布。設定預測值與load中的熱度值誤差為10%。

系統啟動之后，初始化對象的Zipf分布，將分布離散化，使之成為隨機隊列;再由loader對依Possion分布取出請求隊列，發往scheduler;scheduler依負載均衡及資源位置調度到后臺的服務器。其中，以三種負載均衡的放置特征，以及本文提出的放置策略，系統的吞吐量在各種系統配置下的結果如圖3所示。

圖3比例負載均衡的性能在各種條件下均優于完全負載均衡和概率負載均衡，而結合了比例與概率的自適應策略則更優于比例負載均衡，這正是由于從整體(服務器負載)和局部(影片熱度)兩步優化所帶來的性能提升。

4結束語

本文針對傳統的服務—存儲模式的集群VOD系統，提出了一種自適應分布式的媒體副本放置策略，綜合考慮了負載均衡，存儲節點I/O能力，提升集群流媒體服務系統的整體性能。將來的工作可以往兩個方向展開，一方面可以將三個層次，即服務器緩存層#65380;媒體文件層和文件內部層的放置結合起來，進一步提升流媒體服務器的性能;另一方面可以將該放置策略推廣到其他，如P2P類型的分布式系統。

參考文獻:

[1]林光國，戴瓊海，丁嶸.基于用戶行為統計的流媒體集群負載均衡算法[J]. 清華大學學報:自然科學版，2005，45(4):525－528.

[2]吳松，李玉福，金海.流媒體服務器的間隔緩存管理策略研究[J]. 華中科技大學學報:自然科學版，2003，31(4):27－29.

[3]ANASTASIADIS S V，SEVCIK K C，STUMM M. Modular and efficient resource management in the exedra media server[C]//Proc of the 3rd USNIX Symposium on Internet Technologies and Systems. San Francisco:[s.n.]，2001.

[4]SANTOS J R，MUNTZ R. Comparing random data allocation and data striping in multimedia servers[C]//Proc of ACM Sigmetrics.Santa Clara:[s.n.]，2000.

[5]DAN A，SITARAM D. Buffer management policy for an on－demand video server，RC 19347[R].[S.l.]:IBM.

[6]BOLOSKY W，DRAVES J，FITZGERALD R， et al. The tiger video fileserver[C]//Proc of NOSSDAV’96. 1996.

[7]SANDSTA O， LANGORGEN S，MIDTSTRAUM R. Video server on an ATM connected cluster of workstations[C]//Proc of International Conference of the Chilean Computer Science Society. 1997:207－217.

[8]HARTMAN J H，OUSTERHOUT J K. The Zebra striped network file system[J].ACM Trans on Computer Systems，1995，13(3):274－310， 1995.

[9]SHENOY P， VIN H M. Efficient striping techniques for variable bit rate continuous media file servers[J]. Performance Evaluation， 1999， 38(3):175－199.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”