嵌入式移动实时数据库中客户端缓存一致性研究硕士学位论文.docx
《嵌入式移动实时数据库中客户端缓存一致性研究硕士学位论文.docx》由会员分享，可在线阅读，更多相关《嵌入式移动实时数据库中客户端缓存一致性研究硕士学位论文.docx（55页珍藏版）》请在冰点文库上搜索。
嵌入式移动实时数据库中客户端缓存一致性研究硕士学位论文
硕士学位论文
嵌入式移动实时数据库中客户端
缓存一致性研究
AThesisSubmittedinPartialFulfillmentoftheRequirements
fortheDegreeofMasterofEngineering
TheResearchofCacheConsistencyofMobileClientinEmbeddedMobileReal-timeDatabase
Candidate：
ZhichengLi
Major：
ComputerSoftwareandTheory
Supervisor：
ProfessorLuYansheng
HuazhongUniversityofScienceandTechnology
Wuhan430074,P.R.China
June,2007
独创性声明
本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。
尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。
对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。
本人完全意识到，本声明的法律结果由本人承担。
学位论文作者签名：
日期：
年 月 日
学位论文版权使用授权书
本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：
学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。
本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。
本论文属于
保密□，在_____年解密后适用本授权书。
不保密
。
（请在以上方框内打“√”）
学位论文作者签名：
指导教师签名：
日期：
年 月 日 日期：
年 月 日
摘要
随着移动通信技术的迅速发展和使用，许多计算结点已经可以在自由移动的过程中保持与网络的连接。
于是人们迫切需求能在任何时候、任何地点访问任何数据。
随着嵌入式和移动计算技术的发展逐步成熟，嵌入式移动实时数据库系统（EMRTDBS）正开始受到越来越多的研究人员的关注。
客户端缓存技术作为关键技术一方面可以进一步提高移动数据库系统的访问性能与可伸缩性。
另一方面可以支持客户端的断接操作，提高移动数据库的可用性。
客户端的一致性问题研究是缓存技术一个重要研究内容。
保持客户端缓存的一致性就是要保持客户端缓存与服务器数据的一致性。
用什么方法来保持客户端缓存与服务器数据的同步更新，如何在重连后保持缓存与服务器数据的一致性，如何更好的支持在客户端执行的强一致性事务，减少事务延迟，使上行的消息数量最小。
一种改进的基于异步广播的缓存失效策略ASI采用异步广播方式，即服务器上的数据更新时立即广播缓存失效报告，客户端接收到失效报告以后维护本地缓存，保持与数据库的一致性。
在MSS的代理上缓存所有客户端的失效消息，这样客户端即使断接很长时间，也不需要丢弃整个缓存。
周期性的发送控制消息CM来解决异步广播情况下不能够确定下一次异步广播的时间的问题，提高事务的执行速度。
基于异步广播的缓存失效策略ASI能够有效的解决客户端缓存的一致性问题。
实验结果表明，ASI比同步广播的缓存失效策略API表现更为出色。
关键词：
嵌入式移动实时数据库，缓存一致性，失效报告，异步广播
Abstract
Withthefastdevelopmentofmobiletelecommunication,manycomputingnodescanmovefreelykeepingconnectionwiththenetwork.Sopeopleurgentlywanttovisitanydataatanytimeandanyplace.Withembeddedandmobilecomputingtechnologydevelopsgraduallymature,EmbeddedMobileReal-timeDatabasesystem（EMRTDBS）hasbeenahotfield.ClientdatacachingtechnologyasakeytechnologyofEMRTDBSistofurtherenhancethemobiledatabasesystemperformanceandscalability.Otherwise,Clientcachingtechnologycansupportdisconnectionsoftheclient,improvetheavailabilityofthemobiledatabase.Clientconsistencyresearchisoneofthemostimportantissuesofcachetechnologyresearch.
However,formaintainingclientcacheconsistency,thecacheddatamustconsistentwiththosedatastoredintheserver.Themainjobistomaintaindatasynchronizationbetweentheclientandtheserverwhenthedataintheserverisupdated.Aneffectiveschemewillsupporttheprolongeddisconnectionoperation.Thealgorithmsmustachievegreatimprovementsoftransactionlatencyandminimizesthenumberofabortedtransactions.
TheproposedschemeASIusesasynchronousinvalidationreport（call-backs）tomaintaincacheconsistencyi.e.reportarebroadcastbytheserveronlywhensomedatachanges,andnotperiodically.Theclientusestheinvalidationreporttomaintaindataconsistency.ThehomeMSSmaintainsforeachMCadatastructurewhichstoresthelatesttimestampforeachdataitemcachedbyMC.MCcancontinuetouseitscacheevenafterprolongedperiodsofdisconnectionfromthenetwork,withouttheneedofdiscardingtheentirecache.TheserverbroadcaststheControlMessage（CM）periodically.Guaranteescanbegivenaboutwhenthisreportwillbesentandhenceguaranteescanbegivenforthewaitingtime.
ASIisaneffectivecachemaintenancescheme.WecompareproposedalgorithmstothealgorithmbasedonsynchronouscacheinvalidationschemecalledAPI.ExperimentalresultsshowthesuperiorityofASI.
Keywords:
embeddedmobilereal-timedatabase,cacheconsistency,
invalidationreport,asynchronousbroadcasting
目录
摘要I
AbstractII
1引言1
1.1研究背景1
1.2移动计算环境及特点1
1.3国内外研究现状2
1.4本文主要研究内容及组织结构3
1.4.1论文的主要研究内容3
1.4.2论文的组织结构3
2嵌入式移动实时数据库的系统模型及关键技术4
2.1嵌入式实时数据库的系统模型4
2.2嵌入式实时数据库系统的关键技术5
2.2.1数据复制与缓存5
2.2.2数据广播技术9
2.3小结11
3移动客户端的缓存技术12
3.1移动客户机缓存的子集描述12
3.2缓存的工作机制13
3.2.1客户端缓存数据的初始化13
2.2.2客户端缓存的三种工作状态14
3.3联机状态15
3.3.1联机事务处理15
3.3.2缓存的更新16
3.4脱机状态16
3.4.1查询事务处理16
3.4.2更新事务处理18
3.5集成状态19
3.5.3暂时事务处理19
3.5.2缓存的更新20
3.6小结20
4一种改进的基于异步广播的缓存失效策略21
4.1相关研究21
4.2一种改进的基于异步广播的缓存失效策略23
4.2.1数据结构23
4.2.2描述24
4.3小结27
5原型系统实现及实验28
5.1原型系统的总体构架28
5.1.1服务器28
5.1.2MSS28
5.1.3移动客户端29
5.2性能分析与比较29
5.2实验与结论30
5.2.1实验环境30
5.3.2实验结果与分析32
5.4小结34
6总结与展望35
6.1总结35
6.2展望35
致谢37
参考文献38
致谢6
1引言
1.1研究背景
随着移动通信技术的迅速发展和使用，许多计算结点已经可以在自由移动的过程中保持与网络的连接。
于是人们迫切需求能在任何时候、任何地点访问任何数据，这使得原来基于有线网络和固定主机的分布式数据库不再适应，因而移动数据库技术使应运而生。
新的应用对移动环境下的事务处理提出了新的需求，如实时交通信息管理系统、海上导航系统及股票交易系统等，该类应用普遍要求在移动环境下实现实时事务处理。
随着嵌入式和移动计算技术的发展逐步成熟，嵌入式移动实时数据库系统（EMRTDBS）正开始受到越来越多的研究人员的关注。
一般认为嵌入式移动实时数据库系统是指支持移动计算或某种特定计算模式的实时数据库管理系统，它通常与操作系统和具体的应用集成在一起，运行在嵌入式或移动设备上。
嵌入式实时移动数据库技术涉及数据库、实时系统、分布式计算以及移动通信等多个学科，已成为数据库技术发展的一个新方向。
1.2移动计算环境及特点
目前已进入以网络计算为中心的时代，人们迫切需求能在任何时候、任何地点访问任何所需数据，而正在迅速发展并逐渐成熟的移动通信技术与移动计算机的结合为之提供了手段。
可以预见，未来的绝大部分移动计算机都将配备以无线网络为主的移动联网设备，以支持移动用户访问网络中数据的需要。
这将是一种更加灵活、复杂的分布计算环境，人们称之为移动计算（MobileComputing）。
移动计算系统是一个动态的分布式系统，网络中节点之间的连接动态变化，不依赖于一个固定的网络结构。
许多分布式系统中的问题解决方法不能应用于移动计算领域。
移动计算环境与基于固定网络的传统分布式计算环境相比，具有以下一些主要特点：
1）移动性。
2）频繁断接性。
3）网络条件多样性。
4）网络通信的非对称性，下行链路与上行链路的通信带宽相差很大。
5）移动计算机的电源支持时间有限。
6）与固定网络相比可靠性低。
7）规模的可伸缩性。
由于移动计算环境的上述特点，使得传统的分布式实时数据库技术不能或不能有效地支持移动计算环境。
因此，嵌入式移动实时数据库技术，即支持移动计算环境的分布式实时数据库技术，己成为目前分布式数据库研究的一个新方向。
1.3国内外研究现状
数据库技术总是与计算环境的一定发展阶段相适应，新的计算环境和需求促成数据库技术的形成和发展。
计算环境从集中式、分布式、网络环境到日前深受瞩目的移动计算环境MCE（MobileComputingEnvironment）和普遍化计算环境PCE（PervasiveComputingEnvironment）等多种计算环境。
在分布计算的基础上，计算环境进一步扩展包含为各种移动设备、具有无线通信能力的服务网络，构成了移动计算环境。
随着移动计算环境发展，支持多特征的嵌入式移动数据库系统成为当前数据库领域中的一个新的研究热点。
数据缓存是一种重要技术，可以提高数据的利用率和减少读取延迟，特别在低宽带和频繁断接的移动计算环境中显得特别重要。
关于缓存一致性的维护问题，国内外已经进行了广泛深入的研究，其中缓存失效广播技术由于考虑到无线通信的不对称性，充分利用了带宽较宽的下行数据通道，而收到了众多研究人员的青睐。
由于移动数据库可以支持用户随时随地访问各种数据，因此将会成为未来信息社会中的主要技术之一。
为了适应这一变化，世界上几家著名的大型数据库软件公司，如Oracle，Informix，Sybase等都纷纷推出了各自的移动计算解决方案和产品。
我国在上个世纪九十年代对移动数据库就开始了研究，并取得了许多成果。
中国人民大学已经成功研制出“小金灵”嵌入式移动数据库管理系统，并在很多行业进行应用。
长沙国防科技大学在这方面也取得了丰硕的成果。
华中科技大学、东北大学、复旦大学、浙江大学、中国科学院软件研究所等单位也取得了许多成果。
1.4本文主要研究内容及组织结构
1.4.1论文的主要研究内容
针对嵌入式移动实时数据库客户端一致性问题，本文首先讨论了客户端的缓存技术，给出了缓存的描述和工作机制，总体上给出保持客户端缓存一致性的方法。
提出了一种改进的基于异步广播的缓存失效策略，该策略主要是保持客户端缓存与服务器数据的同步更新，维护客户端与服务器的数据一致性。
在MSS上设置代理保存所有客户端的失效消息，这样当客户端经过任意长时间期的断接后，重连时不需要丢掉整个缓存区，通过MSS上的失效消息来验证缓存数据的有效性，从而可以减少上行消息数量，提高系统响应速度。
周期性的发送控制消息CM来保证事务等待提交的时间，从而减少事务执行的延迟时间，提高整个系统的性能。
1.4.2论文的组织结构
本文共分六章来介绍研究内容。
第一章为概述，介绍课题的研究背景及意义，对移动计算环境进行了评述，分析了嵌入式移动实时数据库的国内外研究现状。
第二章讨论嵌入式移动实时数据库的系统模型及关键技术，关键技术主要介绍和分析了数据复制与缓存技术和数据广播技术。
第三章就客户端的缓存技术进行了探讨，介绍了缓存的工作机制，总体上说明缓存是如何保持的一致性的。
在第四章中，提出了一种改进的基于异步广播的缓存失效策略ASI。
第五章给出ASI的原型系统实现及性能分析，主要与传统的同步的缓存失效方法进行实验分析比较。
最后对全文的研究工作进行总结和展望。
2嵌入式移动实时数据库的系统模型及关键技术
2.1嵌入式实时数据库的系统模型
嵌入式移动实时数据库的目的就是有效地支持移动计算环境中的各种数据使用，满足在任意地点任意时刻访问任意数据的要求。
移动实时应用的根本特性是其事务具有移动性和定时特性，数据具有定时限制[1]。
在上述移动计算环境的基础上，建立一个嵌入式移动实时数据库的系统模型如图2.1。
在系统模型中，移动数据库由两部分节点组成：
1）固定部分：
数据库服务器位于固定节点上，每个数据库服务器维护一个本地数据库LDB（LocalDB），服务器之间由可靠的高速网络连接在一起，构成一个传统意义上的分布式数据库系统。
在固定部分还有固定主机FH，可作为LDB的客户机。
另外还有位置服务器位于各个MSS上，对单元中的客户的位置进行管理。
2）移动部分：
移动部分有移动客户端MC，它作为固定部分—分布式数据库的客户，移动主机的CPU处理能力和存储能力相对于服务器来说非常有限，具有移动性。
按CPU的处理能力，将MC分为两类，一类为具有一定数据处理能力的MC，在这类MC上，有一个RTDBMS，可以利用缓存或复制数据（RepDB）进行数据库操作；另一类不具有数据处理能力，只是作为一个“哑终端”（DumbTerminal）或I/0设备，必须借助它所在单元的数据库服务器进行数据处理。
移动计算以及其具有的特点对传统的分布式数据库技术提出了新的要求和挑战，一个理想的移动数据库系统应当实现以下四个目标：
1）可用性和可伸缩性（scalability）：
在避免系统不稳定性的同时提供可用性和可伸缩性。
2）移动性（mobility）：
允许MC在网络断接的情况下访问或更新数据库。
3）可串行性（serializability）：
支持满足可串行性的并发事务的执行。
4）收敛性（convergence）：
使系统总能收敛于一致状态。
对于嵌入式移动实时数据库的研究，目前主要集中在移动环境下事务模型、数据复制和缓存、数据广播、位置相关查询、移动客户机故障恢复、实时事务处理、实时故障恢复等方面。
在上述研究方向中，更为关注复制/缓存技术和数据广播技术的研究，因为这两项技术与客户端缓存的一致性问题紧密相关。
下面介绍在这两个方面有的关键技术和研究成果。
2.2嵌入式实时数据库系统的关键技术
2.2.1数据复制与缓存
复制与缓存的主要目的是提高数据库系统的可用性、可靠性以及访问性能。
传统的复制与缓存技术都是客户机和服务器之间是经常保持连接的，并基于这个前提来维护一致性。
这在移动计算机环境中是不适用的，因为断接是移动计算机的一个显著特点。
文件系统复制与缓存技术的研究较深入，如下是一些代表：
1.Coda系统是第一个支持断连的文件系统[2],Coda系统主要负责确定移动用户缓存哪些对象，如何保持缓存与服务器的同步。
每个Coda客户机上都有一个缓存管理器Venus,Venus采用乐观缓存策略，它工作于三种状态：
收集（hoarding）、仿真（emulation）和再集成（reintegration）。
在保持连接时，Venus处于收集状态，它能够访问服务器上的数据，并收集在可预期的断接期间可能需要的数据。
在断连时，Venus进入仿真状态，此时它基本代理了服务器的作用，并将在缓存数据上的操作记录在日志中，最后在客户机重连时，Venus根据日志记录，将缓存数据与服务器上的数据重新同步，并对发生的各种操作冲突进行清除。
2.Honeyman等人在文献[3]中进一步将移动计算机的连接情况分为四种形式，即连接、弱连接、只读和断连，分别适用于网络带宽和可靠性从高到低的环境，针对每种连接状态，分别研究了相应的缓存策略。
3.SpyUtility是Tait等人开发的一种半自动化工具[4]。
和Coda不同的是：
Tait希望在他们的关于文件预取的工作的基础上自动预测一个应用（而不是用户）的工作集[5]。
4.Seer系统[6,7,8]是自动预测收集数据，是基于寻找用户过去访问的文件之间的语义关系来确定应收集的数据，它的工作原理是建立在用户行为的语义局部性之上。
文件被按照语义距离而捆绑在一起，语义距离的远近表明了它们之间关系的密切程度。
5.文献[9]提出了低开销自动数据收集算法，它根据用户的访问历史来推测不同数据之间的逻辑关联，然后根据数据之间的关联程度把数据对象分成相互独立的组，再推断连时最有可能访问的簇。
6.Saying等人在文献[10]中把数据挖掘（datamining）技术引入到数据收集研究中来，并采用关联规则（associationrules）来描述访问模式和指导预测将来访问的数据，它是一个与应用无关的通用自动数据收集算法，完全通过用户的访问历史来猜测将来的访问。
数据收集在数据库系统中变得非常复杂，有如下一些原因[11]：
1）在文件系统中，收集的数据项的大小是文件，与之对应的是关系和类扩展（对面向对象DB）。
但是，这样的粒度不太好，收集的单位越小（如元组/对象或者是元组/对象的一部分）则越有意义和更好的性能。
2）在数据库系统中依据过去的关系推断将来的依赖关系比在文件系统中推断依赖关系要困难。
发现相关联的文件是容易的，因为它们有同构的组织。
一般而言，同一目录下的文件关系比其它目录下的文件关系要密切。
3）一个文件系统的用户通常仅需要有限的文件数据（整个文件系统的一小部分）就可以完成其任务。
数据库的用户查询一个问题可能需要涉及大部分数据库，这意味着大量的数据必须收集以便支持断连操作。
移动数据库中复制与缓存技术的现有研究主要有：
1.文献[11]提出了预测算法，通过分析某一些客户机过去查询的最好捕获数据的存取模型（这些片段很可能在断连时被存取），总结这些片段的大小（收集片段的大小与移动计算机的Cache大小有关）。
每个关系可以看成是一个垂直片段的联合（对每个属性而言）和同一时间内水平片段的联合（一组元组）。
依据移动计算机过去存取的历史从每个关系中选择非常相关的垂直和水平片段，仅这些片段的交集将被收集。
分布式数据库中垂直分片段的算法是努力测量这些属性的亲近关系，以便放这些属性在同一垂直片段中。
但文献[11]中提出的方法是找到通常是哪些属性一起存取，哪些不是一起存取，垂直片段就与这些属性一致，被看作收集单元。
依据访问情况对片段进行记分和计算权重，最后依据权重来收集片段。
2.在复制方面，传统的复制技术可以适用，但在某些应用中，由于关键用户的频繁移动而造成静态复制策略难以达到满意的性能，因而提出了对动态复制策略的需求。
O.Wolfson在文献[12]中提出了动态复制的分布算法。
在一个分布式系统中，读数据非常频繁时，就应该广泛的复制数据。
这样可以提高本地的读命中机率，减轻服务器的负担；如果是写数据非常频繁时，就应当减少广泛复制的数据，否则就会降低写数据的速度和增大开销。
该算法能够根据各个结点上数据项的读写模式的变化而动态地改变复制布局，使之分别在代价与时间上趋于最优化。
但它们只能处理单一数据项的复制问题。
3.文献[13]中对上述方法进行了扩展，采用滑动窗口算法，设滑动窗口中可以保存K个读/写请求，在K个请求中，如果读请求的数量大于写请求的数量，则就给移动用户MC分配一个副本；结果写请求的数量大于读请求的数量，则就收回在移动用户MC的副本。
因此，分配模式是依据读/写请求的次数动态改变，该文详细讨论了基于连通模式和基于信息模式下的开销。
但他们仍只考虑对一个对象的复制，而且指定移动计算机与服务器是长期保持连接。
4.文献[14]详细分析了数据复制技术在移动计
升级会员 