用 Golang 快速实现 Paxos 分布式共识算法

简介:   前文《理解 Paxos》只包含伪代码,帮助了理解但又不够爽,既然现在都讲究 Talk is cheap. Show me the code.这次就把文章中的伪代码用 Go 语言实现出来,希望能帮助各位朋友更直观的感受 Paxos 论文中的细节。  但我们需要对算法做一些简化,有多简单呢?我们不持久化存储任何变量,并且用 chan直接代替 RPC 调用。

  前文《理解 Paxos》只包含伪代码,帮助了理解但又不够爽,既然现在都讲究 Talk is cheap. Show me the code.这次就把文章中的伪代码用 Go 语言实现出来,希望能帮助各位朋友更直观的感受 Paxos 论文中的细节。

  但我们需要对算法做一些简化,有多简单呢?我们不持久化存储任何变量,并且用 chan直接代替 RPC 调用。

  记得切换到 naive 分支。

  我们定义 Proposer 如下:

  type proposer struct {

  // server id

  id int

  // the largest round number the server has seen

  round int

  // proposal number=(round number, serverID)

  number int

  // proposal value

  value string

  acceptors map[int]bool

  net network

  }

  这些结构体成员都很容易理解,其中 acceptors我们主要用来存储 Acceptors 的地址,以及记录我们收到 Acceptor 的成功/失败响应。

  Acceptor 的结构体:

  type acceptor struct {

  // server id

  id int

  // the number of the proposal this server will accept, or 0 if it has never received a Prepare request

  promiseNumber int

  // the number of the last proposal the server has accepted, or 0 if it never accepted any.

  acceptedNumber int

  // the value from the most recent proposal the server has accepted, or if it has never accepted a proposal

  acceptedValue string

  learners int

  net network

  }

  主要成员解释都有注释,简单来说我们需要记录三个信息:

  promiseNumber:承诺的提案编号

  acceptedNumber:接受的提案编号

  acceptedValue:接受的提案值

  消息结构体定义了 Proposer 和 Acceptor 之间、Acceptor 和 Leaner 之间的通讯协议。最主要的还是 Paxos 的两阶段的四个消息。

  Phase 1 请求:提案编号

  Phase 1 响应:如果有被 Accepted 的提案,返回提案编号和提案值

  Phase 2 请求:提案编号和提案值

  Phase 2 响应:Accepted 的提案编号和提案值

  这样看,我们的消息结构体只需要提案编号和提案值,加上一个消息类型,用来区分是哪个阶段的消息。消息结构体定义在 message.go 文件,具体如下:

  // MsgType represents the type of a paxos phase.

  type MsgType uint8

  const (

  Prepare MsgType=iota

  Promise

  Propose

  Accept

  )

  type message struct {

  tp MsgType

  from int

  to int

  number int // proposal number

  value string // proposal value

  }

  网络上可以做的选择和优化很多,但这里为了保持简单的原则,我们将网络定义成 interface。后面完全可以改成 RPC 或 API 等其它通信方式来实现(没错,我已经实现了一个 Go RPC 的版本了)。

  type network interface {

  send(m message)

  recv(timeout time.Duration) (message, bool)

  }

  接下里我们去实现 network 接口:

  type Network struct {

  queue map[int]chan message

  }

  func newNetwork(nodes ...int) *Network {

  pn :=&Network{

  queue: make(map[int]chan message, 0),

  }

  for _, a :=range nodes {

  pn.queue[a]=make(chan message, 1024)

  }

  return pn

  }

  func (net *Network) send(m message) {

  log.Printf("net: send %+v", m)

  net.queue[m.to] <- m

  }

  func (net *Network) recvFrom(from int, timeout time.Duration) (message, bool) {

  select {

  case m :=<-net.queue[from]:

  log.Printf("net: recv %+v", m)

  return m, true

  case <-time.After(timeout):

  return message{}, false

  }

  }

  就是用 queue来记录每个节点的chan,key 则是节点的 server id。

  发送消息则将 Message发送到目标节点的chan中,接受消息直接从chan中读取数据,并等待对应的超时时间。

  不需要做其它网络地址、包相关的东西,所以非常简单。具体在 network.go文件。

  这个项目主要使用 go 单元测试来检验正确性,我们主要测试两种场景:

  TestSingleProposer(单个 Proposer)

  TestTwoProposers(多个 Proposer)

  测试代码通过运行 Paxos 后检查 Chosen 返回的减肥提案值是否符合预期。

  按照角色将文件分为 proposer.go, acceptor.go 和 learner.go,每个文件都有一个 run函数来运行程序,run函数执行条件判断,并在对应的阶段执行对应的函数。

  按照伪代码描述,我们很容易实现 Phase 1 和 Phase 2,把每个阶段的请求响应都作为一个函数,我们一步步来看。

  // Phase 1. (a) A proposer selects a proposal number n

  // and sends a prepare request with number n to

  // a majority of acceptors.

  func (p *proposer) prepare message {

  p.round++

  p.number=p.proposalNumber

  msg :=make(message, p.majority)

  i :=0

  for to :=range p.acceptors {

  msg[i]=message{

  tp: Prepare,

  from: p.id,

  to: to,

  number: p.number,

  }

  i++

  if i==p.majority {

  break

  }

  }

  return msg

  }

  // proposal number=(round number, serverID)

  func (p *proposer) proposalNumber int {

  return p.round<< 16 | p.id

  }

  Prepare 请求阶段我们将 round+1 然后发送给多数派 Acceptors。

  注:这里很多博客和教程都会将 Prepare RPC 发给所有的Acceptors,6.824 的 paxos 实验就将 RPC 发送给所有 Acceptors。这里保持和论文一致,只发送给 a majority of acceptors。

  接下来在 acceptor.go文件中处理请求:

  func (a *acceptor) handlePrepare(args message) (message, bool) {

  if a.promiseNumber >=args.number {

  return message{}, false

  }

  a.promiseNumber=args.number

  msg :=message{

  tp: Promise,

  from: a.id,

  to: args.from,

  number: a.acceptedNumber,

  value: a.acceptedValue,

  }

  return msg, true

  }

  如果 args.number大于acceptor.promiseNumber,则承诺将不会接收编号小于args.number的提案(即a.promiseNumber=args.number)。如果之前有提案被 Accepted 的话,响应还应包含 a.acceptedNumber 和 a.acceptedValue。

  否则忽略,返回 false。

  func (p *proposer) accept message {

  msg :=make(message, p.majority)

  i :=0

  for to, ok :=range p.acceptors {

  if ok {

  msg[i]=message{

  tp: Propose,

  from: p.id,

  to: to,

  number: p.number,

  value: p.value,

  }

  i++

  }

  if i==p.majority {

  break

  }

  }

  return msg

  }

  当 Proposer 收到超过半数 Acceptor 的响应后,Proposer 向多数派的 Acceptor 发起请求并带上提案编号和提案值。

  func (a *acceptor) handleAccept(args message) bool {

  number :=args.number

  if number >=a.promiseNumber {

  a.acceptedNumber=number

  a.acceptedValue=args.value

  a.promiseNumber=number

  return true

  }

  return false

  }

  Acceptor 收到 Accept请求,在这期间如果 Acceptor 没有对比 a.promiseNumber 更大的编号另行 Promise,则接受该提案。

  在 Paxos 中有一个十分容易混淆的概念:Chosen Value 和 Accepted Value,但如果你看过论文,其实已经说得非常直接了。论文的 2.3 节 Learning a Chosen Value 开头就说:

  To learn that a value has been chosen, a learner must find out that a proposal has been accepted by a majority of acceptors.

  所以 Acceptor 接受提案后,会将接受的提案广播 Leaners,一旦 Leaners 收到超过半数的 Acceptors 的 Accepted 提案,我们就知道这个提案被 Chosen 了。

  func (l *learner) chosen (message, bool) {

  acceptCounts :=make(map[int]int)

  acceptMsg :=make(map[int]message)

  for _, accepted :=range l.acceptors {

  if accepted.number !=0 {

  acceptCounts[accepted.number]++

  acceptMsg[accepted.number]=accepted

  }

  }

  for n, count :=range acceptCounts {

  if count >=l.majority {

  return acceptMsg[n], true

  }

  }

  return message{}, false

  }

  代码拉下来后,直接运行:

  go test

  之前我曾把 mit 6.824 的 Raft 答案推到自己的 Github,直到 2020 开课的时候 mit 的助教发邮件让我将我的代码转为 private,因为这样会导致学习课程的人直接搜到代码,而无法保证作业独立完成。

  确实,实验是计算机最不可或缺的环节,用 mit 6.824 2015 的 paxos 代码会导致很多学习者不去自己解决困难,直接上网搜代码,从而导致学习效果不好,违背了 mit 的初衷。

  当然,你也可以说现在网上以及很容易搜到 6.824 的各种代码了,但出于之前 mit 助教的邮件,我不会将作业代码直接发出来。

目录
相关文章
|
7天前
|
消息中间件 算法 分布式数据库
Raft算法:分布式一致性领域的璀璨明珠
【4月更文挑战第21天】Raft算法是分布式一致性领域的明星,通过领导者选举、日志复制和安全性解决一致性问题。它将复杂问题简化,角色包括领导者、跟随者和候选者。领导者负责日志复制,确保多数节点同步。实现细节涉及超时机制、日志压缩和网络分区处理。广泛应用于分布式数据库、存储系统和消息队列,如Etcd、TiKV。其简洁高效的特点使其在分布式系统中备受青睐。
|
7天前
|
算法 分布式数据库
Paxos算法:分布式一致性的基石
【4月更文挑战第21天】Paxos算法是分布式一致性基础,由Leslie Lamport提出,包含准备和提交阶段,保证安全性和活性。通过提案编号、接受者和学习者实现,广泛应用于分布式数据库、锁和配置管理。其简单、高效、容错性强,影响了后续如Raft等算法,是理解分布式系统一致性关键。
|
7天前
|
算法 Go 分布式数据库
构建高可用的分布式数据库集群:使用Go语言与Raft共识算法
随着数据量的爆炸式增长,单一数据库服务器已难以满足高可用性和可扩展性的需求。在本文中,我们将探讨如何使用Go语言结合Raft共识算法来构建一个高可用的分布式数据库集群。我们不仅会介绍Raft算法的基本原理,还会详细阐述如何利用Go语言的并发特性和网络编程能力来实现这一目标。此外,我们还将分析构建过程中可能遇到的挑战和解决方案,为读者提供一个完整的实践指南。
|
7天前
|
算法
【免费】基于ADMM算法的多微网电能交互分布式运行策略(matlab代码)
【免费】基于ADMM算法的多微网电能交互分布式运行策略(matlab代码)
|
7天前
|
算法 Serverless 调度
基于分布式ADMM算法的考虑碳排放交易的电力系统优化调度研究(matlab代码)
基于分布式ADMM算法的考虑碳排放交易的电力系统优化调度研究(matlab代码)
|
7天前
|
分布式计算 Java Go
Golang深入浅出之-Go语言中的分布式计算框架Apache Beam
【5月更文挑战第6天】Apache Beam是一个统一的编程模型,适用于批处理和流处理,主要支持Java和Python,但也提供实验性的Go SDK。Go SDK的基本概念包括`PTransform`、`PCollection`和`Pipeline`。在使用中,需注意类型转换、窗口和触发器配置、资源管理和错误处理。尽管Go SDK文档有限,生态系统尚不成熟,且性能可能不高,但它仍为分布式计算提供了可移植的解决方案。通过理解和掌握Beam模型,开发者能编写高效的数据处理程序。
142 1
|
7天前
|
Prometheus 监控 Cloud Native
Golang深入浅出之-Go语言中的分布式追踪与监控系统集成
【5月更文挑战第4天】本文探讨了Go语言中分布式追踪与监控的重要性,包括追踪的三个核心组件和监控系统集成。常见问题有追踪数据丢失、性能开销和监控指标不当。解决策略涉及使用OpenTracing或OpenTelemetry协议、采样策略以及聚焦关键指标。文中提供了OpenTelemetry和Prometheus的Go代码示例,强调全面可观测性对微服务架构的意义,并提示选择合适工具和策略以确保系统稳定高效。
148 5
|
7天前
|
存储 分布式计算 负载均衡
分布式(计算机算法)
分布式(计算机算法)
|
7天前
|
缓存 算法 关系型数据库
深度思考:雪花算法snowflake分布式id生成原理详解
雪花算法snowflake是一种优秀的分布式ID生成方案,其优点突出:它能生成全局唯一且递增的ID,确保了数据的一致性和准确性;同时,该算法灵活性强,可自定义各部分bit位,满足不同业务场景的需求;此外,雪花算法生成ID的速度快,效率高,能有效应对高并发场景,是分布式系统中不可或缺的组件。
125 2
深度思考:雪花算法snowflake分布式id生成原理详解
|
7天前
|
存储 算法 前端开发
作者推荐 | 分布式协议之巅 — 揭秘基础Paxos与Raft协议如何实现分布式系统达成一致性(非变种Paxos协议)
作者推荐 | 分布式协议之巅 — 揭秘基础Paxos与Raft协议如何实现分布式系统达成一致性(非变种Paxos协议)
64 0