1. Giới thiệu

Các thuật toán đồng thuận cho phép một tập hợp các máy tính hoạt động như một nhóm mạch lạc có thể tiếp tục hoạt động dù trong nhóm có những máy tính bị ngắt kết nối. Do đó, họ thuật toán đồng thuận luôn đóng một vai trò quan trọng trong việc xây dựng các hệ thống máy tính quy mô lớn đáng tin cậy.

Trong đó Raft là một thuật toán đồng thuận hoạt động tương đối hiệu quả, có những ưu điểm đáng kể so với các thuật toán đồng thuận khác:

• Stronger Leader (lãnh đạo mạnh hơn): Raft sử dụng hình thức lãnh đạo mạnh mẽ hơn các thuật toán đồng thuận khác. Ví dụ, các log entries chỉ broadcast từ leader đến các máy khác. Điều này giúp đơn giản hóa quản lý việc nhân rộng log entries và giúp Raft dễ hiểu hơn.
• Leader Election (bầu cử lãnh đạo): Raft sử dụng bộ tính giờ ngẫu nhiên để bầu nhà lãnh đạo. Điều này chỉ là thêm một thay đổi nhỏ vào heartbeats so với các thuật toán đồng thuận khác, nhưng nó lại giúp giải quyết xung đột một cách đơn giản và nhanh chóng.
• Membership changes (thay đổi vai trò): nghĩa là thay đổi vai trò của máy tính từ follower thành leader và ngược lại, cơ chế mà Raft sử cho việc thay đổi này là sử dụng một phương pháp đồng thuận chung mới (joint consensus), trong đó hai vai trò khác nhau (leader và follower) overlap lên nhau trong quá trình chuyển đổi của máy tính. Điều này cho phép cụm vẫn tiếp tục hoạt động bình thường trong khi các máy tính trong cụm đang trong quá trinh thay đổi vai trò.

2. Replicated state machines

Các thuật toán đồng thuận thường phát sinh trong bối cảnh các state machines cần được replicated. Theo cách tiếp cận này, các state machines trên các máy tính sẽ tính toán các bản sao giống hệt nhau của cùng một state và có thể tiếp tục hoạt động ngay cả khi có một số máy tính bị hỏng. Replicated state machines thường được sử dụng để giải quyết một loạt các vấn đề về khả năng chịu lỗi trong hệ thống phân tán.

Hinh 1: Kiến trúc của Replicated stated machines. Thuật toán đồng thuận quản lý một bản replicated log có chứa các lệnh cập nhật state machine từ các clients. Các state machines xử lý các chuỗi lệnh giống hệt nhau từ các logs, do đó chúng tạo ra các đầu ra giống nhau.

Các replicated state machines thường được triển khai bằng cách sử dụng một replicate log, như trong Hình 1. Mỗi máy lưu trữ một log chứa một chuỗi loạt các lệnh mà state machine của nó sẽ thực hiện theo thứ tự. Các log giũa các máy chứa các lệnh giống nhau theo cùng một thứ tự, vì vậy các state machines sẽ xử lý cùng một chuỗi lệnh, do đó các máy tính cũng cùng một state và cùng một chuỗi đầu ra.

Giữ replicated log sao cho chúng được nhất quán là công việc của thuật toán đồng thuận. Consensus module trên một máy tính nhận lệnh từ client và thêm chúng vào log của nó. Nó giao tiếp với các consensus module trên các máy tính khác để đảm bảo rằng các log trên các máy tính đều chứa các yêu cầu giống nhau theo cùng một thứ tự, ngay cả khi một số máy tính bị lỗi. Sau đó các replicated state machine trên các máy tính sẽ xử lý chúng theo thứ tự có trong log và trả về kết quả cho client. Do đó, các máy tính dường như tạo thành một state machine duy nhất, có độ tin cậy cao.

Các thuật toán đồng thuận cho một hệ thống thực tế thường có các thuộc tính sau:

• Chúng phải đảm bảo an toàn (không bao giờ trả lại kết quả không chính xác) trong mọi điều kiện non-Byzantine, bao gồm các trường hợp như độ trễ mạng, mất gói tin, sao chép gói và sắp xếp lại.
• Chúng phải có sẵn đầy đủ chức năng sao cho các máy tính đang hoạt động có thể hoạt động và giao tiếp với nhau và với client. Do đó, một cụm năm máy tính vẫn có thể hoạt động nếu bất ngờ hai máy tính nào đó bị tắt, sau đó 2 máy đó được bật lại, phục hồi từ trạng thái đã được lưu trước đó và tham gia lại cụm.
• Chúng phải không phụ thuộc vào thời gian để đảm bảo tính nhất quán của log.
• Trong trường hợp phổ biến, một lệnh có thể hoàn thành ngay khi phần lớn các máy tính đã trả lời một vòng các lệnh gọi thủ tục từ xa; một số ít các máy tính chậm sẽ không ảnh hưởng đến hiệu năng của toàn hệ thống.

3. Thuật toán đồng thuận Raft

Raft là một thuật toán để quản lý một replicated log được mô tả trong Phần 2.
Raft thực hiện sự đồng thuận bằng cách trước tiên bầu một leader, sau đó giao cho leader hoàn toàn chịu trách nhiệm quản lý replicated log. Leader chấp nhận các log entries từ client, sao chép chúng cho các máy tính khác và thông báo cho các máy tính đó khi nào an toàn để apply các log entries cho các state machine của chúng. Việc có một leader sẽ đơn giản hóa việc quản lý replicated log. Ví dụ: leader có thể quyết định nơi đặt các entries mới trong log mà không cần tham khảo các máy tính khác và luồng dữ liệu cũng được gửi theo cách đơn giản từ leader đến các máy tính khác. Một leader có thể fail hoặc bị ngắt kết nối với các tính khác, trong trường hợp đó, một leader mới sẽ được bầu.

Theo cách tiếp cận khía cạnh leader, Raft phân tách vấn đề đồng thuận thành ba bài toán con tương đối độc lập:

• Leader election (bầu chọn leader): một leader mới phải được bầu khi leader hiện tại bị fail
• Log replication (sao chép log): leader phải chấp nhận các log entries từ client và sao chép chúng trên toàn cụm, buộc các máy tính khác phải đồng ý với các entries đó vào log của chúng.
• Safety: thuộc tính an toàn chính của Raft là thuộc tính an toàn của state machine, nếu bất kỳ máy tính nào đã apply một log entry nào đó cho state machine của nó, thì không máy tính nào khác có thể apply một lệnh khác cho cùng log entry đó.

3.1 Tóm tắt các khái niệm trong Raft

State

Nhìn vào hình thì ta có thể tháy có 2 loại state trong Raft đó là :

• Persistent state: State này sẽ được update trên stable storage trước khi máy tính đó phản hồi cho RPCs
• Volatile state
  Trong đó, có những thuộc tính chung cho tất cả máy tính, có những thuộc tính riêng mà chỉ leader mới có.

Tóm tắt lại thì máy tính không phải leader và máy tính leader sẽ có những thuộc tính sau:

Trong đó :

• currentTerm: nhiệm kỳ mới nhất, khi bắt đầu hệ thống Raft sẽ được khởi tạo là 0, bước tăng 1
• votedFor: Id của máy tính nào đó mà đã được máy này vote cho ở nhiệm kỳ hiện tại ( currentTerm)
• log[]: log entries; mỗi entry chứa lệnh cho state machine và term mà leader nhận được entry đó (đầu tiên là 1)
• commitIndex: chỉ mục của log entry cao nhất đã được committed (khởi tạo từ 0, bước tăng 1)
• lastApplied: chỉ mục của log entry cao nhất đã được apply vào state machine (khởi tạo từ 0, bước tăng 1)
• nextIndex[]: đối với mỗi máy tính, chỉ mục của log entry tiếp theo sẽ được leader gửi đến máy tính đó (khởi tạo bằng log index của leader + 1 )
• matchIndex[]: đối với mỗi máy tính, chỉ mục của log entry cao nhất đã được replicated trên máy tính đó (được khởi là 0, bước tăng 1)

AppendEntries RPC*

Được leader invoke để replatecate các log entries. Trong đó có các tham số :

• term: term của leader
• leaderId: để các máy tính khác có thể chuyển cho client
• prevLogIndex: chỉ mục của log entry liền trước
• prevLogTerm: term của entry của prevLogIndex
• antries: các log entries cần được các máy tính lưu vào, (là rỗng nếu đó là heartbeat; hoặc có thể nhiều hơn 1 để tăng hiếu suất)

Sau khi leader gửi các tham số đấy đi đến các máy tính khác, kết quả trả về sẽ có 2 thuộc tính :

• term: currentTerm, để leader update currentTerm của chính nó
• success: true nếu máy tính đó có chứa entry được matching với prevLogIndex và prevLogTerm

Phía các máy tính nhận được sẽ thực hiện :

• 1. Trả về false nếu term nhận được < currentTerm của nó
• 2. Trả về false nếu log của nó không chưa entry tại index = prevLogIndex mà nó nhận được có term match với prevLogTerm
• Nếu nó có một entry conflict với một entry mới (cùng index nhưng khác term), nó sẽ xóa entry đó có và tất cả các các entry theo sau.
• Append bất kỳ entry nào mà chưa có trong log của nó
• Nếu leaderCommit mà nó nhận được > commitIndex của nó, nó sẽ đặt commitIndex = min (leaderCommit, chỉ mục của entry mới nhất)

RequestVote RPC

Được gọi bởi các máy tính đang muốn làm leader (candidates – ứng cử viên) để thu thập phiếu bầu. Gồm các tham số :

• term: term của candidate
• candidateId: Id của máy tính thực hiện
• lastLogIndex: index của log entry mới nhất của candidate
• lastLogTerm: term của log entry mới nhất của candidate

Kết quả trả về sẽ có 2 thuộc tính :

• term: currentTerm, để candidate update cho chính nó
• voteGranted: true nếu candidate nhận được 1 vote

Phía các máy tính nhận được request sẽ thực hiện:

• 1. Trả về false nếu term nhận được < currentTerm của máy đó
• 2. Nếu votedFor của máy tính đó đang là null hoặc bằng với candidateId, và log của candidate ít nhất là up-to-date với log của máy tính đó, tiến hành vote.

Rules for servers

Tất cả máy tính đều có:

• Nếu commitIndex > lasteApplied: tẳng lasteApplied, apply log[lastApplied] vào state machine của nó
• Nếu RPC request hoặc response có chứa term T > currentTerm của nó: đặt currentTerm = T, trở thành follower.

Ở các máy tính đang là follower:

• Phản hồi cho các RPC đến từ các candidates và leaders
• Nếu election timeout elapses mà không nhận được AppendEntries
  RPC từ leader hiện tại hoặc đang vote cho candidate: chuyển thành candidate

  Ở các máy đang là candidate:

• Khi chuyển thành candidate, bắt đầu election:
  • Tăng currentTerm
  • Vote cho chính nó
  • Reset election timer
  • Gửi RequestVote RPC cho tất các máy tính khác
• Nếu nhận được votes từ đa số các tính, trở thành leader
• Nếu nhận AppendEntries RPC từ leader mới, chuyển thành follower
• Nếu election timout elapses: bắt đầu cuộc bầu cử mới

  Ở leaders:

• Khi bầu cử: gửi các RPC AppendEntries empty (heartbeat) đến mỗi máy tính; lặp lại liên tục để ngăn election timeout.
• Nếu nhận được lệnh từ client, append entry vào log của nó, phản hồi sau khi entry đã được applied vào state machine.
• Nếu index của log mới nhất >= nextIndex của một follower nào đó, gửi AppendEntries RPC với log entries bắt đầu đầu tại nextIndex:
  • Nếu thành công: cập nhật nextIndex và matchIndex tương ứng với follower đó
  • Nếu AppendEntries do log không nhất quán, giảm nextIndex và thực hiện lại
• Nếu tồn tại một N mà N > commitIndex, đa số matchIndex[i] >= N và log[N].term == currentTerm: đặt commitIndex = N.

3.2 Các đảm bảo trong Raft

• Election Safety: Nhiều nhất một leadet được bầu trong một term nhất định
• Leader Append-Only: leader không bao giờ ghi đè hoặc xóa entries trong log của nó, nó chị append các entries mới.
• Log Match: nếu hai log chứa một entry có cùng index và term, thì các log đó giống có các entries từ đầu đến index giống hết nhau
• Leader Completeness: nếu một log entry được commit trong một term nhất định thì entry đó sẽ có trong tất cả các logs của các leaders trong các term về sau.
• State Machine Safety: nếu một máy tính đã applied một log entry tại một index nhất định vào state machine của nó, sẽ không có máy tính khác apply một entry khác cho cùng index đó.

Tài liệu tham khảo

https://raft.github.io/raft.pdf