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.     

Priority inheritance in soft real-time databases

Due to resource sharing among tasks, priority inversion can occur during priority-driven preemptive scheduling. In this work, we investigate solutions to the priority inversion problem in a soft real-time database environment where two-phhse locking is employed for concurrency control. We examine two basic schemes for addressing the priority inversion problem, one based on priority inheritance and the other based on priority abort. We also study a new scheme, called conditional priority inheritance, which attempts to capitalize on the advantages of each of the two basic schemes. In contrast with previous results obtained in real-time operating systems, our performance studies, conducted on an actual real-time database testbed, indicate that the basic priority inheritance protocol is inappropriate for solving the priority inversion problem in real-time database systems. We identify the reasons for this performance. We also show that the conditional priority inheritance scheme and the priority abort scheme perform well for a wide range of system workloads.This work was supported by the National Science Foundation under Grant IRI-8908693 and by the U.S. Office of Naval Research under Grant N00014-85-K0398.A previous version of this paper appeared in Real-Time Systems Symposium, Dec. 1991.     

基于截止期的可推测实时数据库事务并发控制

在实时数据库应用环境中,最大的并发数或者吞吐量不再作为性能的重要衡量尺度,而把在截止期之前完成的事务数量作为决定性的性能指标。因此,综合乐观并发控制（OCC）和悲观并发控制（PCC）的方法,提出了基于截止期的两阶段可推测并发控制技术（PSCC）以提高事务满足时间限制的可能性。首先,基于事务的截止期对潜在的可能带来数据不一致性的威胁进行推测,尽早地重启那些变为现实的威胁可能性较大的冲突事务,允许变为现实可能性较小的冲突事务继续执行。其次,在校验阶段采用广播式的提交技术控制未违背提交一致性的事务的提交,保证了数据库一致性,同时暂时阻塞违背提交一致性的事务并利用优先级升级技术减少被阻塞事务的不必要的重启。最后,给出了PSCC的行为规则及算法描述。性能测试结果分析表明,PSCC比OCC-BC和HPA有更低的失败率的重启率。     

混合的实时嵌套事务并发控制协议

嵌套事务作为扩展事务模型的一种,提供了事务内部的并行性和更好的失败恢复选择,具有较为广泛的应用,然而却给事务并发控制带来了更高的复杂性,尤其在实时数据库中事务具有时间限制.针对实时嵌套事务模型,提出了一种混合并发控制协议,对同一事务树内的子事务采用锁协议,对不同事务树之间的事务采用基于动态调整串行化顺序的乐观并发控制协议,提高了事务的成功率,最后证明了协议的正确性.     

Managing real-time database transactions in mobile ad-hoc networks

In a mobile ad-hoc network (MANET), mobile hosts can move freely and communicate with each other directly through a wireless medium without the existence of a fixed wired infrastructure. MANET is typically used in battlefields and disaster recovery situations where it is not feasible to have a fixed network. Techniques that manage database transactions in MANET need to address additional issues such as host mobility, energy limitation and real-time constraints. This paper proposes a solution for transaction management that reduces the number of transactions missing deadlines while balancing the energy consumption by the mobile hosts in the system. This paper then reports the simulation experiments that were conducted to evaluate the performance of the proposed solution in terms of number of transactions missing deadlines, total energy consumption and the distribution of energy consumption among mobile hosts. Recommended by: Ahmed Elmagarmid This work is partially supported by the National Science Foundation grants No. EIA-9973465 and IIS-0312746.     

分布式系统中数据复制的研究与应用

维持数据的一致性是复制数据库并发执行的关键。介绍分析了MS SQL Server 2000中内置的数据复制构件以及MS SQL Server 2000的事务模型,最后结合实际的应用软件开发对数据复制的并发控制原理与措施进行了相关实现。     

面向实时应用的时态数据库系统体系结构

提出了面向实时应用的时态数据库系统 Agilor-TDB,详细介绍了系统的体系结构。针对实时应用 ,实现了实时任务调度。在数据存储方面介绍了基于时间区间的多级文件索引结构和高效的内存数据管理机制 ;在数据查询方面提出了高速查询缓存优化策略。此外 ,用 PN模型对系统并发控制进行了详细描述。     

Concurrency control in mobile distributed real-time database systems

This paper presents DMVOCC-2PLV (Distributed Multiversion Optimistic Concurrency Control with Two-Phase Local Validation) protocol for processing mobile distributed real-time transactions in mobile broadcast environments. In DMVOCC-2PLV protocol, transaction validation is performed at two levels: local validation and global validation. Local validation of transactions is performed in two phases: local pre-validation and local final validation. At the MHs (Mobile Hosts), all mobile transactions perform local pre-validation of transactions by using a backward validation mechanism. The local pre-validation process is carried out against committed transactions at the server in the last broadcast cycle. Such an early data conflict detection feature can save processing and communication resources. Transactions that survive in local pre-validation must be submitted to the server for local final validation. In global validation distributed update transactions have to check to ensure distributed serializability in all participants. The protocol can eliminate conflicts between mobile read-only and mobile update transactions, and resolve data conflicts flexibly using multiversion dynamic adjustment of serialization order to avoid unnecessary restarts of transactions. Mobile read-only transactions can be committed with no-blocking, and respond time of mobile read-only transactions is greatly reduced. The tolerance of mobile transactions of disconnections from the broadcast channel is increased. The results of simulation experiment show that the new protocol proposed offers better performance in terms of miss rate, restart rate, commit rate and throughput.     

一种新的实时数据库的乐观并发控制协议

针对一些并发控制协议中由于过多的事务重启动造成资源浪费,提出了一种新的乐观并发控制协议(Optimistic Concurrency Control),通过向后调整不严重冲突事务的动态串行化顺序,许多不必要的事务重启动可以避免。在一个事务的读阶段不用记录事务冲突和串行化限制,各种优先级冲突解决方法可以很方便地加入到该协议中,根据需要选择使用了优先级-中止-50机制。     

一种实时数据库事务处理策略的应用

通过对实时事务特点的分析和对实时数据库中事务处理策略的研究,提出了一种把优先级分配策略与定时调度策略相结合的实时事务调度策略,并融合快照机制与优先级分配策略建立了一种新的基于乐观法的并发控制策略。将这种策略应用于一个实时系统的实时数据库,系统的性能和稳定性明显提高。实验结果表明所给出的新策略及方法的正确性和有效性。     

一种新的混合实时事务并发控制算法

单一的实时事务并发控制策略因为对事务性能以及事务对数据的访问方式有着特殊限制而无法满足不同类型事务同时并存的混合实时数据库的要求.针对不同类型实时事务特征,提出了一种新的混合实时事务并发控制算法,对不同类型实时事务采用不同并发控制策略,具有极强的针对性和自适应性,算法同时通过分析数据的相关语义,利用数据相似性定义,合理放宽可串行化的正确性标准,在优先考虑硬实时事务的前提下,尽可能增加软实时事务成功提交的比例以提高系统整体性能.仿真实验结果证明MRTT_CC算法性能良好.     

数据广播中T-可串行化移动实时事务并发控制

研究了实时数据广播环境中的一致性维护问题。由于广播环境的非对称通讯特性,传统可串行化并发控制方法过于严格而不必要;现有放松可串行化方法都会导致数据库受限不一致、使各个用户读取受限不一致数据。提出了使用?子-可串行化并发控制,首先形式化定义了?子-可串行化正确性准则,证明了它虽比传统可串行化宽松但能始终保证数据一致性,使各个用户始终读取一致性数据,进而给出了相应的并发控制协议。实验结果表明,新协议可显著降低平均响应时间,使更多移动实时事务满足截止期要求。     

数据广播中т-可串行化移动实时事务并发控制

研究了实时数据广播环境中的一致性维护问题。由于广播环境的非对称通讯特性,传统可串行化并发控制方法过于严格而不必要;现有放松可串行化方法都会导致数据库受限不一致、使各个用户读取受限不一致数据。提出了使用т-可串行化并发控制,首先形式化定义了т-可串行化正确性准则,证明了它虽比传统可串行化宽松但能始终保证数据一致性,使各个用户始终读取一致性数据,进而给出了相应的并发控制协议。实验结果表明,新协议可显著降低平均响应时间,使更多移动实时事务满足截止期要求。     

Prescheduling policy for real-time concurrency control: A performance evaluation

A new priority management policy, aprescheduling policy, is proposed. This policy can be applied on any conventional concurrency control protocol to schedule a real-time transaction. Costly preemption is avoided by the prescheduling policy, and parsing dataset of a transaction is not needed. Three widely used conventional concurrency control protocols (dynamic two-phase locking, basic timestamp ordering, and optimistic) are incorporated with the prescheduling policy to form three real-time concurrency control protocols. Performance of the three protocols is evaluated from three different viewpoints: database management systems, protocols, and transaction. From a database management system viewpoint, we show the prescheduling policy can improve the performance of protocols by raising thevalid ratio and reducingrestart counts. In general, two-phase locking with the prescheduling policy performs the best in most cases and yields the best choice for concurrency control in a real-time application. Deciding factors that affect performance of each protocol are identified from protocol viewpoint. Some suggestions are given for writing a timely transaction from the aspect of transaction viewpoint.     

User‐level operating system transactions

User‐level operating system transactions allow system administrators and ordinary users to perform a sequence of file operations and then commit them as a group, or abort them without leaving any trace behind. Such a facility can aid many system administration and software development tasks. The snapshot isolation concurrency control mechanism allows transactions to be implemented without locking individual system calls; conflicts are detected when the transaction is ready to commit. Along these lines we have implemented a user‐space transaction monitor that is based on ZFS snapshots and a file system event monitor. Transactions are committed through a robust and efficient algorithm that merges the operations performed on a file system's clone back to its parent. Both the performance impact and the implementation cost of the transaction monitor we describe are fairly small. Copyright © 2009 John Wiley & Sons, Ltd.     

一种实时事务并发控制的新方法:SMVCC

提出了新颖的实时数据库事务并发控制方法：语义多版本并发控制协议（SMVCC）。利用实时数据库中存在多版本数据的特点,考虑实时数据和实时事务语义,结合实时数据库相似性概念,对传统多版本并发控制方法进行扩展,对不同事务采用不同并发控制策略,提高了事务并发度。     

基于GIS系统中实时数据库应用的研究

实时数据库(RTDB)是当今社会信息量不断与日巨增的产物,是信息监控系统(SIS)的核心。GIS全球定位系统中要监控大量的车辆的运行情况,本文的重点是验证大量车辆携带的无线传感器发送实时数据存入实时数据库的可行性,同时比较了实时数据库和关系数据库在GIS系统中应用的差异。     

Concurrency control in multi-user microcomputer database management systems

The past few years have seen a dramatic increase in the business use of centralized multi-user microcomputer without a concomitant attention to the concurrency control mechanisms employed by those to ensure the integrity of the data they manage. This paper examines the state-of-the art, examines the types of work done previously on the performance of concurrency control, and proposes independent measures to be used in an empirical study to evaluate the efficiency and effectiveness of multi-user microcomputer concurrency control.     

并行数据广播中的亚可串行化并发控制

考虑到移动计算环境的诸多限制以及移动数据库应用的特征,传统冲突可串行化在不对称通信的数据广播环境中显得过于严格而不必要.为此,文中提出一种并行亚可串行化并发控制协议.首先,形式化定义亚可串行化正确性准则,证明亚可串行化虽然比冲突可串行化宽松但能始终保证一致性,给出保证亚可串行化的充分必要条件.进而,提出相应的并行亚可串行化并发控制协议BCC-HSR.实验结果表明,BCC-HSR协议能有效改进移动事务的平均响应时间,更好地满足并行数据广播环境中高性能事务处理的要求.     

Improving the flexibility for replicated data management in distributed database systems

This paper presents a novel scheme for implementing the flexible replica control protocol[13] in the distributed database systems. The scheme requires less nodes to be locked to perform the read(write) operations. This not only provides better performance, but also provides the system designer extra flexibility to implement the protocol.