6.1800 计算机系统工程
6.033 | Spring 2017 | Schedule (mit.edu)
6.033 | Spring 2022 | Schedule (mit.edu)
6.1800 | Spring 2025 | Schedule (mit.edu)
先行条件
6.1910/6.004 计算结构
6.1010/6.009 编程基础
课程描述
6.033课程旨在全面覆盖计算机科学和工程中的关键领域，具体包括以下四个方面：
- 操作系统
- 网络
- 分布式系统
- 安全
希望你通过课堂的学习掌握，
计算机系统中的常见设计模式，如抽象和模块化，如何用来限制复杂性。
操作系统如何使用虚拟化和抽象的方法来强化模块化。
互联网如何应对规模化、多样化的应用程序和相互竞争的经济利益。
如何在不可靠的网络上构建一个可靠、可用的分布式系统。
计算机系统安全中的常见陷阱，以及如何应对这些陷阱。
具体形式：
讲座+论文+实验，三部分组成
参考书
Saltzer, Jerome H., and M. Frans Kaashoek. Principles of Computer System Design: An Introduction
和[线上内容(Part II)](Part_II.print.book (mit.edu))
主题
操作系统
- 复杂度，模块化，抽
- 命名
- 虚拟内存
- 有界缓冲区和锁
- 线程
- 操作系统结构；虚拟机
- 操作系统性能(存储方面)
计算机网络
- 计算机网络介绍，分层
- 网络层： 路由
- BGP
- 传输层：TCP
- 资源管理内部网络
- 应用层
- 数据中心和云
分布式系统
- 可靠性
- 原子、隔离、事务
- 日志
- 隔离
- 分布式事务
- 复制
计算机安全
- 安全介绍+认证
- 低级别攻击
- 安全通道
- ToR
- 网络攻击
实验
Part I 操作系统
Lec 1 复杂度，模块化，抽
阅读参考书 §1.1-1.5, §4.1-4.3
思考题
- 为什么构建复杂系统困难？
- 我们如何降低复杂性？
- 什么是模块化？模块化意味着什么？
- 客户端/服务器模型如何帮助我们实现模块化的？
- RPC与普通的过程调用有什么不同？RPC引入了哪些问题？
- 在设计系统时，除了模块化，我们还需要关心哪些其他事情？
Lec 2 命名
阅读参考书§2.2, §3.1， §4.4
思考题
- 在计算机系统中，名称的作用是什么？ 从高层次讲，他们能让我们做什么？
- 使用名称的好处？
- 命名方案的组成部分有哪些？
- 设计命名方案时，我们需要考虑什么问题？
Lec 3 虚拟内存
阅读参考书 §5.1, §5.3, §5.4
思考题
- 什么是虚拟化？
- 当我们说内存时候，意味着什么？ 内存和存储区别是什么？
- 为什么我们将页表用在虚拟内存？ 他们解决了什么问题？
- 当使用页表时，如何将虚拟地址转换为物理地址？
- 如果我们没有足够的内存来存储我们的程序指令和数据时会发生什么？
- 内核的工作是什么？
- 页表项的其他比特作用什么？如何 P， U/K 和R/W 比特。他们每个都解决什么问题？
- 如何用多级页表实现虚拟地址到物理地址的转换？
- 为什么多级页表要比“一般”的页表要省空间？
Lec 4 有界缓冲区 + 锁
大纲
什么是虚拟化？
什么是有界缓冲区？操作系统用它来做什么？
什么是竞争条件？
锁的作用是什么？例如，这段代码片段的区别是什么：
- python
bb.buf[bb.in mod N] <- message bb.in <- bb.in + 1 - python
acquire(bb.lock) bb.buf[bb.in mod N] <- message bb.in <- bb.in + 1 release(bb.lock)
最后的发送/接收代码为什么看起来是那样的？具体来说：
外层的 acquire/release 的目的是什么？
内层的 acquire/release（在 while 循环内部） 的目的是什么？
注意：测试你是否完全理解最终的发送/接收代码的一个好方法是确保你理解所有之前的版本为什么不起作用。一个好方法是像我们在讲座中那样，通过错误代码工作，看看出了什么问题。如果有问题，可以来办公室时间！
在锁和原子操作的上下文中，“不一致状态”是什么意思？
什么是死锁？
为什么我们需要原子交换操作来实现锁？
Lec 5 线程技术加强模块化
阅读参考书 §5.5, §5.6
思考题
什么是虚拟化？
suspend() 和 resume() 做什么？
yield() 的目的是什么？它是如何工作的？
- 你应该能够解释这个函数的代码
线程处于 RUNNABLE 和 RUNNING 状态分别是什么意思？
为什么保存线程的当前状态等于保存它的页表寄存器和栈指针？
条件变量是什么？它们解决了什么问题？
我们在有界缓冲区的发送（和接收）代码中添加了 wait() 和 notify() 调用。为什么？
什么是“丢失通知”（lost notify）问题？
wait() 和 notify() 是如何工作的？
yield_wait() 和 yield() 的思想相似。为什么我们需要 yield_wait()（即为什么仅有 yield() 不够）？
什么是抢占？它解决了什么问题？
Lec 6 虚拟机技术加强模块化
阅读参考书 §5.8
前面介绍多种高级抽象，用于虚拟化处理器、内存和通信链路，以实现模块化。应用程序通过Supervisor-call接口以及中断和异常处理程序与这些抽象进行交互。
另外一种方法是使用虚拟机（VM）。尽可能利用真实的物理机实现多个虚拟实例（包括特权指令、如加载和存储到页映射地址寄存器）。实现虚拟机的软件被称为虚拟机监视器（Virtual Machine monitor， VMM）
大纲
- 为什么我们希望在同一台物理机器上运行多个操作系统？
- 虚拟机监控器（VMM）的作用是什么？
- “陷入和仿真”（trap and emulate）是什么意思？
- VMM 如何处理客户操作系统的虚拟内存？
- VMM 如何处理客户操作系统的用户/内核位（U/K bit）？
- 为什么 VMM 必须参与这两件事（虚拟内存、U/K bit）？换句话说，为什么客户操作系统不能只在 VMM 拦截任何东西的情况下正常工作？
- 什么是大内核（monolithic kernel）？什么是微内核（microkernel）？它们之间的区别是什么？
- 许多操作系统是整体内核。为什么？
Lec 7 性能
前面讲在单一机器上通过虚拟化内存、有界缓存、线程来增强模块化；了解了微内核和宏内核的区别；探讨了如何在单一物理机器上通过虚拟机加强模块化，使其能够运行多个OS实例（并且其中一个OS发生了BUG不会影响到其他OS崩溃），其中如何实现VMM是一个关键问题，解决方法是通过“trap-and-emulate"，陷入并模拟。一个关键问题是，如何陷入那些不会引发中断的指令。
现在还有什么没有讨论呢？ 性能。这节将会介绍提供性能的通用方法。
本节没有参考书资料
思考题
- 性能瓶颈是指什么？
- 在思考系统性能时，拥有系统模型有何帮助？
- 常见的性能指标有哪些？它们各自的含义是什么？它们之间的关系如何？
- 哪些系统级技术通常能提升性能？
- 硬盘读写操作是如何工作的：
- 对于机械硬盘（HDDs）？
- 对于固态硬盘（SSDs）？
- 为什么在机械硬盘上批量读取能提升性能？
- 假设我们要将一个大型数据库实现为一系列文件（即在文件系统之上实现数据库），我们需要考虑哪些事项？
- 数据库管理系统（DBMS）擅长做什么？
Part II 计算机网络
Lec 8 计算机网络介绍
随着系统的发展，我们需要考虑，如何将一组链路加入到网络中。
| 分层 | 作用 |
|---|---|
| 应用层 | 实际产生流量的东西 |
| 传输层 | 共享网络，可靠传输(或者不可靠) |
| 网络层 | 命名、定位、和路由 |
| 链路层 | 两个相连接点的通信。比如BLT,ethernet, 802.11 |
Lec 9 路由
距离向量、链路状态以及如何
大纲
- 路由协议的目的是什么
- 为什么使用分布式路由协议？
- 分布式路由协议的三个主要步骤是什么，为什么要定期运行每个步骤？
- 链路状态路由：
- 广告中包含什么？
- 如果节点 A 发送广告，哪些节点会收到这份广告的副本？
- 节点使用什么算法来集成广告，该算法如何工作？
- 链路状态路由的优缺点是什么？
- 距离向量路由
- 广告中包含什么？
- 如果节点 A 发送广告，哪些节点会收到这份广告的副本？
- 节点使用什么算法来集成广告，该算法如何工作？
- 距离向量路由的优缺点是什么？
- 距离向量中广告接收顺序为何重要？
- “计数到无穷”是什么意思？
- 何时使用链路状态路由比较合适？
- 何时使用距离向量路由比较合适？
Lec 10 BGP
思考题
自治系统（AS）是什么？
互联网可扩展路由的三个组成部分包括：路由的层次结构、路径矢量路由和拓扑地址。我们如何理解每个组成部分，并且它们如何提升可扩展性？
什么是策略路由？为什么某些互联网利益相关者（例如ISP）需要它？
不同的AS关系意味着什么？
- 客户-提供者关系
- 对等关系（Peering）
为什么两个ISP会选择对等互联？
什么是“导出策略”？
客户/提供者关系中使用的导出策略有哪些？
对等关系中使用的导出策略有哪些？
你应该能够查看课堂上的AS图，并确定哪些路由被广告并发送给谁。
什么是“导入策略”？
- AS如何决定导入到特定目的地的路由？
BGP今天面临的一些挑战是什么？（有几个）
Lec 11 TCP
思考题
可靠传输是什么？什么是“可靠传输协议”？
网络可能存在哪些不可靠因素？（即可能出现哪些问题）
可靠传输的基础知识：
序列号的作用是什么？它们如何工作？
确认（ACK）的作用是什么？它们如何工作？
TCP发送方如何利用超时推断数据包丢失？
TCP接收方如何决定是否将数据包传递给接收应用？
拥塞控制：基础知识
拥塞控制的目的是什么？
拥塞控制的目标是什么？
“窗口”是什么意思？
TCP的拥塞控制是AIMD（加性增加乘性减少）
- 这意味着什么？发送方如何对拥塞做出反应？
- AIMD背后的直觉是什么？（例如：为什么不选择乘性增加乘性减少？或者加性增加加性减少等）
拥塞控制：额外机制
慢启动如何工作，为什么使用它？
快速重传/快速恢复如何工作，为什么使用它？
Lec 12 网络内资源管理
TCP拥塞控制直到出现拥塞问题后才会做出反应；我们能否在队列满之前让发送方做出反应？
TCP的拥塞控制本质上是通过接收到队列中数据丢失的信号来应对特定情况。网络内部的确有队列存在，交换机设置队列的原因是为了平滑流量和吸收流量突发。因此，TCP发送方并不要求精确地调整其窗口大小。 我们想找出一种方法，能帮助TCP 发送方能够更早的响应拥塞。
思考题
队列管理
- DropTail队列管理如何工作？它的优缺点是什么？
- 什么是流同步？为什么在DropTail队列管理中会发生这种情况？
- RED（随机早期检测）如何工作？它的优缺点是什么？
- RED如何解决DropTail的哪个限制？
- ECN（显式拥塞通知）如何工作？它的目的是什么？
基于延迟的调度
- 优先级队列如何帮助服务需要低延迟的应用？
基于带宽的调度
- 轮流调度（round-robin scheduling）如何工作？
- 轮流调度的主要问题是什么？
- 什么是赤字轮流调度（deficit round-robin scheduling）？它如何设置量子值？
- 如果队列为空，为什么不会累积信用？
Lec 13 应用层
思考题
内容交付介绍。客户端/服务器模型如何交付内容？主要的缺点是什么？
P2P
- P2P网络如何交付内容？
- BitTorrent P2P网络如何共享内容？具体来说
- .torrent文件是用来干什么的？
- 追踪器（tracker）是用来干什么的？
- 通信流程是怎样的？（例如，谁与谁进行通信？）
- 如何激励节点上传数据？
CDNs
CDN如何交付内容？
CDN所有者（例如，Akamai）在放置他们的机器和分发内容时需要考虑哪些因素？
CDN所有者（例如，Akamai）在决定哪个服务器对某个特定客户端是“最佳”时可能会考虑哪些特性？
PCDN
Lec 14 数据中心和云
思考题
数据中心网络的物理基础设施是什么样的？比如什么是机架？
网络拓扑是什么样的？
我们如何进行路由？
- 什么是“多路径路由”？
- 多路径路由协议需要处理哪些单路径路由协议（例如链路状态或距离矢量）不需要处理的问题？
数据中心中的集中控制器负责什么？
数据中心网络与内容分发网络（CDN）如何比较？
数据中心网络与互联网如何比较？
在数据中心网络中，以下每个领域有哪些关注点？
性能
可扩展性
容错性
安全性
Part III 分布式系统
Lec 15 可靠性
阅读参考书 §8.1 §8.2 §8.3
阅读论文：GFS
可靠性，Reliability。从这章开始我们转向分布式相关主题的学习，重点将关注当系统出现失败时候，你该如何处理？即围绕一个框架展开： 如何在不可靠的组件上，构建可靠的系统
思考题
- 从高层次看，处理故障的通用思维是什么？
- 如何测量可靠性？
- 讲座中我们将聚焦磁盘的可靠性， 为什么要选择磁盘？
- RAID相关
- 给定两个比特串A和B，如何计算A XOR B？给定A XOR B和A，如何计算B？
- 如果给定三个比特串A、B和C，如何计算A XOR B XOR C？
- 这些思想如何扩展到RAID中？
- RAID系统如何从单个故障磁盘中恢复？
- 读写操作在以下RAID系统中是如何工作的：
- RAID 1？
- RAID 4？
- RAID 5？
- 不同RAID级别之间的性能权衡是什么？
- 讲座中描述的RAID系统是否能在两个磁盘同时故障的情况下恢复？为什么或为什么不可以？
- 附加问题：如果一个磁盘先故障，然后另一个磁盘在1秒后故障，系统能否恢复？在10秒后故障呢？通常情况下，你会如何考虑这些系统恢复所需的故障间隔时间？
Outline
- 构建可靠的系统
- 可靠性的测量
- 案例分析： 磁盘RAID技术
Lec 16 事务
阅读参考书 §9.1，§9.2.1，§9.1.2
系统工程设计有两个策略，一个是all-or-nothing原子性、另外一个是before-or-after 原子性，他们都提供了很强的模块化性质，隐藏了一个事实——原子步骤实际上包含了很多步骤。
Outline
- 原子性
- 隔离性
Lec 17 Logging
阅读参考书 §9.3
论文阅读： MapReduce
上个lec我们介绍了用影子复制实现原子性，但是它性能表现不太好，因为即便很小的改动都需要替换整个文件。本节课介绍用日志实现原子性，接下来我们看到，如何在不损失性能的情况下实现原子性。这种机制叫日志记录(logging)。
思考题
- 日志基础（不考虑cell存储、缓存）
- 每种类型的日志记录（例如UPDATE、COMMIT）包含了哪些内容？
- 给定一系列事务，你应该能构建出相应的日志
- 如何使用日志来读取某个变量的值
- 日志的性能表现如何
- 每种类型的日志记录（例如UPDATE、COMMIT）包含了哪些内容？
- 添加cell存储
- 在添加了cell存储之后，读写操作如何进行？
- cell存储实在磁盘上还是内存上的？我饿什么很重要
- 为什么写入之前必须记录日志？
- 系统崩溃后，如何修复cell存储
- 给定一个日志 + cell 存储系统发生了崩溃，你应该能够在恢复后修复 cell 存储
- 添加了cell存储之后，日志的性能表现如何？
- 添加缓存
- 在同时拥有 cell 存储和缓存的情况下，读写操作是如何进行的？
- 缓存是在磁盘上（非易失性）还是在内存中（易失性）？为什么这很重要？
- 当系统崩溃且存在缓存时，如何修复 cell 存储？
- 给定一个日志 + cell 存储 + 缓存系统发生崩溃的情况，你应该能够在恢复后修复 cell 存储。
- 添加缓存后，日志的性能表现如何？
- 截断日志并写入检查点（checkpoint）的目的是什么？
Outline
Lec 18 隔离性
阅读参考书 §9.4 中 §9.4.1之前的内容, §9.5
上节lec， 我们基本实现了通过Logging为单台机器上的单个用户工作。这节Lec解决单台上的多用户提供服务。这里需要用到隔离性， 隔离性的实现主要由2阶段锁提供。
目标： 并发执行事务T1， T2 ... Tn，要使得它看起来像顺序执行一般
思考题：
- 从高层次看，隔离性意味着什么？
- 为什么串行运行调度（而不是并行）会导致性能不佳？
- 冲突可序列化性（Conflict Serializability）
- 两个操作什么情况下会发生冲突？
- 如何为一组事务调度创建冲突图？
- 冲突图对调度的冲突可序列化性有什么作用？
- 两阶段锁（2PL）
- 2PL 的目标是什么？
- 它有哪两个阶段？
- 2PL 的工作原理是什么？包括初始版本和带有读写锁定的版本。如何判断是否符合2PL？
- 为什么添加读写锁定可以提高性能？
- 2PL 可能导致死锁。发生死锁时我们可以采取什么措施？
Outline
- 隔离性示例
- 冲突可串行化
- 两阶段锁
- 论文阅读：ZFS
Lec 19 分布式事务
阅读参考书 §9.6
阅读论文：Consistency Rationing in the Cloud: Pay Only When it Matters, vldb09
我们的目标是在不可靠的组件上构建可靠的系统， 并且了解到事务是实现这个目标的抽象，提供了原子性和隔离性。其中原子性通过影子拷贝（性能较低）或者日志（稍微复杂但是性能更佳）实现，而隔离性通过2PL（两阶段锁）来实现。最终，我们还需要将基于事务的系统变成分布式的，即能够运行在跨机器上。
思考题
- 现在我们工作在数据分布在跨多机器上系统上，我们将主要解决什么问题（换句话说，当我们引入了跨多机器后会引入什么新的问题？）
- 如何处理网络重排序问题
- 2PC协议中可能出现的各种故障
Outline
- 两阶段锁
- 跨层和多站点的原子性
- 两阶段提交
- 论文阅读： 云环境中的一致性配给
Lec 20 复制状态机
阅读资料：
论文： In Search of an Understandable Consensus Algorithm (raft.github.io), 2014
在阅读论文时，快速浏览第5.4.3节、第7节、第9.1节和第9.2节；前4节提供了Raft的背景和动机。第5和第6节是主要的技术性章节。图2是一份很好的参考资料，在你阅读论文或者结束后可以回头再看。不要试图在转到论文的第5页之前就死记硬背整张表；可以跳过它，在阅读过程中或者最后再回来看。
**辅助理解工具：**A visualization of Raft)
思考题
两个副本不一致意味着什么？两个副本可能如何变得不一致？
考虑一个设定，其中有一个协调者、一个主副本和一个备份副本。
- 这种设置解决了哪些问题？（例如，在这种系统中，是否有可能防止数据变得不一致？）
- 这种设置不能解决哪些问题？网络分区
- 网络分区是什么意思？
复制状态机
视图服务器的作用是什么？
副本如何学习自己是主副本还是备份副本？
在这样的系统中，写操作是如何工作的？
- 系统的哪些模块进行通信，通信顺序是什么样的？
如果主副本失败会发生什么？
如果网络分区阻止主副本与视图服务器通信会发生什么？
RSM（复制状态机）提供什么样的一致性？
- 所有系统都需要这样的一致性吗？
Outline
- 复制状态机
- 论文阅读：Raft共识算法
Part IV 计算机安全
Lec 21 安全介绍&身份认证
阅读参考书 §11.2
思考题
- 解释哈希函数的基本性质，并将其与各种密码存储方案联系起来（例如，哈希函数的抗碰撞性如何帮助我们存储密码？）。
- 你不需要理解哈希函数背后的数学原理，感兴趣的话可以wiki SHA-2。我们关注的是将哈希函数作为一种加密基础原语，用于构建更安全的系统。
- 解释攻击者如何用彩虹表破解用户的密码，即使系统存储的是哈希后的密码；给定一张彩虹表，尽可能多地恢复用户密码
- 解释”慢“哈希函数的好处
- 解释攻击者如何采用彩虹表破解（部分）用户密码，即使系统存储的是使用慢哈希函数处理后的代码；给定一张彩虹表，尽可能多地恢复密码
- 解释盐化哈希如何缓解彩虹表攻击。
- 针对上述任意密码存储方案，实现用户身份验证（即实现
check_password函数） - 解释 Cookie 和challenge-response协议所解决的问题
Lec 22 低级别攻击
思考题
Lec 23 安全通道
阅读参考书 §11.3-11.5
思考题
- 给定一个结合了加密、MAC（消息认证码）和签名的协议，判断它是否提供了机密性（confidentiality） 和/或 完整性（integrity），以及它是否能够抵御重放攻击和反射攻击。
- 你不需要理解加密/解密、MAC或签名/验证背后的数学原理。我们只会问你关于将这些函数作为构建模块的方案。你应该理解它们提供的属性以及它们如何在安全通道中正确使用，但不需要理解，例如，加密提供机密性但不提供完整性的数学原因。
- 给定p 和 g，在两方之间执行Diffie-Hellman密钥交换
- 解释对Diffie-Hellman密钥交换的攻击
- 解释如何用公钥密码学来验证用户身份，包括证书的创建和分发方式
- 你不需要理解TLS握手细节，尽管你应该能够识别其中的熟悉元素（序列号、密钥等）
Lec 24 ToR
像你理解对称密钥加密、哈希函数和消息认证码（MAC）一样，理解公钥加密作为构建（更）安全系统的基础组件。请注意，使用公钥加密进行加密与使用它进行签名在实现上略有不同。描述 A 如何构造用于洋葱路由（onion routing）的数据包（即 A 加密了哪些数据，以及使用了什么密钥）。在给定不同代理配置和各种加密尝试的情况下，判断哪些类型的对手（如果有的话）能够推断出 A 正在与 S 通信。说明如何使用一个单独的代理在本地网络中创建一个安全连接，即使无法在 A 到 S 的整个路径上实现端到端安全。
之前我们讨论了如何提供机密性（Confidentaility）、完整性（Integrity）和真实性（Authenticity）。 这次的主题是匿名性（Anonymity），重点关注Tor 和 Bitcoin：
- Tor：一个让用户保持匿名的网络。
- Bitcoin：一种数字货币系统，可能提供匿名性。
它们的解决方案使用了之前学过的技术（公钥加密、签名等），将会看到一些威胁模型（Threat Models）
Lec 25 网络攻击
前面攻击者试图通过观察或者篡改数据包；这次有新的目标：使服务宕机。采用的策略是让服务拥塞，让服务花时间处理对手的请求，以至于无法处理合法的请求，这就做DoS（拒绝服务）攻击。从多个机器上发起攻击，那我们称之为DDos（分布式Dos）攻击。