Bài toán đồng thuận trong Distributed Systems

Bài viết được sự cho phép của tác giả Huy Hoàng

Ví dụ về Distributed Systems được phát triển và sử dụng trong thực tế bao gồm hệ thống Database (SQL, NoSQL), hệ thống Cache (Redis, Memcached), hệ thống Message-Queue hay Publish/Subscribe (Kafka, RabbitMQ …). Những hệ thống này tuy có những tính năng khác nhau, tuy nhiên phần cốt lõi của chúng đều phải giải quyết một vấn đề cơ bản, đó là bài toán đồng thuận.

Như đã đề cập ở phần 1, một trông những tính chất của Distributed System là khả năng hoạt động như một thực thể thống nhất đối với người sử dụng. Để đạt được mục đích này thì trong quá trình hoạt động, các process trong hệ thống cần có được sự nhất trí về trạng thái dữ liệu (state) cũng như các bước vận hành tiếp theo (action). Do các process có thể không nằm cùng trên một máy tính vật lý nên chúng buộc phải giao tiếp qua network để đạt được sự nhất trí này. Tuy nhiên, cả máy tính lẫn network đều có thể gặp phải các sự cố, khiến cho việc giao tiếp để đảm bảo sự đồng nhất giữa các process trở nên không đơn giản.

Cách đạt được sự nhất trí giữa các process trong Distributed Systems, kể cả khi gặp sự cố, được gọi là bài toán đồng thuận (Distributed Consensus). Để hiểu rõ hơn bài toán này, trong bài viết này chúng ta sẽ bàn về hai ví dụ mang tính minh họa.

Bài toán hai vị tướng (Two generals problem)

Bài toán được phát biểu như sau: Có 2 vị tướng chỉ huy 2 đạo quân đóng ở các địa điểm khác nhau và cùng đối đầu với một đội quân đối phương. Hai vị tướng này cần đi đến một quyết định: cùng tấn công đối phương, hoặc cùng rút lui. Nếu họ cùng tấn công đối phương thì sẽ giành thắng lợi, nếu họ cùng rút lui thì sẽ bảo toàn được lực lượng. Ngược lại nếu hai vị tướng ra quyết định trái ngược (1 tấn công, 1 rút lui) thì họ sẽ bị đối phương đánh bại. Hai vị tướng có thể dùng giao liên để gửi thư cho nhau, tuy nhiên mỗi giao liên đều có khả năng bị đối thử bắt giữ, dẫn đến việc lá thư sẽ không được vận chuyển. Vậy 2 vị tướng trên cần dùng giao thức nào để có thể đi đến hành động thống nhất?

Trước khi tiếp tục bài viết, mình khuyến khích các bạn hãy thử tự tìm cách giải cho bài toán này. Về cơ bản, bài toán yêu cầu một trong hai vị tướng phải đề xuất ra hành động và gửi thư cho vị tướng còn lại để yêu cầu sự nhất trí. Tuy nhiên, làm cách nào để vị tướng đề xuất đó biết được rằng thông tin đã đến được tay vị tướng kia hay chưa?

Đối với những bạn có hiểu biết về mảng Computer Networking, có thể bạn sẽ nhận thấy bài toán này có nhiều điểm tương đồng với giao thức TCP/IP, là giao thức mạng được phát triển nhằm cho phép người gửi tin có thể đảm bảo rằng thông tin đã đến được phía người nhận. Chúng ta có thể áp dụng cách tiếp cận tương tự cho bài toán này, dựa trên giao thức DATA/ACK của TCP/IP. Một vị tướng (G1) sẽ đề xuất phương án và gửi thông tin cho người còn lại (G2). Khi nhận được thư, G2 sẽ thực hiện theo phương án được đề xuất và gửi thư xác nhận (ACK) cho G1. Nếu G1 nhận được thư xác nhận, G1 cũng sẽ thực hiện phương án đó.

Tuy nhiên, những mẩu thư liên lạc kể trên đều có thể bị mất dọc đường, theo như điều kiện của bài toán. Nếu thư G1->G2 bị mất, G2 sẽ không nhận được đề xuất. Tệ hơn nữa, nếu thư ACK bị mất, G2 sẽ tấn công trong khi G1 vẫn chưa quyết định được hành động. Vậy chúng ta giải quyết trường hợp này ra sao? Câu trả lời ngắn gọn ở đây là, bài toán không có lời giải hoàn hảo. Thật vậy, đối phương trên lý thuyết có khả năng chặn được tất cả liên lạc giữa 2 vị tướng, và trong trường hợp đó sẽ không có cách nào đạt được sự đồng thuận cả.

Ý nghĩa chính của bài toán 2 vị tướng có nhằm minh họa một điều, đó là không có lời giải “hoàn hảo” cho bài toán đồng thuận. Tuy nhiên, chúng ta có thể đưa ra một phương án mang tính “thực tế” hơn, bằng việc giả thiết rằng đối phương không phải lúc nào cũng có thể bắt được tất cả các thư liên lạc được gửi đi giữa 2 vị tướng. Theo đó, ta có thể cho G1 gửi lại đề xuất nếu không nhận được ACK sau một thời gian nào đó, cho đến khi nhận được ACK từ G2 (tương tự như cơ chế retransmission của TCP/IP).

Bài toán các vị tướng Byzantine (Byzantine General’s problem)

Viết tắt là BGP, bài toán này được phát biểu như sau: Có n vị tướng đến từ Byzantine (tên một đế quốc thời trung cổ nằm tại vùng Thổ Nhĩ Kỳ và đông nam châu Âu ngày nay), mỗi người chỉ huy một đội quân, cùng bao vây một thành trì của đối phương. Họ cần đạt được sự nhất trí về phương án hành động: hoặc tấn công (A), hoặc rút lui (R). Các vị tướng có thể liên lạc với nhau bằng cách gửi thư qua giao liên một cách an toàn (thông tin liên lạc không bị mất hay đánh tráo). Tuy nhiên, một vài trong số n vị tướng này là gián điệp của đối phương, và có khả năng gửi những mẩu tin bất kì, nhằm ngăn cản việc nhất trí của các đội quân còn lại. Yêu cầu bài toán đặt ra là: 1) tìm ra một giao thức để các vị tướng (không phải gián điệp) có thể nhất trí về hành động (A hoặc R), 2) tìm hiểu xem số lượng gián điệp ảnh hưởng đến giao thức trên như thế nào?

Bài toán này được nêu ra bởi nhà khoa học máy tính Leslie Lamport trong bài báo “The Byzantine Generals Problem“, và tên gọi của kiểu sự cố “Byzantine” (xem lại phần 1) được đặt theo tên bài toán này. Có nhiều người hay nhầm lẫn giữa bài toán này và bài toán 2 vị tướng (2GP) được nêu ở phần trước. Hai bài toán có một vài điểm khác biệt. Thứ nhất, BGP có một số lượng đội quân bất kì (thay vì chỉ 2 như 2GP). Thứ nhì, cả 2 vị tướng trong 2GP đều “trung thành”, trong khi BGP có một hoặc nhiều vị tướng là gián điệp. Thứ ba, ở 2GP, việc liên lạc giữa 2 đạo quân có thể bị gián đoạn, trong khi ở BGP chúng ta coi như liên lạc giữa các vị tướng là hoàn hảo.

Để đi đến lời giải, chúng ta hay thử bắt đầu lý luận từ một vài trường hợp đơn giản. Với n=1, bài toán trở nên tối giản, không có sự đồng thuận nào ở đây cả. Với n=2, ta có một lời giải tương đối đơn giản: một vị tướng sẽ đề xuất phương án v và gửi thư cho vị tướng còn lại, và cả 2 sẽ cùng thực hiện v. Do liên lạc giữa 2 vị tướng được đảm bảo, chắc chắn họ sẽ đạt được sự đồng thuận. Trong trường hợp một trong hai vị tướng là gián điệp, bất kì hành động nào của người còn lại đều hợp lệ.

Bài toán trở nên phức tạp hơn khi n=3. Trong tình huống đơn giản nhất với m=0 gián điệp, lời giải của chúng ta tương tự như trường hợp n=2. Một vị tướng G1 sẽ đề xuất phương án hành động v và gửi thông tin cho các vị tướng còn lại. Các vị tướng còn lại khi nhận được tin sẽ thực hiện theo v. Vậy nếu m=1 thì sao? Trong trường hợp này, người để xuất (G1) có thể là gián điệp và sẽ gửi những thông tin trái ngược nhau cho 2 vị tướng còn lại (G2 và G3). Chúng ta có thể thử dùng liên lạc giữa G2 và G3 để xác nhận lại thông tin. Kể cả vậy, nếu G1 là gián điệp, G2 và G3 vẫn sẽ nhận được những thông tin không thống nhất về phương án hành động v. Thật vậy, nếu G1 gửi A cho G2 và R cho G3, G2 và G3 sẽ nhận nhìn thấy những thông tin như sau:

// G2, G3 là các vector chứa thông tin phương án nhận được từ G1. Phần tử [0] là thông tin nhận được từ G1, [1] là thông tin nhận được từ vị tướng còn lại. 
G2: [A R]
G3: [R A]

Điều tương tự xảy ra khi G2 hay G3 là gián điệp. Điều này dẫn đến việc G2 hoặc G3 không xác định được gián điệp là ai, và không thể thống nhất được phương án v. Một cách tổng quát hơn, BGP không có lời giải cho trường hợp n vị tướng và m gián điệp nếu 3m >=n .

Nói cách khác, BGP chỉ có thể giải được khi số gián điệp nhỏ hơn 1/3 số vị tướng (3m < n). Thuật toán để giải bài toán này được gọi tên là Byzantine Fault Tolerance (BFT). Chi tiết về thuật toán (và cách chứng minh) tương đối phức tạp nên mình sẽ không trình bày ở đây (khuyến khích các bạn đọc thuật toán này trong bài báo của Lamport). Tuy nhiên mình sẽ tóm tắt một vài ý chính:

• Ý tưởng: Các vị tướng được chia thành 2 vai trò: 1 vị tướng đóng vai trò chỉ huy (C), những người còn lại là các phó tướng (L). Chỉ huy sẽ đề xuất phương án v và các phó tướng sẽ làm theo. Để đạt được yêu cầu bài toán kể cả khi chỉ huy C là gián điệp, các phó tướng sẽ thông tin cho nhau biết xem phương án v mà mình nhận được là gì. VD, phó tướng L3 sẽ gửi v3 (nhận được từ C) cho các phó tướng còn lại. Sau khi quá trình này kết thúc, mỗi phó tướng L sẽ có được một vector các giá trị mà các phó tướng nhận được từ chỉ huy: L = [v1 v2 ... v_(n-1)], và sẽ chọn giá trị nào chiếm đa số.
• Tuy nhiên, L3 nói trên có thể là gián điệp và có thể gửi các giá trị v3 khác nhau cho các phó tướng còn lại. Vậy trường hợp này giải quyết ra sao? Nếu L3 là gián điệp thì v3 thực tế vô nghĩa. Điều quan trọng duy nhất ở đây là các phó tướng (không phải gián điệp) đồng thuận với nhau về v3. Ta có thể đạt được sự đồng thuận này bằng cách giải một bài toán đồng thuận “con”, tương tự như bài toán gốc nhưng loại bỏ đi chỉ huy C. Thay vào đó, L3 giờ đóng vai trò chỉ huy, nhằm mục đích thống nhất về giá trị v3 giữa các phó tướng còn lại. Đây là lời giải theo kiểu đệ quy. Do lời giải này chỉ có ý nghĩa khi C là gián điệp, nên số gián điệp trong hệ thống “con” này là m-1. Quá trình đệ quy này được lặp lại m lần đối với mỗi phó tướng, cho đến trường hợp m=0 (là trường hợp đơn giản đã bàn ở trên).
• Performance của lời giải: Độ phức tạp (complexity) xét về mặt số lượng thông tin cần gửi đi của lời giải này là O(n^m), do kết quả của quá trình đệ quy. Điều này có nghĩa là với lời giải trên có tính thực tế không cao trong các hệ thống lớn gồm nhiều process (do số thông tin cần gửi ở đây tăng theo cấp số nhân). Đã có nhiều nghiên cứu cải tiến lời giải nhằm cải thiện hiệu năng của bài toán này, như pBFT, Speculative Byzantine Fault Tolerance…

Ứng dụng thực tế của thuật toán BFT

Thuật toán BFT (và các biến thể) nhằm giải quyết vấn đề consensus cho các hệ thống mà có thể sẽ gặp phải kiểu sự cố Byzantine (mời xem lại định nghĩa về kiểu sự cố này ở phần 1). Ví dụ về các hệ thống này bao gồm Blockchain, các hệ thống hàng không vũ trụ của NASA hay SpaceX…

Tuy nhiên, trong hầu hết các ứng dụng Internet thực tế, kiểu sự cố Byzantine hiếm khi xảy ra (so với các kiểu sự cố khác như fail-stop, fail-recover). Lý do là vì: 1) các hệ thống DS như Database, Message Queue … thường được triển khai ở trong một môi trường an toàn (thường là trong các data center có sự kiểm soát tốt về mặt kết nối mạng thông qua tường lửa…), tách biệt với các cá thể có ý định tấn công từ bên ngoài; 2) kết nối của hệ thống với môi trường Internet bên ngoài thường được mã hóa dựa trên những giao thức bảo mật như SSL. VD như, khi bạn đọc blog này với đường link bao gồm “https“, bạn được đảm bảo rằng nội dung của blog thực sự đến từ người viết chứ không bị đánh tráo; 3) các giao thức được chuẩn hóa như TCP/IP, HTTP… cũng giúp bảo vệ cho hệ thống khỏi những lỗi Byzantine được gây ra do trục trặc từ phần cứng.

Nói thế để thấy rằng, tuy thuật toán BFT tương đối phức tạp và có hiệu năng thấp, chúng ta cũng không cần phải lo đến việc áp dụng thuật toán này cho dự án của mình. Trong các phần sau, chúng ta sẽ bàn thêm về các thuật toán Consensus cho các hệ thống được coi như “miễn dịch” với kiểu sự cố Byzantine.

Bài viết gốc được đăng tải tại dhhoang.github.io

Có thể bạn quan tâm:

• [P1] Tổng quan về Distributed Systems
• Học lập trình Java từ đâu và như thế nào?
• Máy học – Machine Learning và một vài hạn chế

Xem thêm các việc làm Developer hấp dẫn tại Station D