PierangeloDiSanzo PerformanceModelsofConcurrencyControlProtocolsforTransactionProcessingSystems ` S apienza U niversit adi R oma

(1)

Sapienza Universit`a di Roma

Dottorato di Ricerca in Ingegneria Informatica XXIV Ciclo – 2011

Performance Models of Concurrency Control Protocols for Transaction Processing Systems

Pierangelo Di Sanzo

(2)

(3)

Sapienza Universit`a di Roma

Dottorato di Ricerca in Ingegneria Informatica XXIV Ciclo - 2011

Pierangelo Di Sanzo

Performance Models of Concurrency Control Protocols for Transaction Processing Systems

Thesis Committee Prof. Bruno Ciciani (Advisor) Prof. Antonio Puliafito

Reviewers Prof. Kishor S. Trivedi Prof. Miklos Telek

(4)

Dipartimento di Ingegneria informatica, automatica e gestionale Sapienza Università di Roma

Via Ariosto 25, I-00185 Roma, Italy e-mail: disanzo@dis.uniroma1.it

www: http://www.dis.uniroma1.it/∼disanzo/

(5)

Introduction

In many data sharing environments data manipulation leverages on transaction processing. A transaction consists of a set of operations whose processing must provide specific guarantees. These guarantees are defined in terms of properties of transactions, namely Atomicity, Consistency, Isolation and Durability (ACID properties). In IT applications transaction processing is used for the development of various components of different layers of the system architecture. E.g., transactions can be used in a database client application to execute sets of operations on data contained in a database server, or by processes to execute sets of operations on files, as well as in multi-threaded applications to execute sets of memory read/write operations.

Transaction processing relies on the so-called Concurrency Control Protocols (CCPs). A CCP defines a set of rules that allow the system to concurrently execute transactions preserving the desired properties.

Over the last few decades, transaction processing got an important role in many contexts, spanning from enterprise applications to operating systems. As a consequence, its increasing popularity has led to a growing interest in CCPs. Today, CCPs act as core components for the design and implementation of a wide spectrum of applications, as banking, booking, e-commerce, as well as of many low level synchronization mechanisms, as in file system management and, in general, in concurrent programming. For these reasons they are of interest for a lot of IT players. Further- more, despite the transaction processing is not a new research area, CCPs continue to even more attract the interest of researchers, as evidenced, e.g., by the emergence of transactional memories [1], which today represent an hot topic in the concurrent programming research.

The growing interest in CCPs is also due to a recent trend in computer manu- facturing [2]. Over the last decade, the hardware architecture of a majority of computer systems, including the entry level ones, has profoundly changed, moving from

1

(8)

a single-core to a multi-core architecture. On the other hand, the exponential growth of the CPU clock speed has stalled, so that, nowadays, the increase of computing power of a system is mainly due to the increase of the number of CPU cores. As a consequence, single process/threaded applications can no longer take advantage of such a performance gain of hardware architectures. In order to continue to exploit the growth of computing power to boost the performance performance of applications, we need for concurrent applications. This results in a growing care for CCPs.

1.1 The Performance Issue

The appeal of the transactional processing systems is mainly due to the ability to transparently ensure the properties of transactions, requiring the system user only to demarcate the blocks of operations which form a transaction. On the other hand, the concurrency control may have a remarkable impact on the system performance. The latter is a critical issue for the transaction processing systems. Suffice it to say that the transaction response time is one of the most widely used indicators in service level agreements negotiation, as well as the maximum achievable system throughput is used as a foundamental indicator in transaction processing and database system benchmarking [3].

The impact on system performance of a CCP depends on many factors. Basically, a contribution to the performance degradation is due to the dynamics of execution of transactions, which depend on the rules of the protocol. For example, some protocols prevent data conflicts by blocking the execution of a transaction when, while accessing a data item, a (potential) conflict with a concurrent transaction occurs. Con- versely, other protocols aborts a transaction (which has to be subsequently restarted) when a conflict with a concurrent transaction is detected. Both blocking and restart- ing a transaction result in an increment of the transaction response time. The performance degradation is also due to the extra processing time associated with the execution of the code for the protocol implementation, which may require both large data structure management and explicitly memory fence instructions or expensive hardware operations (e.g. compare-and-swap) for process/thread synchronization¹.

The effects on system performance due to the concurrency control are complex to analyze. Infact, the transaction execution dynamics depend on the mix of various factors, as the transaction profiles (including, e.g., the operation types and the accessed data items), the transaction arrival rate, the concurrency level, the processing speed of the system, etc. For example, transactions may experience multiple waiting phases whose durations depend, in turn, on the execution time of the conflicting transactions. Also, a transaction may experience a number of aborts which depends on the

1in some systems, as database ones, these costs can be affordable, but in others, as transactional memories, their impact can be remarkable [4].

(9)

1.2. PERFORMANCE MODELING OF CONCURRENCY CONTROL

PROTOCOLS 3

read/update rate of the set of accessed data items determined by the concurrent transactions. Furthermore, generally, a protocol provides higher performance than others depending on the workload and system features. E.g. some protocols are optimized for read-intensive workloads (as MultiVersion Concurrency Control (MVCC) protocols [5]) and some protocols perform better than others when used in systems with low resources [6].

According to the observations made so far, understanding and/or evaluating the impact of the concurrency control on the system performance are fundamental issues, and, on the other hand, they are non-trivial tasks because of the multitude of involved factors. At any rate, designing, optimizing and tuning transaction processing systems are complex activities which require a deep knowledge of the alternatives and implications associated with the choices of CCPs.

The analysis and the proper understanding of the impact on the system performance of the concurrency control require quantitative approaches. A largely used approach in computer system performance analysis is the model-based one [7, 8].

With this approach the analysis is conducted using an analytical or simulative system model. With respect to the measurement-based approach, which entails direct measurements on the real system, it provides various advantages. Basically, it allows to conduct performance studies by avoiding the burden of building (a component of) the real system or a prototype, as well as by avoiding expensive constructions of test-cases. This can be very valuable, in particular in the early stages of the system design. The model-based approach allows to abstract from undesired effects due to factors which, conversely, could be unmovable when the performance assessment is conducted with a real system. It is an inexpensive approach to explore alternatives, to test new ideas, as well as to analyze, through the composition of models, more complex systems. Obviously, all assumptions and approximations used in the construction of a model, and all its implications and limitations, are crucial aspects to be taken into account in the performance analysis. Finally, the model-based approach must not be considered a completely alternative approach to the measurement-based one, rather they have to be considered complementary.

1.2 Performance Modeling of Concurrency Control Proto- cols

Analytical modeling and simulation are two common approaches used for the performance analysis of transaction processing systems. In the follow, we discuss some basic aspects which need to be considered when dealing with the design of performance models for CCPs.

A transaction processing system is characterized by a peculiar aspect with respect to a system without data contention [9]. In the latter case, the operation response time

(10)

is affected by the queuing and processing delay in accessing hardware resources. In a transaction processing system, the transaction response time is affected by both hardware resources and data contention, and these, in turn, can affect each other.

For example, when a transaction T is blocked due to data contention, then T may determine an increment of the data contention probability of the concurrent transac- tions due to the increase of the lock holding time of locks held by T . Similarly, if T is aborted and restarted, it may determine an increment of the processing time of the concurrent transactions due to the extra resource utilization for the re-processing.

The increment of the data contention and/or the higher processing time of the concurrent transactions, in turn, may determine a subsequent increase of probability for T to be blocked or restarted. These factors entail non-trivial dependences between the various system performance indicators (e.g. the transaction response time vs. the transaction contention probability). Furthermore, the predominance of the impact on the system performance of some factors with respect to others also depends on the mix of mechanisms used by the CCP.

A performance models of a CCP has to be an effective tool aimed to analyze and/or understand performance issues related to the concurrency control. The in- trinsic complexity of the transaction processing systems imposes to rely on system models where specific assumptions are needed in order to make the analysis feasible.

For this reason, the level of abstraction of a model represents a fundamental choice determining its validity. For example, models aimed to perform a qualitative analysis of the transaction execution dynamics could abstract from the actual utilization of the hardware resources. On the other hand, it has been shown that the amount of available hardware resources can determine which type of protocol has the chance to provide the best performance [6]. Accordingly, such models would provide unreliable results if used to conduct a performance comparison study between differet protocols.

The wide diversity characterizing the workloads of applications for transaction processing systems, and the attempt to build models whose validity is not restricted to specific applications, entails the adoption of generic workload models, by the defini- tion of a limited number of parameters determining the workload model configuration space.

Finally, the complex relations existing between the various factors that can affect the system performance lead to use approximation based approaches.

1.3 Contribution Overview

In this dissertation we present performance models of CCPs for transaction processing systems. Primarily, we use an analytical approach. Further, we also use detailed simulation models to evaluate the accuracy of the analytical models we propose, and to analyze some features of the protocols we deal with. We preferred to focus mainly on the analytical approach for two main reasons: (1) analytical modeling can be a

(11)

1.3. CONTRIBUTION OVERVIEW 5

practical approach for building cost-effective computer system performance models and, in particular, (2) the analytical approach enables to quantitatively describe the complex dynamics characterizing the concurrency control, allowing us to analyze and understand existing dependencies between system performance indicators and other system configuration parameters, and to reason about their implications. In this work, we deal with both Database Systems (DBS) and Software Transactional Memories (STMs), which represent traditional and emerging transaction processing systems, respectively.

The first model we present focuses on the MVCC in DBS. The performance modeling of CCPs has been largely conducted in the field of DBS. Anyway, the most of performance analysis work focus on modeling and/or evaluation of protocols considering basic concurrency control strategies and the associated implementation mechanisms (e.g. blocking or restart-oriented lock-based protocols, optimistic timestamp- based protocols). Over the time, the need of performance gain led to the design of new, more complex protocols. Thus, what often happens nowadays is that systems use protocols relying on more complex strategies than those analyzed in performance modeling studies. This entails the need of new efforts in the performance analysis and of new performance evaluation tools. In particular, this is the case of the most used MVCC protocol in Database Management Systems (DBMS), including both commercial and open source ones. It combines different mechanisms, as data versioning, transaction blocking and transaction restart. This mix of mechanisms provides high performance in particular with read-intensive workloads, which characterize many applications which require transaction processing. On the other hand, it determines more complex transaction execution dynamics with respect to other protocols. The literature does not provide analytical performance models which allows us to study and to quantify the effect on system performance of such a mix of mechanisms. We address this lack by providing an analytical performance model tailored for this protocol. To cope with the its complexity, we use a modeling approach wich focuses on the transaction execution dynamics. These are captured by means of a transaction model which represents the transaction execution throught its phases and on basis of the phase transition probabilities. By relying on this transaction model, we incremen- tally derive a set of analytical expressions to calculate the various probabilities and the other involved quantities. The system performances indicators can be calculated numerically resolving the set of expressions. By this model we can evaluate the expected transaction response time and other indicators, as the data validation failure probability and the data version creation rate, which allow to quantify the impact on system performance associated with the different mechanisms used by the protocol.

We then move to the field of STMs. Very little performance modeling work has been made in this field. Concurrency control in DBMS and in STMs relies on similar concepts, therefore, used methodologies and models for DBS can also provide a valuable support for performance analysis of STMs. Anyway, transaction processing in STMs and in DBS is different in many aspects [10], and this entails differences

(12)

concerning both the used CCPs and the choice of appropriate system models. So far, performance analysis of STMs has been essentially conducted with the measurement- based approach. More recently, a few analytical and simulation models have been proposed. In some cases, these models assume simplified system models which do not allow to evaluate time-related performance indicators (e.g. the transaction response time and the system throughput), hence, they enable to study and evaluate protocols only by a limited analysis perspective. In other cases, the focus of the proposed models is shifted to different aspects from the CCPs. We propose a framework tailored for a more comprehensive performance analysis of STMs which overcomes the main limitations of the previous studies. In this framework we deal with the effects on system performance associated with both the CCPs and the dynamics related to the transaction executions by the concurrent threads of an application. Our system model is ispired to a typical STM application where threads are supposed to run on CPU-cores of a multi-core processor system. Threads alternate the execution of transactions, where they perform accesses both on shared and local data, and code blocks where they perform only local computations (e.g. see [11]). To this purpose, we propose a two-layered modeling approach, where a layer captures the dynamics related to the execution of threads, delegating the concurrency control model to another independent layer. These allows us to evaluate the system performance also capturing the effect due to the continuos variation of the concurrency level and to the mix of different transactions in the system. At same time, with our modeling approach, this can be simply obtained by devoloping a CCP model for a fixed, albeit parametric, concurrency level and mix of transactions. Furthermore, the two-layered structure makes the framework feasible to build models for different CCPs. We present an istance of the CCP layer for the case of the Commit-Time Locking (CTL) protocol [12], which is currently used by several STM implementations. The complete in- stantiation of the framework allows us to evaluate, in addition to the expected system throughput, various indicators, as the transaction abort probabilities throughout the various phases of the transaction execution. The indicators can be evaluated on basis of various system configuration parameters, as the profiles of the transaction classes, the number of concurrent threads, the duration of the different memory operations and the shared memory size.

Finally, we propose a modeling approach which opens a new perspective in the CCPs performance analysis. So far, proposed modeling approaches rely on the assumption according to which the data items accessed by transactions do not depend on the phase of the transaction execution. In other words, the data access sequences of transactions are not considered. Actually, in many applications for transaction processing systems, transactions tend to access data items according to specific sequences (e.g. see TPC-C [3] and TPC-W [13] benchmark applications). We show that performance delivered by CCPs which acquire locks during the transaction execution (i.e. before the commit time, as the Two-phase locking (2PL) [5]), can be strongly affected by such data access patterns. Futhermore, we show that performance models

(13)

1.4. STRUCTURE OF THE DISSERTATION 7

which ignore these aspects can provide unreliable results when used in performance analysis of applications. Today, the aforesaid types of protocols represent a very large class of CCPs used in transaction processing systems.

To cope with the above-mentioned problem, we propose, by focusing on the Strong-Strict 2PL (SS2PL) protocol, which is the most used version of the 2PL, a modeling approach which enables to capture the effects due to transaction data access patterns where data accesses depend on the transaction execution phases. This approach can be used in the case of both deterministic and probabilistic transaction data access patterns. In addition, we show as this approach is also suitable for applications with different transaction profiles, where each profile is characterized by a different data access pattern. The model we present allows to evaluate the average transaction response time for each transaction profile and various other indicators, as the lock holding time and the transaction waiting time. These indicators are very useful to investigate the effects on the system performance of the data access patterns of applications. Models built with the approach we present can also be used to support the selection of the optimal transaction data access patterns for the design of applications.

The analytical models we present in this dissertation can be coupled with different hardware resource models and can be resolved by iteration. We show how this can be done by using an hardware model typically adopted in performance studies of CCPs.

Finally, all these models can help to answer further typical questions in the area of the transaction processing systems, as: Which is the potential performance bot- tleneck? How does the system scale up? Which mechanism used by a protocol is the main responsible for the performance loss? Which is the main transaction class responsible for the system overhead?

1.4 Structure of the Dissertation

The rest of this dissertation is organized as follows. In Chapter 2 we provide an overview of the CCPs in the field of both DBS and STMs. A literature overview is presented in Chapter 3. In Chapter 4 we present the performance model of the MVCC protocol. The modeling framework for STMs and the model of the CTL protocol are presented in Chapter 5. In Chapter 6 we present the performance study on the transaction data access patterns and the performance model of the SS2PL protocol. Further, we conclude the Chapter 6 with a brief analysis of the sensitivity to data access patterns of other protocols, including those considered in previous chapters.

A concluding discussion is in Chapter 7.

Most of the material contained in this dissertation can also be found in the following

(14)

articles:

Pierangelo Di Sanzo, Bruno Ciciani, Roberto Palmieri, Francesco Quaglia, and Paolo Romano. On the analytical modeling of concurrency control algorithms for software transactional memories: The case of commit-time-locking. Performance Evaluation, to appear. Available on line: June 2011.

Pierangelo Di Sanzo, Bruno Ciciani, Francesco Quaglia, and Paolo Romano. A performance model of multi-version concurrency control. In Proceedings of the 16th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS), pages 41–50, 2008.

Pierangelo Di Sanzo, Roberto Palmieri, Bruno Ciciani, Francesco Quaglia, and Paolo Romano. Analytical modeling of lock-based concurrency control with arbitrary transaction data access patterns. In Proceedings of the first joint WOSP/SIPEW inter- national conference on Performance engineering, WOSP/SIPEW ’10, pages 69–78, New York, NY, USA, 2010. ACM.

Pierangelo Di Sanzo, Roberto Palmieri, Paolo Romano, Bruno Ciciani, and Francesco Quaglia. Analytical modelling of commit-time-locking algorithms for software transactional memories. In Proceedings of the Computer Measurement Group 10th International Conference. Computer Measurement Group, 2010.

(15)

Chapter 2

Concurrency Control Protocols in Transactional Processing Systems

Over the years, the need for performance improvement has conducted researchers and system designers to explore many alternatives and to evaluate different solutions for the problem of concurrency control in transactional processing systems. Today a variety of Concurrency Control Protocols (CCPs) exist. In this chapter we provide an overview of these protocols, focusing on the fields of Database Systems (DBS) and Software Transactional Memories (STMs) [14]. We discuss their peculiarities and provide various examples. Before discussing STMs’ protocols, we also provide a brief overview on STMs and point out some basic differences with respect to DBS.

We do not focus on protocols for distributed systems because they are out of the scope of this dissertation. Further details about notions we provide in Section 2.1 and 2.2 can be found in [5].

2.1 Basics

A largely used criterion to evaluate the correctness of CCPs is serializability. It states that an execution of a set of transactions must have the same effect on data items as some serial execution of the same transactions. Serializability corresponds to the higher isolation level defined by ANSI/ISO SQL Standard [15]. Actually, a such isolation level is not necessary in many applications. For example, in some benchmark applications (e.g. [3]) some transactions require a lower level, as Read Committed, which only ensures that transactions do not read updates on data items made by transactions not committed yet. Furthermore, some DBMS do not guarantee serializability

9

(16)

(e.g. Oracle Database [16]). In this case, to enforce serializable executions, the sys- tem user has to explicitly add specific instructions within transactions. Recoverability is another requirement for the execution of transactions. An execution is recoverable if transactions which read values written by another transaction T do not commit be- fore T . This ensures that if T has to be aborted, it can be safely done. However, this is not enough to avoid cascading aborts. This phenomenon occurs when a transaction Tigets aborted and another transaction Tj has already read a value written by Ti. In this case also Tj has to be aborted. Cascading abort can be avoided by preventing transactions from reading values wrote by uncommitted transactions. In this case the execution is said cascadeless. Another phenomenon is the following one. When a transaction T_i is aborted, the previous value of each data item updated by T_i has to be restored. If another transaction T_j updates one of this data item before T_i gets aborted, restoring the previous value of this data item entails the loss of the value written by Tj. This can be avoided by preventing transactions from writing values written by uncommitted transactions. This is called strictness. Note that strictness implies cascadeless, which, in turn, implies recoverability. All these are orthogonal properties with respect to serializability.

As concerns concurrency control strategies, basically, CCPs can be classified in pessimistic and optimistic ones. In addition, there are a variety of mixed protocols.

Pessimistic protocols avoid conflicts between transactions by blocking and/or restart- ing a transaction before a conflicting operation is executed. To this purpose, conflicts are detected before the execution of the operations. Optimistic protocols do not block or restart transactions before operations, but allow them to be executed as soon as they are requested. The conflict detection is delayed to the end of transaction, i.e. to the commit-phase. In this phase, if a conflict is detected, the transaction is aborted and restarted. These protocols are also called certification protocols.

In the follow, we describe various examples of pessimistic, optimistic, and mixed protocols. We start from the field of DBS, and after we move to STMs.

2.2 Database-Oriented Protocols

In DBS, pessimistic protocols are tipically implemented by means of locks. Trans- actions acquire a shared lock on a data item before executing a read operation, or an exclusive lock before executing a write operation. If an exclusive lock for a data item is held, no other locks can be acquired for the same data item, while, if a shared lock is held, only shared locks can be acquired. If a transaction can not acquire a lock due to another lock held by a concurrent transaction (i.e. a lock conflict occurs) then it is blocked and waits until the concurrent transaction releases the lock. The Two-phase locking (2PL) is a protocol where a transaction releases locks only after having acquired all needed locks. The 2PL ensures serializability. The Strong Strict 2PL (SS2PL) [17] is a version of the 2PL where all locks acquired by a transaction

(17)

2.2. DATABASE-ORIENTED PROTOCOLS 11

are released only when the transaction terminates or is aborted. The SS2PL ensures serializability and strictness. For these reasons, it is the most used version of 2PL.

Locking protocols which block transactions on conflict are subject to deadlock.

In these cases, further mechanisms are needed to avoid this problem. A widely used method is based on timeouts, i.e. a transaction which experiences a lock conflict can waits at most for a fixed time, after which it gets aborted. This is a low cost method, but it can cause the abort of a transaction also if deadlock does not really occur. Another method is based on the wait-graph. This is a directed graph where a node i corresponds to a transaction T_i. An edge from a node i to a node j means that the transaction Ti is blocked due to a lock held by transaction Tj. When a lock conflict occurs the corresponding edge is added to the graph. A cycle in the graph indicates that a deadlock has occurred, and it is solved by aborting a transaction in the cycle. The aborted transaction has to be subsequently restarted. The drawback of wait-graph method is due to the graph management cost. The method based on timeouts is more widely used in DBMS.

Concerning optimistic protocols, the conflict detection can rely on various mechanisms. One of these is the Serialization Graph Test (SGT) Certification. This is based on a serialization graph, i.e. a directed graph where a node i corresponds to a transaction Ti and an edge from a node i to a node j denotes that an operation ex- ecuted by transaction T_i precedes and has conflicted with an operation executed by transaction Tj. When a transaction executes an operation and a conflict occurs, then an edge is added to the graph. At commit time, if the transaction is within a cycle in the graph, it gets aborted.

The Basic Timestamp Ordering (Basic TO) is a protocol which aborts transactions as soon as a conflict is detected. It allows a transaction T executing an operation only if no conflicting operations have been already executed by other concurrent transactions started after the transaction T. Otherwise T is immediately aborted. This protocol uses timestamps associated with the start of transactions to detect the order of the operations. Basic TO ensures serializability. This version does not provide recoverability, but can be easily specialized to enforce it.

MultiVersion Concurrency Control (MVCC) is a technique which maintains multiple copies, or versions, of a data item. Each version is produced by a write operation. When a transaction reads a data item updated by a concurrent transaction, it is served by using a previous version of the data item. Hence, by maintaining previous versions of updated data items, a reading transaction is never blocked or aborted. An example of such a protocol is the Multiversion Timestamp Ordering (MVTO). Upon a read operation, a transaction T reads the version of a data item produced by the last transaction committed before T started. Upon a write operation of a transaction T on a data item d, if a version of d has already been read by a transaction started after T , then T is aborted. Otherwise a new version of d is created. Finally, a transaction T is committed only after all transactions which have produced versions read by T have been committed. MVTO ensures serializability and recoverability.

(18)

Many different protocols can be defined by combining the aforesaid techniques.

For example, a common version of MVCC used in DBMS is based on locks. Specif- ically, transactions acquire an exclusive lock upon a write operation. When a lock is acquired, the write operation is allowed to be executed only if the data item has not been updated by concurrent transactions, otherwise the transaction gets aborted.

Versions created by a transaction T become visible to other transactions only after T has been committed. This protocol ensures an isolation level lower than serial- izability, namely snapshot-isolation [18]. This level ensures a transaction reads all data from the same (consistent) snapshot of the database and prevents lost updates.

In DBMS which provide snapshot-isolation as highest isolation, the user can add instructions to explicitly acquire locks within transactions to enforce serializability.

However, although snapshot-isolation does not provide serializability, this isolation level is considered acceptable for a wide set of applicative contexts. Also, several recent works have provided formal frameworks for the identification of classes of applications where this type of isolation level suffices to ensure serializability [19], and for detecting (and correcting) applications potentially exposed to non-serializable execution histories [20].

2.3 Brief Overview on Software Transactional Memories

STMs [21] are emerging as a highly attractive and potentially disruptive programming paradigm for concurrent applications. The early proposals for Transactional Memories (TMs) architectures date back to 90s [22]. However, the research on this topic has been largely dormant till the 2002, when the advent of multi-core processors made parallel programming exit from the niche of scientific and high-performance computing and turned it into a mainstream concern for the software industry. One of the main challenges posed by parallel programming consists of synchronizing concurrent access to shared memory by multiple threads. Programmers have tradition- ally used locks, but lock-based synchronization has well-known pitfalls. Simplistic coarse-grained locking does not scale well, while more sophisticated fine-grained locking risks introducing deadlocks and data races. Furthermore, scalable libraries written using fine-grained locks cannot be easily composed in a way that retains scal- ability and avoids deadlock and data races [23].

By bringing the concept of transaction to parallel programming, STMs allow freeing the programmers from the burden of designing and verifying complex fine- grained lock synchronization schemes. By avoiding deadlocks and automatically allowing fine-grained concurrency, transactional-language constructs enable the pro- grammer to compose scalable applications safely out of thread-safe libraries. With an STM, programmers have just to demarcate code blocks which have to be executed as transactions. The underlying STM layer provides the illusion that transactions are executed in a serial fashion, which allows programmers to reason serially on the

(19)

2.4. DATABASE TRANSACTIONS VS. MEMORY TRANSACTIONS 13

correctness of their applications. Of course, the STM layer does not really execute transactions serially, instead, "under the hood" it allows multiple transactions to execute concurrently by relying on a Concurrency Control Protocol (CCP).

Today research on STMs is very active. Commercial releases of STMs do not exist yet, however many research prototypes (e.g. [12, 24, 25]), as well as prototypes for commercial systems (e.g. [26]) are available.

2.4 Database Transactions vs. Memory Transactions

Some basic differences exist between transactions in DBS (database transactions) and transactions in STMs (memory transactions) [10]. Memory transactions are executed ensuring atomicity, isolation and consistency. Unlike database transactions, they do not ensure durability, but encompass operations reading/writing data only in volatile memory. This also leads to another significant difference. As memory transactions do not require access to persistent storage when data are updated, the execution time is tipically much smaller compared to database transactions. Addi- tionally, memory transactions are mediated by lightweight language primitives (e.g.

the atomic{} construct) that do not suffer, e.g., of the overheads for SQL parsing and plan optimization typical of database environments. These factors make the memory transactions execution time typically two or three orders of magnitude smaller than database transactions [27], even when considering complex STM benchmarking applications.

Another difference concerns the isolation level required for memory transactions.

Serializability is considered largely sufficient as isolation level in DBS. However, with serializability inconsistent data values can be read by transactions that will be subsequently aborted. It has been shown that the effects of observing inconsistent states can be much more severe in STMs than in DBS [28]. In STMs, in fact, transactions can be used to manipulate program variables whose state directly affects the execution flow of user applications. As such, observing arbitrarily inconsistent memory states (as it is allowed, for instance, by the optimistic CCPs used in DBS) could lead applications to get trapped in infinite loops or in exceptions that could never be triggered in any sequential execution. This is not the case for DBS, where transactions are executed via interfaces with precisely defined (and more restricted) se- mantic (e.g. with SQL interfaces), and are executed in a sandboxed component (the DBMS) which is designed not to suffer from crashes or hangs in case the concurrency control allowed observing inconsistent data snapshots. For these reasons memory transactions require a higher isolation level than serializability, namely opacity [29].

The latter, in addition, prevents all transactions (also transactions that will be subsequently aborted) from seeing inconsistent values of data items. As we will see in the following, most protocols used in STMs rely on the so-called read validation [30] to provide opacity.

(20)

2.5 STM-Oriented Protocols

Essentially, CCPs for STMs are based on combined techniques. Most of them provide opacity. Generally, in STMs implementations for object oriented languages (e.g.

JAVA) a data item corresponds to a memory object (object-based STMs), while in other languages (e.g. C language) it corresponds to a memory word (word-based STMs). In STMs which use locks, one or more data items can be mapped to a single lock. This entails smaller memory structures needed for lock management. On the other hand, this can lead to false conflicts when two transactions access two different data items mapped with the same lock. The number of data items associated with a single lock can be a design choice or, as in some STMs, it can be adaptively changed at run-time. To simplify the discussion, in the following we assume that a data item is mapped with a single lock. In the rest of this section we provide some examples of STMs which use different protocols.

TL2 [12] is a STM which uses exclusive locks. Upon a write operation the accessed data item is not immediately updated, but the new value is stored in a private buffer of the thread executing transaction. Upon a read operation it is checked if the accessed data item has not been updated by another transaction after the reading transaction started. This check is said validation. Furthermore, it is checked if the associated lock is not held by another transaction. If one check fails then the reading transaction gets aborted. At commit time a transaction T tries to acquire an exclu- sive lock on each data item to update. If a lock is held by another transaction then T is aborted, otherwise, after the lock acquisition phase, all data items read by T are validated again. If one of these data items is not valid then T is aborted, otherwise all data items are updated and all locks are released. Protocols which acquire lock at commit-time are called Commit-Time Locking (CTL) protocols.

TinySTM [24] uses a protocol similar to protocol used in TL2. They differ in the lock acquisition time, namely TinySTM acquires the lock before executing the write operation. Furthermore, TinySTM uses other optimizations, e.g. as hierarchical locking to reduce the cost of validation and dynamic tuning of some configuration parameters.

Also mixed locking techniques can be used, e.g., as in SwissTM [31]. In this STM each data item has a write lock and a read lock. A write lock prevents other transactions from writing, but not from reading. A read lock prevents other transactions from reading. Upon a write operation a write lock is acquired. At commit time a transaction acquires also the read lock of each data item to be updated. Both read and write locks are released after the transaction commits or abort. This mixed technique allows to detect conflicts between write operations as soon as possible, but delays conflict detection between read and write operations at commit time. Furthermore, SwissTM uses a mechanism which, in case of conflict, favors long transactions by aborting shorter ones.

DSTM [32] is an STM which uses the concept of ownership of a data item. An

(21)

2.5. STM-ORIENTED PROTOCOLS 15

ownership is exclusive but revocable. Upon a write operation a transaction Tiacquires an exclusive ownership of the data item. If another transaction Tj executes a write operation on a data item owned by T_i, T_jcan wait a while, but eventually T_jacquires the ownership, possibly determining the abort of Ti if it has not yet released the ownership. On a read operation a transaction T checks if the accessed data item and all data items previously read are still valid. If yes, T executes the read operation, otherwise T is aborted. At commit time a transaction validates again all read data items. If the validation fails the transaction gets aborted, otherwise all data items are updated and ownerships are released.

Finally, multiversion protocols have also been used in STM, as in JVSTM [33]. It has been designed for the Java language. JVSTM uses the so-called versioned boxes to store versions of data items, which are shared java object. On read operation a transaction reads the version contained in the last box made visible before the start of the transaction. On write operation the value to write is stored within a box created by the transaction. Transactions execute the commit operation in mutual exclusion by acquiring an exclusive global lock. After the lock acquisition, all boxes of updated data items are made visible to other transactions and the lock is released.

A still open debate concerns progress guarantees which CCPs for STMs have to provide. In locking protocols running transactions can be affected also by threads which execute transactions and are not running. For example, if a thread is suspended (e.g. preempted by operating system) while it is executing a transaction that holds an exclusive lock, all other running transactions which try to acquire the lock can’t make progress. Non-blocking protocols are those protocols which can provide progress guarantees. Obstruction-freedom [34] is the weakest progress guarantee of non-blocking protocols. Obstruction-freedom ensures that if a thread runs by itself for long enough (including when other threads are suspended) then it makes progress. Obviously, also all transactions executed by the thread are guaranteed to be obstruction-free. Roughly speaking, if a transaction is executed by itself long enough to complete, it eventually successfully commits. Obstruction-free protocols guaran- tee that a deadlock does not occur. Lock-freedom [35] provides stronger progress guarantees than obstruction-freedom. It guarantees that if threads run long enough then at least one thread makes progress. The first work which introduced TMs describes a transactional memory with a protocol which guarantees lock-freedom.

Lock-free protocols guarantee that livelock does not occur. Finally, Wait-freedom [35] provides the strongest progress guarantees. It ensures that if threads run long enough then all threads make progress. Wait-free protocols guarantee that starvation does not occur.

Despite progress guarantees may seem desirable, today there is not a common agreement on their effectiveness in STMs [36]. The STMs we presented in this chapter provide different progress guarantees. E.g. DSTM provides obstruction-freedom.

The version of JVSTM we presented provides lock-freedom for only-read transaction, while a more recent version is completely lock-free. The other STMs we dis-

(22)

cussed above do not provide obstruction-freedom.

(23)

Chapter 3

Literature Overview

In the literature a number of publications which cope with the performance analysis of CCPs exist. Most of them focus on DBS. Less work has been done in the field of STMs. In this chapter we provide a literature overview focusing on the performance modeling. We start from the DBS, and after we move to the field of STMs.

3.1 Database Systems

The work done the field of DBS includes both simulation and analytic approaches.

Most of analytical studies use simulation to validate the analytical models. Early studies encompass locking protocols. Afterwards also optimistic protocols have been considered. E.g. static locking protocols (i.e. where transactions predeclare all lock requests before starting) have been studied by simulation in [37] and [38], and analytical models have been proposed in [39] and [40]. Dynamic locking (as the SS2PL described in Section 2.2) has been analyzed by simulation in [38] and [41], and by an analytical approach in [42]. Optimistic concurrency controls have been analyzed by analytical models in [43] and by simulation in [44] and [45].

The majority of studies rely on system models based on the following assumptions. The database contains a fixed number of data items. A data item can represent, e.g., a record, a page or an entire table. Transactions perform n operations uniformly distributed over the whole set of data items. Some studies assume the presence of data skew, e.g by considering hot spot using the b-c rule (i.e. a fraction of b operations access a fraction of c data items in the database [42]). In other studies data items are partitioned in different sets, and fixed-sized subsets of transaction operations access different data item sets [9]. In studies where both read and write data accesses are considered, each data access is a read/write with a fixed probability (e.g. in [46]).

17

(24)

In some studies, to model a workload with more transaction profiles, transactions are grouped into different classes, where the number of operations and the read/write probability depend on the transaction class [9]. A constant number of transactions in the system is assumed in some models (e.g. [42]). In other works transactions are assumed to be generated by a fixed number of users s (closed system model) [46, 6].

In some studies a ’think time’ exponentially distributed with a fixed average value is considered between transactions executed by users [47]. In closed system models the transaction throughput is used as system performance indicator. When s is assumed to be large, an open system model is considered, and transaction arrivals are modeled as a Poisson process with fixed average arrival rate (open system model) ([48, 9]).

In this case the system performance is evaluated through the average transaction response time. As concerns the hardware resources, CPU and disk are considered. Two different models for the hardware resources have been used. The first one is a simple model where resources are assumed to be ’infinite’, i.e. a transaction never waits for a CPU or I/O request ([44, 41]). In this model transactions interfere due to data contention, but they do not compete for hardware resources. In the second model a number of CPU and/or disks are explicitly accounted for (e.g. see [47]). If a resource is serving a transaction then the arriving transactions are queued. Typically, the CPU and I/O service demands associated with each operation depend on the operation type (read/write), and they are assumed to be fixed or exponentially distributed ran- dom variables. CPU and disks are modeled as a queuing network, where a transaction operation involves CPU and disk requests. In some studies the presence of a memory buffer is assumed ([49, 9]). A subset of data items are contained in the buffer and are replaced according to a policy (e.g. least-recently used). With a memory buffer, when a transaction accesses a buffered data item the I/O time is not considered.

A contribution aimed to explore the effects of the hardware resources on the CCP is provided in [6]. In this work the authors highlight as most of the previous results were seemingly contradictory, and they presented a simulative study aimed to evaluate pessimistic and optimistic protocols. The main result of this work is that, in environments with limited resources, pessimistic protocols perform better, because they tend to prevent further resource utilizations by blocking conflicting transactions.

Conversely, with low resource utilizations, so that further wasted work can be toler- ated, optimistic protocols are preferable. Finally, the authors claimed that the seem- ing contradictions of previous studies were due to the differences in the underlying assumptions concerning the hardware model.

An analytical model based on a recursive solution has been proposed in [50].

The work addresses the case of shared and exclusive locks with multiple transaction classes. A performance study encompassing a restart-oriented protocol is described in [51]. In this work a method to improve the response time based on volatile save- points is considered. A savepoint allows to reduce the wasted processing time when a transaction is restarted. The ideal distribution of checkpoint over the transaction lifetime is evaluated. Other analytical works have been presented in [52, 47, 53], for

(25)

3.2. SOFTWARE TRANSACTIONAL MEMORIES 19

which, most of results have been surveyed in [47]. In the latter work a queuing network model for hardware resources is presented and an approximated analytical approach for the dynamic locking is considered. Furthermore, the work revises models for optimistic and mixed protocols, and some possible improvements are proposed.

A mean value analysis methodology aimed to model lock-based and optimistic protocols is presented in [9]. It brings together various results by different previous studies of the authors. On basis of probabilistic assumptions, the proposed methodology allows to obtain simple approximate expressions for evaluating various probabilities and other quantities which characterize the dynamics of the execution of a transaction (e.g. the conflict probability, the mean wait time on conflict, and the average number of transaction restarts). The provided expressions allow to build approximate models, which can be coupled with a hardware model and can be resolved via iterations.

Finally, few publications addressed the evaluation of the performance of MVCC protocols, and they are mostly based on simulative approaches (e.g. [54]). Analytical models have been proposed in [55, 56]. The objective of these studies was to provide an analysis of the storage cost for maintaining data items, by relying on the evaluation/prediction of the space occupancy for the different versions of the data items vs, e.g., the data update frequency.

3.2 Software Transactional Memories

As concerns STMs, the wide majority of existing performance studies focus on the evaluation of STMs implementations. Among these, some studies compare different STMs prototypes (e.g., [12, 24, 31]), while other studies focus on the assessment of alternative design choices [25]. Some studies are aimed to evaluate adaptive policies [57], and finally, other studies use STMs implementations to evaluate alternative conflict detection and validation strategies (e.g. [30]). A very limited number of studies rely on model-based approaches. A simulation study has been presented in [58]. The authors propose a simulation model to analyze the performance with three protocols, namely a pessimistic protocol and two optimistic ones, with write buffering and with in-place memory updates, respectively. The pessimistic protocol relies on the typical shared/exclusive lock mechanism and transactions are aborted on lock conflict.

Conversely, with the optimistic protocols transactions can perform write operations without checking if a concurrent transaction has already read the accessed data item, and read operations require data validation. With write buffering, when a transaction executes a write operation, it stores the new value locally, and the value is made visible at commit time. With in-place memory update, the new value is immediately stored in shared memory, and an undo log is used to restore the previous value of the updated data item if the transaction gets aborted. By using the simulation model and synthetic workloads, the study encompasses the evaluation of three performance

(26)

indicators, i.e. the mean number of restarts per transaction, the mean number of steps executed and the mean number of locks held by a transaction. The authors show as in their tests optimistic protocols perform better in terms of mean number of restarts.

The studies based on analytical are presented below. The same authors of the above-mentioned simulation study also proposed an analytical approach [59]. They provide an analytical framework for STM systems where the same protocols as in the simulation study are considered. Subsequently, they extended the framework for the case of optimistic protocol with lazy locking [60]. The framework is based on an absorbing discrete-time Markov Chain [61] which models the execution of a trans- action. The system model assumes a fixed number k of active transactions in the system, each one executing N read/write accesses uniformly distributed on L data items, with Pwas probability for an access to be a write. Given a protocol, the out- come of the analytical model depends exclusively on the aforesaid four parameters.

The framework allows to evaluate the same performance indicators as the simulation model proposed by the authors. The analytical models have been validated by performing comparative tests with the output of a discrete event simulator. In these studies the performance indicators are evaluated with respect to the probability Pw

and the number of concurrent transactions N. Further, the authors present some re- sults calculated by means of the analytical model. They confirm the advantages of the optimistic protocols, unless Pw assumes very large or very small values. The study presented in [62] proposes two analytical models to compare the performance of the typical lock-based approach for the execution of a critical section and of a simple version of the CTL protocol (see Section 2.5). In the case of the CTL protocol, the authors consider transactions which speculatively access the critical section. At commit-time, if a concurrent transaction has committed, then the committing transaction aborts and restarts, otherwise successfully commits. The system model consists of N processors witch execute N threads, each one repeatedly issuing critical sec- tions/transactions. All critical section/transaction executions are assumed to access to the same memory location protected by a unique global lock. The duration of a critical section/transaction is exponentially distributed. Concerning the transaction model, the durations of the abort phase and the commit phase are not considered. A queuing based model have been used for both critical sections and transactions. Both the models have been validated by simulation. According to the results obtained with models, the typical critical section approach generally outperforms the transaction approach, while with low contention they are comparable. The same authors subsequently proposed other two works. Also in these works they use a queuing-based approach. In the first work [63] they consider a system with a fixed number of treads, each one executing on a processor. Threads execute a number of different transaction types according to a given distribution probability. The transaction types differ in the number of checkpoints executed. While executing a checkpoint, a transaction may be aborted. The execution of transactions is modeled by means of a continuous-time Markov Chain [61], where a state is represented by the number of active transac-

(27)

3.2. SOFTWARE TRANSACTIONAL MEMORIES 21

tions and by the number of checkpoints executed by the first transaction that will commit. A transition occurs when a new transaction starts, commits, aborts or executes a checkpoint. The conflict detection is simply assumed to be lazy or eager (see Section 2.5) depending on the number of checkpoints of transactions. Read and write accesses are not differentiated and the conflicting probability between transactions is considered to be fixed and to be an input parameter for the model. In the tests performed by the authors, the conflict probability has been evaluated by experi- mental measurements on a real system. The model has been validated against a real system by using STAMP benchmark [11] and by comparing the average transaction response time predicted by the analytical model. In the second work [64] the authors propose a similar approach. Unlike the previous approach, in this model a state of the Markov Chain is represented by the number of active transactions and by the number of transactions that will commit. A transition occurs when a new transaction starts, commits or aborts. Also in this work read and write accesses are not differentiated.

The conflict detection relies on checkpoints and the conflict probability is calculated according to the size of the overlapped sets of data items accessed by concurrent transactions. Also this model has been validated by using STAMP benchmark.

(28)

(29)

Chapter 4

Performance Modeling of MultiVersion Concurrency Control Protocols

4.1 Introduction

Several DBMS rely on MVCC protocols (Section 2.2). These protocols are also largely used in other data management systems (as JBossChache [65]), and are gain- ing ground in STMs (e.g. JVSTM [33]). The exploitation of multiple data versions allows the system to immediately serve, via a version of the accessed data item, a read operation, which with other protocols could entail a delay or an abort of the reading transaction in case of conflict. This approach improves the level of concurrency between transactions and, mainly, it makes multiversion protocols especially suitable for a read-intensive workload. Such a kind of workload is representative of several applications, as most of the Web-based ones.

In Section 2.2 we also discussed the most widely used MVCC protocol in DBMS.

This protocol provide the snapshot-isolation level and it has been adopted in both mainstream proprietary and open source DBMS (e.g. Oracle Database [16] and Post- greSQL [66]). In this chapter we address the performance modeling of the MVCC and we present an analytical performance model tailored for the aforesaid protocol.

The model we propose is able to capture the transaction execution dynamics due to the mix of mechanisms used by this protocol and allows to evaluate both the main performance indicators (e.g. average transaction response) and other specific indicators

23

(30)

for this protocol (e.g. the version check failure probability, the frequency of creation of versions, the lock holding time). In our analysis we consider a level of abstraction which makes the model independent of some specific aspects of systems. In particular, the model is independent of the specific policy adopted by the system to retrieve data item versions (e.g. explicit storing, as in PostgreSQL, or dynamic regeneration of the required version via rollback segments, as in Oracle Database). This makes the model suitable for a variety of version management mechanism implementations.

The model has been validated via a simulation study. The used simulation model explicitly mimics the dynamics of the transaction executions in a database system where the transction execution is regulated by the considered MVCC protocol.

The remainder of this chapter is structured as follows. In Section 4.2 we provide a description of the protocol rules. The analytical model is presented in Section 4.3, where we first provide a basic version of the model, and after we present an extended version copying with multiple transaction classes and non-uniform data access. Finally, we present a model validation study in Section 4.6.

4.2 An Overview of MultiVersion Concurrency Control Pro- tocol Ensuring Snapshot-Isolation

The protocol we are analyzing combines different concurrency control techniques, namely data versioning, transaction blocking and transaction restart. In the follow we describe more in depth the protocol and the basic implementation mechanisms.

Each transaction in the system is associated with a so-called Start-Timestamp, whose value is set when the transaction starts. This value is used to determine the set of transactions that are concurrent with T . In particular, this set is formed by the transactions that are active when Start-Timestamp is set for T , plus the transactions with timestamp greater than Start-Timestamp. When a transaction T tries to write a data item x that has not yet been accessed by this same transaction, version check is performed to determine whether no concurrent transaction that wrote x has already been committed. In the positive case, version check is said to have failed, and T is immediately aborted. Otherwise, T tries to acquire an lock on x, which can lead to a wait phase in case the lock is currently held by any other active transaction T^′. In the latter case, if T^′is eventually committed, then T gets aborted in order to avoid the so called lost update phenomenon [18]. After the lock acquisition, T is allowed to create a new version of x. If T wants to read/write a data item x previously written during its execution, the version of x just created by T is immediately supplied. Instead, a read operation on a data item x not previously written by T is served by accessing the version of x that has been committed by the most recent transaction not concurrent with T . In this way all read operations are never blocked and do not cause transaction abort. When T commits or aborts, all the acquired locks are released. In case of

(31)

4.3. THE ANALYTICAL MODEL 25

commit, all the data item versions created by T become visible to other transactions.

4.3 The Analytical Model

4.4 System Model

We consider an open system model where transactions arrive according to a Poisson Process. A transaction consists of a begin operation, which is followed by a number of read or write operations, each one accessing a single data item, and finally by a commit operation. Begin, write and commit operations are assumed to require a mean number of CPU instructions denoted with nIb, nIwand nIc, respectively. CPU instructions to support read accesses are modeled in a slightly more complex way, as a reflection of the fact that a read access can require traversing the history of data item versions to retrieve the correct one. This is modeled by assuming for a read access a baseline of a mean number of nI_r^F CPU instructions, plus a mean number of nI^V_r CPU instructions for each traversed version. In the case of transaction abort, we assume the execution of a mean number of nIa CPU instructions. Also, the transaction is rerun after a randomly distributed back-off time with mean value T_{backo f f}. When a read or write operation is performed, if the accessed data item is not in the buffer then a disk access occurs. Each disk access is assumed to require a fixed latency tI/O. The CPU is modeled as an M/M/k queue, where k is the number of CPUs, each of which is assumed to have a processing speed denoted as MIPS .

We first present a basic version of the analytical model, relying on the following additional assumptions: (1) transactions belong to a unique class with a mean number of N_wwrite operations and N_rread operations per transaction and with an arrival rate λ, (2) transactions perform accesses uniformly distributed over the whole set of D data items. These assumptions will be then removed while presenting an extended version of the analytical model.

From this point onwards, all the assumptions we make in this chapter are finalized only to the construction of the analytical model. They are not considered in the simulation model we used in the validation study.

In our analytical model we ignore the effects on performance of transaction aborts and restarts due to deadlocks. Previous studies on locking protocols (e.g., [67], [42]) have shown that these effects are negligible with respect to the data contention effects.

Furthermore, given that the above-mentioned studies deal with the 2PL protocol, assuming that deadlock does not occur reveals even more realistic in case of MVCC since it does not use locks on read operations, hence further reducing the deadlock probability.

Finally, we assume that the system is stable and ergodic.

(32)

4.4.1 Basic Analytical Model

Transaction Execution Model

We assume that each transaction is formed by an interleaving of read/write operations such that the are N_rreads uniformly mixed with N_wwrites. This choice is motivated by the fact that a transaction never aborts while executing a read operation. Thus, in order to evaluate the average transaction response time, it is important the average number of read operations executed by a transaction, including the operations executed by the aborted runs of the transaction. The execution of a transaction is modeled through a directed graph. Figure 4.1 shows an example for a transaction with Nw = 2. Each node represents a state of a transaction execution corresponding to a specific phase of the transaction lifetime. The label of an arc from a node p to a node q represents the transition probability from state p to state q. If the label is omitted, than the transition probability is intended to be 1. Obviously, the sum of all transition probability values for outgoing arcs from a node must be 1. The states labelled with begin, commit and abort are used to model the execution of the respec- tive operations. Instead, as for read/write accesses to data items, we use a different state labelling approach to denote the corresponding phases. Considering that the sequence of Nr read operations performed by a transaction is uniformly distributed across the N_w write operations, we assume to have a write operation after executing N_r^S = N_r/(N_w+ 1) read operations (see Figure 4.1). According to this rule, state ˆ0 represents the phase in which the initial N_r^S read operations are performed before the first write access, and states ˆi (with 1 ≤ i ≤ Nw) represent phases in which a write operation has been issued, followed by a mean number of N_r^S read operations.

According to the MVCC description provided in Section 4.2, when a write oper- ation needs to be carried out, version check is performed. If version check for the i-th write fails, the transaction is aborted. The corresponding state transition probability is denoted as P^I_A,i. (The related arc starts from state di − 1 and ends to state abort.) On the other hand, if version check succeeds (this occurs with probability 1 − P^I_A,i) a wait phase for lock acquisition occurs with probability P_cont, corresponding to the probability that a lock is being held by another transaction.

Note that, by assumption (2) in Section 4.4, P_cont is independent of the accessed data item. Thus, the probability of transition from state di − 1 to state ˜i can be ex- pressed as P_w,i = (1 − PÎ_A,i)P_cont. On the other hand, the probability that a lock is immediately granted after version check is 1 − P_cont. Thus, the probability of transition from state di − 1 to state î is PE,i= (1 − PÎ_A,i)(1 − Pcont). A transaction in a waiting state ˜i gets aborted with probability P^C_A,i, which we will subsequently evaluate. When a read/write operation is executed, the accessed data item might be already available in the buffer pool, otherwise a disk access is needed. We denote with P_BH1the expected buffer hit probability. However, as suggested in [9], in order to provide a more accurate evaluation of the effects of buffer hits in case of transaction restart, a differ-

PierangeloDiSanzo PerformanceModelsofConcurrencyControlProtocolsforTransactionProcessingSystems ` S apienza U niversit adi R oma

Sapienza Universit`a di Roma

Performance Models of Concurrency Control Protocols for Transaction Processing Systems

Pierangelo Di Sanzo

Sapienza Universit`a di Roma

Pierangelo Di Sanzo

Performance Models of Concurrency Control Protocols for Transaction Processing Systems

Contents

Chapter 1

Introduction

1.1 The Performance Issue

1.2 Performance Modeling of Concurrency Control Proto- cols

1.3 Contribution Overview

1.4 Structure of the Dissertation

Chapter 2

Concurrency Control Protocols in Transactional Processing Systems

2.1 Basics

2.2 Database-Oriented Protocols

2.3 Brief Overview on Software Transactional Memories

2.4 Database Transactions vs. Memory Transactions

2.5 STM-Oriented Protocols

Chapter 3

Literature Overview

3.1 Database Systems

3.2 Software Transactional Memories

Chapter 4

Performance Modeling of MultiVersion Concurrency Control Protocols

4.1 Introduction

4.2 An Overview of MultiVersion Concurrency Control Pro- tocol Ensuring Snapshot-Isolation

4.3 The Analytical Model

4.4 System Model