A New Method for Concurrency Control in Centralized High Performance Database Systems
Victor T.S. Shi and William Perrizo
Computer Science Department, North Dakota State University
Fargo, ND 58102
Email: {Victor.Shi, William.Perrizo}@ndsu.nodak.edu
9
Abstract:
The Internet has been growing so fast that the number of users accessing online databases doubles every year. This calls for higher system throughput. Virtually all commercial products of single version database systems use two phase locking (2PL) to increase system throughput while maintaining execution correctness. Unfortunately 2PL cannot meet many high performance requirements due to its thrashing behavior caused by blocking. In this paper we present a Read-commit Order Concurrency Control method for centralized database systems (ROCC-c). ROCC-c is a deadlock-free concurrency control method based using optimistic mechanisms. It maintains a Read-Commit queue (RC-queue) that records the access order of transactions. Along with the RC-queue, an “intervening” validation algorithm is developed for execution validation. In addition to traditional operation conflict, we introduce a new concept – element conflict. Through intervening element conflict checking, transaction restarts and validation complexity are reduced significantly. The throughput increase could be as much as 150% if we restrict the restarts to the same level as is experienced in 2PL. If no such restriction is applied, the system throughput increase could be as much as 240%.
Key Words: Concurrency control, High performance, Database systems.
1. Introduction
In recent years, the Internet has grown very rapidly. Internet database systems provide business information for an unprecedented number of customers to access. With the drastic growth of Internet users, the demand for higher system throughput becomes urgent. Replicated database systems have attracted considerable attention due to their apparent advantages of improved data availability and system scalability. In a replicated database system, identical copies of data objects are kept in multiple geographically distributed sites to provide nearby customers with fast and easy accesses. The multiple copies of data objects also provides a much more reliable information service against system outages, which might otherwise cause severe losses in E-businesses such as online stock trading systems. However, while the replication paradigm brings the benefit of quick response to read-only operations, it does cause new problems – the workload of updates in each site increases proportionally to the number of replicas of data objects. As indicated by Dr. Jim Gary in his paper ([1]), the deadlock rate has a cubic growth with respect to the number of replicas. This implicates that two phase locking, the most commonly used locking-based concurrency control method, can not meet the increasing needs of high performance in today’s Internet database systems such as online shopping systems, stock trading systems, etc.
Agrawal, Carey and Livny ([2]) studied the relative performance of three different approaches (blocking-based, immediate-restart and optimistic) for concurrency control under a variety of modeling assumptions. In the blocking-based approach, transactions set read locks on objects that they read, then upgrade the read locks to write locks for the objects that they also write. When a lock request is denied, the requesting transaction is blocked. Wait-for-graph is used for deadlock detection. In the immediate-restart approach, transactions lock the objects in the same way as in blocking-based approach, but they are aborted immediately when a lock request is denied. In the optimistic approach, transactions are allowed to execute unhindered and are validated only after they have reached their commit points, but they are restarted if any object they read has been written by other committed transactions. The conclusion is that a concurrency control method that tends to conserve physical resources by blocking transactions, such as S2PL, outperforms immediate-restart and optimistic methods for medium to high levels of resource utilization. In an environment of sufficient resources of CPUs and disks, an optimistic method is a better choice in terms of both system throughput and transaction response time.
With the fast progress of technologies, the available resources may no longer be a bottleneck (CPU speed increases drastically and the costs of disks and CPUs are dropping significantly). Thus optimistic approaches seem more promising than ever. In literature [3,4], Franaszek and Thomasian proposed a hybrid two-phase CC method, which in the first execution phase uses optimistic CC method and in the restart phase uses conservative 2PL [4]. They found that transactions statistically intend to access the same dataset as they did before, if they are restarted due to access conflicts. With the access invariance property, their method ensures at most one transaction re-execution. This diminishes repeated restarts problem in OCC methods and makes transaction response time more predictable. The locally distributed system they considered for high-volume database uses high-speed network to interconnect database sites, such that the intersite communication costs are negligible.
Early in the 80s, some commercial products adopted optimistic mechanisms to attain better performance in the form of field calls or Escrow method for “hotspot” data items [9, 10]. The field call method tests predicates at the time the transaction requests access to data items. A REDO log record is generated if the predicate test succeeds. All updates are deferred to transaction commit time. When the transaction commits, all its predicates will be tested again to validate if all required conditions hold. The drawback is that transaction commit may return an error if the update predicate has become false since the field call was issued. Escrow method overcomes this drawback by introducing Escrow record. The Escrow record preserves the truth of the predicate between the time the transaction first makes the field call and the time the predicate is reevaluated at commit time. It works only if the field is an aggregate.
Another type of methods to improve throughput is to use low isolation levels that a database management system provides [5, 12, 13]. Many database system uses “read committed” transaction isolation level as default to gain better performance. But this approach only works for some particular applications, and requires careful application analysis and complex programming techniques. Such approaches place a heavy burden on the programmers’ shoulder, contradicting the basic assumption that “the programmers are only mortals. In this domain, every attempt is made to make concurrency control automatic”[9]. Oracle and PostgreSQL use multiverson and snapshot as “serializable isolation level”. But, as [11] pointed out, they may cause write skew problem and corrupt the database.
In this paper we present a new concurrency control method that uses several techniques to reduce restarts and improve performance in terms of system throughput and transaction response time. We use a centralized data structure – Read-commit queue (RC queue), to record the execution order of transactions. We define four types of elements in the RC queue for the convenience of transaction validation. The “intervening” validation method we developed uses element conflict instead of operation conflict to reduce validation failures. In contrast to traditional OCCs, which abort transactions when conflicts occur, ROCC-c only aborts transactions when two or more intervening conflicts occur. This significantly reduces restarts to the same level of 2PL. Transactions can be controlled to complete successfully at any execution phase by using over-declaration technique or access invariance property. This is a desired property in real time systems. Other problems with SI are the infamous “snapshot too old” problem and the “dreadful” performance degradation introduced by rollback segments where old versions of data objects are stored.
The paper is organized as follows. Section 2 describes the system model and the Read-commit queue. Section 3 defines the new concept of element conflict, then develops an “intervening” validation algorithm for the proposed ROCC-c method. Section 4 presents a detailed discussion of the ROCC-c. Section 5 discusses the performance of the ROCC-c. We conclude with section 6.
2. The system and Read-commit queue
We consider a client-server database system. In this system, users may access the database locally or through the Internet. In particular, we focus on a centralized single site system, though it may be easily extended to a replicated database system over a wide area network. In such a system, high throughput and low response time are desired, and locking-based concurrency control methods such as 2PL no longer fit due to the enormous number of users and uncertain network delay, which increases the “intra-transaction think time”[2]. We assume a transaction may send multiple data access requests to the system, each time containing one or more access operations. When the system receives a request message from a client, it generates a corresponding element and posts it to a RC queue, which is used to validate transactions when they enter commit phase. An element in the RC queue contains the identifiers of the transaction, the data items to be accessed and other information.
An example of the RC queue is shown in Figure 1. We divide the elements in the queue into four types: Read element, Commit element, Validated element and Restart element. A Read element corresponds to the read/write request message a transaction submits. A Commit element represents a commit request message. A transaction may own multiple Read elements in RC since it may submit multiple requests. Note that a Read element only contains the identifiers of data items the message requests to read. All the data items that the transaction request to write are contained in the Commit element, because we use deferred writes technique to avoid cascading abort [2,4]. The data manager performs data accesses in the same order as they appear in the RC queue. In this way the element order in the RC queue represents the real execution order of data accesses that the system performs, and can be used for transaction validation. When the validation of a transaction execution fails, and the client intends to access the same data set (access invariance property [3,4]), then the system will generate a Restart element. This Restart element will contain all the identifiers of data items and the operations that the failed transaction intends to perform. If the client intends to access a completely new data set after a validation failure, then the system will abort the failed transaction and treat access requests from the client as if they were newly arriving transaction. A Validated element corresponds to transaction that has been validated, or a transaction that doesn’t need validation. When a validated element represents a transaction that doesn’t need validation, it contains all the access requests of that transaction. In section 3, we develop corollaries that tell what transactions do not need validation when using the ROCC-c method. In the example of Figure 1, transaction T0, T3 each owns one Read element, T1 owns one Read element and one Commit element, T2 owns one Restart element. In the Restart element of T2, the validated field is set to 1, which means T2 does not need further validation.
9
9
Figure 1 also shows the format of elements in the RC queue. An element consists of four fields: Tid field, element type field, access field, and Next pointer field. The Tid is the identifier of the transaction. The access field holds the Read/Write set that the message requests to read/write. The element type field consists of 3 bits: V, C and R. The V bit is set to 1 when the element is a validated element, corresponding to a transaction that does not need validation, or that the transaction has passed validation. The C bit is set to 1 if the element is a Commit element, indicating the corresponding request message is a commit request message. The R bit is set to 1 if the element is a Restart element, indicating the transaction is a restart transaction and has the access invariance property. If a transaction is restarted and has no access invariance property, the transaction should be treated as a new transaction. The Next pointer is set to point to the next element in the queue. The pointer of the last arriving element is set to NULL, as shown in figure 1, because no transaction arrives after it. Here we use a linked list to represent the RC queue for simplicity. In practice, doubly linked list may help speed up the validation process.
3. “Intervening” validation algorithm
With the RC queue, we develop an “intervening” validation algorithm described as follows. We call it “intervening” because it only checks the elements of the transaction and the intervening elements of other transactions in the RC queue for validation. In the algorithm we uses a new concept – element conflict, to determine whether or not a transaction can be validated. We say an element conflicts with another element if any of the operations they represent are in conflict.
“Intervening” validation algorithm
“First” = NULL; “Second” = NULL;
Locate the transaction’s first Read element in the RC-queue;
If (not found) Return Validated = true;
“First” = the first Read element;
While (1)
{ Compare “First” with all the elements of other transactions behind it until it
reaches an element of the same transaction (first-down-reached element);
If (There is no element conflict) //moving down to look for upper-sided conflict
{ Merge the “First” element with the first-down-reached element;
Remove the “First” element from the RC queue;
If (the first-down-reached element is the commit element)
Return Validated = true;
Else “First” = the first-down-reached element;
}
Else // There is Upper_sided_conflict;
{ Insert “First” into the RC queue right before the conflicting element;
Remove the original “First” from the RC queue;
“Second” = Commit element;
While (1) //moving up to look for lower-sided conflict.
{ Compare “Second” with all the elements of other transactions before it until
it reaches an element of the same transaction (first-up-reached element);
If (There is no element conflict)
{ Merge the “Second” element to the first-up-reached element;
Remove the “Second” element from the RC queue;
If (the first-up-reached element is the “First”)
Return Validated = true;
Else “Second” = the first-up-reached element;