Потокобезопасный перевод денег между счетами

31. Реализовать потокобезопасный перевод денег без дедлоков

Условие задачи:
Есть сервис MoneyTransferService, работающий в многопоточной среде.

Необходимо реализовать метод:

transfer(Account from, Account to, BigDecimal amount)

который:

атомарно списывает деньги со счёта from и зачисляет их на счёт to;
не позволяет счёту from уйти в минус;
корректно работает при одновременных переводах;
не допускает дедлоков;
принимает только положительную сумму перевода.

Код:

public class MoneyTransferService {

    public void transfer(
            Account from,
            Account to,
            BigDecimal amount
    ) {
        // TODO
    }
}

public class Account {
    private final int id;
    private BigDecimal balance;

    public Account(int id, BigDecimal initial) {
        this.id = id;
        this.balance = initial;
    }

    public int getId() {
        return id;
    }

    public BigDecimal getBalance() {
        return balance;
    }

    public void debit(BigDecimal amount) {
        balance = balance.subtract(amount);
    }

    public void credit(BigDecimal amount) {
        balance = balance.add(amount);
    }
}

Спойлеры к решению

Подсказки

💡 Проверка баланса и изменение обоих счетов должны выполняться внутри одной критической секции.
💡 Блокировать два счёта нужно всегда в одинаковом порядке.
💡 Обычно порядок можно определить по id.
💡 Если уникальность id не гарантирована, одного сравнения по id недостаточно — нужен дополнительный порядок для счетов с одинаковыми id.
💡 Отрицательную или нулевую сумму перевода нужно отклонять.

Решение

public class MoneyTransferService {

    private static final Object TIE_LOCK = new Object();

    public void transfer(
            Account from,
            Account to,
            BigDecimal amount
    ) {
        Objects.requireNonNull(from);
        Objects.requireNonNull(to);
        Objects.requireNonNull(amount);

        if (amount.compareTo(BigDecimal.ZERO) <= 0) {
            throw new IllegalArgumentException(
                    "Сумма перевода должна быть положительной"
            );
        }

        if (from == to) {
            return;
        }

        if (from.getId() < to.getId()) {
            transferWithLocks(from, to, from, to, amount);
            return;
        }

        if (from.getId() > to.getId()) {
            transferWithLocks(to, from, from, to, amount);
            return;
        }

        int fromHash = System.identityHashCode(from);
        int toHash = System.identityHashCode(to);

        if (fromHash < toHash) {
            transferWithLocks(from, to, from, to, amount);
        } else if (fromHash > toHash) {
            transferWithLocks(to, from, from, to, amount);
        } else {
            synchronized (TIE_LOCK) {
                transferWithLocks(from, to, from, to, amount);
            }
        }
    }

    private void transferWithLocks(
            Account first,
            Account second,
            Account from,
            Account to,
            BigDecimal amount
    ) {
        synchronized (first) {
            synchronized (second) {
                if (from.getBalance().compareTo(amount) < 0) {
                    throw new IllegalArgumentException(
                            "Недостаточно средств на счёте " + from.getId()
                    );
                }

                from.debit(amount);
                to.credit(amount);
            }
        }
    }
}

Главная проблема при блокировке двух объектов — возможность дедлока.

Например, два потока выполняют противоположные переводы:

Поток 1: A → B
Поток 2: B → A

Если первый поток сначала заблокирует A, а второй — B, оба могут начать ждать друг друга.

Поэтому счета блокируются в едином порядке:

if (from.getId() < to.getId()) {
    // сначала from, затем to
} else {
    // сначала to, затем from
}

Внутри обеих блокировок выполняются и проверка баланса, и изменение счетов:

if (from.getBalance().compareTo(amount) < 0) {
    throw new IllegalArgumentException("Недостаточно средств");
}

from.debit(amount);
to.credit(amount);

Это принципиально важно. Если проверить баланс до получения блокировки, два потока могут одновременно увидеть достаточно средств и оба выполнить списание.

Например:

Баланс: 100

Поток 1 хочет списать 80
Поток 2 хочет списать 80

Без атомарной проверки оба потока могли бы увидеть 100, после чего баланс ушёл бы в минус.

Дополнительная обработка:

System.identityHashCode(account)

нужна для счетов с одинаковыми id. Она задаёт стабильный порядок блокировок и для них.

Теоретически identityHashCode двух разных объектов также может совпасть. Для такого редкого случая используется общий:

TIE_LOCK

Благодаря этому порядок получения блокировок остаётся однозначным и дедлок не возникает.

Проверка:

if (amount.compareTo(BigDecimal.ZERO) <= 0)

тоже необходима: отрицательный перевод фактически поменял бы направление движения денег и мог бы нарушить инвариант баланса.

Сложность одного перевода — O(1), дополнительная память — O(1).

Потокобезопасность такого решения предполагает, что изменение balance выполняется только под блокировкой соответствующего Account. В реальном коде методы изменения баланса лучше не предоставлять для произвольного внешнего вызова, а инкапсулировать их внутри потокобезопасной модели счёта.