转载:分布式学习八:Raft 算法

本文涉及的产品
日志服务 SLS,月写入数据量 50GB 1个月
简介: 转载:分布式学习八:Raft 算法

前言

我们之前讲述了 Paxos 一致性算法,虽然楼主尝试用最简单的算法来阐述,但仍然还是有点绕。楼主最初怀疑自己太笨,后来才直到,该算法的晦涩难懂不是只有我一个人这么认为,而是国际公认!

所以 Paxos 算法在 1990 就发表出来,但却得不到运用。真正的名声大噪还是在兰伯特使用 “更简单” 的方式重写了一篇论文才开始。

这些和今天说的 Raft 有什么关系呢?

答:Raft 也是一个一致性算法,和 Paxos 目标相同。但他还有另一个名字:易于理解的一致性算法。

也就是说,他的目标就是成为一个易于理解的一致性算法。以替代 Paxos 的晦涩难懂。

那我们就开始讲讲 Raft 算法吧!

1. 什么是 Raft 算法

首先说什么是 Raft 算法:Raft 是一种为了管理复制日志的一致性算法。

什么是一致性呢?

Raft 的论文这么说的:一致性算法允许一组机器像一个整体一样工作,即使其中一些机器出现故障也能够继续工作下去。

这里的一致性针对分布式系统。

什么是管理日志呢?

一致性算法是从复制状态机的背景下提出的,复制状态机通常都是基于复制日志实现的,这个日志可以理解为一个比喻,相当于一个指令。

关于状态机的描述:

多个节点上,从相同的初始状态开始,执行相同的一串命令,产生相同的最终状态。实际上,与其说是一致,其实可以泛化为分布式的两个节点状态存在某种约束。

复制状态机通常都是基于复制日志实现的,保证复制日志相同就是一致性算法的工作了。

典型应用就是一个独立的的复制状态机去管理领导选举和存储配置信息并且在领导人宕机的情况下也要存活下来。比如 Chubby 和 ZooKeeper。

对于 Raft 更重要的应该是 易于理解。从 Raft 的论文题目就可以看出:In Search of an Understandable Consensus Algorithm (Extended Version)。这里的易于理解是相对于 Paxos 的,在他的论文中,和 Paxos 做了大量针对 易于理解 的对比和统计测试。

从楼主阅读论文的过程中来看,Raft 相较于 Paxos 确实更易于理解。为了提升可理解性,Raft 将一致性算法分解成了几个关键模块,例如领导人选举、日志复制和安全性。

而和一致性最相关的就是前面 2 个模块:领导人选举和日志复制。

2. 领导人选举

Raft 通过选举一个高贵的领导人,然后给予他全部的管理复制日志的责任来实现一致性。

而每个 server 都可能会在 3 个身份之间切换:

  • 领导者
  • 候选者
  • 跟随者

而影响他们身份变化的则是 选举

当所有服务器初始化的时候,都是 跟随者,这个时候需要一个 领导者,所有人都变成 候选者,直到有人成功当选 领导者

角色轮换如下图:

网络异常,图片无法展示
|

角色变化图

而领导者也有宕机的时候,宕机后引发新的 选举,所以,整个集群在选举和正常运行之间切换,具体如下图:

网络异常,图片无法展示
|

image.png

从上图可以看出,选举和正常运行之间切换,但请注意, 上图中的 term 3 有一个地方,后面没有跟着 正常运行 阶段,为什么呢?

答:当一次选举失败(比如正巧每个人都投了自己),就执行一次 加时赛,每个 Server 会在一个随机的时间里重新投票,这样就能保证不冲突了。所以,当 term 3 选举失败,等了几十毫秒,执行 term 4 选举,并成功选举出领导人。

接着,领导者周期性的向所有跟随者发送心跳包来维持自己的权威。如果一个跟随者在一段时间里没有接收到任何消息,也就是选举超时,那么他就会认为系统中没有可用的领导者,并且发起选举以选出新的领导者。

要开始一次选举过程,跟随者先要增加自己的当前任期号并且转换到候选人状态。然后请求其他服务器为自己投票。那么会产生 3 种结果:

a. 自己成功当选

b. 其他的服务器成为领导者

c. 僵住,没有任何一个人成为领导者

注意:

  1. 每一个 server 最多在一个任期内投出一张选票(有任期号约束),先到先得。
  2. 要求最多只能有一个人赢得选票。
  3. 一旦成功,立即成为领导人,然后广播所有服务器停止投票阻止新得领导产生。

僵住怎么办? Raft 通过使用随机选举超时时间(例如 150 - 300 毫秒)的方法将服务器打散投票。每个候选人在僵住的时候会随机从一个时间开始重新选举。

以上,就是 Raft 所有关于领导选举的策略。

3. 日志复制

一旦一个领导人被选举出来,他就开始为客户端提供服务。

客户端发送日志给领导者,随后领导者将日志复制到其他的服务器。如果跟随者故障,领导者将会尝试重试。直到所有的跟随者都成功存储了所有日志。

下图表示了当一个客户端发送一个日志给领导者,随后领导者复制给跟随者的整个过程。

网络异常,图片无法展示
|

image.png

4 个步骤:

  1. 客户端提交
  2. 复制数据到所有跟随者
  3. 跟随者回复 确认收到
  4. 领导者回复客户端和所有跟随者 确认提交

可以看到,直到第四步骤,整个事务才会达成。中间任何一个步骤发生故障,都不会影响日志一致性。

4. 总结

总结一下本文吧:

Raft 算法如同他的论文名字一样:寻找一种易于理解的一致性算法,这里的 易于理解 是相对于 Paxos 的,的确,Paxos 实在过于复杂了。

而如何实现易于理解?

答:Raft 将一致性算法分成了2部分:领导选举,日志复制。

领导选举基于一个随机的时间来保证不会冲突(如果冲突的话)。

而日志复制则类似于 2PC。

通常 5 个节点,只要不超过 2 个节点死亡都不会影响系统的运行。保证了系统的可用性,通过领导者的日志复制,实现了系统的一致性。

似乎 CAP 定理已经不起作用了,当然这又是一个重大的话题。

最后,以 Raft 论文的结尾结束本位:

算法的设计通常会把正确性,效率或者简洁作为主要的目标。尽管这些都是很有意义的目标,但是我们相信,可理解性也是一样的重要。在开发者把算法应用到实际的系统中之前,这些目标没有一个会被实现,这些都会必然的偏离发表时的形式。除非开发人员对这个算法有着很深的理解并且有着直观的感觉,否则将会对他们而言很难在实现的时候保持原有期望的特性。

引用

寻找一种易于理解的一致性算法(扩展版)Raft 中文翻译

Raft 英文原文

Raft 为什么是更易理解的分布式一致性算法

本文转载:https://www.jianshu.com/p/2a22ed3d0107

相关实践学习
【涂鸦即艺术】基于云应用开发平台CAP部署AI实时生图绘板
【涂鸦即艺术】基于云应用开发平台CAP部署AI实时生图绘板
目录
相关文章
|
4月前
|
NoSQL 算法 安全
分布式锁—1.原理算法和使用建议
本文主要探讨了Redis分布式锁的八大问题,包括非原子操作、忘记释放锁、释放其他线程的锁、加锁失败处理、锁重入问题、锁竞争问题、锁超时失效及主从复制问题,并提供了相应的优化措施。接着分析了Redis的RedLock算法,讨论其优缺点以及分布式专家Martin对其的质疑。此外,文章对比了基于Redis和Zookeeper(zk)的分布式锁实现原理,包括获取与释放锁的具体流程。最后总结了两种分布式锁的适用场景及使用建议,指出Redis分布式锁虽有性能优势但模型不够健壮,而zk分布式锁更稳定但部署成本较高。实际应用中需根据业务需求权衡选择。
|
6月前
|
算法 数据可视化 开发者
为什么要学习数据结构与算法
今天,我向大家介绍一门非常重要的课程——《数据结构与算法》。这门课不仅是计算机学科的核心,更是每一位开发者从“小白”迈向“高手”的必经之路。
为什么要学习数据结构与算法
|
8月前
|
负载均衡 算法
架构学习:7种负载均衡算法策略
四层负载均衡包括数据链路层、网络层和应用层负载均衡。数据链路层通过修改MAC地址转发帧;网络层通过改变IP地址实现数据包转发;应用层有多种策略,如轮循、权重轮循、随机、权重随机、一致性哈希、响应速度和最少连接数均衡,确保请求合理分配到服务器,提升性能与稳定性。
1651 11
架构学习:7种负载均衡算法策略
|
7月前
|
运维 NoSQL 算法
【📕分布式锁通关指南 04】redis分布式锁的细节问题以及RedLock算法原理
本文深入探讨了基于Redis实现分布式锁时遇到的细节问题及解决方案。首先,针对锁续期问题,提出了通过独立服务、获取锁进程自己续期和异步线程三种方式,并详细介绍了如何利用Lua脚本和守护线程实现自动续期。接着,解决了锁阻塞问题,引入了带超时时间的`tryLock`机制,确保在高并发场景下不会无限等待锁。最后,作为知识扩展,讲解了RedLock算法原理及其在实际业务中的局限性。文章强调,在并发量不高的场景中手写分布式锁可行,但推荐使用更成熟的Redisson框架来实现分布式锁,以保证系统的稳定性和可靠性。
296 0
【📕分布式锁通关指南 04】redis分布式锁的细节问题以及RedLock算法原理
|
8月前
|
存储 人工智能 算法
解锁分布式文件分享的 Java 一致性哈希算法密码
在数字化时代,文件分享成为信息传播与协同办公的关键环节。本文深入探讨基于Java的一致性哈希算法,该算法通过引入虚拟节点和环形哈希空间,解决了传统哈希算法在分布式存储中的“哈希雪崩”问题,确保文件分配稳定高效。文章还展示了Java实现代码,并展望了其在未来文件分享技术中的应用前景,如结合AI优化节点布局和区块链增强数据安全。
|
8月前
|
消息中间件 算法 调度
分布式系统学习10:分布式事务
本文是小卷关于分布式系统架构学习系列的第13篇,重点探讨了分布式事务的相关知识。随着业务增长,单体架构拆分为微服务后,传统的本地事务无法满足需求,因此需要引入分布式事务来保证数据一致性。文中详细介绍了分布式事务的必要性、实现方案及其优缺点,包括刚性事务(如2PC、3PC)和柔性事务(如TCC、Saga、本地消息表、MQ事务、最大努力通知)。同时,还介绍了Seata框架作为开源的分布式事务解决方案,提供了多种事务模式,简化了分布式事务的实现。
332 5
|
8月前
|
NoSQL 关系型数据库 MySQL
分布式系统学习9:分布式锁
本文介绍了分布式系统中分布式锁的概念、实现方式及其应用场景。分布式锁用于在多个独立的JVM进程间确保资源的互斥访问,具备互斥、高可用、可重入和超时机制等特点。文章详细讲解了三种常见的分布式锁实现方式:基于Redis、Zookeeper和关系型数据库(如MySQL)。其中,Redis适合高性能场景,推荐使用Redisson库;Zookeeper适用于对一致性要求较高的场景,建议基于Curator框架实现;而基于数据库的方式性能较低,实际开发中较少使用。此外,还探讨了乐观锁和悲观锁的区别及适用场景,并介绍了如何通过Lua脚本和Redis的`SET`命令实现原子操作,以及Redisson的自动续期机
864 7
|
10月前
|
算法 关系型数据库 MySQL
分布式唯一ID生成:深入理解Snowflake算法在Go中的实现
在分布式系统中,确保每个节点生成的 ID 唯一且高效至关重要。Snowflake 算法由 Twitter 开发,通过 64 位 long 型数字生成全局唯一 ID,包括 1 位标识位、41 位时间戳、10 位机器 ID 和 12 位序列号。该算法具备全局唯一性、递增性、高可用性和高性能,适用于高并发场景,如电商促销时的大量订单生成。本文介绍了使用 Go 语言的 `bwmarrin/snowflake` 和 `sony/sonyflake` 库实现 Snowflake 算法的方法。
460 1
分布式唯一ID生成:深入理解Snowflake算法在Go中的实现
|
9月前
|
存储 算法 安全
分布式系统架构1:共识算法Paxos
本文介绍了分布式系统中实现数据一致性的重要算法——Paxos及其改进版Multi Paxos。Paxos算法由Leslie Lamport提出,旨在解决分布式环境下的共识问题,通过提案节点、决策节点和记录节点的协作,确保数据在多台机器间的一致性和可用性。Multi Paxos通过引入主节点选举机制,优化了基本Paxos的效率,减少了网络通信次数,提高了系统的性能和可靠性。文中还简要讨论了数据复制的安全性和一致性保障措施。
557 1
|
10月前
|
机器学习/深度学习 人工智能 自然语言处理
【EMNLP2024】基于多轮课程学习的大语言模型蒸馏算法 TAPIR
阿里云人工智能平台 PAI 与复旦大学王鹏教授团队合作,在自然语言处理顶级会议 EMNLP 2024 上发表论文《Distilling Instruction-following Abilities of Large Language Models with Task-aware Curriculum Planning》。

热门文章

最新文章