Golang 實現 Paxos 分佈式共識算法

 1type proposer struct {
 2    // server id
 3    id int
 4    // the largest round number the server has seen
 5    round int
 6    // proposal number = (round number, serverID)
 7    number int
 8    // proposal value
 9    value     string
10    acceptors map[int]bool
11    net       network
12}
13
14

 1type acceptor struct {
 2    // server id
 3    id int
 4    // the number of the proposal this server will accept, or 0 if it has never received a Prepare request
 5    promiseNumber int
 6    // the number of the last proposal the server has accepted, or 0 if it never accepted any.
 7    acceptedNumber int
 8    // the value from the most recent proposal the server has accepted, or null if it has never accepted a proposal
 9    acceptedValue string
10
11    learners []int
12    net      network
13}
14
15

 1// MsgType represents the type of a paxos phase.
 2type MsgType uint8
 3
 4const (
 5    Prepare MsgType = iota
 6    Promise
 7    Propose
 8    Accept
 9)
10
11type message struct {
12    tp     MsgType
13    from   int
14    to     int
15    number int    // proposal number
16    value  string // proposal value
17}
18
19

1type network interface {
2    send(m message)
3    recv(timeout time.Duration) (message, bool)
4}
5
6

 1type Network struct {
 2    queue map[int]chan message
 3}
 4
 5func newNetwork(nodes ...int) *Network {
 6    pn := &Network{
 7        queue: make(map[int]chan message, 0),
 8    }
 9
10    for _, a := range nodes {
11        pn.queue[a] = make(chan message, 1024)
12    }
13    return pn
14}
15
16func (net *Network) send(m message) {
17    log.Printf("net: send %+v", m)
18    net.queue[m.to] <- m
19}
20
21func (net *Network) recvFrom(from int, timeout time.Duration) (message, bool) {
22    select {
23    case m := <-net.queue[from]:
24        log.Printf("net: recv %+v", m)
25        return m, true
26    case <-time.After(timeout):
27        return message{}, false
28    }
29}
30
31

 1// Phase 1. (a) A proposer selects a proposal number n
 2
 3// and sends a prepare request with number n to 
 4// a majority of acceptors.
 5func (p *proposer) prepare() []message {
 6    p.round++
 7    p.number = p.proposalNumber()
 8    msg := make([]message, p.majority())
 9    i := 0
10
11    for to := range p.acceptors {
12        msg[i] = message{
13            tp:     Prepare,
14            from:   p.id,
15            to:     to,
16            number: p.number,
17        }
18        i++
19        if i == p.majority() {
20            break
21        }
22    }
23    return msg
24}
25
26// proposal number = (round number, serverID)
27func (p *proposer) proposalNumber() int {
28    return p.round<< 16 | p.id
29}
30
31

 1func (a *acceptor) handlePrepare(args message) (message, bool) {
 2    if a.promiseNumber >= args.number {
 3        return message{}, false
 4    }
 5    a.promiseNumber = args.number
 6    msg := message{
 7        tp:     Promise,
 8        from:   a.id,
 9        to:     args.from,
10        number: a.acceptedNumber,
11        value:  a.acceptedValue,
12    }
13    return msg, true
14}
15
16

 1func (p *proposer) accept() []message {
 2    msg := make([]message, p.majority())
 3    i := 0
 4    for to, ok := range p.acceptors {
 5        if ok {
 6            msg[i] = message{
 7                tp:     Propose,
 8                from:   p.id,
 9                to:     to,
10                number: p.number,
11                value:  p.value,
12            }
13            i++
14        }
15
16        if i == p.majority() {
17            break
18        }
19    }
20    return msg
21}
22
23

 1func (a *acceptor) handleAccept(args message) bool {
 2    number := args.number
 3    if number >= a.promiseNumber {
 4        a.acceptedNumber = number
 5        a.acceptedValue = args.value
 6        a.promiseNumber = number
 7        return true
 8    }
 9
10    return false
11}
12
13

 1func (l *learner) chosen() (message, bool) {
 2    acceptCounts := make(map[int]int)
 3    acceptMsg := make(map[int]message)
 4
 5    for _, accepted := range l.acceptors {
 6        if accepted.number != 0 {
 7            acceptCounts[accepted.number]++
 8            acceptMsg[accepted.number] = accepted
 9        }
10    }
11
12    for n, count := range acceptCounts {
13        if count >= l.majority() {
14            return acceptMsg[n], true
15        }
16    }
17    return message{}, false
18}
19
20

1go test
2
3