分类目录归档:consensus

Paxos

Paxos算法在分布式领域具有非常重要的地位。但是Paxos算法有两个比较明显的缺点:1.难以理解 2.工程实现更难。

网上有很多讲解Paxos算法的文章,但是质量参差不齐。看了很多关于Paxos的资料后发现,学习Paxos最好的资料是论文《Paxos Made Simple》,其次是中、英文版维基百科对Paxos的介绍。本文试图带大家一步步揭开Paxos神秘的面纱。

Paxos是什么

Paxos算法是基于消息传递且具有高度容错特性一致性算法,是目前公认的解决分布式一致性问题最有效的算法之一。

Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法,那就是Paxos,其它的算法都是残次品

虽然Mike Burrows说得有点夸张,但是至少说明了Paxos算法的地位。然而,Paxos算法也因为晦涩难懂而臭名昭著。本文的目的就是带领大家深入浅出理解Paxos算法,不仅理解它的执行流程,还要理解算法的推导过程,作者是怎么一步步想到最终的方案的。只有理解了推导过程,才能深刻掌握该算法的精髓。而且理解推导过程对于我们的思维也是非常有帮助的,可能会给我们带来一些解决问题的思路,对我们有所启发。

问题产生的背景

在常见的分布式系统中,总会发生诸如机器宕机网络异常(包括消息的延迟、丢失、重复、乱序,还有网络分区)等情况。Paxos算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中,快速且正确地在集群内部对某个数据的值达成一致,并且保证不论发生以上任何异常,都不会破坏整个系统的一致性。

注:这里某个数据的值并不只是狭义上的某个数,它可以是一条日志,也可以是一条命令(command)。。。根据应用场景不同,某个数据的值有不同的含义。

相关概念

在Paxos算法中,有三种角色:

  • Proposer
  • Acceptor
  • Learners

在具体的实现中,一个进程可能同时充当多种角色。比如一个进程可能既是Proposer又是Acceptor又是Learner

还有一个很重要的概念叫提案(Proposal)。最终要达成一致的value就在提案里。

注:

  • 暂且认为『提案=value』,即提案只包含value。在我们接下来的推导过程中会发现如果提案只包含value,会有问题,于是我们再对提案重新设计
  • 暂且认为『Proposer可以直接提出提案』。在我们接下来的推导过程中会发现如果Proposer直接提出提案会有问题,需要增加一个学习提案的过程。

Proposer可以提出(propose)提案;Acceptor可以接受(accept)提案;如果某个提案被选定(chosen),那么该提案里的value就被选定了。

回到刚刚说的『对某个数据的值达成一致』,指的是Proposer、Acceptor、Learner都认为同一个value被选定(chosen)。那么,Proposer、Acceptor、Learner分别在什么情况下才能认为某个value被选定呢?

  • Proposer:只要Proposer发的提案被Acceptor接受(刚开始先认为只需要一个Acceptor接受即可,在推导过程中会发现需要半数以上的Acceptor同意才行),Proposer就认为该提案里的value被选定了。
  • Acceptor:只要Acceptor接受了某个提案,Acceptor就任务该提案里的value被选定了。
  • Learner:Acceptor告诉Learner哪个value被选定,Learner就认为那个value被选定。

问题描述

假设有一组可以提出(propose)value(value在提案Proposal里)的进程集合。一个一致性算法需要保证提出的这么多value中,只有一个value被选定(chosen)。如果没有value被提出,就不应该有value被选定。如果一个value被选定,那么所有进程都应该能学习(learn)到这个被选定的value。对于一致性算法,安全性(safaty)要求如下:

  • 只有被提出的value才能被选定。
  • 只有一个value被选定,并且
  • 如果某个进程认为某个value被选定了,那么这个value必须是真的被选定的那个。

我们不去精确地定义其活性(liveness)要求。我们的目标是保证最终有一个提出的value被选定。当一个value被选定后,进程最终也能学习到这个value。

Paxos的目标:保证最终有一个value会被选定,当value被选定后,进程最终也能获取到被选定的value。

假设不同角色之间可以通过发送消息来进行通信,那么:

  • 每个角色以任意的速度执行,可能因出错而停止,也可能会重启。一个value被选定后,所有的角色可能失败然后重启,除非那些失败后重启的角色能记录某些信息,否则等他们重启后无法确定被选定的值。
  • 消息在传递过程中可能出现任意时长的延迟,可能会重复,也可能丢失。但是消息不会被损坏,即消息内容不会被篡改(拜占庭将军问题)。

推导过程

最简单的方案——只有一个Acceptor

假设只有一个Acceptor(可以有多个Proposer),只要Acceptor接受它收到的第一个提案,则该提案被选定,该提案里的value就是被选定的value。这样就保证只有一个value会被选定。

但是,如果这个唯一的Acceptor宕机了,那么整个系统就无法工作了!

因此,必须要有多个Acceptor

多个Acceptor

多个Acceptor的情况如下图。那么,如何保证在多个Proposer和多个Acceptor的情况下选定一个value呢?

下面开始寻找解决方案。

如果我们希望即使只有一个Proposer提出了一个value,该value也最终被选定。

那么,就得到下面的约束:

P1:一个Acceptor必须接受它收到的第一个提案。

但是,这又会引出另一个问题:如果每个Proposer分别提出不同的value,发给不同的Acceptor。根据P1,Acceptor分别接受自己收到的value,就导致不同的value被选定。出现了不一致。如下图:

刚刚是因为『一个提案只要被一个Acceptor接受,则该提案的value就被选定了』才导致了出现上面不一致的问题。因此,我们需要加一个规定:

规定:一个提案被选定需要被半数以上的Acceptor接受

这个规定又暗示了:『一个Acceptor必须能够接受不止一个提案!』不然可能导致最终没有value被选定。比如上图的情况。v1、v2、v3都没有被选定,因为它们都只被一个Acceptor的接受。

最开始讲的『提案=value』已经不能满足需求了,于是重新设计提案,给每个提案加上一个提案编号,表示提案被提出的顺序。令『提案=提案编号+value』。

虽然允许多个提案被选定,但必须保证所有被选定的提案都具有相同的value值。否则又会出现不一致。

于是有了下面的约束:

P2:如果某个value为v的提案被选定了,那么每个编号更高的被选定提案的value必须也是v。

一个提案只有被Acceptor接受才可能被选定,因此我们可以把P2约束改写成对Acceptor接受的提案的约束P2a。

P2a:如果某个value为v的提案被选定了,那么每个编号更高的被Acceptor接受的提案的value必须也是v。

只要满足了P2a,就能满足P2。

但是,考虑如下的情况:假设总的有5个Acceptor。Proposer2提出[M1,V1]的提案,Acceptor2~5(半数以上)均接受了该提案,于是对于Acceptor2~5和Proposer2来讲,它们都认为V1被选定。Acceptor1刚刚从宕机状态恢复过来(之前Acceptor1没有收到过任何提案),此时Proposer1向Acceptor1发送了[M2,V2]的提案(V2≠V1且M2>M1),对于Acceptor1来讲,这是它收到的第一个提案。根据P1(一个Acceptor必须接受它收到的第一个提案。),Acceptor1必须接受该提案!同时Acceptor1认为V2被选定。这就出现了两个问题:

  1. Acceptor1认为V2被选定,Acceptor2~5和Proposer2认为V1被选定。出现了不一致。
  2. V1被选定了,但是编号更高的被Acceptor1接受的提案[M2,V2]的value为V2,且V2≠V1。这就跟P2a(如果某个value为v的提案被选定了,那么每个编号更高的被Acceptor接受的提案的value必须也是v)矛盾了。

所以我们要对P2a约束进行强化!

P2a是对Acceptor接受的提案约束,但其实提案是Proposer提出来的,所有我们可以对Proposer提出的提案进行约束。得到P2b:

P2b:如果某个value为v的提案被选定了,那么之后任何Proposer提出的编号更高的提案的value必须也是v。

由P2b可以推出P2a进而推出P2。

那么,如何确保在某个value为v的提案被选定后,Proposer提出的编号更高的提案的value都是v呢?

只要满足P2c即可:

P2c:对于任意的N和V,如果提案[N, V]被提出,那么存在一个半数以上的Acceptor组成的集合S,满足以下两个条件中的任意一个:

  • S中每个Acceptor都没有接受过编号小于N的提案。
  • S中Acceptor接受过的最大编号的提案的value为V。

Proposer生成提案

为了满足P2b,这里有个比较重要的思想:Proposer生成提案之前,应该先去『学习』已经被选定或者可能被选定的value,然后以该value作为自己提出的提案的value。如果没有value被选定,Proposer才可以自己决定value的值。这样才能达成一致。这个学习的阶段是通过一个『Prepare请求』实现的。

于是我们得到了如下的提案生成算法

  1. Proposer选择一个新的提案编号N,然后向某个Acceptor集合(半数以上)发送请求,要求该集合中的每个Acceptor做出如下响应(response)。

(a) 向Proposer承诺保证不再接受任何编号小于N的提案

(b) 如果Acceptor已经接受过提案,那么就向Proposer响应已经接受过的编号小于N的最大编号的提案

我们将该请求称为编号为NPrepare请求

  1. 如果Proposer收到了半数以上的Acceptor的响应,那么它就可以生成编号为N,Value为V的提案[N,V]。这里的V是所有的响应中编号最大的提案的Value。如果所有的响应中都没有提案,那 么此时V就可以由Proposer自己选择
    生成提案后,Proposer将该提案发送给半数以上的Acceptor集合,并期望这些Acceptor能接受该提案。我们称该请求为Accept请求。(注意:此时接受Accept请求的Acceptor集合不一定是之前响应Prepare请求的Acceptor集合)

Acceptor接受提案

Acceptor可以忽略任何请求(包括Prepare请求和Accept请求)而不用担心破坏算法的安全性。因此,我们这里要讨论的是什么时候Acceptor可以响应一个请求。

我们对Acceptor接受提案给出如下约束:

P1a:一个Acceptor只要尚未响应过任何编号大于NPrepare请求,那么他就可以接受这个编号为N的提案

如果Acceptor收到一个编号为N的Prepare请求,在此之前它已经响应过编号大于N的Prepare请求。根据P1a,该Acceptor不可能接受编号为N的提案。因此,该Acceptor可以忽略编号为N的Prepare请求。当然,也可以回复一个error,让Proposer尽早知道自己的提案不会被接受。

因此,一个Acceptor只需记住:1. 已接受的编号最大的提案 2. 已响应的请求的最大编号。

Paxos算法描述

经过上面的推导,我们总结下Paxos算法的流程。

Paxos算法分为两个阶段。具体如下:

  • 阶段一:

(a) Proposer选择一个提案编号N,然后向半数以上的Acceptor发送编号为N的Prepare请求

(b) 如果一个Acceptor收到一个编号为N的Prepare请求,且N大于该Acceptor已经响应过的所有Prepare请求的编号,那么它就会将它已经接受过的编号最大的提案(如果有的话)作为响应反馈给Proposer,同时该Acceptor承诺不再接受任何编号小于N的提案

  • 阶段二:

(a) 如果Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应,那么它就会发送一个针对[N,V]提案Accept请求半数以上的Acceptor。注意:V就是收到的响应编号最大的提案的value,如果响应中不包含任何提案,那么V就由Proposer自己决定

(b) 如果Acceptor收到一个针对编号为N的提案的Accept请求,只要该Acceptor没有对编号大于NPrepare请求做出过响应,它就接受该提案

Learner学习被选定的value

Learner学习(获取)被选定的value有如下三种方案:

如何保证Paxos算法的活性

通过选取主Proposer,就可以保证Paxos算法的活性。至此,我们得到一个既能保证安全性,又能保证活性分布式一致性算法——Paxos算法

参考资料

  • 论文《Paxos Made Simple》
  • 论文《The Part-Time Parliament》
  • 英文版维基百科的Paxos
  • 中文版维基百科的Paxos
  • 书籍《从Paxos到ZooKeeper》

 

原文:

https://www.cnblogs.com/linbingdong/p/6253479.html

 

... END ...

 

Raft算法

过去, Paxos一直是分布式协议的标准,但是Paxos难于理解,更难以实现,Google的分布式锁系统Chubby作为Paxos实现曾经遭遇到很多坑。

来自Stanford的新的分布式协议研究称为Raft,它是一个为真实世界应用建立的协议,主要注重协议的落地性和可理解性。

在了解Raft之前,我们先了解Consensus一致性这个概念,它是指多个服务器在状态达成一致,但是在一个分布式系统中,因为各种意外可能,有的服务器可能会崩溃或变得不可靠,它就不能和其他服务器达成一致状态。这样就需要一种Consensus协议,一致性协议是为了确保容错性,也就是即使系统中有一两个服务器当机,也不会影响其处理过程。

为了以容错方式达成一致,我们不可能要求所有服务器100%都达成一致状态,只要超过半数的大多数服务器达成一致就可以了,假设有N台服务器,N/2 +1 就超过半数,代表大多数了。

Paxos和Raft都是为了实现Consensus一致性这个目标,这个过程如同选举一样,参选者需要说服大多数选民(服务器)投票给他,一旦选定后就跟随其操作。Paxos和Raft的区别在于选举的具体过程不同。

在Raft中,任何时候一个服务器可以扮演下面角色之一:

  1. Leader: 处理所有客户端交互,日志复制等,一般一次只有一个Leader.
  2. Follower: 类似选民,完全被动
  3. Candidate候选人: 类似Proposer律师,可以被选为一个新的领导人。

Raft阶段分为两个,首先是选举过程,然后在选举出来的领导人带领进行正常操作,比如日志复制等。下面用图示展示这个过程:

1. 任何一个服务器都可以成为一个候选者Candidate,它向其他服务器Follower发出要求选举自己的请求:

2. 其他服务器同意了,发出OK。

注意如果在这个过程中,有一个Follower当机,没有收到请求选举的要求,因此候选者可以自己选自己,只要达到N/2 + 1 的大多数票,候选人还是可以成为Leader的。

3. 这样这个候选者就成为了Leader领导人,它可以向选民也就是Follower们发出指令,比如进行日志复制。

4. 以后通过心跳进行日志复制的通知

5. 如果一旦这个Leader当机崩溃了,那么Follower中有一个成为候选者,发出邀票选举。

6. Follower同意后,其成为Leader,继续承担日志复制等指导工作:

 

值得注意的是,整个选举过程是有一个时间限制的,如下图:

Splite Vote是因为如果同时有两个候选人向大家邀票,这时通过类似加时赛来解决,两个候选者在一段timeout比如300ms互相不服气的等待以后,因为双方得到的票数是一样的,一半对一半,那么在300ms以后,再由这两个候选者发出邀票,这时同时的概率大大降低,那么首先发出邀票的的候选者得到了大多数同意,成为领导者Leader,而另外一个候选者后来发出邀票时,那些Follower选民已经投票给第一个候选者,不能再投票给它,它就成为落选者了,最后这个落选者也成为普通Follower一员了。

 

日志复制

下面以日志复制为例子说明Raft算法,假设Leader领导人已经选出,这时客户端发出增加一个日志的要求,比如日志是"sally":

2. Leader要求Followe遵从他的指令,都将这个新的日志内容追加到他们各自日志中:

3.大多数follower服务器将日志写入磁盘文件后,确认追加成功,发出Commited Ok:

4. 在下一个心跳heartbeat中,Leader会通知所有Follwer更新commited 项目。

对于每个新的日志记录,重复上述过程。

如果在这一过程中,发生了网络分区或者网络通信故障,使得Leader不能访问大多数Follwers了,那么Leader只能正常更新它能访问的那些Follower服务器,而大多数的服务器Follower因为没有了Leader,他们重新选举一个候选者作为Leader,然后这个Leader作为代表于外界打交道,如果外界要求其添加新的日志,这个新的Leader就按上述步骤通知大多数Followers,如果这时网络故障修复了,那么原先的Leader就变成Follower,在失联阶段这个老Leader的任何更新都不能算commit,都回滚,接受新的Leader的新的更新。

总结:目前几乎所有语言都已经有支持Raft算法的库包,具体可参考:raftconsensus.github.io

 

原文:

https://www.jdon.com/artichect/raft.html

 

... END ...

 

分布式事务与一致性算法 paxos & raft & zab

..

1.CAP原理

  • 要想数据高可用,就得写多份数据
  • 写多分数据就会导致数据一致性问题
  • 数据一致性问题会引起性能问题

2.一致性模型

  1. 弱一致性
  2. 最终一致性(一段时间达到一致性)
  3. 强一致
  • 1、2 异步冗余;3是同步冗余

3. 扩展服务的方案

  • 数据分区: uid % 16
  • 数据镜像:让多有的服务器都有相同的数据,提供相当的服务(冗余存储,一般3份为好)

4.两种方案的事务问题

  1. A向B汇钱,两个用户不在一个服务器上
  2. 镜像:在不同的服务器上对同一数据的写操作如何保证一致性。

5. 解决一致性事务问题的技术

1. Master -Slave

  • 读写请求由Master负责
  • 写请求写到Master后,由Master同步到Slave上
    • 由Master push or Slave pull
    • 通常是由Slave 周期性来pull,所以是最终一致性

问题: 若在 pull 周期内(不是期间?),master挂掉,那么会导致这个时间片内的数据丢失

  • 若不想让数据丢掉,Slave 只能成为 ReadOnly方式等Master恢复
  • 若容忍数据丢失,可以让 Slave代替Master工作

如何保证强一致性?

  • Master 写操作,写完成功后,再写 Slave,两者成功后返回成功。若 Slave失败,两种方法
    1. 标记 Slave 不可用报错,并继续服务(等恢复后,再同步Master的数据,多个Slave少了一个而已)
    2. 回滚自己并返回失败

2. Master-Master

  • 数据同步一般是通过 Master 间的异步完成,所以是最终一致
  • 好处: 一台Master挂掉,另外一台照样可以提供读写服务。当数据没有被赋值到别的Master上时,数据会丢失。
  • 对同一数据的处理问题:Dynamo的Vector Clock的设计(记录数据的版本号和修改者),当数据发生冲突时,要开发者自己来处理

3.两阶段提交 Two Phase Commit _ 2PC

  1. 第一阶段:针对准备工作
    • 协调者问所有节点是否可以执行提交
    • 参与者开始事务,执行准备工作:锁定资源(获取锁操作)
    • 参与者响应协调者,如果事务的准备工作成功,则回应"可以提交",否则,拒绝提交
  2. 第二阶段:
    • 若都响应可以提交,则协调者项多有参与者发送正式提交的命令(更新值),参与者完成正式提交,释放资源,回应完成。协调者收到所有节点的完成响应后结束这个全局事务.。若参与者回应拒绝提交,则协调者向所有的参与者发送回滚操作,并释放资源,当收到全部节点的回滚回应后,取消全局事务
  3. 存在的问题:若一个没提交,就会进行回滚
    • 第一阶段:若消息的传递未接收到,则需要协调者作超时处理,要么当做失败,要么重载
    • 第二阶段:若参与者的回应超时,要么重试,要么把那个参与者即为问题节点,提出整个集群
    • 在第二阶段中,参与者未收到协调者的指示(也许协调者挂掉),则所有参与者会进入“不知所措” 的状态(但是已经锁定了资源),所以引入了三段提交

4. 三段提交:把二段提交的第一阶段 break 成了两段

  1. 询问
  2. 锁定资源(获取锁)
  3. 提交
  • 核心理念:在询问的时候并不锁定资源,除非所有人都同意了,才开始锁定
  • 好处:当发生了失败或超时时,三段提交可以继续把状态变为Commit 状态,而二段提交则不知所措?

5. Raxos 算法(少数服从多数)

  • 解决的问题:在一个可能发生异常的分布式系统中如何就某个值达成一致,让整个集群的节点对某个值的变更达成一致
  • 任何一个节点都可以提出要修改某个数据的提案,是否通过这个提案取决于这个集群中是否有超过半数的节点同意(所以节点数总是单数)—— 版本标记。虽然一致性,但是只能对一个操作进行操作啊??
  • 当一个Server接收到比当前版本号小的提案时,则拒绝。当收到比当前大的版本号的提案时,则锁定资源,进行修改,返回OK. 也就是说收到超过一半的最大版本的提案才算成功。

核心思想

  1. 在抢占式访问权的基础上引入多个acceptor,也就是说当一个版本号更大的提案可以剥夺版本号已经获取的锁。
  2. 后者认同前者的原则:
    • 在肯定旧epoch 无法生成确定性取值时,新的 epoch 会提交自己的valu
    • 一旦 旧epoch形成确定性取值,新的 epoch肯定可以获取到此取值,并且会认同此取值,不会被破坏。

步骤

  1. P1 请求Acceptor的 #1,Acceptor 这时并没有其他线程获取到锁,所以把锁交给 P1,并返回这时 #1 的值为null
  2. 然后 P1 向 第一个 Acceptor 提交 #1 的值,Acceptor 接受并返回 OK
  3. 这个时候,P2向Acceptor请求#1上的锁,因为版本号更大,所以直接抢占了 P1 的锁。这时 Acceptor 返回了 OK并且返回了 #1 的值
  4. 这时 P1 P向 后面两个 Acceptor 提交 #1 的值,但是由于中间的那个Acceptor 版本号已经更改为 2 了,所以拒绝P1。第三个 Acceptor 接受了,并且返回了 OK
  5. 由于后者认同前者的原则,这时 P1 已经形成确定性取值了 V1 了,这时新的 P2 会认同此取值,而不是提交自己的取值。所以,P2会选择最新的那个取值 也就是V1 进行提交。这时Acceptor 返回 OK

6.ZAB 协议 ( Zookeeper Atomic Broadcast) 原子广播协议:保证了发给各副本的消息顺序相同

定义:原子广播协议 ZAB 是一致性协议,Zookeeper 把其作为数据一致性的算法。ZAB 是在 Paxos 算法基础上进行扩展而来的。Zookeeper 使用单一主进程 Leader用于处理客户端所有事务请求,采用 ZAB 协议将服务器状态以事务形式广播到所有 Follower 上,由于事务间可能存在着依赖关系,ZAB协议保证 Leader 广播的变更序列被顺序的处理,一个状态被处理那么它所依赖的状态也已经提前被处理

核心思想:保证任意时刻只有一个节点是Leader,所有更新事务由Leader发起去更新所有副本 Follower,更新时用的是 两段提交协议,只要多数节点 prepare 成功,就通知他们commit。各个follower 要按当初 leader 让他们 prepare 的顺序来 apply 事务

协议状态

  1. Looking:系统刚启动时 或者 Leader 崩溃后正处于选举状态
  2. Following:Follower 节点所处的状态,Follower与 Leader处于数据同步状态
  3. Leading:Leader 所处状态,当前集群中有一个 Leader 为主进程
  • ZooKeeper启动时所有节点初始状态为Looking,这时集群会尝试选举出一个Leader节点,选举出的Leader节点切换为Leading状态;当节点发现集群中已经选举出Leader则该节点会切换到Following状态,然后和Leader节点保持同步;当Follower节点与Leader失去联系时Follower节点则会切换到Looking状态,开始新一轮选举;在ZooKeeper的整个生命周期中每个节点都会在Looking、Following、Leading状态间不断转换。
  • 选举出Leader节点后 ZAB 进入原子广播阶段,这时Leader为和自己同步每个节点 Follower 创建一个操作序列,一个时期一个 Follower 只能和一个Leader保持同步

阶段

  1. Election: 在 Looking状态中选举出 Leader节点,Leader的LastZXID总是最新的(只有lastZXID的节点才有资格成为Leade,这种情况下选举出来的Leader总有最新的事务日志)。在选举的过程中会对每个Follower节点的ZXID进行对比只有highestZXID的Follower才可能当选Leader
    • 每个Follower都向其他节点发送选自身为Leader的Vote投票请求,等待回复;
    • Follower接受到的Vote如果比自身的大(ZXID更新)时则投票,并更新自身的Vote,否则拒绝投票;
    • 每个Follower中维护着一个投票记录表,当某个节点收到过半的投票时,结束投票并把该Follower选为Leader,投票结束;
  2. Discovery:Follower 节点向准 Leader推送 FollwerInfo,该信息包含了上一周期的epoch,接受准 Leader 的 NEWLEADER 指令
  3. Sync:将 Follower 与 Leader的数据进行同步,由Leader发起同步指令,最终保持数据的一致性
  4. Broadcast:Leader广播 Proposal 与 Commit,Follower 接受 Proposal 与 commit。因为一个时刻只有一个Leader节点,若是更新请求,只能由Leader节点执行(若连到的是 Follower 节点,则需转发到Leader节点执行;读请求可以从Follower 上读取,若是要最新的数据,则还是需要在 Leader上读取)
    • 消息广播使用了TCP协议进行通讯所有保证了接受和发送事务的顺序性。广播消息时Leader节点为每个事务Proposal分配一个全局递增的ZXID(事务ID),每个事务Proposal都按照ZXID顺序来处理(Paxos 保证不了)
    • Leader节点为每一个Follower节点分配一个队列按事务ZXID顺序放入到队列中,且根据队列的规则FIFO来进行事务的发送。
  5. Recovery :根据Leader的事务日志对Follower 节点数据进行同步更新
    • 同步策略:
      1. SNAP :如果Follower数据太老,Leader将发送快照SNAP指令给Follower同步数据;
      2. DIFF :Leader发送从Follolwer.lastZXID到Leader.lastZXID议案的DIFF指令给Follower同步数据;
      3. TRUNC :当Follower.lastZXID比Leader.lastZXID大时,Leader发送从Leader.lastZXID到Follower.lastZXID的TRUNC指令让Follower丢弃该段数据;(当老Leader在Commit前挂掉,但是已提交到本地)
    • Follower将所有事务都同步完成后Leader会把该节点添加到可用Follower列表中;
    • Follower接收Leader的NEWLEADER指令,如果该指令中epoch比当前Follower的epoch小那么Follower转到Election阶段

7. Raft 算法

  • Raft 算法也是一种少数服从多数的算法,在任何时候一个服务器可以扮演以下角色之一:
    1. Leader:负责 Client 交互 和 log 复制,同一时刻系统中最多存在一个
    2. Follower:被动响应请求 RPC,从不主动发起请求 RPC
    3. Candidate : 由Follower 向Leader转换的中间状态
  • 在选举Leader的过程中,是有时间限制的,raft 将时间分为一个个 Term,可以认为是“逻辑时间”:
    1. 每个 Term中至多存在1个 Leader
    2. 某些 Term由于不止一个得到的票数一样,就会选举失败,不存在Leader。则会出现 Split Vote ,再由候选者发出邀票
    3. 每个 Server 本地维护 currentTerm
  • 选举过程:
    1. 自增 CurrentTerm,由Follower 转换为 Candidate,设置 votedFor 为自身,并行发起 RequestVote RPC,不断重试,直至满足下列条件之一为止:
      • 获得超过半数的Server的投票,转换为 Leader,广播 HeatBeat
      • 接收到 合法 Leader 的 AppendEnties RPC,转换为Follower
      • 选举超时,没有 Server选举成功,自增 currentTerm ,重新选举
    2. 当Candidate 在等待投票结果的过程中,可能会接收到来自其他Leader的 AppendEntries RPC ,如果该 Leader 的 Term 不小于本地的 Current Term,则认可该Leader身份的合法性,主动降级为Follower,反之,则维持 candida 身份继续等待投票结果
    3. Candidate 既没有选举成功,也没有收到其他 Leader 的 RPC (多个节点同时发起选举,最终每个 Candidate都将超时),为了减少冲突,采取随机退让策略,每个 Candidate 重启选举定时器
  • 日志更新问题:如果在日志复制过程中,发生了网络分区或者网络通信故障,使得Leader不能访问大多数Follwers了,那么Leader只能正常更新它能访问的那些Follower服务器,而大多数的服务器Follower因为没有了Leader,他们重新选举一个候选者作为Leader,然后这个Leader作为代表于外界打交道,如果外界要求其添加新的日志,这个新的Leader就按上述步骤通知大多数Followers,如果这时网络故障修复了,那么原先的Leader就变成Follower,在失联阶段这个老Leader的任何更新都不能算commit,都回滚,接受新的Leader的新的更新。
  • 流程:
    1. Client 发送command 命令给 Leader
    2. Leader追加日志项,等待 commit 更新本地状态机,最终响应 Client
    3. 若 Client超时,则不断重试,直到收到响应为止(重发 command,可能被执行多次,在被执行但是由于网络通信问题未收到响应)
      • 解决办法:Client 赋予每个 Command唯一标识,Leader在接收 command 之前首先检查本地log

9. paxos 算法与 raft 算法的差异

  1. raft强调是唯一leader的协议,此leader至高无上
  2. raft:新选举出来的leader拥有全部提交的日志,而 paxos 需要额外的流程从其他节点获取已经被提交的日志,它允许日志有空洞
  • 相同点:得到大多数的赞成,这个 entries 就会定下来,最终所有节点都会赞成

NWR模型

  • N: N个备份
  • W:要写入至少 w 份才认为成功
  • R : 至少读取 R 个备份
  • W+ R > N ——> R > N - W(未更新成功的) ,代表每次读取,都至少读取到一个最新的版本(更新成功的),从而不会读到一份旧数据
  • 问题:并非强一致性,会出现一些节点上的数据并不是最新版本,但却进行了最新的操作
  • 版本冲突问题:矢量钟 Vector Clock : 谁更新的我,我的版本号是什么(对于同一个操作者的同一操作,版本号递增)

参考资料:

http://www.tuicool.com/articles/IfQR3u3

http://blog.csdn.net/chen77716/article/details/7309915

http://www.infoq.com/cn/articles/distributed-system-transaction-processing/

http://www.jdon.com/artichect/raft.html

http://blog.csdn.net/cszhouwei/article/details/38374603

文章转自:
https://blog.csdn.net/followmyinclinations/article/details/52870418