Write-then-read transaction (W jR) is a transaction that consists of two consecutive phases: write phase containing write and read operations in random order, and second phase containing read operations and write operations only on data items previously updated in the first phase. W jR transactions are of great practical importance, but the problem of efficient processing of such transactions has received only little attention of research community so far. In this paper, we present Dynamic Versioning Protocol (DVP), which optimizes W jR transactions processing using versions on the second phase. DVP supports STEAL policy and incorporates dynamic approach to the problem of selecting most suitable versions for read operations of the read phase. We prove the correctness of our protocol, so it guarantees the serializability of all transactions. The conducted experimental evaluation shows significant benefits of DVP for processing of concurrent W jR transactions.
There is a well-known problem of concurrent processing
of update transactions (usually called updaters) that
update some data items more or less randomly and
readonly transactions (usually called queries) that consist
only of read operations. One of the most widely used
protocols, two-phase locking (2PL [
The solution to the concurrency problem that avoids
data contention between updaters and queries is to
maintain multiple versions of data items. This is
generally called multiversioning [
Most multiversion algorithms support only two transaction classes: updaters and queries. On the other hand, there exists such usable class as write-then-read transactions (W jR transactions, for short). This transactions consist of two consecutive phases: write phase containing write and read operations in random order, and second phase containing read operations and write operations on data items only previously updated in the first phase. Integrity constraints (IC) checking implies using such W jR pattern when such checking occurs at the very end of transaction. Of course, other types of IC’s checking may yield different transaction patterns, which is not the goal of this paper.
Most concurrency control protocols process W jR transactions as updaters (usually using 2PL), which leads to unnecessary delays of W jR transactions. Let us consider an example.
Example 1. Consider a system for items supplies management. This system uses two relations:
Supply(supp id, date, item, item number, ...),
ItemInfo(item id, rating, ...)
Manager can request supply of a particular item. The corresponding order is placed in Supply relation. System checks reasonability of this request by checking ItemInfo relation, which stores some information for each item (rating, sale statistics, etc.). If some criterion (low sales for the item, for example) is not sufficient, request for supply will be denied.
Thus, we could have two transactions here. Let T1 be a W jR transaction that inserts tuple s in Supply relation. Then this transaction reads tuple i from ItemInfo relation to check the criterion. Let T2 be a transaction that runs concurrently and updates ItemInfo relation by updating tuple i from it. Consider one of the possible histories:
W1(s) W2(i) R1(i) c(T2) c(T1)
All concurrency control protocols that process
updaters using 2PL rules would not allow such a
history. For example, strict two-phase locking protocol
(S2PL[
But transaction T2 could be serialized after T1 if T1 do not see version of tuple i created by T2.
Unfortunately, class of W jR transactions has not
received much attention in the database research
community. As far as we know, there is only one protocol
that optimizes processing of W jR transactions: an
extension of the multiversion two-phase locking protocol
(EMV2PL [
However, the approach of [
Towards the goal of optimizing processing of W jR transactions, this paper introduces a new Dynamic Versioning Protocol (DVP), which produces only serializable schedules and supports an efficient processing of W jR transactions. Our protocol allows more efficient processing by employing following techniques. Firstly, it allows W jR transactions to release all their read locks after executing their first phase and to execute second phase without acquiring new locks. Secondly, DVP supports STEAL policy, which is one of its major benefits. Thirdly, it maintains only fixed number of versions per each data item. At last, DVP introduces dynamic approach to the problem of selecting most suitable versions for read operations on the second phase, which allows reading of the most recent versions possible on the second phase without experiencing unnecessary delays. So, DVP ovecomes all aforementioned shortcomings of EMV2PL protocol.
To explain in more details the benefits of dynamic approach let us consider one more example.
Example 2. Consider transactions T1 and T2 from previous example. Concurrent execution of this transactions might produce following history:
W1(s) W2(i) c(T2) R1(i) c(T1)
A static approach obliges T1 to read old versions of tuple i. So, EMV2PL serializes T1 before T2. On the other hand DVP dynamically (i.e. during T1 execution) determines that there are no existing conflicts between T1 and T2 transactions and serializes T1 after T2. Therefore, it allows reading of more recent version of i.
The remainder of the paper is organized as follows. Section 2 presents related work. Section 3 provides description of DVP. Section 4 discusses some possibilities of using our approach for query processing. Section 5 contains performance study and shows our protocol to be very efficient for processing concurrent write-then-read transactions. Finally, Section 6 concludes this paper. 2
To address the problem of data contention between
concurrent transactions two-version protocols were
proposed in [
Another approach is a multiversion two-phase locking
(MV2PL) [
Protocols supporting fixed number of versions were
proposed to address some of the issues [
One of the solutions that makes possible efficient
processing of read operations in concurrent transactions is
Snapshot Isolation [
Another approach, which supports processing of
W jR transactions, is EMV2PL [
[
In this section we will describe our protocol. DVP is
an extension to DFV schemes and it uses some details
of their design. The comprehensive description of DFV
can be found in [
DVP is a multiversion protocol. For each data item it maintains several versions. The number of versions for each data item is limited and this limit is a parameter of our protocol. In this paper we assume data items to be pages. Data granulatity is not essential for our protocol, and it can be implemented to be used with records, for example.
Definition 1. Logical snapshot of the database is a collection of versions, one per each data item, that represents transaction-consistent state of the database. Definition 2. Committed version is a version that has been created by now committed transaction.
Some of the versions are used as parts of logical snapshots of the database. Our protocol supports any number of snapshots, but for the sake of clarity we will describe the case of two snapshots. We will refer to them as “current snapshot” (CS) and “previous snapshot” (P S). The former will represent the most recently obtained logical snapshot, and the latter will represent logical snapshot that has been obtained at some moment before the current one.
Each data item can have several types of versions: Definition 3. Last-Committed Version (LCV ) is the most recently committed version of a data item. Definition 4. Working Version (W V ) is a version of a data item that has been created by some not yet committed (i.e. active) transaction.
Definition 5. Previous Version (P V ) is an obsolete committed version of a data item, which has been created before Last Commited Version.
Each data item has at least one version – LCV. If it has some other committed versions, they can be considered as PV versions. Of course, PV versions may not exist at all. For example, when data item has been created and has never been updated since.
If WV version exists, there cannot be another one for the same data item, because active updaters are processed according to S2PL rules, so they cannot obtain Writelocks for the same data item at the same time. For some data items such version, of course, may not exist at all in the case of absence of active transactions that update them. When updater commits, all WV versions it has created are converted into LCV versions, and “old” LCV versions at the same time are converted to PV versions.
So, all versions of a data element can be divided into three categories: W V , LCV and P V . Belonging to a snapshot can be considered as an additional property of a version. For example, version from current snapshot is always labeled as LCV and CS or P V and CS. It cannot be labeled as W V and CS, because W V cannot be part of any snapshot, as such version has not been committed yet.
It is important to mention that these labels are not physically stored on versions. Our protocol identifies version labels using some auxillary structures described below.
To dynamically identify versions DVP uses following structures: list containing active (i.e. not committed) transactions (we will call it ActList), timestamp of version (which is obtained at the moment of creation of version) and version’s creator identifier (which is an identifier of corresponding updater). Timestamp can be represented as some kind of ascending counter. So, when new version is created, its timestamp is assigned counter’s value, and counter itself increments. Creator identifier uniquely identifies transaction that created the version. Each transaction obtains such an identifier at the very start and gives it to every new version it creates.
ActList is a global list, but timestamp and identifier are version-dependent and must be stored for each version (e.g. on a page itself). Below we will describe dynamic approach to identify LCV, WV and PV versions. Dynamic identification of snapshot versions will be described in Section 3.3.
Consider list V , containing metadata (timestamp and creator identifier) about all versions of some data item1. Let’s assume that this list is sorted in descending order by timestamps. We identify versions for each data item as follows: ² WV. This version is always the most recent one.
Thus, it must have the largest timestamp among other versions. So if it exists, it is the first one in V . And this version exists iff there exists an active transaction that updates this data item. Summarizing, if creator identifier of the first version in V lies in ActList then it is a WV version. Otherwise, WV version does not exist. ² LCV. This version is the most recent one among committed versions. So only WV can have larger timestamp. Thus, we have two possibilities here. If WV version exists, then LCV is the second one in V . If WV version does not exist, then LCV is the first one in V , because in this case the data item has only committed versions. ² PV. Previous versions are all versions except LCV and WV. 3.2
Definition 6. W jR-transaction is a transaction that consists of two consecutive phases: write phase containing write and read operations in random order, and second phase containing read operations and write operations on data items only previously updated in the first phase.
On the first phase W jR transaction is processed as an updater according to S2PL protocol. Such transactions always start as updaters and become W jR ones only when they switch to the second phase. So transaction manager (TM) does not need to know in advance that new transaction is W jR one. We will describe updaters processing in Section 3.4. This section and the next one describe design details of the second phase. Efficient proccesing of the second phase of W jR transaction is our main technical contribution.
On the second phase W jR transaction can read any data items, but it can only update pages previouslylocked on the first phase. So it cannot obtain new write locks. Write operations are processed in a usual way, but read ones require different approach. To get performance gains read operations are processed without acquiring any common locks. This could cause a serialization fault, e.g. when the same data item is already acquired for writing. To guarantee serializability we enable 1In our implementation we store list V in the header of the page that represents last version.
W jR transaction to read one of the PV versions. This happens only when read operation of this W jR transaction conflicts with some another operation on the same data item. The meaning and definitions of different types of conflicts will be exlained in the next section.
We use some kind of notifications of read operations, called read-notification-locks (RN-locks). RN-lock is not a lock in the common sense of this word. It is rather some kind of flag that indicates reading of a data item. But this flags can be easily thought of as some type of locks that are compatible with every other types of locks, even with the exclusive ones. So, they can be implemented as a part of a lock manager. That is why we call it this way. To keep information about read operations in the first phase, TM converts usual read locks obtained at the first phase into RN-locks (this operation, of course, can unlock some transactions that have been locked according to S2PL protocol). Before executing each read operation on the second phase, W jR transaction also obtains RN-lock for the corresponding data item. In contrast to S2PL, W jR transactions almost do not experience unnecessary delays, which is a benefit of our approach.
RN-locks provide information about read operations, but to maintain information about concurrent transactions, we need another structure, called F ollowSet. For each W jR transaction T , F ollowSetT stores identifiers of transactions that must be serialized after T . Two main rules about F ollowSet are: ² All transactions that belong to F ollowSetT must be able to see all versions created by T . ² T must not be able to see versions created by transactions from F ollowSetT .
Using this structure TM can easily find version for reading. It just selects the most recent committed version whose creator has not got into F ollowSetT . In this case W jR transaction does not see versions created by transactions that have been serialized after it. Repetitive readings of the same data element by T will affect the same version, because creators of new ones also will be placed into F ollowSetT . Proper maintenance of F ollowSets is essential for efficient processing of W jR transactions. In the next section we will describe this issue in more detail. 3.2.1
In this section we will describe design details for F ollowSets. The main idea is to dynamically determine conflicts between operations of concurrent transactions. Each concurrent transaction that conflicts with W jR transaction T and is serialized after it must be placed in F ollowSetT . Conflicts can be divided into two classes: direct and indirect.
Definition 7. Two operations conflict when they belong to different active transactions, they are on the same data element and one of them is write.
Definition 8. Direct conflict is a conflict between operations of two active concurrent transactions one of which is W jR transaction on its second phase.
Write(x) Write(y) - end of first phase - read operation - write operation
Direct conflict occcurs only when some W jR transaction reads a data element on the second phase while some other transaction updates it. Such conflicts can be easily recognized by TM at the time of locking of data items. This is illustrated by the following example: Example 3. Consider Figure 1. T is a simple W jR transaction, which reads data elements x and y on the second phase, and T 1 is a concurrent updater, which updates this elements. Let’s look at the data item x. Before reading x, T obtains RN-lock. In this case TM determines that x is already locked by T 1. Direct conflict between T and T 1 is recognized and T 1 is placed into F ollowSetT .
Now consider element y. In this case T 1 obtains Write-lock before updating y. Again, direct conflict is recognized, because T is already obtained RN-lock on y, and T 1 is placed into F ollowSetT .
Direct conflict between two W jR transactions can cause a delay at the second phase. Consider W jR transactions T 1 and T 2. T 1 updates some data element x and T 2 reads it (on the second phase). But if at that moment T 2 is already in F ollowSetT 1, then it must read version created by not yet committed T 1. To prevent reading uncommitted data TM delays T 2 until T 1 commits. Definition 9. W jR transaction T and concurrent transaction T 1 conflict indirectly, when they each conflict directly with some other concurrent transaction T 2.
To clarify this definition, consider for example, W jR transaction T and updaters T 1 and T 2. When T 2 conflicts directly with T and T 1 then it causes indirect conflict between T and T 1. Indirect conflicts can be of three types: W-R, W-W and R-W. We describe each type of conflict providing the only possible scenario for each of them to occur:
W-R: W-R conflicts occur due to read-after-write operations on the same element of data. Consider Figure 2(a). Transactions T and T 1 conflict directly on data element x. So T 1 is placed in F ollowSetT . During its execution T 2 reads version of y created by T 1. Hence, it is serialized after T 1 and must be also placed in F ollowSetT . To prevent such conflict, TM obtains information about creator of the version selected for reading and uses it to put transaction in corresponding F ollowSet. For example, when T 2 reads y, TM puts it in F ollowSetT , because creator of the corresponding version T 1 is already in it.
W-W: This type of conflict occurs due to precedence
relation between versions [
R-W: This type of conflict is always due to creating new version of data element that has been read by another transaction. Consider Figure 2(c). Transaction T 2 creates a new version of element y, but when T 1 was reading y it did not see this new version. So T 2 is serialized after T 1 and it also must be placed in F ollowSetT , because T 1 has been put in it. To handle such conflicts TM needs different approach. When some transaction updates data element, TM cannot determine if this element has been read by another already committed transaction. To keep information about read operations of updaters TM uses another technique called Lock Inheritance. When updater commits, TM converts all its read locks into RN-ones and passes them to W jR transactions that contain committed updater in their F ollowSets. Then R-W conflicts can be handled as direct ones. In our scenario, when T 1 commits TM converts read lock on y into RN-lock and passes it to T . When T 2 updates element y direct conflict occurs between T and T 2. TM handles this conflict by putting T 2 into F ollowSetT .
There are some important issues here: ² F ollowSet is used by TM only at the second phase.
So it is always empty at the start of the second phase. ² F ollowSet is used only for W jR transactions and there is no need to maintain such a structure for another type of transactions. ² When TM places some transaction T into F ollowSetT 1 it must also place it in each other F ollowSetT 2 that contains T 1 itself. This happens because T must be serialized after T 1, and T 1 must be serialized after every T 2. Thus, in this case T also must be serialized after every T 2. ² When W jR transaction T is placed in some F ollowSetT 1 the contents of its own F ollowSetT must be placed with it. This happens because F ollowSetT contains transactions that must be serialized after T . So in this case they must be serialized after T 1 too.
The last two actions enforce serializability and are in total consistence with the definition of F ollowSetT as a set containing all transactions that must be serialized after T . 3.3
Queries are transactions that contain only read operations. Since such transactions are processed in a special way, TM must know that a new transaction is indeed a query. For efficient processing of queries DVP maintains some number of logical snapshots. When a new query begins it just starts reading current snapshot, which it cannot change during execution. Moreover, it does not need to acquire any kind of locks, even notification (RN) ones. Since queries do not obtain any locks they also do not participate in any type of conflicts described earlier. So this transactions never experience delays of any kind during their execution.
Logical snapshot is a set of versions that represents transaction-consistent state of the database. This state corresponds to the moment of snapshot’s creation. As a result, versions belonging to snapshot can be slightly obsolete. There exist different approaches to creation of snapshots. The naive one would be to wait for active transactions to finish and to not start new ones. Then, at the moment when there are no active transactions, snapshot can easily be obtained. Such approach is prohibitive in OLTP systems. Instead DVP uses diffirent, dynamic approach that does not require any manipulations with transactions. The main idea of this approach is that TM can dynamically determine versions belonging to snapshots using some simple auxillary structures. Thus, such versions do not differ from the usual ones and version’s metadata (its timestamps and creator’s identifier) can be used to determine if it belongs to some snapshot. For each snapshot TM only needs to store timestamp of its creation (TCS and TP S for our snapshots) and a copy of ActList (ActListCS and ActListP S ). Timestamp of snapshot is a value of the same counter we use for the creation of versions.
Let V represent list of versions ordered by timestamps as described in Section 3.1. Then algorithm to find version belonging to a current snapshot would be: 1. Obtain sublist V 0 of V that contains versions with timestamps less than TCS . 2. Select LCV version from V 0 as described in Section 3.1, using ActListCS .
In fact, V 0 contains versions that existed at the moment of snapshot creation. The problem is that this Write(y) Read(x)
Write(x) T2
Read(x) sublist can contain WV version as well, because TM did not wait until it became committed. That is where ActListCS comes in. Since it is a copy of ActList at the moment of snapshot’s creation, all that TM needs is to select LCV version from V 0. For any other snapshot (e.g. previous one) the procedure would be the same.
To take a new snapshot TM simply must obtain timestamp and a copy of ActList. In this case there is no need to use the naive approach described earlier. However, there are some restrictions here as well.
First of all, to be transaction-consistent snapshot must contain versions from all transactions that had been serialized at the moment of its creation. Since our protocol maintains serializability for W jR transactions in a special way, there is some possibility that creation of a snapshot may be delayed. TM delays snapshot creation only when some W jR transaction is active and its F ollowSet is not empty. Again, there is only one possible scenario for this:
Consider Figure 3. Updater T 1 directly conflicts with W jR transaction T . Hence, it is placed in F ollowSetT and is serialized after T . If TM took snapshot as depicted, it would not contain version of y created by T . Thus, query T 2 would see version created by T 1, but not by T , which is serialized before T 1. When query reads version of some data element, it must be able to read all the versions that have been serialized before this first one. So this snapshot is not transaction-consistent.
Second restriction is due to that the number of snapshots is fixed. If some snapshot is in use by any number of queries, it cannot be replaced by the new one. To be able to take a new snapshot TM must have a free one. New queries always start using current snapshot (i.e. CS version). So if current snapshot is free, TM just takes another one by obtaining timestamp in TCS and copying ActList into ActListCS . But if current snapshot is used by other queries, then it must be kept intact for them. TM uses previous snapshot for this purpose. To backup current snapshot it just copies TCS into TP S and ActListCS into ActListP S . However, if previous snapshot is also in use by other queries, then creation of a new snapshot must be delayed. 3.4
Updaters are transactions that contain read and write operations in random order. They are processed according to S2PL protocol. That means that transactions must acquire read and write locks. As we explained before, when updater commits TM converts all its read locks into notification ones (RN-locks) and passes it to the corresponding W jR transactions. However, there is a restriction imposed on updates by versioning environment. When transaction updates some data element for the first time it creates new version of this element. That is not a problem when number of versions is unrestricted. In our case, though, this number is fixed and TM must choose a version for replacement.
LCV versions cannot be overwritten because they are the only source of previous versions. If TM replaced LCV versions, it would eliminate versioning at all and DVP would become similar to S2PL. PV versions, however, can be considered for replacement. But we have several limitations here as well: 1. PV version that belongs to the current snapshot cannot be replaced, because current snapshot is used by new queries. 2. PV version that is read now by some active W jR trasaction cannot be replaced. 3. PV version that might be read by some active W jR transaction in the future cannot be replaced by now. We call such situation a potential reading. If TM chose to replace such version, in the future W jR transaction might find no version at all. 4. PV version that belongs to a previous snapshot can be replaced, if there are no queries that use this previous snapshot. Of course, in this case we must consider three aforementioned limitiations as well.
Thus, TM can only replace PV versions that satisfy this restrictions. In the case of potential reading it acts as if W jR transaction is already reading this item. So, if it creates a new version for data item x, for every active W jR transaction it must determine the version of x it is reading now or may be reading later using F ollowSet as described in Section 3.2.
If version for replacement exists then it is replaced by the new one. Otherwise updater must wait for some version to become free. It is important that updater will not be locked permanently, because new transactions do not use PV or PS versions and old transactions will eventually finish. In this case some version will become free and updater will be unblocked. 3.5
Theorem 1. DVP guarantees serializability of all transactions.
We provide the proof for this theorem in Appendix A. Note, that serializability is the key issue for any protocol. Many applications rely on serializability and cannot simply sacrifice it for perfomance gains. 3.6
Theorem 2. W jR transactions cannot experience deadlocks during the second phase.
The proof for this theorem can also be found in Appendix A. This is a very important result. It can significantly increase transaction throughput in the situations with strong data contention between concurrent transactions. We will discuss this issue in the light of experimental results. 4
W jR transaction as a query In this section we discuss the possibility of using W jR transactions as queries. W jR transaction is similar to query when its first phase contains no operations. In this case it is transfered to the second phase right at the start, and because W jR transaction cannot acquire write locks on the second phase, it can only read data. The main difference is that such W jR transaction still has to obtain RN-locks. As a result, it can participate in some of the aforementioned conflicts. But at the same time it uses dynamic approach to find suitable version for reading. Query, on the other hand, uses snapshot, which is completely defined at the moment of querie’s start. Moreover, such snapshot cannot be updated if some longrunning queries are keeping busy all snapshots, because their number is fixed. Hence, new queries would have to read obsolete versions of the pages. Dynamic approach can yield some benefits in such a case, because it selects version based on current situation, and it is independent of concurrent long-running queries.
Using W jR transactions as queries has its own drawbacks. As we mentioned before, if some version has been (or will be) used by some active W jR transaction, it cannot be replaced by a new one. This creates a potential bottleneck for updaters. If number of such W jR-query transactions is high enough, they might cover all versions and updaters might experience delays. It may happen with usual W jR transactions too, but their second phase’s length generally is not big enough to cause any serious delays. However, in many cases even such delays might not be such a major drawback. In other multiversion protocols queries can be started as updaters. In this case they read the most recent versions. But at the same time they must acquire read locks, and, as a result, they experience delays. Such queries-updaters can even become deadlock victims. W jR-query transaction, on the other hand, does not acquire any read locks and cannot experience deadlocks. Thus, its performance can be significantly better than querie-updater’s. So such W jRquery transactions represent some kind of trade-off between performance of updaters and reading of less obsolete versions. 5
We have developed prototype to conduct experimental evaluation of our protocol. This prototype simulates the work of the buffer manager, the version manager and the lock manager. Each transaction consists of write and read operations on the data elements, which in our experiments are pages. It is important to mention that since all protocols were tested on the same prototype, the possible implementation details of this prototype should not influence the results.
We compared DVP with two other protocols: multiversion DFV and nonversion S2PL. Comparision with DVP S2PL DFV S2PL allows us to study benefits of versioning approach in processing of W jR and other types of transactions. But our main goal is to test our protocol against DFV, which also supports queries, STEAL policy and limited number of versions per each data item. It does not support W jR transactions, however, which allows us to study benefits of our approach. In this experiment we compare multiversion algorithms (DVP and DFV) with usual (S2PL) in the case when strong data contention between queries and updaters exists. Our workload contains 25% of queries and 75% of updaters running concurrently. Selectivity factor for queries is varied from 2% to 80% of the database, but within the same experimental run it stays fixed. Updaters, on the other hand, are short, containing only three write operations. This allows us to reduce data contention between them. In this case almost all conflicts are between queries and updaters. Write actions for updaters are generated randomly, while queries always read some continuous region of the database.
Figure 4 shows updater throughput. As we can see, for multiversional DVP and DFV queries selectivity is not an issue. Queries just read snapshots, while updaters write new versions. Updaters do not experience any unnecessary delays, because they do not intersect with queries. Any updaters delays would be because of data contention between updaters themselves, but we have reduced it to minimum by allowing them only three operations. Data contention becomes a problem for S2PL, though. In this case queries and updaters read the same pages. In fact, queries are executed as an updaters here, obtaining read lock before each read operation. It does not create any problems when query selectivity is about 2%, because in this case queries are relatievely small and data contention is not high enough to cause problems. However, increasing query selectivity also increases execution time of queries and data contention. Queries hold read locks for a considerable ammount of time, and, according to S2PL protocol, updaters that read the same pages have to wait for this locks to be released. At 80% selectivity almost all new updaters conflict with queries DVP S2PL DFV 0 0 10 20
30 40 50 Query selectivity, % 60 70 80 and, as a result, spend most of the time waiting for them. This results to a very poor performance of updaters under S2PL.
Figure 5 shows query throughput. DVP and DFV process queries in a similar manner, and, as a result, query throughputs for this two algorithms are almost equal. Again, S2PL loses to multiversion algorithms. In fact, this experiment compares overhead of query processing for S2PL and multiversion algorithms. For S2PL overhead consists of locking needed pages and possible waiting for concurrent updaters. For multiversion algorithms overhead includes one possible additional read operation on each basic read. This additional operation occurs when query reads old version of a page. In this case query first reads LCV version, which contains information about all remaining versions, determines version for reading and reads it. If LCV version is a suitable version itself, no additional read occurs. As we can see on Figure 5, S2PL overhead exceeds multiversion one, and, as a result, query throughput is lower for S2PL.
Our first experiment shows that multiversion environment has benefits in both query and updater processing. It offers better query throughput, which can be an important issue for some applications. More importantly, it offers significantly better updater throughput, which is important for efficient OLTP. This experiment shows benefits of our protocol in W jR transactions processing. The whole workload entirely consists of W jR transations. Each transaction executes randomly generated read and write operations. Data contention between transactions is very high in this experiment, and rollbacks are relatively common. If some transaction is rolled back, it must be restarted. As a result, W jR transaction may start several times before it is committed. We vary relative second phase length in this experiment, which is measured as a ratio of number of operations at the second phase to the total number of operations. As in the previous experiment, it stays fixed on each run.
W jR transactions are processed as usual updaters according to DFV and S2PL, and relative second phase length does not have an impact on the throughput. Be1.3 1.25 cause of severe data contention, transactions experience frequent rollbacks and delays under S2PL and DFV. As a result, throughput of W jR transactions for this protocols is not high. That is not an issue for DVP. First of all, as on the second phase W jR transactions do not acquire any read locks, they would not experience any unnecessary delays. Second, as we stated in first theorem of Section 3.5, W jR transactions do not experience deadlocks at the second phase and, as a result, number of rollbacks dramatically decreases.
Relative number of rollbacks is shown in Figure 6. It is measured as a ratio of number of rollbacks to total number of transactions. If some transaction is rolled back several times, only one rollback counts. As we can see, under S2PL and DFV transactions are indeed rolled back often. On the other hand, under DVP number of rollbacks is significantly lower, and at 60% length rollbacks are almost eliminated.
In this section we evaluate the possibility of using W jR transactions as queries. The main idea was described in Section 4. Workload consists 40% of read-only transactions and 60% of updaters. In this experiment we vary average selectivity of read-only transactions. In contrast to the first experiment, for each run selectivities of different transactions are uniformly distributed around some fixed point. For each such point we conduct two tests using DVP protocol. In the first one read-only transactions are represented as W jR transactions, and in the second they are executed as queries. In this experiment we also study the effect that high number of W jR transactions has on throughput of updaters. This effect was described in Section 4. Again, updaters in this experiment are relatievely short (with several write operations). This allows us to avoid conflicts between them, and we can more accurately evaluate relationships between updaters and queries/W jR transactions.
First of all we want to discuss the weighted reading of versions. This parameter allows us to evaluate the novelty of read versions. Weighted reading is a ratio of weighted version count (W V C) to total number of read pages. Weighted version count increases with each reading of version:
W V C = W V C + 8 1 >< 2
::: > : n for LCV version for version next to LCV for nth version
In some protocols information about versions is stored as some sort of distributed list: version keeps information about the next version. In this case W V C would define real number of read pages, and weighted reading would measure an average number of readings per one read operation. Again, for updater value of this parameter is equal to 1, because it always reads LCV versions. Figure 7 shows us the results. In this case, due to the nature of W V C, the smaller the value, the better. We can see here that dynamic approach leads during this experiment. The cause is that queries are bound to snapshots, while dynamic approach takes into consideration current situation. Also, we can see that after 25% mark, weighted access for W jR transactions grows much slower than for queries. This is caused by slow update rates of snapshots: long queries with large selectivities keep snapshots busy and prevent them from update. As a result, queries read much more obsolete versions. For mentioned above protocols with distributed version information storing using queries would yield an additional readings per operation to find suitable version.
The next parameter we want to discuss is throughput of updaters. In Section 4 we mentioned the main problem that can occur when W jR transactions are used as queries: updater’s delays. Consider Figure 8, which shows throughput results. As we can see, queries have no impact on updaters processing. With queries, updaters always have versions for replacement. So they experince almost no delays, except that are caused by conflicts with another updaters. W jR transactions are a different matter though. When average selectivity is not very high, updater throughput is almost equal to the throughput with queries. This is because length of W jR transactions does not cause any significant delays yet. But then situation changes. With the increase of average selectivity, W jR transactions become longer. As a result they can keep busy all the versions of some data items for some amount of time, and updaters have to wait for replacement versions. Similar situation would occur with any nonversion protocol, such as S2PL, when updaters would wait for other transactions. Here, we must choose between novelty of read versions and possible deterioration of concurrent updaters. Different systems can require different approaches.
This last experiment clearly shows benefits of our dynamic approach. W jR transactions read more recent versions, because they are not bound to some statical structures, like snapshots. Hence, they can yield significant benefits to read-only transactions. If performance of updaters is an important issue (i.e. in OLTP systems), our protocol offers an alternative: snapshot queries. 6
In this paper we presented a new multiversion approach, called dynamic versioning protocol (DVP), which supports efficient processing of W jR transactions. DVP allows W jR transactions to release all their read locks before start of the second phase, and, as a result, during this phase they execute read operations without taking new read locks and cannot experience deadlocks. Our protocol uses dynamic approach to determine which versions to read on the second phase. This approach is based on evaluation of current situation and discovering existing conflicts, which results in reading much more recent versions. For queries, DVP uses dynamically derived snapshots, which are obtained and advanced without need to interrupt transaction processing. One of the important features of our protocol is support of STEAL policy, which allows dirty pages to be written back on disk without need to wait for commit. Also, DVP maintains fixed number of versions, which greatly simplifies version management and reduces storage overhead.
Then we discussed some interesting application of W jR transactions to query processing. The main idea is that W jR transactions with empty first phase can represent read-only transactions. The main benefit of such approach is that W jR transactions generally read more recent versions than queries. However, such processing may result in slight decrease of performance, because W jR transaction can experince rare delays during the second phase. Thus, DVP allows choosing between performance with queries and reading more recent data with W jR transactions. 45 50
We conducted experimental evaluation of DVP. First of all, processing of second phase of W jR transactions without read locks can yield significant benefits in W jR throughput. Furthermore, the third experiment shows that our dynamic approach results in selecting much more recent versions for reading. This confirms that DVP can provide an efficient solution to the problem of processing of W jR transactions.
Finally, we proved the correctness of our protocol. Correctness means that DVP allows serializable execution of concurrent transactions, which is a very important feature of our protocol.
A
In this section we will prove two theorems from Sections
3.5 and 3.6. We will be using elements of standard
multiversioning theory, which can be found in [
First of all, we can define precedence relation between every two versions of some data item x. xi precedes xj (xi Á xj ) iff xi was created before xj . This order is well-defined because DVP processes updaters according to the S2PL rules. In this case xj can be created only when xi has already been committed.
Consider MVSG G. Its vertices represent transactions of three different types: W jR, W (updater) and R (query). It also can contain edges of three types: 1. Ti !1 Tj : That means that Tj reads version of some data item, created by Ti. xi. In this case this edge is drawn: Tk !2 Tj : xj . In this case this edge is drawn: Ti !3 Tj :
First we examine some of the properties of MVSG under DVP. We formulate them in the form of lemmas. In this lemmas, F Si denotes F ollowSet of transaction Ti. oi defines commit operation for transactions of W -type and W jR-type. For transactions of R-type it defines its first read operation. Operations are processed in welldefined order. This implies that for each pair of operations oi and oj , either oi < oj or oi > oj .
1 2 Lemma 1. Let Ti ! Tj ! Tk, where Tj is of R-type. Then, oi < ok.
Proof. This follows from procedure of snapshot’s creation. According to this procedure Ti must be committed before snapshot’s creation, and Tk is committed after that. Otherwise, its versions would have belonged to 2 the snapshot, and Tj ! Tk wouldn’t have been possible.
Lemma 2. This lemma consists of two parts: 1;3 1. Let Ti ! Tj . Then, oi < oj .
2 2. Let Ti ! Tj , where Ti is not of W jR-type or Rtype. Then, also, oi < oj .
Proof. This property follows strictly from S2PL locking rules.
Lemma 3. Let Ti ! Tj ! Tk, Tj 2 F Si and Tk is not of R-type. Then, if ok < oi, then Tk 2 F Si.
Proof. Tk conflicts indirectly with Ti through Tj . DVP handles such conflicts by putting Tk in F Si.
Lemma 4. Let Ti 2 F Sj . Then situation Ti ! Tj is not possible.
Proof. Examine the possibility of edges of different types:
1 1. Ti ! Tj is not possible, because transaction cannot read version, created by transaction from its F ollowSet. 2. Ti !2 Tj is not possible. If Ti is of W -type, then it would have committed before corresponding write operation of Tj and could not have belonged to F Sj . If Ti is of W jR-type, then, according to DVP rules, it would have been blocked until completion of Tj . In this case it would have read version created by Tj .
3 3. Ti ! Tj is similar to the first part of the previous case: Ti would have committed before corresponding write operation of Tj .
F Sk. Then, situation Tj !2 Tk is not possible. Proof. In this case we have active W jR transaction Tk with some transaction in its F ollowSet. In this case snapshot could not have been obtained, according to DVP rules. So situation Tj !2 Tk is not possible. Lemma 6. Let Ti ! : : : ! Tj ! Tk ! Tl, where Tk is of R-type and Tj 2 F Si. Then oi < ol.
Proof. Since Tk reads snapshot, and versions from Tk are in this snapshot, then Ti would have committed before snapshot’s creation. This is ensured by DVP rules for snapshot creation. But versions from Tl are not in this snapshot, and that means Tl would have committed after snapshot’s creation. This implies oi < ol. Lemma 7. If there is a cycle in MVSG, it cannot contain any W jR transactions.
Proof. Let’s assume that cycle with W jR transactions exists: T 1 ! T 2 ! : : : ! Ti1 ! : : : ! Ti2 ! : : : ! Tik ! : : : ! Tn ! T 1. Consider three general cases: 1. o1 < o2 < : : : < oi1 ; Ti1 is a W jR transaction and Ti1+1; : : : ; Ti2¡1 2 F Si1 . Then, again, oi1 < oi2 (notice, that we also have o1 < oi2 here), and oi2 < oi2+1 and so on (we use Lemmas 1-3 here). Similar to o1 < oi2 , we can derive that o1 < oi1 < : : : < oik . Then we have following possibilities: (a) Tn; : : : ; Tik+1 2 F Sik . In this case we also have o1 < oik ; o2 < oik ; : : : ; oi1 < oik . Then, T1; T2; : : : ; Ti1 2 F Sik (Lemma 3). But this implies that Ti1 ; : : : ; Ti2¡1 2 F Sik , and so on. We can receive only situations, described in Lemmas 46 here: Lemma 4 (Tik¡1 2 F Sik ), Lemma 5(Tik¡2 2 F Sik and Tik¡1 is of R-type) and Lemma 6(for example, for some R transaction Tk where k 2 [1; i1]; in this case we would receive oik < ok+1, but at the same time ok+1 < oik in our general case). (b) oik < oik+1 < : : : < on and Tn is of W type or W jR-type. In this case we can derive that either on < o1 (Tn is of W -type; or Tn is 1;3 W jR transaction and Tn ! T1) or T1 2 F Sn 2 (Tn is W jR transaction and Tn ! T1). In the first case we already have o1 < on, which contradicts to on < o1. The second case is equal to 1a, where ik = n. (c) oik < oik+1 < : : : < on¡1 and Tn is of Rtype. In this case we can derive that on¡1 < o1 (Lemma 1). But at the same time we have o1 < on¡1 - contradiction. (d) Tik+1; : : : ; Tn¡1 2 F Sik and Tn is of R-type.
In this case oik < o1. But we already have o1 < oik - contradiction. 2. T2; : : : ; Ti1¡1 2 F S1, o1 < oi1 < oi1+1 < : : : < oi2 and so on. This case is similar to the first general one with the same four possibilities. In fact, we can consider it as the first general case with Ti1 = T1.
Not one of this three general cases is possible, and they include all possible cycles with W jR transactions. So we can derive that such cycles are prohibited. Lemma 8. If there is a cycle in MVSG, it cannot contain any W transactions.
Proof. Consider possible cycle in MVSG: T1 ! T2 ! : : : ! Tn ! T1, where T1 is of W -type. First of all, according to the previous lemma, it cannot contain any W jR transactions. So this cycle can contain only transactions of W -type and R-type. According to Lemmas 1 and 2, we can only derive that o1 < o1, which is impossible. So cycles with W transactions are prohibited. Theorem 3. DVP guarantees serializability of all transactions.
Proof. According to the previous two lemmas, if there existed any cycle in MVSG, then it could not contain W and W jR transactions. But in this case we could receive cycle containing only R-type transactions, which is impossible, because R transactions cannot be adjacent to each other in MVSG.
Next, we will prove that W jR transactions cannot experience deadlock situations on the second phase. Lemma 9. Let Ti 2 F Sj . Then Tj 2= F Si.
Proof. If Ti 2 F Sj , then, according to DVP, in the situation that could lead to Tj 2 F Si, Ti would be blocked until completion of Tj . So it cannot occur that Tj 2 F Si.
Theorem 4. W jR transactions cannot experience deadlocks during the second phase.
Proof. Since W jR transactions, according to DVP, can wait for only another W jR transactions, deadlock cycle can contain only W jR transactions. Consider such cycle: T 1 ! T 2 ! : : : ! Tn ! T 1. If Ti waits for Tj , then Ti 2 F Sj . But for our cycle we would receive that Tn 2 F S1 and T1 2 F Sn, which contradicts with Lemma 9. So such deadlock cycles are prohibited.