分布式一致性如何实现?- Raft 算法

本文涉及的产品
日志服务 SLS,月写入数据量 50GB 1个月
简介: Raft 是一种管理复制日志的一致性算法,它比 Paxos 更容易理解和实现。Raft 为了更加容易理解和实现,做了算法拆解,Raft 将一致性算法抽象为几个关键模块,例如:领导人选举、日志复制、安全等。

介绍

Raft 是一种管理复制日志的一致性算法,它比 Paxos 更容易理解和实现。Raft 为了更加容易理解和实现,做了算法拆解,Raft 将一致性算法抽象为几个关键模块,例如:领导人选举、日志复制、安全等。

Raft 算法的产生不仅是为了解决分布式共识问题,还为了方便使用的他的人能够清楚的明白它为什么能工作。也就是可理解性、可实现上更加的简单。

Raft 算法特性:

  • 强领导人:和其他算法相比,Raft 算法使用一种更强的领导力形式。比如日志条目只能通过领导人复制给其他跟随者。这种方式简化的对日志复制的管理。
  • 领导人选举:Raft 算法使用一个随机计时器的方式进行选举,当计时器结束后节点状态就会由跟随者变成候选人状态,立即发送选举请求。
  • 成员变更:Raft 使用一种共同一致的方法来处理集群成员变更问题。
  • 日志复制:领导人必须从客户端接收日志条目,然后复制到集群中的其他节点,并强制要求其他节点的日志和自己保持一致。

复制状态机

计算机科学领域,状态机复制是实现容错服务的一种常规方法,主要通过复制服务器,并协调客户端和这些服务器镜像间的交互来达到目标。这个方法也同时提供了理解和设计复制管理协议的一套基本框架。

一致性算法是从复制状态机的背景下提出的(参考英文原文引用37)。在这种方法中,一组服务器上的状态机产生相同状态的副本,并且在一些机器宕掉的情况下也可以继续运行。复制状态机在分布式系统中被用于解决很多容错的问题。

https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/8fb84f7b44ab4a178ecaebbee796da84~tplv-k3u1fbpfcp-zoom-1.image

复制状态机的结构。一致性算法管理着来自客户端指令的复制日志。状态机从日志中处理相同顺序的相同指令,所以产生的结果也是相同的。

复制状态机通常都是基于复制日志实现的,如上图。每一个服务器存储一个包含一系列指令的日志,并且按照日志的顺序进行执行。每一个日志都按照相同的顺序包含相同的指令,所以每一个服务器都执行相同的指令序列。因为每个状态机都是确定的,每一次执行操作都产生相同的状态和同样的序列。

一致性算法的任务是保证复制日志的一致性。服务器上的一致性模块接收客户端发送的指令然后添加到自己的日志中。它和其他服务器上的一致性模块进行通信来保证每一个服务器上的日志最终都以相同的顺序包含相同的请求,即使有些服务器发生故障。一旦指令被正确的复制,每一个服务器的状态机按照日志顺序处理他们,然后输出结果被返回给客户端。因此,服务器集群看起来形成了一个高可靠的状态机。

Raft 有哪几种状态?

https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/ab38c5538eb042c79cda1a791cea8560~tplv-k3u1fbpfcp-zoom-1.image

Raft 算法支持三种节点状态,分别是跟随者、候选人、领导者,所以节点初始化的时候都默认是跟随者状态。

跟随者(Follower)

  • 响应来自候选人或者领导人的请求(选举、心跳、日志)。
  • 如果超过随机计时器时间没有接到领导人日志或心跳,就会变更为候选人状态。

候选人(Candidate)

  • 候选人将向其他节点发送请求投票(RequestVote)RPC 消息,通知其他节点来投票:

    • 增加自己的任期号
    • 给自己投票
    • 重置选举超时时间
    • 发送投票请求给其他节点
  • 如果得到了半数以上的票,就晋升为领导人状态。
  • 如果选举期间接收到来自新的领导人的附加日志或心跳 RPC,则立即转变为跟随者状态。
  • 如果选举过程超时,则发起新一轮的选举。

领导人(Leader)

  • 领导人状态下就要每隔一段时间不停地给跟随者发送心跳,来维护领导人的地位。
  • 接收并处理来自客户端的请求:附加条目到本地日志中,在条目被应用到状态机后响应客户端。
  • 管理日志复制,将日志同步到其他跟随者节点中。

选举分析

选举是什么?

选举就是在一个集群多个节点中选出一个节点来担任领导人的角色,负责和外部通信,管理集群中其他节点。

选举过程

首先假设我们有一个 3 个节点的集群,分别是节点 A、节点 B、节点 C。初始化的时候 3 个节点的状态全部都是跟随者(follower)状态,节点 A 的任期编号是 0 ,超时时间是 100 ms 。节点 B 的任期编号是 0 ,超时时间是 200 ms。节点 C 的任期编号是 0 ,超时时间是 300 ms。

任期编号可以理解为是某一个节点当选领导人的时间段,并且也是选举过程中的重要判断依据。类似版本号。

https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/8847ea11cc1d45468ab7b7919d59d2b8~tplv-k3u1fbpfcp-zoom-1.image

Raft 算法实现了随机超时时间,在没有领导人的情况下,最先超时的是节点 A,此时节点 A 会先增加自己的任期编号,设置为 1 。再给自己投一票,同时变更自己的状态为候选人(candidate)状态,并向其他节点发送选举投票请求,请求其他节点选自己为领导人。

https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/f11553c0ef414feabef4672af400e25d~tplv-k3u1fbpfcp-zoom-1.image

此时其他节点收到了节点 A 的投票请求,对比下任期编号是否小于自己的任期编号,如果小于就拒绝投票,反之如果在此任期编号上还没有进行过投票,就会把票投给节点 A。并更新自己的任期编号。

每个任期编号下只有一次投票的机会

https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/e63c5568eacd412bb5d849380a2644b4~tplv-k3u1fbpfcp-zoom-1.image

如果节点 A 在超时时间内得到了节点半数以上的票数,那么它就会成为新的领导人。

https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/0d2b5cae845841a397ad4ab8b9e152fd~tplv-k3u1fbpfcp-zoom-1.image

当节点 A 变成领导人以后,就会每隔一段时间发送心跳给节点 B 和节点 C,证明自己还存活着,不需要再次发起选举,只有当领导人不能正常工作了才需要发起选举操作。节点 B、C 接到心跳请求后会刷新自己的随机超时时间。

https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/453d82597c374f7d9eccfbc407aaaa87~tplv-k3u1fbpfcp-zoom-1.image

选举规则

  • 为了解决选举无效或者规定时间内没有达到指定票数,Raft 实现了一种随机选举超时时间的方式。

    • 跟随者等待领导者的心跳时间是随机的。
    • 选举的超时时间间隔是随机的。
  • 领导者需要周期性的向跟随者发送心跳,证明自己还活着,否则将会触发选举。第一个等待心跳超时的节点会推荐自己为候选人,向其他节点请求投票。
  • 同一个任期编号只有一次投票的机会。按照先来后到原则进行投票。
  • 在一次选举中得到全部节点半数以上票的节点,当选新的领导人。
  • 在一个任期能只能有一个领导者,直到这个领导自身出现问题,才会发生下一个任期的选举。
  • 日志完整性高的跟随者拒绝投票给日志完整性低的候选人。

    • 比如当节点 A 的任期编号是 5 ,并且已经复制了 5 个日志,节点 B 的任期编号是 6,目前复制了 4 个日志,此时节点 B 当候选人,请求节点 A 给它投票,就会被节点 A 拒绝。

日志复制

日志是什么?

Raft 是一种管理复制日志的一致性算法,所以在 Raft 中管理的是日志,日志可以理解为系统中需要进行同步的副本数据。副本数据在 Raft 中是以日志的形式存在的,日志由日志项组成。

日志项包含任期编号、日志索引、用户指定的数据等:

  • 指令:一条由客户端请求的、状态机需要执行的指令,可以理解为要同步给其他节点的数据。
  • 索引值:日志项对应的整数索引值,用来标识唯一的日志项,是一个连续的、单调递增的号码
  • 任期编号:对应创建这条日志的领导人的任期编号。

https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/9096f0d7dbea44bc98cbf541c8e5a2b3~tplv-k3u1fbpfcp-zoom-1.image

复制过程

假设一个 Raft 集群已经选举完毕,此时客户端发来一个请求指令 Set x=3,领导人会根据请求创建一个新的日志项,然后附加到本地日志中。

https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/e16f66cc0fe54f7ca48e1ffe4f18614b~tplv-k3u1fbpfcp-zoom-1.image

然后领导人通过日志复制 RPC ,将新的日志项复制到其他的节点上。当收到大多数节点响应以后,领导人就认为复制成功了,然后就提交本地日志,给客户端返回执行结果。

在领导人提交以后,是不需要告诉跟随者日志已提交的,因为在领导人发给跟随者的心跳请求中就包含当前领导人已提交的日志索引,跟随者会根据提交索引判断自己应该提交哪些日志。

https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/9e7722165647465e9b547609aa99738c~tplv-k3u1fbpfcp-zoom-1.image

领导人通过日志复制 RPC 一致性检查保证日志的一致,找到跟随者节点上与自己相同日志项的最大索引值,然后复制并更新覆盖该索引值之后的日志项,实现了各个节点日志的一致。

首先领导人会发日志复制 RPC 给跟随者,跟随者发现自己本地的日志和发过来的日志对不上,就会拒绝新的日志项,返回失败信息给领导人。这时领导人会递减要复制的日志项索引,并再次发送日志复制消息给跟随者,循环此步骤直到找到跟随者和自己日志相同的日志索引,复制并更新覆盖该索引值之后的日志项,实现集群节点的日志一致。

Raft 是领导人主导,所以跟随者中和领导人不一样的日志会被领导人的日志覆盖,而领导人不会覆盖或者删除自己的日志,只做增加操作。

成员节点变更

受动态扩缩容的影响,我们的系统集群可能会增加节点或者删除节点。在 Raft 中对集群成员变更可能会产生分区问题。这样就会导致集群分裂,一个集群可能会出现两个领导人。

因为 Raft 的领导人选举,建立在“大多数”的基础之上,那么当成员变更时,集群成员发生了变化,就可能同时存在新旧配置的 2 个“大多数”,出现 2 个领导者,破坏了 Raft 集群的领导人唯一性,影响了集群的运行。

https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/25c3162ac04f4cda89e784d1765fe22a~tplv-k3u1fbpfcp-zoom-1.image

最初实现成员变更的是联合共识(Joint Consensus),但这个方法实现起来难,后来 Raft 的作者就提出了一种改进后的方法,单节点变更(single-server changes)。

单节点变更就是通过一次变更一个节点来实现成员节点变更,如果需要添加多个节点,那就需要执行多次单节点变更。比如将 3 节点集群扩容到 6节点集群,就需要先将 3 个节点 变更为 4 个节点,然后再将 4 个节点变更为 5 个节点,最后在将 5 个节点变更为 6 个节点。

  • 第一步领导人向新节点同步日志数据。
  • 第二步领导人将新配置作为一个日志项复制到新配置中的所有节点上,然后将新配置的日志项应用到本地状态机,完成单节点变更。

https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/25fee9eda4624bc69677e7862e151a65~tplv-k3u1fbpfcp-zoom-1.image

本文只对 Raft 的几个关键模块原理进行简单介绍,实际 Raft 在每一个模块都有详细的规则和设计,对 Raft 感兴趣的朋友可以查看参考中的资料进行深入的研究。

后续计划用 Java 实现下 Raft 算法,感兴趣的朋友可以关注 Service Plus 这个项目

参考

相关实践学习
日志服务之使用Nginx模式采集日志
本文介绍如何通过日志服务控制台创建Nginx模式的Logtail配置快速采集Nginx日志并进行多维度分析。
目录
相关文章
|
5天前
|
存储 缓存 负载均衡
一致性哈希:解决分布式难题的神奇密钥
一致哈希是一种特殊的哈希算法,用于分布式系统中实现数据的高效、均衡分布。它通过将节点和数据映射到一个虚拟环上,确保在节点增减时只需重定位少量数据,从而提供良好的负载均衡、高扩展性和容错性。相比传统取模方法,一致性哈希能显著减少数据迁移成本,广泛应用于分布式缓存、存储、数据库及微服务架构中,有效提升系统的稳定性和性能。
24 1
|
1月前
|
算法 关系型数据库 MySQL
分布式唯一ID生成:深入理解Snowflake算法在Go中的实现
在分布式系统中,确保每个节点生成的 ID 唯一且高效至关重要。Snowflake 算法由 Twitter 开发,通过 64 位 long 型数字生成全局唯一 ID,包括 1 位标识位、41 位时间戳、10 位机器 ID 和 12 位序列号。该算法具备全局唯一性、递增性、高可用性和高性能,适用于高并发场景,如电商促销时的大量订单生成。本文介绍了使用 Go 语言的 `bwmarrin/snowflake` 和 `sony/sonyflake` 库实现 Snowflake 算法的方法。
52 1
分布式唯一ID生成:深入理解Snowflake算法在Go中的实现
|
16天前
|
存储 算法 安全
分布式系统架构1:共识算法Paxos
本文介绍了分布式系统中实现数据一致性的重要算法——Paxos及其改进版Multi Paxos。Paxos算法由Leslie Lamport提出,旨在解决分布式环境下的共识问题,通过提案节点、决策节点和记录节点的协作,确保数据在多台机器间的一致性和可用性。Multi Paxos通过引入主节点选举机制,优化了基本Paxos的效率,减少了网络通信次数,提高了系统的性能和可靠性。文中还简要讨论了数据复制的安全性和一致性保障措施。
33 1
|
1月前
|
存储 缓存 算法
分布式缓存有哪些常用的数据分片算法?
【10月更文挑战第25天】在实际应用中,需要根据具体的业务需求、数据特征以及系统的可扩展性要求等因素综合考虑,选择合适的数据分片算法,以实现分布式缓存的高效运行和数据的合理分布。
|
1月前
|
分布式计算 Java 开发工具
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景,随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码,发现使用的`nativeBooster.saveModel`方法不支持OSS路径,而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令,帮助用户顺利迁移模型存储路径。
|
2月前
|
算法
基于粒子群算法的分布式电源配电网重构优化matlab仿真
本研究利用粒子群算法(PSO)优化分布式电源配电网重构,通过Matlab仿真验证优化效果,对比重构前后的节点电压、网损、负荷均衡度、电压偏离及线路传输功率,并记录开关状态变化。PSO算法通过迭代更新粒子位置寻找最优解,旨在最小化网络损耗并提升供电可靠性。仿真结果显示优化后各项指标均有显著改善。
|
2月前
|
算法
raft算法的自我理解
本文介绍了Raft算法的基本概念和工作原理,包括它如何通过日志复制和领导选举来实现分布式系统中不同机器的强一致性。
33 2
|
2月前
|
消息中间件 缓存 算法
分布式系列第一弹:分布式一致性!
分布式系列第一弹:分布式一致性!
|
2月前
|
算法 Java 关系型数据库
漫谈分布式数据复制和一致性!
漫谈分布式数据复制和一致性!
|
23小时前
|
机器学习/深度学习 算法
基于改进遗传优化的BP神经网络金融序列预测算法matlab仿真
本项目基于改进遗传优化的BP神经网络进行金融序列预测,使用MATLAB2022A实现。通过对比BP神经网络、遗传优化BP神经网络及改进遗传优化BP神经网络,展示了三者的误差和预测曲线差异。核心程序结合遗传算法(GA)与BP神经网络,利用GA优化BP网络的初始权重和阈值,提高预测精度。GA通过选择、交叉、变异操作迭代优化,防止局部收敛,增强模型对金融市场复杂性和不确定性的适应能力。
101 80