（计算机系统结构专业论文）dbs多版本并发的移动数据库的设计与实现.pdf

摘要摘要嵌入式系统和无线通讯技术的结合，产生了一种全新的计算模式移动计算模式。在移动计算模式下，用户使用手持计算设备，通过无线网络实现对信息的访问，不受时间和地点的限制，也不受运动方式的限制。在移动计算技术中，有一个很重要的分支，就是移动数据库技术。由于移动计算环境的特点，移动数据库必须支持计算平台的移动、网络条件的多样、无线通讯的频繁断接和有限的资源，这些都是传统数据库技术无法解决的，因此需要针对移动计算的特点研究新的方法。为了更好的讨论移动数据库技术，本文首先对移动计算环境的特点进行了分析。然后对移动数据库中一些重要的概念作了简单的介绍。紧接着回顾了移动数据库发展过程中的一些重要技术。在成熟技术的基础上，本文对冲突的产生、捡测与处理进行了深入地讨论。先是针对读写操作造成的冲突的产生机制和可能的检狈方式进行了讨论。随后根据冲突的不同类型，就冲突的分类方式提出了一些见解，并对每种可能方式提出了比较常用的冲突处理方案。本文的核心是提高移动数据库系统的并发性能。首先分析了使用快照一级隔离级别的多版本数据库作为移动数据库系统的中央数据库的优势，并针对移动数据库系统对中央数据库的要求和多版本数据库的并发特点，提出了一种解决多版本中央数据库并发问题的方案，并对这个方案的有效性进行了分析此外，本文针对移动计算环境安全性、可靠性差的特点，特别提出了数据安全和故障处理策略，以提高移动数据库系统的应用性。在最后，本文提出了一个完整的移动数据库系统的设计方案，在这个方案中，应用了前面提出的安全策略、故障处理策略和多版本中央数据库的并发策略。方案中给出了一个实用的移动数据库系统的所有实现细节和数据同步中每一步的细化流程图。根据本文中的移动数据库设计方案，本人所在的项目小组已经实现了一个实用的移动数据库同步系统，并成功进行了系统初始化和多用户并发的数据同步关键词：移动计算；数据库；数据复制；同步技术；冲突；多版本并发id b s 多版本并发的移动数据库的设计弓实现d e s i g na n di m p l e m e n t a t i o no f am o b i l ed b m sw i t hm u l t i v e r s i o n e d - d b sc a ok e ( m o b i l ed b m s )d i r e c t e db yz h o n gx i c h a n gt h eu n i t i n go fe m b e d d e ds y s t e ma n dt e l e c o m m u n i c a t i o nt e c h n o l o g i e sg e n e r a t e sab r a n - n e wc o m p u t i n gm o d e ：m o b i l ec o m p u t i n g i nm o b i l ec o m p u t i n ge n v i r o n m e n t ，u s e rc a na c c e s si n f o r m a t i o nw i t hp o c k e te q u i p m e n tt h o u g l lw i r e l e s sc o n n e c t i o n sr e g a r d l e s so ft h el o c a t i o na n dt h et i m e ，e v e nt h em o v e m e n to ft h eu s e r o fa l lt h em o b i l ec o m p u t i n gt e c h n o l o g i e s , m o b i l ed b m si sav e r yi m p o r t a n tb r a n c h a sar e s u l to ft h em o b i l ec o m p u t i n ge n v i r o n m e n t ，m o b i l ed b m sm u s th a v et h ea b i l i t yt os u p p o r tm o b i l i t y , h i g i lb a n d w i d t hv a r i a b i l i t y , d i s c o n n e c t i o n ，a n dl o wb a n d w i d t h ，w h i c ht r a d i t i o n a ld b m sc a nh a r d l yd e a lw i t h t h e r e f o r e ，j tn e c e s s i t a t e st h er e s e a r c ho fn e ws o l u t i o n sa c c o r d i n gt ot h ec h a r a c t e r i s t i co f m o b i l ec o m p u t i n ge n v i r o n m e n t t h i st h e s i ss t a r t sw i t ht h ea n a l y s i so ft h ec h a r a c t e r i s t i co fm o b i l ec o m p u t i n ge n v i r o n m e n t ，w i t c hi sf o l l o w e db yt h ei n t r o d u c t i o no fs o m ei m p o r t a n tc o n c e p t so fm o b i l ed b m sa n dt h er e v i e wo f t h ei m p o r t a n tt e c h n o l o g i e si nt h i sf i e l d b a s e do nt h e s ep r o v e nt e c h n o l o g i e s , at h o r o u 曲d i s c u s s i o no ft h eg e n e r a t i o n ，d e t e c t i o na n dr e s o l u t i o no f c o n f l i c ti sp u tf o r w a r d f i r s t ，d u et ot h ec o n f l i c tc a u s e db yt h ew - ro p e r a t i o n s ，t h et h e s i sg i v e sr e a s o no fh o wt h ec o n f l i c tg e n e r a t e sa n dt h ep o s s i b l ed e t e c t i o nm e t h o d t h e na c c o r d i n gt ot h ew - wt y p e so ft h ec o n f l i c t s , t h i st h e s i sb r i n g sf o r w a r dav i e wo fh o wt os o r tt h ec o n f l i c t s ，a n dp r o v i d et h er e s o l u t i o ns t r a t e g i e so fe a c ht y p e t h ec l o uo ft h i s t h e s i si st h ei m p r o v e m e n to ft h ec o n c u r r e n c yc a p a b i l i t yi nm o b i l ed b m s t h i st h e s i sp r e s e n t st h ea d v a n t a g e so fas n a p s h o pi s o l a t e dm u l t i - v e r s i o nd b m sa st h ed b sa n dp r o p o s e sas o l u t i o no ft h ec o n c u r r e n c yd i f f i c u l t yw h e nu s i n gt h em u l t i v e m i o nd b s ，a c c o r d i n gt ot h er e q u i r e m e n to ft h em o b i l ed b m sa n dt h e c h a r a c t e r i s t i eo fm u l t i - v e r s i o nd b m s t h e nt h i st h e s i sg i v e st h ep r o o f o f t h es o l u t i o n sv a l i d i t y m o r e o v e t od e a lw i t ht h ef a c tt h a tt h em o b i l ec o m p u t i n ge n v i m n m e n ti sl a c ko fs e c u r i t ya n dr e l i a b i l i t y , t h i st h e s i sp r o p o s e st h ed a t as e c u r i t ya n df a i l u r er e c o v e r ys o l u t i o n st oi m p r o v et h eu s a b i l i t yo ft h em o b i l ed b m s l a s t t h i st h e s i sp r o v i d e sac o m p l e t ed e s i g no fa na p p l i e dm o b i l ed b m s t h i sd e s i g ng i v e sa l lt h ed e t a i lo fam o b i l ed b m ss y s t e m , i n c l u d i n gt h ed a t as e c u r i t ya n df a i l u r er e c o v e r ys o l u t i o n sa n dt h em u l t i - v e r s i o nd b sc o n c u r r e n c ys c h e m e w i t ht h ed e s i g ni nt h i st h e s i s ，m yp r o j e c tt e a mh a sa l r e a d yi m p l e m e n t e ds y n c h r o n i z a t i o ns y s t e mo fam o b i l ed b m s ，s u c c e s s f u l l yi n i t i a l i z e dt h es y s t e ma n dc a r r i e do u tt h em u l t i - u s e rs y n c h r o n i z a t i o n k e y w o r d s ：m o b i l ec o m p u t i n g ；d a t a b a s e ；d a t ar e p l i c a t i o n ；s y n c h r o n i z a t i o n ；c o n f l i c t ；m u l t i - v e r s i o nc o n c u r r e n c yn l图目录2 1 移动计算体系结构图目录2 2 移动数据库和分布式数据库的分类3 1 移动数据库的体系结构3 2 移动数据库的分层结构5 1m h 三种状态问的转换8 1 上载总体流程8 2 下载总体流程9 1 同步请求应答细化流程9 2m h 上载过程细化流程9 3m s s 上载过程细化流程9 4 发送上载消息细化流程9 5m h 上载后续处理细化流程9 6 整理下载数据细化流程9 7d b s 上载事务细化流程9 8d b s 下载事务细化流程4 8 - 5 09 9d b s 下载后续处理事务细化流程v 5 05 1“矗n：!加弘钳钙牾钉钉表目录表目录5 1 初始状态5 2m h l 同步后主副本状态5 3m h 2 同步后主副本状态2 ：15 4 先执行t 再执行t 2 主副本状态2 25 5 先执行t 2 再执行t 1 主副本状态5 6 冲突的分类。2 22 48 1 上载数据的修改方式的确定4 0、，l h声明我声明本论文是我本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，本论文中不包含其他人已经发表或撰写过的研究成果。与我一同工作的同忐对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。储繇嗜浒嗍炒弓论文版权使用授权书木人授权中围科学院计算技术研究所日j 以保留并向国家有关部门或机构送交本论文的复印件和电子文档，允许本论文被查阅和借阅，可咀将本论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编本论文。( 保密论文在解密后适用本授权书。)作者签名：肴冲导师签名：日期：如pj - 土弓f第一部分移动数据库系统综述第一部分移动数据库系统综述第一章引言1 1 移动数据库技术的产生和发展的背景计算机技术1 2 6 的飞速发展，不仅仅体现在计算能力上，更多的是体现在对新应用的支持上。计算技术和无线通信的结合产生了一种全新的计算模式移动计算在移动计算模式下，用户使用移动计算设备( 智能手机、p d a 等) 通过无线网络实现以往微机在有线网络支持下才能实现的操作【2 】【3 】1 4 】【1 4 1 1 7 1【2 0 。随着科学技术的发展，移动计算设备计算能力的提高甚至超过摩尔定律( 1 8个月翻一番) 的速度，无线网络也已经几乎无处不在。硬件平台的普及，使得几乎每个人都可以方便的使用移动计算技术。现代人的流动性，对移动计算技术不断地提出新的要求。可以预见移动计算技术必将在信息时代中扮演重要的角色，并对人们的生活和工作造成深远的影响。下面我们从可能性和必要性两个方面来介绍一下移动计算技术发展的背景。a ) 移动计算技术发展的可能性近年来，无线通讯技术和掌上计算设备的爆发式发展，又带动了嵌入式软件的发展，共同为移动计算技术提供了产生与发展的平台。移动计算设备的发展电子技术的发展，使得各种计算设备的处理能力和存储能力每1 8 个月就翻一番。近年来，移动计算设备的发展速度甚至超过了摩尔定律的预测。仅仅几年前，能够支持移动计算的设备还只有很少人使用的p d a 。而现在，几乎每个人的移动电话都足以支持移动计算掌上电脑、手持电脑、p d a 、g p a 卡的性能大幅提高。最近已经有厂商推出长度只有2 0 厘米使用奔腾四代c p u 、2 0 g 硬盘的掌上电脑。这样的硬件平台，可以充分满足移动计算的几乎任何要求。嵌入式软件的发展软件技术的发展和硬件同样迅速为支持移动计算，各种嵌入式操作系统，嵌入式数据库、嵌入式通讯软件不断出现。除大厂商自主开发外，自由软件的发展为嵌入式软件提供了新的契机，嵌入式l i n u x ，s q l i t e 等自由软件使得一些小的厂商也可以在此基础上开发自己的软件系统，从而进一步推动了移动计算的发展无线通讯的发展近年来，红外技术、无线局域网、无线广域网、蜂窝通讯系统以及卫星通讯技术都得到了快速的发展。无线网络用户几乎可以在任何时间任何地点从网络中获取信息。d b s 多版本并发的移动数据库的设计与实现b 1 移动计算技术发展的必要性现代人流动性交通发达的今天，每个人活动的范围大大增加，可能延伸到世界任何一个角落。人们不能满足于只能在有限的空间范围内获取信息。随着生活和工作节奏的加快，人们也不能满足于在有限的时间内获取信息。这就需要由移动计算技术来满足人们随时随地，甚至在移动中获取并处理数据的要求。应用领域的需求随着信息化的进程，电子商务( e已经不能满_commerce)足企业的要求，需要更进一步的发展为移动商务( mc o m m e f c e ) 只有通过移动计算的支持，才可以真正做到“商务运作无处不在”。在移动商务的支持下，在不久的将来，企业运作模式将有一个根本的转交。在军事上，实时指挥、协同作战等领域也对移动计算技术提出了新的要求。除此之外，服务业要做到信息的接收与查询不受时间地点的限制，也同样离不开移动计算技术在这两个方面的共同作用下，移动计算技术发展迅速，并且应用到了众多领域之中。在此基础上，产生了一种称为普适计算( p e r v a s i v ec o m p u t i n g ) 的概念。普适计算就是无时不在无处不在的计算，它要求计算摆脱单一平台的限制，使得系统可以根据用户的需要，自由的裁减和定制，以提供个性化服务由于移动计算平台和接入协议的多样性和移动数据管理的复杂性，需要专门支持移动环境的软件来进行移动数据的管理和传输，这就使得移动数据库技术逐渐成为移动计算技术的基础和最重要的分支。1 2 移动数据库技术的现状和前景鉴于以上原因，国内外很多机构都展开了对移动数据库的研究，取得了大量成果。各数据库软件厂商，也纷纷推出了自己的移动数据库产品。移动数据库技术涵盖众多领域，涉及数据库技术，分布式计算技术，嵌入式软件技术、移动通讯技术 1 9 】【2 1 1 【3 6 1 ，有广阔的应用前景。下面我就介绍一下移动数据库技术的重要成果。在国外，i l l i n o i s 大学c h i c a g o 分校、g e o r g em a s o n 大学、k o r e aa d v a n c e di n s t i t u t eo f s c i e n c ea n dt e c h n o l o g y 等院校对移动数据库的复制技术进行了深入地研究。其中j i mg r a y 提出的两级复制机制的影响尤为深远。p i t t e b u r g h 大学、w a s h i n g t o n 大学、s o u t hm e t h o d i s t 大学、o k l a h o m a 大学、m o n a s h 大学、b i l k e n t大学等对移动事务处理和位置相关计算进行了研究。s t a n f o r d 大学、s o u t h w e s t e r nl o u i s i a n a 大学、澳大利亚国立大学、b i l k e n t 大学、香港城市大学、香港理工大学、新加坡国立大学研究了数据广播和移动信息发布技术。对移动数据库技术贡献最大的是p u r d u e 大学和r u t g e r s 大学。前者在移动事务处理和移动数据库复制2第一部分移动数据库系统综述上提出了许多重要算法，如移动数据库加锁机制、移动事务管理机制等。后者对移动数据库技术进行了最全面的研究和分析，在移动计算体系结构、移动事务处理、移动复制算法、移动数据管理等方面都处于领先地位。在国内，人民大学、东北大学、中科院软件中心、国防科技大学、哈尔滨工业大学、华东理工大学等学校和机构都对移动数据库系统进行了研究。其中人民大学以王珊教授为首的研究小组提出了三级复制结构1 1 9 1 ，处于全国领先水平。除了科研机构外，各大数据库软件提供商也着手推出自己的移动数据库系统，其中以s y b a s e 的u l t r a l i t e ，i b m 的d b 2e v e r y w h e r e 和o r a c l e 的o r a c l el i t e最具代表性。其中s y b a s e 对移动数据库市场最为重视，u l t r a l i t e 在各项指标的比较中也处于领先地位。国内的人民大学和东北大学也推出了自己的商业系统，小金灵( k i n g b a s el i t e ) 1 5 1 1 2 3 】1 3 7 】和东大r i i ，其中小金灵的技术已经接近国际先进水平。2 0 0 3 年，中国科学院软件中心着眼于未来的移动数据库市场，开始研究和开发d b s 多版本并发的移动数据库系统。在移动数据库的研究中，可用性问题现在已经基本得到解决，目前的问题主要是如何提高性能和移动数据库系统的易用性。所以在今后移动数据库研究中，如何增加移动数据库系统的并发性能、如何减小同步时的数据量和如何使用户更容易使用移动数据库成为大家关心的焦点。其中在减小同步数据量方面，上要的研究方向是数据广播和移动信息发布技术；在增加易用性方面，上要的研究方向是用户界面、位置相关数据处理和移动对象索引、移动数据安全等技术；在增加系统并发性方面，主要有三级复制机s t j 1 9 和本文涉及的d b s 多版本并发技术。1 3 本文的研究方向在移动数据库技术的研究和应用中，学术上的研究和具体的应用的脱节十分严重。一方面是各个机构不断提出新的算法和技术，但很少考虑到这些新技术在实际的商务应用的前景如何另一方面，各大数据库厂商基于大型分布式数据库系统的技术，都推出了自己的产品，在这些产品中，却很少用到最新的移动数据库技术的研究成果。在这方面我国的人民大学和东北大学做得比较出色，在学校研究小组研究成果的基础上，推出了商用的移动数据库系统。随着商务活动的规模和范围不断增大，移动数据库系统的并发性能和响应速度在现实的商务系统中显得越来越重要本文的核心是通过使用快照一级隔离的多版本并发中央数据库来增强移动数据库系统在数据同步时的并发处理能力，由此提高整个移动数据库系统的性能。由于移动数据库系统研究和应用的脱节，本人希望通过实现一个现实的移动数据库系统，来检验中央数据库多版本并发的移动数据库系统的正确性和性能。3d b s 多版本并发的移动数据库的设计与实现并通过这一个系统，对于在移动数据库研究中比较容易忽视的实用技术，如冲突的检测和处理以及故障的处理等问题进行比较深入地讨论。本文的研究内容主要分为两个部分，一个部分足移动数据库技术的讨论，另一个部分说明如何应用这些技术，实现一个现实的系统。在这几个方面，本人做了如下的工作：中央数据库多版本并发方面的研究现有的移动数据库系统大多应用两级复制技术，使用增量的数据同步。但应用这两种技术时，在中央数据库中的上载和下载事务会因为w - r 冲突而无法并发执行，这将极大的影响系统的效率。本文为解决这一问题，使用快照一级隔离的多版本并发数据库作为中央数据库以提高系统的并发性能。但应用多版本中央数据库后，如果不调整系统中上下载的并发方式，将造成移动数据库系统的数据错误。为此，本文中提出了一种同步并发控制方案，在保证系统数据正确性的前提下，使用多版本中央数据库解决了上下在无法同时进行的问题。冲突检测及处理方面的研究由丁二移动计算的特点，移动数据库系统在一个用户读写数据库的一个副本时，无法对所有其他副本加锁，这就是的数据冲突在移动数据库系统中不可能被避免。为解决这个问题，所有的商用系统都采取了事后检验和语义相关冲突处理的方法。本文结合具体的应用探讨了冲突产生的原因，和检测的方法，并通过对冲突的分类，提出了一些常用的冲突处理手段。特别是对于移动入户问w - r 操作造成的冲突，现在在移动数据库技术中讨论的还十分不够，本文举例说明了这类冲突产生的过程，并从代价的角度上分析了为什么在现实的系统中都不提供针对这类冲突检测和处理方案。故障及安全方面的研究移动计算环境对数据安全和故障处理都有特殊的要求，而这类处理方案与具体的系统关系比较密切，很难从其他系统中借鉴。所以，本人针对本文中涉及的移动数据库系统的具体情况，提出了数据安全和故障处理方案，以保证移动数据库系统在任何情况下都是安全的，而且不会出现数据错误移动数据库技术在现实系统中的应用移动数据库是一种面向应用的技术，研究成果在实际系统中的应用比研究成果本身更为重要有鉴于此，本文除了提出一些应用在移动数据库中的技术外，还重点研究了如何将这些技术应用到移动数据库系统之中。为此，本文提供了一4第一部分移动数据库系统综述个现实的系统的实现方案，设计了系统的总体运行方式，提出了支持系统运行的数据结构和消息的格式，并对同步过程的每一步提出细化的系统流程。以便验证这些技术的正确性和有效性，并为以后的移动数据库研究提供一个平台。1 4 本文结构本文共分为三个大的部分。第一部分介绍移动数据库技术整体发展的情况，共分为三章，分别介绍移动数据库技术发展的背景，移动数据库的基本概念和移动数据库的关键技术。第二部分介绍将在本文设计的系统中使用的技术，分为四章，开始介绍本系统采用的成熟技术，接下来讨论冲突检测和处理机制，然后是本文的核心：多版本d b s 在移动数据库系统中的应用，最后针对移动计算环境的特点讨论安全问题、故障处理和一些细节问题。第三部分是系统的实现，共有两章，开始介绍系统的总体设计，然后对总体设计的同步流程进行细化。在这三部分之后将对本文中提到的工作进行总结并提出下一步的研究方向。d b s 多版皋并发的移动数据库的设计与实现第二章移动数据库的基本概念2 1 移动计算环境和一般的计算环境相比，移动计算环境 1 7 】【1 9 11 2 0 1 有着本质的不同。在某些方面，移动计算环境与分布式计算环境有着某种近似。但在更多的方面，移动计算环境有着自己的特点。在传统的分布式计算环境中，计算机位置固定，计算机的地址不变，各计算机之间通过高可靠性的快速网络保持持续的连接，各计算机之间地位完全对等。但在移动计算环境中，这些都将不再成+ - + - - - i + 1 【1 4 1 6 1 【2 0 】【2 1 1 2 6 3 1 1 。移动环境需要支持用户在计算的过程中任意移动，并且进行于位置相关的计算。由于无线网络的高价格，移动计算设备只能在必要时才接入网络。在与其他固定计算设备相连时，无线网络的低可靠性、低传输速率和移动设备有限的计算能力，决定了移动设备和固定设备的地位是不对等的。为了克服上述局限性，必须针对这些特点，设计特定的结构和算法以支持移动计算。在这些技术的支持下，移动计算模式可以支持很多全新得应用，使得用户可以更为方便的获取和处理信息。下图是计算典型的移动计算体系结构1 2 1 1 。图2 1 移动计算体系结构在图2 1 的移动计算体系结构中可以看到，固定网络上有两类节点，分别为有无线通讯接1 3 的移动支持节点和没有无线通讯接口的固定主机节点，两类节点6第一部分移动数据库系统综述和连接两类节点的高速固定网络构成了移动计算体系结构的可信部分。在每个无线单元中，有若干各移动主机( m h ) 通过蜂窝技术、无线局域网，无线广域网、卫星通讯技术等无线接入技术中的一种或几种与m s s 连接，从而接入固定网络。任何一种无线接入技术都不可能用一个网络单元就覆盖整个地球，无线接入技术不仅仅要保证移动用户在一个单元内可以自由移动，还要保证移动用户在网络单元间切换的时候仍能随时保持网络连接，这样就实现了计算的自由移动性。与传统的固定计算环境相比，移动计算环境有如下的显著特点【2 1 【1 4 1 7 1 2 1 1 【2 2 】【2 3 2 5 -移动性在移动计算环境中，移动计算设备不仅需要在不同的地方联通网络，还需要能够在移动中保持网络连接。在移动时，不仅要保证在一个移动通讯单元内可以自由移动，还要支持移动用户在移动通讯单元间的过区切换。频繁断接性移动计算的硬件支持平台经常会受到电池容量、网络条件、通信价格等因素的制约，而不能保持移动计算设备与固定网络的持续连接。这就要求移动计算系统在断连条件下仍然能够正常运行，至少不会因为网络断连而出现操作错误。网络条件多样性在移动计算体系中，不同的设备之间的网络连接条件可能相差十分悬殊，即使对于一个移动计算节点，在不同的时间地点也可能会有不同的接入条件。因此移动计算系统必须提供高灵活性和高适应性，在任何网络条件下都能够提供较高的效率。计算的非对称性无线网络与有线网络、移动计算设备与固定计算设备之间性能的差异，导致了移动计算系统中，不同的节点之间的计算能力具有非对称性。移动计算系统必须针对这种非对称性，采取适当方法( 如数据广播和增量同步) 保证整个系统的效率处于较高水平。资源有限性移动计算设备在计算能力、存储能力、网络带宽，用户界面等方面都受的极大的限制，特别是电源技术，更是多年都无法得到显著提高。在移动计算系统中，有必要针对这些限制在数据管理，数据传输、事务管理等方面做出改进低安全可靠性由于移动平台远程访问数据，而且移动设备十分容易遗失，这就对移动计算中的安全性设计提出了新的要求。而由于电源能力差、通讯易受到干扰，如何在这种不可靠的硬件和通讯平台上建立可靠的计算系统也是一个新的问题。位置相关性移动计算在需求上与其他计算模式最大的不同就是位置相关性。支持位置相关计算也是移动计算系统设计的主要目标之一上面的特点说明，移动计算系统与传统的分布式计算系统有着非常大的区别，必须通过很多扩充和优化，使得已有的技术支持移动计算。当前，移动计算7d b s 多版本并发的移动数据库的设计与实现计算机科学的一个重要分支，涵盖移动硬件设备、移动通信、和移动软件技术( 例如：移动数据库技术) 等很多方面。2 2 移动数据库与分布式数据库分布式是为了提高数据库系统整体性能和可靠性而产生的一种数据库系统，具有以下特点：资源分散性( d i s t r i b u t e d ) ，资源在物理上分散于若干节点。协同f l $ , j 性( a u t o n o m o u s ) ，全局中所有节点之间关系完全对称，可以通过局部化原则减小通讯量。透明性( t r a n s p a r e n c y ) 擞据存储位置，数据存储方式等对于用户是透明的。工作并行性( p a r a l l e s m ) ，可以将同一事物拆分后在不同节点问同时执行。整体强健性( r o b u s t n e s s ) ，任何一个或几个节点的故障都不会对系统的可用性造成影响。同时也意味着任何节点加入系统时系统仍然能够正常运行。考虑到上一节中移动计算的性质，就会发现，两者之间有着很多的共同点。资源分散性、工作并行性的思想在移动数据库中同样需要，而移动计算的低可靠性和频繁断连性需要分布式数据库的整体强健解决方案。所以一般认为，移动数据库技术是依据移动计算的特点对分布式数据库的扩充。分布数据多数据库图2 2 移动数据库和分布式数据库的关系图2 2 显示出移动数据库与分布式数据库的区别与联系1 1 4 1 1 2 8 。移动数据库与分布式数据库的区别主要是需求和平台造成的，为支持位置相关计算，移动数据库必须提供移动计算设备的位置信息，而分布式数据库的透明性的需求则需要将位置信息对用户完全隐藏起来。无线网络的传输速度和价格决定，生成一个系8第一部分移动数据库系统综述统时钟的通讯代价足不可接受的。而没有一个系统时钟，就无法对整个数据库系统中的事务进行排序，数据库系统的事务并发方式将有根本转变。在分布式数据库系统中，许多计算设备既是客户端，同时也是服务器，但在移动数据库系统中，由于移动计算设备计算能力的限制，移动设备只可能充当客户端的角色，所以数据库的体系结构有必要由分布式数据库的网状结构转变为移动数据库的分层结构。由于移动设备的频繁断连性，移动数据库系统一般无法保持整个系统的强一致性，必须基于其他的一致性，如弱一致性或收敛一致性来设计系统。由于上述原因，移动数据库虽然和分布式数据库有某种程度的类似。但不论在体系结构或事务执行方式上都有着本质的不同，足一个全新的研究领域【7 1 。2 3 移动数据库的设计目标根据移动计算和数据库系统的需求，j i mg r a y 为移动数据库系统提出了下面四个设计目标( s m s c ) f 1 8 1 ：可用性和伸缩性( s c a l a b i l i t y ) ：保证系统随时可用，并且提供高伸缩性。移动性( m o b i l i t y ) ：支持移动设备在移动和断连时的数据库操作。可串行性( s e r i a l i z a b i l i t y ) ：数据库系统事务执行满足可串行化要求。收敛性( c o n v e r g e n c e ) ：系统总能够收敛于一个一致状态。在现有的移动数据库系统中，可用性、移动性和收敛性目标已经基本实现，但可串行性目标的实现还是有困难的。目前只能通过将不可串行化的事务取消执行或使用语义相关事务修改机制( 冲突处理机制) 来解决这个问题，但不能保证无需用户干预的事务自动执行，这还远达不到其他数据库系统的水平。2 4 移动数据库的应用前景移动数据库系统的发展是由应用直接推动的，所以当商业化的移动数据库系统出现时，立刻在许多行业投入了应用，并迅速取得了成功。如警务通、税务通、水文自动观测系统等。此外移动数据库系统在下面的领域还有着广阔的应用前景【3 】【9 】【1 1 】【3 8 1 公共事务行业：警务人员追缉逃犯时，需要一个记录逃犯资料的数据库系统，这个系统的需求决定了它是一个移动数据库系统。除此之外，税务人员的税务管理系统对移动性和数据管理能力也都有很高要求，用移动数据库系统实现是最佳的选择。零售业：零售人员可以通过移动数据库系统，随时帮助客户了解产品信息，随时随地处理业务，并将订单随时提交给总部。这将为客户提供比网上购物9d b s 多版本并发的移动数据库的设计与实现更为方便快捷的购物方式。制造业：有移动数据库的支持，工程师无需携带大量的数据就可以进行需要大量信息支持的工作，并迅速解决问题。金融业：在金融业中，时间就是金钱，信息就是生命移动数据库的方便快捷和数据管理能力可以让交易员在任何时问任何地点得到需要的信息，并进行金融交易。医疗行业：随着个人医生的出现，现在医生已经不局限于只在医院中为病人诊断了。有了移动数据库，医生就不再需要携带大量的病历，并亲自到患者家中，只需要在医院中查询数据库就能监控所有患者的状况。此外，移动数据库在军事指挥，智能交通管理、物流管理、消防管理等方面都有广阔的应用前景。由于移动数据库还可以在手机等个人移动计算设备上运行，将来会有更多的面向个人的应用被陆续开发出来。l o第一部分移动数据库系统综述第三章移动数据库关键技术3 1 移动数据路的体系结构在上一章中我们阐述了移动计算和移动数据库的一些主要概念和性质，这些性质决定了移动数据库系统的体系结构与分布式数据将有本质的不同。下图是经典移动数据库体系结构，大部分科研成果和商业产品的设计与实现都是基于下图所示的体系结构图注：f f i ；m h ：m s s ：d b s ：f i x e d h o s t ( 固定主机，没有无线通讯接口)m o b i l eh o s t ( 移动主机)m o b d es y n c h r o n i z a t i o n , s c r v e t ( 同步服务器，处理m h 同步请求的固定节点)d a t a b a s e s e r v e r ( 中央数据库，通过高速网络连接的大型数据库)图3 1 移动数据库的体系结构从图3 1 中可以看到，由于网络性能的差异，在网络连接上分为两个部分，快速可靠的固定网络部分和不可靠的无线网络部分。在固定网络中，任何数据同步操作或数据库管理活动都可以遵循分布式数据库或分布式操作系统的模式来执行，如果考虑到分布式系统的透明性，多中央数据库和多同步服务器的系统在逻辑上可以看作只有一个中央数据库和一个同步服务器。固定网络可以提供的功能中最重要的是可以维持一个全局时钟，为所有的事务进行排序，但在无线网络的部分这样做则是很不经济的。而且，无线网络部分还不适宜进行大量的数据传输，也不能执行对全系统有重要影响的重要事务，在移动数据库的设计中应该特别考虑到减小无线网络的通讯量和无线部分的故障恢复。由于移动设备间通讯的低容量和高价格，移动数据库系统和分布式数据库系统不一样，每个事务不可能1 1d b s 多版本并发的移动数据库的设计与实现在全系统的范围内多机协同执行，也不可能将执行结果由发起者直接反映到整个系统的所有其他移动计算设备上。所以移动数据库没有采取分布式数据库的网状对称结构，而是采用了图3 2 中类似c l i e n t - s e r v e r 结构的分层非对称结构。整个移动数据库系统分为三个层次：移动设备( m h ) 同步服务器( m s s ) 中央服务器( d b s ) 【2 4 。在这三个层次中，m h 与m s s 通过无线网络连接，m s s 与d b s 之问通过高速固定网络连接。数据库事务在m h 中执行后通过m s s反映到中央数据库中，并最终反映到其他m h 上。国m h 目m h 目m h 目m h 色事童叁童基童l；j无线网络同步服务器( m s s )图3 2 移动数据库的分层结构网络如图3 2 中的分层结构可以提供很高的系统伸缩性，任何m h 的连接和断连可以由m s s 统一处理。所有的m h 通过m s s 和d b s 彼此联络，m s s 和d b s在高速固定网络中，有利于提高系统的稳定性和故障处理能力。由于移动设备问通讯速度慢，无法产生全局时钟，所以要保证系统的串行性，最好的方法是将事务通过m s s 进行集中管理。而m s s 的支持也可以更好的实现m h 的移动性。所以为达成上一章中提到的移动数据库的四个主要设计目标，这种分层结构是一个最佳的选择。3 2 数据库的复制技术为了提高移动数据库系统的可用性和可靠性，需要一种关键的技术，数据复制技术 8 1 1 1 5 1 。即将数据库系统的数据存为多个副本，分别存放在不同设备中，使得用户可以在任何一个设备上对数据库的读写操作进行，即使这个设备处于断连状态。复制的优点非常明显。由于副本保存在移动设备上，在进行数据库操作的时1 2第一部分移动数据库系统综述候无需保持网络连接，这将节省昂贵的无线通讯费用。由于无线网络的带宽十分有限，用户不可能在每次执行事务时都等待与其他计算设备相连，有了本地副本，这个问题就不存在了。由于数据库事务在不同移动设备的不同副本上可以同时执行，这在很大程度上增强了系统的并发性，提高全系统的事务执行效率。对应于无线网络和移动计算设备的低可靠性，多个数据副本可以保证在任何一个或几个节点故障的情况下，系统仍然可以正常运行。但复制技术同样会产生很多新的问题，其中最主要的是一致性问题：如何保证多个副本问的数据一致性。如何保证在有限的系统开销和系统复杂性的前提下，在有限的网络和计算能力的支持下完成高效快速的复制问数据同步。为了保证使用复制技术的数据库的一致性，需要对一致性进行定义。对于用户来说，如果多副本的数据库的执行结果总是等价于单副本数据库的执行结果，这种等价性被称为单副本等价性( o n e c o p ye q u i v a l e n c e ) 。除此之外，多副本数据库系统还需要保证在各个副本上并发执行的事务的结果等价于所有事务在一个副本上串行执行的结果，这种特性被称为单副本串行性( o n e - c o p ys e r i a l i z a b i l i t y ) 。单副本串行性足比单副本等价性更强的约束，是否满足单副本串行性是检验复制数据库系统正确与否的标准。1 1 5 为满足单副本串行性约束，人们设计了各种各样的算法，主要有主副本法( p r i m a r yc o p ym e t h o d ) 、定额同意法( q u o r u mc o n s e n s u sm e t h o d ) 和可用副本法( a v a i l a b l ec o p ym e t h o d ) 三类方法。1 6 1主副本法：规定系统中某个节点上的副本为主副本，任何读写操作需要对主副本加锁以保证系统的可串行性。为提高效率，具体的读操作可以在对主副本加读锁后在本地副本上执行。由于主副本法是一个非对称算法，主副本的计算能力和通信带宽都要远大于普通副本。而在移动环境下，固定网络上的固定计算设备正好可以提供比移动计算设备大得多的计算能力和通信带宽。所以这种算法非常适合移动数据库系统。实际上多数移动数据库算法部是在主副本法基础上的扩充。在主副本法中，包含了一些重要的子算法，在移动数据库中经常用到的有a ) a s a p ( a s8 0 0 1 1a sp o s s i b l e ) 算法，即主副本上包含写操作的事务提交后，事务执行的结果作为一个独立事务发送给所有其他副本。b ) 增量文件( d i f f e r e n t i a lf i l e ) 算法，即各副本间只传递对主副本进行的改动，这种改动可能是多个事务执行后的结果。c ) 增量刷新( d i f f e r e n t i a lr e f r e s h ) 算法，即对副本数据进行更新是，只传递上次刷新后被修改的部分。在移动计算环境下，无线网络的限制要求我们尽可能的减少网络联通时间和传输的数据量，在这种环境下，增量文件算法和增量刷新算法可以提供非常好的性能定额同意法：这种算法使用一种投票的方法确定权限，每次数据库操作前要d b s 多版本并发的移动数据库的设计弓实现在所有副本范围内进行投票，只有获得一定数量节点的同意，操作才能够执行。在这种方法中，所有节点的地位是对等的，而且每进行一次操作都需要在每个节点问进行一次投票，网络通讯十分频繁，而且每个节点都需要参与其他所有节点的操作，对节点的计算性能要求也很高。而且，移动设备的低可靠性和频繁断连性也使得投票的计算问题很难解决。这些都与移动计算的要求相矛盾，所以在移动数据库系统中使用这个算法是不可行的。可用副本法：可用副本法指在保证网络强连接的条件下，每次只须存取一个或少量几个副本的方法。这种方法有最好的可用性。但移动计算环境中不可能提供各个节点问的网络强连接，这种算法所以不可能应用到移动数据库系统中上述复制算法都是建立在节点间保持强网络连接、节点有强计算能力、主机位置保持不变等假设的基础之上的，并不能够很好的适应移动计算环境的需求。所以必须对这些算法进行改进如上所述，定额同意法和可用副本法在根本上与移动计算模式相矛盾，所以新的算法必然是在主副本法基础上进行的改进。在主副本法中，读写操作需要对主副本加锁，这与需要支持断连状态下数据库操作的需求相矛盾，应该予以修改。而a s a p 算法会造成网络连接过于频繁，也应该被舍弃。增量文件法和增量刷新法有利于减小节点进的通信量，应该予以保留。由于全系统的锁不再存在，要求移动数据库系统在事务可串行化方面提出新的算法。在移动数据库系统中，应该抛弃保持系统实时一致的强一致性要求，改为保持系统的弱一致性，即允许系统在某些时刻有短暂的不一致，但通过同步可以使系统达到