（计算机应用技术专业论文）数据复制模块在atc中的设计和实现.pdf

四川大学硕士学位论文 数据复制模块在a t c 中的设计和实现 计算机应用专业 研究生唐世明指导教师游志胜 空管系统对空管事务进行调度，保证空中交通的安全在空管系统中，必 须保证关键服务的容错性和高可用性。数据复制技术为实现这一目的提供了一 个较好的解决方案。因此，研究数据复制技术在空管系统中的应用，对满足国 内空管事业迅速发展的要求，探索更先进的国产民用、军用空管系统，促进现 代国防建设都有重大的意义。 本文把数据复制技术用于空管系统，设计出满足空管系统需求的数据复 制模块，实现了该模块并进行了简单的测试。首先，根据空管系统的特点分析 空管系统对数据复制模块的需求。然后，根据a t c 对数据复制模块的需求进 行几项关键的设计，主要包括状态设计，数据一致性设计，客户代理的引入， 动态改变副本集，以及缓存机制的设计。然后，根据上述设计在a t c 系统中 进行实现。最后，对本文的研究内容进行了总结，对数据复制的研究和应用前 景进行了展望。 本文采用的数据复制技术，较传统的a t c 系统所采用的双机热备份技术 具有更强的容错性和可用性，提供更强的数据一致性，在设计和实现上都具有 更好的扩展性，同时它也更复杂。空管系统中实现的数据复制模块，以透明的 方式对外提供强的数据一致性读写服务。 本文的研究是具有探索性质的研究，本文实现的数据复制模块还有待深 入的测试，设计中还应该进行更多的尝试，这些都是下一步的工作。 关键词：数据复制空中交通管制选举算法副本客户代理缓存机制 四川大学硕士学位论文 d e s i g na n di m p l e m e n t a t i o no f d a t ar e p l i c a t i o nm o d u l ei n a i rt r a f f i cc o n t r o ls y s t e m m a j o r ：c o m p u t e ra p p l i c a t i o n g r a d u a t e ：t a n gs h i m i n ga d v i s o r ：p r o f y o uz h i s h e n g a na i r t r a f f i c - c o n t r o l ( a t c ) s y s t e mm a n a g e sa i rt r a f f i ct a s k sa n dg u a r a n t e e s t h es a f e t yo fa i rt r a f f i c a na t cs y s t e mm u s tb ef a u l t - t o l e r a t e da n dh i g h l y a v a i l a b l e t h et e c h n o l o g yo fd a t ar e p l i c a t i o np r o v i d e sa l le f f e c t i v es o l u t i o nt o a c h i e v et h a tg o a l s o 。s t u d y i n gt h ea p p l i c a t i o no fd a t ar e p l i c a t i o ni so fg r e a tv a l u e f o rm e e t i n gt h en e e do fe v e rd e v e l o p i n ga t ca r e a t h em a i nt a s ko ft h i st h e s i si sd e s i g na n di m p l e m e n t a t i o no fd a t ar e p l i c a t i o n m o d u l ei na t cs y s t e m f i r s t l y , i ti n t r o d u c e sag e n e r a li d e ao ft e c h n o l o g yo fd a t a r e p l i c a t i o n ，f e a t u r e so fa l la t cs y s t e m ，a n dt h eg o a lt od e s i g nad a t ar e p l i c a t i o n m o d u l ei na l la t cs y s t e m d a t ar e p l i c a t i o nm o d u l ei na na t cs y s t e mi sr e q u i r e d t oh a v et h ef o l l o w i n gf e a t u r e s ：f a u l t - t o l e r a t e da n dh i g h l ya v a i l a b l e ，t r a n s p a r e n t ， e x t e n d a b l e ，a n dc a c h em e c h a n i s m s e c o n d l y , i tp r e s e n t sp r i n c i p a l sa n ds e v e r a lk e y d e s i g n so f t h ed a t ar e p l i c a t i o nm o d u l ei na t cs y s t e m d e s i g n si n c l u d es t a t u s ，d a t a c o n s i s t e n c y , c l i e n tc l e r k ，c h a n g i n gr e p l i c a sd y n a m i c a l l y , a n dc a c h em e c h a n i s m f i n a l l y , i ti n t r o d u c e st h ei m p l e m e n t a t i o no ft h i sd e s i g ni na t cs y s t e m t h e i m p l e m e n t a t i o ni s b a s e do nt h ef r a m e w o r ko fa c e t h ec o n c l u s i o na n df u t u r e w o r ka r ep r e s e n t e di nt h el a s tp a r t t h et e c h n o l o g ya d o p t e di nt h i st h e s i si sf a u l t - t o l e r a t e da n dh i g h l ya v a i l a b l e i t p r o v i d e ss t r i c td a t ac o n s i s t e n c y a n di t t a k e si n t oc o n c e r ne x t e n s i b i l i t yi ni t s d e s i g na n di m p l e m e n t a t i o n t h ep u r p o s ei n t h i st h e s i si st os t u d yt h ef e a s i b i l i t yo fa p p l y i n gd a t a 四川大学硕士学位论文 r e p l i c a t i o ni na t cs y s t e m m o r et e s to ft h i sm o d u l es h o u l db ed o n e ，a n dm o r e e x p e r i m e n t ss h o u l db ei n t r o d u c e di ni t sd e s i g na n di m p l e m e n t a t i o ni nt h ef u t u r e k e yw o r d s ：d a t ar e p ii c a t i o f f ：a ir t r a f f i cc o r t t r o l ( a t c ) ：e i e c t i o n a i g o t i t h m ；r e p ii c a ：c ii e n tc i e r k ；c a c h em e c h a n i s i l l 四川大学硕士学位论文 第一章序论 1 1 论文的选题背景和意义 近年来，随着我国国民经济的不断发展，我国空中交通的流量越来越大， 对于空中交通自动化管制系统的要求也越来越高所谓空中交通管制，就好比 地面上的车辆必须遵守交通规则，要接受交警的指挥一样，飞机在空中飞行也 要遵守一定的规则并且受到专门机构的指挥与调度。 安全性是空中交通最为关注的问题。空中交通管制系统具有冲突检测和预 警，飞行计划自动管理等重要功能。因此，保障空中交通管制系统的可靠、稳 定和高效，对空中交通安全具有极其重要的意义 为了实现这一目标，作者参与的a t c 系统使用了双冗余结构来保障a t c 系统的容错性和高可靠性。a t c 系统中使用的双冗余技术具有良好的容错性和 可靠性，但没有实现分布式事务意义的更新操作，在系统出错和服务器切换 时，可能丢失数据，不能最大限度地保护数据。 数据复制技术能够提供数据更新操作的原子语义0 1 ，所以能够保证分布式 副本数据的强一致性，根据完全一致的数据副本，可以建立容错且高可靠的服 务，能够保证数据不丢失且具有更好的可扩展性。 基于以上认识，作者以及所在的项目组查阅了大量的资料，研究和比较了 数据复制中弱一致性和强一致性的算法，借鉴前人的成果，对分布式副本数据 复制强一致算法进行了改进，并在空管系统中实现了该模块，进行了测试。 研究数据复制算法及其在空管系统中的实现具有重要的意义。数据复制算 法在空管系统中的实现，可以为空管系统提供强一致性的数据读写服务，能够 保证数据不丢失，在此基础上建立的关键系统服务具有容错，稳定和可靠的特 点。数据一致性算法是数据复制技术的核心部分，它具有广泛的应用前景，它 的研究有助于脱离商业分布式数据库系统而构建适合特定应用环境的数据复 制服务。数据复制技术为我们提供一个新的解决问题的思路。数据复制技术的 研究涉及同步技术，分布式事务，分布式副本控制等等，它的研究和实现，推 动相关技术的研究和应用。 6 四川大学硕士学位论文 1 2 国内外的研究现状 目前，关于数据复制及其相关技术，已经积累了大量的研究成果，形成了 一系列模型和算法；也已经出现了大量的实验和商用的成果，在分布式数据库 系统和分布式文件系统等中有着非常广泛的应用。 文献 4 5 对数据复制的强一致和弱一致做了介绍，并对两种模型进行了 分析。文献 3 对在多数据库系统下如何保证事务的原子性乜1 进行了研究，对 重做、重试、补偿和两阶段提交协议这几种方法的优缺点进行了分析，并进行 了优化。文献 7 8 介绍了原子广播“1 ，一些实际应用中借助它来实现数据复 制的强一致性，但是它必须建立在支持原子广播的平台上，依赖性太强。依据 不同的应用环境，有多种错误检测方法”1 。文献 1 3 1 4 1 5 采用心跳策 略检测错误。文献 1 7 1 8 1 9 详细论述了三种选举算法的设计和实现，其中 数据复制算法是在选举算法的基础上实现的，经过扩展后支持动态改变副本 集，能够实现容错和高可用性。目前，数据复制和一致性技术研究的内容包括 在服务器层、存储交换机层和存储层的实现，在本地镜像和远程镜像中的应用， 在分布式数据库和分布式文件系统，移动环境。”等分布式环境下的应用。 1 3 本文内容安排 本文主要在研究数据复制算法的基础上，设计并实现了数据复制模块， 把它扩展用于空管系统中，并对它进行了简单测试。需要说明的是，作者所做 的工作主要还是实验性质的，希望能够为实际的空管系统软件摸索出有价值的 方法，并对数据复制技术用于空管系统做出可行性研究。 本篇文章分为了五个部分，内容安排如下： 第一部分为引言，阐述了本文的选题背景和意义，介绍国内外的研究现状。 第二部分简要介绍了数据复制技术和a t c 系统及双机热备份实现方式，在 分析现有实现方式的基础上，结合数据复制的特点，引出了a t c 系统对数据复 制的需求 第三部分详细描述了a t c 系统中数据复制模块的设计，主要包括状态设计， 数据一致性设计，客户代理的引入，动态改变副本集，缓存机制的设计。 第四部分是a t c 中数据复制模块的实现，在基于a c e 框架的基础上，用 7 四川大学硕士学位i 宅文 c + + 将它实现为一个基础库，并对其进行了测试。 最后是对全文的总结和展望。 四川大学硕士学位论文 第二章a t c 对数据复制模块的需求 2 1 数据复制技术及应用 数据复制技术研究的是在分布式节点问进行数据复制时保持数据一致，冲 突的检测和消除，出错时数据的保护，节点动态变化时的处理等等相关技术， 数据一致性是数据复制中的关键技术。它可用于提高系统的可用性和可靠 性。关于数据复制和数据一致性已经有很多研究，很多是关于数据库系统中数 据复制和分布式文件系统中数据复制的研究。下面对数据复制和它的相关概念 和应用背景进行介绍。 2 1 1 数据复制概述 数据复制，顾名思义就是将数据从一个地点复制到另一个地点，以保持 源点数据与目标地点数据的一致“1 。可见，数据复制是在分布式节点上进行的， 为了提高分布式节点间数据的可靠性和一致性，已经形成了多种副本“”控制 技术目前这些复制技术主要分为两类，其划分的标准是0 1 ：一是更新什么时 候被传播；二是哪些副本被更新。依据第一条标准，可以复制技术分为同步复 制和异步复制；依据第二条标准，可分为主副本复制和全部更新。虽然划分的 标准不同，但在实际意义上，同步复制和全部更新，异步复制和主副本复制具 有相近的含义和类似的优缺点，这里先简单介绍主副本技术和全部更新技术， 后面将对同步复制和异步复制进行介绍。 主副本复制技术，中，每一个数据对应着一个主副本的节点，不同的数 据其主副本在不同的节点，对数据的更新，首先在主副本节点进行更新，然后 由主副本节点将更新结果传递给其他副本节点进行更新，以保持各个副本之间 的数据一致性。可以把主副本复制技术认为是异步复制技术。 全部更新技术扣1 ，对数据进行更新时，系统对所有副本上的数据进行更新， 当在所有副本上更新操作都成功后，才表示系统此次更新数据成功，如果一个 副本更新失败，系统即所有副本都退回到上一个一致性状态。全部更新具有分 布式事务语义，它能够保证系统中各个节点数据的强一致性，但实现难度更大， 会导致系统的通信量的增加，并使系统事务提交的响应时间随着系统节点增加 而增加。 数据复制在多个站点上建立备份，提高了数据的安全性，同时也提高了 9 四川大学硕士学位论文 数据的可用性，这是因为一个站点出现问题时。用户可以选择其他站点继续进 行操作，系统还可继续运行，从而数据复制提供了容错保护机制。而在数据库 系统中，数据复制最基本的功能是提高数据库的性能，提高数据库访问的效率。 它将远程数据库中的数据复制到本地，使得本地应用能够就近访问数据，从而 降低网络传输负载，提高效率。数据复制还可以提供多个站点之间的负载平衡， 合理地分配服务器，以避免某些站点负载过重。 2 1 2 强一致和弱一致 一致性问题足计算机领域很常见也很重要的一个问题，它最初用于描述 分布式或并行系统中不同的处理器如何对待共享数据。l a m p o r t 首先定义了该 问题并提出了顺序一致性模型( s e q u e n t i a lc o n s i s t e n c y ) “”。在有关多处理器和 共享内存的后续工作中，涌现出了不少更为开放的模型。 目前广泛采用的多副本数据一致性模型主要有两种0 1 ：第一种是强一致性 模型，要求数据的所有副本在任何时候都要保持严格一致。主副本与从副本上 的数据同步修改，更新数据的事务在主副本与各副本或者全部提交，或者全部 失败，具有分布式事务语义。实现严格一致性模型的主要手段有两阶段提交协 议和实时复制“1 。第二种是弱一致性模型，数据的主拷贝存放在预先定义的副 本上，对数据所有的修改都在该主副本上进行。当在主副本上的更新事务提交 以后，异步地传播更新到其它副本，如果某一副本不可用，发往该副本的更新 操作被存储留待以后重新发送。该模型的主要缺点在于，由于数据复制异步地 进行，从副本和主副本的数据必然出现短时的不一致，就可能造成数据丢失。 在弱一致摸型中，事务只在主副本上提交或回滚。 强一致性模型和弱一致性模型之间的最大区别是，使用弱一致性模型时， 从副本和主副本的数据存在不一致的情况。 2 1 3 同步复制和异步复制 同步数据复制h ，是指将本地产生的数据以完全同步的方式复制到异地， 每一本地i o 操作均需等待远程复制的完成才释放0 1 。同步复制，必须保证一 个事务在所有副本上都能完成，如果有一个副本操作失败，那么那些操作成功 的副本将进行回滚，撤销已完成的操作。当采用同步数据复制方式时，源数据 和目标数据互为备份，保持完全一致。源主机在确保数据成功地存储到目的主 i o 四j i i 大学硕士学位论文 机后，才进行新的操作。目的数据可以存储到磁盘，也可以存储到内存，源数 据主机就可以认为已经成功。两种不同的实现方法导致对应用系统的响应时间 的明显不同。 同步复制，要求远端数据与本地数据完全同步，保证高度的完整性和一 致性，必然会影响主机的工作效率，如果数据更新操作很频繁，那么主机的效 率会很低。因此，同步复制对网络延迟有严格的要求，受网络带宽影响较大。 可以用纯软件的方式实现同步复制，也可以用硬件和软件相结合的方法来实 现。在同步复制中，由于数据的丢失仅仅限于当请求提交后还没来得及写到磁 盘上的数据，因此，它能很好地保护数据，适用于那些对于数据一致性要求较 高的商业应用中 异步数据复制。】贝0 是将本地数据以后台同步的方式复制到异地，异步复制 的原理是对源设备的写操作完成后，不必等待目标设备的写操作完成，主机立 即可处理下一个i o 请求。异步复制方式会造成数据短时间的不一致，有时会 有较大的数据不同，容易造成数据丢失，很难达到零数据丢失，因此，关键是 确保数据的一致性采用异步数据复制，响应时间得到了改进，各副本数据的 一致性较难得到保证。维护数据一致性时，很难确定哪些更新己在所有副本上 执行，哪些还没有执行。即使在成熟的商业软件中，一些文件系统和数据库系 统常常能够在失败后恢复数据的一致性，但大大增加恢复的时间，并且不能保 证恢复所有的数据。异步复制虽然提供了一定程度上的数据保护，但是它还是 有很多不足之处。它没有为企业在最大可能的程度上对数据进行保护，不能满 足商业上对数据持续的保护的要求。在复制的过程中也可能会造成数据的不一 致。总的来说，异步方式的数据恢复功能只适用于允许部分数据丢失的应用场 合。 2 1 4 应用陡 数据复制可以对数据进行分发，也可以将源站点的数据合并，最终目的是 使所有的数据副本保持一致。用户可以就近访问需要的信息，甚至在本机获得 需要数据的拷贝，减少了对网络坏境和服务器的依赖，使得系统的可用性大大 加强。总的来说，数据复制和数据一致性技术通常可用于以下场景： ( 1 ) 高可用性要求的场景 数据复制由于具有容错功能，所以能提高应用程序的可用性。如果一个站 1 1 四i i l 大学硕士学位论文 点不可用，用户可以继续查询其它站点的数据，即它提供了出色的故障转移保 护功能。 ( 2 ) 性能和响应度要求较高的场景 数据复制能够实现在本地快速访问共享数据，因为它可在多个站点之间平 衡操作，数据复制可以实现服务器的负载均衡，使用户从访问成本最低的复制 站点访问数据，这些站点通常在地理位置上离用户最近，同时，用户能获得较 高的响应度。 ( 3 ) 无连接计算扭2 1 用户可在断开与中央数据库服务器连接的情况下使用数据库的一个子集。 以后建立连接时，用户可以根据需要对本地子集进行同步( 刷新) 操作。 ( 4 ) 减少网络负载 复制可用于在多个区域位置上分布数据，应用程序可访问各个区域服务 器，而不用访问一个中央服务器。此配置可以极大地减少网络负载。 ( 5 ) 数据共享 共享并不仅仅意味着互通有无，它更大的内涵在于协作，也就是劳动与智 慧的共享。异地用户可以在同一个平台上共同完成一项工作。例如子公司需要 知道总公司的有关数据信息，总公司必须了解子公司的业务情况，总公司和子 公司就可以复制需要共享的数据，在子公司建立数据库副本，使之与总公司的 数据库同步。同时，子公司也可以维护本地数据副本的表，然后合并到总公司 数据库，达到共享数据的目的。 ( 6 ) 数据备份 进行数据复制、备份以及镜像等工作的目标，不只是为了获得一个备份数 据，最主要的目标是在主服务端存储介质发生故障时，利用备份的数据进行恢 复或者把应用程序迁移到备份的数据上重新启动。因此，可恢复性是衡量数据 备份、复制和镜像技术的关键指标，数据一致性是备份数据可恢复性的前提。 2 2a t c 系统和双机双网热备份实现方式 空中交通管制“”，是指国家对其领空和飞行情报区内的航空器飞行活动实 施统一的管理和控制。其基本任务是，制定和颁布空中交通管制法规；划定管 四川大学硕士学位论文 制区域和各种飞行空域；规划航路的通信、导航、雷达设施建没；审批各种飞 行申请，组织实施飞行调配，协调各部门对飞行空间的使用，提供空中交通管 制服务；监督和控制一切飞行活动，组织飞行情况通报；防止航空器之间、航 空器与地面障碍物相撞；防止对空兵器误射航空器；为国土防空部门提供飞行 计划内的情报。空中交通管制的目的就是防止航空器相撞，防止航空器与地面 障碍物相撞，维持空中的交通秩序，提高飞行空间、时间利用率，保证飞行安 全，保证有一个安全、快速、高效的空中交通流量“”。 通过分析和观察空中交通管制的实际运行情况，a t c 系统中的信息处理和 决策具有以下的特点： 第一信息量大、处理时间短、要求快速准确地做出处理。航空器飞行的安 全涉及到气象、导航、地理、交通状况等多方面的限制，a t c 通过对所有相关 信息加工处理来提供准确的信息和指令，从而保障整个系统的安全。任何决策 都要求在一定时间范围内完成，管制过程更是如此管制员从获取信息开始， 需要在很短时间内考虑各种因素，做出管制决策。也就是说信息获取得越早， 管制员考虑时间越充分，所做出的决策就可能越完善。这种“短时性”同时也 要求管制员在作决策时必须果断，不能在不同的决策预案间犹豫不决，错过决 策的最佳时间可能会带来灾难性的后果。 第二决策的动态性和连续性。空中的交通状态、气象条件等信息随着时间 的推移在不断变化，决定了管制决策过程的动态性。整个管制决策过程就是由 一系列的决策组成的，即后一个决策是在前一个决策结果基础上做出的，是前 一个决策的延续、调整或修改。 a t c 系统利用计算机强大的软硬件能力，能很好地解决以上两点，安全高 效地安排大量的飞行，同时避免和减少飞机的相撞与交通的延迟，对冲突做出 检测和预报。为了适应不断增长的空中交通流量的需要，各国都在开发先进的 空管系统软件，升级已有的计算机系统和对话系统和使用全球卫星定位系统 ( g p s ) 帮助空管人员跟踪，联系飞机，同时不断探索设计新的a t c 体系结构， 以进一步提高完善系统的功能，满足新形势下的需要 a t c 是为着空中交通管制功能服务的。其系统结构如图2 1 所示。 四j i l 大学硕士学位论文 图2 1a t c 系统结构 f d p t e l 雷达前端处理服务器：接收雷达、卫星等传输过来的数据，包括气 象信息，报文信息，以及飞机的经纬度位置，飞行高度，飞行速度等特征信息。 r a d p 雷达数据处理服务器：对多雷达数据进行融合，把飞行数据与系统航 迹关联起来，并对飞机航迹进行识别。 f d p 飞行计划处理服务器：包括飞行计划安排和飞行情报的统计检索打印 等功能。 s d d 雷达显示席位：提供给管制员的观察和操作界面，主要负责显示雷达 探测到的空中交通情况。 f d o 飞行计划编辑席位：提供给管制员的飞行计划操作界面，主要实现计 划操作的程序化。 整个空管系统的处理过程为：雷达获取空域内的实际飞行数据，雷达数据 经过前端处理后传给空管软件控制系统，空管软件系统把它与飞行计划数据进 行比较，对本区域的飞行数据进行系统航迹追踪和确认。通过人机接口，空管 人员能监控本区域内的飞行航迹和飞行事务情况，并通过通讯系统与飞行人员 进行交互，对飞行冲突或紧急情况进行控制 1 5 o 由图2 1 可知，a t c 使用的是双冗余结构，具体地说采用的是双机双网热 备份技术。双冗余技术，就其本质而言是集群( c l u s t e r i n g ) 技术臼 的特殊 情况。集群就是网络上两台或者多台服务器( 通常称为节点) 协同工作的一个 1 4 四川大学硕士学位论文 群组，它们对外表现为一台虚拟服务器，共同提供服务口”。也就是说，当一 个节点出现故障时，群组中的其他正常服务器就会接管其任务，继续服务，用 户很少或者不会注意到群组中的服务器出现故障，整个群组对用户而言可以认 为是透明的，用户只能看到一台虚拟服务器，不知道后台的集群，不知道故障 的产生集群技术的目的是减少服务器的停机时间，使用户的重要应用尽可能 少经受这种故障带来的损失。 该技术的优点在于，它保证了当服务器的硬件或者软件出现故障时，服务 器能够自动从故障中恢复过来，从而保证了服务器连续提供服务的时间。这是 一种对连续工作时间系统的保障，是a t c 系统的设计目标之一。另外一个优 点是改善系统的可扩展性，改善向集群增加新节点的能力，同时最大限度的减 少系统崩溃的概率。可扩展性和稳定性，也是a t c 系统的设计目标。 从图2 1 可看出，a t c 系统采用了双机双网技术，通过双机双网方案保证 系统能够可靠，稳定的工作，能够连续不断的提供空中交通管制服务，保障飞 行安全。整套系统在平时处于正常工作模式，一旦其中一台服务器出现问题， 系统能够自动进行主从网络和服务器的切换。对于服务器，采用了双机热备方 案1 i s | a 双机热备技术“”“钔就目前而言是三种双主机集群技术“町中最为成熟 的一种，它的开发成本较低，而且有丰富的应用案例可以借鉴。 2 3a t o 中数据复制模块的目标 通过对a t c 的特点和a t c 系统的双冗余实现方式的介绍可知，a t c 系统的 双机双网热备份，实质是在两个节点间采用弱一致策略进行数据复制，两个节 点之间通过心跳策略“钉“们维护他们的主从关系和检测彼此的存在，双网能够 减小网络故障的影响a t c 系统中的这种实现方式，具有一定的容错能力，提 高了系统的可靠性和可用性，对用户具有透明性。由于该方案限定了只能使用 双机，所以它不支持节点的扩展。不支持动态改变节点数。有限的节点数也使 它的容错能力受到限制。使用弱一致策略，两节点间可能存在数据不一致，可 能造成数据丢失，那么就没能最大限度地保护数据。在实际的测试过程中，出 现过丢失数据的情况，尽管这种现象只在特定情况下发生，但对于a t c 这样对 数据一致性有着严格要求的系统，这是不允许的。 通过上述分析，a t c 系统中数据复制模块应该具有下述特点：强一致，容 四川大学硕士学位论文 错能力和高可用性，良好的扩展能力，对客户的透明性，为了提高性能和对客 户的响应时间，希望能在数据复制模块中引入c a c h e 机制。 2 3 1 容错和高可用性 服务器的可用性分为多个等级。最基本的要求就是可靠性要求，而最高级 别则是具有容错能力，即在一个服务器节点故障的情况下服务器连续提供服务 的能力。服务器可用性的等级。”划分可以参见图2 2 。 图2 2 可用性等级划分 一般来说下面三层的可用性容易通过选择高品质的硬件设备，适当增加硬 件冗余来实现。而且现在的硬件供应商以及操作系统供应商一般都会提供集群 方案。 a t c 系统服务的高可用性是数据复制算法设计时应重点考虑的问题，系统 中某个或某几个节点出现故障、或是网络出现故障时都会影响服务的可用性。 要达到容错的目的，必须解决下述问题：如何在正常服务过程中保证多个副本 之间数据的一致；当单个副本出现故障或从网络中断开或有新的副本加入时， 如何进行动态侦测和协调而不影响系统整体的可用性。 2 3 2 透明性 用户通过接口使用数据复制模块提供的服务，这个接口必须是简单易理解 的。实现透明性的好处有两个：一是便于用户学习和使用；二是便于客户根据 1 6 硼川i 大学硕士学位论文 自己定义的数据格式和存取方式定制自己的应用。具体地，a t c 系统中数据复 制模块的透明性包括以下内容： ( 1 ) 存取透明性 在系统中，客户程序不需要知道副本的位置和数量等信息就可以使用数据 复制服务，也不知道每一次存取操作的具体执行情况，客户只知道若一次存取 操作返回成功，表示服务端己完整地执行了相应操作。副本之间的数据复制和 一致性维护对用户始终是透明的。 ( 2 ) 并发存取透明性 一个用户对数据所做的修改并不与同时存取该数据的另一用户发生冲突。 在应用程序中，要求对共享数据的存取进行并发控制，在具体实现上代价十分 高昂，并发透明性需要解决的就是共享数据的读写一致性问题。 ( 3 ) 故障透明性 系统中某一个或几个节点出现故障后不会影响用户正常使用，系统会自动 调整继续为用户提供服务，故障节点恢复后再加入系统继续提供服务。 2 3 3 稳定性 稳定性“”。”是指算法本身必须保证在探测故障后，能够对故障做出快速 的处理，并且能够快速地恢复到稳定的服务状态，即算法在最大限度地保护数 据的情况下，当系统遭遇故障时，能够自动处理故障再次进入稳定的服务状态。 2 3 4 扩展能力 a t c 中数据复制模块的扩展能力是：系统规模能够线性改变，即可以动态 增加和减少系统中的副本数量，而且在这种系统扩展过程中，不会对系统服务 产生影响；实现的时候提供高层的抽象接口，便于用户对数据格式，数据存取 方式等进行定制，实现应用层的高扩展能力。实现空管系统中的数据复制模块 的扩展能力，不仅要在设计上下功夫，在实现的时候，也要考虑采用便于扩展 的技术。这里的扩展能力还包括，设计出的数据复制模块，不仅能用于a t c 中，还能较容易扩展应用到类似的环境中。 2 3 5c a c h e 管理 在一个各自拥有主存和磁盘的客户一服务器系统中，有四个地方可用 四川大学硕士学位论文 来存储数据：服务器磁盘、服务器主存、客户磁盘和客户主存，访问磁盘和 主存的速度有着极大的差别，在一个有实时性要求的环境中，这也是必须要 考虑的一个因素，通常采用不同层次的缓存机制来处理。 在a t c 系统中，由于会频繁地通过网络获取数据，频繁地将数据写入本地 磁盘，鉴于此类i o 操作的低效耗时，为了保证系统性能和高响应度，数据复 制模块必须使用缓存机制。在这种情况下，需要重点设计的是客户端缓存和缓 存一致性保持机制。 2 4 本章小结 本章先介绍a t c 系统的任务和特点，再介绍和分析了a t c 系统的双机热备 份实现方式，在此基础上引出了数据复制模块在a t c 中的设计目标。a t c 中的 数据复制模块，应具有以下特点：高可用性并且具有容错能力；对客户具有透 明性，在所有的客户并发访问看来只有一个副本；实现模块的算法本身必须具 有收敛性，在侦测出错误后，能尽快地完成处理进入稳定服务态；较好的扩展 能力，系统本身可扩展，客户的扩展，如客户定义的数据格式、读写方式等； 具有高效的缓存管理机制。 四川大学硕士学位论文 第三章a i o 中数据复制模块的设计 3 1a t o 中数据复制模块的运行环境和应用模型 在讨论数据复制模块的原理和设计之前，先明确模块运行的环境。我们 期望数据复制模块运行在支持t c p i p 的网络环境，其中的节点机器可以是任 意平台，从w i n d o w s 到u n i x 和l i n u x ，不要求节点机器支持原子广播“1 等额 外的功能，但要求网络有足够的带宽。我们实验室和寝室里面的局域网都满足 上述条件。 我们期望在局域网环境下，实现一个分布式数据复制模块，来保证副本 的数据一致。由于多个副本数据一致，可以从这些可交换的副本中构建相同的 服务，这就能保证一个系统服务的高可用性。图3 1 是数据复制模块的应用模 型图。 图3 i 数据复制模块的应用模型图 根据图3 1 ，可把整个服务器部分视为一个整体，即一个黑盒，系统的 1 9 四川大学硕士学位论文 输入是客户请求和副本集中每个副本的状态，运行态或停止态，系统的输出就 是对客户请求的响应。客户请求或者得到系统的响应，或者永久地阻塞。系统 的响应包括正确的响应和抛出明确的异常。正常情况下，系统会在有限的时间 内对客户请求做出响应 3 2 数据复制模块的设计 根据第二章中a t c 系统中数据复制模块的目标，本文设计的数据复制模块 结构如图3 1 ，它向外提供一致性读写的服务，客户通过代理( c l e r k ) 访问 系统提供的服务，对每一个客户应用程序来说，都只有一个数据副本，称为 o n e - c o p y s e r i a l i z a b i l i t y 。 本文的数据复制算法基于主机选举“”“8 ”1 ：整个系统或者有且仅有一个主 副本，或者正在选出一个主副本，算法按照主从模式来管理这些副本机器。 系统只处于两种状态，或者服务态，或者选举态。在进行服务态之前，系统都 进行主机选举，即从副本集中选出一个主副本副本集可以动态改变，改变的 方式是由客户向主副本提交一个删除请求，但每次只能删除一个副本。副本集 中每个副本的状态由一系列时标值表示，时标值显示了哪个副本的数据是最新 的，哪个副本能够被选为主副本。 对数据复制算法进行扩展，在客户端引入缓存机制，在客户端的代理缓 存了客户程序最近读和写的数据。代理采用延迟回写策略来管理它的缓存：写 操作修改的数据不是马上通过c a c h e 写入主机，而是先写入c a c h e ，使c a c h e 条目变脏，然后再传给主机，使c a c h e 条目变干净。客户应用程序通过代理来 完成与服务器的通信细节，代理还负责管理客户机器的缓存。 在对文献 1 7 1 8 2 0 中的算法进行学习和分析基础之上，本文做了改 进，使之满足a t c 对数据复制的需求。为了简化和保证系统的高响应度，在文 献 1 7 选举算法的上，将系统分为两阶段，服务态和选举态，进入服务态，系 统就能处理客户的数据读写请求。为了更好地实现选举，在每个副本中引入一 个变量，用于记录本次服务阶段的数据修改次数，这更有助于选举出最优的主 副本和进入服务态后副本间的数据协调。选举成功之初，各从副本与主副本之 间的数据协调，采用p u l l 模式o ”；服务态，新的更新请求到来时，数据的一 致性通过p u s h 模式。町实现。本文利用t c p i p 在主从之间交换报文实现分布 四川大学硕士学位论文 式事务控制。r t c 系统的容错和可扩展需求，都要求数据复制模块支持动态 增加和删除副本，文中将增加和删除副本的操作视为一般的数据更新操作，采 用类似的处理策略。出于性能的考虑，文中在副本端和客户端部使用缓存机制， 副本端使用缓存机制，有助于减少读写磁盘的消耗，客户端使用缓存进一步提 高系统的性能。文中把客户端的缓存机制和与数据复制通信细节都放到客户代 理中。 为了描述方便，我们先假设副本集是不变的，并且所有的副本和客户代 理事先都知道这个副本集。在后面引入客户代理的时候，详细描述副本集的动 态改变问题，客户代理如何获取主副本信息的问题，以及在客户端引入缓存机 制的问题。 3 2 1 数据复制模块中的状态设计 在任何时刻，运行中的数据复制模块只处于服务态或者选举态，其状态 转换见图3 2 。系统处于服务态，接受和处理客户端的读写请求，并给出响应。 数据复制算法基于主副本选举，因为在服务状态，客户端的写请求发给主副本， 主副本成功写入本地和所有活动副本之后，才向客户端返回写成功。当系统中 副本崩溃，或有新副本加入，或由于网络原因导致服务中断，系统从服务态转 为选举态。在选举态，所有的副本都运行一个选举算法，直到他们协调选举产 生一个新的主副本，系统再进入服务态。 在系统的选举态，其中一个副本会被选举出来成为唯一的主副本 ( m a s t e r ) ，在选举过程中，与之联系，对该主副本的身份进行确认的所有其 他副本称为该主副本的从副本( s l a v e s ) ，所有的这些副本，包括主副本和所 有的从副本一起构成服务态的活动副本集( a c t i v e s ) 。 系统整体的状态是所有的副本状态一起决定的，不是由单个副本的状态 决定的。图3 3 示意系统中一个副本可能存在的状态和状态之间的转换。下面 对副本的状态依次进行介绍。 四川大学硕士学位论文 图3 2 数据复制模块状态图 图3 3 数据复制模块中副本的状态图 未定态。副本处于未定态，表明它不从属于别的副本。它不断地执行选 举算法，直到判断出自己是最佳候选主副本就进入候选主态，或者接收到别的 副本发来的“i a m m a t e r ”消息而进入从态，才停止选举算法。 从态。副本处于从态，表明它已经同意作为另一个副本的从副本。副本 进入从态后，它跟主副本的主从关系将维持一个指定的时间，在这个指定的时 间里，如果主副本没有向它发消息进行刷新，该从副本由从态转到未定态执行 选举算法。 候选主态。进入该状态的副本不停地收集从副本，如果收集到满足给定 条件的从副本，就引导系统进入服务态：否则它转入未定态执行选举算法。 四j i i 大学硕士学位论文 服务主态。处于该状态的副本，已经可以接收和处理客户的请求了。在 对外提供服务过程中，如果出现任何失败，它就进入未定态执行选举算法。 如果有副本处于服务主态，那么系统的状态为服务态；否则系统处于选 举态。系统一进入服务态，即有副本从候选主态转换到服务主态，系统已经可 以对外提供服务了，但同时，系统还必须快速协调副本间数据，这样极大地提 高了系统的响应时间。 3 2 2 数据一致性设计 数据一致性分两种模型。1 ：一是弱一致，一是强一致。弱一致模型的数据 复制算法“是，数据副本分为主从关系，主副本的选定是按照某个预定的策略， 主副本的功能较弱，它只周期性地在所有副本上进行一致性检查，当数据不一 致时，以较新的副本上的数据为准协调一致。当主副本出错时，根据优先级确 定一个新的主副本；只要主副本存在，就能保证一致性。对每条记录，系统维 护两个字段，用于标识记录版本号( 每次修改加1 ) 和该记录最近的更新者。 客户向系统发出数据更新请求时，获取本地副本上该记录的互斥访问权限，执 行更新操作，释放该互斥访问权限，随后该副本用u d p 向其余副本广播刚才更 新的数据，其余副本接收后分别进行本地更新。这个算法实现策略非常简单， 它的最大的问题，是如何检测和消除更新数据时存在的冲突? 可以按照预先定 义的策略解决数据更新冲突。 而强一致模型的数据复制算法“”，是一个基于主副本选举的数据复制强一 致性算法。一个副本必须得到大多数副本( 包括自己) 的同意，才能成为主副 本。在一个副本宕掉或有新的副本连进来时，都要进行主副本的选择。每次选 定主副本之后，接着是恢复状态，确保从机的副本数据与主机副本数据的当前 值一致。恢复状态后，才能对客户提供读写服务：主副本实现分布式事务时用 到远程过程调用r p c 。 本文的数据复制模块中，有两个地方需要协调副本间数据，根据具体情 况的不同，分别采用不同的方式第一种情况是，选举成功之初，从副本与主 副本之间的数据协调，采用p u l l 模式啪1 ，即从副本向主副本请求数据；第二 种情况是，在服务态，新的更新请求到来时，数据的一致性通过p u s h 模式。耵 实现，主副本主动将数据写入所有的活动从副本。 四川大学硕士学位论文 3 2 2 1 选举成功时副本间数据的一致 选举成功后，主副本就进入服务态，一方面它可以开始接收客户的数据 读写请求，另一方面它引导所有从副本执行两个的任务，一是更新各自的状态 变量，这样过期的副本和不活动的副本在下次选举时就能准确地知道他们已经 过期；二是协调数据使所有活动副本的数据，使与主副本的数据都相同，都是 最新的。 由于选举成功后，活动副本中可能有的副本跟主副本的数据一致；也可 能有的副本跟主副本的数据相差很多，例如当一个副本由于故障停止一段时间 后，再次连入系统，那么选举成功后，它没有在停止时间内更新的数据。在这 种情况下，从副本就通知主副本自己当前的数据情况，由主副本把相应的数据 发给从副本，使他们的数据达到一致。从副本数据得到更新后，相应的状态变 量也随着更新。图3 4 描述了从副本协调数据的过程。 从副本根据所获得的主副本的快照信息，判断自己数据是否过期，若没 有过期修改数据时标，若过期，向主副本请求数据进行更新，再修改自己的数 据时标。 图3 4 选举成功时从副本与主副本协调数据 3 2 2 2 服务态执行更新请求时数据的一致 在服务阶段，客户代理把它不能通过缓存处理的所有的读写请求都传递 给主副本主副本处理读请求时，直接从自己本地的硬盘中读取指定的数据， 然后把数据返回给请求的代理。当主副本接收到写数据请求时，它为这次请求 指定一个顺序号，然后并发地把该请求发给所有的活动副本( 包括主副本自 身) ，这些活动副本在本地硬盘上完成写操作后才向主副本给出响应，主副本 收到所有活动副本的响应后才向客户代理给出响应。图3 5 从主副本的角度描 占 四川大学硕七学位论文 述了这一过程。 图3 5 服务态一次更新操作的过程( 主副本视角) 为了提高系统在服务阶段的性能，主副本向从副本传递写请求时没有使 用分布式事务提交协议，它只是简单地向每个从副本发出远程过程调用( r p c ) ， 然后等待他们返回。我们说一次写操作提交成功，就是指数据被正确地写到当 前主副本和它所有从副本的硬盘中。为了提高性能，在系统服务阶段主副本和 从副本都用多个线程来接收和处理读写请求。但是当一个副本在处理写请求过 程中突然死掉时，系统就会进入选举阶段，