k-modes算法优缺点(Multi-Paxos算法及优化)
本文翻译自youtube视频: [Paxos lecture (Raft user study) - YouTube](https://www.youtube.com/watch?v=JEpsBg0AO6o&t=3575s)
在讲解Paxos和Raft算法时,通常都会引用一个replicated log问题。我们由这个问题开始,去分析Paxos和Raft算法是如何解决。
问题有多台server的cluster。
Client可以发送一个指令到任何一台server上。
某一个server(假设S1)接受指令后,会保存在一条log列表里,并且提交给状态机执行log。同时S1会将指令同步到别的server上,别的server也会将log提交给自己的状态机执行。
理想的情况是,所有server执行指令的顺序都是一样的。 如何保证这一点呢?
这个问题的核心是,如果创建一个replicated log。
解决
为了解决这个问题,我们需要运行Multi-Paxos,log列表里每一个index都是单独的Paxos。具体的流程如下图:
1. client给一个server发送指令
2. server运行一个Paxos,来决定这条指令放在log的哪个index
3. server等待log中前边所有的指令运行,然后运行这条新指令。
4. server给client返回response。
在这个过程中,最关键的问题是第二步:决定一个指令应该放在log的哪个index。举例说明:
上图是一个三个server(S1~S3)的集群。
在上图的左侧,我们分析一下当前的状态。对于S1来说,当前的状态是:
1) index 1/2/6已知被chosen了
2) index 3被S1Accept了,但是不知道被chosen了。同时S1并不知道S3的index 3也是cmp指令。
3) index 4/5还是空的
举例:当jmp指令到达了S1,发生了什么?
1. 找到第一个没有被chosen的index,在这种情况下就是index3
2. 在这个index3上运行paxos
3. 在Prepare阶段,发现有的server返回 acceptedValue=cmp
4. 转而提出cmp指令。最终cmp指令被chose在index3上。
5. 对index4做出同样的操作,Prepare阶段发现有sub,运行Paxos之后把sub指令放在index4上
6. 对于index5来说,假设这里majority是S1和S2,prepare没有返回acceptedValue,于是运行Paxos accept,jmp被chosen在index5上。
到这里其实就结束了。细心的同学会发现S3上的index5上有另一条指令不是jmp,这不是矛盾了吗?其实不是的。在Paxos的世界里,只要majority的server accept了这个值,那这个值就已经被chosen了。
有些同学可能会想,index5上的另一个指令来的比jmp要早,但是jmp在这里被choose了。这难道不是错误的吗?其实并不是,如果客户端想让server按照一定顺序执行指令,这是客户端的任务。客户端需要等一个指令执行完成之后,再发送另一个指令,才能实现这一点。而在这里,客户端连续发送了很多指令,导致一些指令发送给了S3,另一些给了S1,在分布式系统中,这样的情况无论如何也无法保证指令执行的顺序。
性能优化我们可以有多个措施来优化这个multi-paxos算法。
1. 为了避免死锁,在同一时间只有一个proposer leader
2. 消除大部分的prepare指令
* 对整个log prepare一次 (而不是每个index prepare一次)
* 大部分的index的值在一轮paxos之后就可以定下来
下边我们具体来分析上述措施
1) 选举proposer的leader
最简单的方法是选择ID最大的那个
* server互相发送心跳
* 如果一个server一段时间没收到来自更高ID server的心跳,他就是leader,leader的作用是:1) 接受client指令。2) 充当proposer和acceptor
* 如果一个server不是leader:1) 拒绝client指令。2) 只充当acceptor
大家会发现这个算法变得有点像Raft了……
2)消除大部分prepare指令
为啥能消除prepare指令呢?首先我们复习一下prepare指令是干啥的:
任务一:block 旧的proposal
* 为了完成这个任务,在这里我们可以改变proposal number的含义。以前proposal number代表一个log中一个index的proposal,现在我们将其代表这个log的proposal。也就是说我们一个prepare block一个index下旧的proposal,现在一个prepare block整个log的旧proposal。
任务二:找到可能的chosen value
* 为了完成这个任务,在prepare阶段,acceptor如果发现在当前index以后没有accept的value了,acceptor还要返回一个noMoreAccepted字段。这样proposer就知道后边不可能有可能被chosen的value了。
这样的话,我们能达到两个效果
1. 如果一个acceptor在prepare阶段返回了noMoreAccepted,我们可以跳过这个acceptor以后所有的Prepare阶段,除非有Accept阶段被reject了。
2. 如果一个leader从大多数acceptor处收到了noMoreAccepted,就再也不需要Prepare阶段了。
保证Full Replication对于现阶段的Multi-Paxo算法,我们还有两个问题:
1. 对于每一个index,被chosen的指令只保存在majority server上。 目标:保存到所有的server上。
2. 当一个index被chosen的时候,只有proposer知道。 目标:所有的server都知道。
大家仔细品味一下,注意这两个问题是有区别的。
解决方法有四步:
1. 为了解决第一个问题,proposal持续retry Accept步骤直到所有的acceptor都response。
* Paxos是当majority的acceptor都同意,就达到了一致。我们可以在background持续retry直到所有的acceptor都同意。
* 这一步基本可以解决第一个问题。
2. 为了解决第二个问题,acceptor需要知道自己的哪些value是被chosen状态,因此需要持续track chosen 的index
* 对于已经被chosen的index,标记accptedProposal=正无穷
* 每个server维护一个firstUnchosenIndex代表着最小的没有被chosen的index
3. 进一步,Proposer要通知Acceptor哪个index被chosen了
* 在Accept步骤,Proposer可以包含自己的firstUnchosenIndex,表示proposer已知的第一个没有被chosen的index,言外之意小于这个firstUnchosenIndex的index都已经被chosen了。
* acceptor在以下两个情况都满足的情况下,标记所有的index i为chosen
i < proposal.firstUnchosenIndex && acceptedProposal[I] = request.proposal
为什么?这块比较难理解。下图举例说明。
收到Accept之前,index1/2/3/5都已经被标记成chosen了,而index4表示accept了proposal number=2.5的proposal,index6表示accept了proposal number=3.4的proposal。
现在来了一个Accept请求,proposal number=3.4, firstUnchosenIndex=7。这意味着Proposer告诉Acceptor,<7的index都已经被chosen了。Acceptor收到这个请求之后,会比较index 1~6,如果有acceptedProposal=3.4,就直接标记成chosen。因为:
* 因为 acceptedProposal[I] = request.proposal,Acceptor就知道index=6的来源和这个Accetor request的来源是同一个Proposer
* Acceptor还知道Proposer的index6已经被chosen了
* Acceptor还知道,Proposer的index6最新值就是proposal number=3.4的值。因为Acceptor刚刚收到的Accept请求就是proposal number=3.4
需要注意的是,这个第三步只是解决了当前Proposer通知Acceptor的问题,Acceptor还可能保存着上一个Proposer的proposal。
4. 为了处理old leader问题
* Acceptor需要在Accepte步骤返回自己的firstUnchosenIndex
* 如果proposer的firstUnchosenIndex > 返回值的firstUnchosenIndex,说明Acceptor对于某些事情是不确定的。
* 在这种情况下,Proposer需要另一个步骤 Success告诉Acceptor自己的值,来消除Acceptor的不确定。
client协议1. 只给leader发送命令
2. leader必须执行完这个指令,才返回。而必须决定了这个指令的index,才会执行这个指令。
3. 如果client request timeout,retry command到另一个leader
问题:leader在sync完指令,执行完执行,但是还没有回复client的时候崩溃了!我们不能让command执行两次啊。。
解决:client在每一个指令中保存一个unique id
* server在log中保存这个id
* 执行完指令之后,就保存下最新执行的指令id
* 在执行指令之前,检查一下这个command是不是已经被执行过。
如果leader执行完指令之后crash了,client会retry同一个指令,这个时候新的leader就会发现这个指令被执行过了。
这样只要client不崩溃,我们就可以完成 执行每一个执行 exactly-once的语义
配置改变系统配置:
* 首先,每个server需要自己的ID
* 系统配置非常重要,因为这决定了什么组成了majority。当server数量从3个变成5个,majority的数量也就从2个变成了3个。这一点非常重要,举例如下图:
Config改变过程中会造成不一致。左边两个server还是旧的config,所以2个就是majority;右边三台机器有最新的config,他们知道majority其实应该是3台机器。这样左边两个choose了V1值,右边两个choose了V2值,这样就会造成不一致。
解决方案:把config也当做log中的一个index。下图中,C1和C2是两个config。我们在系统中定义了一个值α=3,α的意思是,index=1的config在index=1 α时才会生效。也就是index=4的时候开始用C1 config。同样index=6的时候才会用C2 config。
Α取值过小,会造成cocurrency性能问题。因为我们在index=i的config被chosen之后,才能去决定i α的值。当α=1的时候,系统退化成串行
Α取值过大,新config生效就会需要等待很长时间。
,
免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com