基于动态规划算法的分布式实时数据库并发控制模型

基于动态规划算法的分布式实时数据库并发控制模型 一种基于动态规划算法的分布式实时数据库并发控制模型 林小静 薛永生 任仲晟 巢时刚 陈华昌 (厦门大学计算机系，福建，厦门，361005） 1(lovebysea@126.com) 本文在应用于分布式实时数据库系统中的DHP-2PL协议基础上，提出价值函数和动态规划算法，解 决了在并发事务多的系统中，事务优先级如何合理地分配问题，并在确保硬实时事务能在其截至期内完成 的前提下，改善DHP-2PL中即将提交的低优先级事务被重启，或低优先级事务被多次重起及无用重启等状 况，从而提高系统性能。 分布式实时数据库 实时事务 DHP-2PL 并发控制 价值函数 动态规划 Concurrency Control Model Based On Dynamic Programming for Distributed Real-Time Database System Lin Xiaojing Xue Yongsheng Ren Zhongsheng Chao Shi-gang Chen Hua-chang (Computer Science Department, Xiamen University, Xiamen, 361005, China) Abstract: In this paper, we give an algorithm combining Heuristic Function and Dynamic Programming ideology, based on the DHP-2PL protocol which used in distributed real-time database system. The algorithm presented solves the problem that how to assign priority to transactions reasonably. And it avoids multiple restarts of transaction with low priority and nonsense restart of transactions in DHP-2PL protocol without affecting hard-real-time transaction’s completion before its deadline, which improves system performance. Key words: Distributed Real-Time Database System Real-Time transaction DHP-2PL Concurrency Control Heuristic function Dynamic Programming 系统产生灾难性后果的事务；软实时事务，指超过 截止期，对系统的作用会大幅度降低，但不会对系1 引言 统产生负面影响的事务。RTDBS的系统性能指标是 满足定时限制的事务的比率，它要求必须确保硬实近几年来，随着移动电话网络，电子商务交易时事务的截止期，必要时宁肯牺牲数据的准确性与网络，证券交易系统等大规模实时数据库系统一致性；在此前提下，软实时事务满足截止期的比（RTDBS）和分布式实时数据库系统（DRTDBS）率相对较高，但要100％满足截止期很难或几乎不[2]应用的推广，对RTDBS以及DRTDBS的研究引起了。 可能越来越多的关注，其中对DRTDBS的研究尤为突出。 DRTDBS是建立在RTDBS的基础之上，其各场 RTDBS通常定义为对事务的完成时间有明显地或节点都是一个局部的RTDBS。其既具有DDBS截止期(Deadlines)的数据库系统。其 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 目标首先的特征，又具有RTDBS的特征。因此，其系统性能是对事务定时限制的满足，其设计的基本原则[1]指标应包括网络传输代价和全局事务中满足定时是： 限制的事务比率两个部分。故而，DRTDBS中实时事宁可要部分正确而及时的信息，也不要绝对正确但 务的并发控制是一个十分重要的问题，它的好坏直过时的信息。RTDBS中的事务分为硬实时事务和软 接关系到系统性能的优劣。 实时事务。硬实时事务，指超过截止期未提交会对 本研究得到福建省自然基金 (A0310008)和福建省高新技术研究开放 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 重点项目 (2003H043) 资助。 硕士研究生，主要研究方向为数据仓库，数据挖掘，分布式数据库等。 教授，主要研究方向为数据库理论与应用、分布式数据库、 数据仓库、数据挖掘、网络技术等。 硕士研究生，主要研究方向为数据仓库，数据挖掘，分布式数据库等。 [6]本文将介绍常用的RTDBS和DRTDBS并发控这样，低优先级的全局事务的执行制模型——HP-2PL协议和DHP-2PL协议，并提出了代价将会大幅度的增加，且多次的重启必然会给整 传输的负担。一种新的并发控制模型，它在改进系统性能方面起个系统通讯带来重大的负担，同时也使子场地开销 了一定的作用。 增加。同时还可能出现这种无用重启，即被重启的 事务已无法在其截止期内完成了，这样的重启将会 引起系统性能的抖动，因为重启后的事务将有可能 2 RTDBS 和 DRTDBS中的并发控制模型 会导致另一个事务的重启，以致另一个事务也无法 在截止期内完成。在DHP-2PL中，还有可能出现2.1 高优先级两段锁协议(HP-2PL协议) 高优先级的事务重启正在提交的低优先级事务的[3]高优先级两段锁协议（HP-2PL）主要是应用情况,这就造成系统资源的浪费。此外，由于系统的 于RTDBS中的并发控制。该协议是建立在2PL协资源总是有限的，当同时并发的事务过多时，要 议的基础之上的。2PL协议的主要思想是要求并发100％满足截止期很难或几乎不可能，必然会存在 执行的多个事务在对数据进行操作之前对数据进低优先级事务无法在截止期内完成的情况，那么如 行加锁，并且每个事务中的所有加锁操作都必须在何在同时并发的事务之间选择，用有限的资源，得 第一个解锁操作之前执行。HP-2PL协议在此基础到最高的系统效率就是值得我们研究的一个问题。 上引入了优先级的概念。在这个协议中，事务的初因此，我们在DHP-2PL的基础上引入动态规划算始优先级是根据事务的最后期限和事务的紧迫性法。 而定。然而，真正的优先级是把开始的时间印追加 到初始优先级形成的。当事务并发执行时，高优先 级的事务将优先对所需数据项加锁，而低优先级的3 一种新的并发控制模型 事务将被重新启动，从而使得高优先级的事务得以 3.1 引入实时事务的价值 优先执行。同时，由于时间印在不断增加，被迫重 启的事务的优先级就随之不断提高，从而初始优先3.1.1 实时事务的时间参数 级低的事务并不会总被冲突时初始优先级高的事 1． 截止期DL（T），事务能取得最大价值的前提下务所重启。由于在HP-2PL中引入了事务重启机制， 提交的最晚时间。 故采用HP-2PL协议可不必引入死锁检测机制。但 2． 关键性分类：按事务超过截止期未完成对系统在HP-2PL协议里存在这样的问题[4]带来的影响分类，实时事务分为三类： ：低优先级事 A． 硬实时事务：超过截止期未完成会导致恶务的重新启动将会增加系统的开销，即低优先级事 果，为必须在截止期前完成的事务。 务的执行代价将会增加，同时整个系统的性能也会 B． 软实时事务：超过截止期还有一定的价值，降低，这将可能会导致更多的事务错过它们的截止 但会不断下降，直到0。不会导致恶果。 期。 C． 固实时事务：超过截止期其价值立即为0。 2.2 分布式高优先级两段锁协议 实际上，固实时事务为软实时事务的特例。 [5][6]3． 事务估计执行时间E（T）。 分布式高优先级两段锁协议(DHP-2PL)是 4． 事务开始时间：B（T），事务开始执行的时间。 HP-2PL协议在分布式环境下的拓展，主要应用在 5． 事务已执行时间PDRTDBS中。在该协议中，每个局部节点都有一个（T），截止t时刻，事务Tt锁调度机制，该机制负责调度对该节点的数据对象已投入运行的时间。 的加锁请求。当事务要访问某节点的数据对象时，6． t时刻事务空余时间S（T）=D（T）-（t + E（T）t它通过该节点的锁调度机制来对它所需的数据对 -P（T））。 t象进行加锁。当该数据对象已被其它事务加锁时， 就要按优先级来比较，低优先级的事务将被迫重3.1.2 实时事务的价值函数定义 启，释放锁，由高优先级事务获得锁。 1：事务T在t 时刻的价值函数V（T）t但是，在DRTDBS 中,一个分布式实时事务对应=C（T）（W*（t-B（T））+W*P(T)） 12t有多个参与事务和一个协调事务,一个事务的重启令W=W=1；C（T）=50，若T为硬实时事务，12可能包括多个参与事务的夭折, 这样一方面会由C（T）=1，若T为软/固实时事务。 于多个参与事务的夭折而浪费大量的系统资源, 我们将软实时事务和固实时事务都视为超过另一方面协调事务和参与事务的通讯会加重网络截止期就没有任何价值，从而不区分这两种事务的 2 C（T）（均设为1），以方便讨论。 -t） max 1.Value(t+i-max（E(T))）+?V(T)(j=j~j)表1j1j123.2 动态规划算法 示在t+i时刻，若有事务集TS（TS={T，T，…，（）1j11j1+1间，i =1~DL3.2.1 问题描述 T}）获得锁,执行完并成功提交，系统得到的总价1j2 值。 某时刻t，节点中有同时需要访问某数据项的 其中j事务序列T,T,…,T，序列中每个事务都有其预计为读事务序列中截止期=t+i的事务下12n2 执行时间E（T标。若没有读事务的截止期=t+i，则Value(t+i-max）和截止期DL（T）。我们对每个ii （E(T事务都根据价值函数计算其价值，事务在其截止期)）)+?V(T)(j=j->j))= Value(t+i-1-max1j1j12内提交，则系统获得其价值，否则，系统收益为0。（E(T)）)+?V(T)(j=j->j)，j为截止期=t+i-1的1j1j122读事务可以同时获得锁，而写事务，只能有一个事读事务。以此类推。 务获得锁。由于允许多个读事务同时获得锁，我们2.Value(t+i-E(T))+V(T)表示在t+i时刻，若2k2k引入事务集概念。 T执行完成，并提交，系统得到的总价值。其中，2k2：事务集TS为一个或多个同时获得锁、k为写事务队列中截止期=t+i的事务的下标。若没访问数据的读事务的集合，或为一个写事务。E（TS）有写事务的截止期=t+i，则定义为事务集中所有事务中预计执行时间最长的Value(t+i-E(T))+V(T)=Value（t+i-1）。 2k2k事务的预计执行时间。 3.Value（t+i-1）表示在t+i时刻没有事务提交，以下，我们讨论的最优序列均为事务集序列。 系统得到的总价值。 选取当前时间到比较三种情况，得到该时刻最优选择。 有递归关系如下： DL,MAX(DL(T))为一个时间段。 maxi,1~niValue（tt）=-? if tt tt >t。(tt为时间参数) 2n12max Y最后递归得到Value（DL为事务集） ）即我们所求的系统预nmax 期可得到的最大价值。 在t+E（YDL）到的时间内，在除了Y之11max 3.2.4 结果构造 外的事务中选取执行的事务队列以得到最大的价 值。否则，设Y’-Y’为该子问题的最优解，则执由于我们只需要返回事务执行序列的第一组2n 行Y’执行事务集，故使用一个数组a[t]，t为时间，存放-Y’序列系统得到的价值比执行Y-Y序列2n2n t时刻得到最优子序列的最先执行的事务集，可由得到的价值更大。于是加上Y1，有执行Y，Y’-Y’12n 算法递归得到。从而，a[DL序列系统得到的价值比执行Y~Y序列得到的价值]即我们所求的t时刻1nmax大，与Y的最优选择 。 ~Y序列为原问题最优序列矛盾。 1n 从而，该问题具有最有子结构性质。 3.2.5 算法描述 3.2.3 递归关系定义 首先，将Tlist中的事务分到读事务与写事务队 列中并按截止期降序排列，同时计算每个事务的价首先，将请求锁的事务按读事务和写事务分成 值V（T两个队列，并按照事务的截止期排序。 ）。（为讨论方便，我们用符号Tlist表示请ij 令读事务队列为：T求锁的事务队列。） ，T，…，T，写事务11121m Value（time） 构造最优执行事务队列算法 队列为：T，T，…，T。其中，m，n分别为同21222n 1 Value（t）=0 时申请锁的读事务和写事务的个数。 2 V于是对t+i时刻有三种情况如下：（t为当前时=Value（time-1），a=a[time-1] 11 3 3 从写事务队列读取队首元素T ，Tlist，执行动态规划，得到2k22 4 若D（T重启占有锁的事务集后系统预期能得到的最大价）V,则V=V，E=E 价值函数的定义中，当T为硬实时事务时，我33max3max3max 12 V们让C（T）取50，这样大幅度加大硬实时事务的=V,a=a[D（T）-E] 33max31m 价值，确保了其在截止期前能被调度，获得锁并且 13 V=max{V,V,V}，根据选择结果，决max123 完成提交。 定a[time]=a或a或者a。 123 t-B（T）表示事务从开始执行到当前t时刻的 14 return V max 时间，P（T）表示事务投入运行的时间。一个事务t3.3 引入动态规划算法的DHP-2PL并发控制已执行时间越长，离开始执行时间越久，越接近提 交时刻，其重启代价就越大，而根据价值函数计算模型 得到的该事务的价值也越高。这样运行上述算法， 该并发控制模式的主要思想为：当一组访问同求得不重启更优的概率就越大，从而解决前面提到一数据项的事务抵达时，首先用价值函数计算每个的DHP-2PL中即将提交的低优先级事务被重启，事务的价值。若该数据项未被锁住，则调用动态规或低优先级事务被多次重起及无用重启，浪费大量划算法，得到该组事务的最优执行序列，并将锁分系统资源以及加大网络通讯量等问题。 配给序列中最先执行的事务集；否则，由动态规划对于已经不可能在截止期内提交的事务，动态算法分别求解重启与不重启占有锁的事务集的情规划算法保证了其不会在最优执行序列中，该事务况下所可能得到的最优系统性能，并做比较，若不不可能得到锁，从而解决了DHP-2PL协议中无用 重启的性能更高，则该事务集将继续执行，否则，重启和系统抖动的问题。 重启这组事务，释放锁，并将锁分配给动态规划算在并发事务过多的系统中，不可能所有事务都法中求得的在重启占有锁的事务集的情况下的最能在截止期前提交。此时，动态规划算法能在这些优执行序列中应最先执行的事务集。 并发的事务之间做出选择，使当前预期的系统性能算法如下： 达到最高。 1 若该数据未被加锁，则 综上，该算法引入价值函数概念和动态规划算 2 调用动态规划算法，求得最应得到锁法，使得节点每次分配锁时，能做出当前时刻最优的事务集 的决策，提高系统的性能。由于动态规划算法的复 3 该事务集获得锁 杂性，该算法会使系统开销有所增加，但综观之， 4 若该数据项被某事务集加锁，则 该算法在分布式实时事务并发控制领域中有一定 5 Tlist的应用价值。 =申请锁的事务集 1 6 t=t-该事务/事务序列剩余执行时间（t1 为当前时间,下同） 7 参数t，Tlist，执行动态规划，得到4 结束语 11 不重启占有锁的事务集的情况下系统预期能得到 的最大价值V DRTDBS是数据库领域的一个重要分支，至今max1 8 Tlist为止，已有多种用于DRTDBS的并发控制模型，本=申请锁的事务序列?占有锁的2 文所提出的并发控制模型就是在DHP-2PL基础进事务集 行改良的一种，它主要用于解决在并发事务多的系9 t=t 2 4 统中， 事务优先级如何合理地分配，使得预期的 系统的性能达到最高。针对该模型中诸如价值函数 的定义、参数设置的优化、结合加锁粒度的考虑以 及DRTDBS中网络通讯状况等一些不可预知因素 的综合考虑等方面我们还可做许多的有益工作。 参考文献 [1]刘英，王志坚，尹燕敏，实时数据库的事务处理.科技与经济.2002. [2]刘云生，李国徽，卢炎生，实时数据库系统结构. [3] A.Thomasian. Performance limits of two-phase locking[C]. Proceedings of the IEEE Seventh International Conference on Data Engineering. 1991 [4] Abbott,R., and Garcia_Molina,H. Scheduling real-time transactions: A performance evaluation[J]. ACM Transactions on Database Systems. 1992,17(3) [5] Kam-yiu Lam, Tei-wei Kuo, Wai-Hung Tsang, and Gary C.K Law. Concurrency Control in Mobile Distributed Real-time Database Systems[J]. Information Systems. 2000, 25(4) [6] V.C.S.Lee, K.Y.Lam, and B.Kao. Priority Scheduling of Transactions in Distributed Real-time Database[J]. Journal of Real-time Systems 1998, 15(1) [7]李国徽，王洪亚.分布式实时数据库并发控制.小型微型计算机系统.2003.VoL24(6) 5