用paxos实现多副本日志系统--multi paxos部分

上篇 basic paxos : https://cloud.tencent.com/developer/article/1147420

接下来，我们来讲解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多了解一点。