Joining transactions

Copyright 2011 © Gabriel Zs. K. Horvath

Up to now all the transactions have been running in independent threads. There hasn’t been any mention of sub-transactions or the possibility of joining threads.

Sub-transactions

Since all variables within a transaction are immutable, it is meaningless to think in terms of sub-transactions which commit changes. Instead we can have multiple threads running concurrently within a single transaction and merge the recorded write operations of the various threads when joing the threads. Since the threads within the same transaction must still register all the reads and writes independently of the main transaction they are equivalent to normal transactions which happen to share the same version number as the main transaction. So far my model has no concept of sub transactions.

Joining and merging

Any two transactions can be combined in two different ways:

• join: a transactions integrates another one so that the writes from the joining transactions are treated as last-write-wins. The reads from both transactions will require validation.
• merge: two transactions join up symmetrically under the condition that there are no conflicting write operations between the two joining transactions, the writes from both transactions are merged together. The reads from both transactions will require validation.

These two options are depicted in the following diagram:

There is no restriction on the data passed across transactions when a transaction is merged or integrated. Note that consistency is only preserved if both transactions are contemporary, i.e. they have the same version number.

Write conflicts

Non-commutative writes will result in write conflicts. For example incrementing a counter is commutative, so that increment operations performed on multiple threads can simply be merged together when the threads join. The Add and Remove operations on a set do not commute, so that two transactions where one has added an element and the other one removed the same element cannot be merged as their operations conflict. Two threads which have performed conflicting operations on the same variable cannot be merged together.

Rejuvenation

An older transaction can be rejuvenated by performing a validation of the reads to a target version.

Conclusion

The simplicity with which transactions can be merged stems essentially from the semi-mutability of the variables.