（计算机应用技术专业论文）用遗传算法解决基于分条技术的磁盘负载均衡问题.pdf

丫6 5 4 1 4 7 四川大学硕士毕业论文 ( 2 0 0 4 ) 用遗传算法解决基于分条技术的 磁盘负载均衡问题 计算机应用专业 研究生倪云竹指导教师吕光宏 摘要 当 今社会是一个信息社会， 信息数据正以 超乎人们想象的速度增长。 信息 对于人们来说是越来越重要， 面对各种各样、 庞大复杂的信息和数据， 怎样安 全地保存、 及时地传输、 快速地恢复， 避免企业因数据的丢失而造成重大利益 损失，这些都日 益成为人们关注、探讨的话题，存储技术也因此成为i t 行业 的一大热点。 随着i n t e r n e t 的高速发展， 各种基于网络的应用开始越来越多。 而存储作为网络后台的核心设备， 就需要为整个网络上的各类应用提供海量存 储、 高可用数据库集群、 数据备份和容灾、 数据迁移、网络存储、 高性能计算 等等各类服务。 即必须提供对数据进行2 4 x 7 的可靠性操作和保护。 为此， 各 种新的存储技术应运而生， 目 前主要技术有: 使用磁盘镜像和复制提供数据冗 余; 使 用缓 存实 现性能的 增 强; 使 用r a i d ( r e d u n d a n t a r r a y s o f i n d e p e n d e n t d i s k s ) 增强可用性。 而为满足对容量快速增长的需求， 存储子系统中的磁盘数量也在不断增 加， 这就逐渐产生了磁盘阵列。大型磁盘阵列内部一般采用r a i d 结构以 提高 其可靠性和 工 / 0 性能， 它通常按照r a i d 标准将多个物理磁盘组成一个磁盘组， 客户系统所看到的磁盘并非实际的物理磁盘， 而是逻辑磁盘， 每个逻辑磁盘映 射到某个磁盘组上的一部分。由于不同的逻辑盘上应用系统的i / 0 特征不同， 很容易造成各个物理磁盘的负载不均。 因此可以说，目 前提高存储子系统i / 0 性能的最大障碍就是磁盘负载不均衡。 四川大学硕士毕业论文 ( 2 0 0 4 ) 本文提出了一种采用遗传算法来实现基于分条技术的磁盘动态负载均衡 的算法。 该方法包括基于分条技术的文件划分算法和为实现负载均衡的文件分 配算法。 磁盘分条技术是从应用程序或者文件系统的角度来考虑负载均衡， 本文吸 取了分条技术对文件划分的思想，并从存储设备的角度来考虑负载均衡问题。 而遗传算法是近年来提出的一种新型优化算法。 它基于自 然选择的原理， 通过 循环执行相同的以及简单的选择、 杂交和变异三种遗传操作， 并在适应度函数 值的引导下对复杂的解空间进行有效地搜索， 直到获得最优的解。 选择、 杂交 和变异是遗传操作的三个基本遗传算子， 选择和杂交完成遗传算法的大部分搜 索功能，而变异加强了遗传算法找到最优解的能力。 本算法利用树型结构的编码来表示物理磁盘组与逻辑磁盘的映射关系。 在杂交算子的设计上，通过对两个父代个体结合，然后再生成新的树的方法， 使算法具有较好的杂交性能。 通过对该算法的仿真分析可以看出整个算法能以 较快的速度求解。 在本文的 最后， 我们对该算法 进 行了 分 析， 并阐 述了 该算法的正 确性和合 理性以及在存储方面的广阔发展前景。 关键词:存储，磁盘阵列，磁盘映射，负载均衡，分条技术，遗传算法 9 s 川大学硕士毕业论文( 2 0 0 4 ) t h e s o l u t i o n o f d i s k l o a d b a l a n c i n g b a s e d o n d i s k s t r i p i n g w i t h g e n e t i c a l g o r i t h m ma j o r : c o m p u t e r a p p l i c a t i o n p o s t g r a d u a t e : n i y u n z h ua d v i s i o r : l i t g u a n g h o n g ab s t r a c t : t o d a y i s a n i n f o r m a t i o n a g e , a n d in f o r m a t i o n i s b e c o m i n g i m p o r t a n t t o p e o p l e m o r e a n d m o r e . wi t h t h e r a p i d l y i n c r e a s i n g o f i n f o r m a t i o n d a t a , t h e t o p i c o f h o w t o s t o r e s a f e l y , t r a n s f e r l a t e l y , re c o v e r r a p i d l y a n d h o w t o a v o i d l a r g e l o s s b e c a u s e o f l o s i n g d a t a i s c a r e d f o r b y m o r e a n d m o r e p e o p l e . s o t h e t e c h n o l o g y o f s t o r a g e h as b e c o m e v e r y i m p o rt a n t . b e c a u s e t h e r e a re m a n y a p p l i c a t i o n s b a s e d o n n e t w o r k s w it h t h e h i g h d e v e l o p m e n t o f i n t e r n e t , t h e s t o r a g e , a s t h e k e rn e l o f b a c k g r o u n d d e v i c e s , m u s t s u p p l y t h e a p p l i c a t io n s w it h a l l s o r t s o f s e r v i c e s i n v o l v i n g t h e l a r g e s t o r a g e c a p a c i t y , t h e c l u s t e r o f h i g h a p p l i c a b le d a t a b as e , t h e b a c k u p a n d r e c o v e r y , t h e n e t w o r k s t o r a g e , t h e h i g h p e r f o r m a n c e c o m p u t e a n d s o o n . i n o t h e r w o r d s , t h e s t o r a g e m u s t s u p p l y t h e d e p e n d a b l e m a n i p u l a t i o n a n d p r o t e c t i o n f o r t h e d a t a i n 2 4 x7 . t h e d i s k m ir r o r , t h e s t o re b u ff e r a n d th e r a i d t e c h n o l o g y a r e t h e m o s t t e c h n o l o g i e s a t p r e s e n t . wit h t h e i n c r e a s e o f t h e n u m b e r o f d i s k s i n s t o r a g e s u b s y s t e m s d u e t o r a p i d l y i n c r e a s i n g d i s k a r r a y , p e o p l e c a p a c it y u s e t h e r e q u i r e m e n t s , t h e d i s k a r r a y i s f o r m e d . i n a l a r g e r a i d t e c h n o l o g y f o r i n c r e a s i n g r e l i a b i l i t y a n d i / o p e r f o r m a n c e . i n t h e a r r a y , a d i s k g r o u p i s c o m p o s e d o f s o m e p h y s i c a l d i s k s , a n d t h e d i s k s t h a t d i s p l a y i n fr o n t o f t h e c l i e n t s y s t e m a r e c a l l e d l o g i c a l d i s k s . l o g i c a l d i s k i s a m a p p in g o f a p a r t o f t h e d i s k g r o u p . b e c a u s e t h e r e a r e i i i 四川大学硕士毕业论文 ( 2 0 0 4 ) d i ff e r e n c e s o f t h e 1 1 0 c h a r a c t e r s o f t h e a p p l i c a t i o n s y s t e ms o n d i ff e r e n t l o g i c a l d i s k s , t h e l o a d o f e a c h p h y s i c a l d i s k w i l l b e i m b a l a n c e p o s s i b l y . b a s e d o n t h e a b o v e - m e n t i o n e d , t h e l a r g e s t p e r f o r m a n c e p r o b l e m o f t h e s t o r a g e i s l o a d i mb a l a n c e i n t h i s p a p e r , a n e w s c h e m e b a s e d o n d i s k s t r i p i n g a n d g e n e t i c a l g o r it h m t o s o l v e t h e p r o b l e m i s p r e s e n t e d , i n c l u d i n g t h e f i l e p a r t it i o n a l g o r i t h m b a s e d o n d i s k s t r i p i n g a n d t h e f i l e a l l o c a t i o n a l g o r i t h m f o r l o a d b a l a n c e . i n d i s k s t r i p i n g t e c h n o l o g y , t h e r e a l i z a t i o n o f t h e d i s k l o a d b a l a n c i n g i s d e p e n d e d o n a p p l i c a t i o n p r o g r a m s o r f i l e s y s t e m s . b a s e d o n t h e i d e a o f p a r t i n g f i l e s , a l o a d b a l a n c e fr o m t h e p o i n t o f v i e w o f s t o r e d e v i c e i s g i v e n . o n t h e o t h e r h a n d , g e n e t i c a l g o r i t h m i s a n e w a l g o r i t h m t o s o l v e a n o p t i m i z a t i o n p r o b l e m . i n t h e g e n e t i c a l g o r i t h m , i t e x e c u t e s t h r e e s a m e a n d s i m p le g e n e t i c o p e r a t o r s : s e l e c t i o n , c r o s s o v e r a n d m u t a t i o n . i n t h i s a l g o r it h m , a n e ffic i e n t s e a r c h i n g i s e x e c u t e d i n c o m p l e x s p a c e s l e a d e d b y f i t n e s s v a l u e , u n t i l a c q u i r i n g t h e b e s t r e s u l t . t h e r e a r e t h r e e g e n e t i c o p e r a t i o n s : s e l e c t i o n , c r o s s o v e r a n d m u t a t i o n . t h e m a j o r i t y o f s e a r c h i n g i s c o m p l e t e d b y s e l e c t i o n a n d c r o s s o v e r , a n d t h e a b i l i t y o f a p p r o a c h i n g t h e b e s t r e s u l t i s im p r o v e d b y m u t a t io n . i n t h i s a l g o r it h m , t h e c h r o m o s o m e o f t h e t r e e i s r e p r e s e n t e d w i th t h e t r e e s t r u c t u r e c o d i n g . i n t h e d e s i g n o f c r o s s o v e r , w e f i r s t m e r g e t w o p a r e n t t r e e s t o a g r a p h , a n d t h e n c r e a t e a n e w t r e e f r o m t h e g r a p h . b a s e d o n t h e m e t h o d , t h e a l g o r i t h m h a s a g o o d p e r f o r m a n c e o f c r o s s o v e r . o u r s i m u l a t i o n r e s u l t s s h o w t h a t t h e p r o p o s e d a l g o r i t h m i s a b l e t o f i n d t h e r e s u l t w i t h f a s t s p e e d . c o m p u t e r s i m u l a t i o n s w e r e c o n d u c t e d t o e v a l u a t e t h e p e r f o r m a n c e o f t h e a l g o r i t h m i n t h e e n d o f t h i s p a p e r . t h e r e s u l t s s h o w t h a t t h e p ro p o s e d a l g o r it h m i s a c o r r e c t a n d e ff e c t i v e a l g o r it h m . s o i t s c o n s i d e r e d a s a g o o d p r o s p e c t i n s t o r a g e . k e y w o r d s : s t o r a g e , d i s k a r r a y , d i s k ma p p i n g , l o a d b a l a n c i n g , d i s k s t r i p i n g , g e n e t i c a l g o r i t h m i v 四川大掌硕士毕业论文 ( 2 0 7 4 ) 第一章绪 论 随着科技的高速发展， 计算机领域发生了巨 大的变化。 以 前许多 工作必须 由 主机系统才能完成， 现在这些工作却可以由 价格低廉但功能强大的计算机和 计算机集群完成。 尽管如此， 计算机所处理和产生的数据的重要性却没有改变， 因为一旦数据丢失， 所有的计算能力都变得毫无价值， 这就给数据存储技术提 出了新的挑战， 即必须提供对数据进行2 4 x 7 的可靠性操作和保护。 而存储作 为网络后台的核心设备， 就需要为整个网络上的各类应用提供海量存储、 高可 用数据库集群、 数据备份和容灾、 数据迁移、 网 络存储、 高 性能计算等等各类 服务。 存储技术既拥有物理成分，也拥有逻辑成分。物理成分包括磁盘驱动器、 电源、 冷却设备和连接等; 逻辑成分包括r a i d . 镜像、 卷管理软件等.卷管 理软件的目 的是把多个磁盘驱动器转映射成单一虚拟设备。从1 9 9 7 年以 来， 各 类存储技术层出 不穷， 有诸如f c . s a t a , i 9 c s i 等工业标准技术， 有d a s . n a s 和s a n等存储模式技术， 还有各类管理技术。 例如虚拟存储、 s a n管理 等等。 为提高数据存储的 可靠性和可用性， 各种新技术也应运而生， 目 前其主要 技术有: 使用磁盘镜像和复制提供数据冗余: 使用缓存实现性能的增强; 使用 r a i d增强可用性。 虽 川存储模式 1 , 1 一 1 d a s ( d i r e c t a t t a c h e d s t o r a g e ) 直连方式存储 d a s 也叫“ 服务器直连存储” ， 这是一种传统的存储方式， 在这种方式中， 存储设备是通过标准的 接门( 通常是s c s i 接口电缆) 连接到各种服务器或客 户端扩展接口下 如图1 - 1 所示) ，它完全以 服务器为中心，寄生在相应服务 器或客户端上， 其本身是硬件的堆叠， 不带有任何存储操作系统。 服务器通过 工 / 0 通道直接访问d a s中的 数据， 其存 放操作是将服务器上的文件系统通过 s c s i 通道把文件以 数据块方式一块一块地写到磁盘的磁道上;而读取时则把 四川大学硕士毕业论文 ( 2 0 0 4 ) 用于数据备份的网络带宽可以节约下来用于其他应用。 开放的、 业界标准的光 纤通道技术还使得s a n非常灵活。 s a n克服了 传统上与s c s i 相连的线缆限 制，极大地拓展了服务器和存储之间的距离，从而增加了更多连接的可能性。 改进的扩展性还简化了服务器的部署和升级，保护了原有硬件设备的投资。 此外，s a n可以更好地控制存储网络环境，适合那些基于交易的系统在 性能和可用性方面的需求。s a n利用高可靠和高性能的光纤通道协议来满足 这种需要。 s a n 的另一个长处是传送数据块到企业级数据密集型应用的能力。在数 据传送过程中，s a n在通信结点 ( 尤其是服务器)上的处理费用开销更少， 因为数据在传送时被分成更小的数据块。因此，光纤通道s a n在传送大数据 块时非常有效，这使得光纤通道协议非常适用于存储密集型环境。 近两年来，s a n这一概念已经渐入人心。s a n可以取代基于服务器的存 储模式， 性能更加优越。 然而， 时至今日， 互操作性仍是实施过程中存在的主 要问题。s a n 本身缺乏标准，尤其是在管理上更是如此。 s a n存储区域网络的最大挑战是其构建和管理的复杂性。 但s a n解决方 案同 样会面对带宽或系统响 应时间的 挑战。 对于绝大多数业务而言， 高效的 对 客户机数据传送能力其实比流式数据传送( 带宽) 更重要。 大部份服务器都存在 着i / 0 瓶颈的问 题， 对于已 经出现i / 0 瓶颈问题的系统而言， 单是增加一个高 速的存储控制卡之类的设备根本无补于事。 1 . 2磁盘阵列负载均衡解决方案 1 . 2 . 1存储子系统 存储子系统是指一组存储设备的 集合。 这些设备享有共同的电 源分布、 包 装或管理系统策略， 比如r a i d磁盘阵列系统和磁带库。 这两种类型的 子系统 包含一个以上的设备，但在工 / 0 通道上就像单一的系统一样工作。 存储子系统在存储总线或网络上拥有一个或多个地址， 而在存储子系统中 的设备则作为与更高级 i d相联系的l u n寻址。另一种常见的方法是利用虚 拟化技术， 将子系统中的设备看作一个单个的大设备， 这可以通过一个完全分 离的且独立的i / 0 总线或网络来实现。这些i / 0 总线或网络处于子系统内部， 四1 1 ! 大学硕士毕业论文 ( 2 0 0 4 ) 连接所有内部设备。 内部的总线和网络由一个子系统控制器管理， 以 此来屏蔽 子系统内部设备通信的复杂性。 1 . 2 . 2 r a i d磁盘阵列 r a i d 廉价冗余磁盘阵列， 是r e d u n d a n t a r r a y s o f i n 姻:)e n $ z d c d i s k s 的 简称。 磁盘阵列可以分为软阵列和硬阵列两种。软阵列就是通过软件程序来完 成，并由计算机的处理器提供运算能力。但是这种软阵列只能提供最基本的 r a i d容错功能。 硬阵列是由独立操作的硬件 ( 阵列卡)提供整个磁盘阵列的 控制和计算功能，卡上具备独立的处理器，不依靠系统的c p u资源， 所有需 要的容错功能均可以支持，所以 硬阵列所提供的功能和性能均比软阵列好。 作为高性能的存储技术， r a i d已 经得到了 越来越广泛的应用。 r a i d的 级别从r a i d概念的提出到现在， 已经发展了很多个级别， 但是最常用的是0 , 1 , 3 , 5四个级别。下面就分别介绍一下这四个级别。 r a i d 0 : 把多个磁盘合并成一个大的磁盘， 不具有冗余功能，并行工 / 0 速度最快。 它是将多个磁盘并列起来， 成为一个大硬盘。 在存放数据时， 其将 数据按磁盘的个数来进行分段，然后同时将这些数据写进这些磁盘中。所以， 在所有的级别中，r a i d 0 的速度是最快的。但是r a i d 0 没有冗余功能，如 果一个磁盘 ( 物理) 损坏，则所有的数据都无法使用。 r a i d 1 : 两组相同的磁盘系统互作镜像， 速度没有提高， 但是允许单个 磁盘出 错，可靠性最高。 r a i d 1 就是镜像。其原理为在主硬盘上存放数据的 同时也在镜像硬盘上写一样的 数据。 当主硬盘 ( 物理) 损坏时， 镜像硬盘则代 替主硬盘的工作。因为有镜像硬盘做数据备份， 所以r a i d 1 的数据安全性在 所有的r a i d级别上来说是最好的。但是其磁盘的利用率却只有5 0 % ， 是所有 r a i d上磁盘利用率最低的一个级别。 r a i d 3 :存放数据的原理和r a i d 0 , r a i d 1 不同。r a i d 3 是以一个硬 盘来存放数据的奇偶校验位， 数据则分段存储于其余硬盘中。 它像r a i d 0 一 样以 并行的方式来存放数据， 但速度没有r a i d 0 快。 如果数据盘 ( 物理) 损 坏， 只要将坏硬盘换掉， r a i d控制系统则会根据校验盘的数据校验位在新盘 中重建坏盘上的数据。利用单独的 校验盘来保护数据虽然没有镜像的安全性 四i l l 大学硕士毕业论文( 2 0 0 4 ) 高，但是硬盘利用率得到了很大的提高，为n - 1 。 但缺点是作为存放校验位的 硬盘， 工作负荷会很大， 因为每次写操作， 都会把生成的校验信息写入该磁盘， 而其它磁盘的负荷相对较小，这会对性能有一定的影响。 r a i d 4 :使用一个校验磁盘，但和r a i d 3 不一样。 r a i d 4 是以 扇区作 数据分段， 各磁盘相同位置的分段形成一个校验磁盘分段， 放在校验磁盘。 这 种方式可在不同的磁盘上平行执行不同的读取命今， 从而大幅提高磁盘阵列的 读取性能: 但在写入数据时， 因受限于校验磁盘， 同一时间只能作一次。 即使 如此， 小型档案的写入仍然比r a i d 3 要快，因为其校验计算比较简单而非做 位( b i t l e v e l ) 的计算。但校验磁盘造成了r a i d 4 的瓶颈，降低了其性能。因 此由于r a i d 5 的出现而使得r a i d 4 较少使用。 r a i d 5 : 在r a i d 3 的基础上， r a i d 5 进行了一些改进，当向阵列中的 磁盘写数据时， 奇偶校验数据均匀存放在阵列中的各个盘上， 允许单个磁盘出 错。r a i d 5 也是以数据的校验位来保证数据的安全，但它不是以 单独硬盘来 存放数据的校验位， 而是将数据段的校验位交互存放于各个硬盘上。 这样， 任 何一个硬盘损坏， 都可以根据其它硬盘上的校验位来重建损坏的数据。 其硬盘 的利用率也是n - 1 0 1 . 2 . 3 磁盘负载均衡影响存储子系统 i / 0 性能主要因素 通常 现存的 服 务 器是 通过 一 个专 用的in p u t/ o u t p u t q / o ) 子系 统 与l a n , s a n( 存储区 域网络) 直接连接的。 这种专用子系统是由 冗余的p c i 总线、网 卡等组成的。 在许多情况下， i / 0 子系统在决定整个系统性能中扮演着非常重 要的角色。 这个角色的相对重要性在过去2 5 年中逐渐增大，并在将来更是如 此。 其原因主要有两点:首先， i / 0 子系统的组成部分相对于整个系统中的其 它部分发展比较缓慢。例如， 微处理器性能的增长速度是每年3 5 % - 5 0 % ， 而磁 盘驱动器性能的增长速度却只有 5 % - 2 0 % ，照此趋势发展下去，具有大量 i / 0 请求的应用系统将会越来越受到i / 0 子系统的限制。 其次， 技术的发展产生了 许多新的应用， 也使许多己有的应用得到了很大的扩展， 而这些都极大地依赖 于i / 0 性能的增加。因此随着i t 技术的高速发展，工 / 0 子系统逐渐成为了各 快速增长系统中的一个瓶颈。 目 前比 较广泛的 解决方法是在存储子系统中 增加 四川大学硕士毕业论文 ( 2 0 0 4 ) 新的磁盘驱动器。 而为满足对容量快速增长的需求，存储子系统中的磁盘数量也在不断增 加. 这就逐渐产生了 磁盘阵列。 大型磁盘阵列内部一般采用r a i d结构以 提高 可靠性和i / 0 性能 它通常按照r a i d标准将多个物理磁盘组成一个磁盘组， 客户系统所看到的磁盘并非实际的物理磁盘， 而是逻辑磁盘， 每个逻辑磁盘映 射到某个磁盘组上的一部分。目 前常用的r a i d标准为r a i d s 。按照r a i d s 标准， 一个逻辑磁盘由磁盘组中的各个物理磁盘的相同部分构成。 逻辑磁盘的 负载是由访问它的应用系统的i / 0 特征所决定。 磁盘组的负载为映射到该磁盘 组中的所有逻辑磁盘的负载之和， 而根据r a i d s 结构的特点，同一磁盘组中 的各个物理磁盘的负载是均匀的， 即这些物理磁盘的负载等于该磁盘组的负载 除以 其中的物理磁盘的个数。由 于不同的 逻辑盘上应用系统的工 / 0 特征不同， 很容易造成各磁盘组之间的物理磁盘的负载不均。 因此可以说，目 前提高存储 子系统的工 / 0 性能的最大障碍就是负载不均衡或称为磁盘偏移。 所谓负载不均衡是指存储子系统中的一些磁盘驱动器所接受的数据访问 量远大于另外一些磁盘驱动器。 这种偏移通常是引用“ 8 0 / 2 0 规则” 或“ 9 0 / 1 0 规则” 。 8 0 / 2 0 规则”是指2 0 % 的资源 ( 磁盘驱动器)接受8 0 % 的i / 0 量， 而剩下的8 0 % 的资源仅接受2 0 % 的工 / 0 量。 更进一步， 就是2 0 % 资源的2 0 % 接受 8 0 % i / 0量的 8 0 % ，以 此循环类推。 在这种负载不均衡的情况下， 大量的 工 / 0 请求在队列上等待某些正处于忙状态的磁盘， 请求的响应时间大大增加， 而其 它的磁盘却处于空闲状态，从而在整体上大大降低了系统的吞吐量。 1 . 2 . 4磁盘阵列负载均衡解决方案 要提高存储子系统的 工 / 0性能，关键就是要研究一种有效的算法实现磁 盘之间的负载均衡。 目 前主要有使用动态数据存放技术实现磁盘间的负载均衡 和基于分条技术的负载均衡方法。 1 . 2 . 4 . 1动态数据存放技术 在传统的磁盘子系统中， 存放在磁盘上的数据被认为是相互独立的， 而在 逻辑上是连续的。 图1 - 4 显示了 在一个具有四个独立磁盘的磁盘阵列中， 数据 四川大学硕士毕业论文 ( 2 0 0 4 ) 块在逻辑空间中的存放。 图1 - 4动态数据存放 在这种系统中， 主要使用的负载均衡方案就是动态数据存放技术。 动态数 据存放技术需要对在整个活动的多个重要时期内 所收集的数据进行性能分析， 然后将疑为热点的数据从一个磁盘移到另一个磁盘，从而解决负载不均的问 题。 这种重复的过程与其说是一门 科学， 不如说是一门艺术， 因为它通常需要 系统管理人员或专家顾问操作实现。 这些系统管理人员或专家顾问 们通常都是 根据他们的经验和可靠的信息对数据的重新分配做出一个科学的估计。 举个例 子来说， 在某些情况下， 人们可以 通过获取有关每个磁盘的平均工作量的信息， 将处于忙状态的磁盘上的数据与相对空闲磁盘上的数据进行交换。 而在决定磁 盘存放时， 许多比较好的策略还会考虑到个体数据组的信息， 以及未来的发展 变化。 但是这种使用动态存放技术来实现负载均衡的方法存在两个主要的问 题: 首先， 它的耗费是相当昂贵的。 一天中对数据的收集， 考虑是否需要或怎 样重新分配数据所需要的时间，以及在数据重新分配时对磁盘的大量访问 等， 这些都会导致系统性能的降低。 这就需要安排在活动量少或没有活动的时间来 执行，以免严重影响系统性能。因此对人力的消耗是非常大的。 其次， 在解决负载不均的问题上， 动态数据存放的成功率是很低的。 其原 因是:1动态数据存放方案必须处理基本数据组，所谓数据组是指构成一些 单独的逻辑单元的数据，这些数据是以 逻辑单元的形式存放在存储子系统中。 在一个传统的 存储子系统中， 数据的一个逻辑单元必须完全存放在一个单独的 四川大学硕士平业论文( 2 0 0 4 ) 磁盘上。这就从很大程度上阻碍了动态数据存储方案解决偶校验固定负载不 均。 2 . 扩散负载不均是动态数据存储方案所面临的另一个难题。如果 1 / o模 式的变化非常缓慢， 那么它只是一个简单的问题。 但是， 我们知道在许多情况 下负载不均的扩散是非常快的。 扩散负载不均使得在一个测量过程中， 不能根 据当前的磁盘热度精确预测将来的磁盘热度。 因为热点扩散得过快， 数据存储 无法根据热度的变化进行调节， 所以 必须为随时间变化的热点进行单独存放以 实现负载均衡。 这个要求以 及基本数据组问 题更加加大了 确定一个好的数据存 储方案的难度。 1 . 2 . 4 . 2磁盘分条技术 磁盘分条，也称为磁盘交叉，是将多个磁盘地址空间合成一个在主机看 来是单独的、 统一的空间。 这主要是通过一种循环的方法在磁盘上分配连续的 逻辑数据单元 ( 称为分条单元) 来实现的。 磁盘分条技术主要包括多个磁盘数 据空间的结合和数据在这些磁盘上的分布。 例如， 第一个分条单元在第一个磁 盘上， 第二个分条单元在第二个磁盘上， 以 此类推， 第n个分条单元在第( n - 1 m o d m) + 1个磁盘上，其中m表示总的磁盘数。其分布如图1 - 5 所示。 图1 - 5分条数据存放 夸 1 . 3本文所做的工作及内容安排 存储子系统的 工 / o性能问题一直以来都是人们比较关注的问题，它对计 四川大学硕士毕业论文 ( 2 0 0 4 ) 算机系统的整体性能起着决定性作用。因此各种关于 i / 0性能的研究逐渐增 多。 而要提高工 / 0 性能， 关键就是要解决阻碍其提高的障碍，目 前，阻碍工 / 0 性能的最大障碍就是磁盘负载不均衡。 本文在前面己经介绍了目 前实现磁盘负载均衡的两种主要技术:动态数 据存放技术和磁盘分条技术。 这些技术都是从应用程序或者文件系统的角度来 考虑负载均衡， 而没有从存储设备的角度来考虑负载均衡问 题。 从存储设备内 部进行负载均衡也是一种有效的方法， 目 前部分大型磁盘阵列已 经提供数据迁 移功能， 可以在各个磁盘组之间交换逻辑磁盘， 但一般需要管理员来决定数据 迁移的方案。 遗传算法是近年来提出的一种新型优化算法，也可以说是一种通过模拟 生物的遗传进化机制来进行搜索寻优的方法。 它从某一初始种群出发， 执行一 定的杂交、变异等操作， 不断迭代计算， 逐步逼近最优解。 遗传算法具有并行 搜索、种群寻优等优点。 原则上，数据的放置问题可以 看作是一个文件的分配问题，这个问题早 己 被广泛深入研究而且被认为是一个n p 完全问题。 因此， 其各种解决方案也 是层出 不穷的。 其中 文献【 4 介绍了 一 种在磁盘阵 列中 实现数据分配和动态负 载均衡的自 适应方法。 它的基本思想是分配并合理地迁移数据使得磁盘阵列中 的磁盘负载量变化减小。这个思想来源于减少在一特定时间里 “ 负重” 磁盘 的负载变化量， 但这要求其负载量与具有稳态访问 特征的时间间隔的长度成比 例，并且对它的访问具有周期性变化的特征。这种周期性变化是可以预测的， 比 如在晚上进行批处理的联机事务处理 ( o l t p )系统.我们可以 将数据的迁 移称之为 “ 磁盘降温” ，其目 的是将具有最高温度 ( 即热度与数据大小的商) 的数据从热磁盘移到冷一些的磁盘，当然这还要考虑到数据迁移的开销。 文献中许多磁盘负载均衡解决方案都是关注于静态数据的分配及通过数 据 冗余 来 提高 其 性能。 文 献 3 通 过 对r a i d磁 盘阵 列内 逻 辑 磁盘 和物 理 磁 盘 之间的映射和负载关系进行分析， 提出了基于遗传算法的物理磁盘间负载均衡 方法，以提高磁盘阵列的吞吐量。 不过，该方法仅从存储设备的角度来考虑， 而不是从应用程序或文件的角度来考虑的，并且其只限于考虑静态数据的分 配。 n 四川大学硕士毕业论文 ( 2 0 0 4 ) 因 此， 本文参考了 文献 3 、 文 献【 4 等诸多 文 献， 提出了 一 种用遗 传算法 来实现基于分条技术的动态负载均衡的方法。 该方法包括基于分条技术的文件 戈 ii 分算法和为实现负载均衡的文件分配算法。 本文的主要内容及安排如下: 第一章 对目 前的存储技术进行简要介绍，指出存储子系统的1 / 0 性能的重要 性并提出有待解决的问题:磁盘负载均衡问题。 第二章 详细介绍磁盘负载均衡的解决方案:分条技术。并设计基于分条技术 的磁盘阵列模型。 第三章 介绍遗传算法的基本原理及其特征。 第四章 给出了一种用遗传算法来实现基于分条技术的磁盘负载均衡的方法的 具体实现。其中包括: 1 . 编码方式的选择，即将磁盘映射方案以某种方式表示成基因序列。 a . 对适应度函数的设计，适应值是用来衡量种群中个体好坏的标准， 也是两个个体被选择来进行杂交的一个依据。 3 . 选择、杂交和变异算子的设计。 第五章 对该算法进行了实验仿真和性能分析。 第六章 结论 四川大学硕士毕业论文 ( 2 0 0 4 ) 第二章 基于分条技术的磁盘阵列模型设计 2 . 1 磁盘分条技术概述 2 . . i 分条技术的产生背景 大磁盘阵列是由 许多容量较小的 磁盘所组成的( 比 如r a i d s ) ， 它在开销、 容量、 效率等方面都优于单独的大容量磁盘。 除此以外， 磁盘阵列还具有较高 的i / 0 性能 因为它可以利用多个磁盘的带宽来实现并行处理一个单独的逻辑 请求或多个独立的请求。 而随着存储技术的发展， 磁盘阵列的逻辑结构也由一 个单独的逻辑设备发展为更加通用的基于松偶合磁盘和标准通道结构的多磁 盘系统。 在本文中， 我们假设操作系统能够分别地访问磁盘， 而不是将所有磁 盘绑定为一个单独的逻辑设备。 为了有效地利用磁盘阵列的 1 / 0并行的潜力，我们可以将文件进行分块 并分配到多个磁盘上。 文件分条是一项文件组织技术， 它将文件分成多个逻辑 上连续的块 ( 称为“ 分条” ) ， 然后将这些分块分布到多个磁盘上， 从而减少 单个请求的传输时间或提高多个请求的吞吐量。 分条单元数就表示存储在每个 磁盘上的连续的逻辑数据块的个数。 当一个磁盘阵列处理一个应用时，该磁盘阵列所表现出的 i / 0并行的潜 力水平依赖于该应用数据的分布。 一个文件的 划分决定了处理该文件的单个请 求的并行性水平， 而文件的分块在磁盘上的分配决定了 磁盘阵列的负载均衡。 因此，请求内在的并行性和负载均衡最终共同决定了请求的吞吐量和有效速 2 分条技术的定义 磁盘分条，也称为磁盘交叉，是将多个磁盘地址空间合成一个在主机看 01. 度2. 来是单独的、 统一的空间。 这主要是通过一种循环的方法在磁盘上分配连续的 逻辑数据单元( 称为分条单元) 来实现的。 磁盘分条技术主要包括多个磁盘数 据空间的结合和数据在这些磁盘上的分布。 例如， 第一个分条单元在第一个磁 四i l l 大学硕士毕业论文 ( 2 0 0 4 ) 盘上， 第二个分条单元在第二个磁盘上， 以此类推， 第n个分条单元在第 n - 1 m o d m) + 1个磁盘上，其中m表示总的磁盘数。其分布如图2 - 1 所示。 国因目 日日口“ 图2 - 1分条数据存放 2 . 1 . 2 . 1 分条技术的类型 分条技术主要有两种类型，即细粒度分条方式和粗粒度分条方式 ( 如图 2 - 2 所示) 。 ao i i al ! i a2 b o i i bi i i b 2 ( a ) 细粒度分条 ( b )粗粒度分条 图2 - 2分条方式 细粒度分条是指将所需存取的每一个数据块分配在磁盘阵列中的 所有的 四州大学硕士毕业论文 ( 2 0 0 4 ) 磁盘上， 即每一个磁盘都包括了数据块的一部分。 因此， 通常所选择的磁盘数 和分条单元的大小决定了 最小 化存取数据单元的大小。 一般情况下， 细粒度分 条的分条单元的大小为i b i t 、 一个字节或是一个磁盘扇区( 通常为5 1 2 个字节) 。 一旦每一个存取单元被平均分布在所有的磁盘上， 那么分条单元的大小就不是 那么重要了。 因为所有的磁盘都承担了一定的工作量， 这就完全实现了负载均 衡。对于有效传输率来讲，它的传输率几乎是一个单独磁盘 n倍 设阵列中 的 磁盘数为n ) ，因为平均每一个磁盘仅需传输1 ! n的数据。然而，这种分条 技术会使存取中的定位过程 ( 寻道和磁盘旋转) 增多。 并且在同一时间只能处 理一个请求， 因为所有的磁盘都在为这一请求工作。 通常在对传输时间的要求 高于处理时间的情况下，细粒度分条的这种局限性愈加明显。 而对于粗粒度分条方式来说， 并不是所有的磁盘都参与到对每一个请求的 处理当中， 粗粒度分条扩展了 对大请求的数据传输的并行性， 同时也允许各单 独磁盘并发地处理小的请求。 它结合了各种优点以实现自 动的负载均衡: 首先， 一个热点文件将逐渐把自己的组成块分布到多个磁盘上， 也就是扩散其数据请 求。 其次， 如同哈希法， 粗粒度分条通过一个简单的公式为每一个存取请求随 机确定第一个磁盘， 然后以 依次循环的方法确定其它磁盘。 据统计， 在高度注 重访问 模式和快速改变存取分布的 情况下， 这种方式能够保持负载均衡的完整 性。 然而， 当热点小于分条单元时， 负载不均的问题仍然存在。 粗粒度分条很 容易形成热点，因为热门文件 ( 比如v i d e o 或a u d i o )的点播率非常高，这就 使得存储这些文件的区域成为热点，造成系统服务的堵塞。 总的来说， 细粒度分条方式和粗粒度分条方式各有其优缺点: 细粒度分条 的并发性较差， 但它实现了最大的负载均衡， 不会出现热点现象。 细粒度分条 适合应用于对并发性要求不高， 而对服务质量要求很高的点播服务。 粗粒度分 条的并发性能好， 但是容易出 现热点现象。 它适合于对并发性能要求很高的应 用环境。 2 . 1 . 2 . 2分条单元的选择 磁盘分条技术已被许多公司作为提高数据带宽的方法， 以满足在多个磁盘 上并行传输和读取数据的要求。 除此以外， 还有很多 对有关磁盘分条技术在性 四i l l 大学硕士毕业论文 ( 2 0 0 4 ) 能方面影响的研究。 这些研究表明 在使用多个磁盘驱动器处理一个请求和使用 一个磁盘驱动器处理多个请求之间 存在一种明确的折衷方案。 这种折衷方案主 要体现在对分条单元大小的 选择上。 要想获得分条技术的性能潜力， 就需要对 分条单元的大小做出正确的选择。 这个选择能从根本上决定每一个数据请求可 以分布到多少个磁盘上。 若分条单元比较大， 每个磁盘可以单独处理一个请求， 则多个磁盘就能够并行处理多个请求， 从而减少总的定位延迟