Vòng lặp nợ nần không bị kẹt vì những con số

Trong bộ phim Moana, cả một đại dương với những hòn đảo đang lụi tàn chỉ vì một viên đá xanh nhỏ bé chưa hoàn thành được vòng lặp của nó. Ba người bạn nợ nhau 100 đô cũng đang bị kẹt lại vì lý do tương tự.

Hãy tưởng tượng ba người — A, B, và C — nợ tiền lẫn nhau theo một vòng tròn. B nợ A 100 đô. C nợ B 100 đô. A nợ C 100 đô. Đột nhiên, người thứ tư là D xuất hiện, đưa 100 đô cho A. Sau một vài lượt trả tiền qua lại, mọi khoản nợ đều được xóa sạch, và D cầm lại 100 đô của mình rồi rời đi.

Lần đầu thấy câu đố này, mình chỉ nghĩ nó là một trò ảo thuật: chỉ một tờ tiền mà xóa được tận 300 đô tiền nợ. Đó thường là phần mà mọi người hay nhớ nhất. Nhưng càng ngồi suy ngẫm, mình lại càng thấy phần tiền bạc không thú vị bằng sự bế tắc của nó. Nếu các khoản nợ về mặt giấy tờ đã tự triệt tiêu lẫn nhau (toán học ở đây cực kỳ đơn giản), thì tại sao cái vòng lặp này lại cần một người bên ngoài nhảy vào?

Đó là lúc câu đố không còn là chuyện tiền nong nữa. Một khi bạn vẽ lại các khoản nợ này dưới dạng một chu trình có hướng (directed cycle) trong đồ thị, câu đố này trở thành một thứ mà các giáo trình hệ điều hành đã đặt tên từ lâu: deadlock (tình trạng bế tắc). 100 đô của D không phải dùng để trả 300 đô nợ. Nó dùng để phá vỡ sự chờ đợi vòng quanh bằng cách đẩy một đơn vị chuyển động đi hết vòng chu trình đó.

Những khoản nợ chỉ trông phức tạp cho đến khi bạn vẽ chúng thành đồ thị

Một khoản nợ thật ra là mối quan hệ giữa hai người: ai nợ, nợ ai, và nợ bao nhiêu. Cách gọn gàng nhất để ghi lại điều đó là dùng một đồ thị có hướng và có trọng số (directed weighted graph) — các đỉnh đại diện cho người, các cạnh có hướng đại diện cho hành động "nợ", và trọng số trên cạnh chính là số tiền.

Cuốn Grokking Algorithms của Aditya Bhargava định nghĩa về chu trình (cycle) một cách rất bình dân: "bạn có thể bắt đầu từ một nút, đi một vòng và kết thúc tại chính nút đó." Đây chính xác là những gì đang diễn ra: ba đỉnh, ba cạnh, một vòng lặp.

Điều đầu tiên mà đồ thị này tiết lộ là số dư ròng của mỗi người đều bằng không.

Nói một cách trang trọng hơn, đây là định luật bảo toàn tại mỗi đỉnh — nó có cùng hình thái với định luật dòng điện Kirchhoff trong một mạch điện:

Nếu số dư ròng của mọi người đều bằng không, toàn bộ hệ thống đang ở trạng thái bảo toàn. Về lý thuyết, không cần một đồng tiền thật nào phải di chuyển cả — cả ba có thể đồng ý rằng "chúng ta nợ nhau cùng một số tiền, coi như huề nhé" rồi ai về nhà nấy. Các ngân hàng gọi đây là bù trừ đa phương (multilateral netting), và các trung tâm thanh toán bù trừ sử dụng nó hàng ngày để nén hàng triệu nghĩa vụ nợ thô thành một tập hợp nhỏ các vị thế ròng.

Toán học thì tự triệt tiêu, nhưng vòng lặp vẫn kẹt vì thiếu thanh khoản

Đây mới là lúc câu đố trở nên hay ho. Toán học thì ổn. Đồ thị cũng ổn. Nhưng hãy thử đặt mình vào bên trong vòng lặp đó một chút xem sao.

A đang cháy túi và sẽ không trả cho C cho đến khi B trả cho A trước. B cũng hết tiền và sẽ không trả cho A cho đến khi C trả cho B. C cũng tương tự, không trả cho B cho đến khi A trả cho C. Ai cũng đang nắm giữ một quyền đòi nợ. Ai cũng đang đợi một người cũng đang đợi người khác. Không ai nhúc nhích.

Mẫu hình đó có một cái tên. Trong hệ điều hành, deadlock (bế tắc) xảy ra khi và chỉ khi bốn điều kiện sau xuất hiện đồng thời — cái mà Coffman gọi là các điều kiện gây ra deadlock: chỉ cần bỏ đi một điều kiện, chu trình sẽ không thể hình thành:

Cả bốn điều kiện đó đều được thỏa mãn ở đây. Các khoản nợ có tính loại trừ (một đồng đã trả là một đồng đã di chuyển, không thể tự nhân đôi). Mỗi người đang giữ quyền đòi nợ của mình trong khi chờ người tiếp theo. Không ai có quyền can thiệp trước — A không thể tự tiện thò tay vào ví của C. Và mẫu hình chờ đợi là vòng quanh, đây chính là điều kiện cốt lõi của deadlock.

Điều mình thích ở cách đặt vấn đề này là nó tách biệt rõ ràng hai câu hỏi mà thoạt nhìn tưởng là một. Các khoản nợ này có thể xóa bỏ được không? — Có, toán học nói vậy. Các khoản nợ này có tự xóa bỏ được không? — Không, vì vòng lặp đang bị kẹt do thiếu thanh khoản, chứ không phải do sai sót tính toán. Một bảng cân đối kế toán có tổng ròng bằng không vẫn cần ai đó, ở đâu đó, thực hiện bước đi đầu tiên.

Đây không phải là một sự so sánh ví von — nó chính là cùng một đồ thị

Đến đây bạn có quyền nghi ngờ. Đúng là vòng lặp nợ và deadlock trong hệ điều hành nghe có vẻ giống nhau. Nhưng nợ là chuyện ghi chép sổ sách trừu tượng, còn các tiến trình (process) thì nắm giữ tài nguyên thật. Chẳng lẽ đây không phải chỉ là một sự ẩn dụ thú vị thôi sao?

Quay lại với môn CSE 120: Các nguyên lý của hệ điều hành máy tính với Giáo sư Geoffrey Voelker, bài giảng về deadlock đã định nghĩa một thứ gọi là đồ thị chờ đợi (waits-for graph) — một đồ thị có hướng mà một cạnh từ P đến Q có nghĩa là tiến trình P đang đợi một cái khóa (lock) mà Q đang nắm giữ. Hãy thay "khóa" bằng "thanh khoản" và "tiến trình" bằng "con người", bạn sẽ có ngay đồ thị nợ nần. Cùng các nút, cùng các cạnh, cùng một định nghĩa. Giáo trình hệ điều hành không mượn khái niệm này từ tài chính; tài chính chỉ là một nơi khác mà khái niệm này xuất hiện thôi.

Ví dụ của Giáo sư Voelker đã hoàn toàn thuyết phục mình. Thầy vẽ ba tài nguyên đơn lẻ và ba tiến trình trong một chu trình — P1 giữ R1 và đợi R2, P2 giữ R2 và đợi R3, P3 giữ R3 và đợi R1. Ba nút, ba cạnh, một sự chờ đợi vòng quanh. Sau đó thầy thêm một tiến trình P4 nằm ngoài chu trình, đang giữ một phiên bản thứ hai của một trong các tài nguyên đó. Khi P4 giải phóng tài nguyên đó, chu trình sẽ được gỡ rối chỉ trong một lượt xoay vòng. P4 chính là D. "Một phiên bản tài nguyên dư thừa được giữ bên ngoài chu trình" chính là 100 đô của D. Giáo trình hệ điều hành đã vẽ sẵn bức tranh này rồi — câu đố chỉ đơn giản là "tô màu" nó bằng tiền bạc thôi.

100 đô của D không phải là tiền — nó là một thẻ bài (token)

Đây là phần đã định hình lại cách mình nghĩ về D. Câu đố gọi đóng góp của D là 100 đô, và trên hóa đơn thì đúng là vậy. Nhưng về mặt chức năng, tờ tiền của D là một thẻ bài (token) — một vật thể duy nhất phải đi qua toàn bộ chu trình đúng một lần để gỡ kẹt cho tất cả.

Hãy để ý điều gì xảy ra tại mỗi nút. Tờ tiền đến, nghĩa vụ nợ được giải tỏa, tờ tiền lại tiếp tục di chuyển. Không ai kết thúc với số tiền dư ra. Không ai phải trả nhiều hơn số tiền mình nợ. Tổng số tiền trong hệ thống luôn là 100 đô — và 100 đô đó luôn thuộc về D. Họ cho hệ thống mượn "nhịp đập" đầu tiên, chu trình chạy một vòng, và nhịp đập đó quay trở về nhà.

Đây cũng là lý do tại sao thứ tự thanh toán trông giống như một hàng đợi (queue) chứ không phải kiểu "mọi người cùng trả một lúc". Cuốn Grokking Algorithms mô tả hàng đợi là FIFO — vào trước, ra trước (first in, first out) — nơi bạn xử lý theo thứ tự mà các phần tử được thêm vào. Tờ tiền của D được xử lý đúng như vậy: mỗi người cầm nó, dùng nó để tất toán một khoản nợ, rồi chuyển tiếp đi. Một tờ tiền, một bước nhảy, một cạnh được xóa sạch.

Những khoản nợ không bằng nhau không làm hỏng trò chơi — chúng chỉ để lại một chút "cặn"

Có bạn sẽ thắc mắc: Đúng là nó hiệu quả vì mọi cạnh đều là 100 đô. Nếu các khoản nợ không bằng nhau thì sao? Chẳng lẽ trò ảo thuật này không bị phá sản à?

Thật ra là không, nhưng kết quả sẽ trông "thật thà" hơn. Khi một chu trình có trọng số không bằng nhau, bạn vẫn có thể triệt tiêu — bạn chỉ triệt tiêu tối đa bằng đúng giá trị của cạnh nhỏ nhất. Cạnh nhỏ nhất đó chính là nút thắt cổ chai (bottleneck), và quy trình này được gọi là thuật toán triệt tiêu chu trình (cycle-cancellation algorithm), một khối xây dựng cơ bản của các thuật toán luồng chi phí tối thiểu (min-cost flow) từ công trình của Ford và Fulkerson năm 1962 về luồng trong mạng lưới:

Về mặt ký hiệu, với một chu trình C trong đồ thị G, quy tắc cập nhật cho mỗi trọng số cạnh là:

Mỗi trọng số mới trong chu trình sẽ giảm đi đúng bằng giá trị nút thắt. Ít nhất một cạnh sẽ trở về bằng không (chính là cạnh nút thắt), và cạnh đó sẽ bị loại bỏ.

Giả sử B nợ A 100 đô, C nợ B 80 đô, và A nợ C 60 đô. Nút thắt là giá trị nhỏ nhất trong ba số — 60 đô. Trừ con số đó vào mỗi cạnh trong chu trình:

Những gì còn lại không còn là một chu trình nữa. B vẫn nợ A 40 đô và C vẫn nợ B 20 đô — một đồ thị có hướng không chu trình (DAG), thứ có thể được giải quyết một cách tuyến tính mà không gặp bất kỳ deadlock nào. Trường hợp các khoản nợ bằng nhau không phải là ngẫu nhiên; đó chỉ là trường hợp mà đồ thị còn lại hoàn toàn trống rỗng.

Chu trình trong đồ thị có hướng không phải để trang trí — đó là nơi dòng chảy bị mắc bẫy

Một khi bạn bắt đầu để ý đến mẫu hình này, bạn sẽ thấy nó ở khắp mọi nơi có dòng chảy cần được duy trì. CHIPS — Hệ thống Thanh toán Liên ngân hàng của các Trung tâm Thanh toán Bù trừ — xử lý khoảng 1,8 nghìn tỷ đô thanh toán hàng ngày thông qua một thuật toán bù trừ đa phương đã được cấp bằng sáng chế, nơi 1 đô vốn hỗ trợ tới 29 đô giá trị thanh toán được quyết toán. Tỷ lệ 1:29 đó chính là trò mà D đã thực hiện với 100 đô: một đơn vị thanh khoản nhỏ có thể giải tỏa gấp nhiều lần chính nó khi đồ thị nghĩa vụ nợ có các chu trình để bù trừ. Các mạng lưới thanh toán cũng làm điều tương tự với một lượng thanh khoản nhỏ làm cầu nối cho các "giấy ghi nợ vòng quanh". Ngay cả tình trạng tắc nghẽn giao thông tại các ngã tư bốn chiều cũng trông giống như thế này: mỗi chiếc xe chiếm một vị trí, đợi chiếc khác, và một tài xế tự tin di chuyển trước chính là "tờ 100 đô" của tình huống đó.

Lý do mà thuật toán BFS xuất hiện gần đây cũng tương tự. Grokking Algorithms lưu ý rằng BFS hoạt động trên các đồ thị không trọng số "để tìm đường đi ngắn nhất", lan tỏa ra ngoài từng cấp độ một, được xử lý theo thứ tự được thêm vào — một hàng đợi. "Thẻ bài" của chúng ta không tính toán khoảng cách, nhưng nó mượn cùng một hình thái: thăm các nút theo thứ tự chúng được tiếp cận, không bao giờ thăm lại, hoàn thành chuyến đi và dừng lại. Toàn bộ quá trình giải quyết chính là một lượt quét kiểu BFS quanh một chu trình duy nhất.

Đây cũng là lý do tại sao thuật toán Dijkstra, thứ mà Bhargava giới thiệu ngay sau BFS, lại tránh các chu trình thay vì sử dụng chúng: trong bài toán tìm đường đi ngắn nhất, việc đi vòng quanh một chu trình chỉ làm tăng thêm trọng số mà không thay đổi đích đến của bạn. Nhưng trong một bài toán thanh toán bù trừ, đi quanh chu trình chính là mục đích cốt lõi — bạn không cố gắng giảm thiểu khoảng cách, bạn đang cố gắng giải tỏa từng cạnh nợ.

Bốn cách để xử lý một chu trình bị kẹt

Bài giảng của Giáo sư Voelker liệt kê bốn chiến lược kinh điển để xử lý deadlock. Mỗi chiến lược đều có một phiên bản tương đương trong thế giới thực về cách các hệ thống xử lý dòng tiền bị kẹt:

Bất kỳ hệ thống dòng chảy bị kẹt nào mà bạn từng quan sát — một chuỗi cung ứng bị đóng băng, một đợt trả lương chậm lan truyền trong một startup, hay một bữa tối nhóm mà không ai muốn thanh toán — bạn sẽ thấy mọi người đang âm thầm chọn một trong bốn cách này. Biết được cách nào đang được sử dụng chính là phần quan trọng nhất của việc "chẩn đoán bệnh".

Hãy thử ngay tối nay

Mở Splitwise trên điện thoại của bạn và bật tính năng "Simplify debts". Cái nút gạt đó chính là đang chạy thuật toán triệt tiêu chu trình trên đồ thị nợ giữa bạn và những người bạn cùng phòng — chính xác là thuật toán trong bài viết này, trên một đồ thị nhỏ hơn. Thanh toán một bữa tối nhóm trong tuần này và bạn chính là một người dùng thuật toán Ford-Fulkerson rồi đấy.

Mạng Lightning của Bitcoin cũng gặp phải vấn đề tương tự ở quy mô internet. Khi thanh khoản bị kẹt ở một phía của kênh thanh toán, những người vận hành sẽ chạy "tái cân bằng vòng quanh" (circular rebalance) — một khoản thanh toán mà nút mạng tự gửi cho chính nó thông qua một đường dẫn vòng tròn của các kênh khác. Cùng một nước đi như D, nhưng bằng mật mã thay vì tiền mặt.

Một điều mình rút ra được

Hai thuật toán trông gần như giống hệt nhau trên bề mặt — cả hai đều đi qua các cạnh trong một đồ thị có hướng có trọng số — nhưng lại đối xử với chu trình theo hai cách hoàn toàn trái ngược. Dijkstra tránh các chu trình vì chúng chỉ làm tăng thêm trọng số cho con đường ngắn nhất. Còn thanh toán bù trừ lại cố tình đi hết chu trình vì chu trình chính là cơ chế giải tỏa. Cùng một cấu trúc dữ liệu, nhưng ngữ nghĩa thì ngược lại. Lần tới khi bạn thấy một thuật toán đồ thị, câu hỏi đáng để hỏi đầu tiên không phải là nó hoạt động như thế nào — mà là mục đích của việc đi xuyên qua đồ thị đó là gì.

Nguồn tham khảo

• Aditya Y. Bhargava, Grokking Algorithms, Second Edition — Dùng để: lấy định nghĩa về chu trình, đồ thị có trọng số và không trọng số, BFS, hàng đợi (FIFO), và mối quan hệ của Dijkstra với chu trình trong các bài toán tìm đường đi ngắn nhất.
• Coffman, E. G., Elphick, M., Shoshani, A. (1971), "System Deadlocks", ACM Computing Surveys — Dùng để: tham chiếu bốn điều kiện của deadlock (loại trừ tương hỗ, giữ và đợi, không có quyền ưu tiên, chờ đợi vòng quanh).
• Ford, L. R., Fulkerson, D. R. (1962), Flows in Networks — Dùng để: tìm hiểu nguồn gốc của thuật toán triệt tiêu chu trình trong luồng mạng lưới.
• Geoffrey M. Voelker, CSE 120: Principles of Computer Operating Systems, UC San Diego, Bài giảng 8 (Lập lịch và Deadlock) — Dùng để: lấy định nghĩa về đồ thị chờ đợi (waits-for graph), ví dụ về chu trình ba tiến trình/ba tài nguyên, và khung bốn chiến lược xử lý deadlock.
• The Clearing House, CHIPS — Clearing House Interbank Payments System — Dùng để: lấy dữ liệu về khối lượng giao dịch 1,8 nghìn tỷ đô hàng ngày và tỷ lệ hiệu quả bù trừ đa phương 1:29.
• Splitwise, "What does the Simplify Debts setting do?" — Dùng để: lấy ví dụ thực tế về thuật toán triệt tiêu chu trình trên ứng dụng người dùng.
• Lightning Network, Managing Liquidity — Dùng để: lấy ví dụ hiện đại về "tái cân bằng vòng quanh" trong tiền mã hóa.