专栏首页程序员升级之路不了解Raft算法敢说自己研究过分布式?

不了解Raft算法敢说自己研究过分布式?

R一、Raft算法介绍

Raft是一种“共识”算法,共识的含义是保证所有的参与者都有相同的认知,简单来说就是如何做到强一致。

“共识”包含服务器之间及客户端和服务端两方面:

1、服务器之间

指的是所有服务器要达成“共识”,打个比方一个KV系统像Redis,如果服务端是3个节点:A、B、C的集群,客户端先发出一个set key1 a的命令落在A节点上,然后发出 set key1 b落在B节点上,最后应该在所有服务器上执行get key1都应该得到a;

2、 客户端和服务端之间

还是回到上面的例子,不能客户端执行 set key1 a的命令,服务端返回成功了,客户端就认为这里是成功了,中间不能因为网络或其它原因客户端取key1的时候反回空的情况。

“共识”算法主要解决分布式系统的一致性的问题,目前相关的算法有:

1、Paxos算法

这个是最早的,也是非常复杂的,说实话我看了好多文章,也只是大概懂了,细节还是不太清楚,还是要观看一些实现代码才能加深了解;

2、Raft算法

就是我们今天要介绍的,由斯坦福大学的Diego Ongaro和John Ousterhout在2014年提出,在证明了算法的正确性之外,还提供了相关实现及参考代码,所以媒体一直宣传这个算法比Paxos要更容易理解;

3、ZAB算法

Zookeeper使用的算法,算是Paxos算法的一个变种,有兴趣的可以到 Apache官网学习下,结合Zookeeper源码学习下。

二、Raft算法应用场景及案例

上面介绍了分布式相关算法,Raft相对来说比较容易上手,如果要深入研究,Paxox是避免不了的;注意是相对简单,因为进入分析之后你会发现远没你想像的简单,以我目前学习进度看,学习快3周时间才大概了解了一些细节。

学习的方式是先看官方的介绍,以下是其官方网站:

https://raft.github.io/raft.pdf

还有个动画介绍的:

http://thesecretlivesofdata.com/raft/

当然还有中文版的,搜索下raft paper中文版就可以了。

目前开源的实现也不少:

Etcd(Go语言实现)

PingCAP(Rust语言,Codis作者所在公司)

Soft-Jraft(Java语言,阿里开源)

上面几个都是大公司实现的,可以用在生产上,功能也比较全,代码相对来说复杂些,如果先只想简单搞个Demo分析下,可以看以下几个:

1、百度工程师开源的Java实现

https://github.com/wenweihu86/raft-java

2、支付宝工程师实现

也是Java写的,不过功能比较少,没有PreVote等功能,作者还出了本书:《分布式一致性算法开发实战》,建议带着书学习下:

https://github.com/xnnyygn/xraft

以下是个人学习路线仅供参考:先看论文,即理论,然后跑代码,然后再反过来看理论,最后到了你不用看论文就知道相应规则就可以熟练掌握了。

三、Raft算法整体介绍

因Raft算法内容比较多,后面会分几篇介绍,这篇先大概介绍下整体的东西。

官方将Raft算法分为以下几块:选举、日志复制、安全性3大块,从实现的角度分:选举、日志、新节点加入。

另外如果要实现一个完整的应用的话,还要实现状态机的部分;什么是状态机呢,状态机指系统/对象本身有多种状态,然后各种状态分发生切换、转变,其实大部分分布式系统都可以转移为状态机,然后各节点之间以一致的步骤转换状态,大家的状态就是一致了,对应用来说就是强一致了。

还是以前面的redis为例,假设客户端发过来的命令流如下:

set key1 a 状态:key1:a

set key2 b 状态:key1:a, key2:b

即客户端每1次操作都会引起服务端状态的改变,然后把整个修改当成一个序列,则整个就是状态机了。

回到Raft算法,我们看下每块要解决的问题:

1、选举

Raft算法只支持单主,即任何时候只能从主上进行证读写操作,所以选举要解决以下问题:

当前谁是主节点;

如何保证一定会只选出一个主节点;

如何快速、正确的感知主节点挂掉;

如何快速的选出主节点;

如何保证一定会选出主节点,不会无限循环选举;

如何保证主节点的数据是最新的;

2、日志

Raft算法通过日志达到一致的,日志部分要解决以下问题:

谁的日志最新;

主节点是如何将日志复制到其它节点;

如何保证日志复制的正确性,即不会串,不会错;

新节点加入日志如何复制;

各节点日志的一致性是如何实现的;

3、新节点加入

新节点加入集群不会出现脑裂;

配置如何做到强一致,中间会出现短暂不一致,是怎样不影响集群正常工作的;

本文分享自微信公众号 - 程序员升级之路(gh_1fab42db66cb),作者:刘江华

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

原始发表时间:2020-10-09

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Raft算法之客户端交互篇

    Raft算法规定客户端将所有请求发送给Leader。客户端启动的时候,如何知道哪一个节点是Leader呢?具体办法是客户端随机挑选一个服务器进行通信,如果客户端...

    心平气和
  • Nginx配置不当险酿S0

    线上某服务前端负载均衡为Nginx,后端为Java服务,某天突然大量报服务不可用,具体错误如下:

    心平气和
  • 从一次线上故障来看redis删除机制

    公司去年上线一个抽奖系统,主要用来拉新、提升流量,所有新注册的用户在指定时间都可以抽奖,为了保证安全性,程序中做了频率限制,每个用户30秒只能抽1次,...

    心平气和
  • Java红黑树小知识

    宇宙之一粟
  • 查询与引用函数——offset函数

    今天要跟大家分享的是一个强大的查询与引用函数——offset函数! OFFSET函数的语法参数相对比较多,但是因为参数位置和函数都比较固定,所以只要能够理解各自...

    数据小磨坊
  • 前端应该如何准备数据结构和算法?

    据我了解,前端程序员有相当一部分不是科班出身,以至于对“数据结构”和“算法”的基础概念都不是很清晰,这直接导致很多人在看到有关这部分的内容就会望而却步。

    ConardLi
  • 前端应该如何准备数据结构和算法?

    据我了解,前端程序员有相当一部分不是科班出身,以至于对“数据结构”和“算法”的基础概念都不是很清晰,这直接导致很多人在看到有关这部分的内容就会望而却步。

    Nealyang
  • 一文梳理面试中的数据结构与算法

    据我了解,相当一部分同学不是科班出身,以至于对“数据结构”和“算法”的基础概念都不是很清晰,这直接导致很多人在看到有关这部分的内容就会望而却步。

    Datawhale
  • 前端应该如何准备数据结构和算法?

    据我了解,前端程序员有相当一部分不是科班出身,以至于对“数据结构”和“算法”的基础概念都不是很清晰,这直接导致很多人在看到有关这部分的内容就会望而却步。

    lucifer210
  • LeetCode 993. 二叉树的堂兄弟节点(层序遍历)

    在二叉树中,根节点位于深度 0 处,每个深度为 k 的节点的子节点位于深度 k+1 处。

    Michael阿明

扫码关注云+社区

领取腾讯云代金券