草庐IT

分布式系统必须知道的一个共识算法:Raft

悟空聊架构 2023-04-10 原文

一、Raft 概述

​Raft 算法​​​是分布式系统开发首选的​​共识算法​​。比如现在流行 Etcd、Consul。

如果​​掌握​​​了这个算法,就可以较容易地处理绝大部分场景的​​容错​​​和​​一致性​​需求。比如分布式配置系统、分布式 NoSQL 存储等等,轻松突破系统的单机限制。

Raft 算法是通过一切以领导者为准的方式,实现一系列值的共识和各节点日志的一致。

二、Raft 角色

2.1 角色

跟随者(Follower):​​普通群众​​,默默接收和来自领导者的消息,当领导者心跳信息超时的时候,就主动站出来,推荐自己当候选人。

候选人(Candidate):​​候选人​​将向其他节点请求投票 RPC 消息,通知其他节点来投票,如果赢得了大多数投票选票,就晋升当领导者。

领导者(Leader):​​霸道总裁​​,一切以我为准。处理写请求、管理日志复制和不断地发送心跳信息,通知其他节点“我是领导者,我还活着,你们不要”发起新的选举,不用找新领导来替代我。

如下图所示,分别用三种图代表跟随者、候选人和领导者。

角色

三、单节点系统

3.1 数据库服务器

现在我们想象一下,有一个单节点系统,这个节点作为数据库服务器,且存储了一个值为 X。

数据库服务器

3.2 客户端

左边绿色的实心圈就是客户端,右边的蓝色实心圈就是节点 a(Node a)。Term 代表任期,后面会讲到。

客户端

3.3 客户端向服务器发送数据

客户端向单节点服务器发送了一条更新操作,设置数据库中存的值为 8。单机环境下(单个服务器节点),客户端从服务器拿到的值也是 8。一致性非常容易保证。

客户端向服务器发送数据

3.4 多节点如何保证一致性?

但如果有多个服务器节点,怎么保证一致性呢?比如有三个节点:a,b,c。如下图所示。这三个节点组成一个数据库集群。客户端对这三个节点进行更新操作,如何保证三个节点中存的值一致?这个就是分布式一致性问题。Raft 算法就是来解决这个问题的。当然还有其他协议也可以保证,本篇只针对 Raft 算法。

在多节点集群中,在节点故障、分区错误等异常情况下,Raft 算法如何保证在同一个时间,集群中只有一个领导者呢?下面就开始讲解 Raft 算法选举领导者的过程。

四、选举领导过程

4.1 初始状态

初始状态下,集群中所有节点都是跟随者的状态。

如下图所示,有三个节点(Node) a、b、c,任期(Term)都为 0。

初始状态

4.2 成为候选者

Raft 算法实现了随机超时时间的特性,每个节点等待领导者节点心跳信息的超时时间间隔是随机的。比如 A 节点等待超时的时间间隔 150 ms,B 节点 200 ms,C 节点 300 ms。那么 a 先超时,最先因为没有等到领导者的心跳信息,发生超时。如下图所示,三个节点的超时计时器开始运行。

超时时间

当 A 节点的超时时间到了后,A 节点成为候选者,并增加自己的任期编号,Term 值从 0 更新为 1,并给自己投了一票。

  • Node A:Term = 1, Vote Count = 1。
  • Node B:Term = 0。
  • Node C:Term = 0。

成为候选者

4.3 投票

我们来看下候选者如何成为领导者的。

Leader 选举

  • 第一步:节点 A 成为候选者后,向其他节点发送请求投票 RPC 信息,请它们选举自己为领导者。
  • 第二步:节点 B 和 节点 C 接收到节点 A 发送的请求投票信息后,在编号为 1 的这届任期内,还没有进行过投票,就把选票投给节点 A,并增加自己的任期编号。
  • 第三步:节点 A 收到 3 次投票,得到了大多数节点的投票,从候选者成为本届任期内的新的领导者
  • 第四步:节点 A 作为领导者,固定的时间间隔给 节点 B 和节点 C 发送心跳信息,告诉节点 B 和 C,我是领导者,组织其他跟随者发起新的选举。
  • 第五步:节点 B 和节点 C 发送响应信息给节点 A,告诉节点 A 我是正常的。

4.4 任期

英文单词是 term,领导者是有任期的。

  • 自动增加:跟随者在等待领导者心跳信息超时后,推荐自己为候选人,会增加自己的任期号,如上图所示,节点 A 任期为 0,推举自己为候选人时,任期编号增加为 1。
  • 更新为较大值:当节点发现自己的任期编号比其他节点小时,会更新到较大的编号值。比如节点 A 的任期为 1,请求投票,投票消息中包含了节点 A 的任期编号,且编号为 1,节点 B 收到消息后,会将自己的任期编号更新为 1。
  • 恢复为跟随者:如果一个候选人或者领导者,发现自己的任期编号比其他节点小,那么它会立即恢复成跟随者状态。这种场景出现在分区错误恢复后,任期为 3 的领导者受到任期编号为 4 的心跳消息,那么前者将立即恢复成跟随者状态。
  • 拒绝消息:如果一个节点接收到较小的任期编号值的请求,那么它会直接拒绝这个请求,比如任期编号为 6 的节点 A,收到任期编号为 5 的节点 B 的请求投票 RPC 消息,那么节点 A 会拒绝这个消息。

4.5 选举规则

  • 一个任期内,领导者一直都会领导者,直到自身出现问题(如宕机),或者网络问题(延迟),其他节点发起一轮新的选举。
  • 在一次选举中,每一个服务器节点最多会对一个任期编号投出一张选票,投完了就没了。

4.6 大多数

假设一个集群由 N 个节点组成,那么大多数就是至少 N/2+1。例如:3 个节点的集群,大多数就是 2。

4.7 心跳超时

为了防止多个节点同时发起投票,会给每个节点分配一个随机的选举超时时间。这个时间内,节点不能成为候选者,只能等到超时。比如上述例子,节点 A 先超时,先成为了候选者。这种巧妙的设计,在大多数情况下只有一个服务器节点先发起选举,而不是同时发起选举,减少了因选票瓜分导致选举失败的情况。

成为候选者

五、领导者故障

如果领导者节点出现故障,则会触发新的一轮选举。如下图所示,领导者节点 A 发生故障,节点 B 和 节点 C 就会重新选举 Leader。

领导者故障

  • 第一步 :节点 A 发生故障,节点 B 和节点 C 没有收到领导者节点 A 的心跳信息,等待超时。
  • 第二步:节点 C 先发生超时,节点 C 成为候选人
  • 第三步:节点 C 向节点 A 和节点 B 发起请求投票信息。
  • 第四步:节点 C 响应投票,将票投给了 C,而节点 A 因为发生故障了,无法响应 C 的投票请求。
  • 第五步:节点 C 收到两票(大多数票数),成为领导者
  • 第六步:节点 C 向节点 A 和 B 发送心跳信息,节点 B 响应心跳信息,节点 A 不响应心跳信息,因为 A 故障了。

总结

Raft 算法通过以下几种方式来进行领导选举,保证了一个任期只有一位领导,极大减少了选举失败的情况。

  • 任期
  • 领导者心跳信息
  • 随机选举超时时间
  • 先来先服务的投票原则
  • 大多数选票原则

本篇通过动图的方式来讲解 Raft 算法如何选举领导者,更容易理解和消化。

有关分布式系统必须知道的一个共识算法:Raft的更多相关文章

  1. ruby - 使用 Vim Rails,您可以创建一个新的迁移文件并一次性打开它吗? - 2

    使用带有Rails插件的vim,您可以创建一个迁移文件,然后一次性打开该文件吗?textmate也可以这样吗? 最佳答案 你可以使用rails.vim然后做类似的事情::Rgeneratemigratonadd_foo_to_bar插件将打开迁移生成的文件,这正是您想要的。我不能代表textmate。 关于ruby-使用VimRails,您可以创建一个新的迁移文件并一次性打开它吗?,我们在StackOverflow上找到一个类似的问题: https://sta

  2. ruby-on-rails - Rails - 一个 View 中的多个模型 - 2

    我需要从一个View访问多个模型。以前,我的links_controller仅用于提供以不同方式排序的链接资源。现在我想包括一个部分(我假设)显示按分数排序的顶级用户(@users=User.all.sort_by(&:score))我知道我可以将此代码插入每个链接操作并从View访问它,但这似乎不是“ruby方式”,我将需要在不久的将来访问更多模型。这可能会变得很脏,是否有针对这种情况的任何技术?注意事项:我认为我的应用程序正朝着单一格式和动态页面内容的方向发展,本质上是一个典型的网络应用程序。我知道before_filter但考虑到我希望应用程序进入的方向,这似乎很麻烦。最终从任何

  3. ruby-on-rails - 渲染另一个 Controller 的 View - 2

    我想要做的是有2个不同的Controller,client和test_client。客户端Controller已经构建,我想创建一个test_clientController,我可以使用它来玩弄客户端的UI并根据需要进行调整。我主要是想绕过我在客户端中内置的验证及其对加载数据的管理Controller的依赖。所以我希望test_clientController加载示例数据集,然后呈现客户端Controller的索引View,以便我可以调整客户端UI。就是这样。我在test_clients索引方法中试过这个:classTestClientdefindexrender:template=>

  4. ruby-on-rails - 如果 Object::try 被发送到一个 nil 对象,为什么它会起作用? - 2

    如果您尝试在Ruby中的nil对象上调用方法,则会出现NoMethodError异常并显示消息:"undefinedmethod‘...’fornil:NilClass"然而,有一个tryRails中的方法,如果它被发送到一个nil对象,它只返回nil:require'rubygems'require'active_support/all'nil.try(:nonexisting_method)#noNoMethodErrorexceptionanymore那么try如何在内部工作以防止该异常? 最佳答案 像Ruby中的所有其他对象

  5. ruby - 为什么 SecureRandom.uuid 创建一个唯一的字符串? - 2

    关闭。这个问题需要detailsorclarity.它目前不接受答案。想改进这个问题吗?通过editingthispost添加细节并澄清问题.关闭8年前。Improvethisquestion为什么SecureRandom.uuid创建一个唯一的字符串?SecureRandom.uuid#=>"35cb4e30-54e1-49f9-b5ce-4134799eb2c0"SecureRandom.uuid方法创建的字符串从不重复?

  6. ruby-on-rails - Rails - 从另一个模型中创建一个模型的实例 - 2

    我有一个正在构建的应用程序,我需要一个模型来创建另一个模型的实例。我希望每辆车都有4个轮胎。汽车模型classCar轮胎模型classTire但是,在make_tires内部有一个错误,如果我为Tire尝试它,则没有用于创建或新建的activerecord方法。当我检查轮胎时,它没有这些方法。我该如何补救?错误是这样的:未定义的方法'create'forActiveRecord::AttributeMethods::Serialization::Tire::Module我测试了两个环境:测试和开发,它们都因相同的错误而失败。 最佳答案

  7. ruby - 用 Ruby 编写一个简单的网络服务器 - 2

    我想在Ruby中创建一个用于开发目的的极其简单的Web服务器(不,不想使用现成的解决方案)。代码如下:#!/usr/bin/rubyrequire'socket'server=TCPServer.new('127.0.0.1',8080)whileconnection=server.acceptheaders=[]length=0whileline=connection.getsheaders想法是从命令行运行这个脚本,提供另一个脚本,它将在其标准输入上获取请求,并在其标准输出上返回完整的响应。到目前为止一切顺利,但事实证明这真的很脆弱,因为它在第二个请求上中断并出现错误:/usr/b

  8. ruby - 一个 YAML 对象可以引用另一个吗? - 2

    我想让一个yaml对象引用另一个,如下所示:intro:"Hello,dearuser."registration:$introThanksforregistering!new_message:$introYouhaveanewmessage!上面的语法只是它如何工作的一个例子(这也是它在thiscpanmodule中的工作方式。)我正在使用标准的ruby​​yaml解析器。这可能吗? 最佳答案 一些yaml对象确实引用了其他对象:irb>require'yaml'#=>trueirb>str="hello"#=>"hello"ir

  9. ruby - 分布式事务和队列,ruby,erlang,scala - 2

    我有一个涉及多台机器、消息队列和事务的问题。因此,例如用户点击网页,点击将消息发送到另一台机器,该机器将付款添加到用户的帐户。每秒可能有数千次点击。事务的所有方面都应该是容错的。我以前从未遇到过这样的事情,但一些阅读表明这是一个众所周知的问题。所以我的问题。我假设安全的方法是使用两阶段提交,但协议(protocol)是阻塞的,所以我不会获得所需的性能,我是否正确?我通常写Ruby,但似乎Redis之类的数据库和Rescue、RabbitMQ等消息队列系统对我的帮助不大——即使我实现某种两阶段提交,如果Redis崩溃,数据也会丢失,因为它本质上只是内存。所有这些让我开始关注erlang和

  10. ruby - Rails 关联 - 同一个类的多个 has_one 关系 - 2

    我的问题的一个例子是体育游戏。一场体育比赛有两支球队,一支主队和一支客队。我的事件记录模型如下:classTeam"Team"has_one:away_team,:class_name=>"Team"end我希望能够通过游戏访问一个团队,例如:Game.find(1).home_team但我收到一个单元化常量错误:Game::team。谁能告诉我我做错了什么?谢谢, 最佳答案 如果Gamehas_one:team那么Rails假设您的teams表有一个game_id列。不过,您想要的是games表有一个team_id列,在这种情况下

随机推荐