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.     

Timing and causality in process algebra

 There has been considerable controversy in concurrency theory between the ‘interleaving’ and ‘true concurrency’ schools. The former school advocates associating a transition system with a process which captures concurrent execution via the interleaving of occurrences; the latter adopts more complex semantic structures to avoid reducing concurrency to interleaving. In this paper we show that the two approaches are not irreconcilable. We define a timed process algebra where occurrences are associated with intervals of time, and give it a transition system semantics. This semantics has many of the advantages of the interleaving approach; the algebra admits an expansion theorem, and bisimulation semantics can be used as usual. Our transition systems, however, incorporate timing information, and this enables us to express concurrency: merely adding timing appropriately generalises transition systems to asynchronous transition systems, showing that time gives a link between true concurrency and interleaving. Moreover, we can provide a complete axiomatisation of bisimulation for our algebra; a result that is often problematic in a timed setting. Another advantage of incorporating timing information into the calculus is that it allows a particularly simple definition of action refinement; this we present. The paper concludes with a comparison of the equivalence we present with those in the literature, and an example system specification in our formalism. Received December 20, 1993/February 23, 1995     

Experimental Study of Concurrency Control Algorithms in Main-memory Database Systems

The concurrency control algorithm is a key approach for a database system to guarantee the correctness and efficiency of the transaction execution. Thus, substantial effort has been devoted to proposing new concurrency control algorithms in both the database industry and academia. In this paper, we take the lead in summarizing the fundamental ideas of concurrency control algorithms as ``ordering-and-verifying''. We then redescribe and sort out the existing concurrency control algorithms following the ordering-and-verifying paradigm. On the basis of extensive comparative experiments on an open-source main-memory distributed transaction testbed called 3TS, we systematically investigate the advantages and disadvantages of the mainstream concurrency control algorithms and finally summarize the preferable application scenario for each algorithm to provide valuable references for follow-up research on concurrency control algorithms used in main-memory databases.     

Adhesive DPO Parallelism for Monic Matches

This paper presents indispensable technical results of a general theory that will allow to systematically derive from a given reduction system a behavioral congruence that respects concurrency. The theory is developed in the setting of adhesive categories and is based on the work by Ehrig and König on borrowed contexts; the latter are an instance of relative pushouts, which have been proposed by Leifer and Milner. In order to lift the concurrency theory of dpo rewriting to borrowed contexts we will study the special case of dpo rewriting with monic matches in adhesive categories: more specifically we provide a generalized Butterfly Lemma together with a Local Church Rosser and Parallelism theorem.     

基于相对位置的分布式实时协同编辑乐观锁并发控制算法

实时分布式协同编辑系统是计算机支持的协同工作的典型应用系统,不少学者对其进行了大量的研究,其难点是协作编辑的一致性、实时性和无约束性。因此,并发控制始终是它的研究热点,目前已提出的协同编辑的并发控制算法有:传统的加锁法、tickle锁、floor控制、可逆执行(Undo/Redo)和操作转换等。传统的加锁法最突出的优点是设计和实现较为简单,能保证具体上下文的语义完整性,但是在分布式协同编辑中无法保证加锁位置的一致性。tickle锁方法适用于分节加锁的实时分布式协同编辑的并发控制,然而无法提供多个编辑者对节内的同时编辑。JCE中的协同编辑采用了floor控制方法,每个协作编者只有获得floor才能进行     

A practical approach to the design of concurrency in object-oriented systems

Object-oriented software development methods deal with concurrency according to either the implicit concurrency model or the explicit concurrency model. In the implicit model, the objects themselves have concurrent execution capabilities whereas in the explicit model, objects are encapsulated inside processes, the latter providing concurrent execution capabilities. Both models have their advantages and disadvantages. In this paper, we propose applying the implicit model only while conducting object-oriented analysis and then switching over to the explicit model in the design phase. The implicit model naturally fits the analysis phase because the resulting models of the software system will be based on objects—the important concepts of the application—not the issues of how concurrency is implemented. A switch over to the explicit model in the design phase achieves smooth integration with already existing software consisting of processes—which is the main constraint in many industrial applications. This paper presents in detail a systematic solution for the switch over between the concurrency models that applies for soft real-time systems and demonstrates it by a simplified example from a real telecommunication project. Any object-oriented method not yet dealing with concurrency issues can easily integrate the solution. ©1997 John Wiley & Sons, Ltd.     

工程数据库管理系统的体系结构*

设计工程数据库管理系统的体系结构需要在两个重大问题上作出选择:①采用何种客户/服务器结构,以便在客户机和服务器之间寻求一个合适的功能分配点;②采用何种并发控制策略来保证客户端缓冲数据的一致性.首先讨论3种不同的客户/服务器结构（即对象服务器、页面服务器和文件服务器）,比较它们之间的差别和各自的优缺点;其次讨论了实现缓冲一致性的各种并发控制策略;最后介绍了工程数据库管理系统OSCAR的体系结构.     

The Design of the Saguaro Distributed Operating System

This paper describes the design of the Saguaro operating system for computers connected by a local-area network. Systems constructed on such an architecture have the potential advantages of concurrency and robustness. In Saguaro, these advantages are made available to the user through several mechanisms. One is channels, an interprocess communication and synchronization facility that allows the input and output of different commands to be connected to form general graphs of communicating processes. Two additional mechanisms are provided to support semitransparent file replication and access: reproduction sets and metafiles. A reproduction set is a collection of files that the system attempts to keep identical on a "best effort" basis. A metafile is a special file that contains symbolic pathnames of other files; when a metafile is opened, the system selects an available constituent file and opens it instead. The advantages of concurrency and robustness are also realized at the system level by the use of pools of server processes and decentralized allocation protocols. Saguaro also makes extensive use of a type system to describe user data such as files and to specify the types of arguments to commands and procedures. This enables the system to assist in type checking and leads to a user interface in which command-specific templates are available to facilitate command invocation.     

采集系统中存储技术的研究

随着光纤技术在嵌入式领域中的应用,通信数据量不断增加,高速采集网络上的数据并正确地存储到磁盘上已成为整个系统的瓶颈。本文从系统基本功能模块出发结合生产者/消费者(Producer-Consumer)模型,对多线程并发、直接读写扇区、异步I/O等技术在系统中的应用进行分析;对系统模型进行抽象,用数学方法对系统进行可行性分析。实验表明,数据采集系统中采用多线程多缓冲的方式在性能上有一定的提高。     

相对位置乐观锁机制及在协同编辑中的应用

为了满足实时协同编辑对快速响应、无约束协作的要求，提出了一种基于相对位置的乐观锁机制并发控制算法．该算法引入了编辑锁和读锁，并对加锁的起始位置和编辑操作位置用相对位置表示，当锁申请成功将写进锁表或者操作发送到各协作结点时，再把它们转换成绝对位置，加锁的粒度可根据编者的需要任意选择，编者在加锁请求获得确认前，可预先进行编辑操作．应用实例表明：该算法既保证了数据维护的一致性，又具有快速响应性．     

MIRROR: a state-conscious concurrency control protocol for replicated real-time databases

Data replication can help database systems meet the stringent temporal constraints of current real-time applications, especially Web-based directory and electronic commerce services. A prerequisite for realizing the benefits of replication, however, is the development of high-performance concurrency control mechanisms. In this paper, we present managing isolation in replicated real-time object repositories (MIRROR), a concurrency control protocol specifically designed for firm-deadline applications operating on replicated real-time databases. MIRROR augments the classical O2PL concurrency control protocol with a novel state-based real-time conflict resolution mechanism. In this scheme, the choice of conflict resolution method is a dynamic function of the states of the distributed transactions involved in the conflict. A feature of the design is that acquiring the state knowledge does not require inter-site communication or synchronization, nor does it require modifications to the two-phase commit protocol.Using a detailed simulation model, we compare MIRROR's performance against the real-time versions of a representative set of classical replica concurrency control protocols for a range of transaction workloads and system configurations. Our performance studies show that (a) the relative performance characteristics of these protocols in the real-time environment can be significantly different from their performance in a traditional (non-real-time) database system, (b) MIRROR provides the best performance in both fully and partially replicated environments for real-time applications with low to moderate update frequencies, and (c) MIRROR's simple to implement conflict resolution mechanism works almost as well as more sophisticated strategies.     

考虑工程图形协同应用特点的并发控制研究

并发控制是CSCW系统的关键技术，没有统一标准，通常要根据协同应用的特点来构造。文中以CAD系统内部数据库拓扑结构的一致性作为显示一致性的基础，适时放宽整体一致性模型中的事件定义条件和一致性判定条件，提出一种改进的整体一致性模型。按照该模型的事件关系定义，通过图形对象全局ID标识的一致性维护和添加操作的相关性分析，提出一种添加操作优先的并发控制策略。基于上述模型和策略，研究了一种偏复制式混合体系结构下的悲观和有限乐观的并发控制方法，以及相应的并发控制协议实施技术。工程实践证明，这些并发控制模型、策略、方法和技术充分考虑了工程图形数据结构及其协同应用特点，从而有效地支持设计过程中的人人交互。     

Maintaining temporal consistency: pessimistic vs. optimisticconcurrency control

We study the performance of concurrency control algorithms in maintaining temporal consistency of shared data in hard real time systems. In our model, a hard real time system consists of periodic tasks which are either write only, read only or update transactions. Transactions may share data. Data objects are temporally inconsistent when their ages and dispersions are greater than the absolute and relative thresholds allowed by the application. Real time transactions must read temporally consistent data in order to deliver correct results. Based on this model, we have evaluated the performance of two well known classes of concurrency control algorithms that handle multiversion data: the two phase locking and the optimistic algorithms, as well as the rate monotonic and earliest deadline first scheduling algorithms. The effects of using the priority inheritance and stack based protocols with lock based concurrency control are also studied     

一种分布式系统的设计原理

本文提出了七条设计原理,使一类由离散条件组成系统状态和以分立功能部件组成系统动作机能的分布式系统有了一种设计依据.其中,前五条原理针对分布式系统的特例——顺序系统,后两条原理专对系统的并发性.     

内存数据库并发控制算法的实验研究

并发控制算法是数据库系统保证事务执行正确且高效的重要手段,一直是数据库工业界和学术界研究的核心问题之一.将并发控制算法的基本思想归纳为“先定序后检验”,并基于该思想对现有各类并发控制算法进行了重新描述和分类总结.基于在开源内存型分布式事务测试床3TS上的实际对比实验,系统性地探究了各类算法的优缺点和适用场景,为面向内存数据库的并发控制算法的后续研究提供参考.     

Event fairness and non-interleaving concurrency

Event fairness suitable for non-interleaving concurrency is proposed. Fairness is viewed with respect to concurrency, rather than non-determinism, in the sense that no concurrent component of the system should be delayed indefinitely. Shields' asynchronous transition systems and Mazurkiewicz's traces have been used; the model gives rise to a partial order. A class of generalised notions of (weak, strong and unconditional) event fairness relative to progress requirements is derived. The weakest fairness notion in this class is shown to coincide with maximality with respect to the partial order over traces.     

集群RAID5存储系统可靠性分析

集群存储具有高并发性、高可扩展性、高性价比等特点,成为构建大型存储系统的一种重要技术.但随着系统规模的扩大,系统失效事件日益频繁,如何提高系统可靠性,保证数据持续、有效地访问就成为一个必须解决的问题.集群RAID系统是传统RAID技术在集群存储上的延伸,是有效解决可靠性问题的一种方案.出于设计集群RAID5系统的需要,提出了一种基于Markov模型的集群RAID5存储系统的可靠性模型,用以定量分析存储拓扑结构、节点/磁盘平均失效时间、重构速率等参数对集群RAID5系统可靠性的影响.分析表明:1.多层集群RAID5具有比单层集群RAID5更高的系统可靠性,更适合构建集群RAID系统;2.提高重构速率能够带来近似等幅的可靠性提升;3.在保持可靠性不变的前提下,提高重构速率能够降低系统对节点平均失效时间的需求,10倍的重构速率提升最多可以使得系统对节点平均失效时间的需求降低到原来的1/7.     

基于MLVDS和USB3.0的大数据高并发传输控制系统设计

为解决网络主机大数据样本单位并发量有限的问题,有效控制大数据高并发传输数据参量,设计了基于MLVDS和USB3.0的大数据高并发传输控制系统。在Web服务器架构中,接入MLVDS驱动器与并行接收器设备,并联合相关应用元件,调度可移动网关的主控模块,完成大数据高并发传输控制系统的硬件结构设计。利用USB3.0控制芯片,完善接口电路组织的连接回路,完成基于USB3.0的控制电路搭建。设置MySQL数据库表单,借助TCP/IP协议,处理大数据并发文本,再联合相关大数据参量,定义INF传输控制指令,实现对传输控制行为的分析。结合相关硬件结构,完成基于MLVDS和USB3.0的大数据高并发传输控制系统的设计。实验结果表明,设计系统可提升大数据样本顺序和逆序并发量的均值水平,解决了大数据样本单位并发量有限的问题,有效控制大数据高并发传输数据参量。     

Formal aspects of optimistic concurrency control in a multiple version database system

Formal aspects of optimistic concurrency control in a multiple version database system are discussed. It is distinguished between element-optimistic and set-optimistic methods. In an element-optimistic method the unit of scheduling for the concurrency control is one action/transaction, while in a set-optimistic method a set of transactions is scheduled. The underlying decision problems of serializability are defined and shown to be NP-complete in a model, which is typical for most modern transaction oriented database management systems. Therefore it is most probable, that both optimistic concurrency control types cannot be implemented efficiently in the general case.     

基于单磁盘的RAID系统可靠性分析

RAID系统具有高可靠性、高可扩展性和高性价比的特性, 是当前解决信息系统外部存储的一种主要技术。随着该技术应用的普及以及系统规模的扩大, 系统实效事件日益频繁, 因此RAID系统的可靠性研究成为一个热点。简单介绍了RAID系统工作原理及其硬盘组合方式, 从单个硬盘的可靠性出发, 推导出RAID系统的可靠性数学模型, 并进行了分析。