（计算机软件与理论专业论文）并行实时数据库事务处理研究.pdf

华中科技大学硕士学位论文 摘要 现代数据库应用领域要求数据库系统既具有高性能的事务处理能力又能满足实 时应用需求。将并行数据库与实时数据库理论结合起来的并行实时数据库系统正好 能满足人们的需求。并行实时数据库系统不是传统的并行数据库与实时数据库在概 念、原理、技术和方法等各方面的简单拼凑。将实时机制引入并行数据库系统后， 系统的数据划分策略、查询优化机制、事务模型、事务特性、事务并发控制策略及 调度策略都发生了根本性的改变。 事务调度是所有数据库管理系统的核心功能模块，它对一个数据库管理系统的 性能有至关重要的影响。并行实时数据库系统中的事务具有并行性和实时性两方面 的特性：事务的并行性是指一个事务被划分成多个子事务，子事务被分派到不同的 处理机上并行执行；事务的实时性是指事务及其子事务都要在截止期内完成。并行 实时事务调度算法的设计应充分考虑这两个特性。a t s p 算法是一种基于事务优先级 的并行实时事务调度算法，它通过调节平衡因子a 的值决定事务调度算法侧重点： 偏重于并行还是偏重于实时。同时算法还考虑了实时事务的剩余执行时间、空余时 间等因素的影响，根据各种不同的情况采用了不同的优先级分派策略。 a t s p 算法具有高度的灵活性和优良的性能，是一个完全基于优先级的事务调度 算法，它没有考虑节点负载均衡问题和事务价值所产生的影响，这些问题是以后研 究工作的重点。 关键词：并行数据库系统；实时数据库系统；并行实时数据库系统； 优先级分派；并发控制；事务调度 华中科技大学硕士学位论文 _ - _ - - - - _ _ _ - _ - _ _ - _ - l _ _ i r l l _ _ _ _ _ _ 自l 目 _ t a b s t r a c t t h ea d v a n c e dd a t a b a s es y s t e m sa p p l i c a t i o na r e a sd e m a n dt h a tt h ed a t a b a s es y s t e m s h a v eb o t hh i g hp e r f o r m a n c et r a n s a c t i o np r o c e s s i n ga b i l i t ya n ds a t i s f yt h e d e m a n d so f r e a l t i m ea p p l i c a t i o n t h ep a r a r a l l e ir e a l t i m ed a t a b a s e s y s t e m ( p r t d b s ) t h a tc o m b i n i n g p a r a l l e ld a t a b a s es y s t e m ( p d b s ) t h e o r ya n dr e a l t i m ed a t a b a s es y s t e m ( r t d b s ) t h e o r y c a ns a r i s f yt h ed e m a n d so fp e o p l e t h ep r t d b si sn o ts i m p l ym a k i n gu po ft r a d i t i o n a l p d b sa n dr t d b si n c o n c e p t i o n ，p r i n c i p l e ，t e c h n o l o g y , m e t h o d a n ds oo n a f t e r b r i n g r e a l - t i m em e c h a n i s mi n t o p d b s ，t h e d a t a p a r t i t i o ns t r a t e g y , q u e r yo p t i m i z a t i o n m e c h a n i s m ，t r a n s a c t i o nm o d e l ，t r a n s a c t i o n p r o p e r t i e s ，c o n c u r r e n c y c o n t r o l s t r a t e g y a n d s c h e d u l i n gs t r a t e g yh a v ec h a n g e db a s i c a l l y t r a n s a c t i o ns c h e d u l i n gi sc o r em o d u l eo fa l ld b m s ，i tc a ne f f e c tt h ep e r f o r m a n c eo f d b m sg r e a t l y t h et r a n s a c t i o ni nt h ep r t d b sh a v eb o t h p a r a l l e l i s m a n dr e a l t i m e p r o p e r t i e s t h e t r a n s a c t i o n p a r a l l e l i s m i st h a tat r a n s a c t i o ni sd e v i d e di n t os e v e r a l s u b t r a n s a c t i o n ，e v e r ys u b t r a n s a c t i o n i s d i s p a t c h e d t oad i f f e r e n t n o d e ，t h e yc a ne x e c u t e p a r a l l e l l y t h er e a l - t i m ep r o p e r t i e so ft r a n s a c t i o ni st h a tt r a n s a c t i o na n di t ss u b t r a n s a c t i o n m u s tf i n i s hi nd e a d l i n et i m e t h ed e s i g n i n go fp a r a l l e lr e a l t i m e s c h e d u l i n ga l g o r i t h m m u s tt h i n ko ft h et w o p r o p e r t i e sc l e a r l y t h ea t s pa l g o r i t h m i sak i n do f p a r a l l e lr e a l t i m e s c h e d u l i n ga l g o r i t h mb a s e do np r i o r i t y t h e a t s pa l g o r i t h mc a na d j u s tt h eb a l a n c e p a r a m e t e r a t od e c i d et h ea l g o r i t h me m p h a s e s ，e m p h a s eo n p a r a l l e l i s mo rr e a l - t i m e t h e a t s pa l g o r i t h ma l s ot h i n k sa b o u tt h e r e m a i n i n gt i m ea n ds l a c kt i m eo fr e a l t i m e t r a n s a c t i o n ，i tu s e sd i f f e r e n tp r i o r i t ya s s i g ns t r a t e g yt od i f f e r e n ti n s t a n c e t h ea t s p a l g o r i t h mh a sh i g hp e r f o r m a n c e ，i ti sav e r yf l e x i b l ea l g o r i t h mb a s e do i l p r i o r i t yc o m p l e t e l y t h ea t s pa l g o r i t h md o e sn o tt h i n ka b o u tt h el o a db a l a n c i n ga n dt h e t r a n s a c t i o nv a l u ee f f e c t i o n ，t h o s ea r e e m p h a s e s o fo u rr e s e a r c hw o r kl a t e r k e y w o r d ：p a r a l l e ld a t a b a s es y s t e m ；r e a l - t i m ed a t a b a s e s y s t e m ； p a r a l l e lr e a l t i m ed a t a b a s es y s t e m ；p r i o r i t ya s s i g n ； c o n c u r r e n c yc o n t r o l ；t r a n s a c t i o ns c h e d u l i n g 华中科技大学硕士学位论文 l _ - - _ _ - _ _ - l i _ _ - _ - _ _ - _ l l _ _ - _ _ - _ _ - _ i _ _ - 目# 目t = = = 1绪论 1 1 并行数据库系统研究概况 进入九十年代以来越来越多的应用表明，传统的大型计算机系统缺乏支持高性 能联机事务处理和复杂查询操作的能力，当今数据库的规模急剧膨胀以及新的应用 领域不断出现和成熟，已经使传统的计算机达到了性能的极限。并行计算机系统的 出现为高性能数据库管理系统“1 的实现带来了希望。以并行计算机为基础的数据库系 统称为并行数据库系统。并行数据库系统的研究可以追溯到数据库机器的研究，数 据库机器的研究主要集中在专用硬件的研究上，由于磁盘与处理器之间的速度差别 及数据库机器硬件设计的高开销，这方面的研究受到了很大的限制，数据库机器的 研究基本失败了。随着通用并行计算机系统的出现，并行数据库系统的研究取得了 引人瞩目的进展，并行数据库系统已经成为并行计算机上的主要应用之一。 1 1 1 并行系统的特征 理想的并行系统应该展示两个关键特征”： 线性加速( 1 i n e a rs p e e d u p ) 使用n 倍多的硬件以i n 的时间完成相同的任务。 线性放大( 1 i n e a rs c a l e u p ) 使用n 倍多的硬件以同样的时间完成n 倍多的任务。 影响线性加速和线性放大的主要因素有三条： 启动时间( s t a r t u p ) ：启动并行操作所用的时间。 错开( s k e w ) ：各并行处理部件负担的原始数据量和工作量严重不均衡。 干扰( i n t e r f e r e n c e ) ：当访问共享资源时，每个进程都可以对其他进程构成影 响。进程越多，干扰越大。 线性加速比和线性放大率只是并行处理的理想目标。实际上，由于并行处理总 是隐含着如上所述的三个因素，在实际中很难达到上述目标。并行处理技术追求的 目标是接近线性的加速比。 华中科技大学硕士学位论文 鞠- _ - _ - l _ _ - l - 曩_ _ i | 蕾- i _ - _ _ _ - - _ 1 1 2 并行性分类 并行性的主要目的是提高系统的性能。使用多个处理机和系统部件一般可以增 加系统的吞吐率并缩短响应时间。 1 ) 按并行的粒度不同，可以分为查询问并行性和查询内的并行性。查询内并行 是存在于一个查询内部的并行，又可分为操作数间并行性和操作数内并行性。操作 数间的并行性是指查询中多个操作数之间的并行执行；操作数内的并行性是指一个 操作数内部操作的并行执行，它是粒度最小的并行。 2 ) 按并行进程之间的数据依赖关系的不同，并行性还可以分为水平并行性和流 水线并行性。水平并行性是指在不相交数据集上执行的并行操作。流水线并行是指 进程之间存在的“生产者一消费者”关系产生的并行。根据流水线同步方法的不同， 流水线并行又近一步分为同步流水线和异步流水线。在同步流水线中，消费者进程 必须等待生产者进程完全执行完成之后才能启动。在异步流水线中生产者和消费者 进程可以并发工作。 3 ) 除以上两种外还有程序并行性和数据并行性，程序并行性指不同代码的并行 执行，数据并行性与水平并行性同义。 1 1 3 并行数据库系统所要解决的技术难点 目前国内外的并行数据库系统都是基于无共享( s n ) 结构的数据库系统，它们都有 以下一些共同的技术难点需要解决。 1 ) 并行数据划分及放置。1 它要考虑的是如何将数据库的关系分布存放在各个 节点上，以便获得并行处理带来的最大加速比。 2 ) 数据偏斜问题“1 它是指由于数据在处理机上的分布不均匀而造成各处理机 工作时间的差别，从而降低并行处理的加速比。 3 ) 并行查询优化问题“1 并行数据库查询优化与传统的数据库查询优化有所不 同。后者只需要找到一个具有最小工作量的执行规划即可，而在并行数据库中，一 个具有最小工作量的执行规划可能有很强的顺序性，难以并行化。 4 ) 事务处理问题在并行数据库中要实现事务的a c i d 特性比传统数据库复杂 得多。目前研究较多的是如何提高并行查询速度，而在并行事务管理方面鲜有研究。 我们将在并行数据库事务调度策略方面进行一些研究和探讨。 2 华中科技大学硕士学位论文 _ - _ _ - - _ _ l _ _ - _ _ _ _ _ _ _ _ _ _ i _ l _ _ - _ _ _ _ - _ 1 2 实时数据库系统及其特征 实时数据库系统就是其事务和数据都具有显式的时间限制的数据库系统。系统的 正确性不仅依赖于事务执行的逻辑结果，还依赖于逻辑结果产生的时间”3 。近年来， 实时数据库系统受到了数据库和实时系统两个领域研究工作者的及大关注。数据库 研究工作者的动机在于利用数据库技术的特点和优点来解决实时系统中的数据管理 问题，实时系统研究工作者主要对实时数据库系统中的时间分配调度和资源分配算 法感兴趣”1 。 一个实时数据库系统应该具有两个方面的特征”1 ：时间一致性和定时性。其中时 间一致性是实时数据库系统的数据特征，而定时性主要是实时数据库系统的事务特 征。 1 ) 时间一致性在实时数据库系统中，由于其数据的值随时按照外部环境的变 化而频繁地改变，一个数据往往只是在某一特定的时间范围内有效。因而除了考虑 数据库内部状态的一致性之外，数据的一致性还必须和某一“时间有效期”相关联， 不能简单的认为当前最新的数据就是擐有效的数据，必须考虑被选数据与其它数据 的时间上的相互一致性问题。这就是实时数据库系统的数据特征，只有当一个数据 同时是内部一致和时间一致的，它才是正确状态。 2 ) 定时性定时性是事务的基本特点，事务的定时可以是绝对时间、相对时间或 周期时间。一方面它是由数据的时间一致性所引起的，这种定时性往往采取定期或 周期性限制形式；另一方面是由于物理世界施加于控制系统的反应时间要求，它典 型地采取施加于非定期事务的截止时间限制形式。 定时性包括两方面的含义： 1 定时限制 事务的执行具有显式的时间限制，如截止时间等。事务的正确性不仅依赖于逻 辑的正确性，也依赖于其执行时间的正确性。这是由于系统需要随时跟踪外部环境 而引起的。任何超过截止期限的事务是毫无意义的。 2 定时正确性 事务能够按照合适的时间要求正确执行。这是由于要求数据对控制系统的各种 决策活动随时有效而引起的，它要求权衡定时限制与数据一致性等多方面的因素， 3 华中科技大学硕士学位论文 _ _ - _ i i i _ i _ - l _ _ - - _ _ _ _ _ _ _ _ _ - l l _ _ t 提供合适的调度策略。 一个实时数据库系统可以看作是一个传统的数据库管理系统和一个实时系统的 融合a 但它不是两者的概念、机构、工具等的简单集成，实时数据库系统不仅要保 证事务传统的a c i d 特性，同时必须保证事务和数据的定时限制及时间一致性。 1 3 并行实时数据库系统研究意义及概况 随着社会的发展和科技的进步，数据库技术被应用到社会生产和生活的各个方 面。现代的许多应用领域如：军事、股票证券、银行系统、电力和数据网管理、电信 实时计费系统等，一方面要求维护海量的共享数据和控制知识；另一方面这些应用 活动具有很强的时阃性，都要求在一定的时刻或某一时间范围内采集、存取和处理 数据。这就要求我们找到一种既具有较大的吞吐量又能保证事务截止期的数掘库系 统，将并行数据库与实时数据库结合起来的并行实时数据库系统正好能满足这些应 用需求。 我们称以并行为体系结构具有实时事务调度能力的数据库系统为并行实时数据 库系统。并行实时数据库并不是并行数据库与实时数据库在概念、原理、技术和方 法等各方面的简单拼凑，它需要对一系列问题进行研究与决策，包括数据的存储组 织与结构：事务的优先级分派、调度和并发控制的协议与算法；通信协议与算法； 查询优化算法等等。 关于并行数据库及实时数据库已经有大量的研究工作者做了不少的研究工作， 并开发出了许多著名的原型系统：并行数据库系统中，国外比较著名的有美国威斯 康幸大学开发的g a m m a ”1 系统及美国m c c 公司研制的b u b b a “”系统，国内主要有中 国人民大学的p b a s e 1 系统及华中科技大学研制的p a r o “”系统：实时数据库的研 究始于8 0 年代，1 9 9 2 年美国贝尔电话实验室的d k b a r c l a y 等人研制了第一个 专用实时数据库管理系统。随后十多年来，各国的学者就有关实时数据库系统 的设计和实现技术、崩溃恢复、并发控制、事务调度等方面作了一些研究。目 前有些实验原型系统如l i p - r t d b m s 、h i p ：a c 、r t - g e n e s i s 、s t r i p 及a r t s i i 等。 目前的研究大多就并行数据库和实时数据库两个方面单独进行的，关于两者的 结合国际上鲜有研究。国内，华中科技大学现代数据库与信息系统科研组最早丌始 华中科技大学硕士学位论文 了并行实时数据库系统的独创性研究。在存储组织、查询优化、事务调度等方面取 得了一批理论和实践成果，发表了多篇具有创新性的科技论文。 1 4 本文的主要研究内容 本文我们以正在开发研制的并行实时数据库系统p r t s i 为例对并行实时数据库 的事务特性及其调度算法进行了深入细致的讨论。第一章介绍了并行实时数据库的 基本概念及其研究概况；第二章分析了并行数据库系统的硬件体系结构，并给出了 并行实时数据库系统的体系结构图：第三章讨论了并行实时数据库的事务模型、事 务特性及事务调度策略；第四章提出了一种并行实时数据库事务调度算法，并给出 了相应的性能评价及结果分析；第五章为结束语，对全文所作的工作进行概括和总 结。 5 华中科技大学硕士学位论文 2 并行实时数据库的体系结构 2 1并行数据库的四大体系结构 并行数据库系统的发展与体系结构密切相关。由于存在许多构成并行硬件系统 的方法，选择什么样的并行硬件结构最适合并行数据库系统的并行处理，是数据库 研究领域一直在争论的问题。理想的并行硬件应该有一台无限快的计算机，并有一 个宽带无限宽和容量无限大的内存，这在技术上是不可能的。现在的问题是如何用 若干处理速度有限的处理机及存储容量有限的内存构成一台速度和容量尽可能快和 高的计算机。1 9 8 6 年，美国人m s t o n e b r a k e r 提出了三种用于构造并行数据库系统的 硬件结构模型，它们分别是：全共享结构( s h a r e d e v e r y t h i n g ) 、共享磁盘结构 ( s h a r e d d i s k ) 和无共享结构( s h a r e d - n o m i n 曲“”。1 9 9 3 年美国学者g r a e f e 提出了第四 种并行结构，称为分层并行结构( h i e r a f c h ys y s t e m ) 。这四种结构的示意图如图2 1 所 示。 1 ) 全共享结构( s e ) 如图2 1 所示。在s e 结构中，系统中所有的处理机都直接 连接到一个全局内存和共享磁盘系统，它们之间由高速互联网连接。多处理机之间 的通信通过共享主存储器直接进行。这种结构又叫共享内存结构( s h a r e m e m o r y - s m ) 。 2 ) 共享磁盘结构( s d ) 如图2 2 所示。在s d 结构中，系统中的所有处理机都 有一个私有内存。但都通过高速互联网连接到一个共享磁盘系统。这种结构又叫做 c l u s t e r 结构。 3 ) 无共享结构( s n ) 如图2 - 3 所示。在s n 结构中，系统中没有任何共享资源， 每个处理机都有自己的私有内存和磁盘系统。处理机之间的通信完全靠高速互联网 实现。这种结构实际上就是被称作大规模并行处理结构的m p p ( m a s s i v ep a r a l l e l p r o c e s s o r s ) 系统。 4 ) 分层并行结构( h s ) 如图2 4 所示。分层并行结构是融合了s e 和s n 两种结 构特点的并行结构，在分层结构中有许多超级节点由高速互联网连接。每个超级节 点实际上都是一个s e 结构。这种结构存在两种层次的并行性，因而称为分层并行结 华中科技大学硕士学位论文 构。分层并行结构是一种更加通用的结构，若在分层并行结构中只保留一个超级节 点，就得到了s e 结构；若超级节点中只配置一个处理机，就得到s n 结构。 共享内存 图2 1s e 结构 图2 2s d 结构 超缀节点 图2 4 h s 结构 并行数据库系统硬件体系结构是这个研究领域的工作者一直都在讨论的问题， 每一种结构都有热心的支持者。s n 结构被认为是并行数据库最理想的并行结构，它 具有如下一些特点： 1 ) s n 结构通过最小化共享资源来最小化由资源竞争带来的系统干扰。 2 ) s n 结构具有高可扩展性，其处理机的个数可以扩展到成千甚至上万，而不 增加处理机间的干扰。 华中科技大学硕士学位论文 3 ) s n 结构在数据库查询过程中需要在通信网路上进行的数据通信量较少。 4 ) s n 结构在复杂的数据库查询处理和联机事务处理过程中可达到线性加速比。 考虑到以上因素，许多数据库专家都认为，在并行数据库设计中最好一开始就采 用s n 结构，实际上已有很多实验室和商品化的并行数据库系统采用了s n 结构： t e r a d a t ac t 4 , t a n d e m c m , n c u b e ，g a m m a “s l , b u b b a ，a r b r e “”等。 除了s n 结构外。s e 结构是目前应用最为广泛的并行处理系统。因为s e 结构 具有编程难度低、通信效率高和易于到达负载平衡的优点，而且s e 结构不需要在 处理机之间进行数据迁移，其缺点是系统干扰大“”。x p r s “、d b s 3 1 和v o l c a n o ” 都是基于s e 结构的并行数据库的例子。s d 结构也是被普遍采用的并行结构，它的 特点是系统扩充简单，具有容错和容灾能力。h s 结构的特点是具有高度的灵活性， 随着多处理机服务器的普遍使用和高带宽局域网技术的进步，以集群形式存在的h s 结构具有明显的优势。一般来讲，在处理机数目较少的并行系统中，s e 结构的性能 超过s n 和s d 结构，但在高端并行数据库应用中，首选是s n 结构。 鉴于s n 结构的优点及现有的实验条件，我们在选择体系结构时也采用s n 结构。 2 3 并行实时数据库体系结构 并行实时数据库系统是能够进行实时事务调度的并行数据库系统，其实质是在并 行数据库系统中引入了实时调度机制。由于我们采用的并行体系结构是s n 结构，在 s n 结构中引入实时调度机制后反应在体系结构上变化是增加一前端控制节点，此节 点负责全局事务的分派及调度，各处理节点均为一个单独的实时数据库管理系统， 它们只负责处理前端控制节点所分派的子任务，并将结果返回给控制节点。其系统 结构图如图2 5 所示。 其中前端控制节点由事务产生器、事务队列、事务分派嚣、全局数据处理器、全 局数据字典等部分构成。各部分的功能如下： 事务产生器：负责任务的接收及事务的生成。 事务队列：负责保存达到的事务，使其按一定的规贝q 进入事务队列中。 事务分派器：将各事务划分成子事务分派到各处理节点上。 全局数据管理：负责数据查询、收集等工作。 华中科技大学硕士学位论文 数据字典：用于保存全局数据索引。 高速网络 处理节点p f 圈2 5 并行实时数据库体系结构 各个处理机节点上都有一个单独的r t d b m s ，它由事务调度器、局部事务管理 器、局部数据管理器、优先级分派器、并发控制器、局部数据库组成。各部分的功 能如下： 事务调度器：用于决定应投入运行的事务。 局部事务管理器：用于处理b e g i n 、a b o r t 、c o m m i t 、r o l l b a c k 、e n d 等事务原语。 局部数据管理器：用于局部数据存取组织。 9 华中科技大学硕士学位论文 优先级分派器：给事务分派优先级。 并发控制器：多事务的并发控制管理。 局部数据库：局部数据的存放。 各个处理节点之间的通信通过前端控制节点完成，该系统模型的简要工作原理如 下：当用户发出的请求任务到达前端控制节点后，事务产生器根据用户的请求产生 相应的事务并进入队列，事务分派器根据事务所操作的数据范围查询数据字典表确 定所要访问的处理机，事务分派器根据这些信息将该事务划分成一系列子事务分派 到各个处理机节点上执行，各个处理机节点执行完相应的子任务后将结果返回给前 端控制节点，由数据处理器搜集组装最后的执行结果将其返回给用户。 2 4 系统及平台简介 为了实现上述功能，我们找到一种成熟的开放源码的数据库管理系统，通过修 改其中部分功能模块的代码以满足我们的需要。p o s t g r e s q l 。”及m y s q i 1 是目前最流 行的两种开放源码的数据库管理系统，p o s t g r e s q l 的设计非常复杂、代码量巨大，而 m y s q l 的设计更为精简一些且在功能上也能满足我们的要求，因而我们选用m y s q l 作为各处理机节点上的d b m s 。 m y s q l 是一个真正的是一个快速、多线程、多用户和强壮的s q l 数据库管理系 统。它有各种版本能支持u n i x 、o s 2 及m i c r o s o f t 等各种平台。m y s q l 是以一个客 户机朋艮务器结构的实现，它由一个服务器守护程序m y s q l d 和很多不同的客户程序和 库组成。m y s q l 主要目标是快速、健壮和易用。它最初被开发出来的目的是为了支 持g b 级数据量的存储并且速度更快。 m y s q l 具有如下一些特点： 使用核心线程的完全多线程。这意味着它能很容易地利用多c p u 。 能够支持c 、c + + 、e i f f e l 、j a v a 、p e d 、p h p 、p y t h o n 、和t c la p i 等各 种语言。 利用一个优化的一遍扫描多重连接( o n e - s w e e pm u l t i - j o i n ) 非常快速地进行连 接( j o 蛐。 在查询的s e l e l 了和w h e r e 部分支持全部运算符和函数。 华中科技大学硕士学位论文 i - _ _ _ _ _ l l - _ - l _ l - _ - i i i _ 自# l 自= = 口 可以在同一查询中混用来自不同数据库的表。 具备索引压缩的快速b 树磁盘表。 每个表允许有1 6 个索引。每个索引可以由1 1 6 个列或列的一部分组成。最 大索引长度是2 5 6 个字节( 在编译m y s q l 时，它可以改变) 。一个索引可以使 用一个c h a r 或v a r c h a r 字段的前缀。 多种列类型：1 、2 、3 、4 、和8 位组长度的有符号，无符号接数、f l o a t 、 d o u b l e 、c h a r 、v a r c h a r 、t e x t 、b l o b 、d a t e 、t i m e 、d a t e t i m e 、 t i m e s t a m p 、y e a r 、s e t 和e n u m 类型。 通过一个高度优化的类库实现s q l 函数库并且像它们能达到的一样快速，通 常在查询初始化届不应该有任何内存分配。 一个非常灵活且安全的权限和口令系统，并且它允许基于主机的认证。口令 是安全的，因为当与一个服务器连接时，所有的口令传送被加密。 一个非常快速的基于线程的内存分配系统。 全面支持j s o 8 8 5 9 1l a t i n l 字符集 由上的一些基本特征可以看出，m y s q l 在功能上是非常强大的，其最大的优势 在于其开放源码，系统中错误可以被及时发现并修改，系统的功能每天都在加强， m y s q l 已经成为互联网上最成功的数据库管理系统之一。 考虑到m y s q l 源码用c ，c + + 语言编写及现有的实验条件，我们选用操作系统为 m i c r o s o f t w i n d o w s 2 0 0 0 。并行实时数据库系统平台由5 台p c 机组成，其中一台为前 端控制节点，另外4 台为数据处理节点，它们通过普通的局域网进行连接。用户只 与前端控制节点打交道，其它节点对用户来讲是完全透明的。它们作为一个整体为 用户提供服务。 1 l 华中科技大学硕士学位论文 _ _ l - _ l l - _ _ l _ _ - 。- _ - l - - _ _ - - - - _ _ - _ i i , _ _ - _ - 目日= 目_ i l - = = = = l l = 3 并行实时数据库的事务处理 3 1 并行数据库事务调度 在并行数据库系统中，事务调度策略对其性能有至关重要的影响。传统的事务 调度策略可分为两大类：一类是与当前的系统状态无关的调度策略，另一类必需使 用当前的系统状态信息。与系统状态无关的调度策略最常用的有： 1 1 先进先出调度( f i f o ) ： 事务按照到达的顺序被放入就绪队列中，当队首的事务需要访问处理器和1 o 资 源时，它发出锁请求，如果请求获得批准则该事务进入处理状态，否则该事务进入 阻塞队列，无论何种情况该事务都被从就绪队列中移走，下个队首元素发出锁请求。 2 ) 最小事务优先调度( s 1 日： 这种策略按照事务大小进入就绪队列( 小事务在前) ，任何时候有事务到达时，总 是最小事务发出锁请求，其处理方式与先进先出调度策略类似。在此种策略中以事 务的大小作为就绪队列的排列标准，而不是到达时间。对于一个给定的数据库管理 系统来讲它在某个时刻只能处理一定数量的事务，数量的多少要根据事务的大小及 系统种锁的总数目决定。 在以上两种策略中如果事务的数量及锁的数日超过了系统的瓶颈值，会严重影 响系统的性能，为了克服这个缺点，又有人提出了与系统状态有关的调度策略，针 对以上的两种与系统状态无关的调度策略，我们列出两种”： 1 ) 适应性先进先出调度( a _ f i f o ) 与f i f o 调度策略相对应，这种调度策略在f i f o 的基础上加上一个限定条件， 就绪队列中的队酋事务能发出锁请求仅当当前持锁的活动事务数量小于系统中瓶颈 数量n 。 2 ) 适应性最小事务优先调度( a _ s t f ) 其队首元素能发出锁请求的条件同适应性先进先出调度。其中 n - - a * ( d b s i z e a v g t r a n s i z e ) ，d b s i z e 为数据库大小，a v g t r a n s i z e 为事务的平均大小，d 为 0 、1 之间的参数可动态的调节以达到最优性能。并行数据库系统中，每个子事务访 华中科技大学硕士学位论文 问数据量大小可能不同，因而访问偏斜可能发生，而且每个处理节点的处理速度也 有所差别，因而数据偏斜也可能发生，s c s t 调度策略“”提出了同步子事务完成时间 的思想，通过同步各个子事务的完成时间，减少不同事务的子事务之间的数据竞争， 从而提高了系统的并发度。事务调度的负载平衡问题是我们所面临的一个巨大挑战， 由于我们所采用的体系结构为s n 结构，每个结点能够完成独立的计算功能，为了充 分发挥系统的并行功能，提高其效率，每个结点上所承担的工作量应该趋于相同，文 献 2 6 】中关于并行数据库负载平衡问题作了一些探讨，我们不在此详述。 3 2 实时数据库事务处理 3 2 1实时事务的特性 传统的事务是原子的、平坦的数据库操作序列。而实时事务由于其应用的复杂 性，传统的具有a c i d 特性的事务模型对实时事务而言已不再适用。实时事务表现 出许多新的特性。3 ： 1 ) 结构复杂性 事务内部和事务之间可能存在着分层、嵌套、分裂、合并等合作关系。 2 ) 功能替代性 一个实时应用通常由若干任务组成，而一个任务有时可以通过不同途径来实现。 一个应用建模为一个事务，一个任务则建模为一组功能等价的子事务，称为该任务 的替代集。若一个替代集中的子事务之一能成功执行，则该任务是可完成的。若对 应一个事务的所有任务可完成，则该事务是成功的。功能替代导致了事务执行路径 的不确定性，即一个事务成功执行的路径依赖于执行过程中子事务失败的发生，即 使有些子事务失败了，事务仍可能顺利提交。 3 ) 结果补偿性 由于实时事务结构复杂性及功能替代性，事务的执行过程不确定，一个子事务 的执行直到它提交时还不能确定它是否需要。若一个子事务提交后，发现它是不需 要的，这就需要将状态还原到它提交之前，这种还原通过补偿事务来实现。对于一 个事务，若存在能抵消它提交后所产生的所有影响的事务，则称其为可补偿的，否 则为不可补偿的。 华中科技大学硕士学位论文 4 ) 语义相关性 实时数据库事务之间存在着各种关系，包括结构关系、数据与通信关系、时间 关系等，这些关系导致了事务问的各种相关性。 结构相关它来自于复杂事务模型的结构特征，用来建模复杂事务内部并 发事务行为的一种约束。它包括嵌套事务的结构相关、分裂事务结构相关、 合并事务的结构相关、通信事务的结构相关及合作事务的结构相关。 数据相关它指不同事务间的共享数据联系。每一事务都有一个与之关联 的数据集，两个事务问的数据相关性就是表示它们数据集的重叠性。它包 括嵌套事务数据相关、分裂事务数据相关、合并事务数据相关、通信事务 数据相关及合作事务数据相关。 行为相关它是由事务的数据相关性及在共享数据对象上的交互作用而 引起的。不像结构相关是直接的，它是由于在同对象上不同事务操作间 的同步所建立的一种间接相关性，通常用事务的冲突关系来表示。 时间相关它是实时数据库所特有的。它表明事务的执行顺序或紧迫度， 通常以事务事件来表示。时间相关包括时序相关、带时限的时序相关。 5 ) 执行依赖性执行依赖性是实时事务的另一重要特性。它由结构复杂性和语 义相关性引起。事务尤其是嵌套的父子事务在执行时存在着彼此间的各种依赖关系。 它包括开始依赖、提交依赖、夭折依赖、排他夭折依赖、传递夭折依赖、传递提交 依赖、成功依赖、失败依赖及外部依赖。 3 2 2 实时事务的分类 事务的分类是按照事务在某一方面的特征，将其划分成不同的集合，使同一集 合中的事务具有该方面共同的特征，从而可以统一地进行专门性的处理。实时事务 一般有如下几种典型分类： 1 ) 按使用数据的方式分类有如下几种 只写事务唧r d t c - o n l yt r a n s a c t i o n ) 只读事务( r o a d o n l yt r a n s a c t i o n ) 更新事务( u p d a t et r a n s a c t i o n ) 这种分类有助于设计和改造并发控制方案。 1 4 华中科技大学硕士学位论文 2 ) 按事务超截止期对系统带来的影响可分为 硬事务( h a r dt r a n s a c t i o n ) 事务超过截止期会导致灾难性后果，它对应于安 全危急性活动。 软事务( s o f tt r a n s a c t i o n ) 事务超过截止期仍有一定的价值，但随着时间地 增长不断下降，直到某一时刻其价值降到零，此后一直为零。 固事务( f i r mt r a n s a c t i o n ) 事务一旦到达截止期，其价值立刻降为零，此后 一直为零。 这种分类有助于设计事务优先级分派及调度策略。 3 ) 按功能分类 数据接收事务记录现实世界的状态或发生的事件到数据库中。它是简单 的只写事务；为了保持数据库的外部一致和跟踪记录，它应是短的、周期 的，且是应被立即执行的硬实时事务。为了保证其定时限制的满足，它可 能引起数据库一致性的破坏。 数据处理事务与传统的数据库事务类似，它用来恢复已违反了一致性的 数据库状态。 控制事务引起现实世界中有关活动的执行事务。这种事务很短并且通常 是硬实时的，它还可以作为数据处理事务的子事务而被调用，且本身也可 以触发子事务。这种分类有助于并发控制与恢复。 4 ) 按到达时间分类 周期事务事务以一定的周期循环地到达和被执行。 非周期事务由外部事件或内部事件动态驱动 零星事务偶尔一次执行，具有非预测性。 3 2 3 实时事务的调度及其正确性准则 实时事务调度的主要目标是满足事务的时限要求，尽可能保证事务在其截止期 限内完成。它包括对多事务的优先级分配及事务的并发控制两方面，为了解决系统 中硬件资源和数据的竞争问题实时数据库系统为每个事务设定了一个优先级，大 多数实时事务的调度都是基于优先级的，事务优先级分派通常有基于截止期分派策 略和基于价值的分派策略。我们先介绍常用的优先级分派策略： 华中科技大学硕士学位论文 _ ii ii iii i i _ _ _ _ _ _ _ _ _ _ _ _ _ l 目_ _ _ _ | _ _ _ _ 目自目 目# 目_ 1 ) 截止期最早优先啪删( e d f - e a r l i e s td e a d l i n ef i r s t ) 事务的优先级依赖于其截止期，截止期最早者优先级最高。其缺点是它可能让 那些快过截止期的事务获得最高优先级，而这些事务并不能在截止期内执行完，这 显然是不适合的。 2 ) 可达截止期最早优先( e f d f e a r l i e s t f e a s i b l ed e a d l i n ef i r s t ) 具有最早的可达截止期者优先级最高。它是e d f 的一个改进版本，所谓一个事 务t 的截止期是当前时问“可达”的，是指t 从当前时间算起可以在截止期前完成。 它是增加了事务能在截止期前完成这个限制条件后的e d f 算法。 3 ) 最早放行优先( e r f e a r l i e s t r e l e a s ef i r s t ) 该策略将最高优先级指派给具有最早“放行”时间的事务。所谓放行时间是事 务可以开始执行的最早时间，通常即指事务到达的时间。若按事务到达时间来讲， 它就是先来先服务( f c f s ) 策略。e r f 策略的优点是简单，而主要缺点是根本没有 考虑事务的截止期，这样它有可能优先放行那些到达早但紧迫程度低的事务，这对 于实时系统显然不适合。它适合于截止期自放行时间起都是定长的事务。 4 ) 空余时间最短优先( l s f - l e a s t s l a c k f i r s t ) 事务t 的空余时间s 。是指推迟t 的执行而仍然能满足其截止期的可推迟时间量估 算。l s f 与e d f 及e f d f 两者都不一样它考虑了当前时间与剩余执行时间估算，随着 事务的执行，其优先级动态上升。该策略也有类似于e d f 的缺点，同样可限制s o 即只考虑可达截止期情形。 5 ) 价值最高优先( h v f - h i g h t e s t v a l u e f i r s 0 每个事务有一个价值函数，其值最大者优先。其中价值函数可以根据实际需求 构造。 6 ) 价值密度最大优先( v d f - v a l u e i n f l a t e d d e a d l i n ef i r s 0 价值密度是指事务完成时的期望价值与实现该价值所需计算量的比值越大优先 级越高。期望价值可用v t 表示，实现该价值的计算量用d t 表示，则p t = v 训) t 。 7 ) 相对价值密度最大优先( v r d f - v a l u e - i n f l a t e d r e l a t i v ed e a d l i n ef i r s t ) 相对价值密度最大优先同v d f 相似，它用相对截止期代替绝对截止期，其优先 级可以表示如下p t = v t ( d r a t ) ( a 吓、d 叶、v t 分别为事务t 的到达时间、截止时间、 1 6 华中科技大学硕士学位论文 价值) ，p t 越大优先级越高。 8 ) 桶算法优先级分派( b a ) 该算法考虑事务的价值和截止期两个因素，它由一个桶机制策略维护，桶机制 中有一个事务价值链表，当一个新的事务t 到达时，t 被插入到价值链表中记其位 置为p o s t ，t 按照其在链表中的位置放入大小为n u m b u c k e t s 的桶数组中，n u m t r a n s 为系统中并发执行事务数，桶分派策略。“用如下公式完成： d 一 p o s t + n u m b u c k e t s n u m t r a n s 】( n u m t