Implementation and modeling of two-phase locking concurrency control—a performance study

Two-phase locking (2PL) is the concurrency control mechanism that is used in most commercial database systems. In 2PL, for a transaction to access a data item, it has to hold the appropriate lock (read or write) on the data item by issuing a lock request. While the way transactions set their lock requests and the way the requests are granted would certainly affect a system's performance, such aspects have not received much attention in the literature. In this paper, a general transaction-processing model is proposed. In this model, a transaction is comprised of a number of stages, and in each stage the transaction can request to lock one or more data items. Methods for granting transaction requests and scheduling policies for granting blocked transactions are also proposed. A comprehensive simulation model is developed from which the performance of 2PL with our proposals is evaluated. Results indicate that performance models in which transactions request locks on an item-by-item basis and use first-come-first-served (FCFS) scheduling in granting blocked transactions underestimate the performance of 2PL. The performance of 2PL can be greatly improved if locks are requested in stages as dictated by the application. A scheduling policy that uses global information and/or schedules blocked transactions dynamically shows a better performance than the default FCFS.     

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.     

一种实时数据库系统的基于时间戳的多版本并发控制协议

实时数据库系统的定时限制包括数据的定时限制和事务的定时限制,一个好的并发控制协议必须要较好地满足这些定时限制。文章详细讨论了与并发控制有关的实时数据和实时事务的各种特征以及分类。并根据这些特点对传统数据库系统的多版本并发控制机制进行了扩展,提出了一种基于时间戳的多版本实时数据库系统的并发控制协议。该协议对硬实时事务不产生任何延迟,能够很好地保证实时事务和实时数据的定时限制,缺点是该并发控制协议仅是一个准一致性的协议。     

Processing real-time transactions in a replicated database system

A database system supporting a real-time application has to provide real-time information to the executing transactions. Each real-time transaction is associated with a timing constraint, typically in the form of a deadline. It is difficult to satisfy all timing constraints due to the consistency requirements of the underlying database. In scheduling the transactions it is aimed to process as many transactions as possible within their deadlines. Replicated database systems possess desirable features for real-time applications, such as a high level of data availability, and potentially improved response time for queries. On the other hand, multiple copy updates lead to a considerable overhead due to the communication required among the data sites holding the copies. In this paper, we investigate the impact of storing multiple copies of data on satisfying the timing constraints of real-time transactions. A detailed performance model of a distributed database system is employed in evaluating the effects of various workload parameters and design alternatives on the system performance. The performance is expressed in terms of the fraction of satisfied transaction deadlines. A comparison of several real-time concurrency control protocols, which are based on different approaches in involving timing constraints of transactions in scheduling, is also provided in performance experiments. Recommended by: A. ElmagarmidThis work was initiated while the author was at the Computer Science Department, University of Illinois at Urbana-Champaign.     

基于级联深度的主动实时乐观并发控制协议

主动实时数据库因结合了时间限制与主动机制而使系统事务的并发控制变得更为复杂。主动规则的引入使事务触发新的事务且在执行上具有多种耦合方式,传统的实时并发控制策略无法对具有复杂执行模式的事务进行有效调度,而基于主动数据库的并发控制机制也没有考虑事务的实时性问题。通过对事务不同耦合方式的实时要求及事务间冲突关系进行分析,提出了新的主动实时数据库乐观并发控制方法,对不同事务级联深度进行评估,结合事务执行的时间信息对冲突事务进行动态调整串行化顺序。理论分析与实验证明,能在保证事务可串行性的同时降低了不必要事务重启个数,更好地满足系统的实时性。     

并行数据库实时多版本并发控制协议性能研究

随着对实时数据库事务处理性能要求的不断提高 ,将并行数据库和实时数据库相结合的并行实时数据库将成为新的发展方向 .然而通常的实时多版本并发控制协议不适合并行数据库的无共享结构 .比较了几种并发控制协议在无共享结构下的性能 ,该文提出了一种并行实时多版本并发控制协议 .它能有效地减少事务的重启 ,降低事务的错过率 .在长短事务混合的情况下 ,它的性能比其它的并发控制协议更好 .同时 ,它具有更好的可扩展性 .作者利用仿真模型对该协议进行了性能测试 ,与其它协议进行了比较 ,并分析了实验结果 ,仿真实验结果表明该协议性能良好     

Concurrency control in distributed databases through time intervalsand short-term locks

A method for concurrency control in distributed database management systems that increases the level of concurrent execution of transactions, called ordering by serialization numbers (OSN), is proposed. The OSN method works in the certifier model and uses time-interval techniques in conjunction with short-term locks to provide serializability and prevent deadlocks. The scheduler is distributed, and the standard transaction execution policy is assumed, that is, the read and write operations are issued continuously during transaction execution. However, the write operations are copied into the database only when the transaction commits. The amount of concurrency provided by the OSN method is demonstrated by log classification. It is shown that the OSN method provides more concurrency than basic timestamp ordering and two-phase locking methods and handles successfully some logs which cannot be handled by any of the past methods. The complexity analysis of the algorithm indicates that the method works in a reasonable amount of time     

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     

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

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

一个基于SQL的并发控制机制

传统的读写事务模型（由ｒｅａｄ（ｘ）和ｗｒｉｔｅ（ｘ）序列组成）不能使调度机制充分利用应用程序的语义信息对事务进行灵活调度，从而不能有效提高系统的并发度．本文根据ＳＱＬ语言的操作语义，给出了基于ＳＱＬ的事务模型．利用这种事务模型并结合２ＰＬ方法，设计了并发控制机制：Ｃｏｎｄｉｔｉｏｎ—ｌｏｃｋｉｎｇ．这个机制可以：（１）避免数据库中的幽灵（ｐｈａｎｔｏｍ）问题，（２）利用应用程序的语义信息和完整性约束提高系统的并发度，（３）减少发生死锁的机会．因此，这是一个实用的并发控制机制．     

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.     

实时事务调度及静态可调度性分析

在类似闭环控制的硬实时数据库应用环境,实时事务具有一定的静态可预报性,其中实时事务的可调度性分析是维护实时数据库时间正确性的基础.通过利用抢占阈值,提出了一种新的实时事务处理模型,它集成了CPU调度和数据调度,实现离线并发控制,具有单阻塞的特征与好的静态可预测性,并有利于降低事务系统的负载和改善可调度性.进一步由此建立了实时事务的静态可调度性分析模型以及求最优可行调度的整数规划模型,该模型有利于达到实时事务调度的整体优化.     

Global scheduling for flexible transactions in heterogeneousdistributed database systems

A heterogeneous distributed database environment integrates a set of autonomous database systems to provide global database functions. A flexible transaction approach has been proposed for the heterogeneous distributed database environments. In such an environment, flexible transactions can increase the failure resilience of global transactions by allowing alternate (but in some sense equivalent) executions to be attempted when a local database system fails or some subtransactions of the global transaction abort. We study the impact of compensation, retry, and switching to alternative executions on global concurrency control for the execution of flexible transactions. We propose a new concurrency control criterion for the execution of flexible and local transactions, termed F-serializability, in the error-prone heterogeneous distributed database environments. We then present a scheduling protocol that ensures F-serializability on global schedules. We also demonstrate that this scheduler avoids unnecessary aborts and compensation     

基于预分析的实时主存数据库设计

讨论了一种实时主存数据库。考虑到主存数据库特点,通过在事务预分析时确定事务的读写集合,文章给出了一种基于预分析的无冲突并发控制方法。同时,文中给出了基于预分析的数据库具体实现。     

A multigranularity locking model for RDF

The advent of Linked Data is spurring the deployment of applications that use the RDF data model at the information tier. In addition to querying RDF data, there is also the requirement for online updates with suitable concurrency control. Client sessions in Web applications are organized as transactions involving requests that read and write shared data. Executing concurrently, these sessions may invalidate each other’s data. This paper presents a locking model, which is a variant of multigranularity locking protocol (MGL), to address isolation between transactions that manipulate RDF data. Four “hierarchically” related granules are defined, as well as new read/write operations and their corresponding lock modes, specifically created for the RDF data model. These new operations allow greater concurrency than the classical read/write operations in relational databases. We assessed the performance of the proposed locking model through model simulation.     

Algorithm to Process Read-only Transactions in Real-time Environments

In this study, we investigate a different approach to maintaining serializability in real-time database systems (RTDBS) such that concurrency among transactions can be increased. The study is motivated by the dominance of read only transactions (ROTs) in many real-time applications. Given the knowledge about the read/write characteristics of transactions, it can be more efficient and effective to process ROTs separately from update transactions (UTs). In particular, we have devised an independent algorithm to process ROTs while a conventional concurrency control protocol such as optimistic concurrency control (OCC) can be employed to process UTs. Using a separate algorithm to process ROTs can reduce the interference between UTs and ROTs. The undesirable overhead caused by transaction restart and blocking due to concurrency control can be alleviated. Consequently, the timeliness of the system can be improved. The performance of using this approach is examined through a series of simulation experiments. The results showed that the performance of ROTs in terms of miss rate and restart rate is improved significantly while the performance of UTs is also improved slightly. As a result, separate processing of ROTs is a viable approach that achieves better performance and resource utilization than using solely the OCC protocol, one of the best performing protocols in the literature of real-time database.     

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     

一种基于内存的高效在线数据处理服务框架

在海量数据处理环境下,传统的基于中心数据库的架构已经无法满足大规模的数据处理应用中高并发高数据读写的需求,而串行的工作模式也使得数据分析的时效性得不到有效的保证,已经严重地影响了用户体验。该文从应用架构的角度出发,提出了一种基于内存的高效在线数据处理服务框架,通过多索引的高效数据存取方法和基于发布/订阅模式的数据访问控制机制,在有效减少用户对中心数据库的读写请求的同时提高了数据处理的时效性。实验结果表明该文提出的基于内存的高效在线数据处理服务框架能够有效提高数据库的响应速度,缩短数据处理延时。     

一种面向混合实时事务调度的并发控制协议

首先给出了一个两层结构的混合实时数据库系统模型,其中支持采用非定期任务调度算法来改进系统的性能．进一步,针对这种模型下混合事务的数据一致性问题,提出了一种新的并发控制协议——MCC-DATI．该协议采用动态优先级驱动的调度算法,通过限制非定期的软实时事务对硬实时事务的阻塞时间,保证硬实时事务的可调度性;同时,采用非定期任务调度算法以及基于时间戳间隔的动态串行化顺序调整机制来减少软实时事务的截止期错失率．仿真实验表明,相对于先前的混合事务的并发控制协议,该协议在不同的系统负载与截止期约束下都能够改进系统的性能。     

Disk scheduling in video editing systems

Modern video servers support both video-on-demand and nonlinear editing applications. Video-on-demand servers enable the user to view video clips or movies from a video database, while nonlinear editing systems enable the user to manipulate the content of the video database. Applications such as video and news editing systems require that the underlying storage server be able to concurrently record live broadcast information, modify prerecorded data, and broadcast an authored presentation. A multimedia storage server that efficiently supports such a diverse group of activities constitutes the focus of this study. A novel real-time disk scheduling algorithm is presented that treats both read and write requests in a homogeneous manner in order to ensure that their deadlines are met. Due to real-time demands of movie viewing, read requests have to be fulfilled within certain deadlines; otherwise, they are considered lost. Since the data to be written into disk is stored in main memory buffers, write requests can be postponed until critical read requests are processed. However, write requests still have to be processed within reasonable delays and without the possibility of indefinite postponement. This is due to the physical constraint of the limited size of the main memory write buffers. The new algorithm schedules both read and write requests appropriately, to minimize the amount of disk reads that do not meet their presentation deadlines, and to avoid indefinite postponement and large buffer sizes in the case of disk writes. Simulation results demonstrate that the proposed algorithm offers low violations of read deadlines, reduces waiting time for lower priority disk requests, and improves the throughput of the storage server by enhancing the utilization of available disk bandwidth