业务开发算法 50 讲
黄清昊
Hashdata 数据库内核工程师,LeetCode 高赞答主,公众号微扰理论作者
23292 人已学习
新⼈⾸单¥59
登录后,你可以任选4讲全文学习
课程目录
已完结/共 51 讲
业务开发算法 50 讲
15
15
1.0x
00:00/00:00
登录|注册

23|Raft:分布式系统间如何达成共识?

容错性增加
吞吐量提高
计算和存储能力
Leader同步日志的优化方案讨论
对Raft算法的优化思考
Leader同步日志效率问题
工程实践中的优化思考
MIT 6.824课程推荐
提交日志的规则和极端情况处理
Candidate选举请求的限制
领导人完整性的保证
Log Matching规则
日志索引和任期的作用
安全复制的定义
Leader的职责:AppendEntries请求
解决选举冲突和分区问题的策略
选举过程和任期概念
节点状态:Follower、Candidate、Leader
Leader的概念和作用
子问题拆解:领导人选举、日志复制、安全性
Raft算法的简化和明确性
Paxos算法的复杂性
主节点的定义和局限性
一致性模块的作用
客户端请求的处理
状态变更的流程:commit后apply
日志存储在多个节点
redo-log在分布式系统中的应用
一致性算法的重要性
节点故障的不可避免性
分布式系统的挑战
课后作业
实践和优化
安全性
日志复制
领导人选举
Raft算法与Paxos
日志一致性问题
复制状态机
分布式共识问题
Raft算法:分布式系统共识

该思维导图由 AI 生成,仅供参考

你好,我是微扰君。
今天我们要来谈一谈分布式系统中一个非常重要的问题:分布式共识问题,也就是一致性问题。
我们知道,分布式系统的诞生,主要是为了提供单机无法进行的计算和存储、提高吞吐量、增加容错性等。而在现在的互联网架构下,分布式系统由于大量使用廉价的商用机器,节点故障是不可避免的。
在这种情况下,多个机器如何像一个整体一样工作,是件很困难的事情,这里一致性算法就起到了至关重要的作用。
以分布式 KV 存储系统为例,我们来先搞清楚分布式一致性到底解决的是什么问题。

复制状态机

之前在操作系统章节中讲过,数据库常用 redo-log 来实现事务等能力,那当这样的存储系统不再是单机节点,我们通常也需要采用多台机器来存储日志,把同样的日志在不同的节点都存储一份。这样如果有一台节点挂了,整个系统还可以用备份节点来提供日志的能力。
让多台服务器存储相同顺序的多条相同指令,也就是“日志”,可以帮助我们实现复制状态机。
每一个状态的变更记录都会先在日志中存储并 commit,之后才 apply 到状态机中修改对应的状态,这个设计能在分布式系统中解决许多和容错性相关的问题。
既然涉及多个节点存储同样的一份东西,怎样才能保证多个独立的节点所存储的内容是一致的呢?这就是我们常说的“一致性问题”了。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

Raft算法是一种用于解决分布式系统中共识问题的一致性算法。相较于传统的Paxos算法,Raft算法更易理解和实现,将一致性问题拆解成了领导人选举、日志复制和安全性三个独立的子问题。通过引入领导者机制和禁止日志中存在空洞等限制,Raft算法简化了系统状态和接口设计,使得整个过程更加清晰易懂。该算法更加注重工程实践和易用性,为分布式系统中的一致性问题提供了一种更加直观和易懂的解决方案。文章详细介绍了Raft算法中的领导人选举和日志复制两个关键环节,以及相关的设计思路和约束条件。通过对Raft算法的解析,读者可以深入了解其在分布式系统中的应用和优势。文章还提到了Raft协议中的“领导人完整性”特性,以及对该特性的限制和保证方法。此外,文章还探讨了Raft协议的一些优化思路,如在领导者给Follower同步日志时提高效率的方法。整体而言,Raft算法的逻辑清晰,但在工程实践中仍有许多优化空间,需要不断探索和实践。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《业务开发算法 50 讲》
新⼈⾸单¥59
立即购买
登录 后留言

全部留言(3)

  • 最新
  • 精选
  • 松鼠鱼
    老师对于最后一张图的解释太粗略了,我贴一个网上看到的比较细致的给大家参考: 情况 a: 服务器 S1 在任期为 2 的时刻仅将日志 <index: 2, term: 2> 发送到了服务器 S2 便崩溃掉。 情况 b: 服务器 S5 在任期为 3 的时刻当选 Leader (S5 的计时器率先超时,递增任期号为 3 因此高于服务器 S3, S4,可以当选 Leader),但没来得及发送日志便崩溃掉。 情况 c: 服务器 S1 在任期为 4 的时刻再次当选 Leader (S1 重启时,任期仍然为 2,收到新的 Leader S5 发送的心跳信息后更新任期为 3,而在 Leader S5 崩溃后,服务器 S1 为第一个计时器超时的,因此发起投票,任期更新为 4,大于网络中其他服务器任期,成功当选 Leader),同时将日志 <index: 2, term: 2> 发送到了服务器 S2, S3,但还没有通知服务器对日志进行提交便崩溃掉。 情况 d: 情况 (a -> d) 如果在任期为 2 时服务器 S1 作为 Leader 崩溃掉,S5 在任期为 3 的时刻当选 Leader,由于日志 <index: 2, term: 2> 还没有被复制到大部分服务器上,并没有被提交,所以 S5 可以通过自己的日志 <index: 2, term: 3> 覆盖掉日志 <index: 2, term: 2>。 情况 e: 情况 (a -> e) 而如果在任期为 2 时服务器 S1 作为 Leader,并将 <index: 2, term:2> 发送到S2, S3,成功复制到大多数成员服务器上,并且成功提交了该日志。那么即便 S1 崩溃掉,S5 也无法成功当选 Leader,因为 S5 不具备网络中最新的已被提交的日志条目。

    作者回复: 嗯嗯!补充的非常好;感谢这位同学。 不过稍微再补充一句,情况c中,确切来说,不是 `还没有通知服务器对日志进行提交` 而是 不能 `对<index: 2, term: 2>的日志进行提交` 在raft的论文中figure8主要是为了描述 我们不能允许领导提交之前任期的日志;即使他可以把它复制到多数节点中。这正是因为d这样的情况,c中term2的日志即使被复制到多数节点也有可能被新上位的其他节点所覆写;如果允许提交则不符合数据安全的语意了。 我当时写的不是很清楚,已经安排修正了~

    2022-03-13
    2
  • 雨落~紫竹
    这篇干货满满
    2022-07-18
  • peter
    请教老师三个问题: Q1:分布式一致性具体分为哪几种一致性问题? 比如分布式存储一致性等。 Q2:分布式事务算一致性问题吗? Q3:Raft在哪些框架中被使用?
    2022-02-13
    2
收起评论
显示
设置
留言
3
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部