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生效就会需要等待很长时间。

,