Real-time concurrency control in a multiprocessor environment

Although many high-performance computer systems are now multiprocessor-based, little work has been done in real-time concurrency control of transaction executions in a multiprocessor environment. Real-time concurrency control protocols designed for uniprocessor or distributed environments may not fit the needs of multiprocessor-based real-time database systems because of a lower concurrency degree of transaction executions and a larger number of priority inversions. This paper proposes the concept of a priority cap to bound the maximum number of priority inversions in multiprocessor-based real-time database systems to meet transaction deadlines. We also explore the concept of two-version data to increase the system concurrency level and to explore the abundant computing resources of multiprocessor computer systems. The capability of the proposed methodology is evaluated in a multiprocessor real-time database system under different workloads, database sizes and processor configurations. It is shown that the benefits of the priority cap in reducing the blocking time of urgent transactions are far greater than the losses involved in committing less urgent transactions. The idea of two-version data also greatly improves the system performance because of a much higher concurrency degree in the system     

An enhanced concurrency control scheme for multidimensional index structures

We propose an enhanced concurrency control algorithm that maximizes the concurrency of multidimensional index structures. The factors that deteriorate the concurrency of index structures are node splits and minimum bounding region (MBR) updates in multidimensional index structures. The properties of our concurrency control algorithm are as follows: First, to increase the concurrency by avoiding lock coupling during MBR updates, we propose the PLC (partial lock coupling) technique. Second, a new MBR update method is proposed. It allows searchers to access nodes where MBR updates are being performed. Finally, our algorithm holds exclusive latches not during whole split time but only during physical node split time that occupies the small part of a whole split process. For performance evaluation, we implement the proposed concurrency control algorithm and one of the existing link technique-based algorithms on MIDAS-III that is a storage system of a BADA-IV DBMS. We show through various experiments that our proposed algorithm outperforms the existing algorithm in terms of throughput and response time. Also, we propose a recovery protocol for our proposed concurrency control algorithm. The recovery protocol is designed to assure high concurrency and fast recovery.     

以B链树为索引的动态多版本数据库的并发控制

在对B链树极高同步性能研究的基础上,提出了一种将B链树作为数据库索引并和多版本技术相接合的一种新颖方案。该方案将事务分为只读事务或更新事务,只读事务不需要获取锁,而更新事务也只需要少量的锁,不会形成死锁。实验表明,在并发环境下这种方案能较大的提高数据库性能和事务的吞吐量。     

Syntactic control of concurrency

We consider a finitary procedural programming language (finite data-types, no recursion) extended with parallel composition and binary semaphores. Having first shown that may-equivalence of second-order open terms is undecidable we set out to find a framework in which decidability can be regained with minimum loss of expressivity. To that end we define an annotated type system that controls the number of concurrent threads created by terms and give a fully abstract game semantics for the notion of equivalence induced by typable terms and contexts. Finally, we show that the semantics of all typable terms, at any order and in the presence of iteration, has a regular-language representation and thus the restricted observational equivalence is decidable.     

用SQL实现工作流的并发控制

工作流技术在信息系统的应用中，并发控制机制的设计是经常要面临的问题。给出一种基于将工作流中数据和任务分离的工作流并发控制机制，在保证工作流正确性的前提下，引入“数据约束”和“任务约束”的概念来提高工作流的工作性能和降低工作流设计的复杂性，并用数据库中SQL语言强有力的约束控制加以实现。     

Asynchronous operations in distributed concurrency control

Distributed locking is commonly adopted for performing concurrency control in distributed systems. It incorporates additional steps for handling deadlocks. This activity is carried out by methods based on wait-for-graphs or probes. The present study examines detection of conflicts based on enhanced local processing for distributed concurrency control. In the proposed "edge detection" approach, a graph-based resolution of access conflicts has been adopted. The technique generates a uniform wait-for precedence order at distributed sites for transactions to execute. The earlier methods based on serialization graph testing are difficult to implement in a distributed environment. The edge detection approach is a fully distributed approach. It presents a unified technique for locking and deadlock detection exercises. The technique eliminates many deadlocks without incurring message overheads.     

On-line multiversion database concurrency control

This paper presents a new model for studying the concurrency vs. computation time tradeoffs involved in on-line multiversion database concurrency control. The basic problem that is studied in our model is the following: Given:a current database system state which includes information such as which transaction previously read a version from which other transaction; which transaction has written which versions into the database; and the ordering of versions previously written; anda set of read and write requests of requesting transactions. Question: Does there exist a new database system state in which the requesting transactions can be immediately put into execution (their read and write requests satisfied, or in the case of predeclared writeset transactions, write requests are guaranteed to be satisfied) while preserving consistency under a given set of additional constraints? (The amount of concurrency achieved is defined by the set of additional constraints). In this paper we derive “limits” of performance achievable by polynomial time concurrency control algorithms. Each limit is characterized by a minimal set of constraints that allow the on-line scheduling problem to be solved in polynomial time. If any one constraint in that minimal set is omitted, although it could increase the amount of concurrency, it would also have the dramatic negative effect of making the scheduling problem NP-complete; whereas if we do not omit any constraint in the minimal set, then the scheduling problem can be solved in polynomial time. With each of these limits, one can construct an efficient scheduling algorithm that achieves an optimal level of concurrency in polynomial computation time according to the constraints defined in the minimal set.     

Advanced concurrency control in Java

Developing concurrent applications is not a trivial task. As programs grow larger and become more complex, advanced concurrency control mechanisms are needed to ensure that application consistency is not compromised. Managing mutual exclusion on a per‐object basis is not sufficient to guarantee isolation of sets of semantically‐related actions. In this paper, we consider ‘atomic blocks’, a simple and lightweight concurrency control paradigm that enables arbitrary blocks of code to access multiple shared objects in isolation. We evaluate various strategies for implementing atomic blocks in Java, in such a way that concurrency control is transparent to the programmer, isolation is preserved, and concurrency is maximized. We discuss these concurrency control strategies and evaluate them in terms of complexity and performance. Copyright © 2002 John Wiley & Sons, Ltd.     

Integrated concurrency control in shared B-trees

The traditional approach to concurrency control in sharedB-trees is based on locking. Recently new methods have been proposed called optimistic methods. In contrast to locking these methods achieve correct operations on theB-tree by a restart mechanism. In this paper we present a new approach to concurrency control, which integrates locking and the optimistic method. Practical applications are pointed out in which this approach can be expected to be superior to either locking or the optimistic method.     

一种多粒度锁的事务并发控制算法

研究了一种基于多粒度锁的并发控制算法,包括其多粒度锁锁、锁表数据结构及锁操作的算法步骤。算法可以降低冲突发生的概率和事务的夭折数,减少事务重启,有利于满足事务截止期的要求,提高事务的并发度。在验证算法有效性时,通过测试类对内存数据库记录的插入速度、索引查找的速度、记录的删除速度三方面的性能进行了测试,结果表明,事务并发控制优化算法对内存数据库性能的提升是有效可行的。     

Checkpointing for optimistic concurrency control methods

Restart-oriented concurrency control (CC) methods, such as optimistic CC, outperform blocking-oriented methods, such as standard two-phase locking in a high data contention environment, but this is at the cost of wasted processing due to restarts. Volatile savepoints are considered in this study as a method to reduce this wasted processing and to improve response time. There is the usual tradeoff between the checkpointing overhead and the wasted processing when a transaction is restarted. Our study shows that in a system where objects are accessed and updated uniformly during the lifetime of transactions, significant improvement in performance at high data conflict levels are attainable only when the checkpointing cost is low. This implies few optimally placed checkpoints per transaction. It is observed that checkpointing may result in a significant improvement in performance when access to database hot-spots are deferred to the final steps of transaction execution. The parametric studies reported in this paper are facilitated by closed-form analytic solutions expressing system performance, as well as an iterative solution which takes into account hardware resource contention in addition to data contention     

一种面向多租户中间件的应用级并发控制方法

针对在多租户中间件上存在的租户隔离、资源侵占的问题,提出一种面向多租户中间件的应用级并发控制方法。首先分析了现有并发控制方法的局限性,然后介绍了一种基于工作管理器的多租户请求处理模型的原理及设计,进一步给出了基于该模型的应用级并发控制方法的设计与实现,最后通过实验测试方法的性能开销,并设计了一个多租户性能隔离方法来验证方法的应用效果。实验结果验证了方法的有效性。     

Observations on optimistic concurrency control schemes

Optimistic concurrency control schemes allow uncontrolled access to shared data objects during transaction processing under the explicit assumption that read and write conflicts among transactions are rare events. Before a transaction commits, the DBMS has to validate that no conflict has occurred. Conflict resolution mainly relies on transaction abort.Two different optimistic concurrency control schemes are introduced and compared to each other. The problems of implementing such schemes and their implications on DBMS processing is investigated in some detail. A number of general properties of optimistic concurrency control schemes is derived, and their advantages and drawbacks w.r.t. two-phase locking approaches are discussed.     

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

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

Two fully distributed concurrency control algorithms

Two new concurrency control algorithms are introduced for partially replicated distributed databases. They both maintain two values of a data item, and differ in that one requires all locks to be granted at one time, whereas the other does not. They are based on locking, and avoid deadlocks by using timestamps to establish an execution order when conflicts arise. Since they both proceed without any communication among schedulers, but only communication between the originating site and all participating sites, we say they are fully distributed     

Distributed optimistic concurrency control with reduced rollback

Concurrency control algorithms have traditionally been based on locking and timestamp ordering mechanisms. Recently optimistic schemes have been proposed. In this paper a distributed, multi-version, optimistic concurrency control scheme is described which is particularly advantageous in a query-dominant environment. The drawbacks of the original optimistic concurrency control scheme, namely that inconsistent views may be seen by transactions (potentially causing unpredictable behavior) and that read-only transactions must be validated and may be rolled back, have been eliminated in the proposed algorithm. Read-only transactions execute in a completely asynchronous fashion and are therefore processed with very little overhead. Furthermore, the probability that read-write transactions are rolled back has been reduced by generalizing the validation algorithm. The effects of global transactions on local transaction processing are minimized. The algorithm is also free from dedlock and cascading rollback problems. Divyakant Agrawal is currently a graduate student in the Department of Computer Science at the State University of New York at Stony Brook. He received his B.E. degree from Birla Institute of Technology and Science, Pilani, India in 1980. He worked with Tata Burroughs Limited, from 1980 to 1982. He completed his M.S. degree in Computer Science from SUNY at Stony Brook in 1984. His research interests include design of algorithms for concurrent systems, optimistic protocols and distributed systems. Arthur Bernstein is a Professor of Computer Science at the State University of New York at Stony Brook. His research is concerned with the design and verification of algorithms involving asynchronous activity and with languages for expressing such algorithms. Pankaj Gupta is currently a graduate student in the Department of Computer Science at the State University of New York at Stony Brook. He received M.S. degree in Electrical Engineering from SUNY at Stony Brook in 1982 and M.S. degree in Computer Science from SUNY at Stony Brook in 1985. His research interests include distributed systems, concurrency control, and databases. Soumitra Sengupta is currently a graduate student in the Department of Computer Science at the State University of New York at Stony Brook. He received his B.E. degree from Birla Institute of Technology and Science, Pilani, India in 1980. He worked with Tata Consultancy Services, from 1980 to 1982. He completed his M.S. degree in Computer Science from SUNY at Stony Brook in 1984. His research interests include distributed algorithms, logic databases and concurrency control.This work was supported by the National Science Foundation under grant, DCR-8502161 and the Air Force Office of Scientific Research under grant AFOSR 810197     

Cautious transaction schedulers for database concurrency control

Cautious schedulers, which never resort to rollbacks for the purpose of concurrency control, are investigated. In particular, cautious schedulers for classes WW consisting of schedules serializable under the write-write constraints, and WRW, a superclass of W, are considered. The cautious WW-scheduler has a number of nice properties, one of which is the existence of a polynomial-time scheduling algorithm. Since cautious WRW-scheduling is, in general, NP-complete, some restrictions are introduced which allow polynomial-time scheduling. All of these cautious schedulers are based on the assumption that transaction predeclare their read and write sets on arrival. Anomalies which occur when transaction modify their read sets or write sets during execution are discussed and countermeasures are proposed     

Application of an optimistic concurrency control method

This paper illustrates the implementation feasibility of an optimistic approach to concurrency control. After reviewing the approach and clarifying the underlying algorithms and assumptions, it is applied to the design of a multi-user version of an existing relational database management system. Two different system architectures for a UNIX

1 UNIX is a trademark of Bell Laboratories.

-based environment are presented and prototype implementations have been constructed. We also provide some performance statistics on the optimistic approach to concurrency control and compare it with a traditional locking protocol.     

Object-based semantic real-time concurrency control with boundedimprecision

The paper describes a concurrency control technique for real-time object-oriented databases that supports logical consistency and temporal consistency, as well as bounded imprecision that results from their trade-offs. The concurrency control technique uses a semantic locking mechanism within each object and user-defined conditional compatibility over the methods of the object. The semantics can specify when to sacrifice precise logical consistency to meet temporal consistency requirements. It can also specify accumulation and bounding of any resulting logical imprecision. The authors show that this technique, under certain general restrictions, can preserve global correctness and bound imprecision by proving it can guarantee a form of epsilon serializability specialized for object-oriented databases     

Static and dynamic aspects of goal-oriented concurrency control

A new correctness criterion for schedules of update transactions is proposed, which captures users' intended changes to the database. This is motivated by the observation that traditional serializability may lead to anomalies by not taking into account semantics related to such intended changes. The alternate criterion —goal-correctness — is orthogonal to serializability, and is based on realizing goals associated with each transaction. The problems involved in goal-oriented concurrency control are first identified in a general framework. The analysis suggests that this approach is practical only for restricted transaction languages where goals can be inferred and manipulated efficiently. One such language is then considered, capturing a class of updates of practical interest. For this language, it is shown that goal-oriented concurrency control is tractable and compares favorably to serializability with respect to complexity: testing goal-correctness takes polynomial time, while testing serializability is NP-complete. The set of schedules which are correct with respect to the two criteria are incomparable. Thus, goal-correctness may allow increased concurrency. The results highlight the feasibility and advantages of goal-oriented concurrency control in restricted frameworks. The paper also discusses the dynamic aspects of goal-oriented concurrency control; in particular, an optimistic approach to the dynamic generation of goal-correct schedules is presented.An extended abstract of this paper appeared in the Proceedings of the 2nd Symposium on Mathematical Fundamentals of Database Systems (MFDBS), LNCS 364 (Springer, 1989) pp. 398–414.This author was supported in part by the National Science Foundation, under Grant Number IRI-8816078.