@vivekgalatage: Kyle Kingsbury 的分布式系统导论 https://github.com/aphyr/distsys-class…
摘要
Kyle Kingsbury 分享了一份免费的 16-32 小时分布式系统基础课程大纲,涵盖理论、算法和实际生产问题,并通过 Maelstrom 提供可选的实验练习。
Kyle Kingsbury 的分布式系统导论
https://t.co/W7WQFkGpo9 https://t.co/FUx02Kud05
查看缓存全文
缓存时间: 2026/06/27 11:54
分布式系统入门指南 作者:Kyle Kingsbury https://t.co/W7WQFkGpo9 https://t.co/FU02xKud05 — # aphyr/distsys-class 来源:https://github.com/aphyr/distsys-class # 分布式系统入门指南 版权所有 Kyle Kingsbury & Jepsen, LLC。本大纲配套一门16至32小时的分布式系统基础概述课程(https://jepsen.io/training.html)。该课程旨在通过讲座、讨论及可选实验(https://github.com/jepsen-io/maelstrom),向软件工程师介绍分布式系统的实用基础。学员将直观理解关键分布式系统术语,概览算法图谱,并探索生产环境中的实际问题。 ## 开场 - 我是 Kyle Kingsbury - 人称代词:他/他 - 邮箱:[email protected] - 本大纲:https://github.com/aphyr/distsys-class - 我曾从多个角度研究分布式系统 - 2003—2009:系统管理员、网络运维、Web开发者 - 2009—2014:后端工程师、多家Web初创公司的数据库管理员 - 2014至今:分布式系统安全测试(Jepsen) - 本课程面向实践者 - “我希望当初有人告诉我这些” - 后端工程师 - 前端工程师 - 运维人员 - 产品经理 - 本课程旨在帮助你编写、运维和使用分布式系统 - 前半部分:理论框架 - 概念如何相互关联的地图 - 不是死记硬背,而是知道去哪里查 - 建立共同语言 - 与同事交流 - 阅读论文 - 评估系统宣称 - 理解基本原则 - 时间、排序、节点、网络、故障、活性、安全性 - 算法类别 - 能做什么和不能做什么,何时应用 - 后半部分:实践要点 - 设计模式杂烩 - 经验教训 - 计算机,其实是个错误 - 论文里没写的是什么? - 最后:生产环境关注点 - 部署、调试、监控 - 课程安排 - 这门课由你主导 - 我们可以深入探讨,也可以跳过熟悉内容 - 随时提问、挑战、分享想法 - 大约每小时休息一次,每次约10分钟,外加午餐 - 需要暂时离开完全没问题! - 突发状况、孩子、宠物等 - GitHub上的大纲可以帮助补课 - 你可以课间或休息时问我错过的问题! - 我经常邀请大家发言,但也欢迎随时插话 - 如果你不想被点名,请告诉我 - 课后想到问题可以发邮件! - 或者写下来留到第二天讨论 - 禁止录制 - 教学是我的生计 - 本大纲免费! - 如果包含实验: - 本课程配有实验! - 主要集中在中间部分 - 提醒大家先决条件:准备工作(https://github.com/jepsen-io/maelstrom/blob/main/doc/01-getting-ready/index.md) - 如果是远程授课: - 你可以随时关闭视频 - 但请尽量保持一部分人开启视频,这对教学非常有帮助 - 看到表情让我知道讲课效果如何! - 实验阶段,我们会共享tmux会话 - 好了,咱们开始吧! ## 什么让一个东西变得分布式? Lamport, 1987: > 分布式系统是这样一种系统:你甚至不知道存在的那台计算机发生故障,> 却能让你的计算机变得不可用。 - 第一印象:我们机房里的*nix主机,运行进程通过TCP或UDP通信。 - 或者EC2、Rackspace等云主机 - 可能通过InfiniBand通信 - 相隔几英寸和局域网 - 或者相隔数公里和互联网 - 大多数移动应用也是分布式系统的一部分 - 通过极其糟糕的网络通信 - 桌面Web浏览器同理 - 不仅仅是服务器——客户端也是! - 更广义地说:分布式系统 - 由相互交互的组件组成 - 速度慢 - 且通常不可靠 - 不管这些对你意味着什么 - 所以还包括: - 飞机上的冗余CPU - ATM机和销售点终端 - 太空探测器 - 支付账单 - 医生转诊 - 通过短信协调计划 - 所有商务会议 ## 节点与网络 - 我们把分布式系统中的每个部分称为节点 - 也称为进程、代理或参与者 ### 节点 - 特征延迟 - 节点内部操作“快“ - 节点之间操作“慢“ - 快慢取决于系统做什么 - 节点是可靠的 - 整体失效 - 你知道问题发生的时间 - 状态是一致的 - 状态转换有序、规则 - 通常建模为某种单线程状态机 - 节点本身也可以是分布式系统 - 但只要该系统整体提供“快速、一致“的操作,我们就可以将其视为单个节点。 - 进程的形式化模型 - Actor模型(https://dspace.mit.edu/handle/1721.1/6952) - 通信顺序进程(https://www.cs.cmu.edu/~crary/819-f09/Hoare78.pdf) - Pi演算(https://golem.ph.utexas.edu/category/2009/08/the_pi_calculus.html) - 环境演算(http://lucacardelli.name/Talks/1998-03-30%20Mobile%20Ambients%20%28ETAPS%29.pdf) - 节点故障的形式化模型 - 崩溃-停止 - 崩溃-恢复 - 崩溃-遗忘 - 拜占庭 ### 网络作为消息流 - 节点通过网络交互 - 人类通过语言交互 - 粒子通过场交互 - 计算机通过IP、UDP、SCTP等交互 - 我们将这些交互建模为节点之间发送的离散消息 - 消息传递需要时间 - 这就是分布式系统“慢“的部分 - 我们称之为“延迟“ - 消息经常可能丢失 - 这是分布式系统“不可靠“的另一方面 - 网络很少是同质的 - 某些链路比其他链路更慢/带宽更小/更容易失败 ### 因果图 - 我们可以用图来表示节点和网络的交互 - 时间从左到右或从上到下流动 - 节点是时间方向上的线(因为它们位置固定) - 消息是连接节点的斜线 ### 同步网络 - 节点以锁步方式执行:节点步之间的时间总是1。 - 消息延迟有界 - 实际上是完美的全局时钟 - 容易证明相关性质 - 你可能没有这样的网络 ### 半同步网络 - 类似同步网络,但时钟只是近似,例如在[c, 1]范围内 ### 异步网络 - 独立执行,任意时间:步时间在[0, 1]内任意 - 消息延迟无界 - 没有全局时钟 - 比半同步或同步网络更弱 - 意味着某些算法不能那么高效 - 意味着某些算法不可能实现 - 参见 Attiya & Mavronicolas, “Efficiency of Semi-Synchronous vs Asynchronous Networks” - IP网络显然是异步的 - 但实际上真正的病态情况很少发生 - 大多数网络在几秒到几周内恢复,而不是“永远“ - 相反,人类的时间尺度是秒到周 - 所以不能假装问题不存在 ## 当网络出错时 - 异步网络允许: - 重复 - 延迟 - 丢弃 - 乱序 - 丢弃和延迟无法区分 - 拜占庭网络允许任意篡改消息 - 包括重写内容 - 实际网络中很少出现 - 但并非没有 - https://www.pagerduty.com/blog/the-discovery-of-apache-zookeepers-poison-packet/ - https://tech.vijayp.ca/linux-kernel-bug-delivers-corrupt-tcp-ip-data-to-mesos-kubernetes-docker-containers-4986f88f7a19 ## 底层协议 ### TCP - TCP 可靠。用它。 - 不是完美;你可以更快 - 但你知道什么时候需要更快 - 实践中,TCP在单个TCP连接内防止重复和乱序 - 但你可能会打开多个连接 - 哪怕仅仅因为TCP连接最终会失败 - 当失败发生时,你要么a.) 丢失消息,要么b.) 重试 - 你可以通过在TCP之上编码自己的序列号来重建顺序 ### UDP - 与TCP相同的地址规则,但没有流不变性 - 很多人为了“速度“而用UDP - 但没有考虑路由器和节点可以并且会任意丢弃数据包 - 没有考虑数据包会被重复 - 以及乱序 - “但至少它是无偏的,对吧?” - 错! - 这会在例如指标收集中引起各种混乱 - 而且调试起来很难 - TCP提供流量控制并将逻辑消息重新打包成数据包 - 你需要重新构建流量控制和背压 - TLS over UDP是可行的,但很困难 - UDP在TCP FSM开销过大时非常有用 - 内存压力 - 大量短连接和套接字重用 - 在尽力而为的交付很好地映射系统目标时尤其有用 - 语音通话:人们会道歉并重复 - 游戏:卡顿和延迟,但后续追赶 - 更高级别的协议在底层混乱之上施加秩序 ## 时钟 - 当系统被拆分成独立部分时,我们仍然需要某种事件顺序 - 时钟帮助我们排序:先这个,然后那个 ### 墙钟 - 理论上,操作系统时钟提供了系统事件的部分顺序 - 注意:NTP可能不像你想象的那么好 - 注意:节点之间肯定不同步 - 注意:硬件可能漂移 - 有多份关于Supermicro TSC导致系统时钟快26ms/s的报告 - https://groups.google.com/forum/#!search/Supermicro20SYS-1029UX-LL1-S1620system20clock20running20too20fast/mechanical-sympathy/oG9vLZVYjVA/DU-T9QpBAgAJ - 注意:差距可达好几个世纪 - NTP可能不在乎 - http://rachelbythebay.com/w/2017/09/27/2153/ - 注意:NTP仍可能使时钟向后跳(默认:delta > 128 ms) - https://www.eecis.udel.edu/~mills/ntp/html/clock.html - 注意:POSIX时间定义上不是单调的 - Cloudflare 2017:午夜UTC的闰秒意味着时间倒退 - 当时Go无法访问CLOCK_MONOTONIC - 计算出负持续时间,然后传给rand.int63n(),导致panic - 导致DNS解析失败:几个小时内1%的HTTP请求受影响 - https://blog.cloudflare.com/how-and-why-the-leap-second-affected-cloudflare-dns/ - 注意:你想要测量的时间尺度可能无法达到 - 注意:线程可以睡眠 - 注意:运行时可以睡眠 - 注意:操作系统可以睡眠 - 注意:“硬件“可以睡眠 - 注意:虚拟机管理程序可以对你说谎 - 在15分钟内偏差超过16秒!? - https://gist.github.com/sandfox/32e749b5eac861c93f1bbeb8782ae8fd - 就是别用。 - 至少OS单调时钟是单调的,对吧? - 哦不:https://github.com/rust-lang/rust/blob/eed12bcd0cb281979c4c9ed956b9e41fda2bfaeb/src/libstd/time.rs#L201-L232 - 使用CLOCK_BOOTTIME,该时钟考虑了VM暂停 ### Lamport时钟 - Lamport 1977: “分布式系统中的时间、时钟与事件顺序” - 每个进程一个时钟 - 每次状态转换单调递增:t' = t + 1 - 随每条发送的消息包含 - t' = max(t, t_msg + 1) - 如果进程有全序,我们可以对事件施加全序 - 但这个顺序可能很不直观 ### 向量时钟 - 将Lamport时钟推广为所有进程时钟的向量 - t_i' = max(t_i, t_msg_i) - 对于每个操作,递增该进程的时钟分量 - 提供部分因果顺序 - A < B 当且仅当所有A_i <= B_i,且至少一个A_i < B_i - 具体来说,给定一对事件,我们可以确定因果关系 - A在B的因果过去中 => A < B - B在A的因果过去中 => B < A - 否则独立 - 实用角度:过去是共享的;现在是独立的 - 只需保留“当前“且独立的状态 - 祖先状态可以丢弃 - 让我们能垃圾回收过去 - 空间复杂度O(进程数) - 需要协调才能GC - 或者牺牲正确性,修剪旧的vclock条目 - 变体 - Dotted Version Vectors - 用于客户端/服务器系统,排序更多事件 - Interval Tree Clocks - 用于进程动态加入离开 ### GPS和原子钟 - 比NTP好得多 - 全局分布的毫秒级全序 - 将异步网络提升为半同步网络 - 解锁更高效的算法 - 目前只有Google拥有 - Spanner:全局分布式强一致性事务 - 并且他们没有共享 - 比你想要的贵 - 每个GPS接收机几百美元 - 用于本地验证的原子钟:? - 可能需要多种类型的GPS时钟 - https://rachelbythebay.com/w/2015/09/07/noleap/ - 供应商的混乱复选框,将UTC校正应用于GPS时间 - 我不知道谁在这样做,但我打赌未来的数据中心会提供专用硬件接口用于有界精度的时间。 ## 回顾 我们已经介绍了分布式系统的基本原语。节点通过网络交换消息,节点和网络都可能以多种方式故障。TCP和UDP等协议提供了进程通信的基本信道,我们可以使用时钟对事件排序。现在,我们将讨论分布式系统的一些高级属性。 ## 可用性 - 可用性基本上是成功操作的比例。 ### 完全可用 - 朴素:每个操作都成功 - 一致性理论中:非故障节点上的每个操作都成功 - 对于故障节点无能为力 ### 粘性可用性 - 非故障节点上的每个操作都成功 - 约束:客户端始终与相同节点通信 ### 高可用性 - 比系统不分布式时更好。 - 例如能容忍最多f个故障,但不能再多 - 可能某些操作失败 ### 多数可用性 - 如果操作发生在能与集群多数通信的节点上,则成功 - 针对少数组件的操作可能失败 ### 量化可用性 - 我们经常谈论“正常运行时间“ - 如果没人使用,系统也算正常吗? - 高峰时段宕机是否更糟糕? - 可以测量“时间段内满足请求的比例“ - 然后绘制不同时间段的比例 - 时间尺度会影响报告的正常运行时间 - Apdex - 并非所有成功都平等 - 将操作分为“好“、“一般“和“差” - Apdex = P(好) + P(一般)/2 - 同样可以按年报告 - “我们今年实现了99.999的Apdex” - 以及更细的时间尺度! - “用户服务的Apdex刚刚降到0.5;运维人员请呼叫!” - 理想情况下:你的服务提供的幸福感的积分? ## 一致性 - 一致性模型是系统“安全“事件历史的集合 ### 单调读 - 一旦我读到一个值,任何后续读取将返回该状态或之后的值 ### 单调写 - 如果我先写入,那么我后续的任何写入都将在第一次写入之后发生 ### 读自己写 - 一旦我写入一个值,随后我执行的任何读取将返回那个写入(或之后的值) ### 写跟随读 - 一旦我读到一个值,随后任何写入将在那次读取之后发生 ### 因果一致性 - 假设操作可以通过因果关系的DAG链接 - 例如,跟在读取之后的写入是因果相关的 - 假设进程没有丢弃读取的数据 - 不在该DAG中的操作是并发的 - 约束:在进程执行一个操作之前,其所有前驱必须在该节点上已执行 - 并发操作可以自由重排 ### 顺序一致性 - 类似因果一致性,但约束可能的顺序 - 所有操作看起来是原子执行的 - 每个进程对操作顺序达成一致 - 来自给定进程的操作始终按顺序发生 - 但节点可以落后 ### 线性一致性 - 所有操作看起来是原子执行的 - 每个进程对操作顺序达成一致 - 每个操作看起来在invocation和响应之间某个时刻发生
相似文章
@yfractal:MIT 的分布式系统课程相当有意思,对架构设计也很有帮助。我读过 DDIA,但现在已经把里面的内容忘得一干二净,而 MIT 分布式系统里的不少例子我还能记得。更有意思的是 MIT 的操作系统课,写起代码来能让你掉头发。
一位用户分享了对 MIT 分布式系统课程(6.5840/6.824)与 DDIA 的对比感受,并附上 2026 年春季课程表的链接,内容涵盖 MapReduce、GFS、Paxos 和 Raft,还有一场由 Go 语言之父 Russ Cox 带来的客座讲座。
@vivekgalatage: Nancy Lynch的《分布式算法》就是那种你读一页,盯着墙看十分钟,然后……
推荐Nancy Lynch的《分布式算法》,这本书对分布式系统从业者是极有价值的资源。
@vivekgalatage: 最优秀的课程之一 https://courses.csail.mit.edu/6.851/spring21/
麻省理工学院 Erik Demaine 教授的《高级数据结构》课程(6.851)已完全在线开放,包含视频讲座和协作式问题求解。
精选资源列表:供初学者学习分布式训练的理论与代码 [P]
一份精心策划、按序编排的阅读清单,收录基础论文、博客文章和视频,面向学习大语言模型(LLM)分布式训练的初学者,涵盖 ZeRO、Megatron-LM、GPipe、PyTorch FSDP 和 Horovod。
@vivekgalatage: 自底向上的计算机科学 https://bottomupcs.com
一本免费的在线书籍,自底向上涵盖计算机科学,由 Ian Wienand 编写,提供 PDF、EPUB 和源代码格式。