java-multiverse-stm
Software Transactional Memory in Java Using Multiverse
1. Overview
In this article, we’ll be looking at the Multiverse library – which helps us to implement the concept of Software Transactional Memory in Java.
Using constructs out of this library, we can create a synchronization mechanism on shared state – which is more elegant and readable solution than the standard implementation with the Java core library.
2. Maven Dependency
To get started we’ll need to add the multiverse-core library into our pom:
<dependency>
<groupId>org.multiverse</groupId>
<artifactId>multiverse-core</artifactId>
<version>0.7.0</version>
</dependency>3. Multiverse API
Software Transactional Memory (STM) is a concept ported from the SQL database world – where each operation is executed within transactions that satisfy ACID (Atomicity, Consistency, Isolation, Durability) properties. Here, only Atomicity, Consistency and Isolation are satisfied because the mechanism runs in-memory.
The main interface in the Multiverse library is the TxnObject – each transactional object needs to implement it, and the library provides us with a number of specific subclasses we can use.
Each operation that needs to be placed within a critical section, accessible by only one thread and using any transactional object – needs to be wrapped within the StmUtils.atomic() method. A critical section is a place of a program that cannot be executed by more than one thread simultaneously, so access to it should be guarded by some synchronization mechanism.
If an action within a transaction succeeds, the transaction will be committed, and the new state will be accessible to other threads. If some error occurs, the transaction will not be committed, and therefore the state will not change.
Finally, if two threads want to modify the same state within a transaction, only one will succeed and commit its changes. The next thread will be able to perform its action within its transaction.
4. Implementing Account Logic Using STM
Let’s say that we want to create a bank account logic using STM provided by the Multiverse library. Our Account object will have the lastUpadate timestamp that is of a TxnLong type, and the balance field that stores current balance for a given account and is of the TxnInteger type.
The TxnLong and TxnInteger are classes from the Multiverse. They must be executed within a transaction. Otherwise, an exception will be thrown. We need to use the StmUtils to create new instances of the transactional objects:
public class Account {
private TxnLong lastUpdate;
private TxnInteger balance;
public Account(int balance) {
this.lastUpdate = StmUtils.newTxnLong(System.currentTimeMillis());
this.balance = StmUtils.newTxnInteger(balance);
}
}Next, we’ll create the adjustBy() method – which will increment the balance by the given amount. That action needs to be executed within a transaction.
If any exception is thrown inside of it, the transaction will end without committing any change:
public void adjustBy(int amount) {
adjustBy(amount, System.currentTimeMillis());
}
public void adjustBy(int amount, long date) {
StmUtils.atomic(() -> {
balance.increment(amount);
lastUpdate.set(date);
if (balance.get() <= 0) {
throw new IllegalArgumentException("Not enough money");
}
});
}If we want to get the current balance for the given account, we need to get the value from the balance field, but it also needs to be invoked with atomic semantics:
public Integer getBalance() {
return balance.atomicGet();
}5. Testing the Account
Let’s test our Account logic. First, we want to decrement balance from the account by the given amount simply:
@Test
public void givenAccount_whenDecrement_thenShouldReturnProperValue() {
Account a = new Account(10);
a.adjustBy(-5);
assertThat(a.getBalance()).isEqualTo(5);
}Next, let’s say that we withdraw from the account making the balance negative. That action should throw an exception, and leave the account intact because the action was executed within a transaction and was not committed:
@Test(expected = IllegalArgumentException.class)
public void givenAccount_whenDecrementTooMuch_thenShouldThrow() {
// given
Account a = new Account(10);
// when
a.adjustBy(-11);
}Let’s now test a concurrency problem that can arise when two threads want to decrement a balance at the same time.
If one thread wants to decrement it by 5 and the second one by 6, one of those two actions should fail because the current balance of the given account is equal to 10.
We’re going to submit two threads to the ExecutorService, and use the CountDownLatch to start them at the same time:
ExecutorService ex = Executors.newFixedThreadPool(2);
Account a = new Account(10);
CountDownLatch countDownLatch = new CountDownLatch(1);
AtomicBoolean exceptionThrown = new AtomicBoolean(false);
ex.submit(() -> {
try {
countDownLatch.await();
} catch (InterruptedException e) {
e.printStackTrace();
}
try {
a.adjustBy(-6);
} catch (IllegalArgumentException e) {
exceptionThrown.set(true);
}
});
ex.submit(() -> {
try {
countDownLatch.await();
} catch (InterruptedException e) {
e.printStackTrace();
}
try {
a.adjustBy(-5);
} catch (IllegalArgumentException e) {
exceptionThrown.set(true);
}
});After staring both actions at the same time, one of them will throw an exception:
countDownLatch.countDown();
ex.awaitTermination(1, TimeUnit.SECONDS);
ex.shutdown();
assertTrue(exceptionThrown.get());6. Transferring from One Account to Another
Let’s say that we want to transfer money from one account to the other. We can implement the transferTo() method on the Account class by passing the other Account to which we want to transfer the given amount of money:
public void transferTo(Account other, int amount) {
StmUtils.atomic(() -> {
long date = System.currentTimeMillis();
adjustBy(-amount, date);
other.adjustBy(amount, date);
});
}All logic is executed within a transaction. This will guarantee that when we want to transfer an amount that is higher than the balance on the given account, both accounts will be intact because the transaction will not commit.
Let’s test transferring logic:
Account a = new Account(10);
Account b = new Account(10);
a.transferTo(b, 5);
assertThat(a.getBalance()).isEqualTo(5);
assertThat(b.getBalance()).isEqualTo(15);We simply create two accounts, we transfer the money from one to the other, and everything works as expected. Next, let’s say that we want to transfer more money than is available on the account. The transferTo() call will throw the IllegalArgumentException, and the changes will not be committed:
try {
a.transferTo(b, 20);
} catch (IllegalArgumentException e) {
System.out.println("failed to transfer money");
}
assertThat(a.getBalance()).isEqualTo(5);
assertThat(b.getBalance()).isEqualTo(15);Note that the balance for both a and b accounts is the same as before the call to the transferTo() method.
7. STM Is Deadlock Safe
When we’re using the standard Java synchronization mechanism, our logic can be prone to deadlocks, with no way to recover from them.
The deadlock can occur when we want to transfer the money from account a to account b. In standard Java implementation, one thread needs to lock the account a, then account b. Let’s say that, in the meantime, the other thread wants to transfer the money from account b to account a. The other thread locks account b waiting for an account a to be unlocked.
Unfortunately, the lock for an account a is held by the first thread, and the lock for account b is held by the second thread. Such situation will cause our program to block indefinitely.
Fortunately, when implementing transferTo() logic using STM, we do not need to worry about deadlocks as the STM is Deadlock Safe. Let’s test that using our transferTo() method.
Let’s say that we have two threads. First thread wants to transfer some money from account a to account b, and the second thread wants to transfer some money from account b to account a. We need to create two accounts and start two threads that will execute the transferTo() method in the same time:
ExecutorService ex = Executors.newFixedThreadPool(2);
Account a = new Account(10);
Account b = new Account(10);
CountDownLatch countDownLatch = new CountDownLatch(1);
ex.submit(() -> {
try {
countDownLatch.await();
} catch (InterruptedException e) {
e.printStackTrace();
}
a.transferTo(b, 10);
});
ex.submit(() -> {
try {
countDownLatch.await();
} catch (InterruptedException e) {
e.printStackTrace();
}
b.transferTo(a, 1);
});After starting processing, both accounts will have the proper balance field:
countDownLatch.countDown();
ex.awaitTermination(1, TimeUnit.SECONDS);
ex.shutdown();
assertThat(a.getBalance()).isEqualTo(1);
assertThat(b.getBalance()).isEqualTo(19);8. Conclusion
In this tutorial, we had a look at the Multiverse library and at how we can use that to create lock-free and thread safe logic utilizing concepts in the Software Transactional Memory.
We tested the behavior of the implemented logic and saw that the logic that uses the STM is deadlock-free.
The implementation of all these examples and code snippets can be found in the GitHub project – this is a Maven project, so it should be easy to import and run as it is.
