（计算机科学与技术专业论文）面向海量文本数据的多任务并行调度加载技术研究与实现.pdf

国防科学技术大学研究生院工学硕士学位论文 摘要 随着网络的发展，网络信息安全管理迫切需要存储和管理海量的文本数据， 需要高性能的海量文本数据加载和组织管理，因此，研究高性能的海量文本数据 加载技术具有重要的理论意义和应用价值!、 网络信息安全管理中的海量文本数据具有如下特点：数据产生速度高、密度 大、规模大且每天2 4 小时不问断，其应用要求支持高效的全文检索。针对以上数 据特点和应用需求，本文在以下几个方面对海量文本数据的加载技术进行了研究： 1 研究了多流水线并行加载技术。首先，将需要加载的海量文本数据均衡划 分为多个独立的数据集合，实现多个数据集合的并行加载。其次，对于每一个数 据集合，充分挖掘其流水并行，将加载过程划分为多个可以流水并行执行的加载 阶段，从而实现了高性能的多流水线并行加载。 2 在流水线内部，利用o r a c l e l o g 提供的分区交换技术，在每一个分区的加载 上进一步挖掘并行性，将加载划分为多个可以并行执行的子任务。针对这些子任 务之间存在的约束关系以及多个分区可以并行加载的特点，提出了带约束关系的 多任务并行调度算法，从而保障了细粒度并行化后的并行效果。 3 针对计算资源、i 0 资源分布不均衡以及服务器节点存在异构性的特点，提 出了一种虚拟资源池技术，将每一个服务器按照其处理能力计算资源数量，并将 计算出的资源加入资源池中，进行统一的分配与调度，从而实现异构环境下混合 负载的均衡分布，达到资源的最大利用率。 基于以上技术，研制了海量文本数据的多任务并行加载系统，第三方测试表 明，该系统达到了极高的加载性能( 加载峰值达2 0 0 亿条记录2 4 小时，每条记录 0 5 k b ) 。目前该系统已经上线稳定运行了3 个多月。 主题词：文本数据，海量数据加载，加载技术，多维数据，虚拟资源 第i 页 国防科学技术大学研究生院工学硕士学位论文 a b s t p a c t w i t ht h ed e v e l o p m e n to fn e t w o r k s ，t os t o r ea n dm a n a g et h em a s s i v et e x td a t ai sa l l u r g e n tn e e dt on e t w o r k i n f o r m a t i o ns e c u r i t ym a n a g e m e n t ，t h el o a da n dm a n a g e m e n t t e c h n o l o g yo fh i g h p e r f o r m a n c ei sb e c o m em o r ea n dm o r ei m p o r t a n tt oi t ，s o ，t or e s e a r c h l l i g h - p e r f o r m a n c et e c h n o l o g yo fm a s s i v et e x td a t ai so fg r e a tt h e o r e t i c a ls i g n i f i c a n c e a n dt h ev a l u ei na p p l i c a t i o n 砀em a s s i v et e x td a t ai nt h en e t w o r ki n f o r m a t i o ns e c u r i t ym a n a g e m e n th a st h e f o l l o w i n gc h a r a c t e r i s t i c s ：h i g h s p e e dd a t ag e n e r a t e d ，t h eh i g hd e n s i t y ，l a r g e s c a l ea n d n o n s t o p f o r2 4h o u r sa d a y ，t h ea p p l i c a t i o n sc a l lf o rf u l l t e x ts e a r c ho f 王l i g h p e r f o r m a n c e i nv i e wo ft h ea b o v ec h a r a c t e r i s t i c so fd a t aa n dn e e do f a p p l i c a t i o n s ，t h i sa r t i c l es t u d i e di nt h ef o l l o w i n ga s p e c t so ft h el o a d i n gt e c h n i q u e so ft h e m a s s i v et e x td a t a f i r s t ，r e s e a r c ho nm u t i p i p e l i n e d p a r a l l e ll o a d i n gt e c h n o l o g y f i r s to fa l l ，w ed i v i d e t h el o a dp r o c e s si n t oan u m b e ro fi n d e p e n d e n td a t ac o l l e c t i o n ，a n dl o a dt h ed a t a c o l l l e c t i o n sp a r a l l e l y t h e n ，f o re a c hd a t as e t ，w et a pt h ep i p e l i n e p a r a l l e ld e e p l y ，t e x to f t h em a s s i v ed a t ai sd i v i d e di n t oan u m b e ro fi n d e p e n d e n td a t ac o l l e c t i o n s e c o n d ，f o r e a c hd a t as e tt ot a pt h ep i p e l i n ei np a r a l l e l ，s ot h ew h o l el o a d i n gp r o c e s sw i l lb ed i v i d e d i n t os e v e r a ls t a g ei no r d e rt oa c h i e v eah i g h p e r f o r m a n c em u l t i l o a d p a r a l l e lp i p e l i n e i nt h ei n t e r n a lp i p e l i n e ，b yu s i n gs w i t c h i n gt e c h n o l o g yo fo r a c l e10 g ，w et a pt h e p a r a l l e lc h a r a c t e r i s t i c so ft h ee a c hd a t ap a r t i t i o nf u r t h e r ，a n dd i v i d et h el o a d i n gp r o c e s s i n t os o m es u b t s kw h i c hc a nb es c h e d u l e d p a r a l l e l y t oa i m e da tt h eb i n d i n gr e l a t i o n s h i p b e t w e e nt h es u b t a k s ，w es t u d i e daa l g o r i t h mo fm u l t i - t a s ks c h e d u l i n gw i t hb i n d i n g r e l a t i o n s h i p mr e s o u r c e sa r ea l w a y sd i s t r i b u t eu n e v e n l y ，f o re x a m p l e ，c o m p u t i n gr e s o u r c e s ，i or e s o u r c e sa sw e l l ，a n dt h es e r v e rn o d e sa r eh e t e r o g e n e o u s f o rt h e s en a t u r e s ，av i r t u a l p o o lo fr e s o u r c e st e c h n o l o g yi ss t u d i e db yu s ，w ec a l c u l a t et h en u m b e ro fr e s o u r c e so f t h en o d e si na c c o r d a n c ew i t hi t sa b i l i t y ，a n dp u tt h ec a l c u l a t e dr e s o u r c e si n t ov i r t u l r e s o u r s e sp o o l ，t h e n ，t h er e s o u r s e si nt h ev i r t u lr e s o u r s e sp o o lc a nb es c h e d u l e du n i f i e d ， s oa st oa c h i e v et h em i x e dl o a db a l a n c ei nt h eh e t e r o g e n e o u se n v i r o n m e n t ，a n dt h e m a x i m u mu t i l i z a t i o n b a s e do nt h ea b o v et e c h n o l o g y ，w ed e v e l o p e dt h es y s t e mo fm u t i - t a s k p a r a l l e l s c h e d u l i n gl o a d i n gt e c h n o l o g yo fm a s s i v et e x td a t a 1 1 1 es y s t e mw a st e s t e db yt h e t l l i r d p a r t y a n dt h e t e s tr e s u l ts h o w st h a tt h e s y s t e mr e a c h e dav e r yh i g hl o a d p e r f o r m a n c e ( u pt ot h ep e a kl o a dr e c o r do f2 0 ，0 0 0 ，0 0 0 ，0 0 0 2 4h o u r sad a y ，t h es i z eo f e a c hr e c o r di so 5 k b ) n o w ，t h es y s t e mi sr u n e do n l i n es t a b l ef o rm o r et h a n3m o n t h s k e yw o r d s m a s s i v et e x td a t a ，l o a d i n gt e c h n o l o g y ，m u l t i - d i m e n s i o n a ld a t a ， v i r t u lr e s o u r s e 第i i 页 国防科学技术大学研究生院工学硕士学位论文 表目录 表1 1 不同加载方式的性能对比9 表5 1 测试环境3 8 表5 21 8 0 亿条天时入库时间3 9 表5 32 0 0 亿条天时入库时间。3 9 表5 4 加载性能3 9 表5 5 数据入库分布情况4 2 表5 6 压力一情况下查询测试4 3 表5 7 压力二情况下查询测试。4 3 表5 8 压力三情况下查询测试。4 3 表5 9 测试环境4 4 第1 v 页 国防科学技术大学研究生院工学硕- t 学位论文 图目录 图1 1一种调度算法分类的层次模型1 2 3 图2 1m d m p 体系结构【1 2 1 7 图3 1数据入库的整个过程【3 刀。1 3 图3 2o r a c l e 中批量数据加载流程【3 7 1 1 4 图3 3 基于o r a c l e 交换分区机制的并行加载服务中的数据加载过程【3 7 1 1 4 图3 4 粗粒度的多级流水并行加载任务1 5 图3 5 细粒度的多级流水并行1 6 图3 6 加载任务、加载子任务与进程的关系1 7 图3 8 结果状态牌的申请和释放1 9 图3 9 虚拟资源资源映射示例2 3 图3 1 0 虚拟资源的调度2 4 图3 1 1任务执行状态追踪过程2 6 图3 1 2 处理方案知识库匹配2 7 图4 。l 总体结构设计2 8 图4 2 系统各个模块关系2 9 图4 3 任务管理器类间关系图3 0 图4 4 虚拟资源映射的过程图3 1 图4 5 资源调度过程3 2 图4 6 资源管理器类关系3 3 图4 7 排队器类关系图3 4 图4 8 结果状态管理器3 4 图4 9 任务重做器类关系3 5 图5 1 测试环境部署3 7 图5 2 入库时间变化图4 0 图5 3 三个加载服务节点c p u 使用情况【3 8 l 4 1 图5 4 三个加载服务节点内存使用情况f 3 8 1 4 l 图5 5 有无t a s k m a n a g e r 加载性能对比4 4 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目：亘囱连量塞查熬塑的垒堡盘羞堑塑廑拉越拯盔盈究生塞塑 学位论文作者签名：路关2 善墨! 日期：一乙阳譬年h 月留日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：亘囱盗量塞奎数量鲍垒堡查羞短迥廑加蔻撞盛盟窒皇塞垫 学位论文作者鼢位必强一 日期仞。9 年f 7 日 作者指导教师签名：陲毛钯耻 日期：7 卯7 年 f 月争日 国防科学技术大学研究生院工学硕士学位论文 第一章绪论 1 1 研究背景 随着社会信息化的发展，互联网、通信等领域产生了t b 甚至p b 级的海量文 本数据。据w i n t e r 公司统计【l 】，近年来全球最大数据库的容量呈指数增长趋势， 2 0 0 5 年最大数据仓库容量已经达到数百t b ，最大在线处理数据库容量也已超过了 2 0 t b 。如何对海量文本数据进行及时加载、存储成为数据库应用研究领域的热点 之一。近年来，人们对海量数据的加载技术进行了广泛的研究，比如：y d o r ac a i 和r u t ha y d t 联合进行了面向海量天文数据的存储系统的研究【2 】，提出了一个数据 存储框架s k y l o a d e r 。该研究重点考虑提高海量信息的加载性能问题，s k y l o a d e r 依赖于特定的应用和表结构，加载和查询不是同时执行【3 】。当前业界的许多商用数 据库，例如o r a c l ed a t a b a s e1 0 9 ，i b md b 2u d b 等都提供了对于海量数据的支持， 但一般的大型商业并行数据库由于关注的更多的是多用户环境下的并行查询优 化，对单一用户的数据高速加载考虑不足。以上研究和产品针对于t b 甚至p b 级 的大规模海量数据，限于硬件设备和系统的处理能力，在加载性能上显示出了不 足。 当前海量文本数据的加载与存储具有以下特点：一，数据持续的源源不断的 到来，海量信息数据产生的高速性、连续性、即时性等特点，给海量数据的加载 和查询带来了巨大的挑战；二，对于海量数据数据通常会有查询、分析等需求， 所以需要能够全文检索，需要建立文本索引，文本索引的建立速度非常慢，当数 据量达到海量时建立文本索引的时间消耗非常大，另一方面这些索引带来了较大 的空间开销；针对以上诸特点，我们结合o r a c l ed a t a b a s e1 0 9 网格化的特点，通过 采用多集群、多加载服务、多数据库以及对文本数据的多维切片划分等技术，通 过对文本记录的分析以及对数据记录的多维切片划分，使得数据加载过程分成诸 多子任务，并行调度执行。 海量文本数据加载子任务的调度面临以下问题： 一、任务切分后的并行调度问题 经过对文本数据的多维切片划分后，系统中加载子任务众多，有些可以被并 行调度执行，有些子任务之间有制约关系，必须保证其制约关系，而且要使得完 成各个子任务的时间跨度最小化，这就需要高效的带制约关系的多任务并行调度 算法。 二、加载任务最优并发度的控制问题 在加载过程中，加载子任务并行度低不足以发挥多集群多、资源的性能，不 第l 页 国防科学技术大学研究生院工学硕士学位论文 能充分达到并行化的果，反之，并行度过高也会带来一系列i 、u j 题，并行度过高则 操作系统会将不同的任务频繁的切换到处理器上，频繁的切换带来过多的时间消 耗，特别是在海量数据加载过程中大数据会占用大量内存，任务之间的切换会带 来内存的切换，较大的增加了内存转换开销，所以说，过高的任务并行度反而也 会降低性能。因此最优并行度的控制是个对加载性能有重要影响的问题。 三、异构资源的管理问题 在执行加载任务的过程中，加载系统的资源的管理方面面临以下问题：首先 资源要被有效的负载均衡的充分利用，其次系统中资源处理能力有差异，是异构 的，资源的调度要充分考虑资源异构性的特点。在资源异构性的基础上，既要能 做到为任务分配合理的资源、使之充分利用，又要保证异构条件下混合资源的负 载均衡性。 综上所述，针对海量文本数据加载的多子任务并行调度面临的任务调度、最 优并行度控制、以及异构资源管理的问题，是本文研究的内容，我们将研究一种 适合于海量数据加载任务特点的任务调度算法以及资源管理算法，从而有效的对 加载子任务进行调度，提高加载性能。 1 2 研究现状 在多种异构资源的环境中研究并行任务的调度问题已经成为了该领域目前和 未来研究的一个重要方向。在异构的多集群、多资源环境中，各个资源的处理能力 不尽相同，多加载任务的并行调度既要保证各个加载任务之间的逻辑关系的正确， 又要在一定的时间内完成相应的加载任务，需要合适的资源管理、调度策略和可 靠的任务调度策略，假如某一个任务没有在规定时间内完成，可能会导致整个系 统的加载过程不能完成或者出现瓶颈，影响整个加载系统的加载性能。在构成系 统的各硬件设备性能确定的情况下，软件设计中所采取的各种策略和算法便是影 响系统加载性能的主要因素。在单机系统中，设计合适的加载任务调度算法是提 高系统加载性能的关键所在；对于分布式系统而言，整个系统由多个处理节点所 构成，除单个处理节点上的调度算法之外，各个任务在多个处理节点之间的资源 分配策略、任务调度算法也会对加载性能产生较大影响，整个系统的性能会因为 任务和资源的不恰当调度不能被完全发挥。所以说，在并行加载系统中，对于加 载任务的调度以及资源管理、调度问题是至关重要的。对于海量文本数据加载服 务系统来说，整个加载系统全局的资源协调和调度是一个至关重要的问题。通过 任务的并行调度以及资源的有效管理、调度使得集群资源需求下的任务之间的协 同工作，考虑有限资源在时间和空间上的合理、协调搭配，以期达到更好的效果。 目前对于有关涉及到的问题有一些研究： 第2 页 国防科学技术大学研究生院工学硕士学位论文 1 2 1 多任务调度的研究现状 任务调度的一般形式以及其受限形式都是n ph a r d 问题，因此要取得时间复 杂度的最优调度，就必须对表示加载并行任务的任务图或加载并行任务计算模型 附加一些限制条件，表示并行任务的任务图和并行计算模型是多种多样的，因此， 如何针对不同的具体加载并行任务产生了许多有效的任务调度方法。 当前，任务调度算法种类繁多，针对任务调度问题，人们提出了许多个有特 色的解决方案，已经取得了不少成果。随着人们对这一问题重视程度的提高，任 务调度算法还将不断的完善和提高。图1 1 是任务调度的一种分类。 任务调度 局部调度 全局调度 静态调度 动态调度 厂l 厂l 最优调度次优调度 分布式系统的非分布式系统的 枚举法图论法数学规划法排队法 厂- 度 合作式的 非合作式的 厂士 调度 图1 1 一种调度算法分类的层次模型f 2 l 】 为了令存储管理中的加载任务可以更充分、更高效的利用网络和数据库资源， 使得任务可以尽可能地并行执行，以减少总的执行时间，提高加载系统的性能以 及运行效率，实现系统的负载均衡，选择加载任务的调度模式及其相关的算法就 显得尤为重要。目前对于面向集群多资源的任务调度已有些调度算法和策略： 表( l i s t ) 调度、基于任务复制的调度、基于任务集群( c l u s t e r ) 或聚类的调度、非确定 性调度等。 1 2 2 最优并发度控制的研究现状 多任务并行系统中的并行度控制问题直接关系到系统的性能，目前解决最优 并发度的办法有两种：一是通过实际测试计算，找出最优并发度，二是通过一些 算法计算，但该算法主要是针对特定的应用，文献 4 1 、k 5 】给出了几种计算 最优并行度的算法，一般形式的优化调度问题都是n p 难题【6 l ，各种面向任务来解 决并行度的调度算法都相对比较复杂，而且上述算法都缺少对多集群资源异构性 第3 页 国防科学技术大学研究生院工学硕士学位论文 的考量。 1 2 3 资源调度的研究现状 资源调度即匹配应用任务与可用的资源，进行任务执行顺序的调度和应用数 据的分配等。资源调度具体包括下面几个问题：将某个任务或者任务集映射到某 个或者某些资源上；调度任务的执行顺序；调度资源上所有任务的执行顺序。 c a s a v a n t 和k u h l 从对资源的管理角度上，认为资源调度问题的每个实 例都可以被看成由三种要素组成，即消费者、资源、策略。从策略如何对消费者、 资源起作用，可以观察调度行为1 7 。在按照该种对调度问题的描述，来评价某个调 度算法时，应该考虑两个问题：调度者管理和调度资源应该非常有效；消费者自 己访问管理资源的时候很困难，并且开销很大。k u r o w s k i 在文献【8 】中讨论了三 个准则：即时间准则、费用准则和资源利用率准则。基于上面的评价特征和评价 准则许多研究者提出了一些不同的资源调度算法和策略，主要分为基于有向无环 图的算法和基于资源池的算法。 1 3 本文工作 通过对当前海量文本数据加载任务调度的分析，在1 1 文中提出了面临的三个 问题，目前还没有很好的解决方案，鉴于此，本文结合已有的任务调度和资源管 理技术，基于多加载任务、多异构资源，并针对海量文本数据加载的特点，设计 并实现了多维数据切片划分、多加载子任务并行调度、虚拟资源池及虚拟资源映 射等技术，有效的解决了1 1 提出的当前海量文本数据并行调度加载过程中遇到的 三个问题。 本文的研究工作是作为国防科技大学开发的拥有自主版权的面向海量信息的 并行数据管理平台【9 】( m d m p ，m a s s i v ed a t am a n a g e m e n tp l a t f o r m ) 的一部分；作 为m d m p 的子系统的重要组成部分，面向海量文本数据的加载系统针对海量文本 数据加载和存储组织问题，研究并实现了一种面向海量文本数据的多任务并行调 度加载技术，通过对海量文本数据的多维切片划分从而使得整个数据的加载过程 分解成若干个任务，充分发掘这些任务之间的并发性，利用有效的并行调度算法， 使得系统中加载任务充分并行，本文研究的虚拟资源池及虚拟资源映射策略不但 使得系统中资源被有效的管理、调度和充分的利用，而且解决了任务并发度控制 的问题。实现了高性能、高可用的海量文本数据的多任务并行调度加载技术，并 基于此技术开发和改进了面向海量文本数据的多任务并行加载系统。 1 4 本文结构 第4 页 国防科学技术大学研究生院工学硕士学位论文 本文共分六章，各章节的内容概述如下： 第一章为绪论。介绍了本课题的研究背景，引申出了本课题的研究方向以及 所做的工作。 第二章为相关技术。介绍了m d m p 系统，海量文本数据加载存储有关的数据 库知识，以及任务调度、资源调度等相关技术、算法。 第三章为关键技术与策略研究。提出了若干面向海量文本数据加载的多任务 并行调度系统相关的算法、策略。 第四章为系统的设计与实现。介绍了系统结构的设计，提出了并行加载系统 的具体实施方案以及系统的开发实现。 第五章为测试与分析。对系统从各个角度进行了全面的测试，并对测试结果 进行了相关分析。 第六章为总结与展望。对目前的工作进行总结，并对日后的工作及前景进行 展望。 第5 页 国防科学技术大学研究生院工学硕士学位论文 第二章相关技术 弟一早个日大搜小 目前在海量文本数据处理、数据库技术以及在多任务并行调度和资源调度领 域都有一些研究成果、产品或者技术，这些都是与本课题相关的，在本章将介绍、 讨论这些相关的成果、产品和技术，并对这些技术进行分析、对比，并将在以后 的研究过程中借鉴他们的一些思想。 2 1 面向海量信息的并行数据管理平台m _ d m p 面向海量信息的并行数据管理平台m d m p 是本文研究成果应用的系统，本文 研究的设计和实现是在该系统上做的工作，为了更清晰的明确对海量文本数据加 载任务调度的需求，从m d m p 的系统结构、功能、各个模块之间的关系等方面进 行了分析介绍。 面向海量信息的并行数据管理平台m d m p 是采用多文本数据库技术、多数据 库并行技术【1 0 , 1 1 1 以及分布式事务处理技术实现的支持海量文本数据加载与检索的 大规模事务处理中间件。它是由多个局部自治的数据库管理系统和一组中间件组 成，中间件用于对这些数据库进行管理，并为用户的管理和操作提供统一视图。 其系统体系结构如下图2 1 所示。 面向海量信息的并行数据管理平台m d m p 分为四个层次，分别为用户接口层、 数据库访问层、数据处理层以及数据库维护层。 用户接口层 针对不同的用户需求，提供了相应的接口，多种用户类型，多种接口。可以 进行系统运行状态监控、系统配置管理、系统运行状态维护，适于管理人员和维 护人员，采用浏览器方式的图形化界面的方式。 针对数据库的管理维护人员采用交互命令接口，提供具有统一视图的类似于 s q l * p l u s 的s q l 命令解释执行器。对于其他开发方，有专门的i d l 接口，作为对 外的a p i 。 数据处理层 数据处理层是系统的重要组成部分，由一组数据处理模块和一组系统支撑工 具和服务等组成。 数据库维护层 数据库维护层实现对数据库日常维护功能，包括表空间以及数据表的创建、 删除等，表分区的创建和删除，统计表的维护，数据库数据备份、语义缓存的维 护等。 第6 页 田防科学技术大学研究生院上学硕士学位论文 图2 1m d m p 体系结构”“ 数据库访问层 数据访问层实现了对底层数据库异构性的屏蔽，其次，该层针对不同的应用 需求，提供不同配置的高效的数据库访问服务。比如说加载服务、查询服务等； 数据库访问层实现了以服务的方式对外提供数据库访问功能，表现了比较好的灵 活性，能够在系统运行时部署，能够实现在线部署，并且具备容错等功能：数据 库访问层对外提供了简化的编程接口，针对系统使用的特点提供了个性化的编程 接口更加简便易用。 系统支撑工具和服务是由负载平衡服务唧、系统管理模块以及系统运行日志管 理模块组成。其中负载均衡服务是s t a r b u s ”1 ( 一种c o r b a 中间件产品) 提供的服 务，负载均衡服务用于服务对象的负载均衡和容错管理；系统管理模块用于数据 库予系统软件的管理，包括运行状态监测、系统远程部署、远程启动、自主运行 维护、服务对象运行状态管理等；口志管理模块用于数据库系统软件运行日志管 理，包括系统运行轨迹、运行过程中关键事件和状态记录等。 大规模事务处理中间件作为一个海量数据应用开发和管理平台，其主要特点 是： 第7 页 国防科学技术大学研究生院工学硕士学位论文 支持海量文本数据的并行实时加载和数据的多库分布存储 提供统一的对多个异构t l 治数据库的全局管理和使用界面和接口 支持对海量文本数据的高效的并行检索 高可用性，支持容错的服务 系统可在线配置、故障恢复、升级等，能够实现负载均衡 2 2 分区和分区交换技术 o r a c l e 公司的o r a c l e l 0 g 的分区和分区交换技术对海量数据特别是海量 文本数据给予了有力的支持。下面本节介绍分区和分区交换技术，以及为什么要 采用该技术，并对分区交换技术对海量文本数据管理上的影响进行讨论。 准确、快速、全面地搜索到信息，在这个网络和信息化高速发展的时代特别 重要。根据c n n i c 统计，在互联网上搜索的使用量仅次于电子邮件。由于计算机 存储容量和运算速度的大大提高，使得将海量的原始数据特别是文本数据全部转 入检索系统成为可能。 因此，以全文检索为代表的自然语言检索系统受到普遍的关注，而在我们的 应用背景系统中，同样有对海量文本数据进行全文检索的需求。 为了使得数据库系统查询操作拥有较高的性能，需要在多个数据表的字段建 立索引以及文本索引，使其具有较好的文本查询的功能。 当前加载系统所能采纳最好的存储策略就是采取基于o r a c l e1 0 g 数据库访 问服务下的交换分区的方式建立文本索引，并通过s q l * l o a d e r 进行数据导入的加 载方式。 普通的导入方式，向数据表中插入数据时，o r a c l e 会判断要插入的数据和 已有的数据索引是否存在冲突，同时要更新表中的所有存在的索引，这样的更新 操作会消耗较长的时间，在当前需要建立文本索引的背景下，更新索引所消耗的 时间将成倍于加载所使用的时间。 如果采用交换分区的方式，因为在向临时表加载数据时，临时表内没有索引， 这样就节省了大量用于更新索引的时间，且交换分区操作只是在o r a c l e 数据库 的数据字典层面上进行，并没有数据被实际移动，所以分区表交换是极其快速的。 传统的数据加载方式都有一个限制，就是用户对数据表的操作必须在数据导入操 作完成之后。 面对7 x 2 4 不间断访问数据库来说，如果我们只是导入需要增加的数据时，这 种限制将对用户的实时访问产生影响。o r a c l e 在这方面提供了表分区功能，它 可以减少导入数据操作对用户实时访问数据的影响。针对需要建立文本索引的海 量文本数据加载系统，采用交换分区的加载方式能够有效的提高性能。 第8 页 国防科学技术大学研究生院工学硕士学位论文 普通加载方式和交换分区加载方式之问的性能对比见表1 1 。 表1 1 不同加载方式的性能对比 擞据规模 2 0 0 万4 0 0 万1 0 0 0 万2 0 0 0 万 加载状 普通方式1 6 8 9 7 i 7 1 4 61 6 9 3 8 1 6 6 2 5 交换分区方 式 1 1 0 0 4 11 0 9 8 6 2 1 0 7 3 9 2 1 0 3 1 2 6 速率：( 条秒) 。 2 3 资源调度相关技术 资源的调度是是一个经久不衰探讨的问题，针对1 2 章提出的资源调度的几项 准则，这里将现有的资源调度技术分为两类：基于有向无环图的调度算法和基于 资源池的调度算法。 2 。3 1 基于有向无环图的资源调度算法 当应用为单一任务，且资源仅包括计算资源时，已有许多学者进行研究并提 出了解决方法。但当应用本身包含多个任务，且每个任务都要访问不同类型的资 源( 计算资源、通信资源、储存资源、网络资源等) 时，针对单一任务的解决方 案就不适用了。对于多任务模式可以将其表示为有向无环图，基于这个思想也出 现了许多算法。 m a h e s w a r a n m 等人提出的动态匹配算法拉4 1 ，思想是：大的任务可以被分成 若干子任务，并且各个子任务之间的关联关系预先知道，提出了h y b r i dr e m a p p e r 算法，将多个子任务表示成有向无环图，在任务执行的过程中动态的收集资源信 息、动态的分配资源。 i v e r s o n 等人提出的动态竞争调度资源算法1 1 5 1 ，主要思想是很：多系统中， 系统中的任务需要一定的资源完成，在任务执行完毕后就释放所占用的资源，任何 两个需要相同资源而又互相冲突的任务不能同时进行。任务通过网络等向资源发 出请求，获得使用权者使用资源，使用完毕释放，请求先到达先占有。 多次映射策略【1 6 1 ，一次映射就是为一个任务选择最合适的资源使其执行时 间最短的调度过程，当每次映射事件发生时，可通过查询服务获得当前系统所有 组成集群的资源状态信息。任务队列中既包含新到达的任务，也包含那些在上一 次的映射事件中已经被映射但还没有开始执行的任务，算法使用更新的资源状态 信息对所有这些任务进行映射，因此一个任务有可能被多次重复映射，算法可利 用更新的资源状态得到更好的映射结果，但是这种多次映射策略显然加重了系统 第9 页 国防科学技术大学研究生院工学硕士学位论文 负载。 还有s s a n y a l s 等提出的基于遗传算法的任务匹配【1 6 】等算法。这些方法均是 基于计算资源做的研究。在文献【1 8 】中a l h u s a i n i 等人扩展了资源类型，将其他 资源如数据资源、i o 设备等也包括在待分配的资源内，提出了一个资源协同分配 映射框架。 a l h u s a i n i 算法的基本思想是对于每个任务t i ，在映射事件发生时， 首先完成自身所需时间最少的机器( 最优机器) ，寻找一个最优机器根据算法进 行比较，最优条件满足者，则任务可在该机器上执行。a l h u s a i n i 算法通过尽早释 放资源，在信息汇集阶段向，有向无环图中的任务t i 随机分配到系统中的某资源 上，然后根据迁移算法对比，判断是否迁移到其他更合适资源。 2 3 2 基于资源池的资源调度算法 基于虚拟资源池的调度体系【1 9 ，系统中的资源是指系统中任何可以被调度 的实体，如计算机、数据库、存储设备等。每个资源都有其自身的唯一性。任务 是指系统中任何一个发出资源请求的实体。当接收到某个任务对资源的请求时， 资源调度系统首先选择一个运行成本或代价相对较小的一个资源集，然后在这个 资源集中进行资源选择和调度，定义这个资源集即为针对这个应用的虚拟资源池 ( v i r t u a lr e s o u r c ep o o l ，v p ) 。 两级资源池和局部优先策略【2 0 l ，在多级网络结构的集群系统中，定义了多 级网络结构中的节点相关域来标识系统中同一个网络内的节点集，以实现进程迁 移的局部优先策略。任务迁移的局部优先策略的总体思想是：各个节点本地都维 护了一张相关域中的负载信息表，在节点超载时，如果相关域中有欠载的节点， 则优先在相关域中迁移，以达到局部负载平衡，否则，在全局资源列表中查找空 闲节点，作为任务迁移的目标节点。 2 4 任务调度相关技术 任务调度问题由来已久，现有的调度方式有很多，分类方法也有多种，本章 将讨论一种传统层次分类【2 1 】及其在加载任务调度上的应用，以及在面向多资源环 境的一些典型的任务调度算法。 2 4 1 相关的经典任务调度策略分类 文章2 1 】将相关的加载任务调度策略分类做了归纳如下： 局部调度和全局调度 局部调度指的是在单结点上的加载任务调度；全局调度是指在多个结点上的 第1 0 页 国防科学技术大学研究生院工学硕士学位论文 任务调度。局部调度和全局调度可以看成独立的两个问题，用各自独立的加载结 点加以解决。在此我们主要研究全局调度。 静态调度和动态调度 静态调度是在编程时或编译器在编译时将任务分配给加载结点；动态调度是 把每个任务动态地分配给加载结点。 最优调度和次优调度 最优调度要取决于一些评判的标准函数，如最小的总的执行时间，最大的资 源利用率，最大的系统的输入输出量等等，但是，很多条件是不可能满足的；次 优调度则是求得一个接近最优调度的解。 近似优化调度和启发式调度 近似优化调度是去寻找一个相对令人满意的解，而不是去查找整个解空间得 到一个最优解；启发式算法则是利用系统的一个特点，运用一些有效的假设，去 得到一个近似的最优调度解。 分布式调度和非分布式调度 分布式调度是指全局动态调度在分布的多个加载结点上执行，非分布式调度 是指全局动态调度是在单个结点上执行。 合作式调度( c o o p e r a t i v e ) 和非合作式调度( n o n c o o p e r a t i v e ) 在分布式调度中，合作式调度是指每个加载结点不仅要执行自己的调度加载 任务，而且还要考虑共同的系统目标；非合作式调度是指在每个加载结点仅执行 自己的调度加载任务。 2 4 2 面向多资源的任务调度典型算法 下面讨论在多资源调度方面的一种分类及其典型算法f 2 1 】； 表( l i s t ) 调度 表调度的基本思想是首先通过对节点按照其优先级进行排序；排序后构造一 个调度列表分为静态的表调度和动态的表调度算法，其核心是节点优先级的确定， 决定节点优先级别的方法很多，有h l f e t ( h i 曲l e s tl e v e lf i r s tw i t he s t i m a t e dt i m e ) 算法【2 3 1 ，i s h ( i n s e r t i o ns c h e d u l i n gh e u r i s t i c ) 算法【2 4 j ，e t f ( e a r l i e s tt i m ef i r s t ) 算法【2 5 1 ， m h ( m a p p i n gh e u r i s t i c ) 算法【2 6 】等。 基于任务复制的调度 基于任务复制调度算法的思想主要是冗余地将任务图中的任务映射到一些处 理器上，这样可以减少任务到达处理器的总开销，出于避免某些前驱任务的通信 数据的传输的考虑，实际上利用了处理器的空闲时间复制前驱任务，从而减少处 理器等待的时间。复制人物策略是不同的，因此形成了不同的基于任务复制的调 第1 1 页 国防科学技术大学研究生院工学硕士学位论文 度算法。典型算法有：d s h ( d u p l i c a t i o ns c h e d u l i n gh e u r i s t i c ) 算法【z 川、 b t d h ( b o t t o m - u pt o p d o w nd u p l i c a t i o nh e u r i s t i c ) 算法【2 副、d f r n ( d u p l i c a t i o nf i r s t a n dr e d u c a t i o nn e x t ) 算法【四j 等。 基于任务集群或聚类的调度 该类算法的基本思想是：集群是不受限的，将任务图中所有任务映射到集群 上。算法中所有的任务都可以进行集群，而集群的任务不一定要是就绪的。在每 个集群循环中是把上一步的一些集群合并成为新的集群。如果处理器数目有限， 在集群步骤中还必须考虑使集群的数目与可用的处理器数目相等。典型算法： d s c ( d o m i n a n ts e q u n c ec l u s t e r i n g ) 算法【3 0 】、d c p ( d y n a m i cc r i t i c a lp a t h ) 算法f 3 l 】等。 非确定性调度 非确定性调度技术又称为随机搜索调度技术，它主要是通过有导向的随机选 择来搜索问题的解空间而并不是单纯的随机搜索。这类技术组合前面搜索结果的 知识和特定的随机搜索