开发者社区> dasein58> 正文

用 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 助教的邮件,我不会将作业代码直接发出来。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
17088 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,大概有三种登录方式:
9467 0
使用SSH远程登录阿里云ECS服务器
远程连接服务器以及配置环境
13079 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
14698 0
阿里云服务器ECS远程登录用户名密码查询方法
阿里云服务器ECS远程连接登录输入用户名和密码,阿里云没有默认密码,如果购买时没设置需要先重置实例密码,Windows用户名是administrator,Linux账号是root,阿小云来详细说下阿里云服务器远程登录连接用户名和密码查询方法
21585 0
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
13864 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
24957 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,云吞铺子总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系统盘、创建快照、配置安全组等操作如何登录ECS云服务器控制台? 1、先登录到阿里云ECS服务器控制台 2、点击顶部的“控制台” 3、通过左侧栏,切换到“云服务器ECS”即可,如下图所示 通过ECS控制台的远程连接来登录到云服务器 阿里云ECS云服务器自带远程连接功能,使用该功能可以登录到云服务器,简单且方便,如下图:点击“远程连接”,第一次连接会自动生成6位数字密码,输入密码即可登录到云服务器上。
33133 0
+关注
919
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载