转载

一致性算法 Paxos Raft 的一些整理

这个文章主要是对一致性问题中的经典的几个问题做一些记录，算是边学习边整理，包括 paxos算法，raft算法，还有拜占庭问题等等，主要是介绍算法的一些背景和基本原理。

Consensus是什么

一致性是容错性分布系统中需要考虑的一个基本问题。一致性涉及到多个服务对value值达成一致的问题。一旦多个server对某个value的值达成一致，这个决定就会被最终确定下来。典型的一致性算法通常在集群中的大部分节点都正常工作的时候才会起到作用。比如一个包含5个服务节点的集群，如果其中有两个服务节点失败了，这个集群仍然可以正常工作。如果有更多的服务节点失败，这个集群就无法继续正常工作。

一致性问题在replicated state machine的相关场景中会比较典型，这是一个构建容错系统的常见的方式。每一个服务节点都有一个state machine以及一个log。state machine是我们想要让其有容错功能的组件，最简单的比如像hash table（有一个input 还有 output）。在client端看来，它再与一个单独的稳定的single machine进行交互，但实际上这个抽象的single machine是有许多具体的server中的state machine进构成的。每一个state machine 从log中来读取输入值。在我们hash table的例子中，log可能会是如下的一些命令，比如将x的值设置为3。通过一致性的算法可以保证不同server中所存储的log是相同的。一致性算法必须能够保证：如果有一个state machine把 set x to 3 这条命名作为了第n条命令，那集群中其它的state machine 的第n条命令也必须要有相同的操作而不可以是其他操作。所以，每一个state machine都处理着相同的command 序列，这样就会产生有同样状态的同样结果序列。

paxos相关

Paxos算法是莱斯利·兰伯特（Leslie Lamport，就是 LaTeX 中的"La"，此人现在在微软研究院）于1990年提出的一种基于消息传递的一致性算法。这个算法被认为是类似算法中最有效的。号称分布式系统的基石，系统容错。十分巧妙，又比较难以理解。

引入的游戏背景：希腊岛屿Paxon 上的执法者（legislators，后面称为牧师priest）在议会大厅（chamber）中表决通过法律，并通过服务员传递纸条的方式交流信息，每个执法者会将通过的法律记录在自己的账目（ledger）上。问题在于执法者和服务员都不可靠，他们随时会因为各种事情离开议会大厅，并随时可能有新的执法者（或者是刚暂时离开的）回到议会大厅进行法律表决，使用何种方式能够使得这个表决过程正常进行，且通过的法律不发生矛盾。

解决什么问题

如何确定一个不可变变量的取值：值可以是任意的二进制的数据。一旦确定，将不再会被更改。

管理多个propser并发执行在分布式系统中使用paxos

数据本身可变采用多副本进行存储
多个副本的更新操作（op1 op2 op3 …）保证所有的副本每次的更新序列都是相同的以此来保证一致性
每次确定完opi之后让各个数据副本执行opi 以此类推

Google 的 chubby

paper中把一致性问题描述为游戏场景

2 与分布式存储系统的关系

3 核心思想？第一个阶段做什么第二个阶段做什么

确定不可变变量取值的三个方案

问题背景：

如何确定一个不可变变量的取值，就是在分布式系统中，多个节点，如何就某个值，或者决议达成一致。说是paxos算法，更不如说是paxos协议。

参与者的身份：一组可以提出value的process，每个processor可以提出一个value，还有一组可以接受value的acceptor，如果某个value被接受，就称这个value被chosen。

解决思路：在多副本存储的情况下，要保证每个节点（多个副本）更新状态的时候，所执行的一系列更新操作序列： op1、op2、op3。。。是相同的。使用paxos算法的主要目的就是确定不可变变量opi的取值。每确定好opi之后，可以让系统副本去执行对应的opi。

要求：

满足一致性：当变量的取值没有确定的时候，则var的取值为null，一旦var的取值被 确定下来 ，则不可以再被更改，并且可以一直获取到这个值。
容错特性，容忍proposer出现故障，容忍少数acceptor出现故障（半数以下的）

方案一

基本方式：

最简单的场景，考虑单个acceptor，通过互斥锁的方式，来管理多个proposer。proposer向acceptor发申请acceptor的互斥访问权，哪个proposer申请到访问的权限，就可以和acceptor通信，acceptor就可以接受对应的取值。具体实现：

acceptor {      var       lock }  prepare() //申请访问权限 给予var的互斥访问权限 返回var当前的取值f   release（） //释放互斥锁 收回var的访问权限 如果var已加锁  accept(var,v) //如果当前访问者已经获取到锁权限 并且var没有取值 则var值设置为v 释放锁

propose实现的函数

proposer 通过 propose<var,v> 来向系统提交变量的取值，希望把系统中var变量的值 设置为 v 。通过两个阶段来实现：  propose<var,v>     - 通过 Acceptor::prepare来获取互斥访问权，以及当前的var的值，如互斥锁已经被占用，则返回error。   - 根据var的取值f 来确定执行流程      若f为null 说明没有设置历史值 需要由 acceptor（var,v） 来提交数据     若f不为null 说明已经设置好了值 不可再更改 由release释放访问权 返回<ok,f>

总结

通过互斥访问的权限来让proposer按照获取互斥访问权的顺序序列运行
如果proposer在获取到互斥访问权但是还没有实现互斥访问权的时候，发生了故障，会导致其它的所有proposer都无法获取互斥访问权。系统陷入死锁，无法满足之前提出的一致性的要求。
此方案无法容忍任意proposer出现故障。

方案二

基本方式

为了解决方案一所带来的死锁的问题，方案二引入了访问权限失效的方式。acceptor通过某种机制可以让某个proposer的访问权限失效。

acceptor与processor都多添加一个字段：epoch，processor向acceptor提交值的时候，会指定一个epoch（比如使用实践戳）如果epoch的值越大，说明processor越新。而acceptor则采用喜新厌旧的方法，收到更大的epoch申请之后，就会让就旧的epoch值的processor访问权限失效。因此 新的epoch可以抢占旧的epoch的访问权限。

在值更新方面，带有新epoch的processor采用 后者认同前者 的思路。只有在确认旧的epoch无法生成新的确定性取值的之后，新的epoch才会更新value取值，不会造成值的冲突。在携带旧的epoch的processor形成确定性取值之后（即使发生了故障），携带有新的epoch的processor可以获取到这个取值，并且会认同这个取值，不再更新。

函数流程

Acceptor { //存储已经接受的value以及 提出这个value的proposer的epoch var <accepted_epoch,accepted_value> //获取到最新的访问权的proposer的epoch (latest prepared epoch) epoch  }  prepare(epoch)   //携带此epoch的proposer申请访问权   - 只接收比 latest_prepared_epoch 更大的epoch的访问 并且给予对应的访问权   - 更新 latest_prepared_epoch 为当前最新的epoch 并且返回当前的 var 的取值  accept(var,prepared_epoch,v)   // 让acceptor接受此 prepared_epoch的取值 v   - 验证 latest_prepared_epoch=prepared_epoch      看当前提交的这个是否为自己发放访问权的哪一个，如果是的话，执行更新操作     <accepted_epoch,accepted_value>=<prepared_epoch,v>   - 如果不是 说明已经有一个携带更大epoch的proposer获取到了访问权     当前这个proposor的访问权已经失效

下面看一下propose方法的运行状况，仍然需要两个阶段。

propose<var,v>    - 比如选取时间戳作为epoch，通过prepare(epoch)获取访问权限      若不能获取（已经有相同的或者更大的epoch的proposer抢占到了访问权）返回error,若获取到则返回<ok,f>。    - 后者认同前者的原则      第一阶段获取到到的f值为null，历史上旧的epoch没有设置好确定性值，      通过accept<var,epoch,v>提交数据v，若成功则返回<ok,v>，若失败，说明已经被抢占，或者acceptor故障，返回error。      第一阶段获取到的f值不为null，历史上已经设置成功了确定性取值，不再执行更改，直接认同，返回<ok,accepted_value>。

总结

proposer按照epoch递增的顺序抢占式的获取锁资源，避免死锁问题。
采用后者认同前者的思路
只有一个acceptor，当acceptor出现故障，无法继续运行。

方案三（完整paxos方法）

基本方式

在方案二的基础上引入了多个acceptor,acceptor保持不变，仍然采用喜新厌旧的方式运行. 采用少数服从多数的思路：一旦携带有某epoch的proposer设置的取值被半数以上的acceptor接受，则认为此var的取值被确定为f，不再更改

函数流程

propose（var,v）   - 确定epoch 轮次地访问多个acceptor的prepare(epoch)的方法 获取访问权限 acceptor仍是采用对epoch的喜新厌旧的抢占方式     直到获取到半数以上的acceptor的访问权限 以及对应的一组var值。   - 符合要求的proposer进入第二阶段 采用后者认同前者的思路 （旧的epoch的proposer形成确定性取值和没形成确定性取值的两个操作）      - 当第一阶段获取到的var的取值为null，旧的epoch，无法形成确定性取值 ，此proposer努力使         自己提出的value形成确定性取值，向所有的acceptor提交请求：accept(var,epoch,value)如果有半数以上的acceptor返回成功，则方法返回<   ok , value>         否则返回error (acceptor被其他proposer抢占)           - 当第一阶段获取到的var值不为null         - 如果这个f是半数以上的acceptor所返回的,说明f已经是确定性取值了，直接返回<ok，f>         - 若f是半数以下 f可能是确定性取值 也可能不是 此时的 proposor会向所有的acceptor提交 accept<var,epoch,f>相当于认同了这个f为确定性取值，并且重新提交一次。

总结

核心思想思考列表

在抢占式访问权的基础上引入多个acceptor 保证只有一个epoch 只有一个 proposer运行 proposer按照epoch递增的顺序一次运行新的epoch的proposer采用“后者认同前者”的思路运行：

在肯定旧的epoch的proposer无法生成确定性取值的时候新的epoch就会提交自己的取值不会冲突
一旦旧的epoch形成确定性取值新的epoch肯定可以获得到此取值并且会认同此取值不会破坏

容错性要求

半数以下的acceptor出现故障的时候存活的acceptor仍然可以生成var的确定性取值一旦var的值被确定即使出现了半数以下的acceptor故障此取值就可以被获取并且不再被改变

活锁问题

新的轮次会导致旧的轮次的停止运行，如果每一轮次在第二阶段执行成功之前都被新的一轮所抢占，则会导致活锁问题，应该如何解决？

raft相关

问题的起源与背景

在最开始的时候已经对一致性问题有了基本的解释，具体的motivation与paxos是一样的，都是为了解决一致性问题而引入的。通俗一点，就是一个client要给一个节点的server赋值，那很容易。但是一个client要给一个多个节点的server赋值，每个server的值都要保证一致，那么这要怎么做,这就是所谓的分布式系统中的一致性的问题？

下面记录的主要内容都是来自这个： http://thesecretlivesofdata.com/raft/ 很生动地展示了整个算法的过程，并且一步一步循序渐进。

算法的大致描述框架 high level

几个基本状态

Follower 所有节点在最初的时候都是follower，顾名思义，follower所采取的行为也是被动的，就是被动接受其他节点传递过来的心跳信息。

Candidate 如果Follower节点在一定的时间段内没有接收到Leader节点传递过来的心跳信息，那么可以认为Leader节点有问题或者已经crash，那么它的身份就会转化成Candidate，要选一个新的Leader出来。之后candidate节点就会给其他节点发请求，要求它们给自己投票，之后其他节点会返回它们的投票信息。

Leader 如果一个candidate收到了大部分节点的投票，它就会称为一个新的leader节点。由follower->candidate->leader的身份转变实际上是一个leader election的最常见过程，选出leader的目的是，要求所有对于系统的改变的操作都要通过Leader来进行。

具体的状态转换可以结合具体算法过程的描述，同时参考这个

几个过程

Leader Election (偶数个节点容易发生split up 平均分的场景)

基本背景就像前面所说的那样，在leader election 中涉及到两个time

election timeout 是follower节点等待成为candidate节点的时间，或者是说在这段时间内，会等待leader节点给他发送心跳请求。这个时间是一个随机值，在150-300ms之间，由于是随机值，每个节点等待的时间是不一样的，所以可能有一个节点先达到了等待时间，之后这个节点就变成了candidate节点。
heartbeat timeout 当某个节点变成了candidate节点之后，一次新的竞选就开始了，就进入了这一轮的election term，首先这个节点的termid会+1，之后会投票给自己，然后给其他所有的节点发送请求（Vote Request Messages），让它们来投票。如果收到Vote Request Message请求的节点在这一轮（term）还没有进行投票，那么它们就给这个candidate节点投票， 并且会重置它们的election time (因为已经有节点称为candiadte了，其他的节点只需要继续保持follower身份就好了)，如果已经投过了票，就会拒接请求。如果candidate节点接收到的请求超过了半数（超过半数的原因是为了保证一个term中只有一个leader被选出来）,它的身份就会转变，称为leader节点。成为leader节点之后，就会发送Append Entries Messages心跳信息给所有的followers，follower节点收到心跳信息后也会返回对应的信息。

注意，follower节点每次收到新的append entries请求就会重置自己的election time 表示其持续保持自己的follower身份。发送心跳信息的时间间隔是可以指定的，这个就是第二个时间，即heartbeat timeout。这个election term会一直持续下去，直到follower在election time到期之前仍没有收到来自leader的heart beat请求，这样就会变成新的candidator开始下一轮election。

注意一下，由于raft中节点数目的这种信息是declaration的，不是dynamic的，因此有节点down了之后应该快速修复（比如某个follower虽然down了，但是leader还是会给它发送 Append Entries Messages）。

在election中的split vote 场景

上面分析的都是一般情况，在实际中，很有可能一次出现了两个candidator节点，它们的election time同时到期了。并且投票之后票数都是相同的（肯定小于半数），这个时候就会等待，直到另外一个新的candidator出现，在进行election 操作，所谓河蚌相争，渔翁得利。

Log Replicaiton

一旦leader选出来之后，其他的节点需要和leader节点保持同步，leader节点需要把在它上面发生的改变传递到系统中其他所有的节点上去。

先来看下抽象出来的server的 数据结构 ：每一个server由一个state machine以及一个log构成，state machine就像我们在最开始介绍的那样，是一个有状态的，可以接受input并且产生output的app。log由一系列的entry构成，每个entry有两个字段，一个存放具体的command，一个存放termid表示当前是第几次进行竞选。

首先client会给leader节点发信息，对其发送一些命令，比如发送了一个set命令过去。这个command会被appended到leader的log字段上面（ 此时这个值的状态是uncommited ）。

之后leader会把这个node的值replica到其他的节点上，具体传递的方式是在心跳信息上面携带相关的信息。直到大部分的节点都log中添加了对应的entry，之后leader节点就会commit当前的这个值，对应的entry的修改就算确定下来了。接着leader节点会通知其他的所有节点，告诉它们要commit这个值，这样，整个集群对与这个值的修改就达成了一致。之后leader节点就可以执行对应的操作，比如把command输入到state machine中并把结果返回给client。

由于每一个节点都有可能成为leader因此每个节点应该都具有相同的执行能力，这里的关键是维持一个一致的replica log比如在etcd中，replica log可以理解为具体对于etcd的操作，而state machine就是实际存储的key-value键值表。

在发生网络分区问题的时候（network partition）

这个用语言表述真的是不太容易，这就是为啥视频上的课程看起来难以理解，实际上比较容易，强烈建议参考 http://thesecretlivesofdata.com/raft/ 上面的讲解。实际上term_id的作用就在这里。当有多个leader的时候，leader收到其他leader发送过来的心跳信号，会把自己的term_id也发过去，反过来，如果某个leader发现，其他leader的term_id比自己的要高，那么这个leader就会自动转变为follower节点。

比较常见的例子：一个有5个节点的集群 a b c d e，原先的时候a是leader term是1,发生了network partition之后，比如a b 在一个网段，c d e在另一个网段。之后client对a发送请求，当 a replica log的时候，没法获得半数以上的节点的认同(默认的还是5个节点)，这个时候它们的term _ id都是1，并且log都是uncommited的，在另一个网段，由于一直没有接受到leader的心跳信息，eleciton timeout到期时候会产生一个新的leader这个leader的term会变为2（由于有3个节点在这个网段，投票可以超过半数）。之后另个一client向新的leader发信息，进行更新操作，更新成功， c d e 都接受了第二个命令。它们的term _ id都会变为2。之后如果partition取消，两个leader会发送heart beat 信号，term小的leader会放弃自己的leader权限，并且回滚 uncommitted value，之后与term最大的那个master节点保持同步。之后所有的节点又同步了。

可以看到，从解决方式上看，这里的commit的过程还是two-phase的，就是第一次形成值之后还可以在根据其他条件进行对应的更改，这个条件就是term_id，如果有多个id的时候，term小的id会自动同步到term较大的id上去，可以实现roll back uncommitted value的机制。