Deadlock là gì? Bản chất 4 điều kiện Coffman và cách phòng tránh

Cách đây ít lâu, một bạn kỹ sư trong team tôi được giao tối ưu tiến trình khớp lệnh (matching engine) cho hệ thống giao dịch nội bộ. Ý tưởng ban đầu rất trực quan: thay vì xử lý tuần tự từng cặp lệnh mua - bán, bạn dựng một thread pool để xử lý song song. Mỗi worker thread sẽ kéo một lô lệnh chờ ra, kiểm tra điều kiện, khớp lệnh và mở transaction cập nhật số dư của hai bên cùng trạng thái PROCESSED.

Ở môi trường dev, mọi thứ chạy êm ru. Với vài chục lệnh mẫu và 2 worker thread, kết quả kiểm thử xanh rờn, dữ liệu khớp chính xác từng xu.

Nhưng khi đưa vào đợt kiểm thử với tập dữ liệu thực tế hơn — hàng nghìn lệnh chờ và nâng số worker thread lên để đo hiệu năng — sự cố lập tức nổ ra dưới tầng cơ sở dữ liệu.

Không phải CPU database bị quá tải, mà bảng điều khiển Grafana liên tục nhấp nháy cảnh báo đỏ. Nhật ký ứng dụng bắt đầu tràn ngập mã lỗi SQLSTATE 40P01: deadlock detected. Thời gian xử lý của các transaction vọt lên kịch trần, hàng loạt luồng bị cơ sở dữ liệu cưỡng chế huỷ bỏ (abort), và chỉ sau ít phút, toàn bộ connection pool của HikariCP bị nghẽn cứng do các luồng xếp hàng chờ nhau.

Cả tiến trình khớp lệnh gần như tê liệt hoàn toàn.

Khi ngồi lại phân tích hiện trường, phản xạ đầu tiên của bạn kỹ sư là: "Hay là do pool connection đang để timeout 30 giây hơi ngắn, mình tăng timeout lên và bọc thêm khối try-catch với cơ chế retry tự động bằng exponential backoff?"

Đó là một phản xạ rất tự nhiên, nhưng cũng là một cái bẫy kinh điển. Với tranh chấp tài nguyên do thứ tự lấy khoá xung đột, retry mù quáng dưới tải cao chỉ biến các va chạm cục bộ thành một cơn bão deadlock (deadlock storm). Khi hàng loạt luồng bị DB abort rồi đồng loạt retry, chúng lại tiếp tục lao vào tranh chấp đúng các tài nguyên cũ theo thứ tự ngược nhau, khiến toàn bộ connection pool cạn kiệt nhanh hơn gấp bội.

Để giải quyết tận gốc deadlock, bạn không thể trông chờ vào may rủi hay retry. Bạn cần hiểu đúng cấu trúc toán học của nó.

4 điều kiện Coffman: Mắt xích tạo nên thế bế tắc

Năm 1971, nhà khoa học máy tính Edward G. Coffman Jr. cùng các cộng sự đã công bố một nguyên lý nền tảng: Một deadlock chỉ có thể hình thành khi và chỉ khi cả bốn điều kiện sau đồng thời xảy ra. Thiếu bất kỳ một điều kiện nào trong số này, vòng lặp bế tắc toán học sẽ tự động sụp đổ.

Bốn điều kiện này giống như bốn chân của một chiếc bàn. Chỉ cần bạn cưa gãy một chân bất kỳ, chiếc bàn deadlock sẽ đổ sụp. Và trong thực tế thiết kế phần mềm, việc lựa chọn chân bàn nào để bẻ gãy chính là ranh giới giữa một hệ thống mong manh và một hệ thống bền bỉ.

Hiện trường Deadlock: Tầng ứng dụng đối đầu Tầng cơ sở dữ liệu

Nhiều lập trình viên lầm tưởng deadlock là câu chuyện riêng của cơ sở dữ liệu. Thực tế, bế tắc có thể xảy ra ở bất kỳ tầng nào có sự xuất hiện của chia sẻ tài nguyên và đa luồng.

1. Deadlock tại tầng Application Code (JVM / Java Threads)

Xét hàm chuyển tiền nội bộ giữa hai tài khoản, nơi mỗi thực thể Account sở hữu một khoá riêng để bảo vệ số dư:

public class TransferService {
    public void transfer(Account from, Account to, BigDecimal amount) {
        synchronized (from) { // Luồng 1 lấy khoá tài khoản gửi
            synchronized (to) { // Luồng 1 xin tiếp khoá tài khoản nhận
                from.debit(amount);
                to.credit(amount);
            }
        }
    }
}

Nếu User 101 chuyển tiền cho User 202 cùng lúc User 202 chuyển tiền lại cho User 101:

• Luồng 1 (101 -> 202): Giữ lock của Account(101), đang chờ xin lock của Account(202).
• Luồng 2 (202 -> 101): Giữ lock của Account(202), đang chờ xin lock của Account(101).

Cả hai luồng chuyển sang trạng thái BLOCKED. Trình quản lý luồng của hệ điều hành không thể tự động can thiệp vì Java synchronized hoàn toàn tuân theo điều kiện No Preemption. Hai luồng này sẽ chiếm dụng thread pool vĩnh viễn cho đến khi tiến trình JVM bị khởi động lại.

2. Deadlock tại tầng Database (PostgreSQL / MySQL)

Ngay cả khi bạn không dùng khoá ở tầng ứng dụng mà đẩy toàn bộ xuống cơ sở dữ liệu với transaction, hiện tượng tương tự vẫn xuất hiện ở cấp độ hàng (row-level lock):

-- Transaction 1 (Chuyển từ tài khoản 1 sang 2)
BEGIN;
UPDATE accounts SET balance = balance - 100 WHERE id = 1; -- Giữ lock id=1
-- Lúc này Transaction 2 xen vào...
UPDATE accounts SET balance = balance + 100 WHERE id = 2; -- Chờ lock id=2

-- Transaction 2 (Chuyển từ tài khoản 2 sang 1)
BEGIN;
UPDATE accounts SET balance = balance - 50 WHERE id = 2;  -- Giữ lock id=2
UPDATE accounts SET balance = balance + 50 WHERE id = 1;  -- Chờ lock id=1

Điểm khác biệt quan trọng: RDBMS hiện đại có sẵn cơ chế Deadlock Detection.

Ví dụ trong PostgreSQL, khi một transaction bị chặn bởi một transaction khác, nó sẽ kích hoạt bộ đếm thời gian deadlock_timeout (mặc định là 1 giây). Hết thời gian này, PostgreSQL sẽ dựng đồ thị chờ đợi (Wait-For Graph). Nếu phát hiện chu trình khép kín, nó sẽ chủ động chọn một transaction làm "vật tế thần" (victim), tiến hành abort transaction đó và ném về mã lỗi SQLSTATE 40P01:

ERROR:  deadlock detected
DETAIL:  Process 28144 waits for ShareLock on transaction 94012; blocked by process 28145.
         Process 28145 waits for ShareLock on transaction 94011; blocked by process 28144.
HINT:   See server log for query details.

PostgreSQL đã phá vỡ điều kiện No Preemption bằng cách cưỡng chế huỷ bỏ một bên để cứu lấy bên còn lại. Nhưng hãy nhớ: database phải trả giá bằng một thuật toán duyệt đồ thị tốn tài nguyên CPU, và tầng ứng dụng của bạn sẽ nhận về một exception văng ra ngoài.

Dấu hiệu nhận biết và cách chẩn đoán khi sự cố xảy ra

Khi hệ thống có dấu hiệu đông cứng hoặc log bắt đầu xuất hiện mã lỗi, làm thế nào để bạn chỉ mặt điểm tên chính xác thủ phạm?

Chẩn đoán tầng JVM: Bắt quả tang bằng Thread Dump

Với các ứng dụng Java/Kotlin, con đường nhanh nhất để thấy hiện trường là trích xuất Thread Dump thông qua tiện ích dòng lệnh jcmd hoặc jstack:

# Lấy PID của ứng dụng Java
jcmd <PID> Thread.print > threaddump.txt

Nếu có deadlock xảy ra giữa các luồng Java, JVM sẽ tự động quét đồ thị khoá và in hẳn một phần cảnh báo rõ ràng ở cuối file:

Found one Java-level deadlock:
=============================
"http-nio-8080-exec-12":
  waiting to lock monitor 0x00007f9c24003200 (object 0x0000000715a01000, a Account),
  which is held by "http-nio-8080-exec-34"

"http-nio-8080-exec-34":
  waiting to lock monitor 0x00007f9c24004500 (object 0x0000000715a00800, a Account),
  which is held by "http-nio-8080-exec-12"

Java stack information for the threads listed above:
===================================================
"http-nio-8080-exec-12":
    at com.example.service.TransferService.transfer(TransferService.java:18)
    - waiting to lock <0x0000000715a01000> (a com.example.model.Account)
    - locked <0x0000000715a00800> (a com.example.model.Account)
...

Nhìn vào đây, bạn biết chính xác luồng nào đang giữ đối tượng nào, đang đợi đối tượng nào và tại dòng code số mấy. Không cần phải phỏng đoán.

Chẩn đoán tầng PostgreSQL: Truy vấn pg_stat_activity và pg_locks

Khi nghi ngờ các transaction database đang ghìm chân nhau trước khi deadlock_timeout kịp phát hiện, bạn có thể kiểm tra danh sách các tiến trình đang bị chặn bằng hàm pg_blocking_pids:

SELECT 
    blocked_activity.pid AS blocked_pid,
    blocked_activity.usename AS blocked_user,
    blocking_activity.pid AS blocking_pid,
    blocking_activity.usename AS blocking_user,
    blocked_activity.query AS blocked_statement,
    blocking_activity.query AS current_statement_in_blocking_process
FROM pg_catalog.pg_stat_activity blocked_activity
JOIN pg_catalog.pg_stat_activity blocking_activity 
    ON blocking_activity.pid = ANY(pg_catalog.pg_blocking_pids(blocked_activity.pid))
WHERE NOT blocked_activity.wait_event IS NULL;

Bảng kết quả sẽ chỉ ra mối quan hệ nhân quả: ai đang giữ khoá và ai đang phải xếp hàng chờ đợi, giúp bạn khoanh vùng ngay câu truy vấn gây tắc nghẽn.

Chiến lược phòng tránh triệt để: Đừng để bế tắc có cơ hội hình thành

Trong 4 điều kiện Coffman:

• Mutual Exclusion là điều kiện tiên quyết của nghiệp vụ: bạn không thể cho phép hai giao dịch cùng sửa một số dư tài khoản mà không có cơ chế độc quyền.
• Hold and Wait thường khó loại bỏ hoàn toàn trong các nghiệp vụ liên hoàn cần cập nhật nhiều bảng.
• No Preemption chỉ có thể phá bằng timeout (tryLock trong Java hoặc lock_timeout trong SQL), nhưng đây vẫn là giải pháp xử lý hậu quả sau khi đã xảy ra xung đột.

Vũ khí thanh lịch, rẻ tiền và triệt để nhất chính là phá vỡ Circular Wait (Chờ đợi vòng tròn) bằng kỹ thuật Lock Ordering (Thứ tự khoá toàn cục).

1. Phá vỡ Circular Wait bằng Lock Ordering

Nguyên lý rất trực quan: Nếu mọi luồng trong hệ thống đều đồng thuận lấy các khoá theo một thứ tự duy nhất được xác định trước, chu trình chờ đợi vòng tròn toán học sẽ không bao giờ có thể hình thành.

Hãy nhìn lại nghiệp vụ chuyển tiền giữa hai tài khoản:

public void transferWithOrdering(Account from, Account to, BigDecimal amount) {
    // Luôn xác định thứ tự cố định dựa trên khoá chính
    Account firstLock = from.getId() < to.getId() ? from : to;
    Account secondLock = from.getId() < to.getId() ? to : from;

    synchronized (firstLock) {
        synchronized (secondLock) {
            from.debit(amount);
            to.credit(amount);
        }
    }
}

Bất kể User 101 chuyển tiền cho User 202 hay User 202 chuyển tiền cho User 101, cả hai luồng xử lý đều buộc phải xin cấp khoá của tài khoản có id nhỏ hơn trước (Account 101), sau đó mới được phép xin khoá của tài khoản lớn hơn (Account 202).

Luồng nào đến trước sẽ lấy được khoá 101. Luồng đến sau sẽ phải dừng ngay từ cửa ngoài (chờ khoá 101) mà chưa hề kịp chạm vào khoá 202. Chu trình giữ A chờ B và giữ B chờ A hoàn toàn biến mất.

Quy tắc này áp dụng tương tự cho câu lệnh SQL hàng loạt: khi cần cập nhật một danh sách hàng hoá trong giỏ hàng, hãy luôn sắp xếp danh sách ID theo thứ tự tăng dần trước khi thực hiện câu lệnh UPDATE hoặc SELECT ... FOR UPDATE:

-- Luôn sắp xếp id tăng dần trước khi khoá
SELECT * FROM products WHERE id IN (14, 5, 82) ORDER BY id FOR UPDATE;

2. Phá vỡ No Preemption bằng Explicit Timeout

Trong trường hợp luồng nghiệp vụ quá phức tạp và không thể sắp xếp thứ tự tài nguyên từ trước (ví dụ cần khoá động tài nguyên phân tán qua nhiều service), hãy từ bỏ synchronized và chuyển sang dùng ReentrantLock với phương thức tryLock(timeout):

public boolean processWithTimeout(Lock lockA, Lock lockB) throws InterruptedException {
    if (lockA.tryLock(500, TimeUnit.MILLISECONDS)) {
        try {
            if (lockB.tryLock(500, TimeUnit.MILLISECONDS)) {
                try {
                    // Thực hiện nghiệp vụ an toàn khi đã cầm đủ 2 khoá
                    return true;
                } finally {
                    lockB.unlock();
                }
            }
        } finally {
            lockA.unlock();
        }
    }
    // Không lấy đủ khoá trong hạn mức: chủ động rút lui để luồng khác đi tiếp
    return false;
}

Nếu không lấy được khoá thứ hai sau 500 mili-giây, luồng sẽ lập tức nhả khoá thứ nhất và rút lui. Bằng cách chủ động buông bỏ tài nguyên đang giữ khi việc chờ đợi vượt quá ngưỡng cho phép, bạn đã triệt tiêu điều kiện No Preemption, tránh tình trạng treo luồng vô hạn định.

Ở tầng cơ sở dữ liệu PostgreSQL, bạn thiết lập tương tự bằng cách cấu hình:

SET lock_timeout = '2s';

Thay vì chờ đợi âm thầm trong vô vọng, câu lệnh sẽ lập tức dừng lại nếu sau 2 giây chưa lấy được khoá, giải phóng ngay kết nối cho pool.

3. Thu hẹp phạm vi Transaction

Một transaction mở càng lâu thì thời gian giữ khoá càng dài, xác suất va chạm với các transaction khác càng tăng theo cấp số nhân. Hãy giữ cho transaction ngắn nhất có thể:

• Tuyệt đối không gọi API bên thứ ba, không gửi email, không xử lý file nặng bên trong một transaction cơ sở dữ liệu.
• Đọc dữ liệu trước bằng các câu truy vấn thông thường, chỉ mở transaction và giữ khoá tại khoảnh khắc thực sự ghi dữ liệu xuống đĩa.

[Mô hình SAI]   Mở Transaction -> Lock Row -> Gọi API đối tác (2s) -> Cập nhật -> Commit
[Mô hình ĐÚNG]  Gọi API đối tác (2s) -> Mở Transaction -> Lock Row -> Cập nhật -> Commit (<10ms)

Bài học từ sự cố tiến trình khớp lệnh

Trở lại với bài toán khớp lệnh của bạn kỹ sư trong team, chúng tôi không tăng timeout của HikariCP và cũng không thêm vòng lặp retry mù quáng nào.

Thay vào đó, bạn kỹ sư chỉ cần bổ sung đúng ba dòng code để sắp xếp hai ID tài khoản (hoặc ID của hai lệnh giao dịch) theo thứ tự tăng dần trước khi đưa vào câu lệnh SELECT ... FOR UPDATE. Kịch bản kiểm thử chịu tải cho tiến trình khớp lệnh được kích hoạt lại ngay sau đó.

Trên màn hình theo dõi, hàng chục worker thread cùng chạy song song mượt mà, nuốt trọn toàn bộ hàng nghìn lệnh chờ mà không hề phát sinh bất kỳ một lỗi deadlock 40P01 nào. CPU của database hoạt động ổn định, độ trễ xử lý mỗi cặp lệnh giữ vững ở mức thấp, và quan trọng nhất: không còn một kết nối nào bị giam cầm trong connection pool.

Deadlock không phải là một bài toán hên xui mang tính xác suất của môi trường production. Nó là hệ quả tất yếu của một cấu trúc sở hữu tài nguyên thiếu trật tự. Cơ sở dữ liệu có thể phát hiện và phá vỡ bế tắc giúp bạn, nhưng việc dựa dẫm vào cơ chế rollback tự động của nó là một sự lười biếng về mặt kiến trúc.

Thứ tự lấy khoá toàn cục (Lock Ordering) tốn của bạn chưa đến mười dòng code, nhưng nó cứu rỗi hệ thống khỏi những cuộc khủng hoảng âm thầm nhất.

Nếu bạn muốn đào sâu vào cơ chế quản lý khoá ở cấp độ nhân hệ điều hành và cách bộ lập lịch điều phối luồng, hãy tham khảo bài học Deadlock — bốn điều kiện Coffman và cách phá vòng chờ trong khoá học Hệ điều hành & Tiến trình. Còn nếu bạn quan tâm đến 8 cấp độ lock mode và cách vận hành của wait-for graph trong PostgreSQL, bài viết Locks và deadlock trong PostgreSQL sẽ cung cấp cái nhìn chi tiết từ góc độ cơ sở dữ liệu chuyên sâu.