（计算机系统结构专业论文）基于linux的分布式vod系统服务器优化设计.pdf

两北t 业人学颂十学位论文：基于l i n u x 的分布式v o d 系统服务器优化设计 摘要 近年来，i n t e m e t 有了蓬勃的发展。一方面，主干网和接入网速率不断提高。 为各种宽带应用提供了必需的硬件基础设施：另一方面，越来越多的人愿意交互 式地观看音视频节目，这一切都为视频点播( r o d ) 技术的发展创造了良好的条 件。目前，v o d 在影视点播、远程教育和在线直播等众多领域显示出了广阔的 应用前景。 视频应用有广阔的市场前景，然而现有的技术和产品却不能满足大面积部署 并同时服务大量用户的应用需要。本论文的研究工作是在前期分布式v o d 原型系 统的基础上进行的，主要完成的工作包括： 第一，在现有研究成果的基础上选择并适当修改节目替换算法使之适合已 有的系统模型；根据原型系统中负载均锈方式所遇到的问题，提出一 种对于既定分布式v o d 系统模型更为合理的负载均衡策略。 第二，综述了在流媒体应用环境下，对操作系统可能采取的优化措施；确定 首先对文件系统进行优化。设计了针对l i n u x 的e x t 2 文件系统的改造 方案，提出基于“簇”的设计思想并应用于具体的设计，提高了其对 大文件的读写能力，增大了磁盘吞吐量。 第三，抽象出单线程任务调度模型，将此模型应用于视频服务器设计，降低 了多线程切换带来的额外开销；同时设计了与此模型配套使用的平滑 非阻塞的i o 系统。 论文工作致力于优化分布式v o d 系统的服务器部分，整个系统架构在l i n u x 操作系统之上，通过对l i n u x 的e x t 2 文件系统和服务器应用软件两个方面进行 优化，提高系统性能。 关键字： 分布式视频点播、替换算法、负载均衡、e x t 2 文件系统、任务调度 两北丁业人学硕士学位论文：基于l i n u x 的分布式v o d 系统服务器优化设计 a b s t r a c t t h ei n t e r n e th a sg r o w nr a p i d l yi nr e s e n ty e a r s t h eb a n d w i d t ho ft h en e t w o r k ， b o t hb o n en e t w o r ka n dt h el o c a la c c e s sn e t w o r k ，i sb e c o m i n gl a r g e ra n dl a r g e r , w h i c h p r o v i d en e c e s s a r yi n f r a s t r u c t u r e f o rb r o a d b a n da p p l i c a t i o n s m o r ea n dm o r ep e o p l e p r e f e rt oa c c e s si n f c l r m a t i o ni n t e r a c t i v e l y a l lo f t h e s ec r e a t ee x c e l l e n tc o n d i t i o nf o r t h ed e v e l o p m e n to ft h ev o d t e c h n o l o g y n o wv o dp r e s e n t ss t r o n gl i f e i nl o t so f f i e l d s ，s u c ho fm o v i e o nd e m a n d ，d i s t a n c ee d u c a t i o na n d l i v i n gb r o a d c a s t i n g v o dh a sl a r g em a r k e t ，b u tn ot e c h n o l o g ya n dp r o d u c t sc a l ls a r i s f yt i l en e e d so f s e r v i n gl a r g ea m o u n to f u s e r ss p r e a d i n ga r o u n da v e r yl a r g ea r e a t h i sp a p e ri n h e r i t s t h ee x i s t e dd i s t r i b u t i n gv o d s y s t e ma r c h i t e c t u r ea n dr e a c h e ss o m ea c h i e v e m e n t s f i r s t ，an o v e l t yr e p l a c e m e n ta l g o r i t h mi sc h o s e na n dm o d i f i e d ，t h u si tw o u l d a d a p tt os y s t e mm o d e lw h i c hh a sb e e nd e s i g n e d al o a db a l a n c es t r a t e g yf o rm e d i a s e r v e r sw h i c hs o l v e st h ep r o b l e m si ne x i s t e dp r o t o t y p es y s t e mh a sb e e np r e s e n t e d ， w h i c hi si nr e a s o nf o rd i s t r i b u t i n gv o d s y s t e m a r c h i t e c t u r e s e c o n d ，s o m ep o s s i b l eo p t i m i z em e t h o d sf o ro p e r a t i n gs y s t e mi ss u m m a r i z e dt o s u p p o r ts t r e a m i n gm e d i aa p p l i c a t i o n sb e t t e r , t h e nt h i sp a p e rd e c i d e st or e c o n s t r u c t o p e r a t i n gs y s t e m t h ed e s i g na i m i n ga tt h ee x t 2f i l e s y s t e mo fl i n u xi sp r e s e n t e d ， w h i c hi n t r o d u c e sad e s i g nt h i n k i n gb a s i n go n c l u s t e r ”t h er e b u i l d i n go f t h ee x t 2f i l e s y s t e mh a si m p r o v e d t h ea b i l i t yo f r e a d i n ga n dw r i t i n gh u g em e d i af i l e ，a n dh a sr a i s e d t h et h r o u g h p u to f t h ed i s k t h i r d ，as i n g l et h r e a d i n gt a s kp a r a d i g mi sa b s t r a c t e da n dh a sb e e na p p l i e dt ot h e d e s i g n i n go f t h em e d i as e r v e rf o rr e d u c i n gt h ec o s tw h i c hm u l t i t h r e a d i n gs w i t c h i n g b r i n g s ，a n das m o o t h i n g a n d n o n b l o c k i n gi 0s y s t e mi sa l s od e s i g n e d t h i sp a p e r a p p l i e si t s e l f t oo p t i m i z ed i s t r i b u t i n gv o d s e r v e r st h ew h o l es y s t e m c o n s t r u c t so nl i n u x ，a n di m p r o v e sp e r f o r m a n c et h r o u g ho p t i m i z i n ge x t 2f i l e s y s t e m a n ds e r e r a p p l i c a t i o ns o f t w a r e k e y w o r d ： d i s t r i b u t i n gv o d ，r e p l a c e m e n t ，l o a db a l a n c e ，e x t 2f i l es y s t e m ，t a s ks w i t c h i n g 西北工业大学硕士学位论文：基于l i n u x 的分布式v o d 系统服务器优化设计 1 1 课题背景 第一章绪论 电视以其及时、直观、形象生动、单位时间信息量大等特点，成为备受人们 欢迎的第一大媒体，同时，电视作为家庭娱乐的主要手段，在家庭生活中具有不 可替代的作用。但传统的电视系统是单向广播式的，人们只能被动地按时收看节 目。随着互联网和w e b 技术的发展，人们可以主动、及时地从互联网上获得所 需要的信息，包括多媒体信息，互联网逐渐发展成为继电视之后覆盖面最大的一 个新兴媒体1 1 1 。但受网络结构、网络带宽等因素的制约，人们获取的多媒体信息 目前也主要是文字、图片等静态信息。人们迫切需要能够像获取文字图片信息一 样，从网络上随时、主动获得自己所需的动态图像信息，观看视频节目【2 】。视频 点播( v o d ) 技术应运而生，国内外相继推出一些视频点播系统，但目前现有 的视频点播系统面临着造价高、节目存储容量及覆盖面小等众多问题，网络视频 服务应用一直难以真正发展起来。 课题组经过深入而广泛的研究，提出了一种由节目中心、点播中心及代理服 务器构成的分布式视频点播系统模型口】，以便可以有效的在大范围内部署。根据 这个分布式视频点播系统模型，2 0 0 1 年底课题组已经完成了系统结构设计【4 1 ，并 在j a v a 虚拟机环境下，编程实现了一个基本原型系统，通过大量的实际测试和 性能分析，系统性能已基本达到设计目标，取得了阶段性成果。我的研究主要是 在l i n u x 环境下对原型系统进行进一步的设计优化。 1 1 1 新的市场需求与网络基础 i n t e m e t 的迅猛发展和普及，为网上视频、音频业务的发展提供了强大的市场 动力，在不久的将来，这些技术将广泛地用于互联网多媒体新闻发布、在线直播、 网络广告、电子商务、视频点播、远程教育、远程医疗、网络电台、视频会议等 网络服务的方方面面，为网络应用带来革命性的变化，对人们的工作和生活产生 深远的影响。网络视频应用具有的良好市场前景和应用前景，主要体现在以下几 个方面： 1 ) 互连网用户快速增长及对视频服务的迫切需求 国外收视率调查权威机构尼尔逊( n i e l s e n n e t r a t i n g s ) 已发布的2 0 0 1 、 两北丁业大学硕j j 学位论文：基于l i n u x 的分布式v o d 系统服务器优化设计 2 0 0 0 年度统计信息指出”1 ，至2 0 0 1 年9 月时，约有2 1 0 0 万美国上班族使用视频 服务，视频服务的普及率将近5 6 ，较2 0 0 0 年9 月增长2 1 。截止2 0 0 1 年上半 年，在西方发达国家访问视频服务内容的人数已达到2 亿人，比2 0 0 0 年增加0 9 亿人；在亚洲也由2 0 0 0 年的2 5 0 0 万人迅速增加到3 5 0 0 万人，而且这些数据f 在呈几何级数的速度迅猛增长。 近几年中国互联网业飞速发展，中国互联网络信息中心( c n n i c ) 2 0 0 3 年1 月发前i 的第1 1 次中国互联网络发展状况统计报告显示“1 ：截止到2 0 0 2 年1 2 月 3 1 只，大陆地区的网民数最低已经达到了5 9 1 0 万，半年增长了1 3 3 0 万，增长 率为2 9 。其中宽带上网数已达到了6 6 0 万，半年增长了4 6 0 万，增长率为2 3 0 。 这些统计调务资料显示，视频服务技术拥有广火的客户群体，并且在快速的增长，为视频服 务技术的发展和市场前景奠定了坚实的基础。 2 ) 专用视频服务需求日益增长 不仅普通用户需求不断增大，行业用户需求也日益增长，目前很多单位已经 部署了这样的服务，例如c c t v 采用r e a l n e t w o r k s 公司的视频服务技术实现了 视听在线：湖南卫视采用n c u b e 公司的点播系统实现了视频点播服务；北京邮 电大学采用c i s c o 公司的i p 厂r v 系统实现了远程教科1 1 1 2 。此外，视频服务技术 还将在远程监控、电子商务等领域广泛应用。 3 ) 国内宽带网的发展为视频服务技术的应用提供了良好的平台 近年，国内宽带网络发展迅速，国家对信息基础设施的建设不断加大力度。 到2 0 0 2 年9 月3 0 日为至，中国网通互联网、中国公众互联网、中国联通互联网 与国家互联网交换中心的互联带宽分别为3 g b i t s 、7 5 g b i t s 、3 g b i t s 。电信、 网通、广电等的全国骨干网络普遍采用d w d m 技术，带宽达到4 0 g 以上“3 。特别 是中国电信，目前其骨干网的带宽为8 0 g b i t s ，其中上海到武汉已达到 3 2 0 g b i t s ，预计在不远的将来，其骨干网主要干线带宽均可达到3 2 0 g b i t s 。 电信、网通、广电等的省干网普遍采用s d h 技术，并逐渐向d w d m 发展，带宽己 达到2 5 g 以上。在城域网方面，电信、网通、广电等在许多大城市都部署了2 5 g s d i t 传输平台和干兆网交换平台。目前，在接入网方面，新建的住宅小区都普遍 建立了1 0 0 m 1 0 0 0 m 交换网，许多原有住宅小区也在建设1 0 0 m 1 0 0 0 m 以太网，或 进行h f c 双向改造。 宽带网络建设不仅为视频服务应用提供了网络基础平台，同时也将为视频服 务技术提供更广阔的市场。从网络使用情况可以看出，目前仅限于普通上网，如 何在这过程中挖掘新的增值服务，寻找利润增长点，己成为宽带发展的首要问 两北工业大学硕：0 学位论文：基于l i n u x 的分布式v o d 系统服务器优化设计 题，形象、具体、生动的视频服务无疑将是酋选。 1 1 2 研究现状及存在问题 鉴于流媒体广阔的市场前景，国外许多著名厂商都推出了自己的v o d 产品， 如m i c r o s o f t 的w i n d o w sm e d i a ，r e a l n e t w o r k 的r e a l s y s t e m ，a p p l e 的q u i c k t i m e ， i b m 的v i d e o c h a r g e r 等i l 】【翻。这些产品各有特色，均有自己的技术优势。w i n d o w s m e d i a 和w i n d o w s 紧密集成，易于管理；r e a l s y s t e m 利用其优秀的编码方式提供 较高质量的低速率媒体流；q u i c k t i m e 适用于多种平台，支持国际标准协议； v i d e o c h a r g e r 建立于i b m 专有的操作系统a i x ( 对多媒体应用做了优化) 上， 提供更好的性能。这些系统除了i b m 的外均建立在通用操作系统如w i n d o w s ， u n i x 等之上，没有采用专用的多媒体操作系统，系统性能没有充分发挥：而i b m 的a i x 也只与其系列服务器捆绑销售，价格昂贵。另外，它们均采用集中式的 系统结构，不同的服务器采用不同的点播地址，用户必须自己选择提供服务的服 务器，没有对整个系统进行统一管理。 国内也有一些厂商如世纪珠穆朗玛、曼德科技等提供v o d 系统。它们一般 通过群集技术提高并发流的数目：少数使用引进的专用服务器，采用专用硬件， 价格昂贵；虽然个别厂商宣称其采用了分布式的体系结构，支持城域级应用，但 是否可以扩展到更大的服务范围还不明确，且这些系统并没有针对流媒体的应用 特点对底层系统进行优化，未能充分发挥硬件系统效能。 综合以上商业应用型系统，可以看出由于市场和技术上的原因，现存的商业 产品并没有对视频服务器做充分的优化，系统存在进一步进行优化的空间。 国外对于分布式v o d 系统的研究起步较早，主要集中在系统体系结构8 g l f m 】 和单个服务器优化【2 2 l 两个方面。 1 ) 分布式v o d 系统体系结构 为了使系统支持大量用户，且易于扩展，学术界已经达成共识7 m 】：支持大 量用户的v o d 系统结构应该采用分布式的设计，将直接为用户服务的视频服务 器靠近用户，以降低对视频服务器的要求，减小所需的网络带宽。 在分布式v o d 系统结构框架之下，研究的热点主要集中在存储系统设计、 系统的负载平衡、视频代理和反射技术等方面。 目前设计的存储系统普遍采用多级存储体系【8 】【9 】【1 3 1 1 7 1 ( 一般为二级) ，节目中 心存储全部节目，视频服务器只存储部分节目，视频服务器中存储的节目集合是 根据节目的点播情况动态调整的。 现有的研究提出了若干数据替换算法，用于视频服务器中节目的动态替换， 两北t 业大学硕士学位论文：基于l i n u x 的分布式v o d 系统服务器优化设计 如文献 8 采用了l f u 算法，文献【9 】采用了一种基于优先权的算法。以上的节目 替换算法符合视频点播访问局部性特性，但容易导致缓冲区污染问题，即曾经访 问多次而又不再使用的数据不能及时换出，降低了命中率。文献 1 1 对l f u 进行 了改进，提出了e l f u 算法，避免了缓冲区污染问题。但是，现有的节目替换算 法，没有充分考虑节目自身的特性，可能出现即将热播的节目由于丌始点播率低 而被替换出去的情况。 对于单个区域内服务器群节目存储的负载平衡，目前主要有两种方式。第一 种是采用条纹化机制【l ”，将一个节目分成小的数据块均匀分布在整个服务器群 中。另一种是基于点播概率的方法，整个节目存储在一台服务器上，各台服务器 相互独立，依靠节目点播概率的统计信息将节目动态调整( 转移和复制) 到其它 服务器中，以实现统计上的负载均衡【18 1 ，即每一台服务器上所有节目的点播概率 和基本相等。两种方法各有利弊：前者可以实现服务器群的自动负载均衡，但存 在单点失效和局域网流量过大问题；后者简单易行且没有上述缺点，但存在统计 偏差和存储空i 日j s j 用率较低的问题 视频代理将节目源进一步靠近用户，减少网络流量，提高服务质量，其只存 储部分节目片段的缓存机制提高了存储空间的利用率，也带来了复杂的控制问 题。反射技术提供对实时转播的支持，以解决实时节目数据在较广的范围内有效 传输问题。 2 ) 单服务器优化 单服务器优化可以在两个层次实现：应用软件层和操作系统层。 当前对于服务器应用软件层的研究主要是尽可能保证点播的质量，即q o s 问 题。文献 2 0 通过节目数据的预取和数据缓冲区的合理分配保证节目数据流的连 续性，文献 2 i 通过应用层的实时调度满足数据流的时间约束，文献 2 2 通过调 整缓冲区的管理策略提供较好的播放质量。这些研究普遍集中在内存管理和请求 分配方面，在一定程度上提高了系统性能。 现有绝大部分v o d 应用软件的实现是建立在通用操作系统上的。通用操作系 统的设计目标就是方便用户使用，提高资源的利用率和系统的吞吐率，同时强调 系统的公平使用，它们并没有针对某类应用做优化，对多媒体应用支持较弱，在 此基础上建立的v o d 服务器性能必然受到底层操作系统的制约。优化视频服务 器软件最有效的办法是采用多媒体操作系统。i b m 的v i d e o c h a r g e 视频服务器 运行在通用操作系统，如u n i x 、w i n d o w s 中，性能表现一般，但采用它专有的 多媒体操作系统a i x 时性能有大幅提高，这是由于a i x 专为多媒体应用作了优 西北t 业人学顾j ：学位论文：基于l i n u x 的分布式v o d 系统服务器优化设计 化的缘故“。 虽然多媒体操作系统的理论研究已经广泛开展，但并没有商用的多媒体操作 系统出现，a i x 只同i b m 的高端服务器捆绑销售。一些大学和研究机构，已经研究 并试制出了一一些改进的操作系统的原型系统，但它们大部分是为了同时支持各类 多媒体应用，而离散类的多媒体支持对v o d 这样的应用是不必要的。我们仅仅需 要特别对v o d 类流媒体的支持，并做充分的优化。 1 1 3 研究的目的与意义 视频应用有广阔的市场前景，然而，现有的技术和产品却不能满足大面 积部署，并同时服务大量用户的应用需要，电信、广电这样的单位已经拥有充足 的网络带宽资源，却苦于缺少合适的宽带应用提供增殖服务。因此，我们整个分 御式v o d 系统的主要研究目标是：研发出一个具有较高性能价格比的分布式视 频服务系统，它可以在较广地域内进行部署，为大量用户提供服务，并最终成为 一个通用的流媒体应用平台。这一系统可以填补如上空缺，促进视频应用的进一 步发展。 1 2 研究内容及思路 本论文的研究工作是在已经设计并经初步验证的分布式v o d 系统原型的基础 上进行的，重点是服务器的优化设计，具体内容如下： 1 ) 解决单个区域内分布式v o d 系统中各台服务器的负载均衡及节目替换两个关 键问题。 2 ) 考虑在流媒体服务器应用特殊环境下，如何使操作系统更好地支持流媒体应 用，充分发挥硬件效能。实践表明，单台服务器系统瓶颈在磁盘，提高磁盘 读写效率是操作系统优化的关键，因此研究的重点是优化l i n u x 的e x t 2 文件 系统，提高其大文件的读写能力，增大磁盘吞吐率。 3 ) 优化设计服务器软件，尽量减少软件的运行开销，提高系统服务能力。 1 3 论文的组织 本论文的章节安排如下： 第一章主要介绍了研究背景、目的和意义，研究领域的发展现状及存在的问 题，由此引出具体的研究内容。 第二章首先概述了分布式v o d 系统体系结构模型，然后给出了一个在多层 西北t 业大学硕二卜学位论文：基于l i n u x 的分布式v o d 系统服务器优化设计 存储系统下应用的节目替换算法。 第三章详细描述了一个在单个区域内的服务器群中实现负载均衡的策略。 第四章关于基于l i n u x 的流媒体专用操作系统优化改造。 第五章是服务器应用软件的优化设计。 6 西北1 ：= 业大学硕士学位论文：基于l i n u x 的分布式v o d 系统服务器优化设计 第二章系统模型及节目替换算法优化 论文的研究工作是在经过初步验证的分布式v o d 系统原型的基础上进行的， 本章首先简要描述此体系结构模型，然后给出一个在多层存储系统中适用的节目 替换算法。 2 1 分布式v o d 系统体系结构设计 2 1 ，1 采用分布式设计的必要性 要使系统在大范围内支持大量的用户，并且这一系统易于扩展，传统的集中 式设计已不能满足需要，必须采用分布式的设计原则，这主要是由应用的硬件环 境所决定的。 第，线路障碍。如前所述，国内宽带网络发展迅速，骨干网络带宽基本上 不存在“瓶颈”，但到最终用户家里的“最后一公里”问题仍然存在。即使小区 内每个家庭有十兆、百兆的高速端口，但对于人口密度很大的小区，整个小区与 城域级v o d 点播中心之间带宽也会出现“瓶颈”。 第二，设备数据吞吐障碍。计算机设备的总线i o 带宽、硬盘阵列吞吐率远 未跟上摩尔定律的发展速度，成为限制v o d 视频服务器负载的最主要技术“瓶 颈”。 第三，i p 网络没有q o s 保障能力，而视频、音频数据的传输对于延时、抖动 等o o s 指标极为敏感，只有依靠将数据源尽量靠近点播用户，提供充足的带宽来 弥补这，缺陷。 因此，需要采用分布式的设计，将所服务的用户群按区域划分，每个区域中 设定若干台视频服务器处理用户点播请求。单个区域内采用群集及负载均衡处理 技术，支持多台服务器的协同工作，从而满足大数量用户v o d 点播的需求。 2 1 2 分布式设计的可行性 采用划分区域的分布式设计的可行性是由节目的访问特性所决定的。实验表 明v o d 系统中节目的访问有很强的访问局部性，即节目的访问概率分布不均匀， 大部分的访问都集中在很小一部分节目上“。这是分布式的v o d 体系结构中能 够在各个区域的服务器群中存储部分节目的实践依据。 两北t 业大学硕士学位论文：基于l i n u x 的分布式v o d 系统服务器优化设计 2 1 3 分布式v o d 系统体系结构模型 以下是分布式v o d 系统的体系结构模型，系统示意图如下【3 节目 中心 幽2 一l 从存储节目的角度，系统分为节目中一0 和本地区域的播放中心两个层次。 节目中心存放整个系统的全部节目，向各个区域的视频服务器推送指定的节 目，并接受各区域视频服务器的节目下载请求，向其传输请求的节目。 播放中心只缓存部分节目。各个区域中均有一个播放中心，它是由若干台视 频服务器、一台目录服务器和一台控制服务器组成。这些视频服务器协同满足用 户的点播请求，向本区域内用户传送其点播的节目流。各台视频服务器本地存储 器中仅保存部分节目( 包括节目中心推送下来的节目和本区域高点播率的节目) ， 并根据情况动态替换。目录服务器作为系统的门户服务器直接与用户交互，向用 户提供节目信息完成节目的查询、浏览、预约等操作。控制服务器与用户端播 放器交互，负责指定一台视频服务器响应用户的点播请求，并完成节目的控制( 如 播放、暂停、拖动、停止等) 功能。 每个区域只缓存点播率高的节目，当用户请求的节目在本地时，该请求可由 播放中心来服务完成：当请求的节目不在本地时，用户可以通过节目预约的方式， 请求在将来的某个时i 瑚观看。播放中心可以根据用户的预约请求，选择合理的时 间将节目从节目中心调度到播放中心缓存，以供用户点播。 该模型的主要思想是将一些点播率高的节目数据靠近用户，把网络流量限制 在局部，避免给主干网络造成较大负载，从整体上提高系统的服务能力。通过合 理地划分区域的大小，采用相对便宜的视频服务器集群就可满足本区域的点播需 求，不必配置昂贵的高档视频服务器：系统模型也允许在保留原有设备的基础上 随意增加任何档次的新设备，保护了已有投资，有效地降低了整个系统的造价。 螽蚤 馕一 张中曝 乏静 两北t 业人学硕十学位论文： 基于l i n u x 的分布式v o d 系统服务器优化设计 2 2 视频服务器的节目替换算法 根据上述分布式v o d 系统体系结构模型，各个区域的服务器群作为一个整 体，仅保存整个系统中全部节目的一部分，服务器群需要根据所属区域的用户点 播情况，动念调度节目中心的节目到本地服务器群中。这就需要一个节目替换算 法，用于将本地缓存的节目替换出去，以存放点播率更高的节目，提高系统的节 目点播命中率是算法设计的目标。 2 2 1v o d 用户的访问特性 目前没有i _ i 三式的v o d 用户访问统计数据出现，现在的研究大都采用影片出租 业或大众媒体的统计数据类比v o d 的用户访问特性。尽管实际的v o d 服务和影片 出租业务特性不会完全相同，一般认为两者还是具有很强的相似性。它们反映了 共同的用户点播特征，曲线如下： o 概率。 “ o i ) o 0 o 0 o l ， 有两种数学模型经常用来表示影片访问的分布特性1 ：z i p f 法则和几何分 布。将n 部影片的访问概率按降序排列，排序后第k 部影片的访问概率为p k ， 则 在z i p f 法则中 p k 2 南， 在几何分砘p k - 糕。 它们能较好地逼近节目的实际访问概率分布。 2 2 2 研究现状 在以上节目点播特性的基础上，现有的研究提出了若干数据替换算法，如文 献 8 采用了l f u 算法，文献 9 】采用了一种基于优先权的算法，以上的节目替换 上转 f 两北丁业人学硕”i ：学位论文：基于l i n u x 的分布式v o d 系统服务器优化设计 算法符合视频点播访问局部性特性，但容易导致缓冲区污染问题，即曾经访问多 次而又不再使用的数据不能及时换出，降低了命中率。文献【1 1 】对l f u 进行了改 进，提出了e l f u 算法，避免了缓冲区污染问题 然而，现有的节目替换算法，没有充分考虑节目自身的特性，可能出现即将 热播的节目由于丌始点播率低而被替换出去的情况。 2 2 3 替换算法的设计思想 针对现有节e l 替换算法的不足，文献 1 3 展示了一种设计替换算法的新思 路，在其设计的层次化视频点播存储系统中所采用的算法，不仅考虑了v o d 用户 的访问特性，而且还考虑节目的自身特性。模拟显示，与常用算法相比，此算法 具有较高的节目命中率。因此，我们采用此算法作为基础，对判别条件做一定修 改，使之实用化并适用于我们的系统。 节目在其生命周期的不同阶段具有不同的点播特性：成长期，节目的访问概 率宏观上是随时间而增加的；成熟期，节目的访问概率基本维持在一定的水平； 衰老期，节目的访问概率随时间逐渐降低。显然，将处于成长期的节目缓存在本 地最合适，而此时由于节目刚换入不久，其点播概率一般很低，极易成为替换出 去的对象。算法应全面考虑节目的点播概率和自身特性，将热播节目尽可能多地 保存在本地存储器中，减少由于从中心服务器下载节目而增加的系统开销。 为了避免缓冲区污染问题，可以将时间轴按一定的长度划分成一个个的周 期：t ”l ，只用近几个周期的访问频率来决定是否替换，这样较早的访问频 率被屏蔽掉，不会出现历史数据长期影响当前替换决策的情况。 2 2 4 节目换入时机 每个周期中有一个时间段作为节目调整期，它用于节目的优化调整，本身会 给服务器带来一定的负载，所以应在服务器负载最低的时间段选择。但节目的调 度不一定只发生在节目调整期，以下是可能的节目调度时机： ( 1 ) 未到节目调整期，用户点播率较高而没有存放在本区域服务器群中的 节目； ( 2 ) 未到节目调整期，用户选择立即观看而没有存放在本区域服务器群中 的节目： ( 3 ) 处于节目调整期，系统进行优化存储，下载用户预约的节目、管理员 推送的节目及高点播率的节目。 2 2 5 替换算法 o 两北t 业人学颂l 学位论 义：耩于l i n u x 的分布式v o d 系统服务器优化设计 点播车 i c f | | “ 图2 - 3 节目的生命期 如上图所示，横轴表示时间，单位为一个检测周期( 通常为2 4 小时) ，纵轴 表示某节目对应于各个检测周期的点播率。c 点所在竖线的左边为节目的上升期 ( 成长期) ，右边为节目的下降期( 衰老期) ，c 点附近较为平缓的区域为节目的 平稳期( 成熟期) 。显然，在节目的上升期换入节目并在节目的下降期换出节目 较为合适。 我们设定为热播节目与非热播节目的分界线( 阂值) ，如图，在a c 区域内 应换入节目，而若空间不够，在b 以后的区域中可以换出节目。 2 2 5 1 参数定义 t 表示第i 个周期( i 为自然数) p 。表示第k 部节目 f = p kfk - 1 ，2 ，n )总数为n 的节目库 i f k 2 n u 第k 部节目在直到i 的所有周期中访问次数的和 j = l m + = f k ，一h 第k 部节目在第i 个周期中的访问次数 w 萨n rn + 第k 部节目在第i 个周期相对于第i - 1 个周期的访问次数的 增量 f 。= p 。jw 。 0 ) 上升集 f 一 p 。w 。 热播节目 f 。= p 。in 。 ，w 。 o ) 换入集 对每部节目，只需保存一个三元组 ，由它可计算出， 和w 。 2 ，2 5 2 算法描述 两北工业人学硕士学位论文：基于l i n u x 的分布式v o d 系统服务器优化设计 a ) 对于调度时机( 1 ) ，未到节目调整期，用户点播率较高而没有存放在本区域 服务器群中的节目，使用请求调入法。 其设计思想为：及时将点播率高的节目换入，但并不是一定能够换入。其目 的是从系统中所有的节目角度出发，优化节目的点播率。 设现在时刻为t ，当对第k 部节目的请求到来时，本周期到目前为止节目k 的访问次数为，算法描述如下： i f ( 此节目不在本区域的服务器群中a n dp k f 。) i fl 节目k 属于换入集 i f ( 整个服务器群的某台服务器磁盘有足够的空间) i f2 构造能够满足存储需要的服务器集合s ； s e l e c t i d l e s e r v e r ( s ，s 。) ：选择负载最轻的服务器 下载节目p 。到s 。： e l s e e l s ei f _ 2 没有任何一台服务器磁盘有足够的空间 找到f a 中( n k m + n k 。) 的最小者p m ；在下降集中找 i f ( n k ， n 。) i f3 新节目k 的当前点播概率大于选定待换出的节目m 将r 换出，并确定了接收节目的服务器s ，： w h i l e ( 服务器s ，上的空间仍不够) 继续在此台服务器上淘汰( n + n 。) 最小的节目； 换入p 、到服务器s ，中： ) e l s e e s ei f3 ( 新节目k 的当前点播概率不大于选定的节目m 找到r 中( n - i - , + n k ) 的最小者p 。；在上升集中找 i f ( n 。，一 n 。)i f4 下降集中选定的节目m 点播概率很小 将p m 换出，并确定了接收节目的服务器s ，： 西北工业人学颂士学位论文：基于l i n u x 的分布式v o d 系统服务器优化设计 w h i l e ( 服务器s ，上的空间仍不够) 继续在此台服务器上淘汰( n + + n k ) 最小的节目； 换入p 。到服务器s ，中： e n di f4 e n di f3 e n di f2 ) e n di f1 b ) 对于调度时机( 2 ) ，未到节目调整期，用户选择立即观看而没有存放在本区 域服务器群中的节目，使用请求调入法。 设计思想： 将用户要求必须观看的节目换入，保证一定可以换入能够立即为用户提供服 务的服务器( 即低载服务器) 。其目的是满足特殊用户( 如愿意享受高服务质量 并愿意为之付费的用户) 的需要。 i f ( 有必须下载的节目k 需要下载) i fl i f ( 整个服务器群的某台服务器磁盘有足够的空间) i f2 构造能够满足存储需要的服务器集合s ： s e l e c t i d l e s e r v e r ( s ，s 。m ) ；选择负载最轻的服务器 下载节目p 。到s 。； ) e l s e e l s ei f _ 2 没有任何一台服务器磁盘有足够的空间 s e l e c t i d l e s e r v e r ( s ，s n 。) ： 选择负载最轻的服务器 w h i l e ( 服务器s 。中的空间不足) 在下降集中淘汰节目 在服务器s m 。中找属于f d 且( ，一+ n k 。) 的最小者r ： i f ( p _ f c 。) 两北t 业人学硕士学位论文：基于l i n u x 的分布式v o d 系统服务器优化设计 淘汰节目p _ ； c o n t i n u e ；回到循环开始处 ) 在上升集中淘汰节目 在服务器s 。中找属于f 。且( n + ，) 的最小者p 。； i f ( p 。f c 。) 淘汰节目p 。： c o n t i n u e ：回到循环开始处 ) 仅根据点播概率淘汰节目 在服务器s 。中找( n k 。一。+ n k ；) 的最小者p 。； 淘汰节目r ： ) e n dw h i l e 下载节目p 。到s 。： e n di f2 e n di f1 c ) 对于调度时机( 3 ) ，处于节目调整期，系统进行优化存储，下载用户预约的节 目、管理员推送的节目及高点播率的节目，使用预先调入法。 设计思想： 此呵度时机中，实际有两部分的工作： i ) 换入用户预约或管理员推送的节目，保证一定可以换入，在用户点播时， 这些节目必须在本地视频服务器中。 2 ) 换入高点播率的节目，这是为了进行节目的优化存储，在本区域内保存 点播率高的节目。 使用阶线性法则预测下一个时问周期的访问频率n = n 。：+ w 。，定义换入 闽值a 。和换出阈值。， f o r ( f 中的每一个p 。) i f ( 。 ，。a n dw 。 o ) f 。= f ，。u ( p k ) ： j f ( n w ( 。；a n dw 。 o ) 两北丁业人学硕士学位论文：基于l i n u x 的分布式v o d 系统服务器优化设计 f 。= h ，、u ( p “ ： 在某个时候，执行如下操作： ( 1 ) 将f 。中的节目删除： ( 2 ) 将用户颅约的节目、管理员推送的节目下载到本地，采用调度时机( 2 ) 的算法； ( 3 ) 将f ，。中的节目按n k 。从大至小依次换入，换入时采用调度时机( 1 ) 的算法。 2 2 5 3 此算法需要保存的参量 ( 1 ) 对每部节目，需保存一个三元组 ，即节目的当前 检测周期的点播次数，前一个及前两个检测周期的点播次数； 2 2 5 4 此算法需要管理员设定的参量 ( 1 ) 节目与非热播节目的分界线( 阈值) a ； ( 2 ) 节目的换入阂值。和换出闽值a 。 两北t 业大学硕士学位论文：基于l i n u x 的分布式v o d 系统服务器优化设计 第三章服务器群负载均衡 视频服务器群的负载均衡，实际包括两个方面：一是节目存储的负载均衡； 二是点播服务的负载均衡。缓存的节目在点播请求到来时已经存储在特定的视频 服务器上，点播请求只能由拥有此节目的视频服务器服务，不允许出现热播节目 集中存储在少数服务器，使得部分服务器满载而另一部分服务器欠载的情况，这 是节目存储负载均衡所要解决的问题；同一节目存储在多台服务器时，不允许出 现将点播请求分配给高载荷服务器的情况，这是点播服务负载均衡所要解决的问 题，本章从这两个角度进行讨论。 3 1 节目存储的负载均衡 3 1 1 研究现状 对于单个区域内服务器群节目存储的负载均衡，目前主要有两种方式： 第一种是采用条纹化机制“，将一个节目分成小的数据块均匀分布在整个服 务器群中，任何一台服务器都可以访问整个服务器群的存储设备。这样，不论哪 台服务器响应用户请求服务，数据读取造成的磁盘i o 负载都会自动均匀地分散 在各个服务器上，这可以达到最大程度的负载均衡。但这种方式存在单点失效问 题，若某个服务器崩溃，所有的节目都不可用，并且这种方式实现较复杂，也大 大增加了网络流量( 约为原来的两倍) 。 另一种方法是整个节目存储在一台服务器上，各台服务器是独立的，依靠统 计的节目点援概率信息将节且动态调整( 转移和复制) 到其它服务器中，以实现 统计上的负载均衡“，即每一台服务器上所有节目的点播概率和基本相等。这样， 高点播率的相同节目可能重复存储在多台服务器中，高点播率的不同节目尽量存 储在不同的服务器中。这种方式的负载平衡效果严重依赖于节目点播概率信息的 准确获得，并要求过去的点播概率能够很好地反映将来的情况，这在某些时候可 能出现偏差。但这种方法简单，易于实现，且不存在单点失效问题，也没有增加 网络负载。 3 1 2 应用环境与设计要求 根据设计的分布式v o d 系统体系结构模型和系统的应用环境，我们不可避免 两北：f _ 业人学硕l ：学位论文：基于l i n u x 的分布式v o d 系统服务器优化设计 地面临以下两个问题： 1 ) 单个区域内服务器群的硬件可能是异质的。随着本区域内用户数量的增多， 相应地需要增加视频服务器的数量。计算机硬件的发展速度很快，而价格又 在不断降低，新增加的服务器一般都会比原有的服务器配置高档，速度更快， 存储容量更大，造成了各服务器之间的硬件差异，它们所能存储的节目数目 和服务的用户数量都是不同的。 2 ) 视频点播系统所提供的节目具有不同的编码、压缩方式，节目种类也不尽相 同即便是同样的节目，也可能提供不同压缩比的版本以支持智能流。这样， 不同节目播放时对系统资源的耗用量也不同。 这两个问题决定了我们不能简单地使用连接数目作为服务器负载的评判依 据，而要设计一个真正能平衡服务器负载的方案。综合考虑用户与系统健壮性及 系统效率等问题，负载均衡策略应满足如下要求： 1 ) 降低本区域内用户点播请求的拒绝率； 2 ) 尽量使服务器群中各台服务器的负载均衡，使节目的分配合理： 3 ) 应该使单区域内的服务器群具有一定的系统失效抵御能力； 4 ) 新的负载平衡策略要尽量避免造成过大或集中的网络流量。 3 1 3 负载均衡策略的选择 前面已论述，目前较为理想的节目存储i o 负载均衡的方法主要有两类：一 是分布式的节目存储技术；二是基于点播率的存储和动态调整技术。根据系统系 统应用环境与设计要求，我们采用基于点播率的存储和动态调整技术。 3 1 4 负载均衡的实现 负载均衡不仅要在节目从