Transactional Memory Bibliography Template

In computer science and engineering, transactional memory attempts to simplify concurrent programming by allowing a group of load and store instructions to execute in an atomic way. It is a concurrency control mechanism analogous to database transactions for controlling access to shared memory in concurrent computing. Transactional memory systems provide high level abstraction as an alternative to low level thread synchronization. This abstraction allows for coordination between concurrent reads and writes of shared data in parallel systems.[1]

Motivation[edit]

In concurrent programming, synchronization is required when parallel threads attempt to access a shared resource. Low level thread synchronization constructs such as locks are pessimistic and prohibit threads that are outside a critical section from making any changes. The process of applying and releasing locks often functions as additional overhead in workloads with little conflict among threads. Transactional memory provides optimistic concurrency control by allowing threads to run in parallel with minimal interference.[2] The goal of transactional memory systems is to transparently support regions of code marked as transactions by enforcing atomicity, consistency and isolation.

A transaction is a collection of operations that can execute and commit changes as long as a conflict is not present. When a conflict is detected, a transaction will revert to its initial state (prior to any changes) and will rerun until all conflicts are removed. Before a successful commit, the outcome of any operation is purely speculative inside a transaction. In contrast to lock-based synchronization where operations are serialized to prevent data corruption, transactions allow for additional parallelism as long as few operations attempt to modify a shared resource. Since the programmer is not responsible for explicitly identifying locks or the order in which they are acquired, programs that utilize transactional memory cannot produce a deadlock.[2]

With these constructs in place, transactional memory provides a high level programming abstraction by allowing programmers to enclose their methods within transactional blocks. Correct implementations ensure that data cannot be shared between threads without going through a transaction and produce a serializable outcome. For example, code can be written as:

deftransfer_money(from_account,to_account,amount):withtransaction():from_account-=amountto_account+=amount

In the code, the block defined by "transaction" is guaranteed atomicity, consistency and isolation by the underlying transactional memory implementation and is transparent to the programmer. The variables within the transaction are protected from external conflicts, ensuring that either the correct amount is transferred or no action is taken at all. Note that concurrency related bugs are still possible in programs that use a large number of transactions, especially in software implementations where the library provided by the language is unable to enforce correct use. Bugs introduced through transactions can often be difficult to debug since breakpoints cannot be placed within a transaction.[2]

Transactional memory is limited in that it requires a shared-memory abstraction. Although transactional memory programs cannot produce a deadlock, programs may still suffer from a livelock or resource starvation. For example, longer transactions may repeatedly revert in response to multiple smaller transactions, wasting both time and energy.[2]

Hardware vs. software[edit]

The abstraction of atomicity in transactional memory requires a hardware mechanism to detect conflicts and undo any changes made to shared data.[3] Hardware transactional memory systems may comprise modifications in processors, cache and bus protocol to support transactions.[4][5][6][7][8] Speculative values in a transaction must be buffered and remain unseen by other threads until commit time. Large buffers are used to store speculative values while avoiding write propagation through the underlying cache coherence protocol. Traditionally, buffers have been implemented using different structures within the memory hierarchy such as store queues or caches. Buffers further away from the processor, such as the L2 cache, can hold more speculative values (up to a few megabytes). The optimal size of a buffer is still under debate due to the limited use of transactions in commercial programs.[3] In a cache implementation, the cache lines are generally augmented with read and write bits. When the hardware controller receives a request, the controller uses these bits to detect a conflict. If a serializability conflict is detected from a parallel transaction, then the speculative values are discarded. When caches are used, the system may introduce the risk of false conflicts due to the use of cache line granularity.[3]Load-link/store-conditional (LL/SC) offered by many RISC processors can be viewed as the most basic transactional memory support; however, LL/SC usually operates on data that is the size of a native machine word, so only single-word transactions are supported.[4] Although hardware transactional memory provides maximal performance compared to software alternatives, limited use has been seen at this time.

Software transactional memory provides transactional memory semantics in a software runtime library or the programming language,[9] and requires minimal hardware support (typically an atomic compare and swap operation, or equivalent). As the downside, software implementations usually come with a performance penalty, when compared to hardware solutions. Hardware acceleration can reduce some of the overheads associated with software transactional memory.

Owing to the more limited nature of hardware transactional memory (in current implementations), software using it may require fairly extensive tuning to fully benefit from it. For example, the dynamic memory allocator may have a significant influence on performance and likewise structure padding may affect performance (owing to cache alignment and false sharing issues); in the context of a virtual machine, various background threads may cause unexpected transaction aborts.[10]

History[edit]

One of the earliest implementations of transactional memory was the gated store buffer used in Transmeta's Crusoe and Efficeon processors. However, this was only used to facilitate speculative optimizations for binary translation, rather than any form of speculative multithreading, or exposing it directly to programmers. Azul Systems also implemented hardware transactional memory to accelerate their Java appliances, but this was similarly hidden from outsiders.[11]

Sun Microsystems implemented hardware transactional memory and a limited form of speculative multithreading in its high-end Rock processor. This implementation proved that it could be used for lock elision and more complex hybrid transactional memory systems, where transactions are handled with a combination of hardware and software. The Rock processor was canceled in 2009, just before the acquisition by Oracle; while the actual products were never released, a number of prototype systems were available to researchers.[11]

In 2009, AMD proposed the Advanced Synchronization Facility (ASF), a set of x86 extensions that provide a very limited form of hardware transactional memory support. The goal was to provide hardware primitives that could be used for higher-level synchronization, such as software transactional memory or lock-free algorithms. However, AMD has not announced whether ASF will be used in products, and if so, in what timeframe.[11]

More recently, IBM announced in 2011 that Blue Gene/Q had hardware support for both transactional memory and speculative multithreading. The transactional memory could be configured in two modes; the first is an unordered and single-version mode, where a write from one transaction causes a conflict with any transactions reading the same memory address. The second mode is for speculative multithreading, providing an ordered, multi-versioned transactional memory. Speculative threads can have different versions of the same memory address, and hardware implementation keeps track of the age for each thread. The younger threads can access data from older threads (but not the other way around), and writes to the same address are based on the thread order. In some cases, dependencies between threads can cause the younger versions to abort.[11]

Intel's Transactional Synchronization Extensions (TSX) is available in some of the Skylake processors. It was earlier implemented in Haswell and Broadwell processors as well, but the implementations turned out both times to be defective and support for TSX was disabled. The TSX specification describes the transactional memory API for use by software developers, but withholds details on technical implementation.[11]

As of GCC 4.7, an experimental library for transactional memory is available which utilizes a hybrid implementation. The PyPy variant of Python also introduces transactional memory to the language.

Available implementations[edit]

See also[edit]

References[edit]

  1. ^Harris, Tim; Larus, James; Rajwar, Ravi (2010-06-02). "Transactional Memory, 2nd edition". Synthesis Lectures on Computer Architecture. 5 (1): 1–263. doi:10.2200/S00272ED1V01Y201006CAC011. ISSN 1935-3235. 
  2. ^ abcd"Transactional Memory: History and Development". Kukuruku Hub. Retrieved 2016-11-16. 
  3. ^ abcSolihin, Yan (2016). Fundamentals of Parallel Multicore Architecture. Berkeley, California: Chapman & Hall. pp. 287–292. ISBN 978-1-4822-1118-4. 
  4. ^ abHerlihy, Maurice; Moss, J. Eliot B. (1993). "Transactional memory: Architectural support for lock-free data structures"(PDF). Proceedings of the 20th International Symposium on Computer Architecture (ISCA). pp. 289–300. 
  5. ^"Multiple Reservations and the Oklahoma Update". doi:10.1109/88.260295. 
  6. ^Hammond, L; Wong, V.; Chen, M.; Carlstrom, B.D.; Davis, J.D.; Hertzberg, B.; Prabhu, M.K.; Honggo Wijaya; Kozyrakis, C.; Olukotun, K. (2004). "Transactional memory coherence and consistency". Proceedings of the 31st annual International Symposium on Computer Architecture (ISCA). pp. 102–13. 
  7. ^"Unbounded transactional memory". 
  8. ^"LogTM: Log-based transactional memory"(PDF). WISC. 
  9. ^"The ATOMOΣ Transactional Programming Language"(PDF). Stanford. 
  10. ^Odaira, R.; Castanos, J. G.; Nakaike, T. (2013). "Do C and Java programs scale differently on Hardware Transactional Memory?". 2013 IEEE International Symposium on Workload Characterization (IISWC). p. 34. doi:10.1109/IISWC.2013.6704668. ISBN 978-1-4799-0555-3. 
  11. ^ abcdeDavid Kanter (2012-08-21). "Analysis of Haswell's Transactional Memory". Real World Technologies. Retrieved 2013-11-19. 
  12. ^"IBM plants transactional memory in CPU". EE Times. 
  13. ^Brian Hall; Ryan Arnold; Peter Bergner; Wainer dos Santos Moschetta; Robert Enenkel; Pat Haugen; Michael R. Meissner; Alex Mericas; Philipp Oehler; Berni Schiefer; Brian F. Veale; Suresh Warrier; Daniel Zabawa; Adhemerval Zanella (2014). Performance Optimization and Tuning Techniques for IBM Processors, including IBM POWER8(PDF). IBM Redbooks. pp. 37–40. ISBN 978-0-7384-3972-3. 
  14. ^Wei Li, IBM XL compiler hardware transactional memory built-in functions for IBM AIX on IBM POWER8 processor-based systems
  15. ^Java on a 1000 Cores – Tales of Hardware/Software CoDesign on YouTube
  16. ^"STMX Homepage". 
  17. ^Wong, Michael. "Transactional Language Constructs for C++"(PDF). Retrieved 12 Jan 2011. 
  18. ^"Brief Transactional Memory GCC tutorial". 
  19. ^"C Dialect Options - Using the GNU Compiler Collection (GCC)". 
  20. ^"TransactionalMemory - GCC Wiki". 
  21. ^Rigo, Armin. "Using All These Cores: Transactional Memory in PyPy". europython.eu. Retrieved 7 April 2015. 
  22. ^"picotm - Portable Integrated Customizable and Open Transaction Manager". 
  23. ^"Concurrent::TVar". 

Further reading[edit]

  • Harris, Tim; Larus, James R.; Rajwar, Ravi (December 2010), Transactional Memory, 2nd edition, Synthesis Lectures on Computer Architecture, 5 (1), Morgan & Claypool, pp. 1–263, doi:10.2200/S00272ED1V01Y201006CAC011 
  • McKenney, Paul E.; Michael, Maged M.; Triplett, Josh; Walpole, Jonathan (July 2010). "Why the grass may not be greener on the other side: a comparison of locking vs. transactional memory". SIGOPS Oper. Syst. Rev. New York, NY, USA: ACM. 44 (3): 93–101. doi:10.1145/1842733.1842749. ISSN 0163-5980. 
  • Dave Dice, Yossi Lev, Mark Moir, Dan Nussbaum, and Marek Olszewski. (2009) "Early experience with a commercial hardware transactional memory implementation." Sun Microsystems technical report (60 pp.) SMLI TR-2009-180. A short version appeared at ASPLOS’09 doi:10.1145/1508244.1508263
  • Amy Wang, Matthew Gaudet, Peng Wu, José Nelson Amaral, Martin Ohmacht, Christopher Barton, Raul Silvera, and Maged Michael. "Evaluation of Blue Gene/Q hardware support for transactional memories". In Proceedings of the 21st international conference on Parallel architectures and compilation techniques, pp. 127–136. ACM, 2012.
  • Jacobi, C., Slegel, T., & Greiner, D. (2012, December). "Transactional memory architecture and implementation for IBM System z". In Microarchitecture (MICRO), 2012 45th Annual IEEE/ACM International Symposium on (pp. 25–36). IEEE.
  • Harold W. Cain, Maged M. Michael, Brad Frey, Cathy May, Derek Williams, and Hung Le. "Robust Architectural Support for Transactional Memory in the Power Architecture." In ISCA '13 Proceedings of the 40th Annual International Symposium on Computer Architecture, pp. 225–236, ACM, 2013. doi:10.1145/2485922.2485942

External links[edit]

Atomicity between two parallel transactions with a conflict
Hardware transactional memory using read and write bits

Transactions are an essential part of any business critical application as these ensure the integrity of the data being managed by the same application. Transactions ensure that the data remains in a consistent and integral state after this is manipulated, thus mitigating the risk of invalid state. Databases are synonymous for transactions, and many programming languages rely on the underlying database to provide the required transactional support. This works well when all state is found at the database level. Unfortunately, this is not always the case and there can be cases where the state is found at the application level rather than the database level. In this article we will see how we can use Multiverse (Git Hub), a Software Transactional Memory, to provide transactions at the software level without using any databases.

All code listed below is available at: https://github.com/javacreed/software-transactional-memory-example-using-multiverse. Most of the examples will not contain the whole code and may omit fragments which are not relevant to the example being discussed. The readers can download or view all code from the above repository.

Transactions

Say that we have a bank account, which account has two mutable fields, the current balance and the date when this was last modified as shown in the following image. Mutable fields are fields which can be modified after the object is created. On the other hand, immutable fields are fields which value will not change once the object is created.

Bank Account

As shown in the above image, the account now has Euro 100 and was last modified at 8am on the third of March, 2015. Say that I withdraw Euro 20 from this account at 10am of the following day. Then the account details should be updated as shown next.

Transfer Between Accounts

The date when the balance was last modified and the current balance are bound together and these two need to be updated together. This is very important to understand. If we fail to update one of the fields, then none of the fields should be updated. This property is also known as atomic. If I try to withdraw more money than I currently have, the withdrawal should fail and both the date and the balance should remain unchanged. In an atomic transaction, a series of operations either all occur, or nothing occurs (Wiki).

This is quite important as the data in memory or in a database, such as our banking accounts, need to always remain in a consistent and valid state. How would you react if the balance shows less money than it should following an error?

All operations should change the data from one valid state to another valid state. The state before the withdrawal was valid and the state after the withdrawal remained valid. This behaviour is provided by the consistency property. The consistency property ensures that any transaction will bring the data from one valid state to another (Wiki). To build on our previous example, the state of the system following a withdrawal, irrespective of the outcome, should always be valid.

Nowadays systems are used by many users at the same time. For example, a banking system can be accessed by many bank employees and also by the bank customers through the online portal.

Banking System

This scenario introduces new challenges as changes made by one user may interfere with the work of another user. Let us see this with an example. Say that we would like to know how many accounts have not been used for some time. We can use the following simple algorithm to achieve this.

List<Account> accounts = … long threshold = ... int count = 0; for(Account account : accounts) { if(account.getLastUpdate() < threshold) { total++; } }

This very simple and trivial algorithm does not work well within a concurrent (or as also known as multithreaded) environment as we will see next. Say that we have a total of 10 accounts, five of which have not been used lately (since 2015-04-01).

NumberBalanceLast Used
1Euro 1002015-01-01 10:00
2Euro 1502015-02-11 14:10
3Euro 2102015-04-21 09:50
4Euro 3442015-03-02 08:30
5Euro 652015-05-08 14:30
6Euro 6002015-03-15 09:25
7Euro 902015-01-14 08:40
8Euro 702015-05-21 15:20
9Euro 402015-05-04 14:40
10Euro 852015-04-15 15:10

This algorithm starts iterating through the list and checks each account last modified date and increment accordingly. What can possibly go wrong here? If the accounts are not modified while the algorithm counts them, then the results will be correct, 5. Consider the following scenario. The algorithm starts counting and before it reaches the 6th account, another user makes a transfer between account 1 and account 7. Account 1 was already counted as unused as it was last used before the threshold date. The transfer is complete and both accounts are updated accordingly as shown in the following table.

NumberBalanceLast Used
1Euro 402015-06-01 10:00
2Euro 1502015-02-11 14:10
3Euro 2102015-04-21 09:50
4Euro 3442015-03-02 08:30
5Euro 652015-05-08 14:30
6Euro 6002015-03-15 09:25
7Euro 1502015-06-01 10:00
8Euro 702015-05-21 15:20
9Euro 402015-05-04 14:40
10Euro 852015-04-15 15:10

After this transfer is complete, only 3 are the accounts that have not been modified lately. The counting algorithm continues and finishes counting. The result produced is 4, which is incorrect. We never had 4 unused accounts. We had 5 unused accounts before the transfer and 3 after the transfer between the two unused accounts was made. The values of 5 and 3 are both valid, but 4 is incorrect. This issue occurred as the data was modified while the algorithm was processing it.

Transactions mitigate this issue by providing isolation where the changes made by one user do not interfere with the work of another user. The isolation property ensures that the concurrent execution of transactions results in a system state that would be obtained if transactions were executed serially (Wiki).

Database transactions also provide durability, which means that once a transaction is committed, it will remain committed, even if the database is abruptly powered off or crashes. We will not dwell into this property as it is out of our scope since we are referring to software transactional model and these are inherently volatile.

Multiverse

The word “multiverse” means more than one universe and is also the name of a software transactional memory library. Multiverse allows us to turn a normal Java application into a transactional one, enabling most of the features normally provided by database transactions. As in many other cases, one of the best ways to understand something is by example and Multiverse is no exception.

Consider the following class.

package com.javacreed.examples.multiverse.part1; import org.multiverse.api.StmUtils; import org.multiverse.api.Txn; import org.multiverse.api.callables.TxnCallable; import org.multiverse.api.references.TxnInteger; import org.multiverse.api.references.TxnLong; public class Account { private final TxnLong lastUpdate; private final TxnInteger balance; public Account(final int balance) { this.lastUpdate = StmUtils.newTxnLong(System.currentTimeMillis()); this.balance = StmUtils.newTxnInteger(balance); } public void adjustBy(final int amount) { adjustBy(amount, System.currentTimeMillis()); } public void adjustBy(final int amount, final long date) { StmUtils.atomic(new Runnable() { @Override public void run() { balance.increment(amount); lastUpdate.set(date); if (balance.get() < 0) { throw new IllegalArgumentException("Not enough money"); } } }); } @Override public String toString() { return StmUtils.atomic(new TxnCallable<String>() { @Override public String call(final Txn txn) throws Exception { return String.format("%d (as of %tF %<tT)", balance.get(txn), lastUpdate.get(txn)); } }); } }

The class shown above has two fields, the and . The first field holds the last update date (in milliseconds) while the second field holds the account balance. Please note that the monetary values, such as balance, should not be saved in an integer field as we did above. Instead one should opt for more suitable types such as (Java Doc). In this example, we used an integer type to keep these examples as simple as possible.

The example shown above needs more than just a little introduction. Let us break the code into parts and analyse each part further.

  1. All fields that will participate in transaction need to be of a special type as show next. private final TxnLong lastUpdate; private final TxnInteger balance;

    We cannot use the primitives and , but instead we need to use the special fields (referred to hereunder as transactional fields). This is a big disadvantage as you cannot take any existing class and use it with Multiverse without first modifying its fields. Furthermore, you cannot easily switch from one software transactional model to another as the fields are bound to this library.

    Another important observation is that all fields are . This means that the class is immutable. In other words, the state of this class does not change. We change the values of these objects but not the objects themselves.

    Most of the transactional fields are found under the package (Git Hub).

    import org.multiverse.api.references.TxnInteger; import org.multiverse.api.references.TxnLong;
  2. The fields are initialised within the constructor when the instance of the is created. Instead of using traditional constructors we use (Source Code) class to create and wire our objects. public Account(final int balance) { this.lastUpdate = StmUtils.newTxnLong(System.currentTimeMillis()); this.balance = StmUtils.newTxnInteger(balance); }

    uses the proper factory to initialise the required object.

  3. Transactional fields, such as our fields and , can only be accessed from within a transaction. If such fields are accessed outside a transaction, a (Source Code) is thrown. This is an important feature as Multiverse ensures that all transactional fields are accessed from within a transaction. You can rest assure that such fields cannot be accessed outside a transaction. Therefore all concurrent access is properly made as otherwise it will never silently fail. This is quite an advantage and anyone who worked with large multithreaded applications can tell you how challenging this is.

    The method increments (or decrements) the balance and updates the modified date. If the new balance is negative, that is, there is not enough balance to cover this withdrawal, then an (Java Doc) is thrown.

    public void adjustBy(final int amount, final long date) { StmUtils.atomic(new Runnable() { @Override public void run() { balance.increment(amount); lastUpdate.set(date); if (balance.get() < 0) { throw new IllegalArgumentException("Not enough money"); } } }); }

    If an exception is thrown, then both fields are reverted to their values before the transaction started. This ensures that the state of the object moves from one valid state to another valid state.

    Note that all code is wrapped within a (Java Doc) and executed by the shown next.

    StmUtils.atomic(new Runnable() { @Override public void run() { // Code within the transaction } });

    All transaction fields, such as our and fields, need to be accessed and modified from within the method directly or indirectly. The method creates the required environment for transaction. An is thrown if such fields are not accessed properly.

    Later on in this article we will see how to access the transactional fields without having to wrap this within the method.

Using the above class is very simple as we see next.

package com.javacreed.examples.multiverse.part1; import org.slf4j.Logger; import org.slf4j.LoggerFactory; public class Example1 { public static void main(final String[] args) { final Account a = new Account(10); a.adjustBy(-5); Example1.LOGGER.debug("Account {}", a); try { a.adjustBy(-10); } catch (final IllegalArgumentException e) { Example1.LOGGER.warn("Failed to withdraw money"); } Example1.LOGGER.debug("Account {}", a); } private static final Logger LOGGER = LoggerFactory.getLogger(Example1.class); }

The above example makes two transactions. We start with a balance of 10 and then withdraw 5 () from this account leaving it with a new balance of 5. Then we make another withdrawal, only this time we try to withdraw more money than we have. This action is followed by an exception as expected.

Deadlocks

One of the deadliest things in concurrent programming is deadlock (Article). Unfortunately, once in deadlock, the involved threads will always remain in deadlock until the JVM is restarted. Deadlocks cannot happen with Multiverse. The transaction mechanism prevents deadlocks by either restart the transaction or failing it. This is quite a relief as we do not have to worry about deadlocks.

In this section we will work with two instances of account to make a transfer between one account and another. Addressing such problem using a traditional approach (synchronising on the account instance) can easily lead to deadlocks. Multiverse simplifies this as we will see in the following example.

package com.javacreed.examples.multiverse.part2; import org.multiverse.api.StmUtils; import org.multiverse.api.Txn; import org.multiverse.api.callables.TxnCallable; import org.multiverse.api.references.TxnInteger; import org.multiverse.api.references.TxnLong; public class Account { private final TxnLong lastUpdate; private final TxnInteger balance; public Account(final int balance) { this.lastUpdate = StmUtils.newTxnLong(System.currentTimeMillis()); this.balance = StmUtils.newTxnInteger(balance); } public void adjustBy(final int amount) { adjustBy(amount, System.currentTimeMillis()); } public void adjustBy(final int amount, final long date) { StmUtils.atomic(new Runnable() { @Override public void run() { balance.increment(amount); lastUpdate.set(date); if (balance.get() < 0) { throw new IllegalArgumentException("Not enough money"); } } }); } @Override public String toString() { return StmUtils.atomic(new TxnCallable<String>() { @Override public String call(final Txn txn) throws Exception { return String.format("%d (as of %tF %<tT)", balance.get(txn), lastUpdate.get(txn)); } }); } public void transferTo(final Account other, final int amount) { StmUtils.atomic(new Runnable() { @Override public void run() { final long date = System.currentTimeMillis(); adjustBy(-amount, date); other.adjustBy(amount, date); } }); } }

A new method called is added to the class shown next.

public void transferTo(final Account other, final int amount) { StmUtils.atomic(new Runnable() { @Override public void run() { final long date = System.currentTimeMillis(); adjustBy(-amount, date); other.adjustBy(amount, date); } }); }

The method takes two parameters, the account to which the money will be transferred to, and the amount of money to be transferred from this account to the given one. If the amount is negative, then the reverse will happen. In other words, will transfer 5 from account b to account a.

Together with avoiding deadlocks, we need to make sure that the involved accounts remain in a valid state. If the transaction fails, both accounts need to go back to their state before the transaction started. We cannot risk that the money is deducted from one account and it is not transferred to the other one. Similarly, we cannot create money by adding money to one account without withdrawing it from the other.

package com.javacreed.examples.multiverse.part2; import org.slf4j.Logger; import org.slf4j.LoggerFactory; public class Example2 { public static void main(final String[] args) { final Account a = new Account(10); final Account b = new Account(10); a.transferTo(b, 5); Example2.LOGGER.debug("Account (a) {}", a); Example2.LOGGER.debug("Account (b) {}", b); try { a.transferTo(b, 20); } catch (final IllegalArgumentException e) { Example2.LOGGER.warn("Failed to transfer money"); } Example2.LOGGER.debug("Account (a) {}", a); Example2.LOGGER.debug("Account (b) {}", b); } private static final Logger LOGGER = LoggerFactory.getLogger(Example2.class); }

The above example makes two transfers. The first transfer is expected to work without any problems but the second one should fail as the account from where the money is withdrawn does not have enough money to support this transaction. This example will never deadlock even if we inject systematic delays to cause collision and both accounts will remain in a valid state.

Memory Usage

One of the main problems with Multiverse is the memory usage. A Multiverse program can easily take more than 5 times the memory than a traditional one. In this section we will compare a traditional POJO (Plain Old Java Object) with a transactional one and see how much more memory the latter requires for the same amount of objects.

The class is shown next.

package com.javacreed.examples.multiverse.part3; public class PojoAccount { private final long lastUpdate; private final int balance; // Methods removed for brevity }

This class uses the traditional primitive fields instead of the transactional ones used by the shown next.

package com.javacreed.examples.multiverse.part3; public class StmAccount { private final TxnLong lastUpdate; private final TxnInteger balance; // Methods removed for brevity }

In both cases the class methods are removed for brevity. One million instances of take approximately 25 MB whereas the same amount of instances need approximately 141 MB of memory.

1 Million POJO Objects

1 Million STM Objects

These figures were extracted using the Your Kit Java Profiler (Home Page). It is always recommended to use profilers, such as the Your Kit Java Profiler, to measure the performance of your programs instead of guessing or trying to build something yourself.

If we replicate the same experiment using 10 million objects instead of 1 million, we will find that the memory growth ratio is linear and we will need 10 times as much memory in both cases. The following graph compares memory footprint ratio for these two types of objects.

Memory Required Ratio

As anticipated at the beginning of this section, Multiverse requires more than 5 times the memory required by traditional objects. This can be a problem with environments that have limited memory or larger applications that need to create many transactional objects. One need to pay extra attention when calculating the memory required as this can easily lead to out of memory errors.

Supported Types

Multiverse supports primitive types, such as , together with objects (non-primitives) such as . Multiverse has a special type, (Source Code), which can be used to represent all other (non-primitive) objects. The is a generic object that can take any object as its generic type. As an example, we will change the last modified date field from primitive long to a (Java Docs).

package com.javacreed.examples.multiverse.part4; import java.util.Date; import org.multiverse.api.StmUtils; import org.multiverse.api.Txn; import org.multiverse.api.callables.TxnCallable; import org.multiverse.api.references.TxnInteger; import org.multiverse.api.references.TxnRef; public class Account { private final TxnRef<Date> lastUpdate; private final TxnInteger balance; public Account(final int balance) { this.lastUpdate = StmUtils.newTxnRef(new Date()); this.balance = StmUtils.newTxnInteger(balance); } public void adjustBy(final int amount, final Date date) { StmUtils.atomic(new Runnable() { @Override public void run() { balance.increment(amount); lastUpdate.set(date); if (balance.get() < 0) { throw new IllegalArgumentException("Not enough money"); } } }); } }

As you can see, very little change was required. Instead of a field of type long, now we have a date object of type .

private final TxnRef<Date> lastUpdate;

This field can be modified using the setter method like any other object.

lastUpdate.set(date);

Using the we can wrap any object into a transactional one, but not all objects are suitable to be wrapped by the and extra care is required. Mutable objects, such as our , are a bit dangerous as these can be accessed and modified outside a transaction as we will see next.

package com.javacreed.examples.multiverse.part4; import java.util.Date; import java.util.concurrent.TimeUnit; import org.slf4j.Logger; import org.slf4j.LoggerFactory; public class Example5 { public static void main(final String[] args) { final Account a = new Account(10); final Date date = new Date(); a.adjustBy(-5, date); Example5.LOGGER.debug("Account {}", a); // Date is modified outside the transaction date.setTime(System.currentTimeMillis() - TimeUnit.HOURS.toMillis(1)); Example5.LOGGER.debug("Account {}", a); } private static final Logger LOGGER = LoggerFactory.getLogger(Example5.class); }

The object passed as a parameters to the can be modified outside a transaction and thus nullify all benefits gained when using Multiverse. In the above example we were able to modify the last modified date outside a transaction.

This problem only appears with mutable objects. Immutable objects, on the other hand, such as , do not have this problem as these objects cannot be modified after they are created. In order to be able to work with mutable objects, we need to make use of defensive copying (Article) in order to protect the mutable objects from being accidentally or intentionally modified outside a transaction.

Collections

A group of objects can be stored as an array or a collection. Multiverse provides naïve collection support as this feature is incomplete. One need to either fill in the blanks (provide the missing functionality) or avoid the missing functionality by using other methods. In this section we will see how collections can be used with Multiverse and will also see some of its limitations.

package com.javacreed.examples.multiverse.part5; import org.multiverse.api.StmUtils; import org.multiverse.api.Txn; import org.multiverse.api.callables.TxnCallable; import org.multiverse.api.references.TxnInteger; import org.multiverse.api.references.TxnLong; public class Account { private final TxnLong lastUpdate; private final TxnInteger balance; public Account(final int balance) { this.lastUpdate = StmUtils.newTxnLong(System.currentTimeMillis()); this.balance = StmUtils.newTxnInteger(balance); } public int getBalance(final Txn txn) { return balance.get(txn); } // Some methods were removed for brevity }

Note how the method accesses the transactional field without wrapping it within the method.

public int getBalance(final Txn txn) { return balance.get(txn); }

This is possible, because the transaction (an instance of type – Source Code) is passed as a parameter to the object’s method. Whoever invokes the above shown method needs to be within a transaction as it needs to provide the transaction as a parameter. We will see how this is used in a minute.

The next class is the class as it is used to hold a collection of accounts. The list of accounts is saved within an object of type (Source Code) as shown next.

package com.javacreed.examples.multiverse.part5; import org.multiverse.api.StmUtils; import org.multiverse.api.Txn; import org.multiverse.api.callables.TxnDoubleCallable; import org.multiverse.api.collections.TxnList; public class Accounts { private final TxnList<Account> list; public Accounts() { list = StmUtils.newTxnLinkedList(); } public void addAccount(final Account account) { StmUtils.atomic(new Runnable() { @Override public void run() { list.add(account); } }); } public double calculateAverageBalance() { return StmUtils.atomic(new TxnDoubleCallable() { @Override public double call(final Txn txn) throws Exception { if (list.isEmpty(txn)) { return 0; } final int size = list.size(txn); double total = 0; // Iteration is not supported by Multiverse at this stage for (int i = 0; i < size; i++) { final Account account = list.get(txn, i); total += account.getBalance(txn); } return total / size; } }); } }

Let us break this class further and discuss each respective part in more detail.

  1. The class contains a list of accounts of type . private final TxnList<Account> list;

    Similar to the other transactional fields, the list is initialised using the utilities class.

    public Accounts() { list = StmUtils.newTxnLinkedList(); }

    Multiverse (version ) only supports linked list. Array list is not supported. Furthermore, some of the list functionality such as iterator is not supported as we will see later on.

  2. Adding a new account to the list is very straight forward as shown next. public void addAccount(final Account account) { StmUtils.atomic(new Runnable() { @Override public void run() { list.add(account); } }); } The list modification happens within a transaction similar to what we saw before.
  3. In the beginning of this article we talked about isolation and the problems we can encounter when multiple threads interact with the same data. Transactions, by providing isolation allow multiple threads to interact with the same data without interfering with each other. The is a good example of isolation. public double calculateAverageBalance() { return StmUtils.atomic(new TxnDoubleCallable() { @Override public double call(final Txn txn) throws Exception { if (list.isEmpty(txn)) { return 0; } final int size = list.size(txn); double total = 0; // Iteration is not supported by Multiverse at this stage for (int i = 0; i < size; i++) { final Account account = list.get(txn, i); total += account.getBalance(txn); } return total / size; } }); }

    Adding or removing accounts by another thread will not affect the calculation of average by this thread. Multiverse guards us from such problem.

    Unfortunately we cannot iterate the instance (the list object returned by ) as the implementation is missing as shown next.

    Unimplemented Functionality

    Multiverse only provides an incomplete naïve implementation.

The class can be used like any other Java object as shown in the following example.

package com.javacreed.examples.multiverse.part5; import org.slf4j.Logger; import org.slf4j.LoggerFactory; public class Example6 { public static void main(final String[] args) { final Accounts accounts = new Accounts(); accounts.addAccount(new Account(10)); accounts.addAccount(new Account(20)); Example6.LOGGER.debug("Average Balance: {}", accounts.calculateAverageBalance()); } private static final Logger LOGGER = LoggerFactory.getLogger(Example6.class); }

Conclusion

Multithreading is a complex topic and it can have unpredicted results. What works without problems on one computer may continuously fail on another computer. Furthermore, certain events may increase the probability of a problem manifesting while others reduce it. A combination of different libraries can prove deadly as these may interfere with each other. All this is somewhat random and does not help understanding the side effects of a multithreaded application. The larger the application the worse this problem gets. Multiverse can help us mitigate multithreaded related problems and provides several benefits such as:

  1. Reduces the multithreading complexity
  2. Removes the deadlock problem
  3. Does not fail silently

In other words, you do not have to worry whether you application is thread-safe or not as all transactional fields need to be access within a transaction otherwise these will fail. All you need to care about is the transaction scope. What is meant to be in one transaction is actually in one transaction and not split into many transactions.

Multiverse is not the panacea for all multithreaded problems as it has several limitations such as:

  1. Incomplete
  2. Requires a great deal of memory
  3. Specific types
  4. Poor support for immutable objects

In my opinion, one of the biggest drawbacks of this library is the fact that it is incomplete. For example, only a naïve version of linked list is supported and some of its methods are not implemented. With that said one can always extend the current library and add any missing methods or functionality. The second drawback is the amount of memory it requires. An application can easily end up using five times the amount of memory simply because it works with Multiverse. Such approach cannot be used with systems that have limited resources. Furthermore, one need to take extra care with pay per use systems as this approach will require more memory which may result in larger and more expensive server/service plans.

Multiverse requires its own types and thus it will prove challenging to switch an existing application to use Multiverse. Multiverse types do not extend or inherit from the existing Java API and thus it makes them harder to use with existing code. For example, you cannot sort a using the ‘s method ( Java Doc ) as does not extend (Java Doc).

One needs to pay extra attention when working with mutable fields as we saw before. Mutable fields can be modified outside a transaction and thus nullifies all benefits that Multiverse provides.

Albert Attard

Albert Attard is a Java passionate and technical lead at a research group. You can find him on Google+. Over the past years Albert worked on various Java projects including traditional server/client applications, modular applications, large data handling applications and concurrent data manipulation applications to name a few. He has a BSc degree from the University of London (Homepage) and an MSc Information Security with the same university. His MSc thesis (Book) received the 2012 SearchSecurity.co.UK award (Website).

0 thoughts on “Transactional Memory Bibliography Template

Leave a Reply

Your email address will not be published. Required fields are marked *