（计算机软件与理论专业论文）基于中心数据库的作业调度系统的研究与实现.pdf

中山人学坝1 1 论殳 坫十中心数据库的作业训度系统的研究，实现 基于中心数据库的作业调度系统的研究与实现 计算机软件与理论 硕士研究生：钟永安 指导教师：倪德明副教授 摘要 在分布式处理环境中，作业分配和调度的一个主要目的是平衡各处理机问的 负载，并以此提高并行处理的效率。静态作业分配是指在计算前就被指派给确定 的计算机。这种分配方式虽然简单，但是它很难适用于那些具有动态特性的应用 问题。在那些问题中，作业的计算量是难以估计的，而且网络下的工作环境又是 动态可变的，为了提高这类作业的并行求解效率，系统需要有作业动态的调度能 力。 本文以分布式软件系统n e t b u n k e r 数掘备份恢复系统为研究背景，在 n e t b u n k e r 系统的基础上，引入“惰性”作业分配方法，以中心数据库为作业调 度的负载信息中心，提出一个符合n e t b u n k e r 实际需求的算法，设计了具有单一 系统映像的作业调度系统，该作业调度系统将n e t b u n k e r 的介质服务器在逻辑上 组织起来以形成集群工作组，并通过了中心数据库对集群工作组进行管理，优化 了系统，屏蔽了由于网络或者单个介质服务器的不可靠性带来的问题，有效地管 理备份恢复作业，并提高了备份作业的并行执行效率。 关键词：分布式、作业调度、负载平衡、作业调度、中心数据库 中山人学砸i 论殳 摧十中心数据库的作业调度系统的研究：窭脱 r e s e a r c ha n di m p l e m e n t a t i o no fj o bs c h e d u l i n gs y s t e m b a s e do nc e n t r a ld a t a b a s e n a m e ：z h o n gy o n g a n s u p e r v i s o r ：a s s o c i a t ep r o f n id e m i n g a b s t r a c t i nd i s t r i b u t e dp r o c e s s i n ge n v i r o n m e n t ，o n em a i np u r p o s ei st ob a l a n c el o a d s a m o n gp r o c e s s o r ss o 嬲t oi m p r o v ep a r a l l e lp r o c e s s i n ge f f i c i e n c yw h e nj o b sa r e a s s i g n e da n ds c h e d u l e d s t a t i cj o bs c h e d u l i n gi sak i n do fs c h e d u l i n gw a yi nw h i c h j o b sa r ea s s i g n e dt od e f i n i t ec o m p u t e r sb e f o r ec o m p u t i n g t h i ss c h e d u l i n gw a yi s s i m p l e ，b u ti td o e s n ta d a p tt h ea p p l i c a t i o np r o b l e m st h a th a v ed y n a m i cf e a t u r e s i n t h o s ep r o b l e m s ，i ti sv e r yd i f f i c u l tt om e a s u r et h eq u a n t i t yo f j o b s c o m p u t i n g , a n dt h e w o r ke n v i r o n m e n ti sa l s o d y n a m i cc h a n g ei nn e t w o r k t oi m p r o v ee f f i c i e n c yi n p a r a l l e ls o l u t i o nt ot h ek i n do fj o b s ，t h es y s t e mm u s th a v et h ec a p a b i l i t yt h a tc a r l s c h e d u l et h ej o b sd y n a m i c a l l y t h er e s e a r c h b a c k g r o u n d o ft h i s p a p e r i sb a s e do nn e t b u n k e rd a t a b a c k u p a n d - r e c o v e rs y s t e m ，w h i c hi sad i s t r i b u t e ds o f t w a r es y s t e m w er e f e raj o b s c h e d u l i n gm e t h o dc a l l e d ”i n e r t i a ”，r e g a r dc e n t r a ld a t a b a s ea sc a t t i e ri n f o r m a t i o no f j o bs c h e d u l i n gl o a d t h e nw ed e s i g naj o bs c h e d u l i n gs y s t e mw i t hs i n g l es y s t e m i m a g ei nt h ep a p e rb a s e do nt h en e t b u n k e rs y s t e m t h ej o bs c h e d u l i n gs y s t e m l o g i c a l l yo r g a n i z e sm e d i u ms e r v e r si nt h en e t b u n k e rs y s t e ms oa st of o r mc o l l e c t i v e c l u s t e rw o r kg r o u p ，a n dm a n a g e st h e g r o u pb yc e n t r a ld a t a b a s e t h en e t b u n k e r s y s t e mi so p t i m i z e da n ds h i e l d st h ei n s e c u r ep r o b l e ma sar e s u l to fn e t w o r ka n do n e m e d i as e r v e r i tm a n a g e se f f e c t i v e l yt h eb a c k u pa n dr e c o v e r yj o b s ，a n di m p r o v e st h e e f f i c i e n c yo f p a r a l l e le x e c u t i o n k e y w o r d s ：d i s t r i b u t e d ；j o bs c h e d u l i n g ；l o a db a l a n c i n g ；j o bm a n a g e m e n t ： c e n t r a ld a t a b a s e 中山人学帧i 论文璀十中心数据库的作业调度系统的目f 究o 实现 第1 章引言 1 1 作业调度系统的概述 作业调度系统是建立在操作系统之上的一种系统软件，处于应用软件和操作 系统、网络协议等之间的一个软件层。其主要作用是强化操作系统的作业调度功 能，提供作业批处理排队、作业提交、调度、执行及控制的新机制，更加有效地 利用系统资源、均衡网络负载、提高系统整体性能。 计算机发展早期，计算机主要以大型机为主，作业调度主要是通过批处理的 方式对作业进行运行，并在作业提交和处理的过程中由批处理系统进行统一管 理。这种批处理系统就是最早的作业调度系统，属于操作系统的一个子系统。 随着计算机技术的发展，网络技术的出现和计算机的小型化发展，尤其是网 络的出现，作业调度发生了根本的变化。大型机的计算机任务可以被分配到多个 工作站，通过各个工作站的相互协作完成，但是工作站虽然可以完成更多任务， 可惜资源利用率很低。网络队列系统n o s ( n e t w o r kq u e u i n gs y s t e m ) 便由此产 生。网络队列系统n q s 对批处理系统进行了扩展，引入队列的概念，从操作系统 中分离出来，是一个独立的系统管理软件。 随着高性能工作站、集群系统的发展，作业调度系统也发展到支持异构的网 络环境、支持多平台、支持并行应用等新需求的一个阶段。作业调度系统作为集 群系统应用软件的重要组成部分，基于集群技术的作业调度系统在许多领域都得 到了广泛的应用，尤其是在高性能计算领域和商业信息处理领域都发挥着举足轻 重的作用。一些大型研究机构和公司都将作业调度系统作为提高生产效率、提高 资源利用率的一项重要技术，并面向实际需求开展了大量的研究与- 丌发工作。通 过对n o s 系统进行扩展或重新设计，产生了许多公用的或商业化的作业调度系 统，其中颇具代表性和影响力的作业调度系统有：n a s a 与m r j 公司共同开发的 p b s ( p o r t a b l eb a t c hs y s t e m ) ，威斯康星大学开发的集群作业调度系统c o n d o r ， 加拿大pl a t f o r m 公司研发的负载共享软件l s f ( l o a ds h a r i n gf a c i l i t y ) 以及 i b m 开发的集群作业调度系统l o a d l e v e l e r 。 作业调度的主要功能有： 中山人掌坝l 论史 毕十中心数捌库的行业调度系绩的州究j 实现 ( 1 ) 作业定义功“r i m ：提供完备的作业生成、修改，删除、更名、复制、存 储等功能。 ( 2 ) 作业提交力能：提供便捷的作业及时提交与定时提交功能。用户可以 根据需求，创建r 历及提交时刻表，系统将按照提交计划自动提交。 ( 3 ) 作业监控功能：监控作业的执行状态，查看作业的执行结果，对执行 作业进行各种控制，包括执行过程中重新修改作业及属性定义。 ( 4 ) 作业调度功能：通过适当的调度策略，对提交的作业进行合理的调度 和运行，提高系统性能。 ( 5 ) 资源管理功能：包括对机器、队列，请求等资源进行统一管理并合理 分配。比如，建立机器组；在机器组中的任何机器上新建队列，设定队列的属性、 优先级：查看机器中的队列状况、队列中的请求状况。 1 2 在数据备份中作业调度的研究 1 2 i 数据备份的概述 世界著名的数据备份专家w c u r t i sp r e s t o n 0 1 在其名著( u n i xb a c k u pa n d r e c o v e r y 一书中对备份做出如下定义： 备份= 拷贝+ 管理 这个简洁的公式，表明了数据备份中的主要问题，所谓拷贝，就是对数据执 行移动，复制等，所谓管理。就是对备份数据进行索引。 2 0 0 4 年，在第十三届全国信息存储技术与学术会议上 0 2 ，国内著名存储 技术专家华中科技大学谢长生教授在大会报告上提出“计算机领域的问题可分为 三大类，计算，通信i 存储。存储技术解决数据在时间上传播的问题，通信技术 解决数据在空间上传播的问题，而计算技术则解决数据变换的问题”。由此可见， 数据备份在本质上是计算，通信，存储三大领域技术的综合。 基于i n t e r n e t i n t r a n e t 的应用环境下的备份是整个企业作业流程依赖于 n t e r n e t i n t r a n e t 网络环境：网络应用复杂化，计算模式由c s 至b s 到 p e e r t o p e e r 复杂多变，数据种类增加，异种数据库、多种文件系统和操作平 台呈现在异构的企业计算机网络中：数据量剧增，存储空间增大；数据存储位置 2 中山人学坎i j 论文雉十中心数据库的作业粥瞳系缝州究i 实堰 变得分散：出现n a s 和s a n 存储机制，备份技术在结构上也得到了长足的发展， 从l a nf r e e 备份到无服务器备份，基本工作机制也逐步得到更新 研究性的备份系统以对文件系统备份居多，对数据库备份较少，下面就简单 介绍几个。 ( 1 ) a m a m d a 网络备份管理器 0 3 。由马晕兰大学p a r k 学院丌发，用束简化 网络上很多u n i xt 作站并行备份，它使用标准u n i x 备份程序比如d u m p 和t a r 等，为了得到最佳的备份性能，a m a n d a 并行地写多个备份集到一个临时的磁盘 罩，之后再以最大速度把数据以数据流的方式写到磁带上。 ( 2 ) s g i 公司的t b 数量级的数据备份 0 4 ，s g i 公司实现了一个备份系统包 括一个o r i g i n2 0 0 0 服务器，1 3 8 个磁盘，6 6 个u l t r a s c s i 通道，3 8 个i b m 3 5 9 0 磁带驱动器。这个系统达到使用l e g a t o 和c a 的备份软件，在不到1 个小时执行 完成1 t b 级别的o r a c l e 7 数据库的备份。 ( 3 ) p e t a l 系统 0 5 ，由d e c 公司的系统研究中心研制，它提供一个机制允 许网络内引互连接的服务器合作管理一个物理磁盘池，这个磁盘池对每一个服务 器看来就是一个大的虚拟磁盘。p e t a l 实现了一个写时复制( c o p y o n w r i t e ) 快 照机制，当创建快照时，p e r a l 很短暂地暂停应用的执行( 少于1 秒钟) ，快照 可以保持在线地对以前版本的数据地快速访问。为了创建一个虚拟的磁盘备份， p e t a l 仅仅利用象t a r 那样的实用程序简单地复制一个快照到归档设备上去。 ( 4 ) p l a n9 计算环境 0 6 ，它是由a t & t 贝尔实验室开发的一个新的分布式 操作系统，它包括对快速文件访问保持有磁盘文件缓存( c a c h e ) ，每只进行盼在 线备份是通过创建文件系统的快照来作的，它也是使用写时复制机制，它“冻结” 住文件系统的状态，对“冻住”的数据的复制作随后的更新。因为旧的文件没有 被删除，所以用户能够裉据还原单个文件或完全文件系统到以前日期对应的状 态，文件访问许可的维护也是在快照复制上作。 目前备份软件市场上商业领域的备份系统主要被c a 、v e t i t a s 、l e g a t o 和 i b m 四大公司所占领。 1 2 2 本文的研究背景 中山大学软件研究所和广州威腾网络科技有限公司合作的数据备份系统项 3 中山j 、学坝i 论义 草十中心数据席的仃业调度系统的州究实现 目，着力研究数掘备份领域的关键问题和技术，并建立了理论模型 0 7 、备份通 用模型和存储模型等。2 0 0 3 年1 1 月成功丌发了第一版，并于2 0 0 3 年9 月2 9 同 通过广州市科技局的鉴定，于2 0 0 3 年l1 月通过国家软件评测中心的测试，2 0 0 4 年获得了广东省科技进步三等奖。该软件的1 5 版己经被珠海市政府采用，用户 评价极高。目前已经推出第二版，架构更加稳定，功能更加强大，性能更加优越。 本文是作者在参与该项目的过程中，在前期工作的基础之上，根据 n e t b u n k e r 0 8 数据备份系统中面临的实际问题和产品研发中的具体需求，提出 的备份系统中的作业调度模型，对模型进行研究和分析，并在此基础上实现了作 业的分配与再分配以及作业调度负载平衡算法。 1 2 3 存在的问题及解决办法 本课题以当前开发的n e t b u n k e r 备份软件为研究背景，结合当前数据备份实 际现状，对现实需求的软件产品进行建模，并在开发过程中将设计模型实现，并 将丌发的软件在实际中应用，严格按照软件工程的思想进行。 在传统的设计中，备份服务器只是简单的备份信息中心，这种条件下本地资 源的安全性与备份性能得到保证，但是不适合只益复杂的网络环境。在网络环境 下，如何将网络环境中分布的资源整合起来，如何对备份作业迸行调度分配，备 份服务器如何和介质服务器和客户代理端进行协调通信以完成一个备份作业，充 分利用集群下的介质服务器工作组提高并行执行效率，这将是备份服务器的首要 工作。 本课题中丌发的备份软件n e t b u n k e r 一方面要提供安全的本地资源管理和 备份作业调度，同时要满足备份作业复杂的网络环境，由此提出将备份服务器的 作业调度模型以及负载平衡算法。 主要工作集中在： ( 1 ) 分析了作业调度的体系结构并提出了作业调度的三层模型： ( 2 ) 引入了“惰性”作业的分配方法，作业执行与再分配机制。并解决了 备份作业再分配的二次作业问题； ( 3 ) 提出了作业调度的核心算法作业调度和负载平衡算法。 通过对n e t b u n k e r 系统引入作业的动态调度，引入“惰性”作业分配方法， 4 中山人学坝i 沦史基十中心数摄库的作业讽螋系统的糊 究j 实现 以中心数据库为作业调度的负载信息中心，提出一个符合n e t b u n k e r 实际需求的 算法，设计了具有单一系统映像的作业调度系统，该作业调度系统将n e t b u n k e r 的介质服务器在逻辑上组织起来以形成集群工作组，并通过了中心数据库对集群 工作组进行管理，优化了系统，屏蔽了由于网络或者单个介质服务器的不可靠性 带来的问题，有效地管理备份恢复作业。并提高了备份作业的并行执行效率。 1 2 4 论文的写作内容 全文共分五章。第一章说明了本文写作背景和写作内容，提出了现有 n e t b u n k e r 系统存在的问题并讨论问题的解决办法。第二章介绍了作业调度问题 的研究和发展情况，以及负载平衡策略与主要算法模型。第三章简要介绍了 n e t b u n k e r 数据恢复备份系统，并分析了n e t b u n k e r 作业调度系统的体系结构， 给出了作业调度的分级模型。第四章分析了基于中心数据库p o s t g r e s o l 的作业 调度的优点、通信方法以及目的；提出了作业调度中作业分配和再分配的问题i 并提出了相应的作业调度负载平衡算法及其算法实现的伪代码。第五章介绍了作 业的消息结构以及备份作业的实现，同时给出了n e t b u n k e r 的功能介绍。第六章 是结束语。 中山人学坝l 论文 皋十中心数据库f 勺仃业训度系统的研究j 蜜j 地 第2 章作业调度的相关技术 随着计算规模的扩大，作业对资源需求的多样化，计算坏境逐渐地由单机转 向了网络计算环境。网络计算环境是指一组可共享资源，协同工作的计算资源的 集合。作业调度是网络计算环境的核心和灵魂。一个良好的作业调度系统，是确 保高效的网络计算环境的前提之一。 作业调度系统是为了强化和扩展操作系统的作业调度功能而建立于操作系 统之上的一类控制管理软件。它提供作业定义、作业提交、作业调度、作业执行、 作业监控等主要功能，一边更加有效地利用系统资源、平衡网络负载并提高系统 的整体性能。 2 1 作业调度的概述 在网络环境下，如何将网络环境中分布的资源整合起来，根据不同用户提交 的作业的特征，充分利用网络中的资源，合理调度作业，提高系统的利用率，一 直是网络计算要解决的核心问题。作业调度系统正是面向解决以上问题的功能部 件，因此成为网络计算环境的重要组成部分。无论是集群系统，还是网络环境， 人们都根据其共性和特征对其作业调度系统进行了大量的研究。 2 1 1 调度问题的研究 在分布式系统中，一个程序可以看成是一个作业集，这些作业可以并行或串 行地执行。作业之间一般是有优先次序约束的。调度问题的目标是要在满足一定 的性能指标和优先次序关系的前提下，将可并行执行的作业按适当分配策略确定 一种分派和执行顺序，合理分配到各处理机上有序地执行，以达到减少总的执行 时间的目的。 调度问题可以根据一个程序的作业是确定的还是非确定的来进行划分。确定 的调度是指被调度的作业和它们之间的相互关系在系统执行之i i f 就可以完全确 定；非确定的调度是指，只有部分初始作业是已知的，随着系统的执行，作业会 动态地增减。所以，一般将调度划分为两种形式的调度：静态调度和动念调度。 6 中山人学鳓i ：论文 甚十中心数据库的作业棚度系统的研究i 安墁 静态调度通常是在编译时已经确定了并行程序的特点和性质，确定了哪些作 业在那些处理机上执行显然，这种策略需要所有的作业在执行前都是己知的， 执行调度程序的费用也可以忽略不计。因为仅仅根据处理机编号和作业表示，处 理机就可以知道它应该执行哪些作业。 在动念调度中，调度中的许多问题都是未知的。动态调度的目标不仅是减少 作业的完成时问，而且还要减少调度本身的开销，这种开销就是运行调度程序本 身所付出的代价。通常在分布系统中，动态调度算法采用所谓“偷取空闲周期” 的方法来平衡各处理机的负载 0 9 。然而，当调度目标是减少某些特定应用的执 行时间时，这种方法是不适合的。动念调度本身的开销主要关系到调度算法，调 度算法的耗费会直接影响系统的性能，由此产生的一个重要问题是调度算法在什 么地方执行、调度信息存储在什么地方以及调度算法所使用的技术到底有多复 杂。基于这种考虑，有的学者把调度问题分成“分布调度”和“中心调度”两种 情况c l o 】 1 1 。 在分布调度中，调度作业和调度信息是分布在各处理机的存储器中。分布调 度策略普遍采用一个方法，允许空闲处理机通过访问共享作业队列来获取作业。 为了防止一个以上的处理机执行同一个作业，使用这种方法时必须使用某种同步 机制来限定在某个时刻只能有一个处理机来存取这今队列。虽然访问共享队列和 从共享队列中删除一个或多个作业增加了调度系统的耗费，但可以改进系统的负 载平衡情况。与静态调度相比，增加了一些耗费，但从调度质量中挽回了一些损 失。 中心调度技术把全局信息存储在一个中心位置，使用这种技术，要牺牲一个 或多个处理机的存储资源，但能够做出比较全面的调度。在某些中心调度策略中， 发送或者接收的处理机与一个特定的处理机进行联络，进而各自找到自己所需要 的接收者和发送者。现有的中心调度技术的缺点是使用一个指定的处理机来存储 信息，并没有充分利用这个处理机的处理能力来完成复杂的优化技术。 本文主要是针对中心调度技术进行论述和研究，建立符合n e t b u n k e r 数掘备 份恢复系统的调度模型，以及提出它的实现算法。 中山人擘坝卜论史堆十中心敖捌库的佧业侧j 殳系统的叼f 究j 实现 2 1 2 作业调度的特点 新一代作业调度系统应具备如下几方面的特点： ( 1 ) 异构型环境：异构是出一组具有不同操作系统和不同结构的计算机组 成的计算环境。网络的不断发展要求软件系统能够运行在异构环境中，即要求应 用软件必须具备各个系统阃的互操作能力，因此，新一代作业调度系统应提供包 括u n i x 、w i n d o w s 等各类操作系统的支持。 ( 2 ) 分布式操作：分布式系统迅速发展的重要因素之一是由于某些应用本 身具有分布式的特性，作业调度系统在与集群技术不断融合中，分布式特性表现 的越来越明显，部件、资源、作业的分散，使得分布式操作越来越重要。 ( 3 ) 开放型体系：作业调度系统所运行的网络环境，随时可能发生资源变 更，如网络规模的扩大需要作业调度系统管理更多的机器节点，操作系统的升级 需要作业调度系统支持新的作业运行方式等，因此，作业调度系统本身就应该是 一个开发的体系结构，可以灵活地变更机器硬件和软件模块，动态实现系统的扩 充或升级。 ( 4 ) 集中式管理：作业调度系统虽然要求分布式操作，但服务器的管理采 用集中管理的方式便可以通过一点掌控整个网络的运作情况。作业调度系统的运 行环境非常复杂，可能是一个小型的局域网，也可能是一个大型的广域网，因此， 要有效地维护整个系统，必须提供集中化管理机制，以实现从网络中任意一台工 作站上完成对整个系统的全面控制。 2 1 3 作业调度的目的 为了更好的支持网络计算环境中各类作业，一个网络计算环境下的作业调度 系统应当追求如下的性能目标： ( 1 ) 高性能 一个设计良好的作业调度系统能够充分发挥网络计算环境中计算、存储和网 络等各类资源的性能，为作业服务。高性能是作业调度系统始终追求的目标。对 。于用户而言，作业调度系统的高性能是指高效的作业执行效率，较短的作业等待 时白j ；对于系统而言，作业调度系统的高性能是指较高的系统吞吐率。对于作业 调度系统高性能的实现途径主要有：i ) 良好的作业选取策略；2 ) 快速有效的资 中山人学碘i 。论文崔 二中心教据斤的仃业调度系统的研究n 譬现 源信息收集和查询机制；3 ) 负载平衡的资源分配策略。 ( 2 ) 透明性 作业调度系统不需要用户干预就能够动念地调度作业执行。用户不必指定作 业运行在哪些节点，而是山作业调度系统根据系统状态动态指定作业运行节点。 ( 3 ) 可扩展性 可扩展性的定义是：如果系统能够加以扩展( 即增加其资源) 以满足不断增 长的性能和功能的需求，或是能够缩减( 即减少其资源) 降低成本，则称包括硬 件和软件资源的计算机系统是可扩展的。对于网络计算环境下的作业调度系统而 言，可扩展性主要表现在节点规模的可扩展性上，即系统的运行不应受到节点增 加或者减少的影响。当系统规模增加或减少时，均能够对其进行管理当系统的 资源配置发生改变时，不应该影响作业调度系统的正确运行。此外，在进行系统 设计时，我们还需要考虑技术可扩展性。主要体现在超前设计和向后兼容方面 ( 4 ) 高可用性 高可用性包括两方面：负载平衡和故障屏蔽。负载平衡就是在分配作业时， 将作业分配到负载最轻的节点上执行，使得各个节点的负载量基本相当，作业的 执行时间达到最短。故障屏蔽是指当前执行作业的节点发生故障时，作业可以迁 移到其它节点重新执行实现高可用性可以提高作业执行效率，屏蔽由于网络或 者节点的不可靠性带来的问题，有效地管理作业。 2 2 作业调度的基本问题及相关技术 2 2 1 调度模型和d a g 的产生 一个调度系统由程序作业、分布环境和调度程序三部分组成。在这个系统中， 调度的性能可以获得优化。 定义2 1 一个作业调度系统 1 2 可由一组并行程序和一组可并行执行的作 业组成，它的特征可以定义为一个四元组( r ， 将新作业加 刭奉地任务队列 图2 1 发送者主动算法流程 ( 1 ) 转移策略：这晕采用的是门槛策略，当一个节点产生一个新作业时， 若作业队列长度超过门槛t ，则该节点被确定为发送者。 ( z ) 选择策略；本算法选择新到达的作业作为要发送的作业。 ( 3 ) 定位策略：根据被轮询节点的作业队列长度，判断是否超过门槛值， 若没有超过就转移到该节点。这是门槛定位策略 ( 4 ) 信息策略：在本算法中采用的信息策略是要求驱动策略，一个节点只 有在成为发送者时才能收集其他节点的信息。 发送者主动的主要优点是：没有过重负载的忙节点，不会被空闲邻接节点所 打扰。这一点在系统整个负载较低时尤为重要。 发送者主动的主要缺点是：负载过重的忙节点还要额外增加处理负载平衡调 度的负担 关于s i 算法的进一步讨论，可以参考文献 1 6 1 7 。 2 3 3 接收者主动( 砌) 算法 接收者主动算法简称r i ( r e c e i v e ri n i t i a l i z i n g ) ，是任务调度和负载平衡 应用中普遍使用的一种方法 1 8 ，接收者主动算法的主要思想是：由轻负载节点 逐个向邻接节点发出作业申请请求，若请求到作业，则终止请求并执行请求到的 作业，否则继续向下一个邻接节点发出作业申请请求。也可能所有邻接节点都没 中山人学伽论史 毕寸二中心数据库的f f 业调度系统的州究j 实现 有满足请求的作业，这样作业申请节点就等待一段时问之后再重新丌始新一轮的 作业请求循环，直至得到满足。 这种方法是轻载节点向网络中负载比较重的节点请求获得作业，这种方法在 整个系统负载重的情况下工作是很有效的。与发送者主动算法相反，当一个节点 的作业队列小于门槛值，它就尝试从过载节点接收一个作业。图2 2 1 2 给出了 其算法流程。 图2 2 中，g 吧为作业队列长度，q 为节点f 的作业队列长度，t 为门槛值。 n 图2 2 接收者主动算法流程 ( 1 ) 转移策略：这里采用的仍是门槛策略，当一个节点上有作业离开时， 若作业队列长度小于门槛t ，则该节点被确定为接收者。 ( 2 ) 选择策略：所有其他节点上的作业都可能成为接收对象。 ( 3 ) 定位策略：根据被轮询节点的作业队列长度，判断是否超过门槛值， 若超过就转移作业到该节点，。这是门槛定位策略。 ( 4 ) 信息策略：在本算法中采用的信息策略是要求驱动策略，一个节点只 有在成为接收者时才能收集其他节点的信息。 接收者主动主要优点是：不需要相互交换负载信息；对于大规模并行计算问 题，当每个节点均处于忙状态时，几乎不需要额外调度丌销：负载平衡的许多工 作由空闲节点来完成，没有给忙节点增加许多额外负担。 4 中山人学坝i 。论文娃十中心教据库的作业调蝰系统的班_ 尢，实现 接收者主动的主要缺点是：在丌始和结束阶段时作业数相对较少，许多作业 请求会延迟忙节点的执行。 关于s l 算法的进一步讨论，可以参考文献 1 6 1 7 。 2 3 4 双向主动( s i n ) 算法 作为两种最基本的作业调度和负载平衡算法，s i 和r i 各有其优缺点。 s i 算法没有负载过重的忙节点，不会被空闲结点的作业申请请求所打扰， 在系统开始阶段、结束阶段等作业数相对较少的时间段里执行效率较高；缺点是 负载本身己经过重的忙结点还要承担额外的任务调度和负载平衡负担，影响了重 负载结点上任务的执行效率。 r i 算法中负载平衡的主要工作由轻负载节点来完成，节点之间不需要相互 交换负载信息，对于大规模并行计算等应用，当大部分结点都处于忙状态时，只 需很少的额外调度开销且重负载结点不再像s i 中一样亲自进行寻找轻负载结点 等工作，减轻了重负载结点的负担；而由轻负载结点来充当系统任务调度和负载 平衡的主角，有利于系统资源的充分利用和作业执行效率的提高。r i 的主要缺 点是：当系统中大部分结点处于轻负载状态时，许多来自轻负载节点的作业申请 请求会延缓重负载节点的作业执行。 双向主动算法简称为s r i ( s e n d e ra n dr e c e i v e ri n i t i a l i z i n g ) ，在双向 主动算法中，发送者和接收者都能转移作业，因此双向主动算法兼有两者的优点。 在系统负载较低时，本算法中的发送者主动很容易发现轻载节点；在系统负载较 高时，接收者主动更容易找到过载节点，但双向主动算法也有一些不足，如在系 统负载较高，使用发送者主动容易造成系统的不稳定性等。一个较好的解决方法 是采用自适应算法，合理设置门槛值，在系统高负载时采用接收者主导，在系统 低负载时采用发送者主动。 中山人学坝i 论叟： 壮十中心数据库的f r 业涮度系统的 i j 究j 实现 第3 章n e t b u n k e r 作业调度系统模型 3 1n e t b u n k e r 数据备份与恢复系统简介 n e t b u n k e r 是国内一款基于模块化、插件化设计的跨平台备份和恢复的网络 存储备份恢复软件。适用于政府、企业数据中心的数据存储管理备份，采用多进 程、多作业的存储管理解决方案，适合异构平台的服务器和客户端的数据集中管 理有效备份与恢复。 n e t b u n k e r 为u n i x ，w i n d o w s 和l i n u x 环境提供全面的数据保护，直观的图 形用户界面，允许组织机构管理所有备份和恢复作业的方方面面，并为整个企业 制定完全一致的备份策略。n e t b u n k e r 为o r a c l e ，m i c r o s o f ts q ls e r v e r 和文 件系统提供数据库识别和应用识别备份与恢复解决方案，为所有的备份与恢复操 作交付实时与历史分析。n e t b u n k e r 的模块化软件架构使得产品易于升级、扩充 1 9 。整个系统的是建立在高度松耦合，自定义通信协议和多层网络资源协调的 架构之上的，具有良好的扩展性和平台无关性 2 0 。 3 1 1 系统结构 n e t b u n k e r 数掘备份系统有效结合l i n u x 存储管理子系统，能够满足大规模 数据中心的需求。在网络环境下，现有数据类型的复杂性决定了在本系统中代理 程序自身的复杂性和适应多样性的复杂设计。针对异种数据类型，必须分析研究 每一种数据的具体特性，充分考虑代理程序的适应性，这也就决定了代理程序在 复杂度上不可能小，处理不同的数据库的代理，要求的控制台显示和交互的内容 具体会不同，因此对控制台的动态装载有很高的要求，同时，这样也为今后软件 的升级带来方便，满足不同用户的自定制界面。系统的复杂性和要求平台无关的 特性，给控制台的开发提出了更高的要求。该数据备份系统包含了以下几个子系 统：备份服务器g u i 程序客户端代理介质服务器。如图3 1 所示 2 1 。 ( 1 ) 备份服务器是整个系统的数据中心，负责维护客户机、介质服务器、 作业、日志、备份集等索引( c a t a l o g ) ：计划和跟踪客户机备份与恢复作业；提 6 中山人学坝i 论文 堆1 ：中心教据库的f f 业t 嘲度系统的研究实现 供同志和报警功能；提供权限和用户管理功能。 ( 2 ) g o l 程序是整个软件的用户操作界面，完成用户备份和恢复资源的选 择、用户备份计划制定、备份集管理、报表查询等操作。 ( 3 ) 客户端代理程序提供客户机配置管理；管理客户端代理的安装、卸载、 升级等。各备份客户机不同数据源的备份调度通过使用不同的代理程序完成备份 服务器转发控制台的备份或恢复作业。 ( 4 ) 介质服务器提供访问磁盘介质、磁带与磁带库访问接口，完成备份目 标数据的存储、恢复数据的查找、索引卷管理等。 3 1 2 系统特点 图3 1n e t b u n k e r 软件总体架构图 n e t b u n k e r 通过在网络中选定一台服务器为备份和恢复管理的服务器，在其 它需要备份的服务器上安装客户端软件及相应的应用软件备份功能模块，从而将 中山人学埘! i 。论义 娃十中心数据库f l 勺仵业训度系统的w 宄j 实现 整个网络的数掘自动地备份到磁带库或其它的可用存储设备上，实现网络存储设 备共享。通过介质服务器可以将数据备份到网络上任何存储设备( 磁带机，n a s ， s a n ，磁带库) ，真讵实现网络备份的功能。 备份服务器记录所有的作业相应备份信息，提供给丰富的报表。采用结构化 设计，各部分功能各自独立又有相互关系；插件化设计，可对代理模块单独升级、 更新。实现集中管理，异地备份。灵活的插件技术，实现对各种异构平台、异构 数据库的支持。可以备份恢复多种平台的文件和操作系统；可以实现o r a c l e 、 s o l s e r v e r 数据库的在线热备份。 n e t b u n k e r 支持硬盘和n a s ，支持各种磁带机，磁带库的读写，同时n e t b u n k e r 支持硬盘和磁带相结合的分级存储模式，也就是采用虚拟磁带技术，先备份至磁 盘后迁移至磁带两阶段备份模式。n e t b u n k e r 存储管理的特性主要包括： ( 1 ) 可伸缩性集中式管理与控制，高性能以及灵活的多层体系架构， 使n e t b u n k e r 能尽量适应数据中心与日俱增的需求。 ( 2 ) 平台独立性保护多种主流平台，其中包括l i n u xf l a g ，l i n u xr e d h a t 和w i n d o w s 等平台，无论是那种平台都能够实现相同的性能和功能。 ( 3 ) 基于策略的集中式管理中央控制台通过一个直观界面，提供单一 管理点，允许备份管理员以更有效的方式，管理大量网络内的应用主机。 ( 4 ) 支持多种代理应用可以选择安装多