Deadlock: chuyển tiền A→B và B→A cùng lúc

Deadlock là tình trạng 2 hoặc nhiều thread bị kẹt vĩnh viễn vì đang chờ lock của nhau. Ví dụ kinh điển với 2 thread và 2 lock:

static final Object lockA = new Object();
static final Object lockB = new Object();

Thread t1 = new Thread(() -> {
    synchronized (lockA) {
        System.out.println("Thread 1 giữ lockA");
        synchronized (lockB) { System.out.println("Thread 1 giữ lockB"); }
    }
});
Thread t2 = new Thread(() -> {
    synchronized (lockB) {
        System.out.println("Thread 2 giữ lockB");
        synchronized (lockA) { System.out.println("Thread 2 giữ lockA"); }
    }
});
t1.start(); t2.start();

Thread 1 giữ A muốn B, Thread 2 giữ B muốn A. Không ai nhả vì chưa chạy xong block synchronized. Giờ mang nó về project wallet-service của bài trước.

1. Bài toán

Thêm API chuyển tiền POST /transfers. Để không bị lost update ở cả hai ví, mình khóa cả hai trước khi trừ/cộng:

void transfer(Wallet from, Wallet to, BigDecimal amount) {
    synchronized (from) {
        synchronized (to) {
            from.withdraw(amount);
            to.deposit(amount);
        }
    }
}

Chạy test đơn lẻ thì ổn. Lên production, thỉnh thoảng app treo cứng: không exception, không log.

2. Vấn đề

Hai request chạy cùng lúc, một cái A→B, một cái B→A:

Thread 1 (A→B): khóa A ... chờ B
Thread 2 (B→A): khóa B ... chờ A   ← cả hai chờ nhau, không ai nhả

Hai thread đứng đó mãi, request treo tới khi client timeout. Nhiều request dính vào thì Tomcat thread pool cạn và cả app ngừng phản hồi.

Deadlock chỉ xảy ra khi đủ cả 4 điều kiện Coffman:

3. Giải pháp

Phá được một điều kiện là hết deadlock. Thực tế hay phá hai cái:

• Phá circular wait bằng lock ordering: luôn khóa theo thứ tự cố định, ví dụ wallet id nhỏ trước. Đơn giản, không tốn gì, nên nghĩ tới đầu tiên.
• Phá no preemption bằng tryLock có timeout: không chờ vô hạn; không lấy được thì nhả hết và thử lại. Dùng khi không xác định được thứ tự (khóa lấy động, nhiều tầng gọi).

4. Code từng bước

Bước 1: Lock ordering

void transfer(Wallet from, Wallet to, BigDecimal amount) {
    Wallet first  = from.getId() < to.getId() ? from : to;
    Wallet second = first == from ? to : from;
    synchronized (first) {
        synchronized (second) {
            from.withdraw(amount);
            to.deposit(amount);
        }
    }
}

Bước 2: tryLock + backoff (mỗi wallet có một ReentrantLock, bài sau nói kỹ):

boolean transfer(Wallet from, Wallet to, BigDecimal amount) throws InterruptedException {
    for (int i = 0; i < 3; i++) {
        if (from.lock.tryLock(100, TimeUnit.MILLISECONDS)) {
            try {
                if (to.lock.tryLock(100, TimeUnit.MILLISECONDS)) {
                    try {
                        from.withdraw(amount);
                        to.deposit(amount);
                        return true;
                    } finally { to.lock.unlock(); }
                }
            } finally { from.lock.unlock(); }
        }
        Thread.sleep(ThreadLocalRandom.current().nextInt(10, 50)); // backoff ngẫu nhiên
    }
    return false;   // controller trả 409/503 cho client thử lại
}

Sleep ngẫu nhiên để hai thread không cùng nhả rồi cùng lấy lại y hệt nhau mãi (gọi là livelock).

Bước 3: Test, bắn chuyển tiền hai chiều song song:

for i in $(seq 1 200); do
  curl -s -X POST localhost:8080/transfers -H 'Content-Type: application/json' \
       -d '{"from":1,"to":2,"amount":1}' &
  curl -s -X POST localhost:8080/transfers -H 'Content-Type: application/json' \
       -d '{"from":2,"to":1,"amount":1}' &
done; wait
# code cũ: vài request không bao giờ trả về
# lock ordering: tất cả trả về, tổng tiền 2 ví không đổi

5. Cách hoạt động

KHÔNG sắp thứ tự                      CÓ sắp thứ tự (id nhỏ trước)
Thread 1          Thread 2            Thread 1 (A→B)    Thread 2 (B→A)
lock(A)           lock(B)             lock(A)           lock(A) ← chờ
   ↓                 ↓                lock(B)              .
chờ B  ←─ vòng ─→  chờ A              làm việc             .
       DEADLOCK                       unlock B, A  ───→  lock(A) OK
                                                         lock(B), làm việc

Thread 2 vẫn phải chờ, nhưng đó là blocking bình thường: Thread 1 xong sẽ nhả, Thread 2 chạy tiếp. Không có vòng thì không có deadlock.

6. So sánh

7. Khi nào dùng

• Cần lấy nhiều lock cùng lúc: luôn có quy tắc thứ tự (theo id).
• Không sắp được thứ tự: tryLock có timeout + backoff.
• Tốt nhất là không giữ nhiều lock: giảm phạm vi khóa, không gọi API ngoài khi đang giữ khóa.
• Nhớ: lock trong JVM chỉ đúng khi một instance. Với wallet-service chạy 2 instance, khóa thật nằm ở DB, và DB cũng có deadlock (câu tiếp).

Đúng. Database cũng có deadlock, và bản chất gần như y hệt Java. Hai transaction chuyển tiền theo thứ tự ngược nhau:

-- Transaction 1 (A→B)                     -- Transaction 2 (B→A)
BEGIN;                                     BEGIN;
UPDATE wallet SET balance = balance - 100  UPDATE wallet SET balance = balance - 50
WHERE id = 'A';   -- lock A                WHERE id = 'B';   -- lock B
UPDATE wallet SET balance = balance + 100  UPDATE wallet SET balance = balance + 50
WHERE id = 'B';   -- muốn B                WHERE id = 'A';   -- muốn A  ← vòng

Điểm khác quan trọng: MySQL InnoDB, PostgreSQL tự phát hiện vòng chờ và rollback một transaction. App nhận lỗi kiểu Deadlock found when trying to get lock, Spring bọc thành CannotAcquireLockException / DeadlockLoserDataAccessException.

Cũng vì vậy mà @Lock(PESSIMISTIC_WRITE) ở bài trước không phải cứ thêm là xong: khóa sai thứ tự còn tạo ra deadlock. Cách xử lý giống Java:

@Lock(LockModeType.PESSIMISTIC_WRITE)
@Query("select w from Wallet w where w.id in :ids order by w.id")
List<Wallet> lockAllOrdered(List<Long> ids);   // khóa theo thứ tự id

@Transactional
public void transfer(Long fromId, Long toId, BigDecimal amount) {
    lockAllOrdered(List.of(fromId, toId));   // A trước B, bất kể chiều chuyển
    ...
}

• Khóa theo thứ tự: WHERE id IN (...) ORDER BY id FOR UPDATE.
• Transaction ngắn, không gọi API ngoài khi đang giữ khóa.
• Retry transaction bị chọn làm victim (ví dụ Spring Retry @Retryable).
• Xem nguyên nhân: MySQL SHOW ENGINE INNODB STATUS, PostgreSQL xem log.

Đúng hướng: deadlock trong JVM không tự báo lỗi, phải tự đi tìm. Lấy thread dump:

jps                      # tìm pid
jstack <pid> > dump.txt   # hoặc: jcmd <pid> Thread.print

JVM tự phát hiện deadlock với monitor và ReentrantLock, in ra cuối dump:

Found one Java-level deadlock:
"http-nio-8080-exec-2":
  waiting to lock monitor 0x... (object 0x..., a Wallet),
  which is held by "http-nio-8080-exec-5"
"http-nio-8080-exec-5":
  waiting to lock monitor 0x... (object 0x..., a Wallet),
  which is held by "http-nio-8080-exec-2"

Kèm stack trace chỉ đúng dòng code. Thread chờ synchronized có trạng thái BLOCKED, chờ ReentrantLock là WAITING. Trong code có thể dùng ThreadMXBean.findDeadlockedThreads() để tự kiểm tra định kỳ và bắn alert.

Q1. Deadlock là gì, tránh thế nào?

🇻🇳 Tiếng Việt:

Deadlock xảy ra khi nhiều thread giữ các resource khác nhau và đồng thời chờ resource mà thread khác đang giữ, tạo thành vòng chờ nên không thread nào chạy tiếp được. Nó cần đủ 4 điều kiện Coffman: mutual exclusion, hold and wait, no preemption, circular wait. Em thường phá circular wait bằng lock ordering, ví dụ luôn khóa account id nhỏ trước; hoặc phá no preemption bằng tryLock có timeout kèm retry và backoff.

🇬🇧 English:

A deadlock happens when threads hold some resources while waiting for resources held by each other, forming a cycle, so none of them can proceed. It requires all four Coffman conditions: mutual exclusion, hold and wait, no preemption and circular wait. I usually break circular wait with lock ordering, for example always locking the smaller account id first, or break no preemption with tryLock with a timeout plus retry and backoff.

Q2. Deadlock trong database khác trong Java thế nào?

🇻🇳 Tiếng Việt:

Bản chất giống nhau: hai transaction khóa row theo thứ tự ngược nhau. Khác ở chỗ DB tự phát hiện vòng chờ và rollback một transaction làm victim, còn JVM để các thread treo mãi. Với SELECT FOR UPDATE em khóa theo thứ tự id, giữ transaction ngắn và retry transaction bị rollback.

🇬🇧 English:

The root cause is the same: two transactions lock rows in opposite order. The difference is that the database detects the cycle and rolls back one transaction as the victim, while the JVM leaves the threads stuck forever. With SELECT FOR UPDATE I lock rows in id order, keep transactions short, and retry the rolled-back transaction.

Q3. App đang treo, làm sao xác định có deadlock?

🇻🇳 Tiếng Việt:

Em lấy thread dump bằng jstack hoặc jcmd Thread.print. JVM sẽ in "Found one Java-level deadlock" kèm tên thread, lock đang giữ, lock đang chờ và stack trace đến đúng dòng code.

🇬🇧 English:

I take a thread dump with jstack or jcmd Thread.print. The JVM prints "Found one Java-level deadlock" with the thread names, the locks they hold and wait for, and stack traces pointing to the exact lines of code.

Cách nhớ ngắn gọn

• Giữ A chờ B, giữ B chờ A = vòng = deadlock.
• 4 điều kiện Coffman, phá 1 là đủ: ordering (circular wait), tryLock (no preemption).
• Race condition = dữ liệu sai; deadlock = treo; livelock = bận mà không tiến.
• DB tự rollback victim, JVM thì không: dùng jstack.