Java Multithreading — Protecting Invariants with Immutability
In this tutorial, I will go over the concept of invariants and why they are important. Then I will show how it is difficult to protect invariants in a multithreaded program. Finally, I will show how using immutability, one can protect the invariants in a multithreaded program.
We have a lot to cover, so let’s get started!
What is an Invariant?
An invariant is a condition that remains true regardless of the state of the system. In the context of software engineering, particularly in multithreading and concurrent programming, an invariant is a logical condition or a set of conditions that must always hold true during the execution of a program.
Invariants can arise from your domain logic. Some examples of domain related invariants are:
1. Total product in inventory must never be less than zero.
2. The sum of balances across all accounts must equal the total deposited amount minus the total withdrawn amount.
3. The number of booked seats on a flight must not exceed the total number of available seats
Breaking the Invariant in Multithreaded Execution
Here we take an example of a bank that has two accounts and there are only two transactions possible.
- Transfer of certain amount from account A to account B
- Transfer of certain amount from account B to account A
Our invariant will be that total balance of both the accounts should remain same. Note that since our invariant involves two state fields (balanceOfA and balanceOfB), as soon as one of these fields is updated, invariant is broken temporarily.
Unless all the state fields of an invariant are updated atomically, it is impossible to ensure invariant all the time.
First let’s define BankWithTwoAccounts class to represent our bank:
public class BankWithTwoAccounts {
private int balanceOfA;
private int balanceOfB;
public BankWithTwoAccounts(int balanceOfA, int balanceOfB) {
this.balanceOfA = balanceOfA;
this.balanceOfB = balanceOfB;
}
//Transfer amount from A to B
public void atob(int amount) {
while (true) {
if (balanceOfA >= amount) { // read
this.balanceOfA -= amount; // update 1
this.balanceOfB += amount; // update 2
return;
}
}
}
//Transfer amount from B to A
public void btoa(int amount) {
while (true) {
if (balanceOfB >= amount) { // read
this.balanceOfB -= amount; // update 1
this.balanceOfA += amount; // update 2
return;
}
}
}
@Override
public String toString() {
return "BankWithTwoAccounts [BalanceOfA= " + balanceOfA + " BalanceOfB= " +balanceOfB +" TotalBalance= " +getTotalBalance() +"]";
}
private int getTotalBalance() {
return balanceOfA + balanceOfB;
}
}It has two methods for fund transfer: atob and btoa.
Then we create a simulation class that will execute the fund transfer operations in multiple threads:
public class BankAccountSimulation {
public static void main(String[] args) throws InterruptedException {
BankWithTwoAccounts bank = new BankWithTwoAccounts(1000, 1000); // Initial balance
Runnable atobTask = () -> {
for (int i = 0; i < 100; i++) {
bank.atob(10);
}
};
Runnable btoaTask = () -> {
for (int i = 0; i < 100; i++) {
bank.btoa(10);
}
};
ExecutorService executorService = Executors.newFixedThreadPool(10);
// Start multiple deposit and withdraw threads
for (int i = 0; i < 5; i++) {
executorService.submit(atobTask);
executorService.submit(btoaTask);
}
executorService.shutdown();
executorService.awaitTermination(1, TimeUnit.MINUTES);
System.out.println("Final balance: " + bank);
}
}We initialize the bank with 1000 each in both the accounts. Then we define two Runnables that transfer 10 each from A to B and B to A.
We then create an instance of ExecutorService with a fixed thread pool of 10. We then submit the two Runnables to the ExecutorService so that the tasks can be run parallely by threads in the fixed thread pool.
We let it run for 1 minute and finally we see the final balance in the bank. We expect the total balance to be 2000, but that is not what we see:
Final balance: BankWithTwoAccounts [BalanceOfA= 350 BalanceOfB= 1590 TotalBalance= 1940]These results indicate that some deposits or withdrawals were lost or double-counted due to race conditions.
Explanation of Results
- Lost Updates: If two threads try to update the balance at the same time, one update might be lost. For instance, if two threads read the balance as 1000 simultaneously and then both try to add 10, the balance might end up as 1010 instead of 1020.
- Inconsistent Reads: A thread might read an intermediate state of the balance, leading to incorrect updates. For example, if the balance is 1000 and one thread withdraws 10 while another thread deposits 10, both might read the balance as 1000 and update it to 990 and 1010, respectively, instead of 1000.
Using Immutability to Model Invariants
Immutability is a simple concept. Once an immutable object is constructed, it can never change. Any mutation (change) to the object’s state results in creation of new object instance.
We will resolve the problem with previous example by wrapping our two state fields (balanceOfA and balanceOfB) in a single immutable class.
Now, let’s see how we can use immutability to ensure that the invariants are preserved in a multithreaded environment.
Immutable Bank Account Class
public final class ImmutableBankWithTwoAccounts {
private final int balanceOfA;
private final int balanceOfB;
public ImmutableBankWithTwoAccounts(int balanceOfA, int balanceOfB) {
this.balanceOfA = balanceOfA;
this.balanceOfB = balanceOfB;
}
public ImmutableBankWithTwoAccounts atob(int amount) {
while (true) {
if (balanceOfA >= amount) {
return new ImmutableBankWithTwoAccounts(balanceOfA - amount, balanceOfB + amount);
}
}
}
public ImmutableBankWithTwoAccounts btoa(int amount) {
while (true) {
if (balanceOfB >= amount) {
return new ImmutableBankWithTwoAccounts(balanceOfA + amount, balanceOfB - amount);
}
}
}
@Override
public String toString() {
return "ImmutableBankWithTwoAccounts [BalanceOfA= " + balanceOfA + "BalanceOfB= " +balanceOfB +"TotalBalance= " +getTotalBalance() +"]";
}
private int getTotalBalance() {
return balanceOfA + balanceOfB;
}
}Note that this class is almost same as our previous mutable bank class, with one difference. Object mutation is prohibited. Instead, everytime a mutation is attempted, the existing object remains same, but a new object with new state is returned.
Account Service Class
public class ImmutableBankAccountService {
private final AtomicReference<ImmutableBankWithTwoAccounts> bankRef;
public ImmutableBankAccountService(int balanceofa, int balanceofb) {
bankRef = new AtomicReference<>(new ImmutableBankWithTwoAccounts(balanceofa, balanceofb));
}
public boolean atob(int amount) {
ImmutableBankWithTwoAccounts currentBank = bankRef.get();
ImmutableBankWithTwoAccounts updatedBank = currentBank.atob(amount);
if (bankRef.compareAndSet(currentBank, updatedBank)) {
System.out.println("atob done" +updatedBank);
return true; // transaction successful
} else {
System.out.println("atob failed" +updatedBank);
return false;
}
}
public boolean btoa(int amount) {
while (true) {
ImmutableBankWithTwoAccounts currentBank = bankRef.get();
ImmutableBankWithTwoAccounts updatedBank = currentBank.btoa(amount);
if (bankRef.compareAndSet(currentBank, updatedBank)) {
System.out.println("btoa done"+updatedBank);
return true; // transaction successful
} else {
System.out.println("btoa failed"+updatedBank);
return false; // transaction successful
}
}
}
public String getBalance() {
return bankRef.get().toString();
}
}We use AtomicReference to wrap our ImmutableBankWithTwoAccounts class. This ensures that our atob or btoa operation remains atomic, while immutability ensures that invariant is never violated and object state is always visible post construction.
By making our bank class immutable we ensure that the invariant on sum of balanceOfA and balanceOfB remains intact. By wrapping the current instance of immutable bank, we ensure that saving the new instance of ImmutableBankWithTwoAccounts is atomic and always visible.
Finally we create simulation class to simulate multithreaded transactions.
public class SafeBankSimulation {
public static void main(String[] args) throws InterruptedException {
ImmutableBankAccountService accountService = new ImmutableBankAccountService(1000, 1000); // Initial balance
Runnable atobTask = () -> {
for (int i = 0; i < 100; i++) {
accountService.atob(10);
}
};
Runnable btoaTask = () -> {
for (int i = 0; i < 100; i++) {
accountService.btoa(10);
}
};
ExecutorService executorService = Executors.newFixedThreadPool(10);
// Start multiple deposit and withdraw threads
for (int i = 0; i < 5; i++) {
executorService.submit(atobTask);
executorService.submit(btoaTask);
}
executorService.shutdown();
executorService.awaitTermination(1, TimeUnit.MINUTES);
System.out.println("Final balance: " + accountService.getBalance());
}
}No matter how many times you run this code, it will always give 2000 as final balance.
btoa done: ImmutableBankWithTwoAccounts [BalanceOfA= 990 BalanceOfB= 1010 TotalBalance= 2000]
btoa done: ImmutableBankWithTwoAccounts [BalanceOfA= 1000 BalanceOfB= 1000 TotalBalance= 2000]
btoa done: ImmutableBankWithTwoAccounts [BalanceOfA= 1010 BalanceOfB= 990 TotalBalance= 2000]
btoa done: ImmutableBankWithTwoAccounts [BalanceOfA= 1020 BalanceOfB= 980 TotalBalance= 2000]
btoa done: ImmutableBankWithTwoAccounts [BalanceOfA= 1030 BalanceOfB= 970 TotalBalance= 2000]
Final balance: ImmutableBankWithTwoAccounts [BalanceOfA= 1030 BalanceOfB= 970 TotalBalance= 2000]Conclusion
By modeling the bank accounts as fields within an immutable object and using AtomicReference for atomic updates, we can ensure that the invariants are preserved even in a multithreaded environment. This approach eliminates race conditions and ensures that the total balance of the bank is always consistent and correct, regardless of the number of concurrent threads performing operations on the accounts.