专栏首页普通程序员10分钟弄懂Raft算法

10分钟弄懂Raft算法

分布式系统在极大提高可用性、容错性的同时,带来了一致性问题(CAP理论)。Raft算法能够解决分布式系统环境下的一致性问题。

我们熟悉的ETCD注册中心就采用了这个算法;你现在看的这篇微信公众号文章,也是保存在基于Raft算法的高可用存储服务器中。

没有耐心看文字,就直接拉到第四章

一、Raft算法是什么?

过去,Paxos一直是分布式协议的标准,但是Paxos难于理解,更难以实现,Google的分布式锁系统Chubby作为Paxos实现曾经遭遇到很多坑。后来斯坦福大学提出了Raft算法。

Raft是用于管理复制日志的一致性算法。它的效果相当于(multi-)Paxos,跟Paxos一样高效,但结构与Paxos不同。这使得Raft比Paxos更容易理解,也为构建实用系统提供了更好的基础。

下图是斯坦福大学的Diego Ongaro和John Ousterhout在《In Search of an Understandable Consensus Algorithm》一文(提出Raft算法的论文)中,依据Raft学习难度的实验数据绘制的。实验对象是斯坦福大学和加州大学伯克利分校的高年级本科生和研究生。这些天才也觉得Paxos很难。所以对于大多数人看不懂Paxos算法是很正常的,看不懂Raft原理也不奇怪。

二、什么是一致性(Consensus)

一致性是分布式系统容错的基本问题。一致性涉及多个服务器状态(Values)达成一致。 一旦他们就状态做出决定,该决定就是最终决定。 当大多数服务器可用时,典型的一致性算法会取得进展。例如,即使2台服务器发生故障,5台服务器的集群也可以继续运行。 如果更多服务器失败,它们将停止进展(但永远不会返回错误的结果)。

三、Raft算法

论文Raft算法介绍的章节包括6个部分,了解个大概就行,然后拉到本文后边,有个可操作的游戏辅助理解这个算法。

1、Raft基础知识

Raft集群包含多个服务器,5个服务器是比较典型的,允许系统容忍两个故障。在任何给定时间,每个服务器都处于以下三种状态之一,领导者(Leader),追随者(Follower)或候选人(Candidate)。 这几个状态见可以相互转换。

Leader:处理所有客户端交互,日志复制等,一般一次只有一个Leader

Follower:类似选民,完全被动

Candidate:类似Proposer律师,可以被选为一个新的领导人

2、选举Leader

Raft使用心跳机制来触发领导者选举。 当服务器启动时,它们以Follower的身份开始。 只要服务器从Leader或Candidate接收到有效的RPC请求,服务器就会保持Follower状态。 Leader向所有Follower发送定期心跳(不带日志条目的AppendEntries RPC)以保持其权限。 如果一个Follower在称为选举超时的一段时间内没有接到任何通信,该Follower认为没有可行的领导者并开始选举新的Leader。

3、日志复制

一旦Leader当选,它就开始为客户请求提供服务。每个客户端请求包含由复制状态机执行的命令。Leader将命令作为新条目附加到其日志,然后并行地向每个其他服务器发出AppendEntries RPC以复制条目。当条目被安全地复制时,Leader将条目应用于其状态机并将该执行的结果返回给客户端。如果Follower崩溃或运行缓慢,或者网络数据包丢失,Leader将无限期地重试AppendEntries RPC(即使它已经响应客户端),直到所有Follower最终存储所有日志条目。(后边游戏中有个request命令菜单,就是模仿客户端请求的)

除了以上3点,文章还重点描述了安全、Follower和Candidate崩溃、时间和可用性三个方面。

四、可视化的Raft算法

github上有一个帮助大家理解算法的页面,地址是https://raft.github.io/raftscope/index.html

建议用电脑浏览器打开,如果在手机微信里打开,需要选择“访问原网页”

我截了一个运行状态的截图,左侧显示五台服务器,右侧显示日志。

在服务器图标上点击鼠标右键会出现操作菜单。操作菜单对应服务节点的状态改变,其中request模拟客户端请求服务器集群执行任务,会在右边产生日志。

多操作一会,一定能够理解Raft算法是怎么运行的!

五、总结

Raft算法具备强一致、高可靠、高可用等优点,具体体现在:

强一致性:虽然所有节点的数据并非实时一致,但Raft算法保证Leader节点的数据最全,同时所有请求都由Leader处理,所以在客户端角度看是强一致性的。

高可靠性:Raft算法保证了Committed的日志不会被修改,State Matchine只应用Committed的日志,所以当客户端收到请求成功即代表数据不再改变。Committed日志在大多数节点上冗余存储,少于一半的磁盘故障数据不会丢失。

高可用性:从Raft算法原理可以看出,选举和日志同步都只需要大多数的节点正常互联即可,所以少量节点故障或网络异常不会影响系统的可用性。即使Leader故障,在选举超时到期后,集群自发选举新Leader,无需人工干预,不可用时间极小。但Leader故障时存在重复数据问题,需要业务去重或幂等性保证。

高性能:与必须将数据写到所有节点才能返回客户端成功的算法相比,Raft算法只需要大多数节点成功即可,少量节点处理缓慢不会延缓整体系统运行。

本文分享自微信公众号 - 普通程序员(farmerbrag),作者:封宇

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-02-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 10分钟搞懂蚁群算法

    蚂蚁几乎没有视力,但他们却能够在黑暗的世界中找到食物,而且能够找到一条从洞穴到食物的最短路径。它们是如何做到的呢? 蚂蚁寻找食物的过程 单只蚂蚁的行为及其简单...

    大闲人柴毛毛
  • 5分钟弄懂Docker

    尽管之前久闻Docker的大名了,但是天资愚钝,对其到底是个啥东西一直摸不清,最近花了一段时间整理了一下,算是整理出一点头绪来。 官网的介绍是这样的: Do...

    Albert陈凯
  • 30分钟带你理解 Raft 算法

    官方定义: A Distributed Coordination Service for Distributed Applications。本质:基于内存的 K...

    Yano_nankai
  • 10分钟搞懂TensorBoard用法

    基本用法 启动采集器,将运行session环境内的参数都保存到文件里,后续就可以用 with tf.Session() as sess: sess.run...

    linxinzhe
  • 分分钟了解弄懂JavaScript闭包

    有权访问另一个函数作用域内变量的函数都是闭包。这里 couter 函数访问了构造函数 a 里面的变量 n,所以形成了一个闭包。 再来看一段代码:

    Javanx
  • Raft 算法分析

    官方定义: A Distributed Coordination Service for Distributed Applications。本质:基于内存的 K...

    Yano_nankai
  • 10分钟搞懂 vuex

      这个状态我们可以理解为在data中的属性,需要共享给其他组件使用的部分。   也就是说,是我们需要共享的data,使用vuex进行统一集中式的管理。

    我不是费圆
  • 30分钟彻底弄懂flex布局

    在这篇文章里,想说说flex布局的属性语法及其细节。那么网上也有不少flex布局的教程,为什么又要再写一篇?

    elson
  • 五分钟完全弄懂C#特性

    在工作或者学习中,难免或多或少的接触到特性这个东西,可能你不太清楚什么是特性,那么我给大家举两个例子 [Obsolete],[HttpGet],[HttpPos...

    zls365
  • 两分钟弄懂对称二叉树

    大家好呀,我是吴师兄,今天照例来更新一道 LeetCode 算法题,根据以往数据来看,这类文章的打开率普遍不高,一般在三四千左右,远远低于水文或者热点文一两万的...

    五分钟学算法
  • 一分钟搞懂的算法之BPE算法

    昨天总结实验数据分析的时候发现一个机器翻译的其中的一个脚本,其中用到的算法就是BPE算法,刚开始感觉很高大上的,因为总是听到带上算法帽子的东西就觉得666。等自...

    zenRRan
  • 条分缕析 Raft 算法

    Raft 的目标(或者说是分布式共识算法的目标)是:保证 log 完全相同地复制到多台服务器上。

    PingCAP
  • 10分钟看懂Docker和K8S

    2010年,几个搞IT的年轻人,在美国旧金山成立了一家名叫“dotCloud”的公司。

    鲜枣课堂
  • 10分钟看懂Docker和kubernetes

    2010年,几个搞IT的年轻人,在美国旧金山成立了一家名叫“dotCloud”的公司。

    kubernetes中文社区
  • 10分钟看懂Docker和K8S

    2010年,几个搞IT的年轻人,在美国旧金山成立了一家名叫“dotCloud”的公司。

    用户6543014
  • 一文弄懂七种排序算法

    本文介绍了七种经典排序算法,包括冒泡排序,选择排序,插入排序,希尔排序,归并排序,快速排序以及堆排序,并且讨论了各种算法的进一步改进,在文章最后还对所有算法的时...

    zhayujie
  • TiKV 源码解析系列文章(二)raft-rs proposal 示例情景分析

    本文为 TiKV 源码解析系列的第二篇,按照计划首先将为大家介绍 TiKV 依赖的周边库 raft-rs 。raft-rs 是 Raft 算法的 Rust 语言...

    PingCAP
  • 一致性协议浅析:从逻辑时钟到Raft

    春节在家闲着没事看了几篇论文,把一致性协议的几篇论文都过了一遍。在看这些论文之前,我一直有一些疑惑,比如同样是有Leader和两阶段提交,Zookeeper的Z...

    王知无-import_bigdata
  • 10 分钟看懂分布式事务

    什么是分布式事务 问题的引出 先看一张图,一个电商平台的架构图。 ? 对于用户来说的一个创建订单的过程,背后很可能跨越了多个应用服务。涉及诸如:订单、库存、...

    linxinzhe

扫码关注云+社区

领取腾讯云代金券