（控制科学与工程专业论文）集群式视频点播系统的存储调度分析与设计.pdf

a b s t r a c t r e c e n ta d v a n c e so fc 0 m p u t e r n e t 、7 l r o r | 【s t e c h n o l o g y h a v em a d e d o n d e m a n dp o s s i b l e a sv o da l l o w su s e r st 0s e l e c tt h ev i d e oi 赶b r m a t i o n a c c o r d i n gt o t h e i ro w ni n t e r e s t ， i th a sb e e na p p l i e di nm a n yf i e l d ss u c ha s e n t e r t a i n m e n t ，e d u c a t j o n ，a d v e n i s e m e n t ，a n de t c a st h es c a l eo fa p p l i c a t i o na n dt h e n u i i i b e ro fu s e r si n c r e a s e ，t h ev i d e os e r v e r sa i l dt h en e 咐o r ka r eb e 砥n gm o r ea n d m o r eb u r d e n i n0 r d e rt oe n h a n c et h ec o n c u r r e n tp r o c e s s i n ga b i 王i t ya n dt oe 虢c t i v e l y u t i l i z et h en e t 、v o r kb a n d w i d t h ，m o s tv i d e os e r v e r sa d o p tt h ec l u s t e r e ds t m c t u r e ht h ec l u s t e r e dv o d s y s t e m ，t h ew h o l es e r v i n gs y s t e mc o n s i s t so fas e r i e so f c o n c l l r r e n ts t o r i n 2n o d e sa n dd i f f e r e mv i d e o sa r es t o r e d0 nd i 虢r e n tn o d e s w h e na u s e rr e q u e s ta r r i v e s ，t h es y s t e ms e l e c t sa na v a i l a b l es e r v e rn o d et os e r v et h eu s e ru s i n g ac e r t a i ns t r a t e g y ；au s e rr e q u e s ti sr e j e c t e do n l yw h e na l lt h ep o s s i b l es e e r s a r e u n a v a i l a b l e 舢d i 骶r e n tv i d e o sh a v ed i 骶r e n td e m a n dp r o b a b i l i t y ，i fn 0s u i 龇l e s t o r i n gs t r a t e g yi sa d o p t e d ，t h el o a d s0 ft h es e r v e r s w o u l db eu n b a l a i l c e dc a u s i n gt h e n o d e ss t o f i n gh o tv i d e o so v e r l o a dw h i l eo t h e rn o d e ss t a r 、，i n g ，r e s u l t i n g i nl o w e f e e c t i v e n e s so ft h ew h o l es y s t e ma n dw a s t eo fn e t w o r l 【b a i l d w i d t h i h e r ea r et w ot r a d i t i o n a lm e t h o d si ns 0 1 v i n gt h ed e m a n d i n gs k e w n e s so ft h e v i d e o s ：r e p l i c a t i o na n ds t r i p i n g s t r i p i n gs p l i t st h es e r ，i n gt a s k s t od i 珏e r e n ts e r v e r sb y s t r i p i i l gav i d e oi n t os m a l l e rs e g m e n t sa n ds t o r e st h e mo n t 0d i f i e r e n ts e r v e rn o d e s ， t h u ss o l v e st h es k e w n e s sb e t w e e nv i d e o s h o w e v e f ，t h et r a d i t i o n a ls t r i p i n gs t r a t e g y f a i l st oc o n s i d e rt h es k e w n e s sw i t 王l i nas i n g l ev i d e o ；i tb r i n g sn e wp r o b l e m st ot h e n l a t t e ra si ts 0 1 v e sa no l do n e n i sp a p e ri n t r o d u c e dt h eh i s t o r ya n dr e c e n ta d v a n c e si nv o d r e l a t e dr e s e a r c h ， d i s c u s s e dt h es t o r a g e & s c h e d u l i n ga l g o r i t h ma n dd i s ks c h e d u l i n ga l g o r i t l l i i l ，a sw e l l a st h es e i n gs t r a t e g ya n dt h et r a n s p o r tp r o t o c o lo ft h es t r e a mm e d i a 。i nt h ep u r p o s e 0 ff i x i n gt h ed e f e c to ft h et r a d i t i o n a ls t r i p i n ga l g o r i t h m ，t h ea u t h o rp r o p o s e dar e v i s e d s t o r a 寥s c h e d u l 证ga 1 9 0 r i t h ma i l di l l u s t r a t e di t sd e s i g i la n d t h eu s e rb e h a v i o rp a t t e m t h ea l g o r i t h mi sb a s e do n as i m u l a t i o nw a sc a r r i e do u t t od e t e n n i n et h en e w a 1 9 0 r i t h m sa c t u a le 虢c t so nt h es y s t e m sp e r f 0 册a n c eb y t h em e a n s0 fc a l c u l a t i n gt h e l o a db a l a n c es t a t u sa n dt h ea c c e p tr a t i oo fu s e rr e q u e s t s t h el a s tf e wc h a p t e r so ft h i sp a p e rd i s c u s s e dt h ei m p l e m e n t a f i o ni s s u e so f a b s t 糟c l s t o i a g es c h e d u l i n gs y s t e m ，t h ea u t h o ra n a l ) r z e dt h ef h n c i i o no ft h em o d u l e si nt h e s y s t e ma n dp r o v i d e da n0 u t l o o ko nh o w f u t u r ew o r kc o u l db eo r i e n t e d k e yw | o r d s ：v i d e oo nd e m a n d ( v o d ) ，c l u s t e r e ds y s t e m ，s t r e a m i n gm e d i a ，s t o r a g e s c h e d u l i n g ，l o a db a l a n c e 论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工 作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包 含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对 本研究所做的贡献均己在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即： 学校有权按有关规定向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 保密的学位论文在解密后也遵守此规定。 作者签名：无飞 护璋g 月括日 磊够 第1 章绪论 家给予资金上的帮助。i n t e m e t2 首先致力于扩容，也就是增加带宽，扩充网络负 载能力。1 1 1 t e m e t2 不是目前的i n t e m e t 的简单升级，它要创造一个全新的程序系统， 从根本上改变互联网的承受能力。新的信息高速公路将建立在h l t e m e t2 的基础 上，它将彻底改变现阶段网上“交通堵塞”的状况，在真正意义上实现电子商务。 在西雅图群英会上，h l t e m e t2 的模式己经基本确定，远程教学、终生受教等方面 甚至已经变成现实。微软、3 c o m ，c i s c 0 等公司都积极地参与到h l t e m e t2 的研究 与开发中。 视频点播o dv i d e oo nd e m a n d ) 系统是计算机网络技术，通信技术，多媒 体信息处理技术、分布计算技术、数据压缩技术等众多技术相结合的产物。它将 远程视频服务器上的媒体信息，通过计算机网络或其他通信设施传送到本地的媒 体处理器或终端上，用户可以在电视机或p c 上随意点播自己喜爱的视频节目， 并可以控制节目的暂停、快进、倒退，循环等，就像控制自己家庭的v c d 或者 d v d 播放器一样。v o d 的实质是信息使用者根据自己的需要主动获得多媒体信 息，他和信息发布和广播的区别在于主动性和交互性。这种信息服务方式符合人 们对信息资源更深层次的需要，他改变了广播式的被动灌输方式。由于它打破了 以往传统的影音服务的局限，提供给用户更多地主动性，因此，近年来得到了非 常广泛的应用。 视频点播技术是在电脑多媒体技术、通信的分组交换技术、数字和光纤传输 技术日益成熟的条件下发展起来的。电脑技术的进步，尤其是w e b 技术的发展， 改变了信息基础设施的结构，包括信息的生成、存储、传送和表现形式等方面。 现在，文本、图像连同窄带视频信号已数字化，并通过网络存储、传送和再现； 但是，这些传统手段不能充分满足当今社会对高质量、连续多媒体( 如高保真音 频和电视质量视频) 的应用需要。 校园多媒体网络教室：课堂上的教师可以根据需要，随时随地在教学中点播 与课程有关的视频课件以增强教学直观感，丰富教学内容。在课余时间学生可以 自由选取视频课程节目进行预复习，以增强学习兴趣，提高教学效率。 多媒体图书馆：将视频资料分类，提供视频资料自由选取预览、索引查询、 分类管理等功能。 企业内部培训：提供教材管理、线上随选阅览、完成自我训练目的，提高员 工技能，增强公司的员工素质优势 多功能网吧：在原有网络结构上增加电影、广告、m t v 等影片视频节目服 务，可拓宽营业项目。 k ，点歌：实现无人d j 室，降低人工管理成本。统一存储，没有重复歌曲。 点歌迅速，热门歌曲不用等候。 第2 页 第1 章绪论 互动式导览展示系统：适用于百货公司、机场、火车站、剧院和博物院等公 共场所，作为产品讲解说明、服务内容介绍、环境导览、操作演示等目的。 宾馆饭店：可以将一些经典影片、卡拉o k ，菜单等节目加入到视频节目库 中，伎入住客人在自己客房中根据兴趣和时间，任意点播喜欢的内容。甚至可以 将客人关心的当天时事新闻、财经报道等电视节目加入到视频库，使客人在错过 节目播放时间的情况下仍可收看到想看的节目。 住宅小区：为小区提供新的服务内容，住户在家中可以点播电视节目、精选 影片或卡拉o k 伴唱等。可以丰富家庭文化娱乐生活，完善小区的服务。 v o d 系统覆盖广泛的领域，如影视点播、卡拉0 k 、远程教学、公司培训、 广告亭、智能小区等。同时，将这样的媒体引入信息基础建设对电脑研发带来了 新的挑战，因为他们自身的固有属性，包括对流量数据存储和连续播放的需要。 他们需要大容量存储设备，需要宽带网络环境，最主要的是必须确保实时传输。 传统的技术不能满足严格的实时性和大容量需要，其技术瓶颈特别反映在网络带 宽、文档系统和存储设备i o 性能这3 个方面。为此，许多解决方案应运而生，其 中一些方案使用专用硬件平台或终极电脑作为多媒体服务器。然而，依赖硬件解 决方案不但代价昂贵，而且会给今后的扩展、升级和维护带来问题。另一些方案 则以低带宽连接为目标，用于传送低质量、小屏幕的视频内容，例如，我们通过 拔号上网收看的一些“节目”，这些方法只能局限于某些应用，无法确保高质量视 频点播的需要。 1 1 2 流媒体系统 目前在网络上传输音视频( a ) 等多媒体信息主要有两种方案：下载和流 式传输，由于网络带宽的限制、a 文件所需的存储容量大，采用下载方式需要 的时间很长。流式传输则把声音、影像或动画等到信息由音视频服务器向用户计 算机连续、实时传送，用户不必等到整个文件全部下载完毕，而只需经过几秒的 启动延时即可进行播放，当音频、视频等媒体文件在客户机上播放时，文件的剩 余部分将在后台从服务器内继续下载。流式传输不仅使启动延时成十倍、百倍地 缩短，而且不需要太大的缓存容量。 流媒体指在i n t e m e 恤t r a n e t 中严格按时问先后次序传输和播放的连续音视 数据流。流媒体具有三个特点：连续性( c o n t i n u o u s ) 、实时性( r e a l t i m e ) 、时 序性( i m e o f d e r e d ) ，即有严格的前后时序关系。与传统的多媒体文件下载后 播放的方式不同，流媒体在播放前并不下载整个文件，只将部分内容缓存后，流 媒体数据流随时传送随时播放。 流媒体技术所提供的播放功能、交互性能和缓冲区功能，以及其在传输声像 第3 页 第l 章绪论 文件时表现出的“占用硬盘小、速度快、高保真”等性能，使得网上收听广播、收 看实时电视广播进入实用阶段。流媒体服务系统在强调对数据对象的共享使用和 追求最大化的数据吞吐率的同时，更强调对高速、稳定和连续的访问流支持，强 调对同步的支持，从而确保媒体数据的按时到达。 流媒体技术能够广泛应用于多媒体新闻发布、在线直播、网络广告、电子商 务、视频点播、远程教育、远程医疗、网络电台、实时视频会议等，它丰富了传 统互联网内容的表现形式，赋予宽带应用更多的娱乐性和互动性。流媒体技术必 将成为未来宽带网络业务的主流技术。实时性和质量是流媒体的关键问题。为了 保证时延和质量，网络必须提供足够的带宽资源，而资源的保证又依赖于许多其 他的控制，如流量控制、拥塞控制等。当网络资源变化时，还必须能够适应这种 变化并做出相应的调节。 1 1 3 存储调度研究的意义 v o d 系统所传输的数据主要是视频和音频数据，这些数据同传统的文本和 数字数据有着很大的不同( g e m m e l l ，1 9 9 5 ) 。首先，音视频文件通常被称为“连 续媒体”，也就是说他们是由连续的数据单元所组成( 比如视频帧或者声音采样) ， 而且通常也都是按顺序为用户服务( 虽然用户也可能会暂停、快进或者快退，但 是这些操作同传统媒体相比，概率要低很多) 。相比之下，文本和数字数据则会 经常出现随机访问。其次，多媒体数据通常含有非常大的数据量。一个普通质量 的1 0 分钟的视频流在没有经过压缩的情况下需要1 5 g b 的存储空间。即使是经过 压缩，他也需要1 0 0 6 0 0 m b 的存储空间。下表列出了常见的多媒体数据所需要的 存储空间。 媒体类型数据速率 语音级别音频单声道，8b i t8 k h z 采样率 6 4 l a b p s m p e g 编码音频c d 音质音频3 8 4 l ( b p s c d 音质音频双声道，1 6b i t4 4 1 k h z 采样率 1 4 m b p s m p e g 2 编码视频 0 4 2m b p s n ，r s c 视频 2 7 枷b p s 6 4 0 4 8 0 分辨率，2 4 位色 珈时v 视频 1 2 8 0 7 2 0 分辨率，2 4 位色 8 1m b p s 表1 1 常见多媒体数据所需存储空间 第4 页 第1 章绪论 由于视频对象的巨大存储要求和有限的存储空间，每个服务器都只能存储有 限数量的视频流。而且，由于i o 服务带宽的限制，每个服务器可以同时传输的 视频流数量也是有限的。因此，视频文件的存储调度涉及到视频文件在服务器上 的合理放置和不同服务器的负载均衡，只有进行合理的存储调度才能提高资源的 使用率，提高真个系统的性能。 1 。2 研究现状 1 2 1 v o d 系统分类 v o d 系统可以分为两大类：单服务器结构和分布式结构。 单服务器的优点是实现和管理非常简单，一般小型的v o d 系统多用此种结 构，其服务器可以采用普通的p c 也可以使用功能稍强的小型机。但是单服务器 结构的v o d 系统存在着很多难以克服的局限性。其中最突出的一点便是服务器 的服务能力和容错性。单服务器的c p u 处理能力和存储容量等都非常有限，而影 片文件所需要的存储空间是巨大的，在这样的情况下，单服务器系统就的存储影 片数量和并行服务用户数都有很大的局限。另外，由于只有一个服务器，一旦服 务器出现故障，将会影响整个系统的运行，导致系统瘫痪。 分布式结构与单服务器系统的不同之处，在于视频文件存储于不同的服务器 上，点播压力和存储压力被很多服务器所分担，同时也避免了服务段的网络带宽 瓶颈，提高了系统的容错性能，即使一个服务器出现故障，也不至于影响到整个 系统的运行。目前大规模的v o d 服务系统都采用了分布式结构。 分布式系统的研究主要需要解决以下几个问题： 存储空间的有效利用问题，影片文件占用的存储空间非常巨大，如何合理安 排影片在各个服务器上的存储，才能有效利用各服务器的空间是一个研究问题 ( b u 觑c k ，1 9 9 6 ) 。当然，目前存储设备的容量不断增加，成本不断降低，这个 问题已经不是很突出。 负载平衡问题。某些新片可能会在一段时间内非常流行，被用户大量点播， 形成点播高峰；而另外一些相对冷门的影片的点播率则比较低，如果不能对点播 请求进行合理的调度，就会造成某些服务器不堪重负而另外一些服务器却几乎空 载的情况，造成服务资源的浪费( s e r p a n o s ，1 9 9 6 ；w 0 1 f ，1 9 9 7 ；t s a o ，1 9 9 9 ； g o l l z a l e z ，2 0 0 2 ；s h u ，2 0 0 5 ) 。 容错能力问题。v o d 系统中的某些服务器可能会因为软件或者硬件的故障 而不能正常工作，v o d 系统应该在不影响客户端的情况下，将故障服务器的工 第5 页 第1 章绪论 作交由剩下的正常服务器分担( a n k e r ，1 9 9 9 ；v i n ，1 9 9 5 ；g o l u b c h i k ，2 0 0 1 ) 。 1 2 2 视频流的存储 视频流的存储是将系统中的所有视频按照一定的策略放置到系统中的各服 务器中去。如果有一个良好的放置策略，就会给系统的负载均衡带来很大的方便。 如果我们不考虑当用户被服务的时候交换对其进行服务的媒体服务器，那么 我们就应该在分配视频文件的时候使得每个服务器都有相同的被请求的概率。通 常有两种方法来达到这种平衡，也就是复制和分条，另外也有学者将两者结合起 来提出了分组分条的策略。 复制策略是通过将某些热门影片在不止一个服务器上保存副本，来实现负载 在各个服务器上的均衡的。复制策略的典型代表是s e 甲a i l o s 等( 1 9 9 6 ) 提出的一 种被称为“m m p a c l ( i n g ”的算法。在m m p a c k i n g 中，视频流根据其点播概率以升序 排列，从点播概率最低的影片开始，以轮询的方式放置到每一个视频服务器上。 当一个视频流被分配到多媒体服务器上的时候，就计算该服务器的累积的被请求 概率。如果概率高于平均请求概率( 也即是1 n ，当服务器数为n 时) ，就对当 前的视频流生成一个副本放置到下一个服务器上。复制的缺点之一在于它的容 量。整个影片副本都放在一个服务器上，服务性能就受到了单盘i o 带宽的限制。 当需求超过了服务器的服务能力的时候，就需要将影片复制到其他磁盘上，增加 了系统的容量要求。也有一些学者提出了减少存储浪费的算法，这些算法都是基 于存储容量和带宽相同的服务器的( b i s d i l 【i a n ，1 9 9 5 ：v c n k a t a s u b r 锄a n i a n ， 1 9 9 7 ) 。复制通常用在各视频服务器距离较远，难以采用分条策略的分布式v o d 系统中。 分条策略的最初想法是使用磁盘冗余阵列( 鼬虹d ) ，将一部视频分成多个 块分别存储到所有的服务器中( t e w a r i ，1 9 9 5 ；t e w a r i ，1 9 9 6 ；b o l o s k y ，1 9 9 6 ) 。 这种架构下的v o d 系统被称为并行视频服务器( k e ，1 9 9 8 ) 。分条可以将数据 透明地分布到多个磁盘中，而让用户感觉自己是在使用单一的快速磁盘。用户请 求造成的负载被均匀分布到整个磁盘阵列中，很好地消除了影片之间热度不均对 负载均衡造成的不良影响。然而，在不同的分条服务器之间同步确是一个难题。 由于网络延迟、调度等原因，不同的服务器可能会在不同的时间开始数据传输。 第一个分条数据甚至可能会在其他分条到来之后才姗姗来迟。由此造成了客户端 必须缓存一部分乱序的数据并且等待第一个分条数据，造成了开始播放的延迟。 分组分条将纯粹的分条策略和复制策略结合起来。每个媒体服务器都有一部 分分条设置，而同时也根据预测的用户请求概率将某些最热门的影片副本复制到 服务器中。在这种算法下，媒体服务器也被称为“分条磁盘组”( d i s k s t r i p i n g 第6 页 第1 章绪论 g r 0 叩d s g ) ( w b l f ，1 9 9 7 ) 。一些学者基于这种思想提出了在媒体服务器之间达 到静态负载均衡的算法( w r o m1 9 9 7 ；t s a o ，1 9 9 9 ；j g u 0 ，2 0 0 3 ) 。 1 2 3 服务器间的负载均衡 视频文件在媒体服务器之间的复制可以实现实时负载迁移，达到负载均衡。 w o l f 等( 1 9 9 7 ) 提出了d a s d 跳舞算法来通过负载迁移平衡服务负载。t s a o 等 ( 1 9 9 9 ) 提出了分布式v o d 系统动态负载均衡的连接优化算法，他们的算法通 过使个服务器的被访问概率相等来达到负载均衡的目的。y 。g u o 等( 2 0 0 3 ) 提出 了基于视频复制的组合式负载均衡( c o m b i n a t i o nl 0 a db a l a n c i n g ，c l b ) 来降低 用户请求的拒绝率。这些算法都是在服务器负载超过一定的阀值或者用户请求被 拒绝的时候来进行请求迁移。但是，在某些影片热度极度不均的系统中，某些媒 体服务器可能已经达到负载上限而不能继续接受任何用户请求的迁入，这样就可 能导致增加用户初始播放延迟或者用户请求被拒绝。 1 。2 4 动态内容更新策略 由于分布式v o d 系统的服务器连接在广域网中，因此用户请求模式会随着 时间推移而发生变化。视频在各服务器上的副本需要定期进行动态更新以防止系 统过于臃肿或者降低效率。r a d o s l a v o v 等( 2 0 0 1 ) 提出了一种简单但是有效的基 于服务器连接度的初始放置策略，这种策略仅考虑静态放置。当用户请求模式随 着时间发生改变，这个系统不可避免地效率降低。r a b i n o v i c h 等( 1 9 9 9 ) 研究了 动态对象复制技术，在他们的研究中，视频对象的大小通常都是几k b 大小，而 服务时间则可以忽略不计。y g u o 等( 2 0 0 3 ) 研究了集中式v o d 系统的动态内容 重分布问题。 1 3本文研究的工作 在大规模v o d 集群系统中，由于影片的热度不均造成的各服务器之间的负 载不均衡的情况一直是学者们研究的课题。对于这个问题一般有两种解决方法， 一种是复制，另一种是分条。由于视频数据的数据量通常十分庞大，因此，复制 的策略对存储空间造成的浪费是显而易见的。分条的技术应用在了很多公司的服 务器产品中，但是分条的技术也有其缺陷性。其中一点即是影片的内热度不均所 带来的问题。 由于用户在点播影片的时候并不总是从头观看到尾，很有可能会出现中途中 第7 页 第1 章绪论 断点播的情况。甚至有研究表明( 吴松，2 0 0 6 ) ，很多用户会在点播的前5 分钟 内中断点播。因此，影片的各个部分被观看的概率实际上有着很大的差距。影片 开头的部分比影片末尾的部分有着高得多的被访问概率。传统的分条方式将影片 各部分均匀分条存储到各服务器中，很好地解决了影片间热度给负载均衡带来的 不利影响，但是却因为影片内热度的原因带来了新的问题。 本文通过研究用户的访问行为模式，提出了影片内热度的研究模型，并根据 该模型提出了改进的分条存储策略。同时，通过对系统的仿真模拟，得出了评估 系统性能的一系列参数。 1 4 本文内容安排 本文主要研究了v o d 系统中的存储调度相关问题，讨论了在有限的服务资 源条件下，如何通过对资源的合理分配和调度来达到服务器之间的负载均衡，提 高系统性能，以服务更多的用户。针对当前存储调度的研究，讨论了v 0 d 系统 中的各相关技术，集中分析了用户在视频点播时候的行为模式对负载均衡的影 响，并提出了新的存储调度策略，以及讨论了存储调度系统在工程上实现的问题。 本文的具体内容安排如下： 第一章讨论了本文研究的背景和意义，概述性地介绍了视频点播和流媒体系 统的基本概念和主要特点。简述了国内外的相关研究情况，当前视频点播的研究 热点问题。并且概述了本文作者所研究的工作。 第二章介绍了视频点播的相关技术。首先概述了流媒体服务系统的技术问 题，由于基于集群技术的视频点播系统正受到越来越多的关注，首先介绍了计算 机集群技术的发展和应用；接着介绍了v o d 系统架构的问题，形象说明了v o d 系统的结构组成和各部分关系。接着讨论了视频文件的存储调度算法和磁盘调度 算法问题以及请求分配与迁移。介绍了两种视频流服务策略：客户拉和服务器推 的策略，目前这两种策略都有着广泛的应用。同时简要介绍了交互式v o d 的发 展和特征，目前交互式v o d 是研究的一个重要方向。本章最后介绍了流媒体传 输的协议，r 仰协议是最适合于进行流媒体传输的协议，因此对其进行了介绍。 第三章讨论了流媒体服务系统存储调度的相关问题。首先分析了用户行为模 式由于用户的行为模式引起的影片间热度不均和影片内热度不均问题。接着讨论 了文件的分割与服务拒绝率的问题，通过从特殊到一般的方法得出了文件分割与 服务拒绝率之间的量化关系。视频文件的复制和分条是常见的两种抑制文件间热 度不均对负载均衡影响的策略，本章也对它们进行了介绍。接下来详细介绍了改 进的磁盘调度策略，改进的策略针对影片内热度不均进行了处理和分析，以最大 程度消除影片内热度不均给传统分条技术带来的局限性。本章最后讨论了对应于 第8 页 第1 章绪论 改进系统的仿真模拟试验的设计思想，并且根据试验结果分析了改进的策略对系 统性能的影响。 第四章讨论了存储调度系统在工程上的实现问题，分析了存储调度系统的设 计实现上的相关问题，讨论了存储调度各模块的功能和算法流程。 第五章对本文的内容作了总结，并且对以后可以进行的相关工作进行了分析 展望。 第9 页 第2 章视频点播技术概述 第2 章视频点播技术概述 2 1流媒体服务系统 2 1 1 计算机集群技术 分布式流媒体服务器一般采用松藕合的集群结构。虽然采用m p p 结构的集中 式流媒体服务器由于其技术成熟性己得到广泛的应用，集群结构的分布式流媒体 服务器却正在获得越来越多的关注。这是因为基于集群的系统有如下优势： 系统有极强的扩展性。从单台p c 机或工作站，到数百个节点的大规模服务 器，集群结构几乎可以满足所有层次的需要。它既能保证原有投资，又能随意扩 充系统规模。相反，利用传统的高档服务器，一开始就意味着很高的投入，且其 扩展性方面不如集群系统灵活。 集群系统有潜在的容错性。多个在物理上松散耦合的部件，很容易做到故障 隔离，即单个部件的故障不会波及系统其他部分，利用软件，可以使任务平滑地 从一台机器迁移到另一台机器。 较高的性价比。集群系统往往由普通工作站或p c 机构成，这类机器由于其 大规模应用背景，成本已经非常低。一个集群系统和一台同等计算能力的高档服 务器相比，价格相差巨大。 基于集群系统的流媒体服务器已成为许多公司和科研机构的研究热点。现在 已经提出了许多种设计方案，目的都在于如何最大程度地发挥多机效率，以支持 大量用户的并发访问。在这种流媒体服务器中存在两种基本类型的节点，交互服 务节点( a c c e s ss e r v e rn o d e 以下简称为a s ) 和存储服务节点( s t o r a g es e r v e r d e 以下简称为s s ) 。当用户希望使用流媒体服务时，他必须首先和a s 建立连接。a s 通过准入控制功能决定是否接纳用户请求，如果请求被接纳，那么a s 将向用户 发送用于后续流媒体服务操作的必要信息。s s 用于存储流媒体数据信息，通常 采用数据分块方法。s s 可以装备多个磁盘或其它存储设备，也可以使用s a n 结 构，所有的s s 节点构成流媒体服务器的存储子系统，用户请求的流媒体数据从 存储子系统中读出，经过a s 转发或直接传送给用户。 第1 0 页 第2 章视频点播技术概述 2 1 2v o d 系统架构 v o d 系统中的多媒体服务器基本上可以分为两种类型：集中式结构和分布 式结构，如图1 1 所示 甩户照户用户甩户 ( a ) 服 高速交换网 。+ ：_ 广域旷一1f ? 0 = i ，菇磅幺么* 、，j 茹j 旃0 甩户甩户甩产甩产 ( b ) 图1 1 v o d 系统配置( a ) 集中式结构 ( b ) 分布式结构 在集中式结构中，一个服务器( 被称为调度服务器) 接受到来的点播请求并 且将其发送给存储服务器。调度服务器提供所有的管理任务例如准入控制，用户 请求调度和视频流分配。磁盘存储服务器仅完成相应的i o 服务，并不参与任何 决策任务。 另一种结构则是分布式结构，如上图) 所示 在这种架构中，调度器被分布在每个磁盘服务器中，每个磁盘服务器都同时 运行着管理功能和数据传输功能。磁盘服务器通过高速交换网络进行互联，以将 整个系统的请求响应延时降低到最小。 第l l 页 第2 章视频点播技术概述 集中式 分布式 请求调度容易 复杂 容错性 容错性差 更可靠 系统准入单一 安全 比较复杂 授权机制简单 扩展性整个系统嵌入l a n 具有扩展性 可以采用分布式数据库 维护，计费简单 管理技术 表2 1 集中式和分布式结构的比较 另外一种v o d 系统架构是在系统设计中加入一种分层的机制。如前所述， 多媒体对象通常具有很大量的数据并且需要很高的带宽，v o d 系统需要支持上 千个并发视频流的请求，为了能够达到这个目标，多媒体服务器需要同时具有大 的存储容量和大的服务带宽。服务器可能同时具有不同种类的存储设备。磁带和 光盘存储设备具有很大的存储容量，但是只有非常有限的带宽。磁盘的存储容量 相对较小，但是有着高得多的服务带宽，因此可以用来作为磁带的缓存而直接为 用户请求服务。 同时，还有一种研究方向是将分层机制和分布式结合起来。在b e r k e l e y d i s t r i b u t e ds y s t e m ( v d s m ) 中，f e d e r i 曲i 等( 1 9 9 4 ) 使用了一种集中式的存储系统 作为备份服务器，同时在客户端布置分布式视频文件服务器( v i d e of i l es e r v 铘) 。 当一个客户端的请求到来的时候，视频文件服务器首先检查它是否有缓冲的视频 流，如果有了缓冲，视频流就可以马上被播放而无需向存储服务器索要数据。这 种设计思想包含了用户进入s e r a c c e s s ) 的特征。 2 1 3 视频文件的存储调度算法 v o d 系统需要将视频文件缓存到它的存储设备中并且对网络中的多个用户 提供基于点播的多媒体流服务，在多种存储设备中，磁盘或者磁盘阵列因为具有 相对较高的输出带宽和较低的单位成本，通常被用来提供实时服务。因此，这里 讨论的存储设备都是指硬盘。v o d 的目标只是将对当前服务用户的中断和对用 户请求的拒绝降低到最小。这就意味着多媒体服务器需要进行某种程度的资源保 留从而保证实时流传输的定时发送( r a n g a i l ，1 9 9 2 ) 。而资源保留则意味着每 个磁盘的可服务用户数将被限定在有限的数目之内，同时，每个磁盘也只能保持 有限数量的视频流。因此，视频内容的分配问题就有着重要的意义，在v o d 系 统的设计中必须得到妥善的解决。 如果我们不考虑当用户被服务的时候交换对其进行服务的媒体服务器，那么 第1 2 页 第2 章视频点播技术概述 我们就应该在分配视频文件的时候使得每个服务器都有相同的被请求的概率。通 常有两种方法来达到这种平衡，也就是复制和分条。 对于不同的视频流有不同的用户请求概率，经常被请求的影片( 热门影片) 需要有比相对较少被请求的影片( 冷门影片) 更多的副本。一种方法是将整部影 片放入其中一个服务磁盘并在其它的磁盘中分配静态副本。这一方法被称为复 制。s e r p a n o s 等( 1 9 9 6 ) 提出了一种被称为“m m p a c k i n g ”的数据复制策略来同时 达到存储和负载的均衡。在m m p a c k i n g 中，视频流根据其点播概率以升序排列， 从点播概率最低的影片开始，以轮询的方式放置到每一个视频服务器上。当一个 视频流被分配到多媒体服务器上的时候，就计算该服务器的累积的被请求概率。 如果概率高于平均请求概率( 也即是1 n ，当服务器数为n 时) ，就对当前的视 频流生成一个副本放置到下一个服务器上。这部影片的被请求概率是两个副本的 请求概率之和。这个方法有两个问题。首先，系统分配到每部影片的出口带宽非 常有限。第二，生成副本的过程是一个及其消耗时间和存储空间的过程，因此在 v o d 系统中不宜采取。在数据分配中很少用到纯粹的复制策略。 r a i d ( r e d u n d a n ta r r a yo fi n d e p e n d e n td i s k s ) 独立磁盘冗余阵列使得地盘 阵列的并行操作变得流行( p a t t e r s o n ，1 9 8 9 ) 。在七个不同级别的凡u d 中，r 趟d 3 和i 5 被用在v o d 系统中。3 使用细致分条来服务用户请求。对于容错 性，r 趟d 3 使用单奇偶校验磁盘，根据故障磁盘的相关信息来恢复数据。在 u d - 5 中，数据在磁盘中以对固定大小的块来分配，被称作粗块分条。不同于 r m d l 3 ，r a i d 5 在集群中的每个磁盘都有奇偶校验和数据统一性检查，不像 r a i d 一3 那样造成单一奇偶校验磁盘的读写负担过重。下图显示了r a i d 3 和 脚_ 5 中的数据存储模式。在大规模视频服务器中，凡u d 5 风格的粗带分条性 价比最高。 第1 3 页 第2 章视频点播技术概述 偶校验块 图2 1r a i d 一3 和r a i d - 5 的数据配置 视频数据的分条可以分为两种：时间分条和空间分条。在时间分条中，视频 流以帧为单位分条，每个条都有相同时间长度。分条的单位也可能包含非整个帧 的条，这被称为分帧分条。b i e r s a c k ( 1 9 9 5 ) 和b i s d j l 【i a n ( 1 9 9 5 ) 考虑了单帧分 条和分帧分条，并且得出结论，由于每个帧的数据都均匀地分布在每个服务器上， 分帧分条比单帧分条在固定比特率和可变比特率的情况下都具有更好的负载均 衡。b u d d i h l l i k o t 等人研究了时间分条中负载均衡和播放控制问题并提出时间分 条应该尽可能把每个分条中放入更多的帧( 比如m p e g 编码中同属于一个图像 组( g r o u p o f - p i c t u r e ，g o p ) 中的帧) ，尽量使得每个分条都具有相近的大小。时间 分条的好处是简化了客户端的缓冲设计，因为每个服务器在一个服务周期内都发 送相同时间长度的数据。而时间分条最大的缺点则在于其难以使得所有服务器的 负载都保持均衡。 和时间分条不同，空间分条将一个视频流分成相同大小的数据块，并且将他 们通过一定的策略分配到服务器中。空间分条简化了服务器端的存储和缓冲管 理，而且可以达到服务器间最佳的负载均衡。但是对于以压缩方式存储的视频流 第1 4 页 第2 章视频点播技术概述 ( 比如m p e g ) 来说，一个数据单元可能会包含不同数量的帧或者不完整的帧。 即使视频以固定输出质量算法来压缩，每个单元的数据输出率也有可能不同。必 须考虑采取在客户端使用空间分条缓存来防止客户端的播放饥饿( p l a y b a c k s t a r v a t i o n ) 的问题。时间分条和空间分条技术在大多数研究中都被广泛应用。 ( f 。r e e d m a n ，1 9 9 5 ：b u d d b i k o t ，1 9 9 5 ；t e w a r i ，1 9 9 6 ；b o l o s k y ，1 9 9 6 ；b e m h a r d t ， 1 9 9 6 ) 还有一些学者提出分组分条策略，同时具有数据复制和分条的两种特点。磁 盘备份为几个分组，某个分组中使用纯分条，而数据复制技术则应用在其它分组 中。 以上的算法都旨在平衡磁盘服务器之间的存储并且尽最大努力去服务用户 请求。然而，他们却没有考虑用户请求模式。在某些情况下，用户请求的模式是 已知的或者可以预测的。更好的方式是将这些信息加入数据放置策略中。 2 1 4 磁盘调度算法 为了保证流媒体播放的连续性，每个服务周期客户端得到的数据都必须包含 足够的信息，以避免传输过程中出现播放饥饿现象。磁盘调度策略有：先来先服 务( f i r s tc o m ef i r s ts e r v ef c f s ) 最小查找时间优先( t h es h o r t e s ts e e kt i m e f i r s t ) 和轮询策略( s c a n ) ，和分组轮询( g r o u p e ds w e e p i n gs c h e d u l i n gg s s ) 这些策略可以减小查找时间和服务延迟以及使服务器之间有相近的访问率。 第1 5 页 第2 章视频点播技术概述 延迟 ( 1 ) f c f s l 团l 圈l 圈l 缓存大小 一般，( 2 ) s c a n i 圈i嘲 l ? ? j ? 缓存大小 ( 3 ) g s s 一延迟争一分组一 圆圈圆一i 缓存大小 图2 2 磁盘调度算法： ( 1 ) f c f sc 2 ) s a 埘( 3 ) g s s 我们从上图可以看出，每请求的最小缓冲大小等于播放速率和周期长度的乘 积。 在f c f s 中f c f s 顺序在每个周期中是固定的。数据一旦到来就可以让请求 马上得到服务。在s c a n 中，由于服务顺序并不固定，请求必须等到每个周期 的结束才能被服务。在最坏的情况下，被请求的数据在第一个周期的开始就已经 到达，而请求在下一个周期开始才被服务。从周期长度来看，f c f s 的周期长度 比s c a n 长，这是由于f c f s 并没有考虑个磁盘上的视频流的具体分布。在s c a n 中，数据的获取时间与基位置到磁头的距离。因此，在每个服务周期，磁头都必 须从一端运行到另一端去读取整个数据。 y u 等( 1 9 9 2 ) 提出了一种被称为g r o u p e ds w e e p i n gs c h e d u l i n g ( g s s ) 的一般 磁头调度算法。在g