哪个企业提供电子商务网站建设外包,海口网站建设在线,开发网站需要怎么做,中国建设银行招聘信息网站Raft图文详解
refer to: Raft lecture (Raft user study) - YouTube Raft PDF Raft算法详解 - 知乎 (zhihu.com) 今天来详细介绍一下Raft协议 Raft是来解决公式问题的协议#xff0c;那么什么是共识呢#xff1f; 在分布式系统里面#xff0c;consensus指的是多个节点对…Raft图文详解
refer to: Raft lecture (Raft user study) - YouTube Raft PDF Raft算法详解 - 知乎 (zhihu.com) 今天来详细介绍一下Raft协议 Raft是来解决公式问题的协议那么什么是共识呢 在分布式系统里面consensus指的是多个节点对某个状态达成一致结果而共识算法则是用来保障系统一致性的比如说对于某个事件发生的顺序某个key对应的值、谁是领导等 那么如何实现共识呢
现在主要有两种方法第一种是对称的、无领导的方式即server之间是平等的都可以进行日志的添加或者复制client可以和任何一个server交互
第二种方法是非对称的有领导者的。集群中有一台server负责统筹管理其他server只是被动的接受她的决定而client是直接与leader进行交互的
Raft则是leader-based它将问题分解成了两个东西第一个就是在有leader下normal operation第二部分就是当leader crash的时候要做些什么去选出一个新leader。这样的好处就是在正常运行的时候整个系统非常简单不需要考虑不同leader之间的冲突效率也更高 Raft的整体目标是进行集群之间的日志的多副本复制然后将log应用到状态机。假设你有一个程序或者应用想要可靠运行reliable一种方式是把这个程序执行在一堆机器上并且确保他们以相同方式执行程序。这就是复制状态机的概念。
log可以帮助确保这些状态机以相同的顺序执行相同的命令。
如果client想要执行一个命令z 6将会给这些任意一个server的共识模块发送这个命令然后server会将命令存在本地的log中除此之外他还会将这个command传给其他servers其他机器也进行本地存储。当这个command被安全复制到logs之后将会把这个log传给状态机执行执行完毕返回结果给clients。所以我们可以看出来只要logs和机器是相同的这些不同机器上的状态机就会以相同顺序执行相同的命令并且产生相同的结果
所以共识模块的任务就是管理这些logs确保他们能正确的复制并且决定什么时候能安全地把这些command传给状态机执行之所以叫共识就是不需要全部节点都在特定时间运行只需要大多数节点即可。 主要从六个方面介绍
首先是leader election我们如果在多个server里面选出一个作为leader当崩溃之后我们如何选依据什么选一个新的leader呢
第二点是在有leader是情况下系统是怎么正常运行的比如接受client请求log replication等等
第三点是leader change领导人变更这是能保障系统运行的关键部分首先将说一下raft safe意味着什么并且如何保证safe然后将讨论一下leader如何解决一log一致性
第四点将说明一下关于leader changes的另一件事即如何处理并没有真正死亡的旧leader回到集群的问题
第五点将讨论一下clients如何和集群交互客户端在server crash的时候如何处理raft是怎么保证客户端的每个命令只被执行一次的
最后将讨论一下系统成员变更例如增加或者减少servers 在具体说Raft之前首先来看一下server states在任何时候server都处于以下三种状态之一。分别是
leader state即管理整个集群和客户端交互、日志复制的状态follower state这是一个完全消极的状态被动接受RPCs然后做的只有处理RPCscandidate state是两者的中间态用于选举leader。
当系统正常运行的时候只会有1 leader N-1 followers下面这张图则是说明了三种状态之间互相转化的条件这里就不仔细说了在后面的内容中会体现这点。 时间被分成一个个term每个term有一个数字并且这个数字是递增的。每个term 有两个部分term的开始则是进行选举即对当前term选出一个leader如果选举成功则进入第二部分即正常对外服务。可以看出每个term只有一个leader并且这里有一些term是没有leader的这一般是发生了split vote分票导致没有leader赢得多数票当这种情况发生的时候系统会马上重试进入一个新的term。每个server都会维护一个current term作为一个全序的值用来识别过时消息非常有用。 这张图其实已经基本完全的介绍了整个raft协议 OK现在来看一下raft六个部分的第一个部分选主。Raft需要保证在任何时候最多有一台机器是真正的leader。当一个server启动的时候他的状态是follower在这个状态它不会和其他任何followers交流仅仅回复rpc。那么为了维持follower保持follower状态必须让follower相信现在是有leader的实现的方法就是它收到candidate或者leader发送的消息。所以leader为了维护自己的存活就需要不断和其他servers交流当没有具体任务的时候就通过heartbeats来交互。如果一段时间follower没收到rpc将认为没有leader然后发起选举看看是不是需要自己当leader。而这段等待的时间就是election timeout通常在100-500 ms之间。初始化的时候整个集群们没有leader所以都等待election timeout时间然后开始选举。
当一个server开始选举的时候 首先就是增加自己的current term进入一个新的term当然新term第一件事就是开始选举然后将自己从follower转变成candidate在候选者状态要做的事就是让自己变成leader即需要赢得大多数选票。candidate第一件事就是先给自己投票然后发送request vote rpcs 给其他server请求选票。最后将会有三件事情发生第一个就是candidate收到了多数选票然后将自己转变成leader状态立即向其他servers发送heartbeats。第二个就是candidate收到了一个有效的leader发来的RPC然后就会step down成follower。第三种就是没有一个人赢得了选举有可能两个follower同时发起了选举最后出现了分票没人赢得大多数选票。当超过vote timeout时间还没选出leadercandidate就会重新增加自己的term然后再次发起选举。 这是一个选举的demo初始时有三个节点随机一段election timeout后node c首先到时间发起选举term 0-1 vote然后向node a,b发送request vote rpca,b收到之后更新自己的current Term记录vote for给谁投票然后回复node cnode c收到超半数投票当选为leader然后发送心跳信号node a,b收到心跳信号之后就会重置自己的计时器并且更新leader然后给node c肯定回复。 election过程需要满足这两个属性来确保安全safety和liveness。safety说的是每个term最多只有一个leader当选。Raft是通过要求每个server每个term只能投一票来实现的这样就能确保即使有两个不同的candidate也无法同时赢得多数选票。第二个是liveness必须要保证最后会有人赢得选举。如果一直重复split vote是可能一直都没有leader的。Raft解决这个的办法是增大election timeout当split vote之后下一次将在【T,2T】之间timeout通过增大timeout来减少两个servers同时醒来的可能性当有一个先醒来的时候他会有足够的时间向其他server发送请求完成选举。特别是T broadcast time的时候。 Raft的第二部分则是在正常运行情况下leader是如何进行log replication的。首先来看一下log 结构。每个server都独立保存着自己的logleader…followers… log是由Log entry组成的有序列而log entry是由index来索引的在entry内部是一个二元组(t,c) 分别是term和commandcommand是client发出的命令term则是该log entry首次被创建的时候的leader term的值。log存储在稳定存储器上例如磁盘当server对log改变的时候最后必须要在disk上做拷贝。像entry 7被存储到了大多数server中这时entry认为是committed如果entry是committed那么它可以安全地传给状态机来执行raft可以保证该entry的持久化不久之后该entry就会被每一个server上的状态机执行。其实这个committed定义还不够完全的安全在后面维护log的一致性的时候会稍作调整 Normal operation的过程非常简单client向leader发出请求想要将command执行到所有状态机中。而leader会首先将command追加到自己log后面然后向followers发送append entries RPCs一旦收到majority的response来认为entry已经committedleader会将command应用到状态机并且给客户端返回执行结果leader告知followers entries committedfollower得知已提交之后进行状态机执行。如果follower crash或者很慢导致leader没收到回复则超过timeout之后再次发送即可当然leader也不需要每一个server都回复只需要收到大多数节点回复即可。这样就使得整体效率比较高不会因一个slow server导致整个system slow Raft维护logs的高度一致性这一页列出了一些任何时候都成立的属性。第一个是index 和 term的结合 可以唯一标识一条log entry两个在不同server上的log entries有相同的index和term一定存着相同的command。此外除了这两个他们之前的所有entries也都相同所以进一步index和term的结合可以唯一表示一整条log。 第二条如果一个entry是committed那么它之前的所有entries也都是committed。比如entry 5 committed根据1.1前面也都存储在majority了。 那么是如何保证这些特性的呢 是由Append entries consistency check来强制检查实现的。当一个leader向followers发送append entries rpc时里面除了新的log entry还会包含两个值次新log entry的index和term当follower收到rpc的时候只会接受次新log entry能够匹配上的rpc。让我们看个例子leader刚收到z-0然后发送RPC给followers里面将会包含该entry 以及 (term,index) (2,4), follower进行相应的检查上面的这个接收下面的拒绝。
这个一致性检查很重要通过简单的归纳演绎就可以证明出一个新entry只有前面entry匹配的时候才能添加以此类推推出如果一个follower接受了leader的一个log entry那么该follower的log从开始到该entry和leader的log是完全匹配的。 正常状态下的运行到此就讨论完了下面讨论一下leader changes Leader changes 当一个新的leader被选出来的时候它面对的log可能不是那么整齐因为前一个leader可能在完成复制之前就挂掉了。raft并不需要采取特别的清理步骤来解决这个问题只需要正常运行而log修复就在正常运行中完成。为什么不采取特殊措施呢因为new leader来的时候有可能存在一些宕机的server很久才修复好回来即使执行了clean up也很难立即同步好所有logs。所以raft必须设计的正常运行的日志复制必须能达到最终一致性。首先一点raft认为leader的log永远是最新最完整的。leader要做的就是让followers和自己的日志同步上、匹配上。当然在这个过程中新的leader可能会crash反复几次会出现很多繁杂的log entries。
因为前面说过term和index可以唯一标识log所以可以只用这两者来代替log entry。如下图server 4,5当选了term 2 3 4的leader但是出于某种原因没有向外复制log然后挂了并且4,5和123分区了一段时间123 作为term 5 6 7 leader又复制了一些日志最后导致了杂乱的log。但是关键的只有圈出来的这部分loglog entry 1 2 3只有这些才是committed需要维护保存的。其他的即没有应用到状态机也没有返回客户端结果所以不重要。如何server 2 是 term 7 leader最终它会让其他server log与他相同。在讨论如何修复这种凌乱的log之前首先讨论一下安全性。我们如何能确保在这种凌乱的log下我们丢弃添加log但是没有丢掉某些重要的信息并且让系统一直正确地运行下去呢这就是安全性问题 Safety所有做log replication的系统都需要保证的一件事即某个状态机收到并apply了一条log entry就必须保证其他状态机对于该log entry不能apply一个不同的值。考虑到前面raft协议的复制过程该安全性需求等价于任意两个位于相同index的committed entry必须是相同的。为解决这个问题raft实现了一个safety property即如果leader决定某个log entry是committed那么raft将保证该entry将出现在所有未来leader的log中。如果可以让raft满足这个safe property就能够保证上面的safety requirement。具体怎么做的呢
Leaders从不覆写日志条目只会追加写entries要想提交必须在leader的log里面才可能。// 这样其他值就不会提交entries在apply之前必须要committed
这几条共同作用来满足上面的需求。但是前面所讲的raft过程还不足以满足安全性需要就如下面这张图committed-present in future leader’s logs还需要修改raft协议的内容首先是修改一下选举过程保证选到的新leader是最完整的第二修改一下提交策略有些时候可能需要延迟提交直到确保安全之后。 Pick Up-to-Date Leader: 如何选出拥有所有已经提交的log 的leader呢其实我们是无法判断哪个server有所有已提交的logs的因为无法判断哪个entry是已提交的如图假设server 3 不可用了entry 5是否提交取决于是否存储在这个已经不可用的server上。所以我们要做的是尽可能选最可能有最完整已提交entries的candidate当leader 具体的方式是通过比较log所以当一个candidate发送Request vote RPCs的时候需要包含上自己最后一个日志项的index和term,这样可以唯一标识一整条log。当进行投票的server V收到RPC之后会将candidate的log和自己本地的log进行比对看哪个更完整。如果投票者的last term 候选者last term拒绝如果last term相等但是投票者的index更大同样也拒绝除此之外都是认为candidate的log更完整将会进行投票。这样就能保证不管谁嬴得选举都是集群中log最完整的server。 接着我们看一下新的选主方式的实践过程中。第一种是新leader提交了一个当前term的entry例如s1 作为term2的leader在server 3上复制完了entry 4已经majority了然后说committed这样可以安全地apply到状态机。这样为什么是安全的呢因为entry 4一定会出现在未来的leader中比如s4,5都不可能当选leader了一个是因为term一个是因为index。假设s1挂了 s2 s3会成功当选leader完成日志复制。 第二种情况leader尝试提交之前term的entry。这种情况下term 2的leader entry 3只复制了s1 s2就挂了s5因为某些原因没有复制entry 3创建了一些自己本地的entries就挂了。然后term 4 s1又成为了leader,想要同步log所以让s3复制term 2的entry 3这个时刻leader直到entry 3存到了大多数节点可以committed但是entry 3是不安全提交的。原因是假设提交完entry 3,s1又挂了很有可能s5会当选为leader然后同步日志把已经提交的term 2的entry 3 overwrite了。 为了解决这个问题修改了新的提交规则。除了已经存储到majority节点之外还需要至少有一条来自当前leader term的entry已经存到了majority节点才能提交或者说新的leader只有提交过自己当前term的entry之后才能将旧的entries committed。 再看这个例子当完成复制到多数结点之后entry 3也不能提交需要等待entry 4提交才能提交。这样s5就没有机会当选leader了不存在安全隐患。所以Election rules 和 commitment rules 的结合使得Raft协议满足安全性也就是满足一旦一个leader提交entry该entry一定会出现在未来下一个leader的log中以此类推一定出现在未来任何一个leader中。 现在已经讨论完了安全性我们知道leader log永远是正确的完整的最新的那么如何让followers的log 和leader的log 匹配呢首先先看一下log有多种不一致情况follower可能entries确实、如follower abe;c,d,f是存在冗余entries我们要做的就是删除多余无关的entries填补缺失的entries。 Repairing Follower Logs 具体的方法是leader为每一个follower维护一个next index代表着每个follower下一个要写的entry的index新leader当选后初始化都等于leader’s last log index 1图中next index 10 1 11在RPC的时候发送的(term,index)其实就是log[nextindex-1]的term,index当Append Entries consistency check失败的时候将next Index–并再次发送RPCs请求比如一开始将index11的时候拒绝减为10以此类推直到next index变成5然后term和index匹配上了然后就可以写entry 5了以此类推完成A的复制。 对于follower B当替换了一个不一致的log之后会自动将后续的无用log删除。这就是第三部分leader changes的全部内容我们关注了两个问题第一个问题是确保安全性主要是如果选新leader以及怎么提交才是安全的第二个问题是当新leader选出来之后如何让followers和自己的log匹配这个过程主要依靠了Append entries consistency check来实现。 Raft第四部分也是关于leader change的一个问题old leaders可能没有真正死亡比如说现在出现了一个网络分区的情况当前leader短暂的和整个集群断开了连接然后其他servers选出了一个新的leader但是过了一会old leader又重连回来了他并不知道发生了选举和新的leader只会和之前一样把自己当作leader去运行比如说尝试复制日志和client交互。如何阻止呢 我们用Term来解决每一个RPC都要包含上发送者的term接收者接手之后会把该term和自己的当前term进行比较如果sender比较老则拒绝发回包含自己term的responsesender收到后就会step down反之一样。而选举过程恰好是更新了majority server的term而即使old server回来也无法完成大多数共识无法提交log entry。总之如果有什么过时的东西term会发现的。 接下来是第五部分主要讨论一下client如何和系统交互的。client向leader发command然后得到回复。如果不知道谁是leader可以随意发然后会返回client谁是leader重发就行了。leader完成command的logged和committed和executed之后回复client。比较难的地方是如果这个过程中leader crash了怎么办Client会认为leader crash然后向其他server重新发出命令其他server最终将返回一个新leader的地址Client向这个新leader发起request就解决了。这保证了client的一条命令最终都会被执行。
下面是log replication的过程这个过程的任何一个阶段都有可能leader crash 特别需要注意以下这种情况数据到达了leader复制到 (0,all] follower但是leader未收到响应在这种情况下command可能被执行两次。因为leader挂掉之后选的主肯定是包含v3这个log的follower然后再次完成复制和提交执行这个过程中因为client不知道是否成功可能会超时重发而leader也无法分辨是否是相同还是连续两个命令会再次复制提交执行就导致相同命令执行两次。
为了解决这个问题client需要将每一个command和一个唯一的id绑定server会将这个id放在log entry中在接受command之前leader会检查自己的log有没有这个id如果有只需要忽视命令返回之前的结果就行了。这样就实现了幂等性解决重复执行的问题。 最后一部分我们需要一些能够改变系统配置的方法。这里的系统配置主要是指server id network address这决定了到底哪些是集群的大多数。为什么要有成员变更、或者说配置的改变主要是为了替换failed机器或者改变副本因子等等。
首先我们需要意识到不能够直接切换集群的成员配置。如下面的例子Cold是123Cnew是12345我们想要从状态Cold切换到Cnew在这个过程中很难做到同步切换所以可能会出现这样一个阶段server12可以组成old cluster的majority而同时server123可以组成new cluster的majority那么会发生什么这个时间的选主或者复制都会出现问题可能选出两个leader也可能错误提交log。 解决方法就是使用一个两阶段协议来完成这个过程。Raft协议规定首先将旧的成员状态转移到一个叫joint consensus共同一致的过渡状态这种状态的成员组成是old∪new这时候的majority需要old的大多数和new的大多数同时达成。具体流程可以看这张图我们开始的配置叫做Cold然后同别的请求一样client向leader发出请求leader将这种共同一致的配置存到log里即Cold U Cnew,然后向其他follower发送RPC和普通的log replication过程一样唯一的区别是它是立即起作用的当配置log到本地server就会立即把这当作当前的集群配置来用不需要等待提交。Coldnew 什么时候committed的呢即前面说的majority of old and majority of new; 这里在cold起作用的阶段可能有Cold里面的新leader当选但是不影响正确性因为根据log index当选的肯定是包含这条成员变更log的机器当中间态committed整个集群就是在joint consensus下运行的这个时候leader可以成员变更到Cnew与之前一样log然后复制经过一段时间Cnew committed了就完成了成员变更以后的决定的大多数都是看的Cnew了。
一阶段使用两阶段是因为没有对C_old 和C_new 做出限制 C_old 和C_new可以各自形成不相交的majority选出两个Leader。而两阶段过程保证了Cold和Cnew不可能产生没有冲突的两个majority。或者另外一种方法限制每次只允许增加或删除一个成员这样一定无法形成两个不相交的majority同时限制一次成员变更成功之前不允许开始下一次成员变更。 这就是六个部分的全部内容。简单回顾一下第一个leader election我们确保了某个term内最多只有一个server可以当选leader第二部分主要介绍了以下选主之后的正常运行包括接受客户端请求以及日志复制提到了一个重要的一致性检测Append Entries 一致性检测从而证明了index和term能唯一标识log第三部分讨论了leader change带来的两个问题第一个是如何确保安全性即当一个log entry committed他就会一直出现在后面的leader中。还有一致性问题即如何让follower的log和leader log变得相同。第四部分如何保证没真死的旧leader不会影响系统。第五部分简单说了client做些什么以及在leader crash情况下的高可用。最后讨论了如何安全进行成员变更的方法。 分讨论了leader change带来的两个问题第一个是如何确保安全性即当一个log entry committed他就会一直出现在后面的leader中。还有一致性问题即如何让follower的log和leader log变得相同。第四部分如何保证没真死的旧leader不会影响系统。第五部分简单说了client做些什么以及在leader crash情况下的高可用。最后讨论了如何安全进行成员变更的方法。
