Skip to content

05-paxos.md

Latest commit

 

History

History
289 lines (213 loc) · 6.18 KB

05-paxos.md

File metadata and controls

289 lines (213 loc) · 6.18 KB
Raw

5.5 Paxos算法

📍 导航：返回目录 | 上一节：分布式事务 | 下一节：Raft

问题背景

分布式共识问题：多个节点如何对某个值达成一致？

应用场景：

  • 选主
  • 配置管理
  • 分布式锁

Paxos核心思想

三种角色

  1. Proposer（提议者）：提出提案
  2. Acceptor（接受者）：投票决定是否接受提案
  3. Learner（学习者）：学习已被选定的值

两阶段

阶段1：Prepare（准备）

  • Proposer选择提案编号n，向多数Acceptor发送Prepare(n)
  • Acceptor收到Prepare(n)：
    • 如果n大于已见过的编号，承诺不再接受<n的提案，返回已接受的最大编号提案
    • 否则拒绝

阶段2：Accept（接受）

  • Proposer收到多数Acceptor的响应后，发送Accept(n, value)
  • Acceptor收到Accept(n, value)：
    • 如果没有承诺过更大编号，则接受
    • 否则拒绝

算法流程图

Proposer                Acceptor1   Acceptor2   Acceptor3
   |                        |           |           |
   |---Prepare(n=1)-------->|           |           |
   |---Prepare(n=1)-------------------->|           |
   |---Prepare(n=1)------------------------------>|
   |                        |           |           |
   |<---Promise(n=1)--------|           |           |
   |<---Promise(n=1)---------------------|           |
   |<---Promise(n=1)-------------------------------|
   |                        |           |           |
   |---Accept(n=1,v=X)----->|           |           |
   |---Accept(n=1,v=X)------------------>|           |
   |---Accept(n=1,v=X)----------------------------->|
   |                        |           |           |
   |<---Accepted------------|           |           |
   |<---Accepted-------------------------|           |
   |<---Accepted------------------------------------|

简化实现（Go）

package main

import (
    "fmt"
    "sync"
)

type Proposal struct {
    Number int
    Value  string
}

type Acceptor struct {
    promisedNumber int
    acceptedProposal *Proposal
    mu sync.Mutex
}

func (a *Acceptor) Prepare(n int) (bool, *Proposal) {
    a.mu.Lock()
    defer a.mu.Unlock()
    
    if n > a.promisedNumber {
        a.promisedNumber = n
        return true, a.acceptedProposal
    }
    return false, nil
}

func (a *Acceptor) Accept(proposal Proposal) bool {
    a.mu.Lock()
    defer a.mu.Unlock()
    
    if proposal.Number >= a.promisedNumber {
        a.promisedNumber = proposal.Number
        a.acceptedProposal = &proposal
        return true
    }
    return false
}

type Proposer struct {
    id         int
    proposalNum int
    acceptors  []*Acceptor
}

func (p *Proposer) Propose(value string) bool {
    p.proposalNum++
    n := p.proposalNum
    
    // 阶段1：Prepare
    promiseCount := 0
    var maxAccepted *Proposal
    
    for _, acceptor := range p.acceptors {
        ok, accepted := acceptor.Prepare(n)
        if ok {
            promiseCount++
            if accepted != nil && (maxAccepted == nil || accepted.Number > maxAccepted.Number) {
                maxAccepted = accepted
            }
        }
    }
    
    // 未获得多数派支持
    if promiseCount <= len(p.acceptors)/2 {
        return false
    }
    
    // 如果有已接受的值，使用该值
    if maxAccepted != nil {
        value = maxAccepted.Value
    }
    
    // 阶段2：Accept
    proposal := Proposal{Number: n, Value: value}
    acceptCount := 0
    
    for _, acceptor := range p.acceptors {
        if acceptor.Accept(proposal) {
            acceptCount++
        }
    }
    
    // 获得多数派接受
    return acceptCount > len(p.acceptors)/2
}

func main() {
    // 创建3个Acceptor
    acceptors := []*Acceptor{
        {},
        {},
        {},
    }
    
    // 创建Proposer
    proposer := &Proposer{
        id:        1,
        acceptors: acceptors,
    }
    
    // 提议值
    if proposer.Propose("value1") {
        fmt.Println("提案通过：value1")
    }
}

Multi-Paxos

问题

Basic Paxos每次只能对一个值达成共识，效率低。

优化

  1. 选举Leader：只有Leader可以提议
  2. 省略Prepare：Leader任期内直接Accept
  3. 日志复制：对一系列值达成共识
type MultiPaxos struct {
    leader    *Proposer
    log       []string
    commitIdx int
}

func (mp *MultiPaxos) Append(value string) bool {
    if mp.leader == nil {
        mp.electLeader()
    }
    
    // Leader直接提议（跳过Prepare）
    proposal := Proposal{
        Number: mp.leader.proposalNum,
        Value:  value,
    }
    
    acceptCount := 0
    for _, acceptor := range mp.leader.acceptors {
        if acceptor.Accept(proposal) {
            acceptCount++
        }
    }
    
    if acceptCount > len(mp.leader.acceptors)/2 {
        mp.log = append(mp.log, value)
        mp.commitIdx++
        return true
    }
    
    return false
}

Paxos的挑战

1. 活锁

两个Proposer交替提高提案编号，导致无法达成共识。

解决：随机退避

2. 难以理解

算法晦涩难懂。

解决：使用Raft（易懂的替代方案）

3. 工程实现复杂

解决：使用成熟的实现（ZooKeeper的ZAB协议）

应用场景

Google Chubby

  • 基于Paxos的分布式锁服务
  • Google内部广泛使用

Apache ZooKeeper

  • ZAB协议（Paxos的变种）
  • 配置管理、服务发现

本章小结

关键要点：

  • ✅ Paxos解决分布式共识问题
  • ✅ 两阶段：Prepare + Accept
  • ✅ 需要多数派支持
  • ✅ Multi-Paxos优化性能

扩展阅读

💡 思考题：

  1. 为什么需要两阶段？
  2. 如何避免活锁？
  3. Paxos和2PC的区别？

⏮️ 上一节：分布式事务 | ⏭️ 下一节：Raft