視頻網(wǎng)格中自適應(yīng)熱度變化的條塊化存儲(chǔ)

單芝棟

(中國(guó)人民解放軍69240部隊(duì)，新疆烏魯木齊830011)

0 引言

目前，視頻網(wǎng)格［1］采用基于 CDN［2］的存儲(chǔ)機(jī)制，其結(jié)構(gòu)主要由中心服務(wù)器、邊緣服務(wù)器以及用戶組成。每個(gè)服務(wù)器是由多個(gè)計(jì)算元件(Computing Element，CE)和存儲(chǔ)元件(Storage Element，SE)組成［3］。每個(gè)服務(wù)器的CE處理用戶的服務(wù)請(qǐng)求;中心服務(wù)器的SE存儲(chǔ)視頻網(wǎng)格中所有的視頻文件;邊緣服務(wù)器的SE存儲(chǔ)具有高熱度的視頻文件副本。當(dāng)用戶向本域邊緣服務(wù)器申請(qǐng)視頻文件時(shí)，若本域邊緣服務(wù)器的SE已存儲(chǔ)此視頻文件，則直接提供給用戶;否則，用戶需要通過(guò)主干網(wǎng)遠(yuǎn)程訪問(wèn)其他服務(wù)器申請(qǐng)此視頻文件。

在CDN存儲(chǔ)機(jī)制中，視頻網(wǎng)格中大量的次熱度視頻文件未被存儲(chǔ)在邊緣服務(wù)器的SE上，用戶需要通過(guò)主干網(wǎng)遠(yuǎn)程訪問(wèn)其他服務(wù)器才能獲得這些視頻文件，這將造成傳輸延遲。文獻(xiàn)［4－6］提出了解決該問(wèn)題的方法。在文獻(xiàn)［4］中，每個(gè)視頻文件被分為若干視頻數(shù)據(jù)塊，并且存儲(chǔ)于不同的邊緣服務(wù)器。這種存儲(chǔ)機(jī)制增加了邊緣服務(wù)器存儲(chǔ)視頻文件的數(shù)量，但熱度低的視頻數(shù)據(jù)塊長(zhǎng)時(shí)間處于未被點(diǎn)播或是很少被點(diǎn)播的狀態(tài)，造成存儲(chǔ)資源的浪費(fèi);文獻(xiàn)［5，6］提出的視頻點(diǎn)播機(jī)制利用P2P技術(shù)使接收相同視頻服務(wù)的用戶之間形成視頻文件共享群，但由于部分用戶點(diǎn)播行為不穩(wěn)定造成共享群中的其他用戶不能穩(wěn)定地接收視頻服務(wù)，這將影響系統(tǒng)的性能。因此，視頻文件的熱度在視頻文件的存儲(chǔ)調(diào)度過(guò)程中起關(guān)鍵作用，這就需要分析用戶的點(diǎn)播行為，尤其是視頻文件熱度變化，才能對(duì)視頻文件進(jìn)行合理的存儲(chǔ)調(diào)度。

1 視頻文件的熱度特點(diǎn)

視頻文件的熱度在空間上的分布符合Zipf分布，可表示為:

式(1)表示在n部視頻文件中第k部視頻文件的熱度。θ為常數(shù)，稱為深度因子，其取值為［0.271，1］［1］。在 θ分別取 0.6，0.7，0.8，0.9，1.0 時(shí)，利用式(1)計(jì)算n為不同值時(shí)的Pk值，并累計(jì)求和，得出相同的熱度值域空間分布圖，如圖1所示。

圖1 視頻文件熱度值域空間分布

隨著視頻文件數(shù)量的增加，開(kāi)始階段熱度值急劇增加。高熱度視頻文件的熱度值和占總熱度值和很大的比例，但是在急劇增長(zhǎng)之后，熱度值仍具有較高的增長(zhǎng)趨勢(shì)，這說(shuō)明也有較多的用戶申請(qǐng)次熱度視頻文件，尤其是在大規(guī)模的用戶和海量的視頻文件的互聯(lián)網(wǎng)平臺(tái)上的視頻網(wǎng)格中。在CDN存儲(chǔ)機(jī)制中這些視頻文件沒(méi)有被存儲(chǔ)在邊緣服務(wù)器的SE，用戶需要通過(guò)主干網(wǎng)遠(yuǎn)程訪問(wèn)在其他服務(wù)器申請(qǐng)這些視頻文件，造成傳輸延遲。

每一個(gè)視頻文件都存在內(nèi)熱度，即在同一部視頻文件的不同部分的點(diǎn)擊率也存在差異。一般情況下，在視頻文件開(kāi)始播放時(shí)，用戶由于各種原因中斷視頻點(diǎn)播，此時(shí)視頻文件的開(kāi)頭部分的點(diǎn)擊率會(huì)高于視頻文件后面部分的點(diǎn)擊率。在CDN存儲(chǔ)機(jī)制的視頻網(wǎng)格中，存儲(chǔ)在邊緣服務(wù)器上部分熱度高的視頻文件，只是開(kāi)始部分點(diǎn)擊率高，而后面部分的點(diǎn)擊率低，這造成了邊緣服務(wù)器存儲(chǔ)資源的浪費(fèi)。研究結(jié)果表明，用戶接收視頻服務(wù)超過(guò)為5 min［7］時(shí)才能確定整個(gè)視頻文件都具有較高的點(diǎn)擊率，即用戶需要整個(gè)視頻服務(wù)。

視頻文件的熱度在時(shí)間上的變化一般遵循以下過(guò)程:當(dāng)一部新的視頻文件剛加入視頻點(diǎn)播系統(tǒng)時(shí)，在開(kāi)始階段，申請(qǐng)此視頻文件的用戶不斷增加，熱度呈上升趨勢(shì);達(dá)到峰值后由于用戶對(duì)此視頻文件的興趣下降，熱度會(huì)急劇衰退;一段時(shí)間后由于申請(qǐng)此視頻文件的用戶很少，熱度變化趨于平緩。在CDN的存儲(chǔ)機(jī)制中，熱度被分為高熱度和低熱度，不能充分體現(xiàn)熱度在時(shí)間上變化的多態(tài)性。

2 自適應(yīng)條塊化存儲(chǔ)機(jī)制

2.1 視頻文件的分塊機(jī)制

自適應(yīng)熱度變化的條塊化存儲(chǔ)機(jī)制的視頻網(wǎng)格拓?fù)浣Y(jié)構(gòu)以CDN分布式存儲(chǔ)機(jī)構(gòu)為基礎(chǔ)，視頻網(wǎng)格中每個(gè)視頻文件被分為若干體積相同的視頻數(shù)據(jù)塊，數(shù)量一般不超過(guò)10塊［4］。

2.2 邊緣服務(wù)器存儲(chǔ)諸元的設(shè)置

2.2.1 存儲(chǔ)諸元的劃分和功能

邊緣服務(wù)器的SE包括視頻播放區(qū)和暫存區(qū)2部分。視頻播放區(qū)的功能包括:① 當(dāng)視頻文件具有高熱度時(shí)，存儲(chǔ)其全部數(shù)據(jù)塊;② 當(dāng)視頻文件具有次熱度時(shí)，根據(jù)熱度的不同，從第一塊開(kāi)始，連續(xù)存儲(chǔ)不同數(shù)量的視頻數(shù)據(jù)塊。暫存區(qū)的功能包括:①存儲(chǔ)少量次熱度視頻文件的部分視頻數(shù)據(jù)塊，這些數(shù)據(jù)塊與在視頻播放區(qū)內(nèi)正在被點(diǎn)播的視頻數(shù)據(jù)塊組成完整的視頻文件，提供給用戶;② 視頻播放區(qū)更新時(shí)，存儲(chǔ)被本域邊緣服務(wù)器SE的視頻播放區(qū)淘汰的數(shù)據(jù)塊，作為其他邊緣服務(wù)器的視頻播放區(qū)的輔助更新源。

2.2.2 暫存區(qū)的空間設(shè)置

假設(shè)每個(gè)邊緣服務(wù)器的SE體積為T，在單位時(shí)間內(nèi)申請(qǐng)視頻服務(wù)的用戶數(shù)量為λ，用戶申請(qǐng)具有次熱度的視頻文件的概率為μ，則在單位時(shí)間內(nèi)申請(qǐng)次熱度視頻文件的用戶數(shù)量為λμ。在暫存區(qū)中，單個(gè)視頻文件的平均存儲(chǔ)體積為v，視頻播放速度為s，視頻文件的平均播放時(shí)間為v/s，因?yàn)闀捍鎱^(qū)的視頻數(shù)據(jù)塊在播放時(shí)不允許被刪除，在最壞情況下，即在v/s時(shí)間段內(nèi)存儲(chǔ)在暫存區(qū)體積為λμv的視頻數(shù)據(jù)塊未得到重復(fù)利用時(shí)，暫存區(qū)還必須以存儲(chǔ)λμv/s個(gè)用戶點(diǎn)擊次熱度視頻文件的后面視頻數(shù)據(jù)塊，此時(shí)暫存區(qū)的體積可表達(dá)為:

通過(guò)式(2)可以看出，影響Tz的因素與視頻網(wǎng)格中視頻文件的數(shù)量無(wú)關(guān)。因此，在大規(guī)模的視頻點(diǎn)播系統(tǒng)中，當(dāng)邊緣服務(wù)器存儲(chǔ)的視頻文件數(shù)量很大時(shí)，即邊緣服務(wù)器的存儲(chǔ)空間非常大時(shí)，TZ＜＜T。

2.3 視頻文件的調(diào)度機(jī)制

當(dāng)邊緣服務(wù)器接收用戶申請(qǐng)時(shí)，系統(tǒng)自動(dòng)更新視頻文件的熱度，并根據(jù)不同的熱度對(duì)視頻文件采取不同的調(diào)度策略:

①高熱度。視頻播放區(qū)完全存儲(chǔ)此類視頻文件的視頻數(shù)據(jù)塊，邊緣服務(wù)器可以直接提供視頻服務(wù)給用戶。

②次熱度。當(dāng)用戶接收視頻服務(wù)超過(guò)5 min后，若本域邊緣服務(wù)器的暫存區(qū)已存儲(chǔ)相應(yīng)的視頻數(shù)據(jù)塊，則和在視頻播放區(qū)內(nèi)用戶申請(qǐng)的視頻數(shù)據(jù)塊組成完整的視頻文件提供給用戶;否則，根據(jù)負(fù)載均衡調(diào)度原則［1］從其他服務(wù)器上尋找相應(yīng)的視頻數(shù)據(jù)塊，并保存到暫存區(qū)，為同一時(shí)間段內(nèi)申請(qǐng)此視頻文件的其他用戶提供視頻服務(wù)。

③低熱度。邊緣服務(wù)器擔(dān)任中介者角色，由其他視頻服務(wù)器提供視頻服務(wù)。

2.4 視頻文件的更新機(jī)制

由于每個(gè)邊緣服務(wù)器的視頻播放區(qū)存儲(chǔ)的視頻數(shù)據(jù)塊的不同，在對(duì)視頻播放區(qū)的視頻文件進(jìn)行更新時(shí)，需逐個(gè)節(jié)點(diǎn)進(jìn)行處理。首先系統(tǒng)CE統(tǒng)計(jì)視頻文件的熱度，并清空暫存區(qū);設(shè)si為第i個(gè)邊緣服務(wù)器，ci為第i個(gè)視頻文件，P為視頻文件的熱度，更新步驟如下:

①si對(duì)本域被點(diǎn)播的視頻文件的熱度進(jìn)行降序排列，即 PQ:PC1，Pc2...，Pcn...，Pcm，相應(yīng)的視頻文件序列為 Q:C1，C2...，Cn...，Cm;

②如果Pci為次熱度或者高熱度，則S1節(jié)點(diǎn)中視頻文件子序列為 G:C1，C2...，Cn并被保留在視頻播放區(qū);

④當(dāng)Pci為次熱度時(shí)，若視頻播放區(qū)存儲(chǔ)的視頻數(shù)據(jù)塊的數(shù)量超過(guò)系統(tǒng)定義的存儲(chǔ)數(shù)量，則多余的視頻數(shù)據(jù)塊被轉(zhuǎn)移到暫存區(qū);若低于系統(tǒng)定義的存儲(chǔ)數(shù)量，系統(tǒng)根據(jù)負(fù)載均衡原則從其他服務(wù)器的SE尋找并下載相應(yīng)的視頻數(shù)據(jù)塊;

⑤采用以上相同的步驟對(duì)其他邊緣服務(wù)器視頻播放區(qū)內(nèi)的視頻文件進(jìn)行處理;

⑥清空所有邊緣服務(wù)器暫存區(qū)的內(nèi)容。

當(dāng)暫存區(qū)中視頻數(shù)據(jù)塊總體積超過(guò)額定容量，系統(tǒng)使用LFU［2］算法對(duì)暫存區(qū)實(shí)時(shí)更新。

2.5 性能分析

這里提出的自適應(yīng)熱度變化的條塊化存儲(chǔ)機(jī)制的前提是大規(guī)模視頻播放系統(tǒng)，視頻播放區(qū)的存儲(chǔ)容量TP≈T，視頻網(wǎng)格中單個(gè)視頻文件的平均體積為vc，則邊緣服務(wù)器能存儲(chǔ)的視頻文件數(shù)量為NC=T/VC。單部視頻文件被平均分成的數(shù)量為n;邊緣服務(wù)器視頻播放區(qū)存儲(chǔ)i塊視頻文件的數(shù)量為ki，則視頻播放區(qū)存儲(chǔ)的單個(gè)視頻文件的平均體積，視頻播放區(qū)存儲(chǔ)的視頻文件的數(shù)量在CDN存儲(chǔ)機(jī)制下邊緣服務(wù)器SE可存儲(chǔ)的視頻文件數(shù)量為T/V。

3 仿真模擬

因?yàn)樵诓煌囊曨l網(wǎng)格環(huán)境中存在不同的傳輸帶寬和存儲(chǔ)空間，會(huì)導(dǎo)致不同的熱度劃分和視頻文件分塊數(shù)量，導(dǎo)致出現(xiàn)不同參數(shù)的自適應(yīng)熱度變化的條塊化存儲(chǔ)機(jī)制，所以下面舉例仿真。在CDN存儲(chǔ)機(jī)制中，前12%的視頻文件被定義為高熱度視頻文件，被存儲(chǔ)在邊緣服務(wù)器SE中。在自適應(yīng)熱度變化的條塊化存儲(chǔ)機(jī)制中，根據(jù)圖1所顯示熱度值變化曲線，視頻文件的熱度值分為:高熱度、次熱度(較高熱度、次高熱度、一般熱度)和低熱度。這里采用視頻網(wǎng)格模擬器VGSim［8］進(jìn)行模擬仿真。通過(guò)總結(jié)分布式視頻點(diǎn)播的多種模型［3，4，9］，實(shí)驗(yàn)建立了一個(gè)由40個(gè)節(jié)點(diǎn)組成的模擬環(huán)境，site0為中心服務(wù)節(jié)點(diǎn)，其他39個(gè)節(jié)點(diǎn)是邊緣服務(wù)器節(jié)點(diǎn)。主干網(wǎng)帶寬是 1 GB/s，每部視頻文件的體積為375 MB，site0共存儲(chǔ)了5 000部視頻文件。在CDN存儲(chǔ)機(jī)制下，每個(gè)邊緣服務(wù)器可以存儲(chǔ)600部視頻文件，T為60 s，視頻文件的播放碼率為512 kbps，λ=2，根據(jù)式(2)和實(shí)際系統(tǒng)情況，設(shè)暫存區(qū)容量為1 GB。

結(jié)合圖1每部視頻文件被分成4塊體積相等的視頻數(shù)據(jù)塊，當(dāng) θ分別為 0.6，0.7，0.8，0.9，1.0時(shí)，熱度值域劃分表(pk是視頻文件的熱度值)，如表1所示，視頻文件分塊存儲(chǔ)機(jī)制表按照高熱度(前4%)、較高熱度(5% ～11%)、次高熱度(12% ～14%)、一般熱度(15% ～17%)分別存儲(chǔ)前4、3、2、1塊視頻數(shù)據(jù)塊。表1中括號(hào)內(nèi)數(shù)字表示數(shù)值范圍。

表1 熱度值域劃分表

首先對(duì)CDN存儲(chǔ)機(jī)制進(jìn)行仿真模擬，邊緣服務(wù)器中視頻文件的更新算法采用LFU算法;然后對(duì)自適應(yīng)熱度變化的條塊化存儲(chǔ)機(jī)制模擬仿真。在仿真開(kāi)始時(shí)所有的視頻文件都被存儲(chǔ)在中心服務(wù)節(jié)點(diǎn)，隨著仿真的進(jìn)行，視頻文件分別按照CDN存儲(chǔ)機(jī)制和自適應(yīng)熱度變化的條塊化存儲(chǔ)機(jī)制被逐步推送到邊緣服務(wù)器的SE上，相應(yīng)的主干網(wǎng)帶寬的占用情況和邊緣服務(wù)器存儲(chǔ)的視頻文件數(shù)量情況分別如圖2、圖3和圖4所示。

圖2 條塊化存儲(chǔ)機(jī)制時(shí)主干網(wǎng)帶寬變化

圖3 CDN存儲(chǔ)機(jī)制時(shí)主干網(wǎng)帶寬變化

在自適應(yīng)熱度變化的條塊化存儲(chǔ)機(jī)制中，由于視頻文件最初只存儲(chǔ)在中心服務(wù)器上，用戶需要向中心服務(wù)器申請(qǐng)視頻文件，這占用了大量的主干網(wǎng)帶寬。隨著時(shí)間的推移，視頻文件副本的全部或者部分視頻數(shù)據(jù)塊被推送到邊緣服務(wù)器的視頻播放區(qū)，主干網(wǎng)帶寬消耗減少。當(dāng)用戶接收存儲(chǔ)在視頻播放區(qū)內(nèi)次熱度的視頻文件超過(guò)5 min時(shí)，系統(tǒng)通過(guò)主干網(wǎng)從其他服務(wù)器下載此視頻文件中未被存儲(chǔ)在視頻播放區(qū)的視頻數(shù)據(jù)塊，這將占用主干網(wǎng)帶寬。但是系統(tǒng)對(duì)暫存區(qū)存儲(chǔ)的視頻數(shù)據(jù)塊采用緩存復(fù)用策略，避免了在同一段時(shí)間內(nèi)其他用戶通過(guò)主干網(wǎng)調(diào)用相同的視頻數(shù)據(jù)塊而消耗的主干網(wǎng)帶寬。因此，主干網(wǎng)帶寬占用情況和CDN存儲(chǔ)機(jī)制下的主干網(wǎng)帶寬占用情況有一定增加(如圖2和圖3所示)，但無(wú)明顯差別。由圖4可知，在穩(wěn)定狀態(tài)下，邊緣服務(wù)器上存儲(chǔ)的視頻文件的數(shù)量在自適應(yīng)熱度變化的條塊化存儲(chǔ)機(jī)制下比CDN存儲(chǔ)模式下明顯增加。

圖4 邊緣服務(wù)器視頻文件存儲(chǔ)數(shù)量

4 結(jié)束語(yǔ)

在自適應(yīng)熱度變化的條塊化存儲(chǔ)機(jī)制中，系統(tǒng)對(duì)每個(gè)視頻文件進(jìn)行分塊存儲(chǔ)和調(diào)度，減少了單個(gè)視頻文件在邊緣服務(wù)器上的平均存儲(chǔ)體積，增加了邊緣服務(wù)器存儲(chǔ)視頻文件的數(shù)量。當(dāng)用戶點(diǎn)擊次熱度視頻文件時(shí)，對(duì)實(shí)時(shí)從其他視頻服務(wù)器下載的視頻數(shù)據(jù)塊進(jìn)行緩存復(fù)用，減少了視頻文件分塊存儲(chǔ)和調(diào)度而消耗的主干網(wǎng)帶寬。因此，自適應(yīng)熱度變化的條塊化存儲(chǔ)機(jī)制在不明顯增主干網(wǎng)帶寬消耗的同時(shí)，極大地增加邊緣服務(wù)器存儲(chǔ)視頻文件的數(shù)量，提高了用戶在本域邊緣服務(wù)器申請(qǐng)視頻文件的命中率，減少了傳輸延遲。

［1］劉 鵬.高性能和高可用性海量存儲(chǔ)技術(shù)研究［D］.北京:清華大學(xué)，2006:140.

［2］PALLIS G，VAKALI A.Insight and Perspectives for Content Delivery Networks ［J］.ACM Communication，2006，49(1):101.

［3］那寶玉，張毓森，劉 鵬.基于網(wǎng)格技術(shù)的視頻服務(wù)系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)［J］.吉林大學(xué)學(xué)報(bào)，2008，26(2):187.

［4］FEI Zongming，YANG Mengkun.A Segmentation-Based Fine-Grained Peer Sharing Technique for Delivering Large Media Files in ContentDistribution Networks［C］∥ IEEE Transactions on Multmdia，2006，8(4):821－829.

［5］LIU Xinwen，ZHAO Hong，CAO Jie，et al.The Application of P2P Mechanism in Video Grid［C］∥Proceedings of the International Conference on World Congress on Computer Science and Information Engineering，CSIE 2009，6(3):11－15.

［6］LIU Yong，GUO Yang，LIANG Chao.A Survey on Peer-topeer Video Streaming Systems［J］.Peer-to-Peer Networking and Applications，2008，1(1):18 －29.

［7］王 飛，奚宏生，楊 堅(jiān).集群式VoD系統(tǒng)中文件分塊存儲(chǔ)策略［J］.計(jì)算機(jī)工程，2008，34(21):213.

［8］趙 宏，吾守爾·斯拉木，侯 勇，等.Architecture and Realization of Simulator of Video Grid［J］.Proceedings of PACIIA’08，2008，6(4):521 －526.

［9］HUANG Yan，F(xiàn)U Tom Z J，CHIU Dah-Ming，et al.Design and Analysis of a Large-scale P2P-VoD System［J］.In ProceedingsofACM SIGCOMM ’08 Seattle， 2008，3(1):127.