（计算机软件与理论专业论文）社保联网审计中增量数据分布式处理的研究.pdf

c l a s s i f i e di n d e x ： u d c ： ad i s s e r t a t i o nf o rt h ed e g r e eo f m e n g r e s e a r c ho nd i s t r i b u t e dp r o c e s s i n go f i n c r e m e n t a ld a t ai nn e t w o r k b a s e d s o c i a l - s e c u r i t ya u d i t c a n d i d a t e ： s u p e r v i s o r ： a c a d e m i cd e g r e ea p p l i e df o r ： s p e c i a l i t y ： d a t eo fs u b m i s s i o n ： d a t eo fo r a le x a m i n a t i o n ： u n i v e r s i t y ： h o uj i a q i a s s o c i a t e p r o f p i a ox i u f e n g m a s t e ro fe n g i n e e r i n g c o m p u t e rs o f t w a r ea n dt h e o r y j a n u a r y ，2 0 1 0 m a r c h ，2 0 1 0 h a r b i ne n g i n e e r i n gu n i v e r s i t y 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：次隆有 日期：芦细年三月6 日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 日往授予学位后即可口在授予学位1 2 个月后 口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：磁翰 日期：如加年? 月厶日 聊( 签字) ：粥辟 如1 1 年只b l 哈尔滨工程大学硕士学位论文 摘要 近年来，随着互联网和分布式计算的发展，海量数据处理的性能有了很 大提升。在许多应用领域中，都需要从海量数据中提取出增量数据来满足某 种业务需求，尤其是对于不断更新的源数据，往往需要定时抽取出增量数据。 在目前和将来的研发中，如何快速的识别出增量数据，并进行提取、存储以 及传输，将逐渐成为国内外学者关注的研究方向之一。在社会保障联网审计 中，需要提取出增量数据来做为审计预警系统的源数据。增量数据的识别与 提取技术是实现整个系统的关键技术之一。 本文介绍了分布式系统的发展、负载均衡策略和国内外对于增量数据识 别技术的研究情况，给出了基于分布式处理的增量数据处理方案，对增量数 据分布式处理的数据分割、数据分配、增量识别以及数据回收等过程进行了 研究，为了提高处理效率还设计了负载平衡策略，结合多线程技术进行实现， 并做了性能分析和系统设计。 最后，以某省的审计数据作为实验数据，在该省审计厅的曙光机群的基础 上搭建了平台，并进行了仿真实验，性能测试表明该方法基本满足了联网审计 业务的功能要求，完成了较高效的增量数据识别工作，审计工作的时效性得到 了提高。 关键词：分布式计算；增量数据；负载均衡；社会保障审计 哈尔滨工程大学硕士学位论文 a b s t r a c t i nr e c e n ty e a r s ，w i t ht h ed e v e l o p m e n to ft h ei n t e m e ta n dd i s t r i b u t e dc o m p u t i n g ， t h ep e r f o r m a n c eo fm a s s i v ed a t ao p e r a t i o nh a si m p r o v e d i nm a n y 印p l i c a t i o n a r e a s ，i t sn e c e s s a r yt oe x t r a c ti n c r e m e n t a ld a t af r o mt h em a s s i v ed a t at om e e tt h e d e m a n d so fab u s i n e s s ，e s p e c i a l l yi ti sr e q u i r e dt oe x t r a c tf i xt i m ei n c r e m e n t a ld a t a f r o mc o n t i n u a l l yu p d a t e ds o u r c ed a t a t h e r e f o r e ，h o wt oq u i c k l yi d e n t i f yt h e i n c r e m e n t a ld a t af o re x t r a c t i o n ，s t o r a g ea n dt r a n s m i s s i o n , w i l lg r a d u a l l yb e c o m et h e f o c u so fa t t e n t i o no ff o r e i g ns c h o l a r s t h i st h e s i si so nt h eb a c k g r o u n do ft h es o c i a ls e c u r i t yn e t w o r ka u d i t i te x t r a c t s t h ed a t aa si n c r e m e n t a ls o u r c ed a t af o rt h ea u d i tp r e d i c ts y s t e m i tm a k e s p o s t - a u d i t t u r n e di n t o c o n c u r r e n ta u d i t t ok e 印a b r e a s to fc h a n g e si nt h es o c i a ls e c u r i t yd a t a , a n df o u n dt h a tt h ea u d i ti nd o u b ta n df o r e c a s tl a w so fd a m sb a s e d0 1 1t h ed a t a c h a n g e s i n c r e m e n t a l d a t ar e c o g n i t i o na n de x t r a c t i o n t e c h n o l o g y i sak e y t e c h n o l o g yf o rt h ee n t i r es y s t e m t h i st h e s i sd e s c r i b e st h ed e v e l o p m e n to fd i s t r i b u t e ds y s t e m s ，l o a db a l a n c i n g s t r a t e g i e sa n dt h ei n c r e m e n t a ld a t ar e c o g n i t i o nt e c h n o l o g yr e s e a r c hs i t u a t i o na t h o m ea n da b r o a d am e t h o do fi d e n t i f i c a t i o nt h ei n c r e m e n t a ld a t ah a sb e e n p r o v i d e d ，w h i c hi sb a s e do nd i s t r i b u t e dp r o c e s s i n g t h i sp a p e rb a s i c a l l yr e a l i z e d i n c r e m e n t a ld a t a p r o c e s s i n gs y s t e m ，w h i c h i n c l u d e df o u rm o d u l e s ：d a t a p a r t i t i o n i n g ，d a t ad i s t r i b u t i o n , i n c r e m e n t a ld a t ai d e n t i f i c a t i o na n dt a s kr e a l l o c a t i o n , a n dd a t ar e c o v e r y ap l a t f o r mh a sb e e nb u i l tb a s e do np e r f o r m a n c ea n a l y s i sa n d s y s t e md e s i g n i nt h i sp a p e rad i s t r i b u t e da p p r o a c hc o m b i n e dw i t hm u l t i - t h r e a d i n g t e c h n o l o g yh a sb e e nu s e d , a n dl o a db a l a n c i n gh a sb e e nc a r r i e do u ta c c o r d i n gt o v a r i o u ss u b - n o d e sa l l o c a t i o no f t a s k s i nt h ee n d ，u s i n gap r o v i n c ea u d i td a t aa se x p e r i m e n t a ld a t a , s i m u l a t i o n e x p e r i m e n t sh a v eb e e nd o n eo nt h ep l a t f o r mw h i c h i sb u i l d e d0 1 1d a w n i n gc l u s t e ro f t h ea u d i to f f i c e b yt h ep e r f o r m a n c et e s t s ，i ts h o w st h a tt h ep l a t f o r mc a nb a s i c a l l y 哈尔滨工程大学硕士学位论文 m e e tt h ef u n c t i o n a lr e q u i r e m e n t so fn e t w o r ka u d i to p e r a t i o n s i tc o m p l e t e da l l e f f i c i e n ti d e n t i f i c a t i o no fi n c r e m e n t a ld a t a ，a n dt h et i m e l i n e s so ft h ea u d i tp r e d i c t s y s t e mh a sb e t ae n h a n c e d k e y w o r d s ：d i s t r i b u t e dc o m p u t i n g ；i n c r e m e n t a ld a t a ；l o a db a l a n c i n g ；s o c i a l s e c u r i t ya u d i t 哈尔滨工程大学硕七学位论文 目录 第l 章绪论1 1 1 课题背景和意义一1 1 2 国内外研究现状2 1 2 1 分布式系统的发展2 1 2 2 增量数据识别的研究现状3 1 2 3 分布式系统的负载均衡5 1 3 研究内容与论文组织方式。8 1 3 1 研究内容8 1 3 2 论文组织方式9 第2 章增量数据处理技术与分布式编程1 0 2 1 重复数据识别技术l o 2 1 1 临近排序算法10 2 1 2 多趟邻近排序算法。1 1 2 2 增量数据提取方法比较1 2 2 3 分布式编程技术l3 2 4 本章小结l5 第3 章增量数据的分布式处理1 6 3 1 增量数据分布式处理流程1 6 3 2 提取数据分布特征18 3 3 数据分割2 0 3 4 数据分配2 2 3 5 增量数据识别2 4 3 6 负载均衡调度2 7 3 7 数据回收和整合3 4 3 8 本章小结3 5 第4 章系统的设计方案和实施3 6 哈尔滨工程大学硕+ 学位论文 4 1 系统设计3 6 4 2 社保审计中增量数据处理算法的改进4 0 4 3 实验方案设计和性能分析4 1 4 3 1 实验方案设计4 1 4 3 2 运行结果分析4 2 4 4 本章小结4 4 结论4 5 参考文献4 6 攻读硕士学位期间发表的论文和取得的科研成果5 0 致谢。51 哈尔滨工程大学硕士学位论文 第1 章绪论 1 1 课题背景和意义 随着社会信息化的发展，人们经常需要对海量信息进行数据挖掘，在政 府、银行、企业等领域，增量数据对于用户的数据分析、决策支持都有很大 的参考价值。增量识别技术是从海量数据中提取出增量数据的计算机处理技 术，近年来，由于其潜在的应用价值，越来越受到国内外学者的关注。 增量数据在数据挖掘、预测和模型检测等领域都具有重要的意义，它更 能够体现数据的变化情况。在数据挖掘领域，新增数据对商业规律的发现有 重要意义，更容易发现数据之间的关系；在预测领域，通过对增量数据的分 析，能够预测未来数据的变化情况；在模型检测领域，当模型系统出现异常 时，新增数据往往更有研究意义。 在社保审计领域，计算机审计技术主要历经计算机辅助审计、帐套式计 算机审计和数据式计算机审计等几个发展阶段。近两年，为了降低事故发生 时的造成的影响，提出了由“事后审计 变“事中审计 的思想，为了完成 这个任务，哈尔滨工程大学在原有系统基础之上开发了预警审计系统，它是 一个弱实时的审计系统，能够在一定的周期内对审计机关的数据进行审计， 及时发现问题、减少损失。增量识别技术是社保联网审计系统的关键，它要 求在不改变原始信息系统的情况下，快速的在海量数据中识别并提取出增量 数据，这需要涉及很多相关的技术，如采集、转换、存储和处理等。在处理 海量数据方面，分布式计算系统有着先天的效率优势。本文将针对增量数据 的识别技术进行了探讨和研究，搭建了实验系统，并给出了适用于该系统的 负载均衡策略，最后，在我国某审计机关进行了实验仿真。 本课题来自于哈尔滨工程大学分布式计算与仿真实验室的社保联网审计 项目组。2 0 0 2 年7 月，国家计委批准国家审计署建设“金审工程 ，哈尔滨工 哈尔滨工程大学硕士学位论文 程大学分布式计算与仿真实验室担任了项目的主要研发工作，经过多年的项 目实践和理论上的探索，已对五险( 基本养老保险、基本医疗保险、工伤保险、 生育保险和失业保险审计) 五个险种进行的一定范围的审计，在全国的多数大 中城市进行了软件部署和项目实施。随着审计事业的发展，为了满足审计业 务的需求，分布式审计系统已经事在必行，分布式联网审计采用不同的硬件 设备和软件系统，尤其是操作系统和数据库软件的不同也产生了很多新的问 题。 如何能实现系统的高效计算，保证高效的提取出新增数据，如何对整个 系统进行合理的任务调度，都将是必须面对的问题。同时还要考虑到系统的 可扩展性，使之能够适应审计业务的改变，也是本论文要解决的问题，总体 来说，该课题必须在不修改原始数据结构的情况下，实现增量数据的快速提 取，同时进行系统的负载均衡调度，使得系统在高效提取增量的同时，还具 备良好的可扩展性，以应付数据规格和业务的改变。 1 2 国内外研究现状 1 2 1 分布式系统的发展 近年来，随着分布式系统理论的不断完善，国内外已有很多成功的案例， 分布式计算技术也得到了广泛的应用。同多数系统一样，分布式系统对外提 供一个独立的计算功能，对于用户而言，系统的内部完全是透明的，它们就 像一个不可分割的统一整体一样。同时，在系统内部也分为多种通用资源， 包括物理资源和逻辑资源，并且能够进行任务的动态分配。物理资源和逻辑 资源是分散的，它们通过计算机网络进行信息传输和任务调度。如果是分布 式的操作系统，它会为管理计算机资源提供一个全局的方式，就像使用的是 一台计算机一样。对用户而言，通常，分布式系统只有一个模型。在实际的 操作系统之上，通过设计一个软件中间件来实现此模型。万维网就是一个典 型的分布式系统的应用实例，在这个分布式系统中，所有的资源，包括网页、 2 哈尔滨工程大学硕士学位论文 图片等等，使用起来就好像是在本地一样，可以随意访问。 分布式计算机系统是一个计算系统，它对外呈现成一个有机的整体，就 像一个单机服务器一样。它包括两层含义，第一、从物理角度分析，组成他 的每一个计算机都能够进行独立的运算，也就是它们是自主的。第二、逻辑 角度方面，对于用户而言，整个系统就是一台计算机，而内部关于网络、并 行、集中的运算以及各个计算机之间的协作全部是透明的。 分布式系统原理方面，辛春生在其译著中对分布式体系结构、进程、通 信、同步化、一致性和容错、安全等问题进行较为细致的叙述，顾铁成等 人也在其译著中对分布式计算的原理和实现技术进行了介绍瞳8 1 。 1 2 2 增量数据识别的研究现状 随着经济的快速发展，我国各个行业信息系统建立逐步完善，而银行、 企业、交通和政府等部门单位的数据也成指数级增长。在这种大环境下，海 量数据的处理技术显得尤为重要，在很多领域，诸如w e b 领域的应用、数据 挖掘、多维分析等都需要数据的增量进行数据分析，而对很多领域而言，数 据的增量部分往往只占到全部数据的很少的一部分，增量数据的识别却需要 大量的时间，严重影响了对其数据分析和数理统计工作的进行。在数据量激 增的情况下，为了保证数据分析、数据挖掘和预测等研究工作的顺利展开， 如何从海量数据中高效、准确的识别并抽取新增数据，便成为一个必须解决 的技术问题。 国内外对于各种传输协议以及集成方案的研究虽然比较多，但对于在异 构数据库集成中起到决定性作用的增量数据识别方法研究却相对较少。在这 方面，国外的参考资料也较少，近期研究人员已经意识到这种不足，并且从 多方面进行了此类工作的探索。 目前，增量数据的提取方法之一是借助于数据库软件厂商提供的工具或 者数据库本身提供的功能进行增量数据处理，另一种方法是利用重复数据识 别技术，在数据挖掘领域的数据清理方面，对重复数据的识别技术有较多的 哈尔滨工程大学硕十学位论文 研究。 文献 1 7 】给出了在特定的数据库软件环境下的一种增量数据提取方法， 从d b 2 中提取增量数据的方法，最后推广应用到所有支持s q l 3 查询语言的数 据库，其缺点是针对表操作，对数据源要求较多，通用性差。 文献 1 8 】给出了通过使用o r a e l e l o g 数据库的l o g m a n a g e r i 具进行增量数 据的提取方法，虽然能够完成一般的任务，但在个性化需求方面做的不够， 并且应用范围仅限于该类型数据库，数据源要求也是以表的形式存储。 另外，在异构数据库集成方面，也有捕获数据变化的常用方法，如基于 快照法、触发器法、日志法、时间戳法a p i 法、影子表法、变更轨迹法等， 在文献 1 9 】中，刘伟对这几种方法的详细性能进行了分析。 上面所说的几种方法主要应用于各自对应的数据库软件，适用范围小， 通用性差。虽然多数数据库软件上都可以实现简单的快照法来捕获到变化， 但所需的代价大，效率不高，在一些功能上支持欠佳；基于日志的方法，可 以通过日志解析工具对日志文件加以解析，可以得到增量数据，这种方法的 最大优点就是不需要占用太大的空间，缺点是有的数据库厂商都公开其产品 的日志格式，这对于开发基于多种异构数据库系统的系统，实现起来难度很 大；触发器方法可以提高系统的效率，往往结合其它的实现机制来实现同步 和对等式复制，但是资源占用量较大，使得系统性能较低、操作复杂，而且 并非所有的数据库系统都支持多触发器机制。 应用数据清理中的重复数据识别技术解决增量提取的方法也成为人们研 究的热点之一。 在文献 2 0 】中，h e m a n d e z 提出了邻近排序算法，这是一种基础的重复数 据识别方法，是目前应用比较广泛的方法。文中提出了滑动窗口的概念，大 大提高了算法的效率，但不足之处是窗口的大小难以确定，容易出现记录漏 配现象。 很多学者基于邻近排序算法进行了改进。为了记录漏配的现象，在文献 【2 1 中h e m a n d e z 又提出了多趟邻近排序算法，通过计算传递闭包，解决了因 4 哈尔滨工程大学硕士学位论文 为窗口小或者相似记录之间的距离太远问题，从而解决了记录漏配现象。 在文献【2 2 】中，刘伟等人对多趟邻近算法进行了改进最后计算传递闭包 的环节，并通过使关键字按照字典序排列，减少了相似记录比较的时间消耗。 文献 2 3 1 中，将相似记录存于一个簇中，相似记录的判断问题变转化为 寻找无向图的联通子图问题，并且提出了解决无向图的连通子图的判定问题 的一种方法，进而提高了算法的效率。 文献【2 4 】中给出了基于优先队列基础上的临近排序算法的思想，文献 2 5 】 提出了重复记录的增量式识别算法。 另外，文献【2 6 】给出了一种利用权重提高相似记录检测精度的方法。在 文献 2 7 q h ，在多源w e b 数据集成中的重复记录检测方面，黄健斌引入了自 适应字符串距离度量的记录相似度学习方法，在重复记录检测的精度方面有 所提高。 1 2 3 分布式系统的负载均衡 负载均衡问题是分布式系统提高计算效率的主要方式，在集群系统中采 用负载均衡能够提高系统的性能【3 5 】，负载均衡问题的计算难度和时间复杂度 都与图论中的哈密尔顿问题相似，属于n - p 完全问题。近二十年以来，国内 外的研究人员对静态负载均衡和动态负载均衡都进行大量较深入的研究和实 践。由于直接精确求解的耗时往往是人们难以忍受的，所以，现阶段在实际 应用中，采取的方法主要处于两种思路，一种是求局部的最优解，之后对最 优解的某种性能给出一个评判的衡量标准，这往往需要借助一些辅助的数据 结构来完成；另一种是利用一些职能搜索算法求解全局最优解。 负载均衡策略主要分为分布、集中、全局和局部的负载调度算法。z a k i 等人对负载均衡策略做了很好的分类，并对部分策略进行了组合应用【5 】。还 有很多学者对静态负载均衡、动态负载均衡及其在并行计算和机群方面进行 了研究。 在文献【3 】中，温钰洪等人对静态负载均衡进行了较细致的分析，并采用 智能搜索的a 幸算法对静态任务进行划分，得到最佳处理机调度方法。文献 4 】 将遗传算法应用于负载均衡策略求解、文献 5 】中模拟退火算法，它们都属 于全局的静态负载均衡策略，能够得到全局的最优解，但在庞大的分布式系 5 哈尔滨工程大学硕士学位论文 统中静态负载均衡的处理时效并不高。 在实际应用中，动态负载均衡策略往往能比静态负载均衡能带来更好的 系统利用率，虽然它的求解并非全局最优解，但在过去的研究中，人们已经 设计出很多模型。通过这些模型，能够更好地设计、实现负载均衡策略，并 衡量一个负载均衡算法的优劣。 在动态负载平衡方面，国内外的很多学者都提出了一些模型理论，其中 比较著名的有基于水动力学模型的调度算法【6 】、基于梯度模型的调度算法 7 1 、 基于随机选择任务移动结点的概率调度算法【8 】，以及自适应的近邻契约算法 【9 】笔 弋to 进程的动态迁移是负载均衡调度过程中必须面对的一个问题，在这方面 清华大学的傅强提出了一种适用于机群系统的任务动态调度方法，它是一种 惰性的任务调度方法，巧妙的降低了进程的动态迁移的频率【l 们。 在文献 1 1 】中，给出了均衡调度的一个一般模型，将负载平衡的问题的 各个影响因素抽象成一个四元组，对负载平衡问题的各种影响因素做了很好 的总结。 与静态负载均衡和动态负载均衡相对，有人还提出了一种基于公平指标 的调度方法【1 2 】。 还有一种划分的方法，将负载均衡调度策略分为，发送者驱动和接收者 驱动两大类，在文献【1 3 】中，d l e a g e r 做了详细的研究并付诸实践，证明了 在分布式系统中，任务超载情况下，接收者驱动比发送者驱动会来带更好的 效果。 在文献【1 4 】中，陈华平给出了一个通用的模型，并在基于接收者驱动和 发送者驱动之上提出了混合驱动模型，给出了详细的算法设计。 在文献 3 3 】中，张克君等人给出了一般机群管理软件的构建模型，采用 j a v ar m i 通信协议解决了远程管理问题，利用虚拟命令解决了跨平台问题， 这一点可以结合到负载均衡的处理当中。 在集群负载均衡系统的性能评价方面，唐丹等人证明了在集群系统中实 现动态负载平衡的必要性，并建立了一个抽象模型，然后细化模型结点本地 处理部分，对几种负载平衡的算法性能进行了分析【3 6 】。 在并行程序设计方面，它的调度算法和分布式的调度异曲同工，文献 4 0 】 6 哈尔滨工程大学硕士学位论文 对p v m 上的任务动态调度也进行了研究。同济大学的王力生还提出了多处 理器系统下的负载平衡【2 9 1 。 调度算法的自适应性也体现了一个调度算法的优劣，国内外的学者也进 行了较深入的研究，对于调度算法的自适应做了概括分析，有的基于中间件 理论【4 1 1 ，有的基于反馈 4 2 1 ，有的则是基于i p 报头多域分类方法m ，也有 的利用模糊控制技术的调度策略【4 3 1 。 另外，还有一些学者另辟蹊径。在文献 3 7 】中，作者将资源负载分类处 理，并给出了负载均衡的方向性等概念，不但减小了内部通信量，而且抑制 了分布式系统负载均衡过程中产生的抖动现象。文献【3 8 】 3 9 】基于a g e n t 策略， 分别将人工智能技术和重定向机制应用于负载均衡领域，补充了传统负载均 衡策略的不足。 虽然国内外的很多学者对这个领域做了很多的研究工作，也取得了很多 显著的成绩，但是，并不能得到一个万能的负载均衡方法，首要的原因是在 数学上并没有得到本质问题的解决；另一个主要的原因是所采用的负载均衡 策略受太多的实际因素的影响，有以下几个方面： ( 1 ) 网络拓扑结构和系统规模方面，负载平衡算法的性能评估受网络拓 扑结构和系统规模的影响很大，目前的负载均衡方法都是与网络拓扑结构、 机器数目相关的非通用算法【l5 1 。 ( 2 ) 各个结点的软硬件方面，分布式系统中各结点的硬件条件可能不同， 如调度机和子结点的处理器结构、指令集等，软件的操作系统等。 ( 3 ) 为了实现负载均衡而存在的一些附加行为，往往会带来负面的效果， 必须合理利用，如为了实现分布式系统的负载平衡，系统内各结点负载信息 的收藏、存储、决策以及任务迁移都将导致一定的额外开销，如果不能有一 个正确的评估，处理不当，甚至可能造成事倍功半。 ( 4 ) 进程迁移和网络通讯方面，一般的分布式系统各结点之间通过网络 相连，这造成迁移到其它结点执行的任务，要先迁移到该结点，之后再处理 任务，它的响应时间比本地执行的时间要长。 虽然采用不同的模型和方法，但他们都是基于分布式的调度之上。不管 7 哈尔滨工程大学硕士学位论文 是哪一种调度算法，这三个问题都是必须解答的，( 1 ) 负载平衡调度启动的 时机：( 2 ) 本次负载平衡调度执行的源结点和目标结点需要确定；( 3 ) 调度当 前结点的那些任务。如果按照驱动者的不同，可以分为接收者驱动和发送者 驱动这两大类。 现有各种技术都已经被普遍采用，但是各种技术都有各自不同的适用情 况，因此针对分布式系统中的负载均衡问题，要对负载均衡策略进行具体适 应本地系统的设计使之达到更高的系统效率。在本论文中，给出了在增量数 据分布式处理系统中的一种负载均衡调度策略以提高该系统的运行效率。 1 3 研究内容与论文组织方式 1 3 1 研究内容 增量数据处理技术能够在海量信息中快速提取出新增数据，增量数据是 很多数据分析方法必备的源数据，在信息技术飞速发展的今天，许多领域的 数据分析工作都需要以增量数据为基础。 本文将介绍分布式系统及其负载均衡技术和增量处理技术，给出基于分 布式处理的增量数据处理方案，对增量数据分布式处理的数据分割、数据分 配、增量识别以及数据回收等过程进行研究，并做详细的性能分析，进行系 统设计。同时，为了提高分布式处理的增量数据处理系统的工作效率，还将 结合实际情况为该系统设计负载均衡策略，在一定层面上屏蔽了硬件环境的 差异，提高系统的通用性。 本文将以联网社保审计系统为基础，针对联网社保审计的具体需求，基 于j a v ar m i 技术搭建增量数据分布式处理系统实验平台，对增量数据分布式 处理的数据分割、数据分配、增量识别以及数据回收环节给出了社保联网审 计的解决方案。 8 哈尔滨工程大学硕士学位论文 1 3 2 论文组织方式 论文的具体安排如下： 第1 章论述分布式计算、分布式系统中的负载均衡以及增量数据提取等 领域的国内外研究现状，根据课题的背景，提出了针对分布式联网审计的实 际要求，对增量数据提取技术的急迫需要，并阐述了论文的技术路线和主要 内容框架。 第2 章简要介绍当前增量数据识别的主要方法，在各种技术方案之间进 行比较，分析目前增量数据处理方法，同时，也介绍实现分布式计算的主流 编程技术j a v ar m i 。 第3 章给出了基于分布式计算的增量数据处理方法的思想和实现方法， 对关键技术进行说明和实现，详细介绍了数据的分布特征提取、分割、增量 数据提取和任务调度以及增量数据回收等模块的实现方法，并对部分算法性 能进行了分析。 第4 章简要介绍了系统的设计方案，并结合分布式编程技术在实验平台 下进行实践工作。对两种增量数据抽取进行了比较，给出了比较结果。 最后在结论中对本文的研究工作做了总结，并对未来的工作内容进行了 展望。 9 哈尔滨工程大学硕十学位论文 第2 章增量数据处理技术与分布式编程 本章将介绍增量数据提取技术，对几种提取方法的性能和适用情况进行 比较，最后介绍分布式编程技术基础。 2 1 重复数据识别技术 在实际应用中，增量数据的提取方法主要分为两种，一种是借助于数据 库软件厂商提供的工具或者数据库本身提供的功能来实现增量数据的提取； 另一种方法是利用重复数据识别技术，在数据挖掘的数据清理领域，对重复 数据的识别技术有较多的研究，可以借鉴到增量提取技术中，其中应用较多 的有临近排序算法和多趟邻近排序算法，下面将对这两种方法进行介绍。 2 1 1 临近排序算法 一般情况下，增量数据只占全部数据量的小部分，因此，增量数据处理 程序运行的多数时间是在进行重复数据的匹配问题，临近排序法是一种常用 的重复数据识别方法。 早在19 9 5 年，h e m a n d e z 就提出了邻近排序算法( s o r t e dn e i g h b o r h o o d m e t h o d ，s n m ) ，后来许多学者的研究工作都是基于此方法之上的改进。在 s n m 算法中，h e m a n d e z 提出了滑动窗口的思想，先对数据源进行排序，但 并不是全排序，而是每次利用不同的属性集进行排序，然后再检查窗口内的 数据是否匹配，之后窗口向下滑动。因为该法中数据的比较仅限于一定窗口 范围，减少了数据匹配的计算次数，所以提高了重复数据识别的效率。 s n m 算法的过程可以分为三个阶段。首先，进行关键字的选择，关键字 是由一个或者几个属性组成的集合，能够唯一的标识一条记录。一般来说， 需要根据实际的应用背景去确定主键。然后，通过上面的关键字对记录进行 排序，得到对关键字有序的数据集合。最后，根据滑动窗口思想，对数据进 行窗口范围内的比较。如图2 1 所示，如果窗口大小规定为w ，每次窗口向 下移动一条记录，那么每次滑动将有一条新记录进入，同时，有一条原窗口 1 0 哈尔滨工程大学硕士学位论文 中的记录推出窗口，新进入窗口的记录只于窗口中的另外w 1 条记录进行比 较，而不需要全部数据集合的比较，进而减少了数据匹配所消耗的时间。 ： 图2 1 借助滑动窗口扫描数据集示意图 在一个有”条记录的数据集中，如果窗口大小为w ，采用s n m 算法进 行重复数据识别时，对于每一条记录仅与同一窗口中的另外w 1 条进行比较， 比较次数为n ( w 1 ) 。经过分析可知，在按照关键字有序之后，该算法可以在 线性规模内进行重复数据的识别。 从理论分析的角度看，s n m 算法将重复记录比较的时间缩短了很多， 但是，也有以下几个不可避免的缺点：首先，在关键字的创建方面，尚没有 统一的规则，需要根据各自的应用背景来确定，如果关键字的选取不能代表 数据的唯一性，那么，将造成大量不重复的记录被安排在相邻的位置，在接 下来的窗口移动过程中，窗口内进行的重复记录判断结果不准确。其次，因 为各个数据集合的相似程度不同，滑动窗口的大小w 值也难以确定，如果窗 口设置过小，将造成记录匹配不准确；如果窗口过大，将造成多余的记录比 较次数，降低算法的效率。 2 1 2 多趟邻近排序算法 为了解决s n m 算法窗口大小难以确定的问题，h e m a n d e z 有提出了多 趟临近排序算法m p n ，该方法通过多个关键字的创建并通过计算传递闭包 很好的解决了窗口较小可能引起的记录漏配问题。 应用m p n 算法时，首先，确定多个关键字和滑动窗口的大小w ，其中 哈尔滨工程大学硕士学位论文 w 可以取相对较小的数值：然后，按照每个关键字进行临近排序的聚类过程， 进行重复相似记录的匹配，采用规则库来生成一个等价原理，作为将来合并 记录的原则，将每个关键字排序后判定为相似记录的数据合并为一组，合并 过程中，将假定数据的重复具有传递性，这样就可以计算传递闭包了，传递 闭包是指，如果x l 与耽是相似重复记录，娩与勋是相似重复记录，则x l 与 的也是相似重复记录。关于传递闭包的计算，在文献 2 3 】中给出了详细的计 算方法。 2 2 增量数据提取方法比较 在本小节中，将对一些常用的增量数据提取算法进行比较，通过对算法 的分析提出分布式增量数据处理算法。 增量数据的处理的准确度和效率是衡量一个增量数据处理算法好坏的标 准，同时，它们也直接体现了信息系统的性能。当前使用的增量数据提取方 法主要有基于触发器法、基于日志法、基于快照法以及基于时间戳法、变更 轨迹表法和影子表法等【1 9 1 ，下面将对其中的一些方法进行介绍。 快照法是一种简单的处理方法，它可以方便的捕获到数据的变化，目前， 多数数据库上都可以实现。其应用范围不仅仅是结构化的数据源，半结构化 的数据源也同样可以实现。但是，综合效率不高，在同步复制和对等式复制 上支持欠佳，所以，这种算法的应用现在已经不多了，在海量数据处理方面， 快照法的所提供的性能很难满足用户。 基于日志法，目前几乎所有的数据库都存有日志文件，日志中记录着数 据库的数据变化事件，包括通过应用程序的命令、数据管理员直接在后台操 作的命令都会记录在日志文件中。它们构成按照一定的格式组织成的文件， 几乎所有流行的应用数据库的日志文件格式都不一样，有的可以通过相应的 技术手册查阅到，有的数据库厂商还直接提供了日志解析工具软件。如果可 以获得日志文件，通过对其解析，就可以得到数据的更改情况，当然也可以 通过分析得到增量数据。这种方法所需的存储空间很小，但也有其致命的缺 哈尔滨工程大学硕+ 学位论文 点，首先，并不是所有的数据库厂商都公开其产品的日志格式，通过编码实 现日志解析的难度很大；其次，目前各种数据库系统差异很大，对于开发基 于多种异构数据库软件的系统来说，实现起来难度很大。 利用数据库软件提供的工具进行增量数据提取的方法。对于o r a c l e 数 据库，可以基于o r a c l e9 i 、1 0 9 数据库的增量数据提取原理，借用其自带的 日志解析工具l o g m i n e r 来实现增量数据的提取。对于s y b a s e 数据库，可 以基于增量数据备份的方法，利用s y b a s e 数据库系统提供的i s q l 软件， 其调用方法同完整备份基本相刚1 8 】。但是，当日志截断情况发生时，后续的 增量数据备份将不能正常进行。 基于多线程的改进型影子表法【3 4 】。这种方法的软件环境要求低，可以应 用对多种类型的数据库，识别准确率高，但处理效率不高，不适合于实时性 要求较高的系统。 上面的几种方法利用了数据库系统自身所提供的机制或者工具，对于性 能要求较高的系统来说，适用性较差，也可以借鉴重复相似记录识别方法。 下面的章节，将结合社保联网审计的具体情况，对数据的分布和特性的 分析之上，采用分布计算的形式，构建分布式计算系统，并给出基于此系统 之上的负载均衡策略，结合各个客户端硬件情况进行适当的任务分配，改进 增量数据处理的算法效率，提高了程序的灵活性和实用性。 2 3 分布式编程技术 分布式编程技术是分布式计算的实现手段，目前，较为流行的分布式编 程技术有c o r b a 、j a v ar m i 等，它们都是基于t c p 或者u d p 等网络通 信协议基础实现的，本节将对j a v ar m i 做简要的介绍。 j a v a 是一种面向对象的编程语言，s u n 公司推出了j 2 e e 、j 2 s e 、j 2 m e 三个平台为快速开发提供了有利的工具， j a v ar m i 就像j a v a 版本的r p c 一样。所以，j a v a r m i 同时也具备了j a v a 的跨平台的特性，可以做到一次 编写到处运行，为分布式应用系统编程提供了一种纯j a v a 技术的解决方案。 哈尔滨工程大学硕十学位论文 如果分布式应用系统采用j a v ar m i 编程的话，只需要在客户的机器上安装 一个j a v a 运行时环境j r e ( j a v ar u ne n v i r o n m e n t ) 便可以运行。虽然有 j r m p 的支持，但是，这也带来了一点不足。下面简要介绍一下r m i 系统 的一般运行原理和r m i 编程实现的基本方法。 r m i 编程也属于一种特殊的网路编程，所以，一个简单的r m i 应用程 序也同网络编程一样，至少包括两个独立的部分：服务器端程序和客户机程 序。一般的服务器端程序都会建立多个远程对象，并且使远程对象可以被引 用，启动后进入等待状态，等待客户机调用已经生成的远程对象。 r m i 的服务器端和客户端程序通过j a v a 提供的特殊的机制的通信，所 以使用r m i 编程来实现分布式对象调用需要完成以下几步。首先，定位远 程对象，r m i 提供了两种方法来得到对远程对象的引用：一种是用r m i 的 简单命名工具，即r m i r e g i s t r y 来注册它的远程对象，另一种方法是将远程 对象引用作为一种常规操作的一部分，以此来进行传递和返回；其次，发送 命令与远程对象通信，其中，用户可以不用了解远程对象之间具体通信的细 节，因为这个完全由r m i 来处理；最后，加载作为参数或返回值传递的对 象的类字节码，而且在r m i 中，纯j a v a 对象的远程传递是被允许的，因 此，r m i 提供了对应的机制，既能够传输对象的数据也能够加载对象的代码。 利用r m i 编写分布式的应用系统，在系统运行时，本地名字与远程对象 通过服务器会调用注册服务程序使其进行关联。客户机进行调用时，将在服 务器中的注册服务程序中获得对象的名字，在利用它去搜索到远程对象，之 后调用其方法。在应用系统中，因为对象在对象流中传递，所以只有可序列 化的对象才能在服务器和客户机之间传递。j a v a 的对象序列化功能是核心 j