（通信与信息系统专业论文）hlr数据库系统设计及数据一致研究.pdf

华中科技大学硕士学位沦文 摘要 j 、f ( h l r 作为移动通信系统的中心数据库，除需具备传统数据库的a c i d ( 原子眭， 一致性，独立性，持久性) 外，还要满足严格的实时要求和用户扩容的要求。本文 的应用研究是基于通用分组无线业务( g p r s ) 的移动通信网的h l r 系统的研制而 进行的。基本要求是不仅功能上支持g p r s 业务，还要具备1 0 0 万户以上事务承载 能力。彳 本文对支持大容量和实时要求的实时双数据库的模式设计做了深入的研究，分 析了作为“h o tc a c h e ”的内存数据库的数据组织和并发控制特点，并重点讨论了系统 数据一致问题，提出非串行化事务调度策略，针对事务对数据一致的依赖程度提出 不同的调度方法以进一步提高事务的处理效率。 在r t d d b 于g r p s h l r 的具体应用中，采用自行研制的内存数据库承载全部 实时事务逻辑，结合内存数据库的用户数据组织方式讨论了2 p l 的设置“粒度”，冲 突检测等问题，并对事务分载产生的数据一致问题进行重点分析，提出具体的调度 i 策略并用多线索控制，定时定量更新和消息队列等机制加以实现。 随着第三代移动通信系统的出现，h l r 在业务和数据提供方式上也发生厂巨大 变化，作者在课题参与过程中，对h l r 的演进版h s s 的实现做了一些探索性研究， 提出多数据库的构建方式，对事务特点和数据一致问题进行了探讨，提出了基于 m o m 的数据更新策略，希望对未来同行的研究有所助义。 【最后，作者总结了g p r s h l r 的系统测试和数据一致部分自测试过程和方法， 对数据一致的性能和对系统的影响作出评价。 、， y 关键词：h l rh s s内存数据库多数据库系统数据_ l 致并发控制中间件 华中科技大学硕士学位论文 a b s t r a c t a st h ec o r ed a t a b a s eo fm o b i l et e l e c o m m u n i c a t i o ns y s t e m , h l ri sr e q u e s t e dn o tf o r a c i d ( a t o m i c i t y ，c o n s i s t e n c y ，i s o l a t i o n ，d u r a b i l i t y ) ，b u t a l s oh a r dr e a l t i m ea n d e v e r - t a n k i n gc a p a c i t y t h ea p p l i c a t i o nr e s e a r c ho ft h i s t h e s i si sb a s e do nd e s i g na n d r e a l i z a t i o no fh l rs y s t e mt h a t s u p p o r t s t h e g e n e r a lp a c k e t r a d i o s e r v i c e ( g p r s ) a c c o r d i n gt ot h er e q u i r e m e n to fm o t o r o l ai n c ，t h eh l rs y s t e ms h o u l dn o to n l ys u p p o r t g p r sb t t ta l s oh a v eat r a n s a c t i o n p r o c e s s i n gc a p a c i t yo f o n em i l l i o ns u b s c r i b e r s d e e pr e s e a r c hh a sb e e nd o n ei n t h et h e s i so nt h ea s p e c to fs t r u c t u r e d e s i g n o f r e a l - t i m ed o u b l ed a m b a s es y s t e ms u p p o r t i n gr e a l - t i m et a s kh a n d l i n ga n dh i g hc a p a c i t y d a t aa r r a n g e m e n ta n d c o n c u r r e n c yc o n t r o lo fm m d b w h i c hi sw o r k e da s h o t - c a c h e h a s b e e nd i s c u s s e d b u td a t ac o n s i s t e n c yi st h eh i g hl i g h tp r o b l e md i s c u s s e di nt h et h e s i s o n t h i s p r o b l e m ，a u t h o rp r o v i d e s w i t hn o n s e r i a l i z e dt a s k s c h e d u l i n ga n dg i v e d i f f e r e n t s t r a t e g i e sr e g a r d i n g d i f f e r e n t r e l a t i o n s h i pb e t w e e n t a s ka n dd a t a c o n s i s t e n c y v q h e l lr t d d bi su s e di ng p r s h l r ，m m d bi st h ec a i t y i n ge n v i r o n m e n tf o ra l l r e a l t i m et a s k s s od a t a a r r a n g e m e n ta n dc o n c u r r e n c yc o n t r o l i s v e r yi m p o r t a n t i n s m o o t h l yr e s o l v i n ga l l d e a dl i n et a s k s t h et h e s i sd i s c u s s e sl o c kg r a n u l ea n dc o n f l i c t d e t e c t i o no f t w o - p h r a s e l o c km e t h o d ，a n de m p h a s i z e so nd a t ac o n s i s t e n c yc a u s e db yt a s k d i s t r i b u t i o n t h e nr e a l i s t i cm e t h o d s ，s u c ha sm u l t i t h r e a dc o n t r o l ，p o i n t e d t i m e q u a n t i t y a n dm e s s a g eo r i e n t e dq u e u e ，a l ep r o m o t e d w i t ht h e d e v e l o p m e n t o f t h i r d g e n e r a t i o nm o b i l es y s t e m ，h l r i sb e c o m i n gd i f f e r e n ti n d a t aa n da p p l i c a t i o np r o v i s i o n a ne x p l o r i n gr e s e a r c hh a sb e e ni m p l e m e n t e do nh s s ( h o m es u b s c r i b e rs e r v e r ) w h i c hi st h es t e p u pv o l u m eo fh l r , a n d m u l t i p l ed a t a b a s e s t r u c t u r ei s p r o m o t e d d a t ac o n s i s t e n c yh a sn e wf o r mi nt h i ss t r u c t u r ea n dd a t au p d a t e t h r o u g hm e s s a g eo r i e n t e dm i d d l e w a r eh a sb e e nd i s c u s s e d ，h o p i n gt h a tw i l lh e l r l f u l t o c o u n t e r p a r t si nf u t u r e r e s e a r c h k e y w o r d h o m el o c a t i o nr e g i s t r a t i o nh o m es u b s c r i b e rs e r v e rm a i nm e m o r yd a t a b a s e m u l t i p l e d a t a b a s e s y s t e m d a t a c o n s i s t e n c yc o n c u f r e n c y c o u t r o l m i d d l e w a r e i l 华中科技大学硕士学位论文 ! = ! 竺! ! ! = = = = = = = ! ! ! ! = = ! = ! ! ! ! ! = = = = = = ! ! = ! ! ! ! = ! ! = ! ! ! 1 1 绪论 本章介绍了移动通信技术在国内外的发展现状，数据库技术的发展方向和实时 数据库的特点以及主要研究内容，然后说明了课题的研究背景，来源，意义和目标， 最后介绍本文的章节安排。 1 1 移动通信的发展和国内现状 在过去的几十年中，由模拟蜂窝移动通信系统开始，到数字蜂窝移动通信系统， 再到个人通信概念的提出，世界移动通信状况发生了巨大的变化。 移动通信的发展目前主要经历了四个发展阶段：一是模拟蜂窝移动通信系统， 如美国的a m p s 、英国的t a c s 、北欧四国的n m t 一5 0 等；二是数字蜂窝移动通信系 统，如g s m 、p a m p s 、j d c 、i s 一4 1 等；三是第三代移动通信系统，如w c d m a ， c d m a 2 0 0 0 ，t d s - - c d m a 等，其中t d s - - c d m a 是由中国大唐公司提出而被i t u t 采纳的首个中国人自己的规范。 模拟蜂窝移动电话经过十五年的发展渐显其缺陷：一是各系统间没有公共接口； 二是无法与固定网迅速的数字化发展相适应，数据承载业务难以展开：三是频谱利 用率低，无法适应大容量的要求：四是安全保密性差。这些致命弱点妨碍了其进一 步发展。 针对模拟蜂窝的缺点，迎来了移动通信的第二次革命，其标志是全球化、数字 化和个人化。目前，数字蜂窝移动通信系统主要存在两种制式：一是采用t d m a 技 术的g s m 系统；另一种是采用c d m a 技术的i s ，4 l 系统，其频谱利用率是模拟系统 的2 0 倍，且系统成本远小于g s m ，但因组网技术复杂尚欠成熟，故进入世界市场 较晚，只能让g s m 系统捷足先登。 近些年来，随着无线通信宽带化技术的突破，移动通信正在向以c d m a 为基础， 以宽带化通信为特征的第三代移动通信系统发展。推动3 g 发展的好处在于：1 ) 第 三代移动通信系统的频谱资源至少在2 3 0 m h z 以上，且频谱利用率较高，覆盖范围 。懑蘧崩；蕊蕊，；罐。， 华中科技大学硕士学位论文 更广，性能更好，从而可以很好地解决现有业务的开展问题；2 ) 第三代系统可以针 对不同的业务应用，提供从9 6 k b i t s 直至2 m b i t s 的接入速率，从而很好地满足 人们对移动数据业务诸如i n t e r n e t 、电子商务、高速数据、活动视像和v o d 等数据 多媒体业务的需求；3 ) 全球一体化的进程迫切需要一个全球统一的移动通信设备， 以实现全球漫游的需要。 g p r s 是迎合g s m 移动通信市场和全球因特网的迅猛发展和日益融合而推出 的，它为g s m 运营商由仅提供话音业务向提供综合信息服务业务领域拓展提供了重 要的网络平台，并为g s m 向第三代移动通信的过渡打下基础，被喻为t 未来3 g 市 场的助推器”。它有如下特点：1 ) 从无线部分到有线部分提供端到端的分组数据传 输，无线部分可按需动态分配话音和分组信道，更为有效地利用频率资源；2 ) 向用 户提供更高的接入速率 1 1 5 k b i t s 和更短的接人时间；3 ) 可更为有效地提供短消 息、w a p 等原有数据业务；4 ) 底层基于t c p i p 协议，可与因特网进行无缝连接； 5 ) 可提供按时间、流量、内容等更加灵活的计费方式；6 ) 依靠g s m 的广阔覆盖， 可提供随时随地的数据接入；7 ) 对原有g s m 设备无需进行大的改动。专家普遍认 为，g p r s 是g s m 向第三代系统过渡，同时又兼顾现有第二代系统的2 5 g 系统。在 g p r s 后，如果g s m 运营商没有第三代的频谱，则可以通过e d g e 技术把速率提到 3 8 4 k b i t 8 ，接近第三代移动通信系统的水平。如果运营商拥有第三代的频谱，则可 以从g p r s 直接过渡到第三代。 总之，移动通信话音市场经过多年的发展，业已进入成熟期。数据业务特别是 移动互联网业务将在推动未来移动通信的发展中起着越来越重要的作用。据估计， 目前移动数据业务量占整个移动业务量的比例在日本已经达到1 5 ，欧洲是5 1 0 ， 3 4 年后，这个数字会超过5 0 。尽管移动互联网诸业务的发展和前景尚存在许多 不确定性和面临着许多困惑，但未来将会成为移动通信业务的一个重要支柱是可以 肯定的。据分析，在未来的1 0 年里，移动互联网产业将随通信与网络技术的发展而 高速发展，移动上网终端将超过有线上网。 移动通信网的发展趋于高速率、大容量、复杂化、通用性，并伴随着与互联网 2 溉；凌 ， ；， 华中科技大学硕士学位沧文 和电视网的融合。这种趋势要求网络结构上往往是暑次式，分布式的。作为移动通 信网的中央数据库系统h l r 必须适应这一需求，采用现代数据库中的实时技术、主 动技术以及分布技术融合结构化的多层模型提供更好的服务。 1 2 数据库技术的发展 数据库技术的发展经历了三个阶段。第一阶段，1 96 9 年m m 公司研制了基于层 次模型数据库管理系统( i m s ) ，并作为商品化软件投入市场，该系统至今还有其特 定用户，技术还在继续发展。第二阶段从6 0 年代到7 0 年代初，美国数据库系统语 言协会t c o d a s y l ) 下属的数据库任务组d b t g ) 对数据库的方案和技术进行了 系统研究，提出了d b t g 报告。该报告提出了数据库系统的许多基本概念、方法和 技术，成为网状数据模型的典型代表，奠定了数据库发展的基础。d b t g 的存取效率 较高，系统研制较容易，但数据独立性差，用户使用不方便。目前一些实时性要求 较高的专用系统仍采用网状模型。第三阶段，1 9 7 0 年i b m 公司的ef c o d d 发表了摹 于关系模型数据库技术的论文“大型共享数据库数据的关系模型”，获得1 9 8 1 年a c m 图灵奖。 随着数据库技术和计算机软硬件水平的提高，近年来又出现厂许多新的数据库 技术，如文时数据j 牟、主动数据库、内存数据库、分布数据库、面向对象数据库、 多介质数据库及专家数据库等。 1 3 实时数据库 实时数据库系统( r t d b s ) 是业务和数据都有定时特件或显式时间限制的数据 席系统 2 1 系统的正确阽不仅依赖逻辑结果，还依赖逻辑结果产乍的时间：r t d b s 足数据库和丈时系统的结合，它集成阿者的雠念和要求，同时处理定时性和一致性。 此文时数据库系统的对并发控制和数据一致的要求不| 一j 十传统的数据库系统，需 服从一定的时问性，目前对这些问题已经有了广泛而深入的研究 随着半导体仔储器的降价和存储密度的提高，以内存为主要存储介质的数据库 华中科技大学硕士学位论文 系统的发展成为可能。内存数据库系统( m m d b s ) 是将数据存于主存以提供高速存 储的数据库系统6 1 。不同于传统的磁盘数据库系统，m m d b s 有自己独特的数据组 织和存取方式，可靠性管理，数据恢复等措施，以存储的易失性换取高效率，因此 通常m m d b s 有一份数据拷贝存于磁盘这种可靠介质中。m m d b s 的硬件特点决定 了它本身的实时特性，m m d b 属于实时数据库范畴。 内存实时数据库系统( r t m m d b s ) 就是硬件和软件优势的互补结合，将实时数 据库的并发理论与内存数据库的高速存储介质和数据组织结合起来可以进一步提供 更高效的实时性，以满足电信等服务行业对服务质量的严格要求，与本文研究与应 用相关的实时数据库系统是g p r s h l r 系统就具有这样的特征。在r t m m d b s 的研 究中最具挑战意义、最影响系统性能的是能够有效反映事务实时响应优先级的并发 控制策略和事务调度策略。传统的d b m s 的并发算法往往采用消极冲突检测机制和 时间驱动在设计上不相容，从而造成时间响应低优先级事务由于先发生而锁住高优 先级事务，导致其悬挂等待，无法响应。针对事务特点进行的主动调度将有效解决 此问题，因此如何改进并发控制方法和选择调度策略以维护传统数据库数据一致和 提高事务实时性是影响实时系统性能的重要问题。 1 4 本文研究背景，内容及意义 华中理工大学金鹏华中通信研究所于一九九七年十二月承担了金鹏j p m 一1g s m 移动通信系统的h l r 的研制工作，一九九八年十一月，该h l r 系统配合金鹏移动 ， ： 交换机在河北省邯郸市开通实验局，并通过信息产业部组织的入网测试和专家方案 ； ； 评审，于一九九九年三月获得入网许可证。 随着我国移动通信和互联网业务的飞速发展，移动互联网成为新的市场热点。 ； 广州金鹏集团为适应这一市场变化趋势，与移动通讯的著名企业m o t o r o l a 公司签署 了产品合作协议，共同开发g s m 基础上具有较高速率数据接人的g p r s 系统，金鹏 负责其中g p r s h l r 子系统的产品开发任务：经过公司领导的慎重考虑，决定由华 中金鹏研究所继续承担这一任务，与m o t o r o l a 公司密切合作，达到协议规定的目标。 j f 4 鞠蠢懿氮箍纛磊躺、；进巍：。， 1 l !华中科技大学硕士学位论文 本文的实践与应用部分是该项目的一个重要组成部分，主要包括g p r s h l r 系 统中并发控制和数据一致的方案研究、设计与编程实现。 g p r s h l r 子系统将r t m m d b s 理论成功的用于实践，将商用数据库和自行开 发的内存数据库在应用级结合，提出了双数据库模型，并对事务调度，并发控制和 数据一致等主要问题进行了分析和解决，对实时数据库，内存数据库和关系数据库 领域的设计开发人员提供了参考借鉴。另外，本文还对针对第三代移动通信系统中 的核心数据库- s s 的新特点和发展方向提出解决多数据库系统的探索性方案，并分 析了其事务特点和对数据一致问题提出解决建议。 j 年中彳斗一j 支，失学石页士学t 支i 譬文 2 实时双数据库模式设计 本章将在介绍大型商用数据库及实时内存数据库特征的基础上，提出r t d d b 数 据库构建模式，以商用数据库为基石，以m m d b 做前者的主拷贝即“工作版本”n 1 ， 用以解决数据容量和实时性能之间的矛盾，并分析了常用并发控制方法和数据一致 模型特点，提出事务调度策略。 2 1 商用数据库的特点及应用要求 我们通常所说的商用数据库指的是当前流行于软件市场的大型通用数据库管理 系统，如o r a c l e ，s y b a s e ，i m bd b 2 i n f o r m i x 等。商用数据库管理系统( 常简称 商用数据库系统或商用数据库) 是管理数据库的核心软件，是数据处理技术中各种 先进思想的汇集，是一种综合的通用的大型系统软件”。它最基本的功能就是允许 用户逻辑地、抽象地处理数据而不必过问这些数据在计算机中是如何存放、如何处 理的细节，并全面负责数据的存储、安全性、独立性、完整性、一致性、并发操作、 恢复和访问，等等，实现透明。因此，其基本目标就是要提供一个可以让人们方便 高效地存取信息的环境。商用数据库管理系统从初级到高级，其功能越来越强，技 术和理论也越来越完善。而根本的发展是数据独立性越来越高，用户接1 2 1 趋向于简 明、方便、直观，非过程化，智能化。从以前的层次模型、网状模型发展到现在的 关系模型，商用数据库系统的结构越来越复杂，规模越来越庞大，功能愈来愈强大。 商用数据库系统的主要特点是强调其通用性，它并不是为某种应用专门研制的。当 今比较流行的商用数据库系统均采用关系数据模型，因此属于关系数据库系统。另 外，为提高系统容量和町靠性，商用数据库一般采用磁盘作为永久存储介质，也叮 称为磁盘数据库系统d r d b s 。 商用数据库系统以事务做为工作的基本单位，是原子的。商用数据库系统要保 证事务对数据库的一致性约束，即如果事务启动时数据库是一致的，那么当这个事 6 华中制技大学硕士学位论炙 务成功完成时数据库也应该是一致的。商用数据库系统将数据的绝对一致正确性作 为系统最高、唯一的正确性标准，因此在数据库的安全保障、数据的完整性维护、 事务处理的并发控制以及数据库的故障恢复等方面做了大量的工作1 1 9 1 。这就导致商 用数据库系统对一个事务的处理过程十分繁琐复杂，特别是对那些并发的修改类事 务，并不象文件系统中那样只是进行简单的数据修改，整个过程涉及对操作语法的 检查、用户操作权限的检查、内存空间占用情况的分析、回滚缓冲区的数据修改、 用户记录的加锁控制以及日志文件中的事务记录等多项操作。这种繁琐操作过程保 证了整个事务处理的安全性、正确性和一致性，但这是以忽略对时间性的考虑为代 价换来的。因此，商用数据库系统对数据是进行不可预报的存取，没有“时间维”， 更不会显式地考虑定时性。 2 2 内存数据库m m d b 首先，m m d b 是个内存数据库，判断一个数据库是否为内存数据库有很多不同 的说法，比较公认的一个判断标准是看数据库的主拷贝或“工作版本”是否常驻内 存。据此，我们给出如下定义”： 定义：没有数据库d b ，d b m ( t ) 是t 时刻d b 在内存中的数据集，d b m ( t ) c d b ； t s 为所有事务的集合，a t ( t ) 是t 时刻的活动事务集，a t ( t ) c t s ；v t a t ( t ) ，d t ( t ) 为t 在t 时刻的操作数据集，d t ( t ) d b ；若在任一时刻t ，均有：v t a t ( t ) ， d t ( t ) 亡d b m ( t ) 成立，则称d b 为一个内存数据库，简记为m m d b 。 根据这个定义，m m d b 的“工作版本”( 可能是整个数据库) 是常驻内存的任 何一个事务在执行过程中没有内外存间的数据i o 。这样做的好处在于直接在内存中 访问数据使得内存数据库的响应时间和事务吞吐率远远优于基于磁盘进行的存取的 磁盘数据库，而这一点对于实时性要求较高的系统是十分重要的r 6 1 。 m m d b 与d r d b 的主要区别如f ：( 1 ) 内存存取速率比磁盘低几个数量级：i2 ) 内存较之磁盘存储的不稳定性：( 3 ) 磁盘数据库是基于数据“块的存取，而内存 数据库则基于数据“粒”：( 4 ) 事务的串行化存取在d r d b 中显得更重要；( 5 ) 由于 ， 蕊。漱 华中科技大学硕士学位论文 事务直接存取内存数据，发生软件错误的概率比通过缓冲池管理的方法进行存取的 d r d b 要高，因此m m d b 的备份恢复机制要更完善。上述这些差别决定其数据库管 理系统的设计从并发控制到应用接口都与传统磁盘数据库有很大的区别，需考虑内 存直接快速存取的特点，以c p u 和内存空间的高效利用为目标来重新设计开发各种 策略与算法、技术、方法及机制“1 。 2 3 实时双数据库模式设计 由以上叙述可知，实时内存数据库可以在一定程度上解决事务处理实时性问题， 但其存储容量的有限性和具体应用所需存储的数据量的无限性的矛盾以及内存的不 可恢复性决定了，m m d b 不可能单独完成系统的实时，可靠及海量等各种要求。 综合考虑上述两种数据库的优缺点，我们提出m m d b + d r d b = r t d d b 的构 建模式，m m d b 是商用数据库的“工作快照”，存储部分活跃或近期最活跃数据记录。 它们各自拥有独立的数据库管理，完整性和可靠性控制方式，但对外部事务来讲 r t d d b 是一个具有实时特性的整体，即一个完整的实时数据库系统。 2 3 1 功能构架和主要实体 图2 1 ，两个数据库作为独立自治的系统分担部分事务处理，由于数据存储的冗 余，中间需通过各自的数据交换代理交换数据以达到两个系统的数据一致。外存数 据库由于采用商用大型数据库，自备完整的并发控制，完整性检测，数据恢复和友 好的g u i 等机制，上层应用的开发，例如操作管理维护系统o & m 这样的对处理正 确的要求高于实时性要求的事务，最好在其上完成。而实时事务则主要集中在内存， 利用数据快速存取的优势，因此内存数据库需针对实时特性开发全套的管理调度机 制，其中大致包括以下几个功能模块或实体： 事务调度 一组事务在一起运行，由于计算机系统的串行性，不同事务的操作可能交错 进行，这些事务所有操作的一个执行序列，称为这些事务的一个调度。严格串行 。繇瓤f 、，；麓。鞋建 华中科技大学硕士学位论文 化的事务调度是传统数据库的主要特征，而作为实现实时特征的系统核心部件， 它主要负责事务的等待队列管理，资源享用优先级分配，并发控制等。 事务管理 相当于传统的事务管理程序，处理事务的开始，提交，夭折等，所不同的是 具有实时特性。 内外存数据库管理 管理内j ，l , 存的物理数据库，负责数据的组织，存储，存取和恢复。这里的 d r d b s 即商用数据库管理系统，包括了对事务的管理调度，并发控制等数据维 护功能。 内外存数据交换的代理 负责制定内存数据的换入换出策略，与外存相应模块进行数据交换和管理控 制信息的通信。 图2 1 双数据库系统基本构架 9 纛氘l 鎏，二强 华中科技大学硕士学位沦文 2 3 2m m d b 的数据组织和存取特点 m m d b 的物理数据组织和存取方法必须适合内存的直接地址访问特性。传统的 d r d b 中数据以文件形式常驻磁盘，其系统瓶颈是事务存取磁盘的低效率，因此其 数据存储结构的设计目标是减少对磁盘的存取次数，普遍使用例如b 一树这样平衡多 路查找树“1 进行数据“块”存储方法顺序，聚集组织，但m m d b 的快速数据存取 特性决定数据可以分散放置，b 一树失去其优势。目前已提出的数据存储结构主要分 为h a s h 和树型”两种。 h a s h 是种随机存储结构，它可以通过至多一个关键字的比较来定位一个记录， 提供极快的直接存取，在查找定位和投影运算方面有很好的性能，但其缺点是由算 法的固有缺陷而产生的数据分散不均及为避免碰撞而导致的算法实现的复杂性，存 储空间的使用效率不甚理想等。因此，h a s h 在某些特殊的场合，例如只需提供一种 索引关键词就可索引全表，数据逻辑关系较简单，碰撞概率较b f j , t 使用可充分利用 其优势。树型索引，例如t 一树，本身就是为m m d b 而设计，与b 树相比，结构较 深，实现复杂。 另外，为提高牵i n 卡1 用率，通过索引定位的元组不必直接聚集存放在索引值上， 可分散到内存空问中通过存储在索引位置上的指针存取，提高丁变长数据域的存储 效率。 2 3 3r t d d b 的并发控制 在数据库系统中总存在多用户| 一j 时共享或竞争数据库资源，我们称这种现象为 事务的并发，为保证每个请求事务的正确执行和操作后的数据l j 外界的一致性，必 须定义某种原则控制并发事务有序有效的申请和使用资源，此种原则即为并发控制 策略。典型的并发控制策略是基于事务串行调度的原则，通过等待事务队列先进先 出或“时间戳”的力法排列事务，并发控制的设计范围包括冲突的检测，冲突的解 决，串行化规则和运行策略”。 冲突检测的方法大致分为两种消极检测和积极检测，通常我们所说的2 p l ， l o 华中科技大学硕士学位论文 t s o ，s g t 就属于前者，即分别用锁，时间戳和串行图论完成检测。消极检测的特 点是冲突检测发生在读写数据前，积极检测反之。目前针对传统数据库系统的并发 机制已有很多，例如两段锁2 p l ，多元策略等1 2 0 1 ，下面列举几种具体的检测方法： 2 p l 每个事务在取用资源前必须对其加锁，为提高并发度，我们根据事务类型 和操作相容性将锁细化为共享型读锁和排他型写锁，读锁只能与其他同类型锁相容， 而写锁则完全排他。 t s o 每个事务在取用资源前必须分配时间标识，与操作同一数据块的最后一 个事务比较看是否应保存原有的时间顺序。 s g t 并发控制管理器维护着一个串行调度表，记录历史事务调度顺序，通常 只有在表中某事务不再出现时方可将其对应的表项删除，否则当有此类事务出现就 按照s g 的指引完成调度。 d r d b 多用上述方法，其特点是严密的冲突解决机制导致结果的精确性和事务 的串行化调度，串行化是传统并发处理的基本原则，上述每种并发策略均遵循某种 串行化，但串行化过于束缚了事务调度的灵活性，例如上面提到的2 p l 利用加解锁 排列事务，t s o 利用起始时间标识排列和中断事务，s g t 则更明显的用表来实现， 其判断标准的单一导致过多事务被迫过早夭折。 因为存取m m d b 的数据比d r d b 快得多，事务的处理将更迅速。面对相同的 事务访问负荷，m m d b 由于快速存取而缓解了系统的并发处理。因此冲突检测在 m m d b 应用中的基本原理可以不变，但可加入优先级决策信息，同时对冲突解决策 略和运行规则做实时性优化处理。 例如2 p l 是m m d b 通常选用的并发控制方法，在并发“粒度”上不同于d r d b 选小“粒度”锁以提高并发度减少冲突的原则，m m d b 可启用“粒度”较大的锁。 最大的锁即加在整个数据库上。大“粒度”锁的优点是简化了并发控制，但导致事 务处理序列化，例如事务等待队列中长事务排在实时事务前面致使其不能被及时处 理，因此可以对锁的“粒度”进行优化，根据事务取用数据的覆盖范围设定不同“粒 度”的锁，即设计一套加锁的层次模型，称为多“粒度”锁m g l 机制。在2 p l 的实 “。一 ， f 蠢熬靛。、! 鎏，。弘，蠢建 华中科技大学硕士学位论文 现上，d r d b 常通过在r a s h 表存储加锁信息为事务提供数据的存取入口，而m m d b 则可直接在数据域中增加锁状态域，减少了读写的机器指令。 优化并发控制o c c 也是对上述方法的优化，优化冲突检测分为o c c 一2 p l ，o c c - - t s o ，o c c - - s g t ，基本思路与上面相同，只是增加了对c p u 调度优先级的考虑， 例如打破了传统2 p l 导致低优先级事务能抢占高优先级事务的锁。 冲突的解决基本原则是采用事务阻塞和重起两种机制，例如在两段锁协议中要 么让没有获得锁的事务进入等待队列，要么异常中断此事务。但这样通常会引起大 面积阻塞死锁的情况，例如等待队列中某事务在获得某数据区锁后处于等待另一资 源读写权的状态下，而这一资源被另一事务由于资源获取不完全无法执行而长期占 用，在 2 1 】中提到有限深等待队列w d l ，【2 2 】中提到的运行优先级均为解决等 待事务链过常的两段锁优化算法，不同之处在于选择何种等待事务去打破死锁的标 准，前者设置等待队列的最大深度，多余的事务全不予考虑，当然这个队列的深度 要小于导致死锁的可能深度，后者则先中断运行中死锁的事务，释放锁资源。 优化的运行策略是将中断事务的前次调人数据和运行结果等保留在一定容量 的缓冲区中，重新发起时可继续原状态，无需从头开始，对于减少i o ，缩短运行时 间，降低中断率有很大帮助。 2 3 4 实时数据库系统的事务调度和数据一致 传统的数据库系统只提供功能正确性，但对数据库的操作很少受到事务执行时间 的影响。换句话说，传统数据库系统除了某些查询语句允许用户标明时间限制，没 有将时间因子考虑在设计之内，它所基于的假设是任意时刻数据库中的数据在被使 用时都是有效的，时间因子不会改变其有用性。而这不适用于对事务赋予时限的实 时数据库系统，其所有数据均有一定的生命周期“1 。 传统的事务串行调度规则”1 为保持数据库数据一致性预先规定了事务从开始到 结束的一套完整的调度顺序，例如商用数据库中写这样一个简单的操作，从写操作 的合法性检查，加锁控制，写数据的完整性控制，执行读写等操作，刷新相关数据 1 2 华中科技大学硕p 学位论文 以保持一致到最后解锁，牺牲了实时性以获得完整一致的数据，对于实时系统是不 可接受的，实时系统的设计动力最初来自对外部物理环境对象的监督和对外围设备 的控制的实时性需要，系统不完全独立而是需要与外围环境做频繁交互以实时获取 和处理相关信息，因此导致实时数据库满足时限要求和确保内部一致所采用的调度 规则的低效率的冲突。特别是在“硬截止”实时系统中，事务超截止期将给系统带 来灾难性后果”1 ，唯一的解决办法是修改现有的数据致设计重心，探究新的事务 调度规则。这里，我们将针对某些事务对实时要求高于数据一致的特点定义一种新 的实时数据库系统数据一致模型，提出外部数据一致的概念，以区别传统笼统的数 据一致划分，最后我们采用“语义一致性”的概念以强调外围世界对数据库的影响， 同时打破串行调度原则，提出确保外部数据一致的新准则。 1 实时数据库系统数据一致模型 外部数据一致，顾名思义指事务所处理的数据反映了当前外围环境，相对的内 部一致反映的是符合预先指定规则的数据库总体视觉致。在下图中，我们对内外 数据一致有个抽象的描述，数据库与一些物理外设相连，每个外设均对应数据库中 一个相应实体( 用圆圈表示) ，同时数据库还拥有自己的内部数据或衍生信息( 不与 外设相连的圆圈) 。保持相应实体数值与外设的一致就称为外部数据一致，而数据库 内部各实体共有数据的一致则称为内部一致哺1 。 图2 2 实时系统数据一致模型 传统数据库在发现数据不一致后，通常是通过事务回滚将最近修改过的数据覆 。滋氛_ ：蕊；麓玉 华中科技大学硕士学位论文 ! ! ! ! ! ! ! ! ! ! ! = ! ! ! ! ! ! ! ! ! ! ! = = ! ! ! = = ! = ! ! ! ! = ! ! ! ! ! ! = ! ! ! = 盖，但实时系统中是不允许这么做的，因为实时系统要对外部激励或请求及时作出 响应，处理的数据是否外部一致绝对比是否内部一致但已过时的数据更重要，且造 成外部数据不一致的实时事务是无法恢复或重启的，但内部不一致却可通过延后数 据更新的方式解决。例如移动通信网中用户越区漫游做呼叫处理时必须通过查询其 归属h l r 中存储的相关旧位置信息并修改为新路由小区的位置信息，这是一个实时 事务序列，没有在指定时间内执行完全部的事务会引起呼叫业务失败，通常一个完 成的操作最后要做的是共有数据的内部一致更新，但在给外部的响应已正确的情况 下，内部的数据一致可以稍后进行。另外若实时事务序列执行导致“脏”数据修改 错误，还可基于旧有数据更新替代，因此外部数据一致在实时数据库系统中显示着 比内部一致更重要性，为达到系统实时性有时要牺牲内部一致和事务串行调度规则。 2 确保操作一致的非串行化事务调度协议一“语义一致”调度 实时数据库是个并发系统，很多事务并发读写数据库对象，同时实时事务总是 “合作”进行的，彼此间有很多联系，如共享数据联系，通信联系，时间上的联系订1 等。一个完整的事务处理可以看成一个逻辑操纵单元组f a l ，a 2 ，a n ) ，集合中的 每个元素均表示对数据库某字段域独立的读或写，则对并发事务有如下定义啪： 定义1 ：设序列s = r l ，死，兀) ，乃= ( a 1 ，a 2 ，a m ，则有 ( 1 ) 对每个正t ，a i t i ，a i 在s 中仅出现一次或根本不出现； ( 2 ) 假设a i ，a j 是孔t 中的动作，并且在耳中a i 先于a i 执行，则在 s 中a i 先于a i 执行。 定义2 ： 当两个事务序列对数据库的作用和执行所得结果完全一致时，我们说 这两个序列是等价的。 定义3 ：串行化事务序列等价于一个串行序列，其事务的执行是顺序的。 通过以上定义我们可以看出，实时事务序列的结果并不完全依赖于其执行顺序， 传统的数据库事务调度所遵循的串行化调度规则严格控制事务的调度顺序对实时系 统是不必要的。以下我们定义的基于“语义一致”的事务序列如下： 定义4 ：序列0 是“语义一致”的，当且仅当 1 4 蕊。b ，；蠹。 ；-藕蠹： 华中科技大学硕士学位论文 ( 1 ) o 的执行导致数据厍外邵一致； ( 2 ) 所有“可操作性”事务能从数据库获得外部一致的数据。 这里，“可操作性”事务指不可恢复的外部触发事务或对外部实体有直接影响的 事务，此种事务的正确执行不要求满足内部一致性。从上面的定义可知，执行o 不 能保证内部一致，需要后续操作来完成全部的一致性。 3 事务与内部数据一致性的关系 当实时事务不能在指定时间内完成时，要么将其撤消并恢复其影响，或在允许的 范围内得到不精确的结果四1 1 而由于实时要求的重要性，我们选择后者优先考虑， 根据事务对内部数据一致的依赖程度决定事务的调度顺序，因此为方便研究，我们 将根据事务分为如下几类： 强依赖事务必须在内部数据也一致的条件下才能执行的事务，例如两个并发事务 a 和b ( a 和毋分别表示其动作集合的元素) ，则执行序列等价于 a j ，a 2 ，山，山，曰j ，岛，毋，是个串行化序列。 弱依赖事务某些事务对实时数据库的动作可分为两个部分e - p a r t ( 维护外部一 致) 和i - p a r t ( 维护内部一致) ，通常的执行顺序是先前者后后者，这 是由实时系统的时限特点决定的，采用这种划分可以先及时返回结 果然后进行低优先级内部一致的后续处理。例如事务b 等待事务a 的完成方能开始，其中a 由也和a i 组成，b 为下面将提到的无依赖 事务，其执行序列可以这样安排 a l ，a 2 ，b l ，b 2 ，b 3 ，a 3 ，a 4 这种划分有效的将a 事务分为“硬时限的a 。和“软，时限的a ， 但此时的a i 与a 不完全相同，包含b 的后续处理。 无依赖事务仅依赖外部一致即可正确执行的事务，内部一致通过周期复制规则完 成。例如事务a 和b ，其执行序列可以这样安排 a l ，a 2 ，b l ，b 2 ，b 3 这种划分将内部一致放到后续周期处理中，执行完这个序列只能保i 正 一一 _ 1 s 。蓬蕊融i 滋“熬 华中科技大学硕士学位论文 外部一致。 4 事务调度算法 早在实时数据库系统引起足够重视的年代，“硬”实时对数据库和实时系统提出 了融合数据一致和时限的要求。实时系统的各种事务调度方案1 2 1 5 1 分析了事务的到 达时间，最坏情况执行时间，截止期以及危险性，通常只考虑对某种资源例如c p u 或竞争多种资源的调度，导致对最坏情况执行时间的估计在不计算i o ( 实际执行时 必须考虑在内) 的情况下估计过高，并且没有数据一致的要求，这在数据库系统中 是由并发控制完全承担。 典型的事务调度算法包括传统的先到先服务( f c f s ) ，单调速率调度( r m s ) ， 最早死线优先( e d f h p ) 也称为死线驱动调度( d d s ) 和最有用优先( h v f h p ) 算法，r m s 是指按单调速率优先级，即按事务周期的长短来分配的算法，周期越短， 优先级越高 1 7 1 ，是一种静态调度算法，e d f h p 的依据是根据实时事务对执行时间 要求的严格和紧迫程度调度事务，赋予最紧迫或“硬”实时事务最高优先级，而 h v f - h p 的根据是事务在指定时限内完成对系统和应用的重要程度，越重要优先级越 高n ”，两者均为动态调度算法。 这里，我们采用的算法是根据事务非串行化语义特征，即对数据一致的依赖程 度，采用事务协作表t c t 调度事务，为描述方便，先做如下定义： 定义：有事务n ，其读取的数据由另一事务乃写入，我们将这类事务记为死 d e p ( z 1 ) 。 其具体描述如下： r l死乃 n( ( ( 乃 ( ( ( ) ： 代表n 不属于d e p ( t 1 ) ，t 1 可先于如执行即使等待队列中死先于r l 。 值得注意的是，t c t 并非对角对称的，当事务等待