【doc】实时数据库中基于时间戳的事务处理探讨

【doc】实时数据库中基于时间戳的事务处理探讨 实时数据库中基于时间戳的事务处理探讨 第18卷第2期 2004年6月 湖北汽车工业学院 JournalofHubeiAutomotiveIndustriesInstitute Vo1.18No.2 Jun.2004 实时数据库中基于时间戳的事务处理探讨 胡志慧,裘子煦 (湖北汽车工业学院计算中心,湖北十堰4420o2) 摘要:实时数据库系统中,事务的执行受到时间期限的约束.在 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 原有理论的基础上,对实时数据库系统中 的事务处理进行了研究,重点探讨了提交处理和并发控制两方面,并结合时间戳技术的思想,提出了一种新的设 计构思. 关键词:实时数据库;实际时间;事务处理时间;时间戳 中图分类号:TP391文献标识码:A文章编号:1008—5483(2004)02-0058-05 TransactionBasedontheTimestampinginRTDBS HuZhihui,QiuZixu (ComputerCenter,HubeiAutomotiveIndustriesInstitute,Shiyan442002,China) Abstract:Transactionsneedtomeetthedealineconstraintinreal-timedatabasesystem.Thepaper researchestransactionprocessinginRTDBSwithfocusonbothcommissionprocessingand concurrencycontro1.Onefeasibledesignandmethodarealsoaddressedbasedontheideaof timestamping. Keywords:real-timedatabasesystem;validtime;transactiontime;timestamping 实时数据库在现实生活中的应用越来越广泛.诸如电子商务,空中交 通管制,程控电话交换,电力调度 等应用都需要它的支持.然而实时数据库中还有解决许多悬而未决 问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 需要的精妙 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 .如其中并发控制 的处理.并发控制是任何多用户数据库管理系统(DBMS)必不可少的 组成部分.其作用是正确协调同一时 间内多个用户访问数据库的操作.以保证数据库的一致性和完整性. 实时数据库中的截止期和一致性不仅 有与传统数据库相同的逻辑一致性要求,同时也有强的时间一致性 (时间截止期)要求.传统的并发控制技 术能保证强一致性但不能很好的满足截至期要求.放松的可串行化 并发控制虽可更好地满足截止期.但牺 牲了一定的一致性.本文采用一种扩展时间戳算法对实时数据库并发控制进行探讨. 1实时数据库及其特征 1)与传统数据库的比较 一 个实时数据库管理系统(RTDBMS)也是一个数据库管理系统(DBMS),所以它也具有一般DBMS的 基本功能:永久数据管理(包括数据库的定义,存储,维护等);有效的数据存取(各种数据操作,查询处理, 存取 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 ,完整性检查);事务管理(事务的概念,调度与并发控制,执行管理);存取控制(安全性检验);数 据库的可能性(恢复机制).但传统DBMS的 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 目标是维护数据的绝对正确性,保证系统的低代价,提供 友好的用户接口.系统的性能指标是吞吐量和平均响应时间.它不考虑与数据及事务相联的定时限制.调 度与处理决策也不考虑各种实时特性. 与之相反,RTDBMS的设计目标首先是对事务定时限制的满足,即在有效时间内响应数据变化和完成 事务处理;其基本原则是:宁要部分正确而及时的信息,也不要绝对正确但过时的信息.系统性能指标是满 收稿13期:2004-02—27 作者简介:胡志慧(1980一),男,湖北荆州人,硕士研究生,从事网络数据库技术研究. 第18卷第2期胡志慧等:实时数据库中基于时间戳的事务处理探讨一59一 足定时限制事务的比率,它要求必须确保硬实时事务的截止期,必要时宁肯牺牲数据的准确性与一致性. 2)RTDB的定义 实时数据库就是其数据和事务都有显示定时限制的数据库,系统的正确性不仅依赖于事务的逻辑结 果,而且依赖于该逻辑结果所产生的时间.实时数据库系统(RTDBS:Real-TimeDatabaseSystem),是事务 和数据都具有定时限制或显式定时限制的数据库系统. RTDBS中数据的时间限制是通过事务对数据的处理时间来实现的,因此,又可将事务具有定时限制或 显式定时限制的数据库系统称为RTDBS.显然,RTDBS的正确性不仅仅依赖于计算的逻辑结果,还同时依 赖于逻辑结果的产生时间.实时并非就是”快”,也不一定就是ms级或ys级的定时限制.陕”固然重要,但应 恰到好处.因此”实时”意在用户可显示地施加所要求的时间限制,并能通过系统的时间识别与处理机制来 处理并保证或尽可能地保证满足与各种活动相关联的时间限制. 3)RTDB的数据特征 实时数据库中有一对基本的概念是实际时间和事务处理时间. 实际时间(validtime)指的是事件在现实世界中实际发生的时间,有时又称现实世界时间(real—wodd time)或真实时间(realtime),它可以是和很多的时刻和时间段的关联,是应用的发生的依赖.而事务处理 时间(transactiontime)是指在数据库中记录该事件的时间,又称系统时间(systemtime)或数据库时间 (databaSetime),它相对与应用事件独立,源自于系统时钟,是数据库中事务执行提交的时间. 在RTDB中,数据随外部环境状态的变化而快速变化,其值只在一定的时间内是”流行”的,过时则无效 了,故系统除了维护数据库内部状态(数据值)的正确性外,还必须同时维护内部状态与外部环境实际状态 的一致性.以及数据用来决策或推导新数据时在时间上的相互一致性. RTDB中的一个数据对象d由三个分量组成(dv,dtp,devi),它们分别为d的当前值,采样时间,外部有效 期(外部现实对象状态变化的时间间隔),有效期即自dtp算起dv有效的时间长度.对于RTDB中的每一个数 据对象d,有内部一致性,外部一致性和相互一致性特征. 内部一致性:dv满足预先定义的数据库内部状态完整性和一致性限 制,即传统意义下的数据正确性. 外部一致性:设dv为当前或检测时间,当且仅当(dv—dtp)<devi,则说d是外部一致的,即dv和对应的外 部现实对象的状态是一样的. 相互一致性:用来决策或导出新数据的一组相关数据称为一个相互一致集,记为R,其中的数据必 须尽可能地在一个允许的公共时间期内被采集(或导出),这个公共时间期就称为R的相互有效期,记为 Rmvi,对于R中的任两个数据d和d’,有Idtp—d’tpI~<Rmvi,则说R中的数据是相互一致的.外部一致性和相 互一致性都是关于时间的,可统称时间一致性.既是内部一致又是时间一致的数据才是正确的. 2实时事务的特征 由于实时任务往往有内部结构和相互之间的联系,传统的”ACID”的事务概念及模型对实时事务不适 合.RTDB事务表现出了许多不同的特征. 1)定时性 实时事务具有定时限制的特征,定时可以是绝对,相对或周期时间.在实时应用中,事务的定时性来源 于两方面:一是外部环境显式给出的反应时间要求,这时它典型地取施加于非周期事务的截止时间限制的 形式(截止期),如”若温度达到1000度,则在5秒内加冷却剂到反应 堆”;二是由于系统中的数据随时间变化 而转嫁来的(即由数据的时间一致性引起的),此时它往往取周期或定期性限制的形式,如”每5秒取样一 次”等. 实时事务的定时限制有多种,其中最重要的有: a)截止时间:实时事务完成的最后期限.它可以有硬,软,固之分.硬实时事务(HRT):具有硬截止时间 的事务,必须在其截止时间以前完成,否则将带来灾难性的后果,故到达其截止时间还不能完成的硬实时 一 60一湖北汽车工业学院2004年6月 事务必须天折.软实时事务(S:具有软截止时间的事务,应该在其截 止期完成,但超过其截止时间也还有一定意义(尽管不断下降),故软实 时事务到达其截止时间后不必立即天折它.固实时事务(FRT):一旦事务 到达截止期,则对系统失去意义,其价值为零.如图1所示. b)到达时间:事务在系统中生成的时间.它可以是可预报的,也可 以是不可预报的.图1实时事务分类描述 c)期望执行时间:估算在最坏情况执行时间.由于各种不可预报性因素,它很难做到准确,估算的最 坏情况执行时间可能与实际情况相差很大. 因此,在实时数据库中,定时性包括以下两方面的含义: a)定时限制.事务的执行具有显式的时限,如期限,截止时间等.因为控制系统要随时紧紧地跟踪被 控系统.它要求RTDB必须有时间处理机构. b)定时正确性.事务能按合适的时间要求正确执行.由于要求数据对于控制系统的各种决策活动随 时有效.所以需要权衡定时限制与数据一致性等多方面因素,提供合适的事务调度与并发控制算法. 2)相关性 实时数据库事务之间存在着各种关系,包括结构关系,数据与通信关系,时间关系等,这些关系带来了 事务间的各种相关性. 结构相关:来自于复杂事务模型的结构特征.用来建模复杂事务内部并发事务行为的一种约束.不同 的复杂事务模型有不同的结构相关性,但它们可以通过事务间的”执行依赖性”来定义,实时嵌套事务中基 本的事务依赖有: 子事务对父事务的开始依赖(BD):子事务开始前父事务已经开始; 父事务对于事务的提交依赖(CD):父事务提交前子事务已经结束(提交或夭折); 子事务对父事务的夭折依赖(AD):父事务夭折则子事务一定夭折. 数据相关:就是不同事务间的共享数据联系.除了传统意义下的”共享”概念,数据相关还包括如嵌套 事务模型中的数据继承,通信事务模型的数据通信,合作模型的数据交换,分裂与合并模型的数据”委托”. 每一事务都有一个与之关联(或它所使用)的数据集,两个事务间的数据相关性就表示它们的数据集的重 叠度. 行为相关:事务间的行为相关性是由事务的数据相关性及在共享数据对象上的交互作用而引起的.它 是由于在同一对象上不同事务操作间的同步所建立的一种间接相关性,而不象结构相关是直接的,通常用 事务的”冲突关系”来表示. 时间相关:是实时数据库事务所持有的,它表明事务的执行顺序或紧迫度,通常以”事务事件”来表示. 一 般而言,时间相关性分为两类:时序相关和带时限的时序相关.前者表明有关事务中相应事务事件发生 的时间顺序,后者是事务间带时限的时序相关. 3实时事务调度 时间戳技术是事务管理程序TM把系统中的时戳作为附加数据项加到事务所发出的每一个操作上.由 于系统时戳的唯一性(即某一时刻只有一个系统时戳)和可比性(根 据时戳产生的早晚可比大小),数据管理 程序DM就可以参照时戳的次序来执行事务的每一个操作,从而处理同步中的冲突,这就是基本原理. 下面以处理RW同步为例,说明时间戳技术是如何实现的(读写操作均带时戳TS).DM中的数据项x保存 了读操作Read(x)的最大时时戳R—timestamp(x)和写操作Write(x)的最大时时戳W—timestamp(). Read(x):首先比较的读操作的时戳和写时戳的大小,若读的时戳大,则输出读操作,并更新读时戳, 否则拒绝执行读操作,撤销该事务.TS>W—timestamp()? Yes:输出Read(x);R—timestamp(x)=maximum(TS,R—timestamD()) 第18卷第2期胡志慧等:实时数据库中基于时问戳的事务处理探讨二鱼二 No:拒绝Read(x),撤销发出本操作的事务. 同理对Write(x),则将X的写操作的时戳和读时戳比大小,有TS>R-timestamp(x)? Yes:输出Write(x);W—timestamp(x)=maximum(TS,W—timestamp(x)) No:拒绝Write(x),撤销发出本操作的事务. 同理可知WW同步,这里不再赘述. 从上述可知基于时间戳的的并发控制算法在传统的数据库中的时间戳算法是无死锁的,将时间戳算 法根据实时事务中数据模型的特点进行扩展. 实时数据库是比较注重实时性,从这个角度来说时间戳是比较适合于实时数据库的,为了满足截止期 的要求.对于提交每个实时事务的时间戳的可扩展为如下的三元tJ~(A,C,D),写入处理完之后,事务的时 间戳为三元~it(si,Xi,Di).其中Ai为事务的提交时间;C为事务的预测处理时间;为事务的截止时间;S为 事务的实际启动处理时间;X为事务的实际完成处理时间. 1)有保证调度 给定一组时实时事务M=f(Aj,Ci,Di)lc<~Dr-A,i=1,…n} 若存在一组实数S,1,…/7,,称f(,S,C,D),i=1,…n}是它的一个调度.如有 a)Ai?Si?D广Cf,i=1,…/7, b)[SiSl斗C],i=1,…/7,两两不相交 则称该调度为有保证调度. 2)理论基础 性质1(,Ci,D)与(Af,Cf,Df)存在有保证调度 充分必要条件是I]I—?cl斗q或QD广Aj?cl斗 性质2实时事务集合f(,C,D)lc~<Dc-A,i=1,…n}有保证调度 必要条件是max(D一D)一min(A1..?A)??. 性质3有两个实时事务(Al,C,D)与(,,I]I) a)P~=DFA?Cl斗C则有调度 最早启动sFA,Xf=sl斗CSj-~max(Xi,)=sJ斗 最晚启动Xj=E,=x广C,Xi=min(D,,)sx-Ci b)Q=D广AC,+Cf则有调度 最早启动=Af,xj=sj+cjSi=max(,Af)xFSf+C 最晚启动xDf,Si=Xc-CiX~=min(Df,s)x厂q 3)调度的灵活性 a)事务调度的排序:按到达时间排序;事务的截止时间排序;事务的宽松度排序R=D—A—C(其中R为 事务的宽松度) b)调度的策略选择:最早启动:最晚启动 c)三种任务排序原则形成三种算法: (A,D)以事务到达时间排序 (D,A)以事务的截止时间排序 (R,A)以事务的宽松度排序 例如有下列一组事务: T1(1,2,8)T2(2,3.5)T3(7,3,l1)T4(10,4,17)T5(15,5,25)T6(20,3,24) 先按以事务的宽松度排序为: T2(2,3,5)Ts(7,3,l1)T~(20,3,24)T4(10,4,17)Tl(1,2,8)T5(15,5,25) 对(T2T3)事务分析=11-2/>3+3按最早启动:T2(2,3,5)T3(7,3,10) 对(T2T6)事务分析P~-=24—2/>3+3按最早启 动:T2(2,3,5)T6(20,3,23) 一 62一湖北汽车工业学院2004年6月 对(T2T4)事务分析P#=17—2?3+4按最早启动:T2(2,3,5)T4(10,4,14) 对(T2T】)事务分析P=8—21>3+2按最早启动:T2(2,3,5)T】(5,2,7) 对(T2T5)事务分析P0=25—21>3+5按最早启动:T2(2,3,5)Ts(15,5,20) 用同样方法分析T]与T6,T4,T】,T5;T6与T4,T】,T5;T4与T】,T5;T与T5得到调度的结果为: T2(2,3,5),T】(5,2,7),T3(7,3,10),T4(10,4,14),Ts(15,5,20),T6(20,3,23) 从上述分析.这种方法使其既保持了无死锁的特点,使事务的执行按一定时间戳顺序执行,保证相对 的时间一致性和逻辑一致性.并且尽可能的满足了数据的实时性,及时性. 4结语 文中实时事务集合是实时数据库管理系统在周期性的时间片内的采集的一组事务集合,当情况在满 足事务集合为有保证调度情况.可以采用上述的方法可以尽可能的让实时事务处理都在截止期前完成,有 时宁愿牺牲事务的”绝对正确性”而得到及时部分正确的结果.为了当不满足有保证调度时,保证实时数据 库的性能,实时事务还应该考虑事务的硬,软,固属性,事务之间的相关性等因素来确定优先级.本文仅对 实时事务的并发控制作了一些简要论述. 参考文献: [1]KTorp,C.S.Jensen,R,T.Snodgrass.EffectiveTimestampinginDatabase 288. sEJ1.TheVLDBJoumal,1999,(8):267— [2]刘煜,蔡希尧.一种新的分布事务处理模型与协议[J].计算机工程与科学,2003,(10). [3]陈建荣.分布式数据库设计导论[M].北京:清华大学出版社,1992. [4]顾耀林.时间戳顺序在分布式并发控制中的应用[J].信息技术,2001,(11). [5]党德鹏,刘云生.一种新的实时事务并发控制方法[J].小型微型计算机系统,2002,(7). [6]刘英.实时数据库的事务处理[J].科技与经济,2002,(2). [7]万常选,刘云生,夏家莉.一种实时数据库系统的基于时间戳的多版本并发控制协议[J].计算机工程与应用,2001,(15).