接下来,我们来讲解multi-paxos。大家应该还记得我们开始时提到的multi-paxos的目标是实现多副本log系统。要实现多副本log系统的一种方法就是,使用一组彼此独立的basic paxos实例,每个独立的basic paxos实例用来决定一系列log当中的一条。为了做到这一点,我们需要给Prepare和Accept两个rpc增加一个参数,index,用来表示这个basic paxos正在决策哪一条log。而所有的状态机只需要一步步地按顺序执行已经被选定的log。
这页ppt底部的图演示了整个系统的工作情况:
1. client希望状态机能执行一个command,他把这个请求发送给server的一致性模块(consensus module)。
2. server的一致性模块(consensus module)使用paxos,与其他server相互通信,并选定出这个log entry应该是什么值。
3. 一旦这个值被选定(这里假设前面的log都已经被状态机执行过了),这个值就可以输入到状态机中。
4. 状态机处理完这个command,进入新的状态,并返回处理结果给client。
这就是Multi-paxos基本的工作流程。我们接下来就要进入multi-paxos的细节当中,看看multi-paxos到底是怎么实现的。
这一页概述了为了让一个multi-paxos能够实实在在地跑起来,我们需要解决哪些问题。在这里我只是简单说明下,在接下来的几页ppt中,我再来展开讲。
第一个问题是,当一个client发起请求时,我们要怎样为此请求来选择一个log entry来存放这个命令?
第二个问题是怎么解决我们在前面讨论basic paxos时提到过的性能问题。如果完全按前面讲述的basic paxos来做的话,整个系统会非常缓慢。所以我们会使用leader这个角色来减少proposer之间的冲突;我也会给你们讲解怎么把大部分prepare请求都移除掉,而(大部分情况下都)只需要一次rpc调用,就能把值选定下来。
第三个问题是怎么确保一个完整的log副本被确定了下来,并且让所有的server都知道这一份完整的log副本。
第四个问题是关于与client间的协议的,我们会讨论client在multi-paxos中的server crash时最好怎么处理。
第五个问题则是关于配置变更,我们怎么在multi-paxos中增加或减少multi-paxos里的server?在增减过程中,是否安全?
我还应该提醒大家的是,basic paxos的问题和解决方案都是已经被白纸黑字定义、分析、描述得非常清楚,并且已经被严格地数学证明的。但multi paxos并不是这样,multi paxos在很多地方只是被很粗略地描述。实际上也并不止一种方法来解决这一页ppt中所描述的问题。我只是挑选了一种简单明了的方案,一个实际的系统在解决multi paxos问题时,很可能和我们接下来要讲的方案是不一样的。但我希望接下来的讲解至少可以让大家知道,在实现一个实际的multi paxos系统时,可以以怎样的思路来解决这几个问题。
刚才我们说到的第一个问题是,当客户端的请求到达时,我们应该怎样确定要使用哪一个位置来记录这条log?为了说清楚这个问题,我们直接看ppt底部的这个图。注意这里是有三台服务器,所以这里的大多数(majority)就是两台。在图的左侧展示的是每台服务器已经存储的log。
当客户端发送了一个命令,jmp,到s1这台服务器,希望这个命令被状态机执行时,整个系统就要决策到底这个command放在log的哪个位置了。对于s1这台服务器来说,他当前的每条log其实都可能处于以下几种状态之一:
1. s1知道已经被整个系统选定的log,这里就包括了第1、2、6三条(方框已经被加粗的)。我们后面会讨论s1是怎么知道这几条log已经被选定的(例如刚好是s1发起这些值的提议,所以s1就知道了),但现在我们只要了解s1知道这些log已被选定,就可以了。
2. 第二种状态就是s1服务器上虽然保存了一个值,但s1并不知道这个值有没有被系统选定。比如第3个位置的cmp。我们如果对比看三台服务器第3个位置的值,可以知道,这个cmp确实是被选定了,只是现在s1并不知道。当然也有可能这个值刚好就没被选定。
3. 还有一种状态是,s1服务器上为空的log位置,比如第4、5两个位置。s1没有为这些位置接受任何值,但当然,其他服务器可能接受过值。比如s2在第4个位置接受了sub这个值;而s3在第5个位置接受了cmp这个值。
这是基本的情况,我们接着往下走,看看会发生什么事。当client发送了jmp这个command到s1时,s1首先找到自己未知是否被选定的最小的log位置,这里就是第3个位置。
插一句,我们都知道这个系统只要有s1、s2两台机器,其实就能正常工作了。所以我们讨论的时候,其实可以完全把s3排除在外,这并不会影响我们最终的结论。我们直接把s3这一行划掉,不再考虑,所以整个paxos协议都是在s1和s2之间跑了。
我们接着刚才的思路往下说,s1在找到第3个位置时,(s1的proposer)就想尝试提议jmp放到这个位置上,但因为s1(s1的acceptor)其实已经接受了cmp这个值了,所以跑完basic paxos后,s1、s2都接受了cmp值。s1第3个位置变成确定选定状态,所以s1接着往后面找,找到第4个位置。这个位置s1是空的,所以s1尝试用跑一遍basic paxos。结果在prepare阶段时,s1就知道s2已经接受了sub这个值。跑完这遍basic paxos,s1也知道第4个位置被选定了,值是sub。s1接着往后找,到了第5个位置。s1、s2的第五个位置都是空的,所以s1发起basic paxos后,第5个位置就被确定成了jmp命令的位置。
如果s1下次又收到client的一个命令,那s1就会接着尝试第7个位置。以此类推。
总的来说,一台服务器收到一个客户端的请求后,就会从自己最小的未知是否选定的位置开始,跑basic paxos,这个位置不成功的话就再找下一个未知是否选定的位置,直到成功为止。
在这个系统里边,服务端可以批量并行处理客户端的请求。比如服务端知道3、5、7这几个位置都是未确定是否选定的,那就直接把收到的3个命令并行尝试塞到这三个位置。只要你在不同的log位置提交不同的命令,每个操作就是完全独立的,可以并行。但是,当状态机要取出log来作为输入时,那就必须是按照log顺序逐一执行。所以如果第3条log不是被选定,即使我们知道第4条log被选定了,状态机也不能执行第4条log,直到第3条log被选定。
下一个要讨论的问题就是效率。我们目前讨论过的basic paxos的算法有两个问题:
1. 如果所有的proposer都一起并行工作,我们因proposer间大量的冲突而需要重新协商的可能性就很大。你应该还记得我们前面讲到的basic paxos活锁的问题,这种情况是完全可能在这里发生的。并且随着负载的增加,这种冲突的可能性就越大。如果每台服务都在为客户端的命令选择log位置,他们很可能都会在同一个位置上竞争。每个proposer都需要和半数以上的acceptor进行通信,整个系统可能每台服务器都很忙,但其实进度并不快。
2. 每个log位置的值的选定,都需要至少两轮rpc调用。先要proposer要发起Prepare,然后还要发起Accept。
为了改善这里的效率,我们要对原来的算法做两个改动:
1. 我们要通过某种方式,使得在大部分典型的情况下,都只有一台server扮演proposer的角色。客户端所有的请求都发送到这台机器上。我们把这台server称为leader。
2. 第二个改变,就是要把绝大部分的prepare rpc都移除掉。为了做到这一点,proposer(现在改称为leader了)在发起第一个prepare时,不是针对一个log的位置来发起,而是针对整个log!一旦针对整个log的prepare阶段ok的话,我们就拥有了大量可用的log位置了,接下来只要对这些log位置调用accept rpc就可以了(直到被拒绝为止。译注:这里可能老师讲得还不是很明白,但后面的ppt马上就展开讲了)。
首先,我们来看下leader的选举。有很多方法可以选举出leader,这里只介绍兰伯特博士提出的一种,这种选举非常简单。
1. 既然每一台server都有一个id,那我们就直接让id最大的服务器来扮演leader的角色。
2. 每台server都定期向其他所有的服务器发送心跳,定期的时间定位T ms。
3. 如果一台server在一段时间内(2T)都没有收到比自己id大的服务器的心跳,那他就把自己转换成leader角色就可以了。所谓转换成leader角色,意味着两个事:a.开始接收处理客户端的请求;b.同时担任proposer和acceptor两个角色(在不是leader时,服务器是仅担任acceptor角色的)。
4. 如果一台server能收到比自己id大的服务器心跳,那他就不能做leader的角色。不做leader意味着两个事情:a.要拒绝掉客户端的请求,让客户端去和leader交互;b.不要担任proposer的角色,只担任acceptor的角色。
按照这种方式,系统中同时有两个leader的概率是较小的。但当然,即使系统中有两个leader,paxos也是能正常工作的,只是冲突的概率就大了很多,效率也就降低了很多。
我还要提醒的是,在大多数实际的系统里边,leader的选举方式可能为了得到其他优点(如更稳定)而不是这样的,实际的情况可能更复杂,但限于时间,这已经不是我这个视频所能覆盖到的了。
第二个效率的改进就是减少paxos过程中的rpc调用次数。为了做到这一点,我们要把大部分的Prepare请求移除掉。要弄清楚到底是怎么做到这一点的,我们先回过头来看一下我们为什么需要prepare请求。
之所以需要prepare请求,有两个原因:
1. 我们用prepare请求来阻塞掉老的提议。
2. 我们用prepare请求来找到可能已经被选定的值。
对于第一个作用,我们可以通过改变提议号(proposal number)的含义来做到。我们不再让proposal number仅阻塞一个log位置,而是让它变成全局的,即代表整个log。所以一旦我们prepare成功,整个log都会被阻塞掉。(这里要注意的是,虽然提议号变成全局的了,即一旦prepare成功,所有log位置都受这次prepare的影响,但这个proposer在accept阶段时还是 只需/也只能 accept自己申请的那个log位置的。)
对于第二个作用,(要做到移除掉大部分prepare请求)需要一点技巧性,我们要让prepare请求能带回多一点信息给我们。正常情况下,acceptor在收到prepare请求时,是只返回当前log位置的最大的提议号的。但如果acceptor发现,proposer要用的这个位置之后,其实全是空的,没有接受过任何值,那acceptor就额外返回一个标志位,noMoreAccepted,来告知proposer这一点。
一旦某个acceptor回了proposer一个noMoreAccepted标志,那leader在后面的paxos过程中,就可以跳过这个acceptor的prepare过程,而直接对此acceptor进行accept调用了。更进一步,如果过半数的acceptor都回了noMoreAccepted的标志,那leader就完全不需要发送prepare请求了,直接发送accept请求就可以了。这样,leader就基本上只需要发送一轮rpc就可以确定一条log了。
上述的情况可以一直持续,除非系统中出现了另一个leader,而这会导致当前leader的Accept请求被拒绝。这时,这个leader就又需要重新发起Prepare了。
第三个问题是如何做到信息在系统内完全公开可用(full disclosure)。这里的目标是让所有的服务器都得到完整的被选定的log副本。而当前已经讨论了的算法并不能保证acceptor得到所有的信息。比如:
1. 并不是每个acceptor都有所有的log,因为一条log要被选定,只需要被大多数acceptor接受即可。我们的目标是让每台服务器都有一份完整的log。
2. 当前只有发起请求的proposer知道到底一条日志是被选定的(proposer得知大多数acceptor都接受了他提出的值时,proposer就知道了),而其他服务器并不知道,比如acceptor就不知道自己存储的某条log到底有没有选定。我们的目标是让所有的服务器都知道哪些log是被选定的。
我们一定要得到完整的信息的一个原因是,只有一台机器log完整时,他才能把各个命令(即log)都传给状态机进行执行,从而使自己的状态机状态和leader保持一致。如果我们做不到这一点,其他机器不知道哪些log是被选定的,他们就无法将log传给状态机,也就无法让状态机的状态同步。
要做到这一点,有四个步骤。
1.第一个步骤是proposer在accept请求时,即使收到了大多数的acceptor的回复(这时proposer已经确定了自己的值被选定,按理是可以不理剩下的acceptor的回复的),proposer也仍要对未回复的acceptor进行重试。更具体地说,proposer在收到大多数acceptor的回复后,确认了一个log已经被选定了,proposer可以接着做后面的事情,比如看是否可以把这条log传给状态机执行,但同时仍继续在后台对未回复的acceptor进行重试。通过这种方式,我们就可以让所有acceptor几乎都得到一份完整的log。但并不是一定能得到,因为仍有可能因为服务器当机导致前面的一些log没有同步到。所以我们还需要其他步骤来保证。
2. 第二个步骤是在每台server上,我们都需要能跟踪哪些log是已经被选定的。通过两个方法来做到这一点:a. 一旦我们知道某条log已经被选定,那就把这条log对应的proposal number(即acceptedProposal变量)置成一个特定的值,以标识它已经被选定了。这里使用无穷大来代表这个特定的值,实际系统中,我们会挑选一个任何服务器都无法生成的最大的值来代表。因为根据我们的算法,只有proposal number大时,提议才可能被接受,所以我们知道这个值是永远也不会再被重写了的。b.每个server都维护一个firstUnchosenIndex的变量,用于标记自己最小的未选定的log index是多少。结合a,我们知道firstUnchosenIndex也就是acceptedProposal不为无穷大log中,index值最小的那条log的index。
3. 第三个步骤是,proposer要给acceptor提供哪些log被选定的信息。proposer通过把这个信息打包到Accept这个RPC里来做到这一点。所有的proposer的accept请求都带上他自己的firstUnchosenIndex值。换句话说,现在acceptor在收到proposer的accept rpc后,可以知道小于firstUnchosenIndex的所有log都是被选定的。所以acceptor可以利用这个信息来更新自己的log状态。我们通过例子来具体说明这个步骤。(译注:这页ppt的下半部分即是例子。为了更好地用文字说明,我把上图用紫蓝黄三色将例子分成三部分。三部分从上到下其实分别是在说明同一台acceptor上 收到Accept请求前、收到的Accept请求、收到Accept请求后的情形)。
假设我们有一个acceptor的log如紫色框所示。注意图中并没有展示每个log的value,而只是展示了log的index和acceptedProposal。根据我们上一页ppt中说的约定(提议号为无穷大即是标志为被选定),我们知道索引为1、2、3、5的log都是已经被选定的;而索引为4、6的两条log,proposal number并不是无限大,所以并不一定被选定了。
现在这个acceptor收到了一个accept rpc请求,请求详情如蓝色框所示。这个请求的proposal number是3.4,firstUnchosenIndex是7。这意味着,发起这个accept rpc的服务器确定,index为6及6以下的log全部都已经被选定。
acceptor使用这些信息的方式是,acceptor比较自己log中index<=6的所有未被选定的log,如果发现proposal number和3.4相等,就可以确定这个log肯定是被选定了!在这个例子中,index为6的log就符合了这个条件,所以确定这条log就是被选定了。所以可以将index为6的acceptedProposal标记成无穷大,即被选定。
为了理解为什么能这么做,我们思考下acceptor现在知道了什么信息。首先,因为proposal number是相等的,所以acceptor知道这条log的值是来自同一个proposer的(还记得proposal number的低bit是server id吗)。另外,acceptor根据firstUnchosenIndex可以知道,这个值proposer已经确定选定了。更进一步地,acceptor可以肯定proposer已经选定的值肯定和它上次提交的值一样,因为proposer提交的proposal number没有变!如果proposer上次提交的值没有被选定,那根据paxos的步骤,proposer是必然要变更自己的proposal number的。所以acceptor知道,自己存储的这个值肯定是被选定了。
因为同时,这个accept rpc还让acceptor接受index为8的log的值,所以acceptor仍需要根据paxos的步骤,设置index 8的值。所以我们最终得到黄色框的结果。
需要指出的是,做完这三步,我们仍没有完全解决问题。acceptor历史上可能收到一些来自其他proposer的请求。例如这里index为4的log,这个值是在更早时来自server 5的。当前情况下,acceptor无法确认这个值是否就是被选定的值。acceptor知道index为4的值是被选定了(proposer的firstUnchosenIndex为7说明了这一点),但acceptor无法确定自己的值是否就是被选定的值。
所以我们还需要最后一步。
4. 第四步就是为了确定acceptor之前从老的leaders(也就是老的proposer,因为引入leader后,就只有一个proposer了)接受了的,但未确定是否被选定的log。为了做到这一点,acceptor在处理完accept rpc后,会返回自己的firstUnchosenIndex给proposer。proposer会将acceptor返回的firstUnchosenIndex和自己的firstUnchosenIndex比较,如果发现自己的firstUnchosenIndex比acceptor大,那proposer就知道自己知道一些 acceptor不确定的东西了。proposer通过一个新的rpc将这些信息同步给acceptor,这个新的rpc就是Success rpc。这是除prepare和accept外的第三个rpc。Success rpc有两个参数:第一个是log的index,第二个是log的值。这个调用是告知acceptor一个信息:某个index的log的值已经被选定为值v了,不再有任何不确定性了。
proposer直接取出acceptor的firstUnchosenIndex对应的log的value,然后调用Success rpc,将这个信息同步给acceptor。acceptor也只需要简单地把这个index的值更新为新的值,并把proposal number置为无穷大,代表这个值已经被选定。然后acceptor更新自己的firstUnchosenIndex,并再次返回给proposer。根据acceptor返回的firstUnchosenIndex,proposer可能还要通过Success调用同步多轮数据给acceptor,直到acceptor的firstUnchosenIndex要大于等于proposer的为止。此时acceptor也就proposer所有确定的信息都同步过来了。
总结一下,我们通过这四个步骤就可以确保让所有的acceptor都最终得到所有的已经被选定的log值,并且也知道这些值确实已经被选定的事实。并且在普通的场景里边,并不需要额外的第四步来做到这一点,因为正常情况下,只需要Accept请求,就可以保证信息同步。只有在leader切换的短暂的时间里,才可能用到第四步这一额外的同步步骤。在所有server都同步了已当机的老leader的信息之后,就又不需要第四步了。
multi paxos的第四个问题就是client怎么和系统配合工作的问题。如果client知道哪台server是leader,那client就直接发送命令到这台server。如果client刚启动,并不知道谁是leader,那它可以给任何server发送命令,如果接收到命令字的server并不是leader,那这台server会返回leader的信息给client,让client把命令再发给leader。所以client最终总是能知道leader是谁。
leader收到这个命令后,leader就会为这个命令安排log位置,并尝试让其他acceptor都接受这个安排。等到log被确定下来后,leader会将此命令传给自己的状态机,状态机执行此命令,处理完毕后,leader会把状态机的执行结果返回给client。
client会一直把命令发给自己认定的leader,直到这个leader不再能工作为止,例如这个leader因为某些原因crash了。这时client的请求就会超时。这种情况下,client只需要随便挑一台server,重发这个命令即可。这就又进入了前面说到的情况:server不是leader的话,就会返回新leader的信息,client的请求会重定向到新的leader那里。client将请求给新的leader重发一遍后,最终这个请求会被成功处理。
但是,这里的重试可能会造成问题。万一leader是在执行这个命令之后,但在给client响应之前crash了,怎么办?这时如果client把命令又重新提交给新的leader,那就相当于这个命令被执行了两次。这是不可接受的,我们不允许这种情况发生,一个命令只能被执行一遍。
解决这个问题的方法是client发送命令时,要带上唯一的id。你可以将此id理解为将cilent id加上在client上递增的sequence id(类似proposal number的结构)。这个id会随着命令一起发送给server,而server会将此id和命令一起存储在log里边。而状态机在执行命令时,会跟踪保存每个client已经被执行过的最近的(也即最大的)id。当状态机被要求执行一条log里边的命令时,状态机会比较这个id,看是否自己已经执行过这个命令了,如果已经执行过,就忽略掉这个命令,返回上次执行此命令的结果。
这个方案的结果是,只要client不crash,这个系统对外就表现出“执行且只执行一次”的语意:一个client发出来的命令,即使重试,也只会被执行一次。但如果client crash了,那命令就有可能没被执行,或者被执行多次。
multi paxos相关的最后一个问题是配置变更。我这里说的系统配置,指的是参与到一致性协议过程中服务器的信息的变更,尤其是指:
1. 这些服务器的id、网络通信地址的变更
2. 另一个变更使得系统配置显得尤为重要:当系统配置中这些服务器信息变更时,一致性协议里边的大多数(majority)也可能发生了变化。比如将服务器数量由3台变更为5台,那大多数就有原先的2台变成3台。
有几个原因使得我们必须支持系统配置变更:
1.如果部分机器不再工作了,我们要用新机器替换他。
2.我们可能为了增强可靠性而需要改变机器的数量,比如从5台机器增加到7台机器。
配置变更如果涉及到对“大多数”这个值的变更时,会显得比较棘手。因为在变更过程中,我们仍要保持整个系统的安全特性(还记得我们在前面ppt里讲过的paxos的安全特性吗?安全特性要求:1.系统只能选定一个值;2.如果一台server根据算法得知一个值被选定了,那就是真的被选定了,永远不能改变)。
要做到这一点,我们要确保对于任何一条log,都不能有不同的“大多数”选定了不同的值。
举例说明一下我们会遇到的问题。假设系统中原先有三台server,现在增加两台server,变更成5台。假设因为某些原因,系统中一些server相信旧的系统配置(2台是大多数),而另一些相信新的配置(3台才是大多数)。那可能会发生这样的情况:左边的两台机器接受了值V1,右边三台机器接受了值V2;那么相信旧的系统配置的proposer会认为V1被选定了,而相信新的系统配置的proposer会认为V2被选定了。这就破坏了安全特性。
在兰伯特的paxos论文中对配置变更的建议解决方案是,使用log来管理配置变更。所以配置被当做一条log存储起来,并且也像其他普通log一样在各server中同步。以ppt中的图为例子,这里1、3两个log位置上存储了两组系统配置,而其他log位置则存储了普通log,即状态机需要执行的命令。
而这里一个有趣的技巧是,任何一条log用到的配置都必须是log位置在这条log之前的配置。至于到底之前多少,则取决于系统参数α。这里假设现在α是3,而图中我们有C1、C2两组配置,分别在index 1、3两个位置。这意味着C1这组配置,要到选定4这个位置的value时,才会被采用;而C2这组配置,要到选定6这个位置的value时,才会被采用。这也意味着,如果我们要选定1、2、3的value时,不能用C1这组配置,而只能用更前面的配置,这里我把它称之为C0配置。只有等到要选定4这个位置的value时,我们才能开始用配置C1。5这个位置的时候也用配置C1。但到了6这个位置以后,我们又要使用配置C2了。
需要指出的是,α这个值是在系统启动的时候就指定的一个系统参数。这个参数有一些有趣的特性。它的大小会限制我们在系统可以同时选定的log条数。在i这个位置的值被选定之前,我们不能选定i+α这个位置的值,因为我们不知道中间是否有配置变更。所以如果α值很小,假设就是1,那整个系统就只能是串行工作了,我们只能选定了上一个log的值,才能接着选定下一个log的值。如果α值是3,那意味着我们可以同时选定3个位置的值,因为我们知道即使有配置变更,在选定这三个位置的value时也是不生效的。但如果我们把α值定得非常大,那事情就开始复杂了。例如我们把α值定成1000,那我们在配置变更后,要等好一阵子,一直到配置所在位置之后的1000条log都被确定后,我们的配置才会开始生效。为了迫使我们的配置更快的生效,我们可以产生一些no-op指令来填充log,让log迅速达到需要的条数,而不用一直等着client的命令。
总结一下关于配置变更的处理方法,其实非常简单:我们把配置作为一条普通log一样存储和同步,然后我们就等待系统在一定的条数log后采用我们的新配置。
这里重新列了下这次课的内容。让我们总结一下这次paxos的课都覆盖了哪些内容。
首先,我覆盖到了basic paxos,这是你可能想象的最简单形式的一致性问题:多台server如何就一个值达成一致意见。记住,他使用了非常重要的两阶段方法:使用prepare阶段来找出已经被选定的值,并且阻止了其他的提议;然后使用Accept阶段来完成整个过程。
然后,我描述了怎么让一组basic paxos实例一起配合工作,来选定一系列的log。我讲了怎么选定一个log位置。接着讲了两个可以提升paxos效率的方法。在实际系统中我们并不完全照搬选定单个值的basic paxos,而是通过leader选举来减少这里的竞争;我们通过锁定整个log的方式来移除大部分prepare请求。我还讲到了怎么才能让所有的server都最终得到完整的信息。
我讲到了client应该怎么系统交互,这里的关键点在于,client在发送请求时,带上一个唯一的id,状态机在执行这些命令时,根据这些id来确保一条命令自己只执行一遍。
最后,我讲了如何处理配置变更。通过将配置记录到log里边,根据系统参数α,系统在确定每个log的值时都知道应该使用什么配置。
感谢大家的参与,希望这个讲解可以让你对paxos多了解一点。
原文链接:http://v.youku.com/v_show/id_XNjgyODc3ODU2.html
原文作者:翻译自视频
来源: https://cloud.tencent.com/developer/article/1158799