ѧ
JOURNAL OF SOFTWARE
1999 4 10 Vol.10 No.4 1999



ģλƵ㲥洢ϵͳ*
¡⡡ɡ¸
ժҪͨżķչʹƵ㲥video-on-demand,VOD)ڼ;ϳΪ.ýʹVODϵͳҪģĴ洢.λ洢ϵǼϵͳõĺ.һֲλĴ洢ģͺʹcacheĸ.ģ,˻ڷƵʵ滻㷨,㷨ЧԽģͷ.,㷨LFU(least frequently used)㷨еġcacheȾcache pollution,ܽϺõýӦ.
ؼʡý,Ƶ㲥,λ,洢,滻㷨.
ͼšTP393
Design and Management of Large Scale 
Hierarchical VOD Storage System
LI YongWU FeiCHEN Fu-jie
Department of Computer Science Changsha Institute of Technology Changsha410073
AbstractRecent advances in computing and communication technologies have made VOD video-on-demand technically feasible and economically. The VOD system needs massive storage server because of the characteristic of the continuous media. Hierarchical storage is a good solution for the system under low cost. In this article, the authors first propose a hierarchical architecture model and the concept of disk cache, then develop a replacement algorithm based on access frequency by the model, finally analyse and simulate the algorithm. The results show that the algorithm avoids cache pollution problem in LFU (least frequently used) algorithm and well suits the applications of the continuous media data objects.
Key wordsContinuous media, VOD (video-on-demand), hierarchical, storage server, replacement algorithm.
ʹ洢Ľչʹöý(on line)ʳΪ.,Ƶ㲥VODһ͵Ӧ÷,ΪĿǰֲʽýоȵ1.VOD洢,Ѿ˺ܶɫо26.ЩоýʵʱԷ̵ȺʹеķֲŻȡһĳɹ,,Ǵ󶼾ڵڵСģƵо.Brubeckף5һֲַVODϵṹ,ӰƬֲģСƵ.оһִģļʽVODϵͳ,һķϴ洢˴ӰƬ,ֺ֧ܴģĿͻĿ.Ͻ,صķЭͬ.ģVODϵͳϢṩߺ߶,ҲԴŻʹ.
ýʵʱ,ģVODϵͳҪ޴Ĵ洢.һ100ӵӰƬ,4MbpsMPEG-ѹ׼Ҫ3GBĴ洢,1 000ӰƬҪ3TBĴ洢.
ݱ1ʾĲ,ӰƬ洢ڴ,ϵͳ洢ýﵽ600Ԫ,ϵͳ֧1 000û,ÿû洢Ϊ6 000Ԫ,ھǲе.ʹô̴洢ӰƬ,ϵͳ洢Ϊ150Ԫ,ûƽΪ1 500Ԫ.ʹù,ϵͳ洢Ϊ1.5Ԫ,ûƽýΪ15Ԫ,ھ߿.,̵̫,.ɼ,һĴ洢ܺͼ۸ϵ˫Ҫ.ΪƼҪ,ֺĴ洢,ʽ洢һֺѡ.
1洢

豸ӳ(ms)(Mbps)۸($/MB)
ڴԼ0.018002 0002
10202004000.5
305010200.005


λ洢ϵͳǽȫݴ洢ڵٵĺԮ洢,ѳõݴھнϸٶȵĴ洢,󲿷ֵķڸ,洢ϵͳܽӽڸٴ洢,ƽ۸ӽںԮ洢,ܼ۸Ⱦ.ܷﵽЧȡݷʵľֲԺ滻㷨Ч.
һֲλ洢ϵͳģͺʹcacheĸ.VODϵͳݷԺݾֲԽ˷,VODϵͳʹͳļϵͳԵĲͬ,µ滻㷨.µ1ϵͳģ,VODӰƬݵķԺͷʵľֲ.2˲λ洢ϵͳ滻㷨,㷨ģͷ.3ȫĵܽ. 
1VODݷԺϵͳģ
ǵVODϵͳģǴڷֲµĲʽṹ.ͼ1ʾ,͵ķֲڹϣInternet.ͼĵASṩԮ洢,ȫӰƬ洢,ʵŵӰ.Ǳص,Ҳص,֮Խ.ƵVS洢ӰƬ,ͻṩ㲥ʵʱ.ͻǻУset-top-boxý,ͨ(EFS),ͻ,ǷԼһضƵ,ȻƵΪͻṩʵʱ.Ƶͱĵɲλṹ,޴ӰƬ洢ɹ̻ŴɵĺԮ洢,ɴ̹ɵĶ洢洢ǷʸʽϴӰƬ,ǳ֮Ϊcache.û㲥ƵӴ̶ڴ滺,ͨ緢͸ͻ.


ͼ1ϵͳģͺͷṹ
λ洢ϵͳĹؼݷʵľֲ,ĿǰûдģͶʵеVODϵͳ,޷ͳƳȷеӰƬ,,ǿӰͳ,ΪVODϵͳƷ.о,ʸʴӴС,ӰƬķʸʻϷZipf,NӰ,iӰķʸf(i)=C/i,i=1,2,...,N,.
ͼ2ʾ,ͻĵ㲥ǰһСӰƬ,ӰƬʵľֲ.ӰƬʱ,־ֲԱֵø.о,ŵλʱڷ,ӰƬķʸʽø,ӶʵľֲԾ͸ǿ.,ģVODϵͳòλ洢Ǻʵ.һӰƬڲͬʱڵķʸ,ȻÿӰƬķʸвͬı仯ص,ǶƽȺ½3׶,Ƿֱ֮Ϊɳڡں˥.Ȼ,ɳڵӰƬcache.

ͼ2Zipfµķ
ӰƬֵķʾֲǲλVOD洢ϵͳƺ͹,һڽݵľֲԺӰƬʸʵı仯ɿʵ滻㷨.
2δ洢ϵͳĹ
λ洢ϵͳĹҪʲе.ڲλVODϵͳ,Ҫڴݵѡȡ,cache滻㷨.ڴͳļϵͳ,cache滻㷨ҪFIFO(first in first out),LRU(least recently used)LFU(least frequently used).FIFO㷨,ֻǽȽcache滻,ûпݵʹLRU㷨ݵʱֲ,ʹõ滻cacheLFU㷨ݵʹƵ,ʹƵС滻cache.
VODϵͳ,ӰƬݳߴܴ,ݷһǰ˳,ʱֲԲǿ,ڷʾֲ,FIFOLRU㷨ڴcache.LFU㷨ݵķƵ,νcacheȾ⣨cache pollution,һʶζֲʹõݲܼʱ滻cache,cacheʣ7.
ǸVODϵͳӰƬʹڽϳ,Ƶʱ仯һĹЩص㿪һƵԤ㷨(periodic frequency prognosis,PFP).ʱᰴһĳȻֳһڣT1,T2,....ֻǰһںͱڵķƵǷ滻.,ķƵʱε,ͿԱLFU㷨еcacheȾ.㷨Ҫ˼÷Ƶʵı仯,ɳڵӰƬ绻,˥ڵӰƬ绻.ڵмʱʹƵʷ,ڵĽʱʹԤⷨ滻㷨.
TiʾiڣiΪȻ.PkΪkӰ.ΪNӰƬԱʾΪ
S{Pk|k=1,2,...,N}.
fkiΪPkTiеķʸ.ŵӰʾΪShot={Pk|fki>},ŵӰʾΪScold={Pk|fki<}.ЦΪӰʸʵֵ.ǵĿǽŵӰŵȥ,㷨,̶һŵӰ,ͳӰƬķƵ,÷ƵӰƬķʸ.
NkiΪPkTiеķʴ;FkiΪPkT1Tiܵķʴ,;WkiΪPkTiTi-1ʴ,WkiNkiNki-1.ÿʱ,ͳܷʴ.ΪÿӰƬһԪ顴Fki,Fki-1,Fki-2,ٸNkiWki:Nki=Fki-Fki-1,Wki=Nki-Nki-1.
(a) ÿڵм,ʹ.
ʱΪt,kӰƬܵķʴΪFk,ڵΪֹķʴΪNk,
Nk=Fk-Fki-1,ǽcacheеӰƬƵʵı仯Ϊ½.
Sa={Pk|Wki>0},½Sd={Pk|Wki<0}.
Ԯ洢дڡƵʴֵӰƬһ뼯,
Sin={Pk|Nki>,Wki>0}.
ԵKӰƬʱ,У
PkSin,㻻,㹻Ŀռͻ,,˳򻻳ӰƬ.
(1) SdеǰʱڵķƵʼһڵķƵʣNk-1+NiСΪPk,Nki>Nki,Pk任,˳,,ת2
(2) SaеǰʱڵķƵʼһڵķƵʣNk-1+NiСΪPk, Nki ->Nki, Pk任.
(b) ڵĽʱ,ʹԤ.
 һԷԤһʱڵķƵNki+1=Nki+Wki,
 廻ֵinͻֵout,
 㻻Nki+1>in,Wki>0ӰƬ뻻뼯Sin,
 㻻Nki+1<out,Wki<0ӰƬ뻻Sout,
 ضʱ,еӰƬ,Nki+1ĴС˳򽫻뼯еӰƬλ,ֱ̿ռΪֹ.
÷Zipfм򵥵ģ3滻㷨Ч,ͼ3ʾʾ,ƵԤ滻㷨(PFP),FIFOLRUʽϵ,߲𲻴.FIFO滻,ӰƬʱƱ滻cache,.LRUʹõӰƬ滻cache.ӰƬΪʹ,Աڴcache,ӰƬһ滻cache,ؽ滻ӰƬ,Ӷ滻,.ڷƵʵ㷨,ɽӰƬڴcache,ӰƬΪƵʵͶ滻cache,ἷռӰƬĴ̿ռ,.

ͼ3滻㷨ģ
3
ڴģVODϵͳ,ӰƬݾзʾֲ.ַʾֲ,һֲλĴ洢ϵ.VODӰƬݷƵʱ仯,ǿƵԤ滻㷨PFP.滻㷨LFU㷨еcacheȾ.ģʵʾ,LRU㷨FIFO㷨,㷨Ч.VODλ洢ϵͳҪо,,cacheĴСáԮԵ.ͻģͶϵͳӰܴ,Ŀǰûоȷģ,Ҫһо.
*оõֲصʵһ.
ͨѶϵˣ,ɳ 410073,ɳѧԺϵо
߼顡,1970,ʿ,ҪоΪֲʽý,Ƶ,ý紫.
,1968,ʿ,ҪоΪ֯ϵͳṹ,ֲʽý弼.
¸,1935,,ʿʦ,ҪоΪܼϵṹ,ֲʽý弼.
ߵλɳѧԺϵɳ410073
Email: yli@nudt.edu.cn
ο
1Gemmell D J et al. Multimedia storage servers: a tutorial. IEEE Computer, 1992,28(5):4049
2Rangan P V, Vin H M, Ramanathan. Design an on-demand multimedia service. IEEE Communication Magazine, 1994,30(7):5664
3Lougher P, Shepherd D. The design of a storage server for continuous media. The Computer Journal, 1993,36(1):3242
4Banu Ozden, Rajeev Rastogi, Avi Silberschatz. On the design of a low-cost video-on-demand storage system. Multimedia System, 1996,4(1):4054
5Brubeck D W, Rowe L A. Hierarchical storage management in a distributed VOD system. IEEE Multimedia, 1996,3(3):3747
6,¸,.һֲ֧Ķýϵͳ.ѧ,1997,8(5):327334
(Wu Fei, Chen Fu-jie, Wang Pu. A multimedia service system supporting parallel streams. Journal of Software, 1997,8(5):328334)
7Ramakrisna Karedla, Love J S, Wherry B G, Cacheing strategies to improve disk system performance. IEEE Computer, 1995,27(3):3846
1998-01-22յԭ,1998-05-04յ޸ĸ
