Skip to content

Latest commit

 

History

History
136 lines (112 loc) · 6.48 KB

raft算法.md

File metadata and controls

136 lines (112 loc) · 6.48 KB

Raft 是一种分布式共识算法，主要用于管理一组服务器之间的一致性状态。它被广泛应用于分布式系统中，如分布式数据库、分布式文件系统等，确保多个副本之间数据的一致性。Raft 算法通过领导者选举、日志复制、容错机制等手段，保证了在网络分区、节点宕机等情况下，仍能维持系统的一致性和可用性。

Raft 的基本概念

Raft 的目标是解决分布式系统中状态一致性的问题，和 Paxos 类似，但它的设计强调了简洁性和易于理解。Raft 算法将集群中的服务器分为三种角色：

  1. Leader（领导者）：处理客户端的请求，并负责将日志条目复制到其他服务器。
  2. Follower（跟随者）：被动地接收 Leader 发送的日志条目，并保存它们的副本。
  3. Candidate（候选者）：当 Follower 超时没有收到 Leader 的心跳信号时，它会进入 Candidate 状态，发起领导者选举。

Raft 的核心机制

Raft 分为三个主要过程：领导者选举、日志复制和安全性保证。

1. 领导者选举

Raft 保证集群中的某一时刻只有一个 Leader 负责处理客户端的请求，领导者是通过选举机制产生的。

  • 初始状态：所有服务器启动时都是 Follower 状态，并监听来自 Leader 的心跳。
  • 超时：如果 Follower 在一定时间内没有收到 Leader 的心跳，它会转换为 Candidate，并向集群中的其他节点请求选票。
  • 选举过程：
    • Candidate 会向其他节点发送选举请求（RequestVote）。
    • 其他节点会根据自己的日志判断是否支持该 Candidate，并投票给其认为有资格成为 Leader 的节点。
    • 当某个 Candidate 获得大多数节点的选票时，它就成为新的 Leader，并开始发送心跳信号。

2. 日志复制

一旦选举出了 Leader，所有客户端请求都会由 Leader 处理。Leader 负责将日志条目复制到其他 Follower 上。

  • 日志条目：每个客户端的请求会被 Leader 转换为日志条目，并追加到它的日志中。
  • 复制过程：
    • Leader 会将日志条目发送给所有 Follower，并等待多数节点（quorum）的确认。
    • 一旦大多数节点确认该日志条目被复制，Leader 会将日志提交并执行对应的操作。
  • 日志一致性：Raft 保证日志条目在集群中的顺序一致，所有节点都会按照相同的顺序执行相同的日志条目。

3. 安全性保证

Raft 通过严格的规则保证系统在网络分区、节点宕机时仍能保持数据的一致性和安全性。

  • 任期编号（Term）：Raft 使用递增的任期编号来区分不同的领导者任期，每次选举新 Leader 时，任期编号都会增加。每个服务器都会记录当前的任期编号。
  • 领导者合法性：只有日志最完整的节点才能被选为 Leader。这一规则保证了新的 Leader 拥有最完整的日志，不会导致数据回退。
  • 提交日志条目：Leader 只有在日志条目被大多数节点复制后，才能提交该条目并将其应用到状态机中。

Raft 算法流程

  1. Leader 选举：

    • 集群中初始时所有节点为 Follower。
    • 如果 Follower 没有在指定的时间内收到 Leader 的心跳信号，它将成为 Candidate 并发起选举。
    • 节点向其他所有节点请求选票，如果某个节点得到超过半数的选票，它将成为 Leader。
    • 新的 Leader 开始向集群发送心跳，确保其他节点知道自己是 Leader。

  2. 日志复制：

    • 客户端请求发送到 Leader，Leader 生成日志条目并将其复制到 Follower。
    • 当大多数 Follower 确认收到日志条目后，Leader 提交该日志并将结果返回给客户端。
    • Follower 同步 Leader 的日志，保持集群中的日志一致。

  3. 日志一致性：

    • 如果某个 Follower 崩溃或暂时失联，当它重新加入集群时，Leader 会通过比较日志找到其缺失的日志条目，并同步缺失的部分。

Raft 的容错性

Raft 保证了在最多有一半节点出现故障的情况下，系统仍能正常运作。例如，假设有 5 个节点的集群，最多可以容忍 2 个节点故障，集群中的剩余 3 个节点仍能组成多数派，选出新的 Leader 并继续提供服务。

Raft 的优势

  • 易于理解：与 Paxos 相比，Raft 的逻辑更清晰，步骤更容易理解。
  • 强一致性：Raft 保证所有已提交的日志条目都会被所有节点一致执行。
  • 高容错性：Raft 能容忍最多半数的节点出现故障，同时保持系统的可用性。

Golang 实现 Raft 的示例

type Raft struct {
    mu        sync.Mutex
    peers     []*rpc.Client
    me        int // 当前节点的 ID
    term      int // 当前任期
    isLeader  bool
    log       []LogEntry
    commitIdx int
}

type LogEntry struct {
    Term    int
    Command interface{}
}

// 心跳 RPC
type HeartbeatArgs struct {
    Term int
    LeaderId int
}

type HeartbeatReply struct {
    Term int
}

// 处理心跳请求
func (rf *Raft) Heartbeat(args *HeartbeatArgs, reply *HeartbeatReply) {
    rf.mu.Lock()
    defer rf.mu.Unlock()

    if args.Term >= rf.term {
        rf.term = args.Term
        rf.isLeader = false
    }
}

// 向其他节点发送心跳
func (rf *Raft) sendHeartbeat() {
    for _, peer := range rf.peers {
        go func(peer *rpc.Client) {
            args := &HeartbeatArgs{Term: rf.term, LeaderId: rf.me}
            reply := &HeartbeatReply{}
            peer.Call("Raft.Heartbeat", args, reply)
        }(peer)
    }
}

// 发起选举
func (rf *Raft) startElection() {
    rf.mu.Lock()
    defer rf.mu.Unlock()
    
    rf.term++
    rf.isLeader = false
    voteCount := 1 // 自己的选票

    for _, peer := range rf.peers {
        go func(peer *rpc.Client) {
            args := &RequestVoteArgs{Term: rf.term, CandidateId: rf.me}
            reply := &RequestVoteReply{}
            if peer.Call("Raft.RequestVote", args, reply) && reply.VoteGranted {
                voteCount++
                if voteCount > len(rf.peers)/2 {
                    rf.isLeader = true
                    rf.sendHeartbeat()
                }
            }
        }(peer)
    }
}

总结

Raft 是一种简单而有效的分布式共识算法，通过领导者选举和日志复制机制实现分布式系统中的一致性和高可用性。它相对其他一致性算法更易于理解，因此被广泛应用于分布式系统中。