Raft算法

Raft算法是一种用于管理复制状态机的共识算法，旨在提供与Paxos算法相同的功能，但通过更清晰的逻辑结构和更易理解的实现方式降低学习门槛。Raft通过分解问题为领导者选举、日志复制和安全性三个子问题，成为分布式系统中广泛采用的共识协议之一。

核心概念[编辑 | 编辑源代码]

角色划分[编辑 | 编辑源代码]

Raft集群中的节点分为三种角色：

Leader（领导者）：处理所有客户端请求，管理日志复制。
Follower（跟随者）：被动响应Leader的指令。
Candidate（候选者）：选举过程中临时存在的角色。

任期（Term）[编辑 | 编辑源代码]

每个任期是一个连续编号的时间段，用于标识Leader的合法性。Raft保证每个任期最多只有一个有效的Leader。

$T e r m = T_{1} \to T_{2} \to \dots \to T_{n}$

算法细节[编辑 | 编辑源代码]

领导者选举[编辑 | 编辑源代码]

1. Follower在选举超时（通常150-300ms）后成为Candidate 2. Candidate发起投票请求（RequestVote RPC） 3. 获得多数节点投票后成为Leader 4. Leader定期发送心跳维持权威

日志复制[编辑 | 编辑源代码]

Leader接收客户端请求后： 1. 追加日志到本地 2. 通过AppendEntries RPC同步日志 3. 多数节点确认后提交日志 4. 通知所有节点应用日志

安全性约束[编辑 | 编辑源代码]

选举限制：只有包含全部已提交日志的节点才能成为Leader
提交规则：Leader只能提交当前任期的日志

代码示例[编辑 | 编辑源代码]

以下是Raft领导者选举的简化Python实现：

class RaftNode:
    def __init__(self, node_id):
        self.node_id = node_id
        self.state = "FOLLOWER"
        self.current_term = 0
        self.voted_for = None

    def start_election(self):
        self.state = "CANDIDATE"
        self.current_term += 1
        self.voted_for = self.node_id
        votes_received = 1
        
        # 向其他节点请求投票
        for peer in self.peers:
            response = peer.request_vote(
                term=self.current_term,
                candidate_id=self.node_id,
                last_log_index=len(self.log),
                last_log_term=self.log[-1].term if self.log else 0
            )
            if response.vote_granted:
                votes_received += 1
                if votes_received > len(self.peers) // 2:
                    self.become_leader()
                    break

    def become_leader(self):
        self.state = "LEADER"
        # 开始定期发送心跳
        self.start_heartbeat()