Bài toán hai vị tướng và giới hạn của "gửi đúng một lần"

17:00, dịch vụ đơn hàng của BanHang chuyển đơn 10051 sang đã thanh toán rồi gửi sự kiện DonDaThanhToan lên message broker. Broker không trả lời trong thời hạn. Gửi lại thì khách có thể được cộng điểm hai lần, không gửi lại thì kho có thể không bao giờ xuất hàng. Bài toán hai vị tướng, có từ năm 1975, giải thích vì sao không có lựa chọn thứ ba, và phải làm gì thay vào đó.

1. Phát biểu bài toán #

Hai đạo quân đóng trên hai ngọn đồi, thành địch ở giữa. Cùng đánh thì thắng, một bên đánh thì bên đó bị diệt. Hai tướng chỉ liên lạc bằng người đưa tin đi qua vùng địch, và người đưa tin có thể bị bắt. Tướng A quyết định có đánh không, tướng B chỉ biết điều đó qua tin nhắn. Giao thức đúng phải thỏa ba điều:

1. An toàn: không bao giờ chỉ một tướng đánh.
2. A làm chủ: A không muốn đánh thì A không đánh.
3. Hữu ích: A muốn đánh và không ai bị bắt thì cả hai đánh.

Điều 3 loại lời giải "không ai đánh". Số người đưa tin không giới hạn, nhưng mỗi tướng phải quyết định sau hữu hạn tin.

Cái khó nằm ở chữ "biết". B nhận lệnh thì biết giờ đánh, nhưng A chưa biết B đã biết. B gửi xác nhận thì tới lượt B không biết A đã nhận chưa. Đánh an toàn cần đủ mọi tầng "biết rằng bên kia biết", gọi là common knowledge (tri thức chung). Halpern và Moses (1990) chứng minh khi việc truyền tin không được bảo đảm thì common knowledge không đạt được, và giao thức an toàn nào cũng dẫn tới không ai đánh.

Bài toán xuất hiện lần đầu ở phụ lục bài báo của Akkoyunlu, Ekanadham và Huber tại SOSP 1975, trong vai một băng cướp chốt kế hoạch qua người đưa tin có thể bị chặn đường. Jim Gray kể lại bằng hai vị tướng năm 1978, ở mục "The generals paradox" của "Notes on Data Base Operating Systems", để dẫn vào two-phase commit. Tên gọi đi ra từ bản của Gray.

2. Vì sao không có giao thức nào #

Giả sử có giao thức đúng. Khi A muốn đánh và không tin nào mất, cả hai đánh sau k tin. Gọi R(i) là lần chạy giống hệt nhưng chỉ i tin đầu tới nơi, các tin sau đều mất.

1. Giả sử trong R(i), với i ≥ 1, cả hai đánh. Người gửi tin thứ i, chẳng hạn A, không phân biệt được R(i) với R(i − 1): i − 1 tin đầu như nhau, và sau tin thứ i, A không nhận thêm gì. Vậy A đánh trong cả hai.
2. Trong R(i − 1), A đánh, nên theo điều 1, B cũng đánh. Tin thứ i là thừa.
3. Lặp từ i = k xuống 1: trong R(0), không tin nào tới mà cả hai vẫn đánh.
4. Khi A không muốn đánh và mọi tin mất, B thấy giống hệt R(0) nên B đánh, còn A không đánh. Trái điều 1.

Phép chứng minh viết cho giao thức tất định và không dùng gì về nội dung tin: đánh số, mã hóa hay gửi trăm bản đều không thoát. Akkoyunlu và cộng sự ghi thêm: chuỗi xác nhận vô hạn ngay cả khi không tin nào thực sự mất. Cái thiếu là sự chắc chắn, không phải đường truyền.

Two-phase commit cũng không phá kết quả này. Gray viết ngay sau đó: bỏ yêu cầu độ dài tối đa cố định thì mới có lời giải, đổi lại số tin có thể tùy ý. Nói cách khác, gửi lại cho đến khi tin tới và chấp nhận chờ.

3. Gửi nhiều bản: xác suất tăng, chắc chắn thì không #

Mỗi bản mất độc lập với xác suất p thì B có ít nhất một trong n bản với xác suất 1 − pⁿ. Với p = 0,3 và n = 3: 1 − 0,027 = 0,973. Script dưới đây mô phỏng điều đó, thêm chiều ACK, và thêm bảng 3 cho mục 4. Chỉ dùng thư viện chuẩn, chạy bằng Python 3.14.3, hạt giống 1975.

import random

rng = random.Random(1975)
N = 200_000  # số lần mô phỏng cho mỗi ô

def toi(p):  # một bản tin, bị mất với xác suất p
    return rng.random() >= p

def gui_su_kien(p, so_lan):  # gửi đến khi có ACK, tối đa so_lan lần
    so_ban = 0                # số bản broker ghi được
    for _ in range(so_lan):
        if toi(p):
            so_ban += 1
            if toi(p):        # ACK về tới producer
                break
    return so_ban

print("Bảng 1. Số lần B không nhận được bản nào trong n bản, trên 200.000 lần")
print("n  p=0.1  N·p^n    p=0.3  N·p^n")
for n in range(1, 6):
    dong = f"{n}"
    for p in (0.1, 0.3):
        mat_het = sum(not any(toi(p) for _ in range(n)) for _ in range(N))
        dong += f"  {mat_het:<5}  {N * p**n:<7.1f}"
    print(dong.rstrip())

print("\nBảng 2. p = 0.3, B trả n bản ACK. A không thấy ACK nào gọi là im lặng")
print("n  P(im lặng)  P(B đã nhận | im lặng)  (1 - p^n)/(2 - p^n)")
for n in range(1, 6):
    im_lang = b_da_nhan = 0
    for _ in range(N):
        b_nhan = any(toi(0.3) for _ in range(n))
        if not (b_nhan and any(toi(0.3) for _ in range(n))):
            im_lang += 1
            b_da_nhan += b_nhan
    q = 0.3**n
    print(f"{n}  {im_lang / N:.4f}      {b_da_nhan / im_lang:.3f}"
          f"                   {(1 - q) / (2 - q):.3f}")

print("\nBảng 3. 200.000 sự kiện DonDaThanhToan, gửi lại khi không có ACK")
print("tối đa  p    mất    đúng 1 bản  từ 2 bản")
for so_lan in (1, 5):
    for p in (0.1, 0.3):
        kq = [gui_su_kien(p, so_lan) for _ in range(N)]
        mat, mot = kq.count(0), kq.count(1)
        print(f"{so_lan:<6}  {p}  {mat:<5}  {mot:<10}  {N - mat - mot}")

Bảng 1. Số lần B không nhận được bản nào trong n bản, trên 200.000 lần
n  p=0.1  N·p^n    p=0.3  N·p^n
1  20054  20000.0  59984  60000.0
2  2005   2000.0   17830  18000.0
3  193    200.0    5367   5400.0
4  16     20.0     1679   1620.0
5  3      2.0      477    486.0

Bảng 2. p = 0.3, B trả n bản ACK. A không thấy ACK nào gọi là im lặng
n  P(im lặng)  P(B đã nhận | im lặng)  (1 - p^n)/(2 - p^n)
1  0.5096      0.412                   0.412
2  0.1727      0.477                   0.476
3  0.0528      0.499                   0.493
4  0.0161      0.505                   0.498
5  0.0047      0.502                   0.499

Bảng 3. 200.000 sự kiện DonDaThanhToan, gửi lại khi không có ACK
tối đa  p    mất    đúng 1 bản  từ 2 bản
1       0.1  19821  180179      0
1       0.3  60145  139855      0
5       0.1  1      180022      19977
5       0.3  485    141345      58170

Bảng 1 khớp kỳ vọng N·pⁿ. Với p = 0,1 và n = 5, xác suất tới là 0,99999, vẫn có 3 lần trên 200.000 B không nhận được gì. Với 13.000 đơn mỗi ngày của BanHang, sự cố xác suất 10⁻⁵ xảy ra cỡ một lần mỗi 8 ngày (ước lượng).

Bảng 2 là phần đáng nhớ. A im lặng khi lệnh mất, hoặc lệnh tới mà mọi ACK mất: xác suất pⁿ + (1 − pⁿ)·pⁿ. Trong đó, phần B đã nhận lệnh là (1 − pⁿ)/(2 − pⁿ): với p = 0,3 và n = 1 là 0,7/1,7 = 0,412. Tăng n làm im lặng hiếm dần, từ 0,5096 xuống 0,0047, nhưng tỉ lệ đó tiến về 1/2. Gửi thêm làm tình huống mơ hồ hiếm đi, không làm nó bớt mơ hồ.

ACK chỉ chuyển sự bất định đi: B trả ACK thì B thành người gửi tin cuối, đúng bước 1 của phép chứng minh. Halpern và Moses ghi nhận phần làm được: với giả định xác suất phù hợp, có giao thức bảo đảm một bên đánh thì bên kia đánh theo với xác suất cao. Phần còn lại phải xử lý ở bên nhận.

4. BanHang: broker, consumer và cổng thanh toán #

Dịch vụ đơn hàng là tướng A, broker là tướng B. Theo tài liệu Kafka, producer gặp lỗi mạng thì không biết lỗi xảy ra trước hay sau khi tin được commit. Không gửi lại là at-most-once, có thể mất. Gửi lại đến khi có ACK là at-least-once, có thể trùng. Bảng 3 mô phỏng việc này, tin và ACK cùng mất với xác suất p. Với p = 0,1, gửi một lần mất 19.821 sự kiện. Gửi lại tối đa 5 lần chỉ mất 1, nhưng 19.977 sự kiện, khoảng 10%, bị ghi từ hai bản. Mạng nội bộ khỏe mất ít hơn 10% rất nhiều, nên con số chỉ minh họa hình dạng của đánh đổi.

Consumer gặp lại lựa chọn đó: lưu offset (vị trí đọc) trước khi xử lý là at-most-once, sau khi xử lý là at-least-once.

Ba hệ quả cho BanHang, giả sử broker là Kafka. Client Java bật enable.idempotence mặc định từ Kafka 3.0. librdkafka, nền của client .NET Confluent.Kafka, để mặc định false (CONFIGURATION.md nhánh master, xem ngày 2026-10-01), nên phải tự đặt EnableIdempotence = true. Idempotence chỉ có trong một session của producer: dịch vụ khởi động lại rồi gửi lại thì Kafka thấy hai tin. Consumer ghi SQL Server, gửi email hay gọi API nhận at-least-once.

Phía gửi còn khe hở: đổi TrangThai trong SQL Server và gửi lên broker không chung giao dịch. Transactional outbox ghi sự kiện vào một bảng trong cùng giao dịch đổi trạng thái, rồi tiến trình khác gửi lên broker, có thể nhiều lần.

Cổng thanh toán là hai vị tướng thật của BanHang: lời gọi trừ tiền timeout thì không biết thẻ đã bị trừ chưa. Theo Kleppmann, bài này giải được trong thực tế vì tiền đã trừ hoàn lại được, và khi mạng thông có thể hỏi cổng trạng thái giao dịch. Sau timeout, hỏi trạng thái hoặc gửi lại với cùng idempotency key (Idempotency key), không tạo yêu cầu trừ tiền mới.

5. Không phải các vị tướng Byzantine #

Lamport, Shostak và Pease (1982) dùng cùng hình ảnh cho một bài khác. Giả định A1 của họ là mọi tin gửi đi đều tới đúng, nhưng một số tướng phản bội. Chỉ dùng tin miệng thì giải được khi và chỉ khi hơn hai phần ba số tướng trung thành: cần 3f + 1 tướng để chịu f kẻ phản bội. Có chữ ký không giả mạo được thì giải được với mọi số kẻ phản bội.

Dịch vụ nội bộ của BanHang cần lo mất tin, timeout và sập: mô hình hai vị tướng.

6. Consumer idempotent trên SQL Server #

Dịch vụ điểm thưởng cộng 1 điểm cho mỗi 10.000 đồng. Đơn 10051 của khách 7 có TongTien 1.250.000, đáng 125 điểm, giao hai lần thì thành 250. Cách sửa là bảng khử trùng theo mã tin, ghi cùng giao dịch với phép cộng. Ghi dấu và commit trước thì sập ở giữa làm mất điểm. Cộng trước, ghi dấu sau thì sập ở giữa làm lần giao lại cộng thêm. Một giao dịch cho cả hai hoặc không gì, và consumer chỉ xác nhận với broker sau khi commit.

CREATE TABLE dbo.SuKienDaXuLy (
    MessageId uniqueidentifier NOT NULL CONSTRAINT PK_SuKienDaXuLy PRIMARY KEY,
    XuLyLuc datetime2(0) NOT NULL CONSTRAINT DF_SuKienDaXuLy_XuLyLuc DEFAULT SYSUTCDATETIME()
);
CREATE TABLE dbo.DiemThuong (KhachHangId int NOT NULL CONSTRAINT PK_DiemThuong PRIMARY KEY, Diem int NOT NULL);
GO
CREATE OR ALTER PROCEDURE dbo.usp_DiemThuong_CongTheoDon
    @MessageId uniqueidentifier, @KhachHangId int, @TongTien decimal(18, 2)
AS
BEGIN
    SET NOCOUNT ON;
    SET XACT_ABORT ON;
    BEGIN TRY
        BEGIN TRAN;
        -- Dấu "đã xử lý". UPDLOCK, HOLDLOCK bắt hai bản trùng đến cùng lúc xếp hàng.
        INSERT dbo.SuKienDaXuLy (MessageId)
        SELECT @MessageId
        WHERE NOT EXISTS (SELECT 1 FROM dbo.SuKienDaXuLy WITH (UPDLOCK, HOLDLOCK)
                          WHERE MessageId = @MessageId);
        IF @@ROWCOUNT = 0
        BEGIN
            COMMIT;
            SELECT N'bỏ qua bản trùng' AS KetQua;
            RETURN;
        END;
        -- Tác dụng thật, cùng giao dịch: 1 điểm cho mỗi 10.000 đồng.
        UPDATE dbo.DiemThuong
        SET Diem = Diem + CAST(FLOOR(@TongTien / 10000) AS int)
        WHERE KhachHangId = @KhachHangId;
        IF @@ROWCOUNT = 0
            THROW 50001, N'Khách chưa có dòng trong dbo.DiemThuong.', 1;
        COMMIT;
        SELECT N'đã xử lý' AS KetQua;
    END TRY
    BEGIN CATCH
        IF @@TRANCOUNT > 0 ROLLBACK;
        THROW;
    END CATCH;
END;
GO
INSERT dbo.DiemThuong (KhachHangId, Diem) VALUES (7, 0);
DECLARE @MessageId uniqueidentifier = '6f1d2c3b-0a4e-4b8f-9c71-2d5e8a9b0c42';
EXEC dbo.usp_DiemThuong_CongTheoDon @MessageId, 7, 1250000.00;  -- đã xử lý
EXEC dbo.usp_DiemThuong_CongTheoDon @MessageId, 7, 1250000.00;  -- bỏ qua bản trùng
SELECT Diem FROM dbo.DiemThuong WHERE KhachHangId = 7;          -- 125

Năm dòng cuối giao cùng một tin hai lần. Kết quả trong chú thích chạy trên SQL Server 2019 LocalDB (15.0.4382.1). UPDLOCK, HOLDLOCK giữ khóa phạm vi quanh giá trị MessageId đến hết giao dịch, cùng mẫu upsert ở Transaction, khóa và mức isolation. Thử với hai phiên sqlcmd: phiên sau gọi cùng MessageId khi phiên đầu chưa commit, chờ khoảng 8 giây đến lúc phiên đầu commit, rồi trả bỏ qua bản trùng.

Quy tắc rút ra:

1. Coi mọi kênh là at-least-once. Consumer idempotent bằng bảng khử trùng hoặc bằng thao tác tự idempotent: SET TrangThai = 3 làm hai lần vẫn ra 3, Diem = Diem + 125 thì không.
2. Mã tin sinh một lần ở nguồn, như mã đơn sinh trước vòng thử lại ở bài transaction. Khóa nghiệp vụ như (DonHangId, LoaiSuKien) cũng dùng được. Dọn bảng khử trùng theo XuLyLuc, nhưng giữ lâu hơn thời gian broker còn có thể giao lại một tin.
3. Tác dụng ngoài database, như email hay cổng thanh toán, cần idempotency key ở phía bên kia.
4. Timeout là "không biết", không phải "thất bại". Hỏi trạng thái trước khi làm lại, làm lại thì dùng cùng mã. Thử lại có giới hạn, có backoff và jitter, gói trong thời gian người gọi còn chờ. Hết lượt thì đưa vào dead-letter queue.

Những chỗ hay hiểu sai #

• "Gửi đủ nhiều lần thì chắc chắn tới." 1 − pⁿ luôn nhỏ hơn 1, và bên gửi không biết lần này rơi vào đâu.
• "Có ACK là hết lo." ACK chuyển nỗi lo sang người gửi ACK.
• "Kafka có exactly-once nên consumer khỏi khử trùng." Nó chỉ phủ chuỗi đọc, xử lý, ghi giữa các topic.

Đọc tiếp #

• Idempotency key: để một đơn không bị trừ tiền hai lần: khử trùng ở phía cổng thanh toán.
• Transaction, khóa và mức isolation: XACT_ABORT, upsert với UPDLOCK, HOLDLOCK, vòng thử lại dùng mã đơn sinh trước.
• Một request HTTPS mất bao lâu: timeout của lời gọi tới cổng thanh toán rơi vào bước nào.

Nguồn #

• Akkoyunlu, Ekanadham, Huber. Some constraints and tradeoffs in the design of network communications. SOSP 1975, phụ lục tr. 73–74.
• Jim Gray. Notes on Data Base Operating Systems. LNCS 60, 1978, mục 5.8.3.3.
• Halpern, Moses. Knowledge and common knowledge in a distributed environment. Journal of the ACM 37(3), 1990.
• Lamport, Shostak, Pease. The Byzantine Generals Problem. ACM TOPLAS 4(3), 1982.
• Martin Kleppmann. Distributed Systems, lecture notes. Cambridge, 2023/24.
• Apache Kafka 4.3. Design: Message Delivery Semantics.
• Apache Kafka 4.0. KafkaProducer Javadoc.
• librdkafka. CONFIGURATION.md.
• Confluent. Exactly-once Semantics is Possible: Here's How Apache Kafka Does it, 2017.
• Chris Richardson. Pattern: Transactional outbox.