Efficient execution of read-only transactions in replicatedmultiversion databases

Multiple versions of data are used in database systems to increase concurrency. The higher concurrency results since read-only transactions can be executed without any concurrency control overhead and, therefore, read-only transactions do not interfere with the execution of update transactions. Availability of data in a distributed environment is improved by data replication. We propose a protocol for managing data in a replicated multiversion environment, where execution of read-only transactions or queries becomes completely independent of the underlying concurrency control and replica control mechanisms, and the data availability for read-only transactions increases significantly since they can be executed as long as any one copy of the object is available in the system. In order to validate the feasibility of our approach, we developed a simple prototype to measure the performance improvement in the response times of queries. The results clearly establish the viability of the approach as a useful paradigm for the design of efficient and fault-tolerant distributed database systems     

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

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

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

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

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

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

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.     

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     

移动广播环境中有效处理实时只读事务

提出了移动广播环境中有效处理实时只读事务的方法。给出了多种多版本广播磁盘组织。采用多版本机制，实现移动只读事务无阻塞提交。通过乐观方法，消除移动只读事务和移动更新事务的冲突。使用多版本动态调整串行次序技术，避免了不必要的事务重启动。在移动主机上如果移动只读事务通过向后有效性确认，则可提交，不需要提交到服务器处理，降低移动只读事务的响应时间。通过模拟仿真对提出的方法进行了性能测试,实验结果表明新方法要优于其他协议。     

移动实时事务预留广播空间的验证协议

在无线数据广播环境中,从移动客户机到服务器的上行带宽非常有限,传统的并发控制协议不适合这种不对称通信环境.本文提出一种可变乐观并发控制协议,服务器周期性向移动客户机广播数据对象,同时把一个广播周期分成若干个子周期,在两个连续的子周期间,一个保留空间被预留来存放服务器更新事务在第一个子周期开始后修改的所有数据对象,移动只读事务通过比较服务器更新事务提交的写集合和自己读集合来自主进行一致性验证,如果只读事务不能通过部分验证,它不会被草率地夭折并重新启动,相反,应用一个改进的向前验证策略,帮助移动只读事务争取更多提交机会.最后,本文进行充分的实验对提出的算法性能进行了评价.     

A concurrency control scheme for mobile transactions in broadcast disk environments

Broadcast disk technique has been often used to disseminate frequently requested data efficiently to a large volume of mobile clients over wireless channels. In broadcast disk environments, a server often broadcasts different data items with differing frequencies to reflect the skewed data access patterns of mobile clients. Previously proposed concurrency control methods for mobile transactions in wireless broadcast environments are focused on the mobile transactions with uniform data access patterns. These protocols perform poorly in broadcast disk environments where the data access patterns of mobile transactions are skewed. In broadcast disk environments, the time length of a broadcast cycle usually becomes large to reflect the skewed data access patterns. This will often cause read-only transactions to access old data items rather than the latest data items. Furthermore, updating mobile transactions will be frequently aborted and restarted in the final validation stage due to the update conflict of the same data items with high access frequencies. This problem will increase the average response time of the update mobile transactions and waste the uplink communication bandwidth. In this paper, we extend the existing FBOCC concurrency control method to efficiently handle mobile transactions with skewed data access patterns in broadcast disk environments. Our method allows read-only transactions to access the more updated data, and reduces the average response time of updating transactions through early aborts and restarts. Our method also reduces the amount of uplink communication bandwidth for the final validation of the update transactions. We present an in-depth experimental analysis of our method by comparing with existing concurrency control protocols. Our performance analysis shows that it significantly decreases the average response time and the amount of uplink bandwidths over existing methods.     

A formal characterization of SI-based ROWA replication protocols

Snapshot isolation (SI) is commonly used in some commercial DBMSs with a multiversion concurrency control mechanism since it never blocks read-only transactions. Recent database replication protocols have been designed using SI replicas where transactions are firstly executed in a delegate replica and their updates (if any) are propagated to the rest of the replicas at commit time; i.e. they follow the Read One Write All (ROWA) approach. This paper provides a formalization that shows the correctness of abstract protocols which cover these replication proposals. These abstract protocols differ in the properties demanded for achieving a global SI level and those needed for its generalized SI (GSI) variant — allowing reads from old snapshots. Additionally, we propose two more relaxed properties that also ensure a global GSI level. Thus, some applications can further optimize their performance in a replicated system while obtaining GSI.     

Efficient validation of mobile transactions in wireless environments

In broadcast environments, the limited bandwidth of the upstream communication channel from the mobile clients to the server bars the application of conventional concurrency control protocols. In this paper, we propose a new variant of the optimistic concurrency control (OCC) protocol that is suitable for broadcast environments. At the server, forward validation of a transaction is done against currently running transactions, including mobile transactions and server transactions. At the mobile clients, partial backward validation of a transaction is done against committed transactions at the beginning of every broadcast cycle. Upon completion of execution, read-only mobile transactions can be validated and committed locally and update mobile transactions are sent to the server for final validation. These update transactions have a better chance of commitment because they have gone through the partial backward validation. In addition to the nice properties of conventional OCC protocols, this protocol provides autonomy between the mobile clients and the server with minimum upstream communication, which is a desirable feature to the scalability of applications running in broadcast environments. This protocol is able to process both update transactions and read-only transactions at the mobile clients at low space and processing overheads.     

移动计算环境中实时嵌套事务并发控制协议的研究

提出了移动计算环境中多版本乐观并发控制协议(MultiversionOptimisticConcurrencyControl,MVOCC)处理移动实时嵌套事务.协议消除了只读事务和更新事务之间冲突,通过动态调整事务串行次序,避免不必要的事务重启动.只读事务在移动主机处理,只读事务的响应时间大大改善.事务有效性检查分两级局部有效性检查和全局有效性检查.局部有效性检查在移动主机进行.通过局部有效性检查的事务提交到服务器进行全局有效性检查.如此早地检测数据冲突,节省了处理和通信资源.通过模拟仿真,对协议进行了性能测试,并与OCC-TI-WAIT50和HP2PL协议进行了比较.实验结果表明该协议要优于其它协议.协议不但能有效地降低事务的重启动率和延误截止时间率,而且改善只读事物的响应时间.     

数据广播环境下移动实时事务的有效并发控制

在无线数据广播环境下,从移动客户机到数据库服务器的上行带宽非常有限.传统的并发控制协议不适合这种不对称通讯环境.本文结合乐观并发控制协议和时标排序协议提出一种并发控制协议.只读事务满足弱一致性,包含所有更新事务和一个移动只读事务的可串行化图是非循环的.使用本文提出的并发控制协议,移动只读事务能够自主执行,移动更新事务能够较早地检测到数据冲突.模拟试验显示,我们提出的协议相对其它已经存在的并发控制协议来说,能够更好地满足事务截止期.     

NCS中实时数据库的多版本并发控制研究

实时数据库是网络控制系统(NCS)的重要组成部分,是整个控制系统中数据交换的平台。本文在原有的两段锁机制的基础上,提出一种适用于多版本的两段锁并发控制方法。简述数据多版本给现场控制带来的不利影响。分析在数据多版本的情况下,现场事务的可串行性,用多版本并发控制协议MV2PL解决多版本并发控制问题。用简化的多版本并发协议2V2PL说明它的正确性,并通过实例表明该协议是可行的。     

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

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

Multiversion locking protocol with freezing for secure real-time database systems

Database systems for real-time applications must satisfy timing constraints associated with transactions. Typically, a timing constraint is expressed in the form of a deadline and is represented as a priority to be used by schedulers. Recently, security has become another important issue in many real-time applications. In many systems, sensitive information is shared by multiple users with different levels of security clearance. As more advanced database systems are being used in applications that need to support timeliness while managing sensitive information, there is an urgent need to develop protocols for concurrency control in transaction management that satisfy both timing and security requirements. In this paper, we propose a new multiversion concurrency control protocol that ensures that both security and real-time requirements are met. The proposed protocol is primarily based on locking. However, in order to satisfy timing constraints and security requirements, a new method, called the freezing method, is proposed. In order to show that our protocol provides a higher degree of concurrency than existing multiversion protocols, we define a new serializability for multiversion concurrency control, called FR-serializability, which is more general than traditional serializability. We present several examples to illustrate the behavior of our protocol, along with performance comparisons with other protocols. The simulation results show significant performance improvement of the new protocol.     

A neural-based concurrency control algorithm for database systems

Concurrency control (CC) algorithms guarantee the correctness and consistency criteria for concurrent execution of a set of transactions in a database. A precondition that is seen in many CC algorithms is that the writeset (WS) and readset (RS) of transactions should be known before the transaction execution. However, in real operational environments, we know the WS and RS only for a fraction of transaction set before execution. However, optional knowledge about WS and RS of transactions is one of the advantages of the proposed CC algorithm in this paper. If the WS and RS are known before the transaction execution, the proposed algorithm will use them to improve the concurrency and performance. On the other hand, the concurrency control algorithms often use a specific static or dynamic equation in making decision about granting a lock or detection of the winner transaction. The proposed algorithm in this paper uses an adaptive resonance theory (ART)-based neural network for such a decision making. In this way, a parameter called health factor (HF) is defined for transactions that is used for comparing the transactions and detecting the winner one in accessing the database objects. HF is calculated using ART2 neural network. Experimental results show that the proposed neural-based CC (NCC) algorithm increases the level of concurrency by decreasing the number of aborts. The performance of proposed algorithm is compared with strict two-phase locking (S2PL) algorithm, which has been used in most commercial database systems. Simulation results show that the performance of proposed NCC algorithm, in terms of number of aborts, is better than S2PL algorithm in different transaction rates.     

动态多版本并行控制技术在主存数据库中的实现

针对主存数据库中以索引为基础的数据访问并行控制 问题提出了动态多版本技术，并考虑了记录数据和索引结点各自的多版本管理方案及相互联 系。实验证明该技术允许对数据库更新操作的并行执行，减少了对数据锁定的需求以及版本 维护所需的系统开销，同时保证了只读事务的无阻塞性，提高了系统的整体性能。该技术尤 其适用于以只读事务为主的应用。     

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

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

Distributed Version Management for Read-Only Actions

Typical concurrency control protocols for atomic actions, such as two-phase locking, perform poorly for long read-only actions. We present four new concurrency control protocols that eliminate all interference between read-only actions and update actions, and thus offer significantly improved performance for read-only actions. The protocols work by maintaining multiple versions of the system state; read-only actions read old versions, while update actions manipulate the most recent version. We focus on the problem of managing the storage required for old versions in a distributed system. One of the protocols uses relatively little space, but has a potentially significant communication cost. The other protocols use more space, but may be cheaper in terms of communication.