Transactions on Objects

So far, we have considered concurrency schemes for synchronizing accesses to shared databases - that is, shared objects supporting only read/write operations. Object transactions are concurrency schemes for synchronizing accessed to shared objects on which arbitrary operations can be supported.

How should concurrency schemes be adapted when accesses are made to shared objects? The answer depends on how much of the application semantics is available to the concurrency scheme. To understand the nature of such a concurrency scheme, let us introduce the notion of a dependency relation, D (X,Y), which is a relation formed between transactions based on the order in which they execute certain kinds of operations, defined by X and Y, on a shared object. A transaction Tj depends on transaction Ti with respect to a dependency relation D(X,Y) Ti <D(X,Y) Tj

if Ti performs an X operation before Tj performs a Y operation.

Consider first the situation when the concurrency scheme has no semantic information, that is, has no information regarding the effect of an operation on an object. In this situation, we must assume that an operation can perform arbitrary actions. Let us define one operation kind, any, and the dependency relation: D = D(any, any)

Then, a transaction schedule is serializable if this dependency relation does not introduce any cycles, that is, if transaction Ti performs an operation on an object before transaction Tj, then Tj does not perform an operation on the object before transaction Ti.

Also, assume that we wish to prevent cascaded aborts. Then we need to ensure that a transaction performs an operation on a shared object only if all transactions that have accessed the object have committed.

Now assume that we know which operations are reads and which are writes. We can define four dependency relations:

D1 = D(R, R)
D2 = D(R, W)
D3 = D(W, R)
D4 = D(W, W)

To ensure that there are no cascaded aborts, we have to ensure only that no D3 dependencies exist among overlapping transactions, which is again more liberal than ensuring no dependencies exist.

Finally, assume that we know type-specific semantics of the operations. In this case, it is possible that we can have an even more liberal scheme for ensuring serializability and no cascading aborts. Consider the example of a queue supporting the QEnter (q, e) (abbreviated as E(e)), and QDelete (q) (denoted below as D(e)), where e is the ID of the element inserted/deleted. Each element is assumed to have a unique ID assigned when it is entered into the queue. We can define the following dependency relations:

D1 = D (E(e), E(e'))
D2 = D (E(e), D(e'))
D3 = D (E(e), D(e))
D4 = D (D(e), E(e'))
D5 = D (D(e), D(e'))

If we were to model QEnter as a write and QDelete as a read followed by a write, then this schedule would not have been allowed. Since T1 <D2 T2 dependency is insignificant, this schedule is indeed serializable. Similarly, to prevent cascaded aborts, we have to ensure no D3 and D5 dependencies occur among interleaving transactions. The dependency D1 is insignificant since it is similar to the W,W dependency.

A locking-based scheme for supporting this scheme must support locks of the form LockClass(data) where LockClass corresponds to operation type and data corresponds to explicit or implicit operand of the operation. The compatibility matrix of Figure 9 describes a locking scheme for Queues:

Here we assume, that QEnter must ask for a lock on the element to be added, which is held till the end of transaction to avoid cascaded aborts. Similarly, QDelete must ask for a lock on the head of the queue, which is also held until end of transaction. This scheme allows a transaction entering items to interleave its steps with one removing items.

We may further refine our transaction model by defining a weaker notion of consistency than serializability. This constraint is too strong in some situations. Let us return to our example of queues. We may want to use the queue as simply a buffer between producer and consumer processes. FIFO queues used as buffers ensure that items are removed in the order in which they are entered. We may be satisfied with weakly-FIFO queues-- queues that allow items to be removed out of order but ensure there is no starvation - that is, an inserted item will eventually be removed by moving to the front of the queue and when it does so, it will be eventually removed. This may be useful, for example, when the buffer items are independent jobs to be executed by the consumers that are created by the producers. For such data structures, we can ignore the D1 and D5 conflicts, that is, we can allow transactions to overlap their entries and removals in a non-serial way. Thus, the only relationship we serialize is the D3 relationship to avoid cascaded aborts and to order transactions synchronizing on queue items. The locking scheme changes to Figure 10:

This scheme allows transactions entering and deleting items to interleave their steps but is not serializable. To prevent cascaded aborts and order transactions synchonizing on a queue item, a transaction is not allowed to dequeue an element enqueued by an uncommitted transaction. A modified queue remove is supported to increase the concurrency in the system: If the entry at the front of the queue has been entered by an uncommitted transaction, then it is not removed to avoid cascaded aborts. Entries behind it are searched in the order in which they were entered for a committed one, and that is removed. If no committed entry is found, then the queue is searched for an entry made by the removing transaction, and that entry is removed. If no such entry is also found, then the remove operation blocks.

This scheme allows:

entries made by a transaction to be interleaved in the queue,

dequeue order of items entered by the same transaction to be different from enqueue order.

The order depends on the commitment and abort order among (a) the enqueues, (b) dequeus, (c) dequeues and enqueues. As in a traditional queue, it also depends on the order in which the items were dequeued.

Let us take some examples:

Assume a queue is empty, and T1 adds item a and then T2 adds item b and then T1 adds item c. The queue is now: [a[1], b[2], c[1]], where i[j] says item i entered by Tj has not been committed. Now if they both commit, the queue is: (a, b, c). Thus, serializability of the queue is not maintained.

Now let us say transaction T3 removes the item at the front of the queue, and then T4 removes the next two items. The queue is now: [a(3), b(4), c(4)]. (i(j) says item i has been removed by uncommitted transaction Tj.) If now T3 aborts and T4 commits, the queue becomes: a. Thus, c is removed from the queue before a, even though it was inserted after it by the same transaction!

Consider another situation: [a[5], b[6]]. If T6 commits, the queue is: [a[5], b]. Now if T7 dequeues and commits, and then T5 commits, the queue is: [a]. Thus, as before, b is removed before a though it was added after it. The two items are removed in order in which their enquing transactions committed.

If in above, T6 commits after T5, but both commit before T7 dequeues, the queue is: [b]. Thus, items are not always removed in the enqueue commitment order.

Though items are removed out of order, no item remains in the Q forerever as long as:

the transaction that enters an item takes a finite amount of time to finish successfully (without abort).

a transaction that tries to remove an item takes a finite amont of time to finish successfully (without abort).

only a finite number of transactions that try and remove a queue item abort.