Thuật toán đồng thuận trong hệ thống phân tán – Raft, Zookeeper Atomic Broadcast

1. Bài toán toán đồng thuận trong hệ thống phân tán

Bài toán đồng thuận trong hệ thống phân toán cho phép nhiều process đạt được đồng thuận trên cùng một giá trị. Theo định lí FLP, trong một hệ thống bất đồng bộ không thể đạt được trạng thái đồng thuận trong một khoảng thời gian giới hạn. Ngay cả khi việc gửi message trong hệ thống được đảm bảo, không có cách nào để kiểm tra liệu một process bị crash hoặc chậm.

Định lí FLP

Định lí FLP giả sử hệ thống là bất đồng bộ, các process không chia sẻ thời gian với nhau. Các thuật toán hoạt động không thể áp dụng timeout cho process. Do đó, một process không có cách nào để nhận biết các process khác bị crash hay slow. Định lí này chỉ ra không tồn tại một giao thức đảm bảo đồng thuận trong khoảng thời gian xác định với các điều kiện trên.

FLP Impossibility Problem – Fisher, Lynch, and Paterson

Các thuật toán đồng thuận có 3 thuộc tính chính:

• Agreement
  • Giá trị quyết định cuối cùng phải giống nhau ở tất cả process.
• Validity
  • Giá trị quyết định được đề xuất bởi một trong các process của hệ thống. Mục đích của tính chất này để đảm bảo sự cần thiết của đồng thuận trong hệ thống. Thuật toán đồng thuận yêu cầu tất cả process cùng đồng ý về một giá trị. Nếu các process sử dụng giá trị có sẵn thay vì một giá tri được đề xuất, hệ thống sẽ đạt được sự nhất trí về giá trị nhưng output của thuật toán sẽ không phù hợp với yêu cầu trong thực tế.
• Termination
  • Tất cả các process cuối cùng phải đưa ra được quyết định (tính eventually). Thuật toán sẽ hoạt động mãi mãi nếu không có tính chất “dừng” hoặc chờ vô thời hạn khi một process gặp sự cố.

2. Raft

Raft là thuật toán đồng thuận được ra đời để giải quyết bài toán sao lưu log trong hệ thống phân tán, đảm bảo tính an toàn và nhất quán. Mục đích của Raft còn để thay thế cho họ các thuật toán Paxos trước đây có nhược điểm và khó hiểu và khó triển khai trong thực tế.

Thông tin trong một cụm phân tán cài đặt Raft giao tiếp thông qua giao thức RPCs. Raft được thiết kế dựa theo các mục tiêu:

• Chia nhỏ vấn đề cần giải quyết
• Giảm số lượng trạng thái cần kiểm tra
• Xử lý vấn đề lựa chọn trong hệ thống bằng các chọn các giá trị ngẫu nhiên để giảm độ phức tạp

Ý tưởng của Raft chia việc quản lí sao lưu log thành 3 tác vụ chính:

• Leader election: bầu chọn leader khi một leader cũ bị crash

• Log replication: leader nhận log từ client và sao lưu sang các node còn lại trong cluster

• Safety: sử dụng request state machine để đảm bảo tính nhất quán log giữa các node, chỉ có node ở trạng thái up-to-date mới có thể được chọn làm leader

Chúng ta sẽ đi tìm hiểu kĩ hơn về các tác vụ này ở những phần sau

>> Thuật toán về tìm kiếm theo chiều sâu DFS bằng ngôn ngữ C/C++

>> Thuật toán về duyệt các thành phần liên thông của đồ thị bằng C/C++

2.1. Các thành phần của Raft

2.1.1. Server states

Mỗi node trong một cụm server cài đặt Raft có thể ở 1 trong 3 trạng thái:

• Leader:

Một node khi nhận đủ số vote từ các node khác trong cụm và thỏa mãn điều kiện của Raft(1) sẽ chuyển sang trạng thái leader. Node này sẽ có trách nhiệm xử lý các request từ client đến cụm và quản lí sao lưu dữ liệu sang các node còn lại.

• Follower

Tất cả các node được khởi tạo ở trạng thái follower. Một node ở trạng thái follower chịu trách nhiệm phản hồi lại request từ các node khác trong cụm. Khi có request từ client đến node follower thì request đó sẽ được forward sang cho leader hiện tại của cụm.

• Candidate

Node đang ở trạng thái follower chuyển sang trạng thái candidate khi một cuộc bầu chọn mới trong cụm được khởi tạo. Một candidate khi nhận đủ số vote và thỏa mãn điều kiện của Raft(1) sẽ trở thành leader

2.2.2. Term

Term là khái niệm Raft dùng để đánh dấu các khoảng thời gian từ khi một cuộc bầu chọn leader bắt đầu đến khi bắt đầu một cuộc bầu chọn mới. Mỗi term có duy nhất 1 leader được chọn.

2.2.3. Log

Một log được chia thành các entry dùng để lưu trữ các thông tin bao gồm data, command, term của mỗi node. Mỗi term được đánh số tương ứng với entry đang chứa nó.

2.2.4. Log entry

Một entry gồm 3 thành phần chính data, index và term.

2.2.5. Communicate

Các node trong cụm Raft giao tiếp với nhau thông qua việc gửi các request sử dụng giao thức RPCs. Các request này được chia làm 2 loại:

2.2. Raft subproblems

Như đã nói ở trên, Raft được thiết kế với ý tưởng chia nhỏ các vấn đề để giải quyết. Có 3 vấn đề chính của Raft cần xử lý bao gồm:

• Leader election
• Log replication
• Safety

2.2.1. Leader election

Để điều phối các hoạt động trong hệ thống, Raft bầu chọn ra một node làm leader. Ban đầu các node khởi tạo ở trạng thái follower. Nếu một node không nhận được “tín hiệu” từ leader sau một khoảng thời gian thì node nó sẽ chuyển sang trạng thái candidate và bắt đầu một cuộc bầu chọn mới. Một candidate trở thành leader nếu nhận được đa số vote từ các node trong cụm.

Chi tiết quá trình bầu chọn leader:

• Raft sử dụng 2 giá trị timeout để quản lí quá trình bầu chọn leader:
  • Election timeout: Khoảng thời gian chờ của một follower cho đến khi chuyển sang trạng thái candidate. Sau khi hết thời gian timeout, follower sẽ chuyển trạng thái sang candidate và bắt đầu một term bầu chọn. Candidate này sẽ vote cho chính nó và gửi RequestVote đến các node còn lại trong hệ thống.
  • Heartbeat timeout
• Nếu node nhận được RequestVote chưa từng vote trong term bầu chọn hiện tại thì nó sẽ vote cho candidate đã gửi request và reset lại thời gian timeout của node đó.

• Khi một node nhận được đủ quorum vote từ các node trong hệ thống, thì node đó sẽ chuyển trạng thái từ candidate sang leader

• Leader sau đó gửi các request AppendEntries đế các follower, các request này được gửi trong một khoảng thời gian xác định gọi là heartbeat timeout.

• Follower sau khi nhận được request sẽ phản hồi lại cho leader. Term hiện tại sẽ kết thúc khi một follower không nhận được heartbeat từ leader và bắt đầu một term bầu chọn leader mới.

Để đảm bảo chỉ có một candidate được chọn trở thành leader trong team, Raft thêm vào một số điều kiện:

• Mỗi server chỉ vote cho duy nhất một candidate
• Bổ sung thêm một số điều kiện của hệ thống (Safety)

Một cuộc bầu chọn leader trong Raft có thể gặp phải trường hợp không chọn được leader (split vote). Khi đó không node nào trong hệ thống nhận đủ số vote để trở thành leader. Một ví dụ về việc không chọn được leader như sau:

Giả sử hệ thống có 4 node A, B, C, D đang hoạt động và có 2 node C và D cùng bắt đầu một cuộc bầu chọn tại term 4:

Cả node C và D đều có 2 vote từ một node khác và chính nó và không thể nhận thêm vote do trở thành candidate cùng lúc. Do đó, trong term 4, hệ thống không thể chọn ra được leader.

Để giải quyết trường hợp này, Raft sử dụng timeout ngẫu nhiên cho mỗi node trong mỗi lần bầu chọn để đảm bảo giảm khả năng xảy ra tình trạng không đủ số vote quá bán. Thời gian timeout được chọn trong khoảng 150-300 ms. Mỗi khi xảy ra timeout trên một node thì cuộc bầu chọn mới sẽ được bắt đầu. Tuy nhiên cách làm này cũng có thể gây ra vấn đề về tính available của hệ thống trong trường hợp phải đợi timeout.

2.2.2. Log replication

Sau khi hệ thống chọn ra được leader, node này sẽ chịu trách nhiệm xử lý các request từ client và sao lưu dữ liệu lưu trữ dưới dạng các log entries sang các node còn lại trong hệ thống sử dụng request AppendEntries. Trong trường hợp một node trong hệ thống gặp sự cố (crash, network,…) thì leader sẽ gửi lại request cho đến khi tất cả các node follower trong hệ thống thực hiện xong quá trình sao lưu.

Cách tổ chức log trong Raft:

• Mỗi log entry được gắn term index tương ứng để xác định vị trí. Index này có tác dụng đảm bảo tính nhất quá về dữ liệu giữa các node và khôi phục lại dữ liệu khi có sự cố.
• Raft có cơ chế để duy trì trạng thái đồng bộ log giữa các node bằng cách:
  • So sánh entry: Nếu 2 entry ở 2 log khác nhau có cùng index và term thì 2 entry này lưu cùng một command
  • So sánh index: Nếu 2 entry ở 2 log khác nhau có cùng index và term thì 2 log này chứa cùng các entry giống nhau ở các term trước đây.
• Trong trường hợp logs giữa các node bất đồng bộ (xảy ra khi leader hoặc follower gặp sự cố – crash, network) follower có thể bị thiếu các entry do không nhận được cập nhật từ leader hoặc có thêm các entry mà leader không có. Để đồng bộ lại log giữa các node, Raft đưa ra cách giải quyết:
  • Follower sao lưu toàn bộ log của leader hiện tại
  • Các entry bị conflict của follower được ghi đè
  • Leader tìm đến entry đúng cuối cùng trong log, xóa tất cả các entry sau đó của follower rồi gửi lại các entry đúng để follower cập nhật

2.2.3. Safety

Raft bổ sung thêm các ràng buộc để đảm bảo tính đồng nhất giữa các log. Nhờ các ràng buộc này, hệ thống đảm bảo leader từ bất kì term nào mang đầy đủ các entry đã được commit ở term trước đây, do đó không cần phải chuyển các entries cũ cho leader mới, đơn giản hóa quá trình bầu chọn, commit log. Cơ chế vote của Raft bổ sung thêm điều kiện cho candidate muốn trở thành leader cần phải chứa tất cả entries đã được commit.

Trong trường hợp các node follower và candidate crash, Raft đưa ra các xử lý như sau:

• Nếu follower hoặc candidate bị crash, thì các request RequestVote RPC và AppendEntries RPC gửi đến sẽ fail, khi đó, các request này sẽ được gửi lại vô thời hạn cho đến khi node được restart thành công và xử lý request
• Nếu một server bị crash sau khi xử lý xong request nhưng chưa kịp phản hồi lại cho leader thì sau khi restart thành công, node đó sẽ nhận lại được đúng request RPC trước khi bị crash.

Timing

Một trong những yêu cầu Raft đặt ra về tính an toàn là không phụ thuộc vào thời gian: Hệ thống trả về kết quả đúng bất kể một sự kiện xảy ra nhanh hay chậm. Trong khi đó, tính availability của hệ thống lại phụ thuộc vào thời gian xử lý. Nếu message trao đổi thông tin cần nhiều thời gian hơn bình thường do server bị crash thì candidate không đủ thời gian để thắng một cuộc bầu chọn leader. Vì vậy, Raft đề xuất duy trì leader trong một khoảng thời gian thỏa mãn điều kiện: Broadcast time << Election timeout << MTBF

• Broadcast time là thời gian trung bình của một server cần để gửi request đến các node còn lại trong hệ thống và nhận được response
• Election timeout là thời gian timeout của một cuộc bầu chọn
• MTBF: là thời gian trung bình giữa các lần gặp sự cố của một node

Raft đề xuất broadcast time nên nhỏ hơn thời gian timeout giữa 2 lần bầu chọn để leader có thể gửi heartbeat đến follower khi bắt đầu bầu chọn. Thời gian timeout giữa 2 lần bầu chọn là tham số được chọn ngẫu nhiên, nhỏ hơn rất nhiều so với MTBF time để hệ thống được hoạt động ổn định.

Broadcast time và MTBF time là các thuộc tính cơ bản của hệ thống, thời gian timeout bầu chọn là tham số được điều chỉnh. Broadcast time thường được cài đặt trong khoảng 0.5ms -> 20ms, thời gian timeout chọn ngẫu nhiên trong khoảng 10->500ms, còn thời gian MTBF thường khoảng vài tháng.

2.2.4. Cập nhật cấu hình hệ thống

Khi thực hiện thay đổi cấu hình hệ thống, trong trường hợp cấu hình được thay đổi bằng cách thủ công (off hệ thống -> cập nhật cấu hình -> khởi động lại), rủi ro lớn có thể xảy ra do lỗi của hệ thống hoặc người thực hiện. Do đó, Raft chọn cách cài đặt tự động thay thế cấu hình hệ thống. Một cụm các server cài đặt thuật toán Raft khi cập nhật được chia làm 2 phần, quá trình cập nhật diễn ra trên từng phần. Đối với mỗi phần, quá trình này được chia làm 2 bước:

• Disable cấu hình cũ, không nhận xử lý request từ client
• Enable cấu hình mới

Trong quá trình cập nhật sẽ xảy ra tình trạng tồn tại song song 2 cấu hình trên cùng một node. Trường hợp này được gọi là đồng thuận chung

Đồng thuận chung cho phép các node khác nhau chuyển đổi cấu hình trong các khoảng thời gian khác nhau mà không cần đảm bảo các yêu cầu Safety của Raft, hệ thống có thể tiếp tục xử lý request từ client trong quá trình cập nhật cấu hình.

Quá tình chuyển đổi cấu hình của Raft:

• Khi leader nhận request thay đổi cấu hình từ cấu hình cũ Cold sang cấu hình mới Cnew, leader lưu trữ kết hợp cả cấu hình cũ và mới gọi là đồng thuận chung Cold, new
• Khi một node cập nhật cấu hình mới, thì cấu hình mới sẽ được sử dụng để xử lý các yêu cầu sau này (Raft yêu cầu các node luôn sử dụng cấu hình mới nhất)
• Leader sẽ sử dụng cấu hình đồng thuận chung Cold, new

Nếu leader gặp sự cố, leader mới có thể chọn một trong 2 cấu hình Cold hoặc Cold, new, phụ thuộc vào candidate được chọn làm leader tiếp theo đã nhận được cấu hình Cold, new hay chưa. Trong bất kì trường hợp nào, cấu hình mới Cnew không thể được sử dụng để đưa ra quyết định trong quá trình chuyển đổi

• Trong trường hợp Cold, new được commit, cả 2 cấu hình Cold và Cnew đều không thể tự đưa ra quyết định. Dựa vào thuộc tính Leader Completeness Property, Raft đảm bảo chỉ server đang có cấu hình Cold, new mới có thể được chọn làm leader tiếp theo
• Cấu hình mới sẽ được sử dụng ngay khi một node được cập nhật từ leader. Khi cấu hình mới được commit vào log, cấu hình cũ sẽ bị loại bỏ. Các node không sử dụng cấu hình mới sẽ bị shutdown. Dựa vào cách cập nhật cấu hình này, ta thấy không có khoảng thời gian nào xảy ra trường hợp cấu hình cũ và mới có thể đơn phương đưa ra quyết định. Điều này đảm bảo cho hệ thống hoạt động ổn định, tránh xung đột.

Một số vấn đề liên quan đến việc thay đổi cấu hình trong hệ thống cài đặt thuật toán đồng thuận:

• Các node mới có thể không lưu log entry nào. Nhưng node này được thêm vào hệ thống có thể mất một khoảng thời gian để update log đến term hiện tại. Trong khoảng thời gian update, không thể thêm các entry mới vào log của mỗi node. Để xử lý vấn đề này, Raft thiết kế thêm một bước trước khi cập nhật cấu hình, theo đó, node mới khi được thêm vào hệ thống sẽ không được vote trong cuộc bầu chọn (node chưa được xem là một thành viên chính thức trong hệ thống) nhưng vẫn được sao lưu log từ leader. Khi các node mới này theo kịp term hiện tại của hệ thống thì quá trình cập nhật cấu hình sẽ tiếp tục.
• Leader có thể không chứa config mới. Khi đó, leader sẽ bị gỡ bỏ và chuyển trạng thái sang follower cho đến khi nhận được cấu hình mới (leader vẫn quản lí các node trong hệ thống, ngoại trừ chính nó, các entry được sao lưu đến các node không tính leader). Leader sẽ tiếp tục thay đổi cấu hình khi nhận được cấu hình mới.
• Đối với các node bị xóa có thể làm gián đoạn hoạt động của cụm (các node bị xóa không được cập nhật cấu hình mới). Các node này sẽ không nhận được heartbeat từ leader, vì thế các node này xảy ra timeout và bắt đầu term bầu chọn mới. Node sẽ gửi request RequestVote để bắt đầu một term mới, leader sẽ chuyển trạng thái về follower. Tuy nhiên khi leader mới được chọn, các node đã bị xóa sẽ tiếp tục xảy ra timeout và quá trình bầu chọn lại sẽ lặp lại liên tục, hệ thống khi đó sẽ bị lỗi.

3. Zookeeper Atomic Broadcast – ZAB

Zookeeper Atomic Broadcast – ZAB là một trong những thuật toán đồng thuận phổ biến được sử dụng bởi công cụ lưu trữ key-value Apache Zookeeper. Mục đích ZAB được sử dụng để giải quyết vấn đề đảm bảo thứ tự các sự kiện, duy trì tính nhất quán giữa các bản sao.

Một node trong cluster cài đặt ZAB có thể đảm nhận một trong hai trạng thái: leader và follower. Leader có nhiệm vụ thực hiện các bước của thuật toán ZAB, broadcast message đến các followers và quản li thứ tự các event. Để đảm bảo các thao tác đọc ghi luôn lấy được giá trị mới nhất, client chỉ connect đến một trong các node của hệ thống. Nếu một node trở thành leader, node đó sẽ chịu trách nhiệm xử lý các request, nếu node không phải là leader thì request nhận được sẽ forward sang cho leader.

Để đảm bảo có duy nhất một leader trong cluster, ZAB cũng chia timeline thành các epoch, đánh số thứ tự mỗi epoch tăng dần. Trong suốt một epoch, chỉ có duy nhất một leader được chọn. Leader được chọn là node có xác suất cao nhất thông qua một thuật toán bầu chọn. Khi một leader tiềm năng được chọn, node đó sẽ thực hiện một giao thức gồm 3 phrase:

• Discovery

Leader tiềm năng lấy thông tin mới nhất từ các node khác, đề xuất epoch mới có thứ tự lớn hơn thứ tự của epoch hiện tại trên bất kì node nào.

• Synchronization

Bước này được thiết kế để khôi phục dữ liệu từ các leader trước gặp sự cố và tăng tốc độ cho các node follower bị trễ. Leader tiềm năng gửi một message đến các follow tự thông báo nó là leader của epoch mới và nhận tín hiệu từ follower. Khi leader tiềm năng đó nhận được tín hiệu, thì trạng thái leader chính thức được thiết lập. Sau bước này, các follower sẽ không nhận tín hiệu thông báo trở thành leader từ bất kì node nào nữa. Trong quá trình đồng bộ, leader mới đảm bảo các follower có cùng lịch sử dựa và cập nhật thông tin các epoch trước.

• Broadcast

Sau khi các follower được đồng bộ hóa, quá trình lan truyền message bắt đầu. Ở bước này, leader nhận message của client, sắp xếp thứ tự và lan truyền đến các follow. Quá trình này diễn ra theo thứ tự: gửi đề xuất đến các follower -> chờ nhận được đủ số quorum follower phản hồi lại (quá bán) -> commit message. Quá trình này tương tự với giao thức two-phrase commit. Bước lan truyền thông tin tiếp tục được thực hiện cho đến khi cluster gặp sự cố như leader bị crash, message bị delay, network bị phân mảnh.

Tính an toàn của giao thức ZAB được đảm bảo nếu các follower đảm bảo chỉ chấp nhận các proposal từ leader trong epoch hiện tại. Có nhiều hơn 1 tiến trình bầu chọn có thể diễn ra tại epoch nhưng chỉ một tiến trình có thể thắng và chọn leader mới.

Cả leader và follower dựa vào heartbeat để quyết định một tiến trình còn sống hay không. Nếu leader không nhận được heartbeat từ đủ quorum số follower, node đó sẽ từ bỏ trạng thái leader và bắt đầu một tiến trình bầu chọn mới. Tương tự, khi một trong các follower phán đoán leader bị crash thì cluster sẽ bắt đầu tiến trình bầu chọn mới.

Message được sắp xếp theo thứ tự, và leader sẽ không gửi message tiếp theo cho đến khi message trước đó được commit. Thậm chí một message được nhận bởi follower nhiều hơn một lần, miễn là đảm bảo thứ tự của các message. ZAB có khả năng xử lý đồng bộ khi có nhiều trạng thái thay đổi từ client vì chỉ có một leader nhận request và xử lý message.

Các message được sắp xếp theo thứ tự giúp ZAB nâng cao khả năng khôi phục dữ liệu. Trong suốt quá trình đồng bộ, các follower phản hồi mới đề xuất commit mới nhất từ leader, dựa vào điểm này, leader chỉ cần chọn node có đề xuất mới nhất để khôi phục khi có sự cố.

Ưu điểm của ZAB – tính hiệu quả:

• Quá trình lan truyền message chỉ cần 2 bước
• Leader khi gặp sự cố có thể khôi phục dữ liệu dựa vào node có trạng thái mới nhất
• Thời gian sống của leader dài, giảm việc áp dụng thuật toán đồng thuận để xử lý đồng bộ và chọn leader mới