（计算机软件与理论专业论文）流媒体服务器负载均衡的研究.pdf

摘要 摘要 对流媒体服务器而言，存储系统性能的好坏直接影响到系统的整体性能， 而存储系统的性能主要足由存储设街的物理性能，数据的布局以及负载的分布 决定的。 本论文中提出了一种神：流媒体服务器存储系统中保存多份数据拷贝的策 略，即存储系统中的所有视频文件并不仅仅是一份，而是根据视频文件的负载 商低来决定其拷贝数，负载多的视频文件的拷贝数一般要多于负载低的视频文 件的拷贝数。同时在存储系统中将视频文件的拷贝合理地布局到各个磁盘上， 并将视频文件的负载合理地分布在各个拷贝上，从而提高存储系统的性能，最 大程度地提高系统的吞吐量，使服务器能处理更多的用户i 方问清求。这其实是 一种用物理存储空问来换取系统性能的策略。 关键字 数据布局 负载转移数据迁移边界着色问题o 一1 背包问题 a b s t r a c t c o n c e r n i n gm e d l u ms e r v e r ，t h ep e r f o r m a n c eo fs t o r a g es y s t e mh a sad i r e c te h e c f o nt h a to ft h ew h o l es y s t e m ，w h il et h ep e 广f o r m a n c eo fs t o r a g es y s t e mi t s e l fw e i l d e p e n d so nt h ep e r f o r m a n c eo fp h y s i c a ls t o r a g eu n i t s ，d a t ap l a c e m e n t a n dl o a d a l l o c a t i o n t h ep a p e ri n t r o d u c e sas c h e m et os a v em a n yd a t ac o p i e si nt h es t o r a g es y s t e mo f t h em e d i u ms e r v e r ，t h a ti s ，a l lt h ev i d e on l e sa r en o tk e p ts i n 鲥ei nt h es t o r a g es y s t e m a n dh o wm a n yc o p i e st h a to n en l eh a sd e p e n d so ni t sp r o s p e c t i v el o a di nt h i ss e n s e ， t h e 矗1 e st h a ta r ea n t i c i p a t e dt oh a v ec o n c e n t r a t e dl o a dg e tm o r ec o p i e st h a nt h o s et h a t a r ea n t i c i p a t e dt oh a v ei e s sl o a dm e a n w h 订e ，p r o p e ra l i o c a t i o no fa l lt h o s ev i d e o 行1 e c o p i e si nt h ed i s ka n dt h ep r o p e ra l l o c a t i o no f i o a do na l lt h o s ec o p i e sw o u l di m p r o v e t h ep e r f o r m a n c eo f t h es t o r a g es y s t e ma n dm a x i m i z et h et h r o u g h p u to f t h es y s t e mi n t h ee n d t h es e r v e rc a nh a n d l em o r ec a l l sf r o mt h ec u s t o m e r st h e r e f o r e ，i ti s ，i ne 何、e c t ， as c h e m eo ft r a d e o f fb e t w e e nt h ep h y s ；c a ls t o r a g es p a c ea n dt h ep e r f o r m a n c eo ft h e w h 0 1 es v s t e m k e y w o r d d a t a p l a c e m e n t ， l o a dt r a n s f e r ， d a t a m i g r a t i o n ，e d g e c 0 1 0 r i n gp r o b l e m ， o 一1k n a p s a c kp r o b l e m 目录 图目录 图2 1 二分图边着色过程l l 图3 1 视频文件布局图1 9 图3 2 初始视频文件的分布图2 3 图4 1l o a dd a n c i n g 有向图3 2 图5 1 数据迁移模型图3 6 图5 2 着色后的数据迁移模型图3 8 图5 3 数据迁移图的变更4 6 图6 1 不同磁盘数下的最大负载比较图5 0 图6 2 不同旦值下最大负载比较图5 l 图6 3 不同旦值下负载均衡系数比较图5 2 v 目录 表目录 表3 1 负载均衡重要术语表1 4 表3 2 视频文件在磁盘上的分布1 8 表3 3 视频文件的访问请求和拷贝数2 2 表4 1 视频文件在磁盘上的分布2 7 表4 2 视频文件在磁盘上的分布3 l 第一章绪论 第一章绪论 第一节流媒体服务器负载均衡背景介绍 随着企、i k 对数据需求的不断增大，用来存储数据的存储介质的规模f 旦越来 越大，由以前的单个磁盘发展到现在的大型存储系统( 如s a n ) 。随着存储系统规 模的不断增大，负绒不均衡的的问题也越来越引起人们的重视，因为存储负载 均衡的好坏将直接影响到整个系统性能的高低。因为一般存储介质( 如硬盘) 由于本身机械特性的限制，其性能提高速度直较为缓慢，远远落后于c p u ，内 存等系统其它部分的发展速度，一旦“i 现负载不均衡的现象，【；! | j 系统绝大部分 的访问请求集中在少数几个存储介质上，；f j | 5 么这几个存储介质就会由于负担过 重而成为整个存储系统性能的“瓶颈”，导致整个系统性能的下降。所以合理 的数据布局和负载分布对提高存储系统的性能而言是非常重要的。 当然提高存储漫备的物理性能将有助于系统性能的提高，但是物理设备性 能的提高意味着系统的升级换代，企业将要付出一笔不菲的代价，同时物理设 备性能的提高也是十分有限的，并不能完全解决问题。为了在物理存储设备不 变的情况下提高存储系统的吞吐量，一种常见的解决方法是利用磁盘条纹组 ( d s ks t r i p i n gg r o u p ) ，即将多个独立的磁盘形成一个组，在这个磁盘组上存 放的任何文件都不是存放在一个单一的磁盘上，而是首先将文件分成大小相等 的条纹，条纹的数目为该磁盘组里独立磁盥的个数，然后将相同文件的不同条 纹分别存放到磁盘组里独立的磁盘上。这样，该文件的负载就均匀的分布到了 磁盘组里所有的磁盘上，从而提高了存储系统的吞吐量。但是仅靠磁盘条纹组 也只能部分解决负载均衡问题，而并不能全部解决，这是因为磁盘条纹组下的 磁盘数目不可能很大，因为随着磁盘数目的增加，数据损坏的概率电在不断增 加，为了保证数据的可靠度，像在i 认i d 5 中那样加入校验单元的方法又会由于 需要保存用于校验的数据而使系统存储空间的利用率下降。 为了进一步提高存储系统承受的最大负载( 对于流媒体服务器而言，视频文 件的负载主要是指视频文件的用户请求数) ，同时考虑到系统负载的均衡，在本 论文中提出y 一种保存多份数据拷贝的策略，即存储系统中的所有视频文件并 不仅仅是一份，而是根据视频文件的预期负载来决定其拷贝数，负载多的视频 文件的拷贝数相应的要多于负载低的视频文件的拷贝数。同时在存储系统中合 第l 页 第一草绪论 理的布局备视频文件的拷贝以及视频文件的负载在各拷贝上的分布。这其实足 种用物理存储空问来换取系统性能的策略，由于单个磁盘的价格一赢柏：下降， 凶此这种策略在现实中是完全可行的。 同时考虑到流媒体服务器上视频文件负载是不断随着用户访问量的变化而 动态变化的，所以需要不断的动态调整视频文件的拷贝数，有些负载增大的视 频文件拷贝数目有可能会增，! j ，相应的负载下降的视频文件的拷贝数会减少。 在增加视频文件的过程中，会涉及到数据迁移问题，所以在本论文中专门用一 章来介绍数据迁移问题以及数据迁移后负载的重新分布问题。数据迁移的目的 是进一步均衡系统的负载，提离j 系统的性能，而数据迁移本身会对系统的性能 ，“生较大影响，会降低系统的难常性能。所以数据迁移策略一方面要能均衡系 统的负载，另一方面要使迁移的数据尽可能的少，数据迁移持续的时间也是越 少越好，从而减少数据迁移过程对系统正常性能的影响。 在具有多份数据拷贝的流媒体服务器负载均衡方案中，涉及到了一些算法 方面的知识，主要是0 一i 背包问题和图的边着色问题，为了让读者可以更好地 理解后面的负载均衡方案，在第二章中专门开辟了一章来介绍这两个问题以及 这两个问题的常见近似算法。 第二节本文内容组织 本文在第二章中首先介绍论文中将会用到的一些理论知识和一些近似算 法，主要是0 一l 背包问题和图的边着色问题，分别描述了几种关于这两个问题 的近似算法，为论文后面部分的正式讨论负载均衡方案打下基础，有利于读者 更好的理解本文。 然后在第三四章中提出了一种针对具有多份数据拷贝的存储系统的数据 布局和负载分布算法，该算法决定存储系统中所有视频文件的拷贝数，每份拷 贝在系统磁盘上的分布以及视频文件的负载在这些拷贝上的分布。同时考虑到 系统中视频文件负载的动态变化，因此论文还涉及到了在服务器服务过程中随 着视频文件负载的动态改变而相应地动态改变负载在同一视频文件不同拷贝之 问的分布。这一算法的目标在于均衡系统的负载，将整个系统的负载比较理想 的分布到系统中所有的磁盘上，尽可能的减少磁盘性能瓶颈给系统性能带来的 影响，从而增大存储系统的吞吐量。负载均衡策略的数据布局和负载分布算法 分为初始布局和动态布局两部分，第三章主要描述初始布局，初始布局决定每 第2 面 第一蕈绪论 份况频文件的拷贝数以及这些拷贝在系统中的分布，第四章主要描述动态布局。 动态布局决定每个视频文件的负载f l ：该视频文件的所有拷贝上的分布，同时还 处理当视频文件的负载发生变化时负载在系统各个磁盘上的重新分布。 在第五章中介绍了一种数据迁移算法，主要是在负载均衡算法中仅靠第四 章中动态布局部分的负载转移不能达到均衡负载的目的时，我们开始考虑在存 储空间允许的情况下，增加部分视频文件的拷贝，同时将这些视频文件的负载 部分转移或全部转移到新的拷贝上丽。在实现过程中，我们的一个目标是均衡 系统的负载，提高系统的性能，另一个目标是提出利，数据迁移调度算法，使 整个数据迁移过程持续的时问最少，【到为数据迁移过程会使存储系统的正常性 能受到很大的影响，所以我们希望这个过程持续的时间越少越好。 第六部分是结论部分，通过仿真实验来验证策略对存储系统性能的改善情 况主要是通过不同情况下的最大负载和负载均衡系数两方面来测试不同负绒 均衡方案的性能。 最后，第七章为总结部分，总结厂这篇论文的取得的一些成果，晟后还介 绍论文中的一些不足的方面和其它相关的可以进一步研究的方面和领域，为今 后的研究： 作起到穿针引线的作用。 第3 页 第二：章负载均衡相关理论知识 第二章负载均衡相关理论知识 在讨论流媒体服务器存储系统负载均衡算法的过程中我们要涉及到了几 个比较重要的理论问题及其近似算法，它们分别是o 一1 背包问题和边界着色问 题。因此在这章中首先分别简单介绍这j l 个问题，以及这几个问题常见的近似 算法的思路，为后面的章节打下基础，同时【! = i 有助于更好的理解后面介绍的流 媒体服务器负载均衡方案。 2l l0 1 背包问题介绍 第一节o 一1 背包问题 给定n 种物品和1 个背包。物品， 量为c 。问应如何选择装入背包的物品 的重量是w ，其价值为，背包的容 使得装入背包中物品的总价值最大。 在选择装入背包的物品时，对缚种物品，只有2 种选择，即装入背包或不 装入背包。不能将物品，装入背包多次，也不能只装入部分的物品，。因此，该 问题称为o 1 背包问题。 此问题的形式化描述是，给定c 0 ，彬 o ，旷 o ，0 ， ，要求找出n 元 。一1 向量，( r t ，x ：，r 。) ( r ， o ，1 ) ，o ，) 使得二w r ，c 而且：。v f x ，达 到最大。 o - 1 背包问题作为一个n p 一完全问题，不可能找到一个具有多项式时间的算 法，但是我们可以利用贪心算法，动态规划算法以及回溯算法等近似算法来解 决o 一1 背包问题，下面分别介绍这儿种算法。 2l2o l 背包问题的贪心算法 其实贪心算法就是每次都挑选“性价比”最好的物品放入背包中( 背包有足够 的空问放入该物品) ，因此贪心算法首先将所有的物品按照单位重量的价值v ，w ， 第4 页 第二章负载均衡相关理沦知识 的值降序排列 z i 爿，二 ，即v ， 1 ，2 ，m ，如果， ，则有v - ，j v ：w ： 其中、，j ，v j ，v ：，w ：分别为队列 - ：，尼 ，物；w ，和厂j 的价值和重量。 贪心算法每次部从队列 ：，二 头开始遍历队列，寻找队列中第一个重 量小于背包的剩余容量的物品，找到后就将其放入背包中，然后修改背包的剩 余容量，并将该物品从队列 i ：，形 吖一删除，然后又重复上面的操作，如果 出现队列中没有物品或队列中有物品但没有任何物品的重量小于背包的剩余容 量的情况，算法就结束了。由于0 1 背包问题中，物品是不能划分的，所以一 般情况下背包都会有空余。 由于背包的装入过程仅需o ( n ) 阶的时问，所以o l 背包问题的贪心算法的时 间代价 ! | j 为排序的代价o ( n l o g n ) 。除排序过程外，背包装入过程只需个别的工作 单元，即额外空问需求为0 f 1 ) 阶。 213 o l 背包问题的动态规划算法 。一l 背包问题是一个特殊的整数规划问题 最优予结构性质 0 - 1 背包问题具有最优子结构性质，设( y ，y ：，y 。) 是所给o l 背包问 题的个最优解，则 y ：，y ， 是下而相应子问题的一个最优解 m a x v ，一 j v ，c w j ， lz ， o ，l 2 ，” 第5 页 ， c _ y ，w y + w ，z 。c 。 f = 2仁2 仁2 这说明 y 。，：! 。，z 。) 是所给0 一l 背包问题的一个最优解，这与前面的前提 y ，。 ，y 。 是所给0 1 背包问题的一个最优解矛盾。 递归关系 设所给o 1 背包问题的子问题 m a x j ： ， lz t o 1 ，f 七 的最优值为( f ，) ，即m ( ，j ) 是背包容量为j ，可选择物品为1 ，i ，i + 1 ，n 时 。一1 背包问题的最优值。由。一l 背包问题的最优子结构性质，我们可以建立计算 7 ( ，) 的递归式如下： m ( ，) v 吣) 2 o “ 算法描述 第6 页 ， r 0 m d + ，)嗄， h 州” m 卅 ，、，l 第二章负载均衡相关理沦知识 。一l 背包问题的k n a p s a c k 算法具体描述可以参考文献 2 1 ，参考文献中的 k n a p s a c k 算法需要o ( n c ) 计算时问。 21 4o i 背包问题的回溯算法 算法思路： o j 背包问题的回溯算法在参考文献 2 2 ，有洋细介绍，下面就简单描述一下 2 2 【= = 1 的【亘】溯算法。o 一1 背包问题的一个解可以表示为长= 度为n 的o ，l 向量 ( x i r ：r ，) ，因o l 背包问题的一个解可以表示为长度为n 的o ，l 向量 ( r ，r ! x 。) ，因此其全部可能解与所有长度为n 的二进制数相对应，故可能解的 总数为2 n 个。 解。一l 背包问题时，首先判断是否二w ，m ，如果n 个物品的总重量不大 于m ，则解为( 1 ，1 ，1 ) 。否则，为了便于找到价值最大的装载方案，对于这n 个 物品按照单位重量的价值v ，w ，的值从大到小进行排序，把这项工作记为： b t s o r t ( f i o a tw n o a tp ，i n tn ) ， hn 按照问题约束条件的要求：一w ，m 且一只取最大值，在状态空间树 仁1仁l 的任意一个部分解( 。) 结点处，应该有两个判定函数 t ( 1 ) 当前部分解的总重量r ，w ，m ： j = l ( 2 ) 当前问题状态下，继续向前搜索( 该结点的子树) 可以找到比目前已 知解的总价值更大的解。 第二点可以通过“限界函数”b o u n d ( i ) 来实现，方法是： 。在算法中设置一变量b e s t p ，初始值为o ，用来记录已搜索到的解状态结 点( 叶结点) 的最大价值。 。缚到达个活动结点，( 部分解) ，就调用限界函数b o u n d ( i ) 。计算方法 是从这个部分解( t ，_ ) 开始，采用贪心算法计算一般背包问题的策略，允许最 第7 贾 第二蕈负载均衡相关理论知识 后一个物品被分割后加入背包，从而得到从结点川l 发的予树中可以达到的总价 值的上界。如果这个上界小j 二当前的b e s t p 值，说f ! j _ j 该子树不可能包含最优解， 即可以被“剪枝”，则将这个部分解结点变为d 一结点( 死结点) 。根据条件( 1 ) 和 ( 2 ) ，可以确定若下状态结点为d 一结点，从而大大加速了搜索过程。 算法实现和复杂度分析： 0 一l 背包问题的网溯算法的实现过程在可以查看参考文献 2 2 ， 2 2 中有关于 o 1 背包问题的刚溯算法洋细的描述和复杂度分析。 o l 背包问题同溯算法b t k n a p s a c k 的时间复杂度为0 ( ，2 ”) 阶。 算法的空间代价t 要由两个因素决定： 算法的输入、输出和运行中的临时数据占用的空间，显然为c ) ( ”1 阶。 递归过程所， = j 的栈空问，由于递归是彳i 断调用和退出的过程，递归层数不 可能超过状态空问树的高度n ，而每一层调用一与用的空问为常数，因此递归过程 的空问代价为c ) m ) 阶。 所以算法的空问复杂度为d ) 阶，这也是回溯算法的一个重要优点。 第二节图的边着色问题 22 1 图的边着色问题介绍 图的着色问题分为图的顶点着色问题和图的边着色问题，我们在这部分主要 是讨沦图的边着色问题。 对于图g 的任意两条边e ，e z ，如果它们两个恰好有一个公共顶点，则称这 两条边是相邻的。图的边着色定义如下： 图g 是正常k 一边着色，记作，它是从g 的边集e ( g ) 到颜色集c ( k ) 的一种映 射，即厂：e ( g ) 寸c ( ) 。并且映射，需满足：当p ，p ，e ( g ) ，且e l 与e 2 相邻时， ( p 。) ( p ：) 。图g 的全体正常k 一边着色集记作c 。( g ) ，若c 。( g ) ，即g 中至少存在一个正常k 边着色，则称g 是k 一边可着色的。图g 的边色数，记作 第8 页 第二章负载均衡十h 关理论知识 z7 ( g ) ，是指k 一边可着色的k 的最小值。若z ( g ) = ，则g 称为k 边色图。没 gl = _ 】所有结，r 量的最大度数为( g ) ，因为f e 何一个结点关联的边着色不同，所以 必有： z ( g ) ( g ) 定理21 ：如果g 是二分图，则z ( g ) = ( g ) 2 3 。 证明和二分图的定义见参考文献 2 3 。由二f 在后面的负载均衡数据迁移过程 中，我们的数据迁移模型是个二分图，所以我们只讨论二分图这种情况。 22 2 二分图边着色方法 假设有二一分图g ( v e ) ， p 7 = ，v ：，、，。 ，e = p ，p ：，p 。) ，结点v 的度数 定义为( “，= m a x ( u ) ，( 叱) ，( 、，。) ，假发图g 中度数最大的结点为 ”。( 1 ，m ) 。 由定理21 得到图g 是边可着色的，所以在着色过程中可以保证用种不 同的颜色为所有的边着色，且相连边的颜色均不相同。 ( 1 ) 点为v 。( 1 ，m ) 的所有边e = 吲，p ：1 ，p ：) 分别着上不同的颜色 c 2 h c ：c n 。 ( 2 ) 然后开始从边e = e 中挑选与e = p j ，g ：，p ：) 相连的边 e ”= e ? ，p 知，p ： ( o 玉一) ，如果e ”= 中，则回到( 1 ) ，重新在剩下的结点 中寻找度数最大的结点，继续着色的过程。否则对庄”中的每条边，从 c 2 溉，c ：，c 。 中挑选一种它的邻边尚未着过的颜色，由定理2l 我们知道，总 是可以找到一种这样的颜色对其着色。 ( 3 ) 将e 4 中的每条边着完色后，e = e u e ”，然后重复步骤( 2 ) 直到= 中为 第9 页 第二：草负载均衡相关理论知汉 止，着色过程结束。 下面用一个简单的例子来描述这一过程： 假发二分图为g ( v e ) ，矿= v ，v ：，、，- ，“! ，f ， ，所有结点问的连接情况见下 面的演示图。 首先找到度数最大的结点，由图可知，度数最大的结点为u 。，v ，它们的度数 都为3 ，所以= 3 ，我们的颜色的集合为c = c i ，c 。c ， 我们任意选取其中的 一个结点开始着色，似设我们从结点u 。开始。 以结点u l 为端，一点的边有e l ( u 1 ，v 1 ) ，e 2 ( u l ，v 2 ) 和e 3 ( u l ，v 3 ) ，我们分别为其着上颜 色c l ，c 2 和c 3 。 与边e 1 ( u 1 ，v 1 ) ，e 2 ( u l ，v 2 ) 和e 3 ( u l ，”3 ) 相邻的边为e 4 ( u 2 ，v 2 ) ，e 5 ( u 2 ，v 3 ) 和 e 6 ( u 3 ，3 ) ，首先给边e 4 ( u 2 ，v 2 ) 着色，与边e 4 ( u 2 ，v 2 ) 棚邻的边为：e 2 ( u i ，v 2 ) ， e 5 ( u 2 ，v 3 ) ，其中只有e 2 ( u l ，v 2 ) 被着上了颜色c 2 ，所以边e 。( u 2 ，v 2 ) 可选的颜色为 c ，和c 3 ，我们将边e i i 着上颜色c 。 与e 5 ( u 2 ，v 3 ) 相邻的边e 3 ( u l ，v 3 ) 和e 4 ( u 2 ，v 2 ) 分别着上了c l 和c 3 ，于是我们将 e 5 着上颜色c 2 。 与e 5 ( u 2 ，v 3 ) 类似，我们将边e 6 ( u 3 ，v 3 ) 着上颜色c ，。至此，所有的边都已经成 功着色，着色过程蜘i 下图所示。 第】0 页 第二章负载均衡相关卫 ! 论知识 u lu 2u 3 焱够 ( 1 ) 8 u lu 2 u 3 ( 2 ) n u l u 2 u 3 ooo e 。f | 誉淑7 必义n u uuu ( 3 ) 第l i 页 第三章负载均衡初始布局 第三章负载均衡初始布局 第一节流媒体服务器负载均衡简介 对于一个由一系列磁盘组成的流媒体服务器存储系统而言，i 0 系统一般是 系统性能和成本的瓶颈。通过均衡存储系统各磁艋的负载来提高系统吞吐量， 便成了非常具有挑战性而且十分具有实际意义的：i ：作。一方面磁盘的过载会导 致服务器中断已有的对该磁盘上存放的观频文件的服务请求或拒绝新用户的服 务请求，另一方面磁盘过低的负载又会导致系统资源的浪费。因此，为了提高 流媒体服务器的性能，能支持更多的用户访问清求，就必须解决存储系统的负 载均衡问题。 流媒体服务器上的某个视频文件一旦被点播，就意味着给存放该视频文件的 磁盘产t 仁持续一段时问的恒定负载，该负载是由对磁盘的读写请求产生的。由 于不同视频文件的用户点播的次数和频率可能相差很大，而且用户访问清求的 不规律分布在每周，每天甚至每小时都在变化，因此这也就给均衡系统磁盘间 负载的：l 作变得十分复杂。事实上，如果将非常受用户欢迎的视频文件存放到 单个磁盘上将会导致该磁盘过载的话，有一种部分解决这个问题的方法：磁盘 条纹组( d i s ks t r i p eg r o u p ) ，如在 1 中定义的那样，将分成条纹的数据均匀的分 布到多个磁盘上，由该文件的产生的负载就均匀的分布到了各个磁盘。但是磁 盘条纹化包有它自身的不足，因为随着磁舷的增多，磁盘损坏的概率也在增大。 所以参与条纹组的磁盘的个数必须限制在一定的范围内。所以在单个视频文件 负载特别大的时候，仅仅靠磁盘条纹组并不能完全解决问题。另外一种解决办 法是将过载磁盘上的一部分视频文件迁移到其它负载较低的磁盘，这种办法在 一些情况下也可以解决负载不均的问题，但是数据迁移有两个缺点：其一是数 据迁移涉及到数据的拷贝，而数据拷贝过程会进一步加重磁盘的负载，进而影 响整个系统的性能。另一方面是数据迁移只能解决用户访问量比较高的视频文 件存放比较集中的情形，但如果单个视频文件的负载就已经超过了磁盘所支持 的用户访问上限的话，数据迁移的办法就行不通了。所以在这篇论文中提出了 种在存储系统t 附艮据视频文件访问量的多少而相应的保存多份拷贝，同时结 合数据迁移的策略来均衡系统的负载。 第1 2 页 第三单负载均衡仞始布局 铂：这篇论文中，主要是利用数据的多份拷贝以及负载在多份拷贝问的理想 分斫，来有效地解决负载均衡问题。在该存储系统中，视频文件不再是只有份 拷贝，而是根据用户访问请求的多少来决定拷贝的份数，同时随着用户对视频 文件坊问请求的动态变化，视频文件负载的布局以及视频文件的拷贝数也会相 应的动态调整，在此过程中，用户访问清求下降的视频文件的拷贝数可能会减 少，而与此相反，用户，访问清求增j i ：】的视频文件的拷贝数目可能会增加。整个 负载均衡算法由两部分组成，第一部分是初始布局部分，该部分主要是用来决 定不同视频文件的拷贝数并将视频文件的所有拷贝有效地分布到存储系统f = | = l 不 同的磁盘l ，在这篇沦文中似定每个磁盘只能存放同一个视频文件的一份拷贝。 另外一部分是动态布局部分，这部分主要是根据用户访问请求的变化动态地凋 整视频文件的负载存该视频文件所有拷贝上的分布。同时我们的负载均衡算法 还紧密结合数据迁移算法，它主要足针剥负载转移不能解决负载分布不均的情 况下，利用第四章中介绍的数据迁移算法将访问量比较集中的磁盘上的部分视 频文件拷贝到其它比较空闲的磁槛上，我们的目标是一方面可以实现负载均衡， 另一方面使数据迁移过程持续时问最短。我们在第在这章中主要描述负载均衡 的初始布局，动态布局将在第四章中描述。 初始布局分为两个阶段： 第一阶段主要基于对视频文件坊问清求的预测，利用分配问题的优化 方法来决定每个视频文件的拷贝数，每份视频文件至少有一份拷贝，用 户访问请求多的视频文件的拷贝数要多一些，而用户访问请求比较少的 视频文件的拷贝数相应的要少一些，最少的只有一份拷贝。 第二阶段设计了一种算法将视频文件及其拷贝最优地分配到不同的磁 盘上。算法有两种模式：初始模式和扩展模式，初始模式就是配置一个 全新的存储系统，即存储系统开始时没有存放任何视频文件。在初始模 式中，首先将具有多份拷贝的视频文件利用团集树的图论方法分布到不 同的磁盘上，然后将单份的视频文件利用最少负载优先( l l f l e a s tl o a d f i r 吣的算法进行分布，整个分布算法称之为c l l f 。扩展模式是在限制 视频文件的拷贝总数的限制条件下，随着用户访问清求的变化动态地改 变视频文件的拷贝数目和拷贝在磁盘上的分布来达到均衡系统负载，提 高系统吞吐量的目的。扩展模式是周期性运行地，运行周期可能是一周 或一天，准确的运行频率取决于系统访问请求变化的浮动范围，负载变 第】3 页 第三章 负载均衡衲始布局 化范围大的话，为了在这种情况下仍然保持系统的负载均衡，扩展模式 运行的周期就要短一些。 第二节初始布局介绍 这部分一 三要用来介绍流媒体服务器存储系统负载均衡的初始布局，即决定视 频文件的拷贝数，同时将视频文件的拷叭分布到不同磁盘上，在分布的过程中， 我们的一个重要目标就是这种分布要有利一j 二后面动态布局部分由于用户访问清 求变化而引起的负载的动态调度，我们将往f 而详细地描述这一过程。 存流媒体服务器存储系统中，我们似i 5 2 存储系统是由个磁盘组成d ， 鹏，仉，整个系统有m 部不同的视频文件 ，尼， ，肠，为了读者方便， 将这章r 附h 到的所有重要概念放到了下丽的表格中。 表3l 负载均衡重要术语表 变量定义 m 存放到磁盘e 的不同的视频文件数 d 磁盘的数目 爿 视频文件，磁盘矩阵 _ 磁盘，的最大负载 ，j 磁盘，的衡量函数 。j 视频文件f 在磁盘，上产生的负载 ，l ，视频文件，产生的总负载 所有视频文件产生的负载 kj 视频文件，在磁盘j 上产生的最理想负载 e磁盘，的最理想负载 n 负载过高的磁盘的数日 班 负载过低的磁盘的数日 口 负载均衡好坏的标准 第1 4 页 第三章 负载均衡初始布局 ， 负载均衡的阀值 f 有向l o a dd a n c l l l g 图 驴。视频文件，的预测访问睛求 所有视频文件的预测访问清求 所有可| ；j 的观频文件拷贝数 ，说频文件，的拷贝数 l | 无向l o a dd a n c l n g 图 s磁盘，的存储容量 s 1 视频文件，的大小 最大允许的新视频文件的拷贝数 目 z i p f - 1 1 k e 分布参数 相关系数 m 表示不同的视频文件数，d 表示磁盘的数目，矩阵a = ( 。) 表示视频文件 在磁盘上的分布，我们假设每个磁盘最多包含一个视频文件的一份拷贝，则a 是一个m 的 o ，1 ) 矩阵。 吩，= 托嬲粼凳贝 t ， 。 o 视频文件f 在磁盘j 上没有拷贝 “ 每个磁盘都有一个最大可承受的负载与，当磁盘的负载不超过白时就可 以确保对该磁盘上视频文件的请求在固定的时间内部能得到响应，l 的值取决于 存储系统下每个磁盘的具体性能。为了使用户的访问请求能在固定的时间内都 能得到及时的响应，所以应当避免负载超过，我们用函数巧来衡量磁盘负载 与的接近程度，巧是一个定义域为 o ， ，上，j 且满足( o ) = o 的递增函数， = 叫( l ，( ，+ 1 一r ) ) 就是一个满足条件的函数( 用衡量磁盘访问时问的函数f ! j l 是个不错的选择) 。假设某一时刻，视频文件f 产生的总负载为九，在磁盘j 上产 第1 5 页 第三蕈 负载均衡初始布局 i ：的负载为h ，则丑。= ：，五。如果d 。= o ，则丑，= o ，这是因 为视频文件，在磁盘，上没有拷贝，则必定也不会在磁盘上产生负载。我们用 a = ! ，五，表示所有视频文件产生的总负载。负载均衡的初始布局部分的输出是 简单的 o ，l 矩阵a = ( q ，) 。 第三节视频文件的拷贝数 通过前而部分的介绍，我们知道初始布局；： | j 分的第一阶段用来决定每个不同 的视频文件的拷贝数( 假发对每个视频文件的预期访问清求系统都能满足) 。在决 定视频文件拷贝数之前，先将所有的存储空问c 分成两部分c ，和c 。，c ，用于 存放最秽j 的视频文件，c ? 用于当视频文件发生变化时视频文件拷贝的扩展，即 有些视频文件拷贝数可能会增加，存储空间g 就用来存放新增加的视频文件的 拷贝。我们定义中，为视频文件，的预期访问清求，= ! o 为所有视频文件 的预期防问请求数。 决定况频文件的拷贝数的方法有两种：一种是视频文件的拷贝数与该视频文 件的负载成正比，另一种是视频文件占用的存储空间和该视频文件的负载成正 比，然后根据它所占据的存储空问和文件的大小决定它的拷贝数。在所有的视 频文件大小相同的情况下，两种算法其实是一致的。 33l 拷贝数与负载成正比 假发k 表示系统能够存放的视频文件拷贝数( k 由用于初始分配的存储空间 c ，以及视频文件的平均大小估算得到) ，我们的目标是计算每个视频文件，的拷 贝数，使k 与中，大致成正比，并且满足： 吖 足= 足 卢1 ( 32 ) 这实质是一个资源分配问题，该问题在现实中我们也常常遇见，例如政府代 表人数分配的问题，在美国政府总共4 3 5 名众议院代表，需要将代表名额按照 每个州的人口数成比例的分配到5 0 个州。 第1 6 页 第三章负载均衡_ j | j j 始布局 我们希望保持每个视频文件的拷贝数k 与负钱成正比，假发我们首先限 定系统总共可以存放k = ：足，份视频文件，因此我们希望k ，中，z 足巾。我 们的资源分配问题的目标是使视频文件，的拷贝数k ，接近配额k 中。中，但是配 瞢! j k 中，中并不总是整数，而足，必须为艇数，所以我们可以利用凑蹩算法使k ，总 是落花配额的上界和下界之问。我们采用t h e w e b s t e r m o n o t o n ed i v i s o r m e t h o d 8 】 来决定每份视频文件的拷贝数，该算法描述如下：开始时每个k = l ，然后不断 寻找使巾，( k ，+ o5 ) 值最大的视频文件，然后将k ，增加1 ，重复此过程直到 k = ! k ，时结束。w e b s t e r 的算法实质足个贪心算法，分母+ o5 是许 多可能的除数之一，用该除数来选择下个需要增加拷贝数目的视频文件。 332 存储空间与负载成正比 假殴用于初始分配的存储空间为c ，则根据存储空间与负载成i i j 比的目标， 视频文件f 【与据的存储空问为： 。，：盟 中 ( 33 ) 所以该视频文件的拷贝数： 弘m a x 肛a x 普j b a ， 考虑到整数问题，我们在算拷贝数时取下界，将多余的存储空间留给后面的 扩展部分。同时要注意视频文件至少有一份拷贝，所以丘取1 乘1l 专导l 之间的 最大值。 在上面的两种方法中，虽然在决定视频文件的拷贝数时只利用了存储系统的 一部分存储空间，但在后面的视频文件的初始布局过程中，视频文件的拷贝是 分布到存储系统所有的磁盘上，并不是只分和到存储空问c ，对应的磁盘上。这 样，剩余的存储空间就散布到了所有磁盘上，有利于整个系统的负载均衡。在 第三章负载均衡初始布局 我们的负载均衡方案中，采取的是视频文件占用的存储空间与视频文件负载成 征比的方法。 第四节初始布局的两种模式 初始布局的第二阶段主要足将第一阶段得到的视频文件拷贝分布到各个磁 盘i i ，第二个阶段有两种可能的模式：初始模式和扩展模式。初始模式用于配 簧一个全新的系统，即分布前没有任何视频文件存放到磁箍上。扩展模式用于 根据用户，访问请求的变化定期地动态地改变视频文件的拷贝数和在磁盘上的分 布，为了保证调整在实际中是可行的，我们限制了可以分布到磁盘上的新增加的 视频文件拷贝总数。 在讨论负载均衡初始布局之前，先介绍一下视频文件布局图，是无向图， h 的定义如下：图中的每个结点都代表一个磁盘，如果结点，和止之间有一条 边相连，则意味着必有至少一有同一个视频文件的两份拷贝分别存放在结点， 和，2 对应的磁盘上。 “2 “z 1 ，2 2i r 3s 、 下丽用一个简单的例子来更好的阐述无向图。考虑一个由6 个磁盘和4 部 视频文件组成的系统，视频文件在磁盘条纹组上的分布如下表所示： 表32 视频文件在磁盘上的分布 视频文件所在磁盘 t h e t h i nm a n1 2 3 d a s h i n gt h r o u 曲 2 5 t h i c ka st h i e v e s3 4 p o l k ad o tp u s s5 6 根据我们的定义，则上面的存储系统的视频文件布局图如下 第l8 页 第三章负载均衡初始布局 图3l 视频文件布局图 磁盘l ，磁盘2 和磁盘3 之间由于都存放有视频文件t h et h i nm a n 的拷贝， 所以这三个结点之问都有无向边相连，同理，磁盘2 和磁盘5 之间，磁盘3 和 磁盘4 之间以及磁盘5 和磁盘6 之问都有无向边相连。 负载均衡初始布局部分两种模式的第一个基本目标都是提高视频文件布局 图的连接性，因为图中两个结点之间有边相连，也就意味着在负载均衡的 动态布局部分，视频文件的负载有可能在这两个结点之问互相转移，因为这两 个结点至少包含有同一个视频文件的两份拷贝，所以我们可以根据需要来调整 该视频文件负载在这两个结点上的分布。所以提高视频文件布局图的可连接性 对于后面动态布局部分负载的动态调整是大有帮助的，我们主要是试图通过减 小图的直径来提高图的连接性( 我们定义图的直径是指图中任意两个结点之 间的最大距离) 。 第二个目标是使磁盘，的预期负载与它的最大可承受负载j l ，大致成正比。根 据前面的定义，中为视频文件，的预期负载，足，为负载均衡初始布局部分第一 阶段得到的视频文件，的拷贝数，假发视频文件，每份拷贝的预期平均负载为j ， 第l 9 页 第三章负载均衡初始布局 磁盘，的预期负载为，则 j ：竺 ， x j = d 。6 ， ( 36 ) ( 37 ) y 我们i = i f 标是使每个磁盘的尽量保持一致，最后我们还需要保证每个磁盘 上存放的视频文件大小的总和不超过该磁盘的最大容量，用与表示磁盘的最大 存储容量，_ 表示视频文件，的大小，则要求 3 41 初始模式算法 ( 38 ) 在初始模式中通过三个阶段来取得高连接性的无向图，我们首先介绍团集 树和初始图，然后使用贪心a d d 方案来减小图的直径，最后利用一种称为l l f 的算法将视频文件的拷贝分布到磁盘上。前面的两个阶段用来处理具有多份拷 贝( m c ) 的视频文件，最后的阶段用来处理剩余的只有单份拷贝( s c ) 的视频文件， 我们将在下面依次介绍这三个阶段。 团集树中的每个根结点或分支结点不弭是对应一个磁盘，而是对应于一系列 存放有同一个视频文件拷贝的磁盘的集合，每个磁盘最多包含在树中一个结点 里，即同一个磁盘不可能属于团集树中的两个或两个以上的结点中。除了根结 点中的视频文件外，其它的视频文件的一份拷贝可能存放在前面已经存在的结 点上，则我们在树中创建一条边来连接团集树中的这两个结点。下面我们将更 具体地描述整个执行过程：首先是将用户访问最多的视频文件的拷贝分别存放 到不同的空磁盘上，这些磁盘就形成了树的根结点。然后我们再考虑剩下的用 户访问最多的视频文件，将该视频文件除保留一份以外的所有拷i _ ! 都分布到剩 余的不同空磁盘上，这些磁盘形成了树中的一个分支结点，保留的那份拷贝则 分布到根结点下负载相对较低且有足够存储空间的磁盘上，因为这份拷贝将会 创建团集树树中从根结点到这个分支结点之间的一条边，所以称这份拷贝为连 第2 0 页 第三晕负载均衡剀始布局 接拷贝。重复上面的步骤不断创建新的引集树分支结点，并将连接拷贝分布到 与根结点最近的分支结点下有足够存储空问磁斑中，当根结点下的磁盘有足够 存储空问的话，连接拷贝就存放到根结点f 的磁槛上，否则选取与根结点最近 的分支结点下有足够存储空间磁盘。重复这个过程直到用完所有的空磁盘或所 有的m c 视频文件拷贝都已经分配完毕为止。吲集树中的叶结点代表存放用户 防问较少的视频文件拷贝的磁枯。在建树过程的最后一步中，视频文件的拷贝 数“涂去连接拷贝) 可能比剩下的未分配的字磁毹的数目要多，则将剩下的每个空 闲磁盘部存放视频文件的一盼拷贝，并形成一个新的分支结点，并将连接拷贝 分布到根结点或分支结点上，超出的未能分配到空闲磁盘的拷贝将会在下一个 阶段中进行分配。 下面我们使用a d d 算法分两步来处理第一个阶段遗留下来的m c 视频文件 拷贝。将所有第一个阶段未分配的m c 视频文件配成对，剩下最多一份拷贝未 配对。第一步按照圻问量从高到低的顺序处理配对的拷贝。第二步按照相同的 顺：乒处理剩下的单份拷贝。 针对每对遗留下来的视频文件，我们将其分配到不同结点下的有足够剩 余空间且距离最远的两个磁盘上。因为这将会使距离最远的两个磁盘之 间用一条边相连，从而有效地降低了图的直径。 剩下的m c 视频文件的单份拷贝分布到能最大程度减小视频文件分布 图h 直径的磁盘上，因为最后的那份拷贝存放到某个磁盘后，在视频文 件布局图中，该磁盘对应的结点与前面分配了该视频文件拷贝的磁盘对 应结点之问都会有边相连，从而也会对图h 的直径产生影响。 最后剩下的s c 视频文件不会对图的直径产生影响，所以分布s c 的时候 只需要考虑负载平衡。这部分利用一种称为最少负载优先( l e a s tl o a df i r s t ) 的贪 心算法，即将视频文件的单份拷贝存放到实际负载和最大负载比值最小且具有 足够存储空间的磁盘上。 下而我们用一个简单的例子来描述上面的算法。首先介绍团集树和初始图， 然后利用贪心a d d 算法来减小图的直径，最后利用l l f 算法来分布视频