Tìm hiểu bài toán đồng thuận trong hệ thống phân tán (Phần 2)
1. Giới thiệu
Ở Phần 1 mình đã giới thiệu các vấn đề liên quan tới bài toán đồng thuận trong hệ thống phân tán. Ở cuối bài mình có nhắc tới 2 thuật toán điển hình Raft và 2PC giúp ta giải quyết bài toán đồng thuận. Trong bài blog này mình sẽ giới thiệu cho các bạn về thuật toán 2PC.
2. Thuật toán 2PC
Ý tưởng của thuật toán rất đơn giản, nó tương tự câu chuyện mình kể đây:
- Sau nhiều năm đi học xa, bạn muốn tết này về quê tổ chức một buổi họp lớp đề hàn thuyên tâm sự. Trước hết bạn cần chọn ngày giờ họp lớp, sau khi đã chọn được ngày lành tháng đẹp và vì bạn chỉ còn giữ liên lạc với năm người bạn cũ nên bạn mong muốn mọi người đều có thể đi được trong một ngày nên bạn đã nhắn tin cho các bạn trong lớp hỏi các bạn trước có bận ngày đó không. Nếu các bạn trả lời đồng ý đi ngày đó, bạn sẽ nhắn tin để thông báo xác nhận với mọi người lần nữa là chúng ta có thể đi này đó. Nếu có ai đó không đồng ý thì bạn phải hủy họp lớp ngày đó.
Các bạn thấy đó ý tưởng thuật toán đồng thuận 2PC rất đơn giản. Trong thuật toán có 2 vài trò chính:
Leader (coordinator, master): đây chính là bạn trong câu chuyện. Nó có vai trò nhận yêu cầu từ phía Client và gửi đề xuất (propose) cho các node Acceptor. Bất kỳ node nào cũng có thể được chọn làm leader.Acceptor (cohort, replica): chính là các bạn của bạn. Đây là node nhận đề xuất của node Leader và bình chọn (vote) cho đề xuất đó.
Cách thuật toán hoạt động như thế nào, phần tiếp theo mình sẽ trình bày.
3. Cách hoạt động
Giống như tên của nó, thuật toán gồm 2 giai đoạn:
Giai đoạn 1 - Proposal:
- Khi nhận giá trị ghi mới từ phía Client, node Leader sẽ gửi đề xuất về giá trị đó cho tất cả các node Accepter trong hệ thống.
- Các node Acceptor sau khi nhận giá trị đề xuất từ node Leader thì chúng sẽ bình chọn. Nếu node đồng ý về giá trị đó nó sẽ gửi về node Leader tin nhắn
Ready(yes). Ngược lại nó sẽ gửiNot ready(no) khi không muốn đồng ý về giá trị đó. Các tin nhắn này là biến kiểu binary.
Giai đoạn 2 - Commit/Abort:
Khi tất cả các node Accepter gửi yêu cầu bình chọn, các node Acceptor sẽ bị block lại cho tới khi nhận được yêu cầu từ node Leader. Có hai trường hợp xảy ra:
- Nếu tất cả các node Acceptor đều đồng ý về giá trị mà node Leader để xuất thì node Leader sẽ gửi yêu cầu
Commitcho tất cả các node Acceptor. - Nếu node Leader nhận được yêu cầu không đồng ý từ bất kì node nào, thì node Leader sẽ gửi yêu cầu
Abortcho tất cả các node. - Sau đó các node Acceptor sẽ gửi ACK cho node Leader. Node Leader sau khi nhận được hết gói tin ACK thì xem như dữ liệu đó đã được đồng thuận. Cuối cùng node Leader sẽ gửi kết quả về cho Client.
Các bạn có thể xem chi tiết các bước ở đây.
Thuật toán trông có vẻ hoàn hảo nhưng nó vẫn còn gặp một số vấn đề về crashes và failures.
Crashes và Failures
Các node trong hệ thống phân tán có thể crash theo nhiều cách. Đơn giản nhất, node bị crash và không bao giờ phục hồi lại. Đây là mô hình lỗi fail-stop của hệ thống phân tán. Ngược lại, các node có thể sụp đổ và có thể phục hồi sau thất bại và tiếp tục thực thi. Đây gọi là mô hình fail-recovery.
Mình cùng điểm qua các vấn đề chính mà thuật toán 2PC gặp phải:
Vấn đề ở giai đoạn 1:
- Trước khi node Leader gửi đề xuất thì node Leader bị crash. Đơn giản là quá trình đồng thuận sẽ không bao giờ xảy ra. Hoặc node Acceptor bị crash, thì khi node Leader gửi đề xuất thì node này không nhận được yêu cầu, chúng ta có thể xử lí lỗi đó sau.
- Node Leader bị crash sau khi gửi đề xuất tới các node Acceptor. Lúc này một số node Acceptor sẽ nhận được đề xuất và bắt đầu vòng 2PC và một số node khác thì không nhận được đề xuất. Có 2 khả năng xảy ra ở đây, một là node Leader sẽ không bao giờ hồi phục lại. Trong trường hợp này những node nhận được đề xuất và gửi gói tin
commitcho node Leader sẽ bị block mãi mãi. Hai là node Leader có thể phục hồi lại trong thời gian ngắn, thì khi phục hồi lại nó sẽ nhận được gói tincommittừ node Acceptor và nó sẽ bắt đầu giai đoạn hai. Giải pháp lúc này là sẽ chọn một node bất kì trong hệ thống để thay thế node Leader và dựa vào log của các node để biết trạng thái hiện tại của quá trình. Các bạn xem chi tiết giải pháp ở đây. - Node Leader không nhận được đầy đủ tất cả gói tin bình chọn của các node Acceptor, có nghĩ là node Acceptor đã bị crash. Giải pháp tốt nhất lúc này là dựa vào
timeoutkhi chờ gói tin bình chọn từ các node. Khi timeout xảy ra thì node Leader sẽ gửi gói tinAbortcho tất cả các node Acceptor. - Sau khi gửi bình chọn node Acceptor bị crash. Trong trường hợp nếu node Leader đã nhận đủ các gói tinh bình chọn thì nó sẽ chuyển qua giai đoạn 2. Ngược lại nếu không nhận đủ thì giải pháp như trường hợp trên.
Vấn đề ở giai đoạn 2:
- Node Acceptor không nhận được gói tin commit hoặc abort từ node Leader. Có lẽ node Leader đã bị crash. Hoặc sau khi nhận commit/abort thì bị crash. Mình nghĩ giải pháp như vấn đề thứ hai trong giai đoạn 1 mình đã nói trên.
- Một vài node Acceptor bị crash trước khi node Leader được khôi phục, thì node Leader sẽ không biết node Acceptor đã bình chọn ready hay not ready. Lúc này node Leader có thể quyết định là sự đồng thuận có thành công hoặc không.
Ngoài ra còn một số vấn đề nhỏ khác trong thuật toán 2PC mà mình không trình bày, các bạn có thể tìm đọc thêm ở đây.
Node Leader thường sẽ ghi log lại kết quả của bất kỳ quá trình đồng thuận thành công trong bộ lưu trữ, để khi phục hồi, nó có thể trả lời các câu hỏi về việc giao dịch có được thực hiện hay không. Điều này cho phép thu thập rác định kỳ của log tại các node Acceptor: Node Leader có thể nói với các node rằng không node nào sẽ cố gắng khôi phục giao dịch được cam kết và họ có thể xóa sự tồn tại của nó khỏi log.
Chiến lược khi khôi phục/thay thế node Leader:
- Bất kì node Accepter nào detected được timeout của node Leader thì cũng có thể thay thế làm node Leader.
- Khi khôi phục lại, node Leader mới cần thu thập lại trạng thái của các node Acceptor. Đặt ra yêu cầu là các node Acceptor cũng phải ghi lại log trong quá trình bình chọn.
- Nếu như tất cả các node Acceptor đã bình chọn. Thì chúng ta có thể suy ra là giai đoạn Propose đã hoàn thành.
- Tất cả node Acceptor bình chọn ready thì node Leader mới sẽ gửi lại gói tin commit cho tất cả. Ngược lại sẽ gửi gói tin abort.
- Nếu khi kiểm tra trạng thái phát hiện có node Acceptor chưa bình chọn thì trường hợp này ta bắt buộc phải restart lại quá trình đồng thuận.
4. Ưu điểm, nhược điểm
Ưu điểm
Ưu điểm chính là thuật toán 2PC an toàn, vì trong trường hợp không có node nào bị crash thì tất cả các node Acceptor đều tham gia bình chọn của mình. Và khi có bất kì node nào bình chọn not ready thì kết quả cuối cùng đồng thuận là hủy bỏ.
Nhược điểm
Một trong những nhược điểm lớn nhất mà thuật toán 2PC gặp phải là hiện tượng block. Nếu node Leader bị crash thì các node Acceptor đã gửi bình chọn ready ở giai đoạn 1 sẽ bị block cho tới khi node Leader được phục hồi hoặc thay thế. Nhược điểm thứ hai là qúa trình đồng thuận sẽ không được kết thúc khi mà node Leader và các node Acceptor có node bị crash và không hồi phục lại được.
5. Kết luận
Thuật toán 2PC là một thuật toán đồng thuận đơn giản giải quyết được vấn đề đồng thuận giúp cho hệ thống phân tán của chúng ta được nhất quán mạnh mẽ. Nhưng thuật toán còn gặp nhiều nhược điểm khi có node trong hệ thống bị crash, ở Phần 3 mình sẽ trình bày về thuật toán Raft, và nó đã giải quyết những nhược điểm mà thuật toán 2PC gặp phải như thế nào, mời các bạn đón đọc.
