Java synchronisation: atomically moving money across account pairs?

Question

How can I make money transfer from one account to another atomic? For class:

public class Account {
    public Account(BigDecimal initialAmount) {...}
    public BigDecimal getAmount() {...}
    public void setAmount(BigDecimal amount) {...}
}

I expect following pseudo-code:

public boolean transfer(Account from, Account to, BigDecimal amount) {
    BigDecimal fromValue = from.getAmount();
    if (amount.compareTo(fromValue) < 0)
         return false;
    BigDecimal toValue = to.getAmount();
    from.setAmount(fromValue.add(amount.negate()));
    to.setAmount(toValue.add(amount));
    return true;
}

updates accounts safely in a single threaded (or sequential) environment.

In case of multithreaded / concurrent environment I see danger cases:

acc1 --> acc2  ||  acc2 --> acc1
acc1 --> acc2  ||  acc2 --> acc3  ||  acc3 --> acc1
...

Easiest solution is to block on shared object, but it will be inefficient for cases like:

acc1 --> acc2  ||  acc3 --> acc4  and  acc1 != acc3 and acc2 != acc4

I expect independent transfers are performed in parallel.

UPDATE Seems that suggested solution:

synchronize (acc1) {
   synchronize (acc2) {
     ....
   }
}

lead to deadlock as 2 locks acquired sequentially...

UPDATE 2 what do you mean with "update accounts safely in multithreading environment" exactly? Is the only worry that the accounts won't end up having minus funds or is there some other problem?

If acc1(2); acc2(3) and acc1 --1--> acc2 and acc2 --2--> acc1 I expect consistency: (acc1, acc2) has (3, 2) value, but not (4, 2) or (3, 4). Total should be 5, and not 1+3=4 or 4+3=7.

how much concurrent transaction are you expecting at a time ? 1000-10000 - so lock on shared object isn't efficient.

Answer 1

A simple solution could be to use a lock per account, but to avoid deadlock you have to acquire locks in the same order always. So, you could have a final account ID, and acquire the lock of the account with a less id first:

public void transfer(Account acc1, Account acc2, BigDecimal value) {
    Object lock1 = acc1.ID < acc2.ID ? acc1.LOCK : acc2.LOCK;
    Object lock2 = acc1.ID < acc2.ID ? acc2.LOCK : acc1.LOCK;
    synchronized (lock1) {
       synchronized (lock2) {
          acc1.widrawal(value);
          acc2.send(value);
       }
    }
}

Answer 2

One way to do this is to have a transaction log. Before moving the money, you'll need to write to the transaction log of each account what you intend to do. The log should contain: the amount of money that's taken in/out of the account, and an lock which is shared between the log pair.

Initially the lock should be in a blocked state. You created the log pair, one with amount of X and the other with amount of -X, and both shares a lock. Then deliver the log entry to the inbox of the respective accounts, the account from which money is taken out should reserve that amount. Once you've confirmed that they're delivered safely, then release the lock. The moment the lock is released you're at a point if no return. The accounts then should resolve themselves.

If either of the party want to fail the transaction at any time before the lock is released, then simply remove the logs and return the reserved amount to the main balance.

This approach may be a bit heavy, but it would also work in a distributed scenario where the accounts actually are in different machines, and the inboxes actually would have to be persisted, to ensure money never get lost if any of the machine crashes/goes offline unexpectedly. Its general technique is called two phase locking.

Answer 3

I would propose to create a method Account.withdraw(amount) which throws an exception if it doesn't have sufficient funds. This method needs to be synchronized on the account itself.

Edit:

There also needs to be a Account.deposit(amount) method which is synchronized on the receiving account instance.

Basically this will result in a lock of the first account while withdrawing and then another lock on the receiving account while depositing. So two locks but not at the same time.

Code sample: Assumes that withdraw/deposit are synchronized and return boolean success status rather than throw exception.

public boolean transfer(Account from, Account to, BigDecimal amount) {
    boolean success = false;
    boolean withdrawn = false;
    try {
        if (from.withdraw(amount)) {
            withdrawn = true;
            if (to.deposit(amount)) {
                success = true;
            }
        }
    } finally {
        if (withdrawn && !success) {
            from.deposit(amount);
        }
    }

    return success;
}

Answer 4

You can create an extra Account T that exists solely for transferring the money. So if you want to transfer from A to B you actually transfer from A to T and then from T to B. For each of these transfers you only lock either A or B depending on which account is participating in the transfer. Since you are using the same type for transfers, you end up with little extra code and therefore low maintenance costs.

To reduce the number of extra accounts you could hold them in a pool. If you have a thread pool that is processing transfers, than you can assign each thread it's own extra account. Therefore you don't need to request and release those extra accounts from/to a pool too often.

Answer 5

One approach is to use kind of "striped lock" with lock/unlock methods operating on several locks. Accounts are mapped to locks using hashCode, the more locks you allocate, the more parallelism you get.

Here's code sample:

public class StripedLock {

    private final NumberedLock[] locks;

    private static class NumberedLock {
        private final int id;
        private final ReentrantLock lock;

        public NumberedLock(int id) {
            this.id = id;
            this.lock = new ReentrantLock();
        }
    }


    /**
     * Default ctor, creates 16 locks
     */
    public StripedLock() {
        this(4);
    }

    /**
     * Creates array of locks, size of array may be any from set {2, 4, 8, 16, 32, 64}
     * @param storagePower size of array will be equal to <code>Math.pow(2, storagePower)</code>
     */
    public StripedLock(int storagePower) {
        if (!(storagePower >= 1 && storagePower <= 6)) { throw new IllegalArgumentException("storage power must be in [1..6]"); }

        int lockSize = (int) Math.pow(2, storagePower);
        locks = new NumberedLock[lockSize];
        for (int i = 0; i < locks.length; i++)
            locks[i] = new NumberedLock(i);
    }

    /**
     * Map function between integer and lock from locks array
     * @param id argument
     * @return lock which is result of function
     */
    private NumberedLock getLock(int id) {
        return locks[id & (locks.length - 1)];
    }

    private static final Comparator<? super NumberedLock> CONSISTENT_COMPARATOR = new Comparator<NumberedLock>() {
        @Override
        public int compare(NumberedLock o1, NumberedLock o2) {
            return o1.id - o2.id;
        }
    };


    public void lockIds(@Nonnull int[] ids) {
        Preconditions.checkNotNull(ids);
        NumberedLock[] neededLocks = getOrderedLocks(ids);
        for (NumberedLock nl : neededLocks)
            nl.lock.lock();
    }

    public void unlockIds(@Nonnull int[] ids) {
        Preconditions.checkNotNull(ids);
        NumberedLock[] neededLocks = getOrderedLocks(ids);
        for (NumberedLock nl : neededLocks)
            nl.lock.unlock();
    }

    private NumberedLock[] getOrderedLocks(int[] ids) {
        NumberedLock[] neededLocks = new NumberedLock[ids.length];
        for (int i = 0; i < ids.length; i++) {
            neededLocks[i] = getLock(i);
        }
        Arrays.sort(neededLocks, CONSISTENT_COMPARATOR);
        return neededLocks;
    }
}

    // ...
    public void transfer(StripedLock lock, Account from, Account to) {
        int[] accountIds = new int[]{from.getId(), to.getId()};
        lock.lockIds(accountIds);
        try {
            // profit!
        } finally {
            lock.unlockIds(accountIds);
        }
    }

Answer 6

Don't use built-in synchronization, use a Lock object. Use tryLock() to get an exclusive lock on both accounts at the same time. If either one fails, then release both locks and wait a random amount of time and try again.

Answer 7

As stated previously, you should lock on both accounts, always in the same order. The key part, however, is ensuring both high granularity and singularity across the VM instance. This can be done using String.intern():

public boolean transfer(Account from, Account to, BigDecimal amount) {
    String fromAccountId = from.id.toString().intern();
    String toAccountId = to.id.toString().intern();
    String lock1, lock2;

    if (from.id < to.id) {
       lock1 = fromAccountId;
       lock2 = toAccountId;
    } else {
       lock1 = toAccountId;
       lock2 = fromAccountId;
    }

    // synchronizing from this point, since balances are checked
    synchronized(lock1) {
        synchronized(lock2) {
            BigDecimal fromValue = from.getAmount();
            if (amount.compareTo(fromValue) < 0)
                 return false;

            BigDecimal toValue = to.getAmount();
            from.setAmount(fromValue.add(amount.negate()));
            to.setAmount(toValue.add(amount));
            return true;
        }
    }
}

Answer 8

As you have mentioned there will be 1000-10000 concurrent transaction you expecting at a time than you can store accounts on which some transaction is going on and handle concurrency

One Solution is to allow system to create only one object of particulate account id, means that if you want to make a transaction between account "123" and "456" than your thread will create account object and in that constructor of account class we will check if any other object of account is there with particulate account id, if other object of account is there with same account id means that some transaction is going on with particulate account id so you have to wait to get the account object.

So we can do transaction between "123" and "456" and at same time we can do transaction between "abc" and "xyz" but if at same time some other thread will try to create object of account "123" than system will say please wait

for reference you can see below code

Please note :

1. dont forgote to remove your account id from locks map by call to freeAccount(BigDecimal accId) from LockHolder class

2. I have used HasMap instand of list because list will not be a good choice when you are randomly removing element from it(or when frequently you are updating it)

   package test;
   
   import java.math.BigDecimal;
   import java.util.HashMap;
   import java.util.Map;
   
   public class T {
   
   public static void main(String[] args) {
       Account ac, ac2;
   
       try {
           ac = new Account(new BigDecimal("123"));
       } catch (Exception e) {
           e.printStackTrace();
       }
       try {
           ac2 = new Account(new BigDecimal("123"));
       } catch (Exception e) {
           System.out.println("Please Wait");
       }
   
   }
   }
   
   class Account {
    public Account(BigDecimal accId) throws Exception {
       if (LockHolder.isLocked(accId)) {
           throw new Exception();
       } else {
           LockHolder.setLock(accId);
       }
    }
   }
   
   class LockHolder {
    public static  Map<BigDecimal, Integer> locks = new HashMap<BigDecimal, Integer>();
   
    public synchronized static boolean isLocked(BigDecimal accId) {
       return LockHolder.locks.containsKey(accId);
    }
   
    public synchronized static void setLock(BigDecimal accId) {
       LockHolder.locks.put(accId , 1);
    }
    public synchronized static void freeAccount(BigDecimal accId) {
       LockHolder.locks.remove(accId);
    }
   }
   

Answer 9

An approach which will remain robust even if threads may get arbitrarily waylaid is to have each account maintain a list of transactions requested or posted against it. To request a transfer from one account to another, create a transaction object defining the request and add it to the request queue for the source account. If that account can perform the transaction, it should move it to its list of posted transactions and add it to the request queue for the destination. Using AtomicReference it's possible to ensure that from the moment the transaction is placed into the queue for the first account, the state of the system will always thereafter either have the transaction pending, completed, or aborted, and even if some or all threads were to get waylaid, examining the transaction lists would make it possible to determine what money belonged where.

By contrast, when using locks, events which unexpectedly delay one thread can arbitrarily impede the execution of many others, and if a thread gets killed off while holding a lock it may be impossible to determine what exactly it had or had not done prior to that.