泽民博客 ☰ Menu

raft


分布式系统的Raft算法



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



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



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



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



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



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



Leader: 处理所有客户端交互，日志复制等，一般一次只有一个Leader.
Follower: 类似选民，完全被动
Candidate候选人: 类似Proposer律师，可以被选为一个新的领导人。
Raft阶段分为两个，首先是选举过程，然后在选举出来的领导人带领进行正常操作，比如日志复制等。下面用图示展示这个过程：





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




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





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





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




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




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




  4. Follower同意后，其成为Leader，继续承担日志复制等指导工作：





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



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



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




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



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




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



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



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



总结：目前几乎所有语言都已经有支持Raft算法的库包，具体可参考：raftconsensus.github.io
CAP定理
分布式领域CAP理论，
Consistency(一致性), 数据一致更新，所有数据变动都是同步的
Availability(可用性), 好的响应性能
Partition tolerance(分区容错性) 可靠性



定理：任何分布式系统只可同时满足二点，没法三者兼顾。
忠告：架构师不要将精力浪费在如何设计能满足三者的完美分布式系统，而是应该进行取舍。



关系数据库的ACID模型拥有 高一致性 + 可用性 很难进行分区：
Atomicity原子性：一个事务中所有操作都必须全部完成，要么全部不完成。
Consistency一致性. 在事务开始或结束时，数据库应该在一致状态。
Isolation隔离层. 事务将假定只有它自己在操作数据库，彼此不知晓。
Durability. 一旦事务完成，就不能返回。
跨数据库事务：2PC (two-phase commit)， 2PC is the anti-scalability pattern (Pat Helland) 是反可伸缩模式的，JavaEE中的JTA事务可以支持2PC。因为2PC是反模式，尽量不要使用2PC，使用BASE来回避。



BASE模型反ACID模型，完全不同ACID模型，牺牲高一致性，获得可用性或可靠性：
Basically Available基本可用。支持分区失败(e.g. sharding碎片划分数据库)
Soft state软状态 状态可以有一段时间不同步，异步。
Eventually consistent最终一致，最终数据是一致的就可以了，而不是时时高一致。



BASE思想的主要实现有
1.按功能划分数据库
2.sharding碎片



BASE思想主要强调基本的可用性，如果你需要High 可用性，也就是纯粹的高性能，那么就要以一致性或容错性为牺牲，BASE思想的方案在性能上还是有潜力可挖的。



现在NOSQL运动丰富了拓展了BASE思想，可按照具体情况定制特别方案，比如忽视一致性，获得高可用性等等，NOSQL应该有下面两个流派：



  1. Key-Value存储，如Amaze Dynamo等，可根据CAP三原则灵活选择不同倾向的数据库产品。

  2. 领域模型 + 分布式缓存 + 存储 （Qi4j和NoSql运动），可根据CAP三原则结合自己项目定制灵活的分布式方案，难度高。



这两者共同点：都是关系数据库SQL以外的可选方案，逻辑随着数据分布，任何模型都可以自己持久化，将数据处理和数据存储分离，将读和写分离，存储可以是异步或同步，取决于对一致性的要求程度。



不同点：NOSQL之类的Key-Value存储产品是和关系数据库头碰头的产品BOX，可以适合非Java如PHP RUBY等领域，是一种可以拿来就用的产品，而领域模型 + 分布式缓存 + 存储是一种复杂的架构解决方案，不是产品，但这种方式更灵活，更应该是架构师必须掌握的。



分布式Paxos算法
分布式系统Paxos算法



　　这是一个有关Paxos算法非常形象的讲解与示范。Paxos是能够基于一大堆完全不可靠的网络条件下却能可靠确定地实现共识一致性的算法。也就是说：它允许一组不一定可靠的处理器（服务器）在某些条件得到满足情况下就能达成确定的安全的共识，如果条件不能满足也确保这组处理器（服务器）保持一致。



什么是共识？
　　具体来说是这样：分布式系统中由于网络之间通讯可能会中断，虽然概率很低，但是没有100%完美的网络因此，依靠网络通讯的计算机之间要达成共识就比较困难，假设有X, Y和Z三台计算机谋划在周一攻击人类世界，它们的攻击计划是只要所有计算机可用于战斗时就一起进行攻击，不落下任何一台机器，但是当他们决定具体什么时间开始攻击时，在这个关键问题上往往会出错。



　　一个基本问题是，每台机器都有自己的攻击时间建议，计算机X可以建议在08:00时间，因为这个时间正是周一早晨，而人们刚刚过完狂欢的周末休息天，但是计算机Z认为13:00比较好，理由当然也有一大堆，让这三台计算机基于某个时刻达成共识是非常困难的，因此，也给人类反击留下了机会。



　　另外一个情况是，这三台计算机是位于世界不同的位置，之间通讯或许通过电缆或者其他不太可靠的网络设备通讯，如果X建议在08:00，它必须确认它的这个建议能够到达活着的Y和Z，以免一个人战斗。



问题是：我们不能准确地知道某个计算机的延迟的原因：是因为性能慢了还是已经是彻底死机不能用？



　　那么，X怎么知道其他两个计算机是可用的呢？也就是说，当X和其他两个计算机通讯发现得到响应要过很长时间，它不能确定这两台计算机到底还能不能继续活下去，也许这次通讯有延迟了，下一次它们又活过来了没有延迟了，也许下次延迟更长了一点，也许下次延迟稍微短了一点，这些随机概率问题使得X不能确定Y和Z到底是出了什么问题造成延迟的，是因为处理了某个特别耗费CPU的任务还是因为死锁等原因？当然，有些天真的设计者会说，只要我们将性能监控到位，如果延迟超过一定时间，我们人工介入告诉X确切情况就可以，那么这种人工介入的分布式系统不是一个天然自洽的自动化系统了，不在我们讨论范围之内，而且这样的系统会让人疲于奔命。



　　因为X不能确定Y或Z是否可用，所以X仅仅只能和Y与Z中一台基于攻击时间达成共识，就无法完全三台机器全部投入战斗的计划。注意的是，X Y Z三台中任何一台都可能会出现延迟，这就造成了三台机器之间任何通讯都是无法确认可靠的，比如X发出消息给Z，Z确认后回执给X，但是这段时间X突然死机了，那么Z要等待X多长时间才能知道它收到确认呢？还是再次等待X回复确认的确认，这样无限循环下去也不能解决它们之间通讯可能出现随机不可靠的问题。



　　所有关键问题在于：由于这三台机器之间通讯是无法保证100%可靠，它们就不能就任何事情达成共识。



　　下面以分布式拍卖案例说明这种情况以及Paxos的基本原理？



　　在传统拍卖场景中，价高者先得，这些拍卖者都是在同一个房间，彼此能够直接看得到对方的报价，如果我们假设分布式拍卖是将这些拍卖者分离到不同的地方，这样我们可以用拍卖者之间的联系模拟分布式计算机之间的通讯。



　　假设拍卖者各自在自己家里拍卖，通过邮局信件发出自己的拍卖信息，拍卖者之间除非等到邮局投递人告诉他们彼此之间的报价，否则是无法知道对方报价的。如果邮局信件投递这个环节出了问题，投递速度慢了甚至无法投递了，那么整个拍卖程序就无法继续进行下去。



Paxos解决共识思路
　　Paxos是一个解决共识问题consensus problem的算法，现实中Paxos的实现以及成为一些世界级软件的心脏，如Cassandra, Google的 Spanner数据库, 分布式锁服务Chubby. 一个被Paxos管理的系统实际上谈论的是值 状态和跟踪等问题，其目标是建造更高可用性和强一致性的分布式系统。



　　Paxos完成一次写操作需要两次来回，分别是prepare/promise, 和 propose/accept：



paxos



　　第一次由提交者Leader向所有其他服务器发出prepare消息请求准备，所有服务器中大多数如果回复诺言承诺就表示准备好了，可以接受写入；第二次提交者向所有服务器发出正式建议propose，所有服务器中大多数如果回复已经接收就表示成功了。



　　为了详细描述这个两段过程，首先让我们定义一下我们将使用的一些名词术语：



一个进程是系统中计算机的一个. 人们使用有关复制或节点等词语表达，都差不多。
一个客户端是属于系统中一个成员的计算机，但是询问系统值是什么或者要求系统获取一个新的值。
　　Paxos构建分布式数据库的小片段: 它仅仅实现进程将一个新的东西精确地写入系统中，进程是由Paxos的一个实例管治，可以失败或者不知道任何东西、或者大多数进程都知道一个同样的值，这就是共识，Paxos并不真的告诉我们如何用它来构建数据库或类似的东西，它只是负责独立节点之间通讯的进程， 这些进程服务器会基于一个新值执行决定，Paxos会存储一个值数据，只是一次性的，一旦你第一次设置以后就不能再改变它。



Paxo读操作
　　其实Paxos精华是在写操作，将读操作放在写操作前面讲解，是着重Paxos以大多数服务器达成共识为重要标志，通过读取判断是否达成共识这一状态。



　　为了从Paxos系统中读取一个值数据，客户端会请求读取所有进程中存储的当前值，然后从大多数进程服务器中获得这个值，如果数量凑不够大多数或者没有足够的客户端响应，读取操作失败，下面图示你会看到一个客户端询问其他节点他们的值是多少，这些节点返回值给客户端，当客户端获得了大多数节点的响应，返回的值都是同样的，它就算成功地读操作了，并顺便保存读结果。



　　与单节点系统(只有一台服务器)相比这有些奇怪，这两个系统中，客户端都需要观察系统已决定状态，但是在非分布式系统中像MySQL或一个memcached服务器中, 客户端只需直接向标准的状态存储的服务器地址获取状态即可，在简单的Paxos中, 客户端也是同样的方式观察状态，但是因为并没有标准的状态存储的服务器地址，它需要询问所有的成员，以便能够确定仅有一个会报告值数据，实际上是大多数节点都持有的值数据，如果客户端询问一个节点，有可能这个节点进程已经过期，得到了错误的值数据，进程失效过期的原因有很多：由于不可靠的网络导致本应送达到它们的消息丢失了；或者他们也许当机然后使用了一个过期状态恢复；或者算法还在运行计算中，进程并没有正好得到消息等等。在现实中使用Paxos实现时，其实不需要每个节点都进行一次读取，会有更好的读取方式，但是他们都是拓展的原始 Paxos 算法。



Paxos写操作
　　当一个客户端要求写入系统一个新值时，让我们看看Paxos让我们集群的进程都做了什么？下面的过程都是只有一个值的写入，最终我们能用这个进程作为原始数据，允许值数据在彼此之间一个个设置，但是基本的Paxos算法管治了一个新值数据的写操作流程， 然后做重复的事情。



　　首先Paxos管理的系统中一个客户端要求写入一个新值，客户端这里如图所示是红圈，其它进程是蓝圈， Paxos能保证客户端发送它们的写请求到Paxos集群中任何成员, 这里演示中客户端随机挑选进程中任意一个，这种方式是重要且巧妙的，意味著没有任何单点风险，意味着我们的Paxos管治系统能继续保持在线可用，无论任何一个节点当机或其他不可用原因无响应。如果我们设计一个特定节点作为“推荐人proposer”或者 “the master” 等, 如果这个主节点死机，那么整个系统就崩溃了。



　　当写请求被接受后，Paxos进程会接受这个写新值到系统中请求“建议”， “建议”是Paxos中一个正式概念: 向一个Paxos管治的系统建议可能会成功或失败，需要步骤来确保共识能够达成维系，这个建议以准备消息从那些与客户端连接的进程节点们被发往整个系统。



序列号
　　这个准备消息保存在被建议的值数据中，它们也称为序列号sequence number，序列号是由建议进程产生的，它定义了接受进程应该准备接受带有序列号的建议，这个序列号是关键: 它用于表明新旧建议之间的区别，如果两个进程试图获得需要设置一个值，Paxos认为最后一个进程应该有优先权，这样让进程分辨哪个是最后一个，这样它就能设置最新的值。



　　这些接受的进程能够进行在系统中关键的检查：这个在到来的准备消息中序列号是我见过的最高级别吗？如果是，那就很cool, 我能准备好接受将要到来的值数据，那就不要管之前听到的任何其他值数据了，你能看到这个过程在右边演示中：客户端每隔一段向一个进程建议一个新值，这个进程发送准备消息给其他进程，然后那些进程注意到这是一个成功的更高的超过旧的新序列号，然后就放手那些旧建议。



　　这里有一个顺序的设计(先发送准备消息)，这是为避免单点风险，如果没有这个顺序，Paxos中成员就无法分辨哪个建议是他们可以有信心地准备接受的。



　　我们不能想象有另外不同的共识算法，不是按照如下步骤：首先发送第一个消息询问其他进程，以确保将设置的新值是最新的值，尽管方式可以再简单些，但是可能就不能满足共识算法安全的需求了，如果两个进程正好同时建议不同的值，如下所示：



　　大自然经常会这样欺骗我们，每个包都能另外一半的进程相信它们接受的也许是正确也许是错误的值，系统将进入一个僵局，存在两个相同数量的组却有不同的值，那么就无法确定大多数这个概念了，这个僵局能够被第一个Paxos消息避免，因为Paxos的序列号，那些有问题的建议将有被其他更低的序列号，这样序列号更高的建议就会毫不含糊地被大多数进程接收，它们也首先获得了更高的序列号，然后如果接受到更低的序列号就会拒绝，Paxos 就是这样通过用序列号控制整个系统的时间节奏。



上图演示了客户端首先发一个准备消息给Paxos进程，Paxos进程会检查下一步将到来的建议的序列号，以分辨是否准备接受这个新值，所有进程都是这样消除歧义，共识由此达成。
　　注意：保证没有两个建议使用相同的序列号是很重要的，这是确保他们的顺序，这样每个序列号只有一个建议，这样才能比较两个建议，实现Paxos时，全局唯一有序的序列号实际是精确系统时间和集群中节点数量的拷贝，随着时间不断增加，从来不会重复。



Paxos第一阶段：准备Perpare/诺言Promises
　　Paxos的第一阶段是prepare/promise，准备阶段就是将建议值发送到各个目标节点。



　　当建议被发到目标节点后，进程会会检查建议中的序列号，是否是它们见到过的最高级，如果是最高级，它们会发出一个promise不再接受比这个新序列号更旧的建议了，这个诺言promise作为消息从许下诺言的进程发到提交建议新值的进程服务器，这个诺言消息给提交建议的进程后，提交建议的进程需要自己统计一下有多少其他进程已经发回它们的诺言promise了，如果判断数量上是否达到大多数？如果大多数进程已经同意接受这个建议或者更高级序列号的建议，这个提交建议的进程就能知道它获得了发言权(因为有大多数支持)，这样就开始讲话，算法中的下一步处理将可能进行；如果回复诺言的节点数量没有达到大多数，也就是共识没有达成，这样这个节点提交的建议将退出，客户端要求的写操作失败。



　　为了决定一个建议是否已经有足够的回复诺言promises, 提交建议者只是统计一下它接受到的 promise 消息数量，然后和整个系统中节点服务器数量比较一下，“足够”意味着大多数(N/2 + 1)个进程服务器在某段时间内都回复了诺言promises。如果超过一半的进程服务器没有返回诺言，这意味着这个建议没有被大多数通过，那么在前面描述的读算法中就不能满足大多数的要求，也就不能达成共识，这个建议就退出。其他包括网络分区错误也可能会阻止大多数达成共识，



第二阶段：Paoxs接纳Acceptance
　　当完成prepare/promise阶段，进入了 propose/accept阶段。



　　一旦建议提交者已经从大多数其他进程服务器获得了诺言，它会要求许诺的进程服务器接收它们之前承诺接受的新值数据，这是一个“确认commit”阶段，如果没有冲突建议 失败或分区错误，那么这个新建议将被所有其他节点接受，那么Paxos过程就完成了。



　　你能看到右边的演示，注意这个演示比上面promise在最后多了一个动作，也就是提交建议者将新值发给那些许诺言的进程服务器，让它们接受了这个新值。



　　接受的过程也许可能会发生失败，在回复了诺言消息以后，在接受到Accept消息之前，如果有足够多的服务器正好在这个时间段失败，那么接受行为只能是少数服务器，那么Paxos进入了厄运状态：一些进程服务器接受了新值，而不是全部的，这种不一致已经在前面读操作中描述：一个客户端试图从系统中大多数节点服务器读取它们同意接受的值，它发现一些节点服务器报告有不同的值数据，这会引起读失败，但是Paxos还保持一致性，不允许在没有达成共识情况下任何写操作发生，这种坏的情况在实践中经常通过重复接受阶段来让大多数节点最终接受。



总结
　　Paxos算法是保证在分布式系统中写操作能够顺利进行，保证系统中大多数状态是一致的，没有机会看到不一致，因此，Paxos算法的特点是一致性>可用性。



　　vector clock向量时钟是另外一种保证复制的算法，其特点是可用性>一致性，但是，一旦发生冲突，不像Paxos能自行解决，需要人工干预编写代码解决。



　　Paxos算法和Vector Clock都是由Leslie Lamport提出。
ZooKeeper在服务发现中应用
1.CAP原理
要想数据高可用，就得写多份数据



写多分数据就会导致数据一致性问题



数据一致性问题会引起性能问题



2.一致性模型
弱一致性



最终一致性（一段时间达到一致性）



强一致



1、2 异步冗余；3是同步冗余




  1. 扩展服务的方案
    数据分区： uid % 16



数据镜像：让多有的服务器都有相同的数据，提供相当的服务（冗余存储，一般3份为好）



4.两种方案的事务问题
A向B汇钱，两个用户不在一个服务器上



镜像：在不同的服务器上对同一数据的写操作如何保证一致性。




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

  2. Master -Slave
    读写请求由Master负责



写请求写到Master后，由Master同步到Slave上



由Master push or Slave pull



通常是由Slave 周期性来pull，所以是最终一致性



问题： 若在 pull 周期内（不是期间？），master挂掉，那么会导致这个时间片内的数据丢失



若不想让数据丢掉，Slave 只能成为 ReadOnly方式等Master恢复



若容忍数据丢失，可以让 Slave代替Master工作



如何保证强一致性？



Master 写操作，写完成功后，再写 Slave，两者成功后返回成功。若 Slave失败，两种方法



标记 Slave 不可用报错，并继续服务（等恢复后，再同步Master的数据，多个Slave少了一个而已）



回滚自己并返回失败




  1. Master-Master
    数据同步一般是通过 Master 间的异步完成，所以是最终一致



好处： 一台Master挂掉，另外一台照样可以提供读写服务。当数据没有被赋值到别的Master上时，数据会丢失。



对同一数据的处理问题：Dynamo的Vector Clock的设计（记录数据的版本号和修改者），当数据发生冲突时，要开发者自己来处理



​



3.两阶段提交 Two Phase Commit _ 2PC
第一阶段：针对准备工作



协调者问所有节点是否可以执行提交



参与者开始事务，执行准备工作：锁定资源（获取锁操作）



参与者响应协调者，如果事务的准备工作成功，则回应”可以提交”，否则，拒绝提交



第二阶段：



若都响应可以提交，则协调者项多有参与者发送正式提交的命令（更新值），参与者完成正式提交，释放资源，回应完成。协调者收到所有节点的完成响应后结束这个全局事务.。若参与者回应拒绝提交，则协调者向所有的参与者发送回滚操作，并释放资源，当收到全部节点的回滚回应后，取消全局事务



存在的问题：若一个没提交，就会进行回滚



第一阶段：若消息的传递未接收到，则需要协调者作超时处理，要么当做失败，要么重载



第二阶段：若参与者的回应超时，要么重试，要么把那个参与者即为问题节点，提出整个集群



在第二阶段中，参与者未收到协调者的指示（也许协调者挂掉），则所有参与者会进入“不知所措” 的状态（但是已经锁定了资源），所以引入了三段提交




  1. 三段提交：把二段提交的第一阶段 break 成了两段
    询问



锁定资源（获取锁）



提交



核心理念：在询问的时候并不锁定资源，除非所有人都同意了，才开始锁定



好处：当发生了失败或超时时，三段提交可以继续把状态变为Commit 状态，而二段提交则不知所措？




  1. Raxos 算法（少数服从多数）
    解决的问题：在一个可能发生异常的分布式系统中如何就某个值达成一致，让整个集群的节点对某个值的变更达成一致



任何一个节点都可以提出要修改某个数据的提案,是否通过这个提案取决于这个集群中是否有超过半数的节点同意（所以节点数总是单数）—— 版本标记。虽然一致性，但是只能对一个操作进行操作啊？？



当一个Server接收到比当前版本号小的提案时，则拒绝。当收到比当前大的版本号的提案时，则锁定资源，进行修改，返回OK. 也就是说收到超过一半的最大版本的提案才算成功。



核心思想：



在抢占式访问权的基础上引入多个acceptor，也就是说当一个版本号更大的提案可以剥夺版本号已经获取的锁。



后者认同前者的原则：



在肯定旧epoch 无法生成确定性取值时，新的 epoch 会提交自己的valu



一旦 旧epoch形成确定性取值，新的 epoch肯定可以获取到此取值，并且会认同此取值，不会被破坏。



步骤



P1 请求Acceptor的 #1,Acceptor 这时并没有其他线程获取到锁，所以把锁交给 P1，并返回这时 #1 的值为null



然后 P1 向 第一个 Acceptor 提交 #1 的值，Acceptor 接受并返回 OK



这个时候，P2向Acceptor请求#1上的锁，因为版本号更大，所以直接抢占了 P1 的锁。这时 Acceptor 返回了 OK并且返回了 #1 的值



这时 P1 P向 后面两个 Acceptor 提交 #1 的值，但是由于中间的那个Acceptor 版本号已经更改为 2 了，所以拒绝P1。第三个 Acceptor 接受了，并且返回了 OK



由于后者认同前者的原则，这时 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 事务



协议状态



Looking:系统刚启动时 或者 Leader 崩溃后正处于选举状态



Following：Follower 节点所处的状态，Follower与 Leader处于数据同步状态



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保持同步



阶段



Election： 在 Looking状态中选举出 Leader节点，Leader的LastZXID总是最新的（只有lastZXID的节点才有资格成为Leade,这种情况下选举出来的Leader总有最新的事务日志）。在选举的过程中会对每个Follower节点的ZXID进行对比只有highestZXID的Follower才可能当选Leader



每个Follower都向其他节点发送选自身为Leader的Vote投票请求，等待回复；



Follower接受到的Vote如果比自身的大（ZXID更新）时则投票，并更新自身的Vote，否则拒绝投票；



每个Follower中维护着一个投票记录表，当某个节点收到过半的投票时，结束投票并把该Follower选为Leader，投票结束；



Discovery:Follower 节点向准 Leader推送 FollwerInfo,该信息包含了上一周期的epoch，接受准 Leader 的 NEWLEADER 指令



Sync：将 Follower 与 Leader的数据进行同步，由Leader发起同步指令，最终保持数据的一致性



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来进行事务的发送。



​



Recovery ：根据Leader的事务日志对Follower 节点数据进行同步更新



同步策略：



SNAP ：如果Follower数据太老，Leader将发送快照SNAP指令给Follower同步数据；



DIFF ：Leader发送从Follolwer.lastZXID到Leader.lastZXID议案的DIFF指令给Follower同步数据；



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阶段




  1. Raft 算法
    Raft 算法也是一种少数服从多数的算法，在任何时候一个服务器可以扮演以下角色之一：



Leader：负责 Client 交互 和 log 复制，同一时刻系统中最多存在一个



Follower：被动响应请求 RPC，从不主动发起请求 RPC



Candidate : 由Follower 向Leader转换的中间状态



在选举Leader的过程中，是有时间限制的，raft 将时间分为一个个 Term，可以认为是“逻辑时间”：



每个 Term中至多存在1个 Leader



某些 Term由于不止一个得到的票数一样，就会选举失败，不存在Leader。则会出现 Split Vote ，再由候选者发出邀票



每个 Server 本地维护 currentTerm



选举过程：



自增 CurrentTerm，由Follower 转换为 Candidate，设置 votedFor 为自身，并行发起 RequestVote RPC,不断重试，直至满足下列条件之一为止：



获得超过半数的Server的投票，转换为 Leader，广播 HeatBeat



接收到 合法 Leader 的 AppendEnties RPC，转换为Follower



选举超时，没有 Server选举成功，自增 currentTerm ,重新选举



当Candidate 在等待投票结果的过程中，可能会接收到来自其他Leader的 AppendEntries RPC ,如果该 Leader 的 Term 不小于本地的 Current Term，则认可该Leader身份的合法性，主动降级为Follower，反之，则维持 candida 身份继续等待投票结果



Candidate 既没有选举成功，也没有收到其他 Leader 的 RPC (多个节点同时发起选举，最终每个 Candidate都将超时)，为了减少冲突，采取随机退让策略，每个 Candidate 重启选举定时器



日志更新问题：



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



流程：



Client 发送command 命令给 Leader



Leader追加日志项，等待 commit 更新本地状态机，最终响应 Client



若 Client超时，则不断重试，直到收到响应为止（重发 command，可能被执行多次，在被执行但是由于网络通信问题未收到响应）



解决办法：Client 赋予每个 Command唯一标识，Leader在接收 command 之前首先检查本地log




  1. paxos 算法与 raft 算法的差异
    raft强调是唯一leader的协议，此leader至高无上



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



Category storage