Priority Scheduling of Transactions in Distributed Real-Time Databases

One of the most important issues in the design of distributed real-time database system (DRTDBS) is transaction scheduling which consists of two parts: priority scheduling and real-time concurrency control. In the past studies, mostly, these issues are studied separately although they have a very close interaction with each other. In this paper, we propose new priority assignment policies for DRTDBS and study their impact on two typical real-time concurrency control protocols (RT-CCPs), High Priority Two Phase Locking (HP-2PL) and Optimistic Concurrency Control with Broadcast Commit (OCC-BC). Our performance results show that many factors, such as data conflict resolution, degree of data contention and transaction restarts, that are unique to database systems, have significant impact on the performance of the policies which in turn affect the performance of the real-time concurrency control protocols. OCC-BC is more affected by the priority assignment policies than HP-2PL owing to the late detection of conflict. In the design of priority assignment policies, we have found that neither the purely deadline driven policies nor data contention driven policies are suitable for DRTDBS. Our proposed policy, the Mixed Method (MM), which considers both transaction timeliness and data contention, outperforms other policies over a wide range of system parameter settings.     

Transaction Scheduling in Distributed Real-Time Systems

Inthis paper, we study the performance of using optimistic approachto concurrency control in distributed real-time database systems(RTDBS). The traditional optimistic approach suffers from theproblem of unnecessary restarts. Transaction restarts can significantlyincrease the system workload and intensify resource and datacontention. In distributed environments, the complexity of thesystem and the high communication overhead exacerbate the problem.Therefore, the number of unnecessary restarts is the determinantfactor that affects the performance of optimistic approach indistributed RTDBS. When optimistic approach is extended to distributedenvironments, a number of issues resulting from the increasedcomplexity and communication overhead have to be resolved. Inthis paper, a new real-time distributed optimistic concurrencycontrol (DOCC) protocol with dynamic adjustment of serializationorder (DASO), called DOCC-DA is proposed. This protocol can avoidunnecessary transaction restarts by dynamically adjusting theserialization order of the conflicting transactions. Therefore,resources can be saved and more transactions can meet their deadlines.In the DOCC-DA protocol, a new distributed circular validationscheme is included to facilitate transaction validation in distributedenvironments. The performance of the DOCC-DA protocol has beenexamined in detail by simulation. The results showed that theperformance of the DOCC-DA protocol is consistently better thanthat of other protocols.     

移动实时嵌套事务的并发控制

在移动计算环境中，事务移动性和无线网络固有的缺陷使得传统分布式实时事务管理机制不足以支持移动实时事务的执行，故有必要为移动实时事务研究新的事务处理机制以提高其成功率．该文着重研究移动实时事务的并发控制机制．首先，该文给出了一个考虑事务定时限制以及移动性的嵌套事务模型．然后，为减少移动分布式环境中解决数据冲突的开销，该文研究了一种结合优先级夭折和优先级继承的基于封锁的并发控制协议PAI-2PL．当高优先级事务被低优先级事务阻塞时，对于相同家族事务，采用优先级继承方法解决冲突；而对于不同家族事务，则夭折重启低优先级事务．另外，为减少由于断接所引起的无效阻塞，PAI-2PL允许低优先级事务夭折处于断接状态的高优先级事务．通过性能测试，表明所提出的事务模型及并发控制机制能提高实时事务的成功率．     

Scheduling Value-Based Nested Transactions in Distributed Real-Time Database Systems

Many noticeable studies have focussed on scheduling flat transactions in a distributed real-time database system (RTDBS). However, a nested transaction model has been widely adopted in many real-life applications such as Internet stock trading systems and telecommunications. This work concerns efficiently scheduling real-time nested transactions in a distributed RTDBS. A new real-time scheduler called flexible high reward for nested transactions (FHRN) is proposed. FHRN consists of (1) FHRN_p ¹ policy to schedule real-time nested transactions and (2) 2PL_HPN to resolve the concurrent data-accessing problem among interleaved nested transactions. Simulation results show that FHRN outperforms these existent real-time schedulers such as random priority (RP), earliest deadline (ED), highest value (HV), hierarchical earliest deadline (HED), and highest reward and urgency (HRU) when an application requires a nested transaction model.     

实时主动数据库有效性检查并发控制协议

在实时主动数据库中,事务不仅有时间约束,而且事务执行可能触发其它事务执行。传统并发控制协议不适应于实时主动数据库系统。该文研究了实时主动数据库事务执行模式,提出了有效性检查并发控制协议。协议使用动态调整串行次序策略,避免不必要的事务重启动。通过仿真模拟与HP2PL协议和OCC-TI-WAIT-50协议进行了比较。结果表明,该协议能有效地降低事务延误截止时间率和事务重启动率,性能优于HP2PL和OCC-TI-WAIT-50协议。     

基于DHP-2PL的分布式实时数据库的并发控制模型

介绍了几种用于RTDBS(实时数据库系统)中的并发控制模型以及它们在分布式环境下(DRTDBS)的拓展。根据DHP-2PL提出一种改进的并发控制模型。在该模型中,引入优先级分配机制和加锁检测机制。通过这两种机制可更好地协调DRTDBS中一致性与截止期的关系,同时也解决了DHP-2PL中事务高重启率的问题。     

实时Client/Server数据库并发控制和恢复机制研究

该文提出了实时Client／Server数据库系统多版本两阶段封锁并发控制协议和有效的恢复机制。协议区分只读事务和更新事务。只读事务在执行读操作时遵从多版本时间排序协议,更新事务执行强两阶段封锁协议,即持有全部锁直到事务结束。只读事务读请求从不失败,不必等待等特性。在典型数据库系统中,读操作比写操作频繁。这个特性对于实践来说至关重要。为了提高只读事务的响应时间,协议让每个客户端与一个一致数据库影子相联,只读事务在客户端处理。更新事务提交到服务端运行。服务端每个事务Ti在提交时系统必须向所有客户端广播信息。客户端根据得到的广播信息自动构造一致数据库影子。一致数据库影子还将用于系统恢复。通过仿真模拟。与2V2PL和OCC-TI-WAIT-50协议进行比较,结果表明：该并发控制协议不仅能有效降低事务延误截止时间率和重起动率,而且能改善只读事务的响应时间,减少优先级高事务的锁等待时间。协议性能优于2V2PL协议和OCC-TI-WAIT-50协议。     

分布式实时事务提交处理

由于提交处理的复杂性,分布式实时事务很难满足其截止期.提出了一种新的提交协议A2SC(主动的双空间提交),它适合于分布式实时事务提交处理的需要.分析了由于数据冲突访问而形成的各种依赖关系.当处于准备状态的事务和处于提交状态的事务发生数据冲突访问时,A2SC允许处于执行状态的事务在一种控制的方式下乐观地访问锁住的数据.当处于准备状态的事务夭折时,仅仅只有其夭折依赖集中的事务夭折.进一步提出了"没有结果的运行"的观念.当一个事务发现它是没有结果的允许时,它将主动夭折.进行了广泛的模拟实验比较A2SC和其它协议比如基准协议、PROMPT和DDCR的性能.模拟结果表明A2SC在最小化错过截止期的事务数方面较成功,因此A2SC适合于高性能分布式实时事务.     

一种改进的内存数据库封锁机制

事务之间的封锁协议一直是数据库领域中的研究重点。在典型的内存数据库系统中,由于事务通常都比较短小,执行速度快,因此事务之间通常采用类似单写多读这样较为简单的封锁控制协议,将不同事务近似串行地分别执行。在事务并发量较高但是相互之间数据交集不大的情况下,可以通过引入粗粒度意向锁和锁粒度变换的方式来进一步提高事务之间的并行程度,加速事务的整体执行,提高事务吞吐量和系统响应速度。     

移动分布式实时事务实时原子提交

形式地给出了移动分布式实时事务实时原子提交协议的定义,在此基础上提出了适合于移动分布式实时事务的实时原子提交协议：一阶段实时原子提交协议(1PRACP)。1PRACP通过参与者与协调者的一次消息交换,在一个阶段完成移动分布式实时事务提交活动;结合超时恢复处理协议,1PRACP能避免由于站点故障或网络通信链路故障而导致的阻塞。对1PRACP进行了性能比较和评测,显示了它在各方面的优越性。     

一种基于移动环境的混合乐观实时事务处理策略

随着移动计算技术的快速发展，移动环境下涉及到实时事务处理的应用需求正逐渐增长．由于移动环境下固有特性：高的网络延迟、频繁的断接性和移动性等，采用传统的事务处理技术，在移动环境下很难满足事务的截止期要求．提出了一种基于高优先级两段锁的混合乐观实时事务并发控制协议(HORTCC—SHP2PL)．该协议在移动实时事务处理中将乐观并发控制和高优先级两段锁结舍起来，利用两阶段提交协议实现移动实时事务的全局提交．为了进一步减少移动实时事务重启的数目．在并发控制协议中引入了相似性的概念．仿真实验显示．与分布式高优先级两段锁(HP2PL)比较，HORTCC—SHP2PL明显地减少了实时事务错过截止期的比率，提高了事务的并发度，能更好的满足移动实时事务截止期的要求．     

实时Client/Server数据库多版本两个阶段封锁并发控制协议

提出了实时Client／Server数据库多版本两阶段封锁并发控制协议．该协议具有多版本并发控制机制与两阶段封锁机制的优点，使用如下策略以减少延误截止时间事务数量：若冲突集中有比持锁事务Ti优先级高的事务，且Ti重启动不会延误截止时间，则Ti重启动，冲突集中优先级最高的事务获得锁；否则，冲突集中其它事务等待．为了提高只读事务的响应时间，客户端设有一致数据库影子，只读事务在客户端处理．通过仿真模拟，与2V2PL和OCC—TI—WAIT—50协议进行比较，结果表明：该并发控制协议不仅能有效降低事务延误截止时间率，而且能改善只读事务的响应时间，减少优先级高事务的锁等待时间．协议性能优于2V2PL协议和OCC—TI—WAIT—50协议．     

Real-time transaction scheduling in database systems

A database system supporting a real-time application, which can be called “a real-time database system (RTDBS)”, has to provide real-time information to the executing transactions. Each RTDB transaction is associated with a timing constraint, usually in the form of a deadline. Efficient resource scheduling algorithms and concurrency control protocols are required to schedule the transactions so as to satisfy both timing constraints and data consistency requirements. In this paper,^† we concentrate on the concurrency control problem in RTDBSs. Our work has two basic goals: real-time performance evaluation of existing concurrency control approaches in RTDBSs, and proposing new concurrency control protocols with improved performance. One of the new protocols is locking-based, and it prevents the priority inversion problem^{, †} by scheduling the data lock requests based on prioritizing data items. The second new protocol extends the basic timestamp-ordering method by involving real-time priorities of transactions in the timestamp assignment procedure. Performance of the protocols is evaluated through simulations by using a detailed model of a single-site RTDBS. The relative performance of the protocols is examined as a function of transaction load, data contention (which is determined by a number of system parameters) and resource contention. The protocols are also tested under various real-time transaction processing environments. The performance of the proposed protocols appears to be good, especially under conditions of high transaction load and high data contention.     

移动实时数据库系统中的更新分发

数据广播作为移动计算环境下有效的数据分发技术已有许多研究,当数据广播用于发送不断更新的数据时称它为更新分发.现有的更新分发协议因没有考虑实时数据库系统中数据和事务的定时要求而不适合移动实时只读事务的处理.重点研究了移动实时数据库系统中更新分发的问题,提出了混合前向多版本数据广播协议,该协议在保证事务一致性的同时满足了数据和事务的定时约束.模拟实验表明,该协议能够有效地降低事务错过率和提高数据流行性,较现有更新分发协议更适合移动实时只读事务的处理.     

基于全局目录的分布式数据库加锁管理算法

针对简单的分布式封锁方法和完全分布式加锁算法在加锁时所需通信开销大、封锁时间长、锁管理复杂的缺点,结合集中式数据库加锁管理算法的优点,指出了在分布式数据库中保持事务可串行化方面存在的难点,利用全局目录和事务调度器,提出了基于全局目录的分布式数据库加锁管理算法。该算法使用两阶段封锁协议和多粒度封锁协议,在全局目录服务器中使用全局锁管理器管理和维护全局目录中的锁结点信息并对分布式封锁请求进行集中控制和灵活管理,能有效地保证事务的可串行化调度,降低封锁时的通信开销。     

移动分布式实时嵌套事务提交

在移动分布式计算环境中,事务移动性和无线网络固有的缺陷使得传统的分布式实时事务管理机制不足以支持移动分布式实时事务的执行,故有必要为移动实时事务研究新的事务处理机制,以提高其成功率.着重研究移动实时事务的提交机制.首先,通过分析移动分布环境中实时事务的特点给出了一个基于功能替代的移动实时嵌套事务模型.然后,提出了一个基于此模型的三层提交结构以及能够保证移动实时事务原子性和结构正确性的三阶段实时提交协议3PRTC(three-phase real-time commit).性能测试表明,所提出的事务模型及其提交机制能够提高实时事务的成功率.     

移动广播环境中实时事务处理性能研究

提出了移动广播环境中MVOCC-DA-2PV(Multiversion Optimistic Concurrency Control with Dynamic Adjustment of serialization order using Two-Phase Validation)并发控制协议。移动实时事务处理分两阶段进行。第一阶段在移动主机(MobileHosts,MHs)上处理,第二阶段在服务器上处理。移动主机(MHs)上所有移动事务执行部分向后有效性确认,与在服务器提交事务进行有效性确认。如果移动事务通过MH上部分有效性确认,提交到服务器进行最终有效性确认。如此早地检测数据冲突,节省了处理和通信资源。协议消除了移动只读事务和移动更新事务的冲突,使用多版本动态调整串行次序技术,避免了不必要的事务重启动。降低了移动只读事务的响应时间。通过模拟仿真,对MVOCC-DA-2PV协议进行了性能测试,并与PVTO和HP2PL进行了比较。实验结果表明MVOCC-DA-2PV并发控制协议要优于其它协议。     

Distributed real time database systems: background and literature review

Today’s real-time systems (RTS) are characterized by managing large volumes of dispersed data making real-time distributed data processing a reality. Large business houses need to do distributed processing for many reasons, and they often must do it in order to stay competitive. So, efficient database management algorithms and protocols for accessing and manipulating data are required to satisfy timing constraints of supported applications. Therefore, new research in distributed real-time database systems (DRTDBS) is needed to investigate possible ways of applying database systems technology to real-time systems. This paper first discusses the performance issues that are important to DRTDBS, and then surveys the research that has been done so far on the issues like priority assignment policy, commit protocols and optimizing the use of memory in non-replicated/replicated environment pertaining to distributed real time transaction processing. In fact, this study provides a foundation for addressing performance issues important for the management of very large real time data and pointer to other publications in journals and conference proceedings for further investigation of unanswered research questions.     

支持分布式合作实时事务处理的协同检验点方法

在实时事务执行时,事务故障或数据竞争会导致事务重启,为减少事务重启损失的工作量,可以采用检验点技术保证事务的时间正确性．在一类分布式实时数据库应用中,不同结点的事务通过消息交换形成合作关系,为保证合作事务间的全局一致性,当某一事务记检验点时,相关事务也要记检验点．传统协同检验点方法没有考虑应用的定时约束,不能很好地支持分布式合作实时事务处理．该文提出了一种基于图论的协同检验点方法,利用在每个计算结点上为每个合作事务集维护的局部有向图,使用一个基于图论的计算过程标识出应记检验点的事务,该方法既具有最小协同检验点特性,又使全局检验点的时延最小．实验表明该算法减少了全局检验点时延,有利于实时事务截止期的满足．     

基于MDRTDB并发控制协议DHP-2PL的研究

并发控制协议是确保数据库性能目标的一个关键问题,对移动分布式实时数据库(Mobile Distributed Real-time DataBase,简称MDRTDB)并发控制协议-分布式高优先级两段锁协议(Distributed High Priority two Phrase Locking protocol,简称DHP-2PL)从两个方面做出了改进:一是采用动态优先级分配策略,能够缩短实时事务执行的等待时间和避免饥饿现象的产生;二是为了增加并发度在加锁机制中使用混合加锁粒度,同时能够减少加锁开销。最后通过模拟应用环境的性能测试表明,这两方面的改进更好地满足了事务截止期的要求,提高了移动实时事务的成功率。