转码记录 Vol.04 | 25 Fall：OS、数据库、网络，三个系统方向同时打通
从 24 Fall 开始算，这是第四个学期。前三个学期的路径：打数学和逻辑基础，自学从 Python 到 RISC-V 汇编的完整栈，动手实现 CPU、写 C、做全栈项目。这学期是系统软件层的集中展开：操作系统、数据库、网 络三个方向同步推进，配合 MIT 6.S081、Berkeley CS 186、CS 168，加 Redis 工程实践和一个从零上线的 Agent 应用。
从 24 Fall 开始算，这是第四个学期。
前三个学期的路径：24 Fall 打数学和逻辑基础，25 Winter 自学从 Python 到 RISC-V 汇编的完整栈，25 Summer 动手实现 CPU、写 C、做全栈项目。走向是从硬件层向上——先理解计算机怎么工作，再理解软件怎么在硬件上运行。
这学期是这条路径里"系统软件层"的集中展开：操作系统、数据库、网络，三个方向同步推进。校内三门课，同步跟三门顶级自学课（Berkeley CS 168、CS 186，MIT 6.S081），加 Redis 工程实践和一个从零上线的 Agent 应用项目。
校内课程
EECS 2101 – Fundamentals of Data Structures
前置是 EECS 2030（高级 OOP）和 MATH 1090（逻辑），成绩 A。
CS 61B 和 EECS 2030 里已经用过这些数据结构（链表、树、哈希表、图）。这门课的增量在于形式化方法：每个 ADT 有明确的规约语言（前置/后置条件、不变量），每个算法要证明正确性。这是 MATH 1090 里那套形式化框架在数据结构领域的直接应用。
摊还分析（Amortized Analysis）：动态数组（ArrayList）在追加元素时，满了就扩容为 2 倍并复制。单次扩容代价是 O(n)，但把这个代价平摊 到之前所有的 append 操作上，每次操作实际承担的成本是常数级的——均摊 O(1)。这个分析工具不只用于动态数组，分析 Splay Tree 等自适应数据结构都要用到。
哈希表的期望分析：哈希表的 O(1) 查找是期望情况，不是最坏情况。分析建立在哈希函数均匀分布的假设上——n 个元素分布到 m 个槽，每个槽的期望长度是 n/m（装载因子），装载因子保持常数，查找就是 O(1) 期望。最坏情况（所有元素哈希到同一个槽）是 O(n)。
图算法的正确性证明：BFS 为什么能找到最短路径（无权图）？因为 BFS 按层展开，第一次到达某节点时走过的层数就是最短路长度。用归纳法证明：第 k 层的所有节点都在最短路长度为 k 的位置上。Dijkstra 的贪心策略为什么正确？因为到一个节点的最短路不会经过一个还没确定最短距离的节点（非负权图条件）。
这门课让数据结构从"我知道怎么用"升级到"我能说清楚为什么是对的，为什么是这个复杂度"。
EECS 3421（York）+ CS 186（Berkeley）– 数据库系统
这两门课同步进行——EECS 3421 讲数据库"是什么以及如何使用"，CS 186 讲数据库"内部是怎么实现的"。两门互补，一起看是这学期效果最好的组合，成绩 A。
使用层（EECS 3421 – Introduction to Database Systems）
ER Model 到关系模式：实体关系图描述业务概念，转换成关系模式时要处理各种关联——一对多（外键），多对多（联结表），继承层次（每个子类一张表，或所有子类共享一张表）。设计选择影响后续查询效率和数据一致性维护成本。
关系代数和 SQL：SQL 是声明式语言，写的是"想要什么"；关系代数描述"怎么计算"。SELECT ... WHERE ... 对应关系代数的选择（σ）和投影（π）；JOIN 对应连接（⋈）。理解这个对应关系，有助于理解查询优化器在做什么。
Transaction 的 ACID 和隔离级别：
| 隔离级别 | 脏读 | 不可重复读 | 幻读 |
|---|---|---|---|
| Read Uncommitted | ✓ | ✓ | ✓ |
| Read Committed | ✗ | ✓ | ✓ |
| Repeatable Read | ✗ | ✗ | ✓ |
| Serializable | ✗ | ✗ | ✗ |
PostgreSQL 默认 Read Committed，MySQL InnoDB 默认 Repeatable Read。选隔离级别是在数据一致性和并发性能之间做权衡，不存在"一律用最强"的正确答案。
实现层（CS 186 – Introduction to Database Systems）
Buffer Pool Management：数据库不直接读写磁盘，而是维护内存缓冲池，把频繁访问的页（page，通常 4KB 或 8KB）缓存在内存中。替换策略（LRU、Clock）决定内存满时驱逐哪一页。这和操作系统的页面置换是同一类问题，但数据库自己管理，因为它比 OS 更了解访问模式。
B+ 树索引：关系数据库的主流索引结构不是二叉树，而是 B+ 树。原因：B+ 树的阶数（branching factor）很高（通常数百个子节点），树高极低（3-4 层就能索引数百万条记录），每次查找的磁盘 I/O 次数少。B+ 树的叶节点形成有序链表，范围查询可以顺序扫描叶层，不需要回到上层节点。
Join 算法：SQL 的 JOIN 有多种执行算法，查询优化器根据代价估计选择：Nested Loop Join（简单但 I/O 代价高）、Sort-Merge Join（适合大表、有序数据）、Hash Join（适合等值连接、大表对小表）。同一条 SQL，优化器选不同的 Join 算法，执行时间可以差几个数量级。
WAL 和 ARIES 恢复协议：崩溃恢复靠 WAL（Write-Ahead Logging）——在数据页写入磁盘之前，日志记录必须先落盘。ARIES 恢复流程：Analysis（扫描日志确认崩溃状态）→ Redo（重做所有操作，包括未提交事务）→ Undo（回滚未提交事务）。这是"先全部重做，再撤销未提交的"，和直觉上"只恢复已提交的"相反，但逻辑上更简洁。
EECS 3221（York）+ MIT 6.S081（MIT）– 操作系统
同样是校内 + 自学双轨并行。EECS 3221 提供系统性框架，MIT 6.S081（Operating System Engineering，用 xv6）通过动手实现把概念落实到代码层面。成绩 A。
进程和线程
进程是资源隔离的单位：每个进程有独立的虚拟地址空间，进程间内存默认不共享。进程间通信需要管道、消息队列、共享内存等机制，有显式的同步代价。
线程是调度的单位：同一进程的线程共享地址空间（全局变量、堆内存对所有线程可见），切换开销比进程切换小（不需要切换页表）。但共享内存意味着竞态条件（race condition）——两个线程同时修改同一变量，结果取决于执行顺序，不确定。互斥锁保证互斥访问，但会引入等待时间和死锁风险。
上下文切换：CPU 从一个进程切换到另一个进程时，要保存当前进程的寄存器状态到 PCB（进程控制块），加载下一个进程的寄存器状态，切换页表。xv6 的 swtch 函数只有几十行汇编实现了这个核心操作——读了之后，"上下文切换"从一个词变成了可以逐行追踪的代码。
内存管理
虚拟内存和页表：每个进程有独立的虚拟地址空间，通过页表映射到物理内存。RISC-V 用 Sv39 多级页表（3 级），每级页表项（PTE）包含物理页号和权限位（读/写/执行/用户/有效）。TLB 缓存最近的地址翻译，命中时直接返回物理地址；不命 中时需要"页表遍历"（page table walk），开销大；触发 page fault 时要从磁盘换入，更慢。
MIT 6.S081 的 Page Table Lab：直接修改 xv6 的页表代码，把内核的某些内存区域映射到用户地址空间。错一个权限位，程序 panic；映射范围不对，进程崩溃。这把"虚拟内存"从教材里的图变成了可以逐字节调试的代码。
系统调用的完整路径：
用户程序调用 read(fd, buf, n) 时背后发生了什么：
- 用户态：C 库函数把参数放进
a0-a2，系统调用号放进a7，执行ecall指令 ecall触发陷阱，CPU 自动切换到内核态，跳转到stvec寄存器指向的陷阱处理程序- 陷阱处理程序保存用户态寄存器，切换到内核栈
- 根据
a7里的系统调用号，分发到对应的内核函数（sys_read） - 内核函数执行，结果写入
a0 - 恢复用户态寄存器，
sret返回用户态，继续执行ecall的下一条指令
MIT 6.S081 要求在 xv6 里添加新的系统调用——修改这条链路的每一个环节：在用户态添加调用接口，在内核的分发表里注册，实现具体的内核函数。做过一次之后，"系统调用"从一个词变成了一个完整的代码路径。
文件系统
inode 结构：文件的元数据（大小、权限、时间戳、数据块地址）存在 inode 里，目录是 inode 编号到文件名的映射表（不是反过来）。硬链接是指向同一 inode 的 另一个目录条目——引用计数归零才真正释放 inode 和数据块；软链接是存储目标路径字符串的特殊文件，目标被删除后软链接就失效了。
崩溃一致性：文件系统操作涉及多个磁盘写入，中途崩溃会导致不一致状态。日志式文件系统（如 ext4、APFS）在实际写入前先把操作记录进日志，崩溃后重放日志恢复一致状态。xv6 实现了一个简化的日志层，可以直接在代码里读到它是怎么保证原子性的。
自学：CS 168 – Introduction to the Internet Architecture（Berkeley）
互联网的核心设计挑战是：在一个不可靠、去中心化的基础设施上，构建可靠的通信服务。
IP 层是"尽力交付"——包可以丢失、重复、乱序到达。TCP 在 IP 上面加了一层可靠性：序列号保证有序，确认号 + 重传保证不丢失，滑动窗口控制发送速率，拥塞控制（AIMD——加性增、乘性减）避免把网络打爆。
端到端原则（End-to-End Argument）：可靠性、加密、错误处理这些功能应该在端点（应用层）实现，而不是在网络核心实现，因为网络核心无法知道应用层对"正确性"的完整语义。这解释了为什么 IP 协议本身设计得极简——核心只做转发，复杂性推给边缘。
BGP 和路由：互联网由自治系统（AS）组成，AS 之间通过 BGP 交换路由信息。BGP 的路由策略受商业关系影响（provider / customer / peer），不只是纯粹的技术最优路径——理解了这个，才能理解为什么互联网的路由有时候会"绕远路"。
DNS 解析链路：输入 api.example.com，找到对应 IP 的过程：本地 DNS 缓存 → 递归解析器 → 根域名服务器（.）→ 顶级域名服务器（.com）→ 权威域名服务器（example.com）→ 返回 IP。理解这条链路，CDN 的工作原理和 DNS 缓存污染攻击的机制就都清楚了。
自学：Redis（工程实践）
Redis 的核心设计决策：单线程事件循环 + I/O 多路复用（epoll / kqueue）。
没有多线程意味着没有锁竞争，没有上下文切换开销；I/O 多路复用让单线程能同时监听数千个连接，有事件才处理，不阻塞等待。代价是单个命令不能耗时太长——这也是为什么 Redis 的 KEYS 命令在生产环境是危险的，它会扫描所有 key，可能阻塞数秒。
几个常用数据结构及工程应用：
Sorted Set（ZSet）：底层是跳表（skip list）+ 哈希表。跳表支持按 score 范围查询（O(log n)），哈希表支持按 key 查 score（O(1)）。实时排行榜：ZADD leaderboard 9527 user_id 更新分数，ZREVRANGE leaderboard 0 9 WITHSCORES 取 Top 10，ZRANK leaderboard user_id 查排名。
List + BLPOP：BLPOP 是阻塞式弹出——列表为空时消费者阻塞等待，有新元素 push 进来时才唤醒。这个原语让 Redis List 天然适合做轻量级消息队列，不需要额外引入 Kafka 或 RabbitMQ。
HyperLogLog： 用固定 12 KB 内存估算集合基数（unique count），标准误差约 0.81%。统计页面 UV 时，存完整用户 ID 集合需要几十 MB；HyperLogLog 在误差可接受的场景下，内存占用低三个数量级。
持久化：RDB 是快照（定时把内存数据写入磁盘），AOF 是日志（把每个写命令追加到日志文件）。RDB 恢复快但可能丢失最后一次快照后的数据，AOF 更可靠但日志文件大、重放慢。生产环境通常两者结合。
项目：Agent 应用上线
这学期用 Vibe coding（AI 辅助编程）做了一个 Agent 应用，走完了产品想法 → 技术选型 → 实现 → 测试 → 上线的完整链路。
Vibe coding 的实际体感：对有工程基础的人而言，AI 生成的代码需要审读而不是无脑接受——AI 不理解你的系统约束、不知道你的数据模型边界，在错误的假设上能写出"看起来正确"但实际有问题的代码。工程判断力（知道哪里会出问题，为什么会出问题）仍然是瓶颈，不是代码生成速度。但它确实把"从想法到能跑的原型"的时间压缩了，特别是对样板代码（boilerplate）部分。
上线和做出来的区别：本地跑通是一回事，上线是另一回事。上线要处理的问题包括：真实用户行为和设计假设不符、错误处理不完整（本地测试的 happy path 太窄）、性能边界（并发请求超出预期时的响应时间）、部署环境的配置差异。这次是第一次把这些问题真实处理了一遍，而不是停在"能跑"。
当前进行中（26 Winter）
这学期之后，转码的系统层基础基本成型。目前正在进行：
EECS 3101 – Design and Analysis of Algorithms（In Progress）：算法设计范式——分治、贪心、动态规划、图算法，以及 NP 完全问题。EECS 2101 做的是证明数据结构操作的正确性，EECS 3101 在更高层次上设计和分析算法策略。
EECS 3311 – Software Design（In Progress）：软件设计方法——设计模式、正确性规约、模块化、测试策略。这门课和 MATH 1090 的逻辑基础、EECS 2030 的 OOP 实践都有直接联系，是把工程能力系统化的课程。
此外，刚完成了 CS 146S – The Modern Software Developer（Stanford），覆盖现代软件开发的工程实践：版本控制工作流、CI/CD、代码审查、系统设计原则，以及 AI 时代的开发范式。
这学期结束时的状态，以及回头看
这学期最明显的变化是知识开始产生复利效应——早期学的东西在新的地方出现，而且以意想不到的方式相互印证。
OS 课里学的缓存替换策略（LRU、Clock），在数据库课的 Buffer Pool 里又出现了；网络课里 TCP 的可靠性机制（序列号、ACK、重传），和分布式系统里处理节点故障的逻辑是同一套思想；离散数学里的图论（最短路、拓扑排序），在 OS 的死锁检测和 EECS 3101 的算法分析里都有具体应用。前三个学期的知识是点状的，这学期开始形成网状结构。
回头看 Vol.01 里写的那句话："我想要的不是一个能通过技术面试的技能包，而是能支撑长期技术成长的基础结构。"
四个学期后可以做一个初步验证：这个选择的方向是对的。不是因为结果已经很好——毕业还没到，很多东西还在进行中。而是因为开始看到"基础结构"在实际发挥作用的样子：能说清楚一个数据库查询慢的原因在哪一层（索引？Buffer Pool？锁等待？）；能追踪一个 HTTP 请求从用户输入到服务器响应的完整路径；能读懂一段汇编代码，知道它在做什么，为什么这样写。这些能力不是工具课程给的，是系统课程积累出来的。
有一个问题值得诚实回答：四个学期下来，最难的部分是什么？
技术难度是有的，但技术难度是可以对付的——遇到不会的就查，查不明白就做 Lab，做多了就会了。更难的是：在一个需要很长时间才能看到全貌的学习路径上，如何在"我不确定自己有没有真正学到东西"和"继续走下去"之间保持平衡。
这种不确定感在早期学期里更强，因为知识还没有连成网，每一门课都是孤立的，很难感受到进展。应对方式是具体的：做项目（给出真实反馈，比考试更诚实），写复盘（把学到的东西用自己的语言重新表达，这个过程本身就是检验），和真实问题接触（面试、技术讨论、实际工程）——这些都能提供比成绩单更有质地的信息。
现在这个问题的答案是：系统开始成型了。这个结论不是乐观主义，是可以被具体指出来的——能指向某些具体的能力，说明它们是从哪里来的，以及为什么之前没有。
系列持续更新，下一 篇写 26 Winter 进行中的内容。