文档章节

paxos算法理解

hgfgoodcreate
 hgfgoodcreate
发布于 2016/04/27 09:17
字数 2432
阅读 468
收藏 3

主要从以下几点理解paxos:

  1. 基础paxos算法
    1. 阶段一:prepare
    2. 阶段二:accept
  2. multi-paxos
    1. 选择log entry
    2. leader选举
    3. 消除prepare RPC调用
    4. 全备份
  3. 客户端协议
  4. 改变系统配置

基础paxos

只有一个acceptor可以吗? 不可以。所有的proposer都往一个acceptor上发消息,这个acceptor crashed,那么整个系统就crashed。 解决方法:使用quorum (仲裁人数)。多个acceptor, 只需要大多数acceptor选中某个value就可以了,万一某一个acceptor crashed,不影响系统。

每个acceptor 只chose第一个value,这样可以吗? 不可以。因为这样可能会出现proposal1的acceptor和proposal2的acceptor的数量一样多,无法选出哪一个proposal作为chosenproposal。例如server1 选中proposal1,server2 选中proposal1和proposal2,server3 选中proposal2。 解决方案:每个proposer在发起proposal前必须确认当前是否有proposal选中,如果有,则放弃自己的proposal。

chosen过程中会出现冲突,依据冲突不同得出结论: 一旦选中一个proposal,其他竞选proposal必须选择同样的value;proposal按照proposal number排序,拒绝旧proposal;

通过上述描述, 可设计proposal number 结构如下: 由两部分组成:

  1. round number: paxos执行的回数,每个服务器都必须保持最新的maxRound【保证尽量少的出现冲突,都竞争最大编号】
  2. server id:每个服务器有唯一的id【保证proposal编号不会相同 】

maxRound必须保存在永久存储介质上,一段server crash,可以重新使用 round number 发起proposal

  • paxos各阶段目标:
    • prepare阶段
      1. 发现任任何被选择的proposal。发现后将自己的value改为发现的Value
      2. 阻塞还未完成的proposal。当proposal number较大的proposal进入prepare阶段后,旧的proposal在accept阶段会被拒绝。
    • accept阶段
      1. 使得所有acceptor接受proposal。

主要逻辑:

|proposer|acceptor| |-|-| |1.选择proposal number n|| |2.广播给acceptor prepare(n)|| ||3. 响应prepare(n): if (n > minProposol) then minProposol=n; Return(acceptedProposol,acceptedValue)| |4. 获取大多数acceptor回复:如果有返回,选择返回中最大的proposal number 对应的value作为本次proposal的value;如果没有返回,可继续使用之前的value|| |5.向所有acceptor广播accept(n,value)|| ||6. 响应accept(n,value):if(n >= minProposol) then acceptedProposol = minProposol = n; accptedValue = value; Return minProposol| |7. 获取大多数acceptor返回:如果存在result>n;表示proposal被拒绝,重复1~6,且下次设置的n比result大,否则chosen proposal||

所有竞争的proposal必须有一个公共的acceptor,这样就能发现新旧proposal,并及时终止旧proposal。

paxos活锁:导致无proposal chosen。 proposal A 早prepare阶段通过,另一proposal B进入prepare, acceptor的minProposal增加,导致A在accept阶段被拒绝,A立即重试,并进入prepare阶段,导致acceptor的minProposal增加,B进入accept阶段后被拒绝。。。如此往复。没有command能正常进行。

解决方案:每次重试必须在随机的时延后进行。

multi-paxos

如何选择log entry?

实现步骤:

  1. 找到第一个log entry 不知道是否chosen的entry slot,(不一定是第一个为空的slot)
  2. 运行basic paxos, value为client command,
  3. prepare return 中是否包含acceptedvalue?
    • 有:chosen acceptedvalue,并重复步骤1
    • 无:chosen client请求,该slot即是寻找的slot

例子:

| |1|2|3|4|5|6|7| |-|-|-|-|-|-|-|-| |server 1|mov|add|cmp|||ret|| |server 2|mov|add||sub||ret|| |server 3|mov|add|cmp||cmp|ret||

如上表,当client请求jmp时,假设server3 crashed,此时到slot3,由于server1和server2不同,不知道是否chosen Proposal,于是以client command的值为value; 运行paxos,进入prepare(n),server1 slot3已经有acceptedvalue,所以Proposal的value会改为server 1 slot 3的值,然后进行accept阶段,server2 slot3 接收value。将server2 slot3 改为cmp。

| |1|2|3|4|5|6|7| |-|-|-|-|-|-|-|-| |server 1|mov|add|cmp|||ret|| |server 2|mov|add|cmp|sub||ret|| |server 3|mov|add|cmp||cmp|ret||

同理,server1 slot4 改为sub:

| |1|2|3|4|5|6|7| |-|-|-|-|-|-|-|-| |server 1|mov|add|cmp|sub||ret|| |server 2|mov|add|cmp|sub||ret|| |server 3|mov|add|cmp||cmp|ret||

然后slot5, acceptedValue=null;次次Proposal的value为元定义的value,即client的command。

| |1|2|3|4|5|6|7| |-|-|-|-|-|-|-|-| |server 1|mov|add|cmp|sub|jmp|ret|| |server 2|mov|add|cmp|sub|jmp|ret|| |server 3|mov|add|cmp||cmp|ret|| 找到 log entry slot。

注意:上述server3 crashed!

在上述处理过程中:server可以同时接收多个client请求,只要能保证client 请求的log Entry不同即可; 但是在command进入server状态机执行的时候,必须是顺序进行。

如何改善multi-paxos性能?

multi-paxos的问题:

  1. 多个proposer进行时,会出现冲突和重试,降低系统chosen效率;
  2. 对每个选定的value需要进行2回RPC调用;

解决方案:

  1. 选择learder。一次只有一个leader,这样就不会有多proposer发生冲突

  2. 清除绝大多数的prepare RPC调用

    • 进行一次prepare
    • 大多数的log entry 能在一个RPC调用完成
  3. 如何选择leader? 1.让serverid最大的作为leader; 2.每隔Tms,每个server发送心跳包给其他server, 3.如果server在2Tms内没有收到比它大的server心跳,那么它可以作为leader,接受client 请求,拥有proposer角色 4.不是leader的server,拒绝client请求将请求重新定向到leader,acceptor角色。

  4. 怎么处理prepare阶段

    1. 为什么需要prepare阶段?
      1. 阻塞旧Proposal:
        • 将Proposal与logEntry slot关联,每个Proposal number表示一个slot
      2. 查找可能chosen的value:
        • 最大的acceptedProposal 的values;
        • 当前log entry slot中,每个server的当前slot都没有acceptedvalue,返回noMoreAccepted
    2. 改进后:
      1. 如果acceptor返回noMoreAccepted,则跳过同slot当前server 后的所有的prepare RPC(直到accept拒绝Proposal,拒绝Proposal说明acceptro层接受过Proposal,存在acceptedvalue)。
      2. 如果leader得知noMoreAccepted,不需要使用prepare了,直接进入accpt阶段。因为所有server的该slot均为空,直接通知acceptor accept Proposal。此时只需要一轮accept RPC。

怎么全备份? 目标:每个server上的备份都是全备份。

目标细分:

  1. log entry没有full replication:full replication
  2. 只有proposer知道那个entry被chosen:所有server都知道那个entry被选中。

解决步骤:

  1. proposer在后台一直accept 请求RPC,直到到所有server都回应。能保证大多数server都是full replication(为什么只是大多数?因为有可能之前有server crash,有些log entry为空,就算回应一次,并不能把所有slot都都填充完整,操作布恩那个进入状态机执行,不能达到full replication)
  2. track chosen entries
    1. 使得entries能被知道是否已经chosen:acceptedEntry[i] = 无穷大 表示第i个entry被chosen。
    2. 每个server都维护一个firstUnchosenIndex,该索引是entry的索引,表示该索引前的entry均被chosen。
  3. proposer(也就是leader)告知acceptor选择entry:
    1. proposer在accept RPC时,发送firstUnchosenIndex。那么acceptor知道entry索引小于firstUnchosenIndex的均被chosen。
    2. acceptor标记同时满足以下条件的entry为chosen:i<firstUnchosenIndex && accptedProposal[i] == proposal【proposal相等即表示是同一个leader发送的proposal,又index < firstUnchosenIndex,可知前面均chosen,】
  4. acceptor不能确认proposal number不同的log entry 是否chosen。 解决方案:acceptor在返回时,返回acceptor的firstUnchosenIndex,若proposer的firstUnchosenIndex 大于acceptor的firstUnchosenIndex, 那么proposer在后台发送[success] RPC。
success(Index, v):
acceptedValue[index] = v;
acceptedProposal[index]=无穷大
return firstUnchosenIndex

客户端协议

  1. 发送command给leader
    1. 如果leader down, 发送消息给任意的server
    2. 如果联系的server不是leader,自动重定向到leader
  2. leader在command被log entry选中后,在leader的状态机中执行,执行出结果,然后回应client
  3. 请求超时
    1. clinet请求别的server
    2. 重定向leader server
    3. 重新请求command
  4. 如果leader在执行后,响应client前crash,一条command不能被执行两次
    1. client为每个command提供唯一的标识
    2. server 在log entry中保存command id
    3. 状态机保最近的每个client的commandid
    4. 执行command前,状态机检查command是否已经执行过,执行过,直接忽略并返回old command的执行结果。

如果client在发送command后,接受响应前crash, 然后重新登陆,会遇到同样的问题。client会提交两次command,使用上述措施可以保证每条command只执行一次。

配置修改

系统配置:serverid和address 这些直接会改变quorum。造成系统的majority数量的改变。

为什么需要系统设置变化:

  1. server crash
  2. replication change

安全原则:在配置变动时,避免对同一个log entry 有不同数量的majority和不同的value选择。

解决方案:使用paxos中log entry管理配置变动

  1. 配置保存为log entry
  2. 和其他log entry一样备份
  3. 在choseing log entry i 时 使用log entry index为i-a作为系统配置。(其中a为系统参数,在系统启动时定义)

引入a后:

  1. 系统的并发数量必须在a以内:因为在log entry i 被chosen后才能 chosen entry a+i; 可以使用一些无操作的command加速配置改变。

核心为代码

核心逻辑伪代码:

--- Paxos Proposer ---
proposer(v):
	while not decided:
	choose n, unique and higher than any n seen so far
	send prepare(n) to all servers including self
	if prepare_ok(n, na, va) from majority:
		v’ = va with highest na; choose own v otherwise
		send accept(n, v’) to all
		if accept_ok(n) from majority:
			send decided(v’) to all
--- Paxos Acceptor ---
acceptor state on each node (persistent):
np --- highest prepare seen
na, va --- highest accept seen

acceptor’s prepare(n) handler:
	if n > np
		np = n
		reply prepare_ok(n, na, va)
	else
		reply prepare_reject

acceptor’s accept(n, v) handler:
	if n >= np
	np = n
	na = n
	va = v
	reply accept_ok(n)
	else
		reply accept_reject

readmore:算法证明

© 著作权归作者所有

上一篇: spring cache
下一篇: 数据库技巧---join
hgfgoodcreate
粉丝 15
博文 65
码字总数 139099
作品 0
海淀
程序员
私信 提问
图解分布式一致性协议Paxos

Paxos协议/算法是分布式系统中比较重要的协议,它有多重要呢? <分布式系统的事务处理>: Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法,那就是Paxos,其它的算法都是残...

wangdy
2016/06/22
15
0
Distributed Systems-一致性协议背景介绍及Paxos算法的推导

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/feilengcui008/article/details/50829689 Paxos算法无疑是分布式系统理论中的经典,由于很多论文、博客都没有...

feilengcui008
2016/03/08
0
0
分布式系统的共识(consensus)算法比较

这是一篇比较分布式系统中服务器之间获得状态最终一致性也就是取得共识consensus几个流行算法,包括Paxos、Egalitarian Paxos、Hydra、Fast Paxos、Ios、VRR(Viewstamped Replication Revis...

大糊涂
2016/04/10
614
0
Raft 与 Paxos的区别

Raft Raft概述 Raft一致性算法用于保证在分布式的条件下,所有的节点可以执行相同的命令序列,并达到一致的状态。这类的问题可以归结为“Replicated state machines”问题。 Raft一致性算法的...

cloud-coder
2016/07/14
1K
0
Paxos 算法原理与推导

本文作者:伯乐在线 -LBD 。未经作者许可,禁止转载! 欢迎加入伯乐在线专栏作者。 原文:www.linbingdong.com Paxos算法在分布式领域具有非常重要的地位。但是Paxos算法有两个比较明显的缺点...

伯乐在线
2017/02/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

idea下springboot 项目在static目录下添加文件不生效

idea下springboot 项目在static目录下添加文件不生效 问题描述 是这样子的,我的项目目录结构如下: 我在static目录下,创建了index.html和aaaa.jpg这两个文件。然后,启动服务访问 http://l...

wotrd
昨天
5
0
k8s1.14 一、环境

1. 4台虚拟机 (CentOS Linux release 7.2.1511 (Core) ) 192.168.130.211 master 192.168.130.212 node1 192.168.130.213 node2 192.168.130.214 node3 2. 设置服务器hostname 2.1 设置本机......

ThomasCheng
昨天
4
0
盖茨:如果我现在开创一家公司 将会专注于AI

新浪科技讯,北京时间 6 月 26 日凌晨消息,微软联合创始人比尔·盖茨(Bill Gates)在周一接受采访时表示,如果他今天从哈佛大学辍学并开创一家新公司,那么这家公司将会专注于人工智能(A...

linuxCool
昨天
1
0
聊聊feign的Retryer

序 本文主要研究一下feign的Retryer Retryer feign-core-10.2.3-sources.jar!/feign/Retryer.java public interface Retryer extends Cloneable { /** * if retry is permitted, retur......

go4it
昨天
14
0
HyperLogLog简介

  (1)HyperLogLog简介      在Redis 在 2.8.9 版本才添加了 HyperLogLog,HyperLogLog算法是用于基数统计的算法,每个 HyperLogLog 键只需要花费 12 KB 内存,就可以计算接近 2^64 个...

SEOwhywhy
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部