Computer Science Notes

一份基于 mdBook 的个人 CS 知识库，目标是对计算机科学的核心知识做全面、深入、可工程化落地的整理, 并以"一纵一横"的结构呈现: 导论卷沿时间 / 抽象层级 / 形态 / 承接四视图搭骨架, 第零到第十三部分按学科横切做工程级深度。

这份笔记的定位

• 不是面试速记卡，也不抄一遍教材的目录。
• 是自己用过的、推过的、踩过的坑沉淀下来的工程级笔记。
• 对每个专题，要求三件事：
  1. 原理讲透：知道为什么这么设计、代价是什么、什么时候该用不该用。
  2. 代码落地：用 Go / TypeScript / Python / C/C++ 至少两种语言给出可运行实现，必要时给出工业优化版本。
  3. 可被验证：复杂度、边界、对抗用例都列出。

谁应该读

• 已经能写代码、但对"为什么"还不够熟的工程师：能完成需求，但读论文、看源码、做架构选型时仍卡在数学或底层概念。
• 复习型读者：离校多年、忘了"自动机 / MVCC / Sylvester / KL"的人，需要一份从工程痛点反向回溯到原理的笔记，而不是教材正着讲一遍。
• 想横向打通 CS 的工程师：把 DSA、OS、DB、Compiler、Crypto、信息论当同一张网而不是十本独立教材来看的人——第十二部分"元抽象"专为你写。

章节骨架

合计：导论卷 + 工程化实践轴 + 第零部分（前置数学）+ 13 主题 + 形式化卷 + 量子卷，281 个 .md / ~57.6K 行 / ~220 个一线章节。

骨架的设计原则是「一纵一横」：导论卷沿时间轴（1936 → 2026）+ 抽象层级（晶体管 → AI 模型）+ 形态演进（大型机 → XPU）+ 承接链（CPU/内存 → AI）四视图把全书串起来；第零部分到第十三部分按学科横切，每个专题做工程级深度。工程化实践轴则是把基础落地到生产的手艺（Git / 测试 / CI-CD / 性能 / 安全 / 质量 / 可观测性）。读者通过 prologue/map.md 的一张矩阵可以一眼定位任何一部分所在位置。

阅读路径

起点推荐（新读者）: 先读 导论卷 — 用 4 个视图（时间 / 抽象层级 / 形态演进 / 承接链）把全书骨架在脑子里搭起来, 然后任选下面三条按背景分型的路径下钻.

按背景分型:

1. 应用工程背景 / 看论文吃力 → 先 导论 → 第零部分 数学 → 线代 → 概率 → 微积分与优化 → 再回主线.
2. 没系统学过 CS 理论 → 导论 → 数学 · 离散篇 → DSA → 计算理论.
3. 学习 Transformer 优先 → 导论 · 形态演进 (XPU 段) → 线代 → 概率 → 微积分 → 第十二部分 AI/ML.

主线推荐顺序（已系统学过、想横通 CS）：

导论卷 → 第零部分 数学 → DSA → OS → 网络 → DB → Compiler
       → 分布式 → 系统设计 → 计算机组成 → 计算理论
       → 密码学 → 信息论 → AI/ML → 元抽象（收束）

mdbook serve 后左侧目录即为主线阅读序，每章开头都有"一句话 + 思想链 + 章节列表 + 读完应能回答"。

本地预览

cargo install mdbook mdbook-mermaid mdbook-alerts
mdbook serve --open

默认监听 http://localhost:3000。

渲染特性：

• 数学公式：KaTeX 渲染，行内 $ ... $ / 块级 $$ ... $$。
• 流程图：mermaid v10 本地化嵌入（mermaid.min.js + mermaid-init.js）。
• 代码高亮：mdBook 内置 highlight.js 配合 language-xxx 标注。

编写约定

• 每章结构：TL;DR / 一句话 → 思想链（ASCII 树从工程问题回溯到原理）→ 形式化定义 → 例子 → 多语言实现 → 提示框 → 文末"一页速查"。
• 多语言实现：Go / TypeScript / Python / C++ 至少两版；工业优化版另开小节。
• 涉及分析处给出形式化结论 + 直觉解释两版。
• 重点结论用 mdBook alerts 框出：
  • > [!NOTE] — 关键观察、跨章引用入口
  • > [!WARNING] — 反直觉、常见误用、踩坑警告
  • > [!TIP] — 速查表 / 速记口诀
• 数学记号统一见 math/README.md §记号约定。

与 TODO 的对齐

后续可继续扩展方向见 TODO.md。当前 15 个部分（导论 + 工程化轴 + 数学 + 13 主题 + 形式化卷 + 量子卷）均已就位；近期已补 DNS、倒排索引/全文检索、分布式事务、虚拟化与容器、SSD/NAND 存储硬件、经典 ML 与树模型、LLM 推理部署，并对 DSA 的贪心/回溯做了深度重写。后续增补按需进行（如流处理引擎、图数据库、工程化的专项实操）。

导论卷 · 计算机基础知识体系

一句话

这份笔记剩下 13 部分（数学 + DSA / OS / 网络 / DB / Compiler / 分布式 / 系统设计 / 组成原理 / 计算理论 / 密码学 / 信息论 / AI/ML / 元抽象）是按学科纵切的深度章节；这一导论卷反过来——沿着时间与抽象层级横拉一条贯穿全场的纵贯线, 让你先在脑子里搭起一座"全景骨架", 再下钻各主题时永远知道自己在哪一节脊椎上.

思想链

1936 Turing / Church                ─── 可计算性的形式化
   │
1945 von Neumann / ENIAC             ─── 存储程序 → CPU + 内存一体
   │
1957 Bell Labs / IBM 360             ─── 大型机时代 (transistor, OS, 编译器, Fortran)
   │
1971 Intel 4004                      ─── 微处理器; 半导体路线胜出
   │
1975 Altair / Apple II (1977)        ─── 个人 PC 时代起
   │
1981 IBM PC + x86 + DOS              ─── PC 标准化; Wintel 联盟
   │
1991 Linux 0.01 / WWW (Berners-Lee)  ─── 自由 OS + 全球网
   │
2006 AWS EC2 / iPhone (2007)         ─── 云计算 + 移动互联网 (ARM 逆袭)
   │
2012 AlexNet / GPU CUDA             ─── 深度学习靠 GPU 起势 → XPU 时代
   │
2017 Transformer                     ─── 大模型; AI 作为新计算范式
   │
2022 LLM / 扩散 + RLHF               ─── 生成式 AI 工程化
   │
2024+ NPU / TPU / 量子 / CXL         ─── 异构计算 (XPU) 成主流
   │
2025 GPT-5 统一 o 系 / DeepSeek-R1    ─── 推理模型 + Agent (MCP) 主流化
   │
2026 Claude 5 / Gemini 3.6 / Rubin   ─── 月级迭代; 整柜算力 + HBM4 + 量子纠错爬坡
   ▼
你现在 ↓
   ──数学──硬件──OS──网络──DB──编译──分布式──系统设计──计算理论──密码学──信息论──AI──
       │      │    │     │    │     │      │         │         │       │      │     │
       └─ 导论卷 把这一整条用「纵贯线 + 抽象层级 + 形态演进」串起来 ─┘

你将带走什么

读完应能:

1. 站在 1936 / 1945 / 1971 / 1991 / 2006 / 2017 / 2024 / 2026 的每一节点上, 知道那一年"硬件能力 / 编程模型 / 主流抽象"三件事的契约是什么, 一句话解释为什么那节点是质变而不是渐进.
2. 看懂"抽象层级": 晶体管 → 逻辑门 → ISA → microarch → 机器码 → 汇编 → C → OS 系统调用 → 高级语言 → 编程框架 → AI 模型. 这十层里每一层都靠下一层的契约与不等式支撑; 知道这些契约何时被打破 (Spectre / GC 暂停 / cache miss / NaN).
3. 用一条主线把计算机从真空管演到 XPU 讲清: ENIAC → IBM 360 → PDP/Unix → x86 PC → ARM 移动 → 云原生 → GPU 深度学习 → LLM XPU. 每一阶段的"参数" (单台算力 / 价格 / 功耗 / 程序员数) 与"软件范式"如何同步变.
4. 看任意一份新技术文档 (e.g. H100 spec / CUDA 12 / LLaMA-3 卡) 立刻看出它在"层级 / 历史 / 异构形态"哪一格, 不被名词震到.
5. 从纵贯线一眼定位本书每一部分的位置: 看完导论后再回各部分深读时不再"信息孤立".

章节结构

• 开篇: 这卷要做什么 ← 当前
• 1. 计算机发展史纵贯线: 1936 → 2026
• 2. 抽象层级: 从晶体管到 AI 模型的十层金字塔
• 3. 形态演进: 大型机 → PC → 单片机/ARM → 云 → Web → AI → XPU
• 4. 主干纵贯: CPU/内存 → OS/Linux → 网络/Web → DB → 编译 → 分布式 → AI 的承接链
• 5. 全书地图: 13 部分与导论的交叉索引

这卷不是什么

• 不是 Wikipedia 复制粘贴. 重点在"每一节点改变了什么契约", 不在"年份-事件" trivia.
• 不是 教你硬件设计 / OS 内核 / 编译器实现的入口 (那是后续 8 部分 OS / 5 部分 Compiler 做的事).
• 不是 答辩稿式编年史. 锚点是形式系统 + 硬件能力 + 软件范式三联, 而不是换 CEO.

与 13 部分的接口

阅读路径

• 第一次来全书: 先读导论 5 章 → 再按 主 README 的阅读路径下钻.
• 已熟 CS 想横通: 直接读 map 与 standing-shoulders, 跳过 history.
• 学 Transformer 优先: 看 mainframe-xpu 的"GPU / XPU"段即可, 跳到第十二部分.

下一篇: 1. 计算机发展史纵贯线: 1936 → 2026.

1. 计算机发展史纵贯线: 1936 → 2026

TL;DR

90 年计算机史用三条线索串起: (1) 形式系统: "什么是可计算"逐步被严格定义;(2) 硬件能力: 计算速度、内存、IO 用摩尔定律等指数曲线提升, 价位指数下降, 推动"软件范式"被迫重组; (3) 抽象层级: 每一代工程师不得不引入新抽象来对抗复杂度, 把上一代底层细节封装到契约里.

每一节都讲: 那年发生了什么 / 缔造了什么契约 / 把什么写进了"已经不可能回退"的清单.

读完应能: 用 20 分钟讲清计算机从 Turing → 2026 推理模型时代的关键节点, 每个节点一句话点破质变.

0. 概览图

1936   Turing 论文 "On Computable Numbers..."
1945   von Neumann 架构报告; ENIAC 完成
1947   Bell Labs 三人组发明晶体管
1957   Sputnik → ARPA 成立; FORTRAN; IBM 360 开端
1961   COBOL; 第一台分时系统 CTSS
1969   UNIX Prototype (Bell Labs); ARPANET 起
1971   Intel 4004; 第一台微处理器; 软盘
1975   Altair 8800 → Bill Gates/Microsoft; "个人计算" 概念
1977   Apple II; Commodore PET; TRS-80
1981   IBM PC (开放架构 → clone 洪流 → Wintel 垄断)
1985   Windows 1.0; ARM1 (Acorn)
1991   Linux 0.01 (Linus); WWW 第一网页
1993   Mosaic → Web 爆炸; iPhone 之父在此出生
1995   Win95; Java 1.0; Amazon/eBay (Web 商业化)
2006   AWS EC2 起; iPhone (2007); 触屏 + app store
2012   AlexNet (ImageNet top-5 < 16%, GPU 训练); "深度学习 = GPU"
2017   Transformer / "Attention Is All You Need"
2020   COVID → 数亿人远程办公 → 云速率 5x; 扩散模型
2022   ChatGPT —— 5 天注册破 100M; RLHF 出现工程化
2023   LLaMA / Qwen / DeepSeek 系; 开源 70B 可单机推理
2024   NPU / H100 / TPU v5p / Groq / Cerebras / 量子计算长征
       Blackwell B200 / GB200 NVL72 (NVIDIA); DeepSeek-V3 开源 (12 月)
2025   GPT-5 统一 o 系; Claude 4.x / Gemini 3 / Grok 4 推理模型常态化;
       DeepSeek-R1 "时刻"; Agentic AI + MCP; gpt-oss 开源; HBM4 量产;
       Google Willow 低于阈值量子纠错
2026   GPT-5.x→5.6 / Claude 5 / Gemini 3.6 Flash / DeepSeek R2 快节奏迭代;
       NVIDIA Rubin 量产 + AMD MI450; 昇腾 950 超节点 (1024 卡);
       HBM4 三家量产 (~2 TB/s/stack) + CXL 3.2; 量子数十逻辑 qubit

一、1936-1945: 可计算性的形式化 + 第一台通用电子计算机

1.1 Church-Turing 论题 (1936)

• Alan Turing: 论文 On Computable Numbers, with an Application to the Entscheidungsproblem 提出 Turing Machine.
• Alonzo Church: lambda calculus 同期给出等价定义.
• Church-Turing 论题: 任何"算法可计算"的函数 = TM 可计算 (直觉但不是定理, 是把"算法定义"和"TM 定义"绑成一体).

→ 回到 第九部分 计算理论 看形式化定义与停机问题.

1.2 第二次世界大战的硬件倒逼

• Colossus (1943, Bletchley Park) 破译 Lorenz 密码的专用机器 (非通用).
• ENIAC (1945, Eckert & Mauchly, 宾大): 第一台通用电子数字计算机. 17468 真空管、30 吨、5 kW、每秒 5000 加法.
• EDVAC 报告 (1945, von Neumann): 提出存储程序架构, CPU + 内存 + IO 三分, 指令和数据同存内存. 这就是后世"von Neumann 架构".

二、1947-1960: 晶体管 + 大型机 + 高级语言

2.1 晶体管 (1947)

Bell Labs 的 Shockley / Bardeen / Brattain 发明点接触晶体管 (Nobel 1956). 替代真空管: 体积小、能耗低、长寿命 → 可堆大规模. 没它就没有集成电路.

2.2 集成电路 (1958)

• Jack Kilby (TI) 与 Robert Noyce (Fairchild) 几乎同时分别发明 IC.
• 1965 Gordon Moore 提出 Moore 定律 (每 18-24 月晶体管数翻倍). 半个世纪后这条曲线仍未平.

2.3 大型机时代 (1955-1975)

• IBM 701 (1952): IBM 第一台商用电子计算机.
• IBM S/360 (1964): 主打"全系列兼容", 引入 ISA (instruction set architecture) 与 microarch 分离的概念. 这一台机器让"程序员一旦写汇编, 在更高型号同运行"成为可能, 也让ISA 抽象成为行业必需.

→ 这是"计算机抽象层级"的真正起点, 见 abstraction-layers.

2.4 高级语言史 (1957-1972)

→ C 与 Unix 是孪生兄弟; 操作系统首次可移植 (PDP-7 → PDP-11 → VAX). 这件事让"硬件厂家锁定"被反复松动, 是后续一切的种子.

三、1969-1981: Unix + ARPANET + 微处理器 + PC

3.1 Unix (1969)

Ken Thompson & Dennis Ritchie 在 Bell Labs 为 PDP-7 写"unics" (-> Unix), 后用 C 重写为可移植 OS. 几乎所有现代 OS (Linux, macOS, iOS, Android 底层, BSD) 都直接或间接是 Unix 派生.

贡献: 文件即字节流 / 进程 / fork-exec / pipe / 小工具组合的 shell 哲学 / 网络套接字.

→ 本书 第二部分 OS 几乎是 Unix 与 Linux 工程化的延伸.

3.2 ARPANET (1969)

第一个分组交换网络; 4 节点起步 (UCLA / SRI / UCSB / Utah). 1973 TCP/IP 雏形 (Cerf-Kahn). 1983 NSFNET 升级 TCP/IP, "互联网" 实质开始.

1971 Ray Tomlinson 发第一封 email. 1976 Apple I 卖给爱好者; 1977 Apple II 内置 BASIC + 成品机箱; 1981 IBM PC 出货, 标致"个人计算机"被企业级认可.

3.3 Intel 4004 (1971): 第一颗微处理器

Intel 4004 = 2300 晶体管, 4-bit, 740 kHz. 上面运行 Busicom 打印机的计算. 这件事的本质: CPU 也能做成芯片而不再是机房箱柜. 后续 8080/8086 (1978 x86 起) 一步步推.

3.4 Altair 8800 (1975) 与 Microsoft 起步

Pop Electronics 1975 封面 Altair 8800 → 哈佛大二学生 Bill Gates 与 Paul Allen 写 Altair BASIC 解释器, 一年不到成立 Microsoft. "软件"作为商品第一次清晰化.

四、1981-1995: PC 标准化 + GUI + 互联网基础

4.1 IBM PC (1981)

• 用 Intel 8088 (4.77 MHz, 16-bit 内核 + 8-bit 外总线); OS 用 Microsoft DOS (买断 Seattle Computer 产品 QDOS 改名).
• 关键: 架构未保密 → Compaq / Phoenix BIOS 等厂商大量克隆 → "PC 兼容机"潮 → x86 成为事实标准.

→ x86 vs ARM 分叉的故事从这年开始, 见 mainframe-xpu.

4.2 WIMP + GUI

• 1973 Xerox PARC 的 Alto 第一次实现 GUI (windows, icons, mouse, popup).
• 1984 Apple Macintosh 商业化 GUI. 1985 Windows 1.0.
• 1989 Tim Berners-Lee 在 CERN 提 HyperText + HTTP/HTML, 写下第一个 web server.

4.3 LAN 与数据库

• 1980 Novell NetWare / 3Com Ethernet 网卡让办公室组 LAN 成常态.
• 关系数据库 1970 Codd 论文 → Oracle (1979) / IBM DB2 (1983) / PostgreSQL前身 Postgres (1996). 这是 第四部分数据库 的源头.

五、1991-2001: Linux + Web + 开源

5.1 Linux (1991)

Linus Torvalds 在赫尔辛基大学宿舍写 Linux 0.01 (1991-08-25 公告), 1992 GPL 化 → 开源爆发. 90 年代 ~ 一切服务器都 Linux 化; "LAMP stack" (Linux+Apache+MySQL+PHP) 成为 web 默认.

→ 这是 Unix 之外第二支不锁厂商的开源 OS, 给后续 web 服务、云计算、AI 训练堆栈全部用 Linux 作底.

5.2 World Wide Web (1991)

Tim Berners-Lee 在 CERN 部署第一个 web server, HTTP 0.9 / HTML. 1993 Marc Andreessen 写 Mosaic 浏览器 → Netscape (1994) → 商业化 web.

→ 后续影响 第三部分网络 的一切. HTTP 是几乎所有协议层的"最后一公里".

5.3 开源浪潮

• 1985 GNU (Richard Stallman) → GCC, glibc, bash, Emacs.
• 1991 Linux + 1995 Apache HTTP 服务器 + 1996 PostgreSQL + 2005 Git.

→ 2000 年后开源几乎成为基础设施软件默认形态, 也是 AI 时代模型托管 (HuggingFace) 的预设.

六、2001-2010: Web 2.0 + 移动 + ARM 逆袭 + 虚拟化

6.1 AJAX + Web 2.0 (2004-2005)

• Gmail (2004) / Google Maps (2005) 引爆 AJAX → 浏览器成"富客户端", SPA (Single Page App) 兴起.
• 2006 AWS EC2 商业化 (虚拟机租用), 启云时代.

6.2 iPhone + 触屏 + App Store (2007)

• 2007 初代 iPhone (ARM11 412 MHz, 128MB RAM) 改变"手机"定义: 全屏触屏 + 应用商店.
• 2008 Android 1.0; ARM 几乎一夜成为移动通用 CPU → 制造规模超 x86 → RISC 复兴.
• 2010 iPad; 2011 Chromebook.

→ ARM 在手机出货量以 100× 量级碾压 x86, 后又通过 Apple Silicon M1 (2020) 与 AWS Graviton 反杀数据中心. 见 mainframe-xpu.

6.3 虚拟化与云萌芽

• 1999 VMware; 2003 Xen; 2006 EC2; 2008 KVM 入 Linux 主干.
• "弹性的服务器"成为商品 → 创业公司不需自买机架 + 上架.

→ 第七部分系统设计 的所有 case (Twitter Snowflake / Google 三件套 / Kubernetes 控制平面) 都默认这套云底座.

七、2010-2020: 深度学习 + 大数据 + 容器化

7.1 GPU 通用计算爆发 (2007+ CUDA, 2012 AlexNet)

• 2007 NVIDIA 推出 CUDA 让 GPU 可做通用并行.
• 2012 AlexNet (ImageNet top-5 error 16%) 第一次大规模用 GPU 训 CNN, 一举把深度学习从学识题变成工业题.
• 2013-2015 VGG/ResNet/Inception; 2014 GAN; 2015 Batch Norm; 2016 ResNet (152 层可训).
• 2017 Transformer → 序列建模换赛道.

7.2 大数据基础设施 (2004 MapReduce / GFS → 2010 Spark)

• 2004 Google MapReduce & GFS paper → Hadoop (2006) 开源 copy.
• 2006 BigTable paper → Cassandra (2008) / HBase / Dynamo (2007) / Redis (2009).
• 2014 Kubernetes; 2015 Docker 1.0 主流; 2018 service mesh / Istio / Envoy.

→ 第六部分分布式系统 的 CAP / Paxos / Raft / K8s 全靠这十年开源沉淀.

7.3 CPU 增长遇阻 + 多核 + 加速器登场

• 2005 后单核性能增速放慢 (Dennard scaling 结束), 8 核 / 16 核 / 32 核 CPU 成主流.
• 2010 后 GPU / TPU / FPGA 在数据中心占比上升 → 异构计算开篇.
• 2017 RISC-V 基金会成立; ISA 开源化大潮.

→ 直接铺垫 第八部分组成原理 里的 GPU / TPU / NPU 章节.

八、2020-2024: 大模型 + 生成式 AI + XPU 主流化

8.1 关键事件

• 2020 GPT-3 (175B); scaling law (Kaplan 2020) 起势.
• 2021 ViT / DALL-E; 2022 ChatGPT (5 天 +1 亿用户, 历史最快).
• 2022 扩散模型 (Stable Diffusion, Midjourney).
• 2023 LLaMA-2 (Meta); Qwen / Baichuan / DeepSeek 等中国开源; 推理成本 -90% / 半年.
• 2024 推理为王, TPU v5p, Groq LPU, Cerebras WSE, RISC-V 在 AI子系统, NPU 进入个人 PC 与手机, CXL 内存池化.

8.2 范式迁移: CPU 时代 → GPU 时代 → XPU 时代

→ "XPU" 是 Andy Bechtolsheim 2017 命名,统一意味着异构: CPU 处理控制流, GPU 处理大并行, DPU 卸载网络与存储, NPU 在终端推理. 见 mainframe-xpu 详述.

8.3 RLHF 工程化

• 2022 InstructGPT → ChatGPT 把"政策对齐"从科研推成通用工程.
• 后续 DPO (Direct Preference Optimization, 2023) / RLHF with KL penalty / GRPO (DeepSeek 2024) 成主流.

八·5、2025-2026: 推理模型、Agentic AI 与 Blackwell 时代

按 2026-08 公开资料 (原厂 release note / 主流媒体) 核对; 模型发布与数字以官方口径为准.

8.5.1 推理模型 (Reasoning Models) 主流化

• OpenAI o1 (2024 末) 与 o3 (2025): 把 Chain-of-Thought 显式化训练, 用 RL 学习"长内部思考"过程; "test-time compute" 成为新维度.
• DeepSeek-R1 (2025-01): 完全开源的 reasoning 模型, 凭冷启动 + 规则奖励 RL 训出一阶性能接近 o1; 价格却只有零头, 一夜踩穿美国闭源厂商定价 → "DeepSeek 时刻".
• GPT-5 统一 o 系 (2025-08): OpenAI 把 o 系并入 GPT-5 按需切换推理 / 普通模式, 同周开源 gpt-oss-120b/20b (2025-08-05, Apache 2.0); 此后按"月"迭代 (5.1 → 5.2 → … → 5.6), 2026-07 的 GPT-5.6 再分成 Sol / Terra / Luna 三档能力层.
• Anthropic (2025-2026): Claude 3.7 / 4.x 把 "extended thinking" 做成内置开关; 2026-02 Sonnet 4.6 首搭 1M context, 2026-06/07 进入 Claude 5 时代 (Sonnet 5 / Opus 5), agentic 编程与超长上下文成为默认能力.
• Google / xAI (2025-11): Gemini 3 Pro 与 Grok 4.1 同期发布; 2026-07 Google 出 Gemini 3.6 Flash / 3.5 Flash-Lite / 3.5 Flash Cyber 主打 agent 效率, Grok 5 却一再跳票、只更新到 4.5 —— 大版本节奏第一次被拉开.
• 中国开源路线齐发 (2025-2026): DeepSeek V3.2 → R2 (2026 初)、Qwen3-Max → Qwen3.5 (2026-02)、Kimi K2.5、GLM-Z1 等, 把 RL + verifier + 过程奖励走通并保持开源权重.

→ 统计学含义: 不再只是 next-token 似然, 而是 MCTS + PRM + verifiable reward 上的策略优化; 模型从"模仿分布" 变 "在状态空间搜解". 这把强化学习 (RL) 从边缘推成 LLM 训练 core 环, 且 2026 年推理算力曲线比预训练更陡 —— "推理时算力" 成为新的军备竞赛主轴.

8.5.2 百万 token 上下文与 KV / attention 革新

• 2024 Gemini 1.5 Pro 首秀 1M context; 2026-03 Claude Opus 4.6 / Sonnet 4.6 把 1M context 转正为 GA (标准价、无溢价), Gemini 3 / Claude 5 延续 1M+ 原生支持, OpenAI 400K 走"短上下文快推理" 路线.
• 技术栈: sparse attention + sink token + RoPE 外插改进 (YaRN / LongRoPE) + KV 量化 (FP8 / INT4) + PagedAttention.
• → 把 第十二部分 §2 MHA 与 §3 backprop 里 attention 显存 $O(T^2)$ 的容器打到工程极限; 长上下文从"演示指标" 变成"默认产品参数".

8.5.3 NVIDIA Blackwell 与 HBM4 / Rubin

• B200 (2024 发布 / 2025 量产): 双 die, 192 GB HBM3e, 8 PFLOPS FP4. 注意 B200 不再单芯片, 而是 2 个 reticle 用 NV-HBI 互连封装.
• GB200 NVL72: 36 块 Grace CPU + 72 块 B200 通过 1.8 TB/s NVLink 互联构建单机柜巨型张量机.
• HBM4 (JEDEC 2025-04 定标; SK 海力士 2025-10 量产 → Samsung 2026-02 → Micron 2026-06 通过 NVIDIA 认证): 位宽 1024→2048 bit, 单 stack 约 2 TB/s, 8-hi 24 GB / 12-hi 36 GB 起步; 配合 CXL 3.x 让 Tiered memory 走向主流.
• Rubin / Vera Rubin (CES 2026 发布, 2026 下半年量产): 72 Rubin GPU + 36 Vera CPU, NVLink 6 (每 GPU 3.6 TB/s) + ConnectX-9, 把"整柜张量机"再推上机架级 NVLink Domain; 2026 起 AI 硬件竞争从单卡打到整机柜.

8.5.4 ASIC 与 XPU 谱系扩展

• Google TPU v6 Trillium / AMD Instinct MI450 (2026, 432 GB HBM4, 19.6 TB/s, Helios 机架) / AWS Trainium 2: 都朝"张量 + 互联" 押大注; Intel Falcon Shores 2025-01 取消 (仅作内部测试芯片), 转向机架级 Jaguar Shores —— 路线图再一次证明竞争重心在"系统" 而非"单卡".
• Groq LPU 主打"流式推理"几十到几百 tok/s 单卡.
• Cerebras WSE-3 与 SambaNova SN40L: 整片晶圆级芯片 + 长上下文推理 SDK.
• Apple M5 (2025-10) / M5 Pro/Max (2026-03) Neural Engine + 骁龙 X Elite NPU 终端推理普及; 一台笔记本上跑百亿参数成产品级.
• 国产: 昇腾 910C 大规模国产替代 → 昇腾 950 超节点 Atlas 950 SuperPoD (2026 WAIC 首展: 1024 卡互联, 1 EFLOPS FP8 / 2 EFLOPS FP4, 256 TB 统一内存), 昇腾 384 超节点已商用 750+ 套; SMIC N+2 (7nm 等效) 2026 年底产能目标 7 万片/月; 寒武纪思元 590 / 阿里倚天 / 含光 亦成熟.

8.5.5 Agentic AI + MCP 协议

• 2024 末 Anthropic 提出 MCP (Model Context Protocol) 让 LLM 与外部工具 / 数据源通过标准 JSON-RPC 协议交互.
• 2025-2026 GPT-5.x / Claude 5 / Gemini 3.x 把 tool use / 多轮调用 / sub-agents 工程化; Codex / claude-code 等 coding agent 成为首个"产品级 agent" 品类, "Agent = LLM + tool loop + memory" 成主流范式.
• 由此工具调用从单 API 进化为"企业应用总线"; 安全与沙箱 (Yamada / eBPF 隔离) 同步兴起, agent 从 demo 走向生产.

8.5.6 量子计算 "logical qubit" 时代

• Google Willow (2024-12, 105 qubit): 首次演示表面码低于阈值 (below threshold) —— 错误率随码距增大指数下降, 纠错从理论变成工程曲线.
• Quantinuum Helios (2025-11): 98 物理 qubit 编码出 48 个逻辑 qubit, 2Q 门平均保真 99.92%, 是目前逻辑 qubit 的最高纪录.
• 2026 现实: 主流设备落在 10-48 逻辑 qubit, 尚未抵达 "~100 logical" 门槛; IBM 200 逻辑 qubit 的 Starling 预期 2028-2029.
• 但 Shor 还要 100 万-1 千万物理 qubit 才能威胁 RSA-2048; 业内"Y2Q (years to quantum)" 估计仍在 10-30 年.

九、用一条数学线把 1936-2026 拉直

1936 TM        ──── "可计算" 形式化
                                        1948 Shannon 信息论 ── 熵 = 压缩下界 / 容量 = 通信上界
                                              │
1980 协议理论 (Lamport / Pew / FLP) ─── 分布式算法理论起步
                                              │
1995 RSA / DH / ZKP 一线 (Crypto)
                                              │
2012 深度学习 = 反向传播 + GPU + 概率分布建模 大爆
                                              │
2022 大模型工程化 = 自回归 + RLHF + 推理优化
                                              │
2024 异构计算 = 数学调度优化 + 硬件窄并发抽象
                                              │
2025 推理模型 + Agent = RL + verifier + 显式思维链;
       Blackwell B200 把"芯片"从单片推到多 reticle 系统
                                              │
2026 HBM4 (~2 TB/s) + CXL 3.2 + 昇腾 950 超节点 + 量子数十逻辑 qubit:
       数学调度不止 on-die, 跨 memory / chiplet / quantum 同步推上日程

这条线告诉读者: 数学在第零部分不是孤立基础, 而是在 1936-2026 这 90 年里每隔十几年就被换一次主角, 从离散的 TM → 概率的信息论 → 协议的不变式 → 数论的密码学 → 优化的 AI.

十、一句话点破每一年质变

十一、结束 + 速查表

下一篇: 2. 抽象层级: 从晶体管到 AI 模型的十层金字塔.

2. 抽象层级: 从晶体管到 AI 模型的十层金字塔

TL;DR

计算机科学的本质 = 分层抽象: 每一层为上层提供契约 (一组语法 + 语义 + 不变式), 上层不知道也不需要知道下层如何实现. 但抽象会泄漏 — 当下层契约被打破时, 上层必须有人理解并修复.

这条"十层金字塔"从前一天最熟悉的程序语言脚本一路下钻到晶体管电压, 再上钻到 AI 模型. 一共 10 层, 每层一句话:

┌──────────────────────────────────────┐
│ 10. AI 模型 / 智能体层 (Agent)         │   GPT / Claude / Agent
│  9. 应用与框架层                       │   web / db / 分布式 / 编程框架
│  8. 高级语言运行时层                   │   Java JVM / Python / V8
│  7. 系统调用接口层                     │   POSIX / Win32
│  6. 操作系统内核层                     │   Linux / NT
│  5. 指令集架构 (ISA) 层               │   x86-64 / ARM / RISC-V
│  4. 微架构 (microarch) 层              │   流水线 / 超标量 / cache / OoO
│  3. 数字逻辑层                         │   RTL / 门 / 触发器 / FSM
│  2. 模拟电路层                         │   放大器 / ADC / DAC
│  1. 半导体器件物理层                   │   MOSFET / 晶体管 / PN 结
└──────────────────────────────────────┘

读完应能: 任意给一份技术资料能立刻说出它在哪一层 / 它依赖下层哪契约 / 它向上提供什么. 看到现象 ("Redis 抖动"或 "Hyper-threading 引起 30% slowdown") 能沿层级定位泄漏源.

一、为什么抽象分层

1.1 复杂度 vs 单脑容量

• 现代数据中心有 $\sim 10^{18}$ 晶体管, $\sim 10^9$ 行代码, 个人脑容量 $\sim 10^{11}$ neurons. 显然不可能"自上而下" 一气讲清.
• 抽象分层 = 把능力分工: 一层专家可以专心设计下一层 + 履行契约, 上层专家可以假定契约不变.

1.2 每层的契约

• 语法: 什么样的输入合法.
• 语义: 输入对应什么输出 / 系统行为.
• 不变式: 上层可以依靠的"始终为真"的保证 (e.g. "malloc 返回 non-NULL 不意味分配成功, 还要 free"; "TCP 是 reliable" 不变式 vs 链路层"按位丢失" 等等).

1.3 抽象会泄漏

"All non-trivial abstractions, to some degree, are leaky." —— Joel Spolsky, 2002.

抽象整层错误不存, 至少六个典型泄漏手段:

• 性能泄漏: 上层假设"免费", 实际 cache miss / page fault / GC pause.
• 正确性泄漏: 上层定义 OK, 下层在并发 / 故障下会违反契约 (e.g. fsync 在某些 fs / drive 上不保证 crash safe).
• 资源泄漏: 上层 closure / lambda 引用底层 file descriptor 不释放; OOM.
• 延迟泄漏: 上层 RPC, 下层跨网 RTT 50ms, 上层调 1000 次 = 50s.
• 资源粒度泄漏: 上层"加 1 字节" 在下层是"加 1 page" (4KB).
• 失败模型泄漏: 物理断电 → 网络 quiet → 上层 app 假死.

→ 本书每一部分都是某一层专家视角, 第十三部分元抽象专门谈同级跨层共同点.

二、底层向上: 第 1-4 层

2.1 第 1 层: 半导体器件物理

契约: 把外部电压 / 电流转换为可预测的"开关"行为.

• MOSFET (Metal-Oxide-Semiconductor Field-Effect Transistor): 三端 Gate/Source/Drain, Gate 电压控 Source↔Drain 通道.
• 工艺节点 (5nm / 3nm / 2nm) 是 marketing 词; 真晶体管密度与 pitch 跟名字关系不严格对应.
• 关键变数: $V_{th}$ (阈值), $I_{on}/I_{off}$ 比, 漏流 (static power), 短沟道效应, 量子隧穿.

2.2 第 2 层: 模拟电路

契约: 把 MOSFET、电阻、电容组成放大器、ADC/DAC、PLL、SRAM cell.

• SRAM 单元 = 6T, 6 个晶体管组成双稳态寄存器.
• DRAM 1T1C: 1 MOSFET + 1 电容; 容量高但需周期刷新 (64ms 内必须读回写一次).
• PLL 用作时钟倍频, ADC 把"模拟信号" 数化为 ADC 输出.

→ 这一层给硬件上一个"稳定态 + 离散数字"契约; 上层第 3 层 RTL 不再关心电压.

2.3 第 3 层: 数字逻辑 (RTL / Verilog)

契约: 把布尔函数 (组合) 与时序逻辑 (状态) 组成可综合电路; 时钟无穷假设下, 输出由输入决定.

• RTL (Register-Transfer Level): Verilog / VHDL 描述数据在寄存器之间流动 + 触发时序.
• 自动综合 + 布局布线 (PD).
• 关键抽象: 时钟域同步 (CDC), 亚稳态 (metastability), 关键路径 (timing closure).
• 组合电路: 逻辑门, 多路选择, 算术单元 (一位加法基本是 28T 半加器 + 9T 全加).
• 时序电路: 触发器 + 状态机 + counter.

2.4 第 4 层: 微架构 (microarch)

契约: 把 RTL 实现成"对上一层 ISA 提供指令的时间抽象" — 一条指令在多少周期做完、是否可乱序、是否可预测.

• 流水线 (5 级 / 16 级), 超标量 + OoO (Tomasulo), 分支预测 (Tage / Perceptron).
• Cache 层次 L1 / L2 / L3 / DRAM → 见 第八部分 memory hierarchy.
• Memory consistency & reorder buffer (ROB), memory ordering.
• TLB + huge page + page walk.
• GPU SM / warp scheduler; Tensor Core 矩阵乘张量核心.

三、中层: 第 5-7 层

3.1 第 5 层: ISA (Instruction Set Architecture)

契约: 一份"机器指令 + 寄存器 + 寻址模式 + 系统态"的精确规范, 上层编译器目标即它, 下层微架构实现即它.

• CISC: x86-64 / zArch. 变长指令, 复杂寻址, 长历史兼容.
• RISC: ARM (v8/v9), RISC-V, MIPS. 固定 32 位指令, load-store 抽象, 解码简单.
• 子系统: 向量扩展 (AVX-512 / SVE2 / RISC-V V), AMX (Intel Advanced Matrix Extensions), Apple Silicon Matrix Coprocessor.

→ 第 8 部分 指令集架构 详解.

3.2 第 6 层: 操作系统内核

契约: 通过系统调用接口, 对上层隐藏硬件细节: 进程调度、虚拟内存 / 页表、文件系统、套接字、设备驱动.

• Unix: 进程 fork/exec, 文件 = 字节流, 设备 = /dev 下 file-like, socket = file descriptor.
• Linux: monolithic + module; CFS 调度, cgroup v2 隔离, eBPF 动态扩展.
• Windows NT: 微内核思想实用化, micro-kernel-ish + Executive.

→ 第二部分 OS 全部讲这一层.

3.3 第 7 层: 系统调用 POSIX

契约: 上层应用看到的标准 API: read/write/open/close/fork/exec/mmap/epoll/....

• POSIX (IEEE 1003.1) 让软件跨 Unix 兼容.
• Windows Win32 等价.
• 这一层一旦定下来, 70 年的 C 代码都能在 2024 Linux 跑 (grep old codebase).
• 典型泄漏: fork + exec 在 fork 后 fd 复制仍占用 → 父子进程都需 close. Threads 不是"轻量 fork" → 用 pthread_create 而且内存共享 (信号 mask, thread-local, errno 要小心).

四、上层: 第 8-10 层

4.1 第 8 层: 高级语言运行时

契约: 提供更高级抽象 (GC / 闭包 / 模块 / 异步) 对编译后的字节码 / 解释后的 AST 解释运行, 调系统调用完成 IO.

• JVM / HotSpot: 字节码 + JIT (tiered compilation 把热点方法机编本地 code).
• CPython: 解释 + 字节码; GIL (global interpreter lock) 限制纯 Python 多线程; PyPy JIT.
• V8 / JS 引擎: tiered JIT (Ignition + TurboFan + Maglev + Sparkplug).
• Go runtime: goroutine + GMP + runtime 调度 + channel, binary 自带.
• Erlang BEAM: actor 模型 + 极轻量进程 + 热升级.
• C/Rust: 无运行时 (Rust 用 minimal runtime), 编译到机器码直接跑.

→ 第五部分编译原理的 JIT 与 _meta runtime-semantics 详解各派不同.

4.2 第 9 层: 应用与框架层

契约: 业务语义 + 编程框架的库抽象 + DevOps 链路.

• Web: React / Vue / Spring / Gin / Django; BFF; 后端服务 (RPC / GraphQL).
• 数据库客户端: ORM (Hibernate / SQLAlchemy / GORM); 迁移工具 (Flyway).
• 分布式: Kafka / Pulsar; gRPC / Thrift; Etcd / ZooKeeper; K8s operator / Helm / Argo CD.
• 数据 / ML: Spark / Flink / Dask / Ray / Airflow; experiment tracking (MLflow / W&B).

→ 第七部分 系统设计 与第六部分 分布式 都在这一层操作.

4.3 第 10 层: AI 模型 / Agent

契约: 输入 prompt / multimodal content, 输出 tool call + text; 训练时还要有 reward 信号或对比信号.

• 现状: 2024-2026 是"模型即应用" 范式年; LLM 不止续写, 还有 tool use (MCP), 长 context memory, multi-agent orchestration.
• 形态: 在线服务 (OpenAI / Anthropic API) vs 自托管开源模型 (LLaMA / Qwen / DeepSeek) vs 端侧模型 (Apple Intelligence / Phi-3) vs 嵌入式 (NPU on phone).
• 关键不变式破坏: 训练数据分布 ✗ 推理分布 (covariate shift) / 测试时思考预算 ≠ 训练分布 / 多模态对齐困难.

→ 第十二部分 AI/ML 与未来可能的 RL/Agent 章节.

五、横向跨层的几个关键事实

5.1 一条"虚拟 → 物理" + 一条"逻辑 → 概率" 主干

10. 语义 / 行为        Agent 语义 / 训练目标
9.  应用 / 业务         组件 + 数据流
8.  运行时             类型 + 函数 + GC
7.  POSIX              fd / file / socket
6.  内核               进程 / 虚拟内存 / inode
5.  ISA                寄存器 + 指令
4.  microarch          ROB / cache / TLB / branch pred
3.  RTL                寄存器 + 组合逻辑
2.  模拟               SRAM / DRAM cell / PLL
1.  物理               MOSFET / 掺杂 / PN 结
─────────────────────────────────────────
对调 → 一条"从概率到行为"主干 (AI 层的来源)

向下"从可计算到物理可造", 向上"从工程到语义可表达". 这个对称是抽象的根本.

5.2 每条层对调, 走 1ms 都要多少层?

你点按钮 (10 Layer)
  → React handler -> 服务后端路由 (9)
    → Python 调 OS write (8→7)
      → kernel epoll (6)
        → NIC 驱动 (5→6 跨)
          → NIC 物理 PHY (4→3→2→1)
            → 光纤传输
              → 远端 反向
                → ...→ DB cache hit
                  → 返回
                    → 经历同样 10 层回你屏幕
 total ~ 50ms 到 10s 视复杂度

→ 这就是"为什么优化 latency 要看哪一层泄漏". 跨 1ms 不是一层优化的事.

5.3 抽象的成本与边界

每条左侧给了便利, 它依赖右侧的实现细节往往在压力下泄漏.

六、抽象怎么"被打破"——5 个真实历史事件

每个都是"下一层物理 / 微架构行为把上层契约撕掉一块"; 一旦撕掉, 修法常常是要在多层同时打补丁.

七、抽象层级的工程用法

7.1 调试定位: "把症状挂到某层"

现象: 服务 P99 抖动
9 (业务): 流量突增 / 队列爆 → 容量问题
8 (运行时): GC pause / go runtime block
7 (POSIX): epoll 漏 wake / TCP ack 慢
6 (内核): 调度延迟 / softirq starvation
5 (ISA): - (上层几乎不报)
4 (microarch): branch mispred / cache miss
3 (RTL): (几乎无)
2 (模拟): (硬件故障)
1 (物理): bit flip

→ 能力定位: 一旦你能把现象对应到大概一层, 你就知道该看哪个工具 (perf / strace / py-spy / vtune / ipfc / sledf).

7.2 系统设计: "新抽象必须问'泄漏怎么办'"

设计 cache / scheduler / scheduler / predictor 时, 先回答:

• "失败时契约怎么退化?"
• "性能泄漏到什么粒度?"
• "并发 / 故障模型下不变式是什么?"
• "依赖下层什么不变式? 下层失败呢?"

→ 见 第十三部分 _meta/brhardware-shapes-software 与 第八部分 / OS 第 2 章.

7.3 学习路径: "沿层上下走"

• 从程序员角度看, 学完高级语言 (8) 应该往上 ((9) 框架与 (10) AI 应用) 与往下 (指 7 POSIX 与 6 内核与 5 ISA) 各推一些.
• 从硬件工程师角度看, 学完数字逻辑 (3) 应该往物理 (1-2) 与微型架构 (4) 与 ISA (5) 与内核 (6) 推.
• 从 AI 工程师角度看, 应该至少熟悉 (10) 与 (9) + (8) + (5) (手算 attention FLOPs 都要 ISA 层系统) + (4) (Tensor Core / SM).

八、与第零部分 + 各部分的接口

• 抽象 ↑层(10-9) 主线依靠第十二部分 AI/ML 与第七部分系统设计.
• 抽象 ↓层(1-4) 主线依靠第八部分组成原理.
• 第 5 ISA 直接对应第八部分 isa-design.
• 第 6 内核对应第二部分 OS.
• 第 7-8 之间——语言运行时 vs 系统调用——与第五部分 compiler + _meta runtime-semantics 直接相关.
• 第 4 层泄漏洞的 crypto/sidechannel 讲 Spectre/Meltdown 的密码学攻击面.
• 数学 (第零部分) 跨层使用: 第零部分线代对应 (4) 微架构张量核心; 概率对应 (10) AI 模型; 微积分/优化对应 (10).

九、结束 + 速查表

下一篇: 3. 形态演进: 大型机 → PC → 单片机/ARM → 云 → Web → AI → XPU.

3. 形态演进: 大型机 → PC → 单片机/ARM → 云 → Web → AI → XPU

TL;DR

计算机 90 年史, 物理形态大致经过 7 段 演化. 每一段新形态不是上一段的"放大版/缩小版", 而是新的契约 + 新的使用人群 + 新的工程师心智模型:

1. 大型机 (mainframe): 5 大单位共用 1 台机器, 分时.
2. 小型机 (minicomputer): 实验室级, 关键用户开放.
3. 个人计算机 (PC): 桌面 1 人 1 机.
4. 单片机 (MCU) / 嵌入式: 物联网之家家电、汽车、卡片电脑.
5. ARM / 移动: 口袋超算, RISC 一夜成反主流. 同时云计算也起飞.
6. Web / 云原生: 用户运行不再占设备, "数据在云上, 浏览器即终端".
7. AI / XPU: 数据中心向张量机倾斜, 在 N 年内 GPU / NPU + CPU 共生, 异构成为主流.

每段不仅硬件变, 软件 / 用户 / 商业模式也变. 我们把"形态学"这一节当作"硬件 + 软件 + 人的契约" 三联一起讲.

读完应能: 给一台新设备 (e.g. Groq LPU / Apple Vision / 某家国产 7nm 服务器芯片) 立刻判断它在哪一段 / 在异构谱系哪一端 / 它依赖上一段哪些遗产.

一、形态演进总图

1960.DataBindings
┌──────────────────────────────────────────────────────────────────┐
│ 1. Mainframe (IBM 360 / 370 / z)            单台 / 分时共享    │
│ 2. Mini (PDP-11 / VAX)                        实验室级          │
│ 3. PC (x86 / PC-clone)                     1 人 1 机, 平民化   │
│ 4. MCU / 嵌入式 (Arduino / Pi / 单片机)    几人franc块           │
│ 5. Mobile (ARM 手机 / 平板)                  口袋超算           │
│ 6. Cloud / Web (AWS / Azure / GCP)         1 服务 / N 用户      │
│ 7. AI / XPU (H100 / NPU / TPU / 量子预研)   分工化算力          │
└──────────────────────────────────────────────────────────────────┘

每一阶段, 单台算力 + 人数 + 软件范式 这三条线互相带火. 表三条线随时间:

二、阶段 1: 大型机 (1965-)

2.1 物理形态

• 一台 IBM S/360 = 几个机柜, 水冷, 卷磁带库, 集中管理. 当年 "data processing department".
• 操作系统 OS/360 (later MVS / VM / z/OS); 任务, JCL (Job Control Language).
• 编程范式: COBOL (商业), FORTRAN (科学), PL/I (混合), 后来 RPG, 汇编.

2.2 契约 / 不变式

• 批处理 + 分时 (TSO):
  • 批: 提脚本 → 等结果. 用 JCL 描述作业调度.
  • 分时: 写终端 (3270) 上 ISPF.
• 可靠为先: 7x24 不停. RAS (Reliability/Availability/Serviceability) 重于性能.

2.3 至今大型机仍在使用

• IBM z15 / z16 用 5nm 工艺, 跑 z/OS, 在银行 / 航空 / 政府仍主力. 其工作负载大多是 COBOL 老 transaction 处理系统; 据估计全球 200K+ COBOL 程序员仍在岗.

三、阶段 2: 小型机 (1965-1985)

3.1 PDP/VAX

• DEC PDP-8 (1965): 第一台 < $20K 的小型机 → 大学实验室都能买.
• PDP-11 (1970): 决定性影响, 给 Ken Thompson & Dennis Ritchie 写 Unix 用. C 语言在此诞生.
• VAX-11/780 (1977): 32 位, 单机虚拟内存, 标准 1 MIPS 性能基准.

3.2 关键遗产

• Unix 与 C 都在 PDP 上诞生 → 第一份与硬件解耦的 OS + 语言 (1973 C 重写 Unix kernel). → 后续 Linux / BSD / Solaris 全都站着.
• 分时系统 Unix 让程序员直接交互式开发, 不再写卡片等一天.

3.3 1980 后逐渐让位 PC

• minicomputer 因 PC 在性能上赶上 (80486 一代) 而 vax 都被 Sun / SGI 工作站替代 → 进一步 PC / Linux 替代.

四、阶段 3: 个人计算机 (1981-)

4.1 形态定义

• 单台桌上机, 价格 $1000-5000, 1 人 1 机.
• IBM PC 开放架构 (1981): IBM 只把 BIOS 留 copyright, 其它都让外面 chip 厂做; Compaq 等做 clean-room BIOS → PC clone 洪流 → x86 + DOS 标准.
• Wintel 联盟 (Windows + Intel): 1990s 主导.

4.2 操作系统迭代

• MS-DOS 1.0 (1981) → 6.22 (1994).
• Windows 1.0 (1985) → 3.x (1990-1993) → 95 / 98 (1995-1998) → NT / 2000 / XP / 7 / 10 / 11.
• 终于 Windows + Office 成为商业上标准应用.

4.3 关键软件革命

• VisiCalc (1979 Apple II) 第一代 killer app; Lotus 1-2-3 → Excel 接力.
• Internet 同期借助浏览器从科研拉到家里 (Mosaic → Navigator → IE → Firefox → Chrome).

4.4 形态不变但内部 XPU 化

• 至 2024-2026, 校园 / 办公 PC 大多内含 NPU (Apple Neural Engine / 骁龙 Hexagon / Intel / AMD NPU); 传统桌面任务在 CPU, 视频处理在 GPU / NPU 媒体引擎, AI 推理在 NPU. 用户的"键盘手"完全感受不到分工, 但芯片任务被分配得像 Viking 时代分工一样精细.

五、阶段 4: 单片机与嵌入式 (1976-)

5.1 8-bit 单片机史

• Intel 8048 (1976)、8051 (1980) — 集成 CPU + RAM + ROM + IO 在一片, 既家电控制也打印机控制.
• Microchip PIC, Atmel AVR — 90 年代起家电 / 工业占比大.
• 32-bit ARM Cortex-M (2004+) — 给嵌入式加上 MMU-less 32 位 → MCU 进入位数升级时代; 现代智能家居系列用 STM32 / nRF52 / ESP32.

5.2 关键契约与约束

• 8/16-bit 单片机典型几十 MHz, 几 KB SRAM, 几十 KB Flash; 低功耗 (< mA @ 3.3V) 比性能重要.
• 程序循环 + 中断驱动, 裸跑或 RTOS (FreeRTOS / Zephyr).
• 适配硬件 IO 与外设协议 (I2C / SPI / UART / CAN), 这是 [操作系统 + 编译原理] 的下边界实践.

5.3 树莓派 / 嵌入式 Linux 与新形态

• Raspberry Pi (2012 起) = ARM 单片机 + Linux; 普通人可以 35 美元跑完整 OS + python.
• BeagleBone Black / Jetson Nano / Coral Dev Board — 边缘 AI 推理板, AI 工业应用入门.

5.4 物联网 (IoT) 与 MICRO-CLOUD 端

• IoT 设备峰值数十亿台 ↔ 几十亿 IP; 6LoWPAN / MQTT / CoAP / OPC UA 等协议.
• 数据汇总到边缘网关 → 上云 / 流式 → ML 推理再下沉到端 (端 NPU) 的"edge ML" 链路成主流.

六、阶段 5: ARM + 移动 (2007-)

6.1 ARM 历史

• Acorn Archimedes + ARM1 (1985): Acorn Computers 设计的低功耗 32-bit RISC CPU.
• ARM (公司) 1990 独立, 商业模式 = ISA 授权 + 核授权: 谁都拿 ARM 设计 → Apple A 系列 / Snapdragon /Samsung Exynos / 联发科 Dimensity / 华为麒麟 / Google Tensor; 都按 ARM 几亿片付版税.
• ARM 在 2007 iPhone 起进入手机主流, 2010 iPad, 2020 Apple M1 桌面 / 笔记本, 2018 AWS Graviton 进数据中心, 2023 通 Microsoft Windows on ARM, 2024+ 自研车规级芯片 (Tesla / 高通 8295 / 联发科).

6.2 RISC 与 CISC 的胜负史

1980 x86 CISC 起 ← IBM PC 路线
1985 ARM1 RISC
1990 RISC 工作站死 (Sun/SGI 让位 PC)
2000 x86 由摩尔推往更快
2005 单核停 → x86 强向多核, 但功耗不行入手机
2007 iPhone ARM
2010 ARM Cortex-A 系打平 x86 性能/瓦
2020 Apple M1 在桌面都胜 x86
2024+ ARM 的 Neoverse V/N 与自研 (Graviton / XuanTie / 阿里 倚天)成型成为数据中心升

关键: RISC 并未在 1990 年工作站时代赢; 它是在 mobile / 功耗 / 集成 SoC 这一新形态上 2007+ 赢, 再逆向卷回桌面与数据中心.

6.3 形态新约: App + 触屏 + 推送

• 用户在触摸屏上手势/语音交互; 通知 / 推送代替弹窗; 后台 / 前台切换由 OS 自动; 电池结构作为合约 (energy budget per app).
• 操作系统 iOS / Android 主流, 沙箱 + 审核制 + 应用商店分发 与 PC 时代相比完全变了软件商业模式.
• API 重心从 Linux 系统调用移到 Apple SDK / Android SDK; JNI/Swift/Flutter/React Native 跨平台层多样.

6.4 ARM 在 2024-2026 的姿态

• ARMv9 + SVE2 与 CXL / 一致性 / page table 多机架化扩展 (CCIX → CXL 4.0) 进一步强化数据中心能力.
• Apple M5 / 骁龙 X2 Elite / Nvidia Grace — 桌面 / PC / 服务器 ARM 都路线成熟; x86 走异构 + chiplet + AI 加速的 binary compatibility.
• 中国: 阿里平头哥 倚天 / 华为 昇腾 CPU + 鲲鹏 / 飞腾 / 龙芯 / 海光 — 在政企 / 信创 / 金融大批量部署.

七、阶段 6: Web 与云计算 (1995-)

7.1 Web 1.0 → 2.0 → 3.x

• Web 1.0 (1991-2004): 静态 HTML + 链接 + 邮件; 浏览器看网页.
• Web 2.0 (2004-): AJAX + UGC (User Generated Content); Wikipedia / YouTube / Facebook / Twitter 起势; JavaScript + CSS + DOM 成熟框架 (jQuery → React → Vue / Angular).
• Web 3.0 (2014-): Blockchain + decentralized identity + 媒介原资产, 部分 industrial deployment 但仍是 experimental.
• Web 与 LLM 时代 (2023-): 浏览器内嵌 LLM (Edge Copilot / Brave Leo), Browser-LLM 协议 (MCP, etc).

7.2 云原生态

• AWS EC2 (2006) 起, 一切 on-demand; S3 对象存储; RDS 一键数据库. 资本支出从机房 → "API 一个 form".
• 容器化 (Docker 2013), Kubernetes (2014-2018), service mesh, GitOps, IaC (Terraform / Pulumi / Crossplane).
• "无服务器 (serverless)": Lambda / FaaS / EventBridge — 上层抽象更上一层, 工程师不接触实例.
• 2024+ 通 WebGPU / WebGPU compute API / WebAssembly 系统接口 (WASI) 让浏览器执行本地任务 (含 LLM 推理).

7.3 数据中心 "机房是社会"

云数据中心 (Google / AWS / Azure / 阿里 / meta / 字节 / 腾讯) 一般 10-100MW+, 需 50-100MW 风电 / 水电 / 核电配套. 在 2023+ AI 训练需求暴增, 单数据中心能力推到 1GW+ 接边; 核电 / SMR (small modular reactor) 直接进 Microsoft / Amazon 长约; 数据中心从"工程师资产"变"国家级能源政策", 是不可忽略的形态变化.

八、阶段 7: AI / XPU 异构时代 (2012-)

8.1 XPU 谱系

8.2 为什么 XPU 必然

• Dennard scaling 2005 止 → 单核不再提速 → 必须 SIMD / 多核 / 加速器.
• AI 训练 = 矩阵 × 矩阵 (GEMM) 大规模并发, CPU SIMD 的乱序调度远不如 GPU 的 SIMT.
• 推理 latency / 功耗关键, NPU 在 50-200 GOPS/W 比通用 CPU 5-10x 能效.
• 摩尔放缓 → 工程师换 vertical specialization: 每类算力做专门芯片 → 形成多 die + 互联 (NVLink 5/6 / CXL 3.x / UALink / Infinity Fabric).

8.3 互联 (interconnect) 与 memory hierarchy 重塑

• 关键事实: 2024-2026 大模型训练, 算力不卡 GPU 而卡 GPU 间带宽 + HBM 容量.
• HBM4 + CXL 3.x + NVLink 5/6 / Infinity Fabric 让"memory pool" 成为单数据中心级资源.
• 背景: 见 第八部分 / interconnects 与 memory-hierarchy.

8.4 XPU 上的"用户" 是谁

统一框架: MLIR / OpenXLA / TorchTitan / SDAA — 让你写一份 PyTorch 在哪一 XPU 上都跑, 内部 dispatcher 把算子路由到对应芯片.

九、形态演进对工程师的影响

9.1 工程师"脑模型" 演化

• 1960 大型机时代: 排队作业 / 数据表 / 作业流 / COBOL 主导.
• 1980 PC 时代: 单人作业 / 文件 / GUI 桌面 / C / VB.
• 2000 Web 时代: client-server / DB / HTTP / PHP / Java Servlet / Spring.
• 2010 移动时代: app / 推送 / 通知 / 离线 cache / Swift / Kotlin / Flutter.
• 2020 云时代: container / K8s / IaC / GitOps / observability / micro-service.
• 2025 AI/Agent 时代: prompt + tool use + MCP + sub-agent orchestrator + model registry.

9.2 形态与抽象层级的双重图

把 abstraction-layers 的 10 层叠加在这 7 段形态上, 每段形态都激活某些层:

形态              主要激活的抽象层级
─────────────────────────────────
Mainframe          1-7 (低层缺独立硬件锤)
Mini               3-7 (Unix 起来)
PC                 1-8 (高级语言运行时大众化)
MCU                1-5 (baremetal 与 ISA 露骨)
Mobile             1-9 (系统 → App → 触屏)
Cloud / Web        1-9 (容器 + 微服务 + 网络套接)
AI / XPU           1-10 (新增 LLM 层; 每层都革新)

→ 这就是为什么 AI 时代让人"压力大": 同时在 10 层里推 — 数学层 (第零部分) / 硬件层 (第八部分) / OS (第二部分) / 编译 (第五部分) / AI (第十二部分) 全被推.

9.3 工程师必备的"形态切换" 能力

1. 给我一段 CUDA kernel, 能定位它在第 3 (RTL) / 4 (microarch SM) / 5 (ISA) / 9 (PyTorch→ cuBLAS path).
2. 给我一段 Go 服务, 能告诉我它的 latency 受第 6 (kernel fork) / 第 7 (epoll) / 第 4 (cache miss) 哪层主导.
3. 给我一段 Transformer 训练脚本, 能告诉我它在 XPU 谱: CPU 做控制, GPU 做 GEMM, DPU/NIC 做梯度同步, HBM 做激活 cache.

十、未来 (2026+) 应看的形态信号

• NPU 进 PC / 移动成主流: Apple Intelligence / Windows Copilot+ / Android AI 主推.
• CXL pool 化内存: 数据中心级 "memory pool" 走出研究阶段, 进入商用 workload.
• 量子-经典混合协处理 (QPU-as-accelerator for crypto / material / optimization): 部分 HPC workload 上线.
• Chiplet + die-stacking: AMD 3D V-Cache / Intel Foveros / 台积电 CoWoS / chiplet 互联取代单大 die.
• 6G 与低轨卫星直连: 卫星互联网补齐地球 IP (Starlink 等).
• AI 编程范式入工程主体: Agent / MCP / multi-tool loop 成为默认开发栈, IDE 与 git 都换头脑.

十一、与后续各部分的接口

十二、结束 + 速查表

下一篇: 4. 主干纵贯: CPU/内存 → OS/Linux → 网络/Web → DB → 编译 → 分布式 → AI 的承接链.

4. 主干纵贯: CPU/内存 → OS/Linux → 网络/Web → DB → 编译 → 分布式 → AI 的承接链

TL;DR

前面 history 讲时间线、abstraction-layers 讲层级、mainframe-xpu 讲形态. 这一节反过来 — 沿"承接链"反向回到纵贯主线: 每条技术都因"上层拿它做啥"才有意义, 每条新技术大概率是对上层需求的回响.

承接链 (dependency-of-statements):

物理 → 晶体管 → 数字 → ISA → 微架构 → 内存 → OS → 进程 / 虚存
                                            ↓
          → 文件系统 → 网络 → Web → 数据库 → 应用 → 业务
                  ↘
                   → 编译器 → 高级语言 → 框架
                                              ↘
                                               → 分布式 → 共识 → 一致性 → 云
                                                                   ↓
                                                                   → AI 训练 → 推理

每一节都讲: 它的上一站契约是什么 / 它对下一站提供什么 / 没有它上一步走不动.

读完应能: 把任意一份你做过 / 你读过的工程问题挂到这条承接链某节点上, 知道"上一站是怎么影响它"和"它对下一站指挥谁".

一、CPU 与内存: 1945 年那纸契约的开始

1.1 von Neumann 架构

     CPU  ←─── shared bus ───  Memory
                                   │
                                 IO

存储程序 + 共享总线 + 取指 → 解码 → 执行 → 写回. 这套循环在一台机器上仍是 2026 主流 (除 Harvard / NUMA / DSP variant).

1.2 第一道承接: 性能 vs 内存之间的-frequency gap

1980  CPU 5MHz, DRAM 100ns     到 CPU 一致
1995  CPU 100MHz, DRAM 60ns   缓慢拉开
2000  CPU 1GHz, DRAM 6ns       10x 差距
2010  CPU 3GHz, DRAM 0.3ns    100x 差距 ← cache 不可缺
2026  CPU 5GHz, HBM 0.2ns     memory wall; cache + HBM + CXL

→ 这就是为什么 第八部分 memory-hierarchy / TLB / DRAM / HBM 全是必需. 内存是 CPU 的最薄弱点, 没有第二选项, 没有它后整个 OS / 编译 / AI 承接链都得重.

1.3 为何 OS 出现: 单机内部多任务化的契约

• 主机仍单 CPU 时, OS 把"硬件时序"封成"时序进程"; 进程 / 线程 / 上下文切换 = 虚拟时间 + 虚空间.
• 一旦有保护模式 + 虚拟内存 + 系统态分, 用户程序不必对每个硬件细节了如指掌 — 这是 OS 出现的核心动因.

二、OS/Linux: 让程序员不再写硬件

2.1 进程 + 虚拟内存 = 抽象母机

• 进程 = 一份拥有独立虚地址空间的执行单位; 内核为每个建 page table, 给"独立空间"幻觉.
• 调度器 (Linux CFS / EDF / RT) 将 CPU 时间切片让多进程并发"幻觉".
• 上下文切换挂上下文 + TLB; 延迟 ~ 1-10us (见 os/sched).

2.2 文件系统: 让 IO 字节流化

→ 见 os/fs.

2.3 网络栈与 epoll/io_uring

• socket() 复用 fd 抽象; TCP 4 层 + IP + 驱动.
• C10K 问题 (2002): 单机 10000 连接压力 → epoll (2002) + kqueue; 后 100K / 1M 由 io_uring (2019) 实现.

2.4 同步原语与内存模型

• 进程内 sync: mutex / semaphore / rwlock; kernel 内 futex + CAS; 浪费大批 lock-free / RCU 设计.

→ 见 os/lock.

2.5 OS 对承接链"承诺"的清单一句话

• 进程隔离的虚空间
• 通用 IO 的字节流
• 跨进程的协议: socket / IPC / pipe
• 命名隔离: filesystem
• 安全 / 权限: uid / cgroup / capability

这一组契约就是后续一切软件的"地基".

三、网络与 Web: 让孤立的机器互连

3.1 IP/TCP 契约

• IP: 不可靠的、按 packet; 上层自己保序 / 重传可靠性.
• TCP: reliable byte stream; congestion control (Reno/Cubic/BBR); 3-way handshake + 4-way close.

3.2 HTTP / TLS: 最薄一英里

• HTTP/0.9-1.1 一条 TCP 一个 request; HTTP/2 (2015) 一条连接多路 stream; HTTP/3 over QUIC (2022+) → 见 networking/quic.
• TLS 1.3 (2018) 1-RTT + 0-RTT; X.509 + PKI + CT.

3.3 Web 把客户端拉成终端

• 浏览器是 OS 上的一个 "虚拟机"; HTML/CSS/JS DOM/WASM/WebGPU 成熟.
• 2024+ WebGPU 让浏览器可调 GPU 算 + WASI 让 WASM 调本地 file. 浏览器从文档看待器 → 通用客户端 → 实际计算平台.

3.4 网络对 DB / 应用的影响

• DB 出现 single machine 邦联后就受网络影响; 网络 RTT 决定 commit 时间 → 数据库 replication 的延迟很关键.
• 应用从 monolith → SOA → micro-service → service mesh 全由于网络可靠性 / IP/TLS / k8s / 等成熟.

四、数据库系统: 让状态在并发 / 故障下成立

4.1 为什么需要 DB 而不是文件

OS 文件系统只承诺 "字节流", 没说"原子写 / 多 client 并发 / crash 后一致". DB 把这些不变式钉死:

• ACID (事务原子性 / 一致性 / 隔离性 / 持久性).
• MVCC + WAL + 2PL + snapshot isolation.
• 主流: PostgreSQL / MySQL (OLTP), ClickHouse / Snowflake (OLAP), Redis / Dynamo (KV).

→ 见 databases. 这是承接链 保存状态 的核心一层.

4.2 数据库如何依赖 OS / 网络 / 硬件

• 依赖文件 + fsync 确保持久性 (write-ahead log); 这是个 OS 与块设备之间的契约. 一旦块设备"写入但未 flush" 破坏这一契约, ACID 就有空洞 (e.g. SSD cache 丢).
• 依赖网络做 replication; latency → Paxos / Raft 单写 1 RTT trip.
• 依赖 page cache / direct IO / io_uring / NVMe 多队列 → 与 OS / 块设备协同.

4.3 DB 是 web 后端的"状态核心"

• Web 上层把所有"状态"丢 DB, 自己做无状态服务 + 容器; K8s + RDS 模型 一切都这么搭.
• DB 与分布式系统的 cap 线 / 一致性范畴都来自这条承接.

五、编译器 / 高级语言: 让机器可读变成人可写

5.1 编译器史的简线

• 1957 FORTRAN; 1972 C; 1990 GCC; 2000 LLVM; 2010 V8 Tiered JIT; 2020 Rust + LLVM + Miri.
• 编译器把"人工可写"高级语言转到"机器可执行" ISA, 同时做优化: SSA / CFG / constant folding / dead-code / loop unroll / auto-vectorize / IPO.
• 见 compilers.

5.2 编译器承接了"OS 加上后程序可点点"

• OS 提供 syscall ABI; 编译器知道怎么写出对 ABI 正确的代码 (caller/callee saved regs, stack frame).
• 语言层 → 库 → syscall → kernel → driver.

5.3 高级语言运行时: 抽象 GC 与线程的延展

• Java / Python / Go / Rust / JS 等, 加 GC / 协程 / async / await / Future / channel; 都把 OS 线程 + sqlite / pipe 的细节包到运行时.

六、分布式系统: 一台机器不够用后 N 台协同

6.1 必来

• 单机扩展到 +10GHz 时 CPU 与内存墙都搅过; 一台机器能跑的 QPS / 数据量 / HA 都不可满足 → 必须多机.
• 多机 = 网络 → 延迟 + 故障 + 异构 → 必须协议 (CAP / 一致性).
• Multi-Paxos / Raft / Gossip + CRDT; 见 distributed.

6.2 共识 = 状态机复制的工具

• 1990 Lamport Paxos; 2014 Raft.
• 任何"被许多机器共享的状态"几乎都用这俩或其变种. -共识是承接链中调度多机, 把"不可靠网络 + 部分机器丢"转成"一组虚拟主机机".

6.3 一致性与时间

• 物理时钟不可同步全 → logical clock (Lamport, vector clock, HLC) → 全序 / 偏序隔离.
• TrueTime (Spanner) / HLC (CockroachDB) 借 GPS + 原子钟做单亿误差.

6.4 把"集群"抽象成"单机"

• K8s 把 10000 台集群抽象成一组 control-plane API; 用户提 YAML 即一份声明式资源 → 内部 reconciliation loop → 自动调拨.
• 见 system-design/case/k8s-control-plane.

七、Web 后端 / 微服务 / 系统设计

7.1 估算 → 缓存 → 队列 → 限流

• Little's Law + Little's Law → 平均 response = arrival_time / (1 - rho); back-of-envelope 计算 QPS / IOPS / 带宽 / 存储.
• cache-aside / write-through / write-behind; 失效 (穿透 / 击穿 / 雪崩).
• 队列 Kafka / Pulsar / SQS; at-least-once vs exactly-once; outbox pattern.

7.2 系统设计 = 反推与分解

• 任务需求 → 估算 → 主组件 → 数据流 → 失败模式 → 可观测 → 上云.
• 见 system-design.

7.3 微服务网格的承接

• 服务网格 (Istio / Linkerd / Envoy) 在 K8s 之上加: mTLS + routing + 重试 / timeout / 熔断 + observability + sidecar proxy.

八、AI: 状态机的"高维"模式化

8.1 它从哪里踏上承接链

• 数学 (第零部分): 反向传播 + 链式法则 + softmax / SVD + 概率分布 → 是 AI 训练算法本身.
• 硬件 (第八部分): GPU/TPU/NPU 异构芯片 + HBM + 互联 → 性能 + 显存决定 能不能训.
• OS (第二部分): Linux + cgroup + nccl + RDMA → GPU 集群的互联.
• 网络 (第三部分): RoCE v2 / nvBandwidth → 多卡通信快; HTTPS 推理 API.
• 数据库 (第四部分): 训练数据集存储; vector database 给 LLM 工具调用 / RAG.
• 分布式 (第六部分): model 并行 / data 并行 / pipeline 并行 / ZeRO-3 → 8 卡变 65K 卡.
• 系统设计 (第七部分): inference service 设计 / KV cache 共享 / 多 tenant / autoscaling.

8.2 AI 反过来反推这条承接链

• GPU/NPU 出来前: CPU 单线喂不饱; 现在 GPU 训练一批 7B 模型 1000 卡密集用; NCCL + RDMA + GPUDirect-RDMA 是新协议栈; 这把承接链的工具形态全部改.
• LLM 推理: 把反向 AD 的 cache 改成 KV cache, 不是梯度是 attention 中间结果 → 这反过来推 HBM / CXL / 互联带宽.
• Agent (2025+) 反推 RPC / tool/API 框架: MCP 协议让 LLM 配 SQL / fs / browser 成为可工程交互.

8.3 新承接: AI → 系统 / OS 的反向输入

• GPU 集群调度: Borg/Omega/Kubernetes 都要支持 device plugin + topology-aware; Linux 内核对 GPU 的 cgroup 隔离还很弱 (2024+ 才有 NVIDIA MIG 与 DPDK 隔离成熟).
• ML 监控与 trace: OpenTelemetry 增强 ML metrics; 单步训练几百次需 trace-blame 与 schema.
• 推理直接接 OS syscall (e.g. AI tool use) → 安全沙箱新关注.

九、整个承接链图

物理 ─ 晶体管 ─ 数字 ─ ISA ─ microarch
                                  ↓
                            虚拟内存 + CPU cache
                                  ↓
            ┌───────── OS (Linux Kernel) ─────┐
            ↓             ↓                 ↓
        File System    网络 (TCP/IP)      进程 + 调度
            ↓             ↓                 ↓
        块设备 / SSD   HTTP / TLS          线程/协程
            ↓             ↓                 ↓
            DB          Web/REST        编译器 / 语言运行时
            ↓             ↓                 ↓
            OLAP / OLTP    LAMP/MEAN/MERN   JIT/HotSpot/V8
            ↓             ↓                 ↓
            分布式: KV / Queue / Consensus / K8s
            ↓             ↓                 ↓
───────────────────────────────────────────
                            ↓
                    AI: Training + Inference
                            ↓
                  GPU / NPU / TPU / 异构 XPU
                            ↓
                  HBM4 + NVLink + CXL 3.x
                            ↓
                  Agent + MCP + 推理 SDK
                            ↓
                  === 下一波新抽象 ===

每一节点都为前一节点顺承不变式; 跳一节点工程就断了.

十、五个"如果是新工程师, 你正在哪段承接"的练习

→ 这套表帮你定位"读完哪几章本书就可以接入你工作".

十一、与第零部分数学的加乘

数学 (第零部分) 不在承接链有自己的节点 — 它横跨所有节点:

• 第 1-2 物理层 - 信息论/熵与极限.
• ISA 与微架构 - 不必数学.
• OS / 调度 - 概率 + 排队 + 极限.
• 网络 - 概率分布 + 信息论熵 / 信道容量.
• DB - 关系代数 + 估计 + 一致性序.
• 分布式 - 偏序 + 概率 + 信息论.
• AI - 微积分 + 线代 + 概率 + 优化.

→ 这就是为什么数学放在第零部分: 每段承接都要用到, 不能单挑一节点上.

十二、结束 + 速查表

下一篇: 5. 全书地图: 13 部分与导论的交叉索引.

5. 全书地图: 14 部分与导论的交叉索引

TL;DR

导论卷最后一篇, 把书中 14 个部分 (导论卷 + 第零部分数学 + 13 主题) 全部丢到一套二维矩阵上, 让读者一眼定位"我读这章它在讲什么 / 在哪一站 / 在历史和抽象层级哪一格", 同时给出四类读者画像的纵贯走法、按"查新资料归属"的 SOP、以及每章入口建议.

读完应能:

1. 不再在"现在我读哪章"上犹豫 — 用三张矩阵给任意新资料归位.
2. 凭四个典型读者画像 (后端工程师 / 移动 App 工程师 / ML 工程师 / 硬件 / 嵌入式工程师) 各自挑通缩短到对应章节.
3. 看到"我现在缺什么"立刻找书必看哪章.

一、合成的四视图

导论把全书骨架按 4 个相互正交的视图 抽出, 每视图各答一个问题:

本页 (map) 再把上面 4 视图按"14 部分 × 4 视图"二维矩阵化, 让你能在矩阵里点一个格, 知道这格的全部上下文.

二、14 部分 × 抽象层级 矩阵

符号说明:

• ● 该部分主线章节在这层
• ◯ 强相关 (但非主线)
• ○ 触及但不深入
• ★ 跨层桥接专项 (e.g. 信息论的 Shannon 容量把第 3 层 RTL 与第 10 层 AI 用同一组数学串起来)
• ⤴ 导论卷贯通所有层
• — 不涉及

怎么用这张表:

• 横看一行: 一个部分主要钻研哪些层. 例: 第 2 OS 横跨 4-7 层 (microarch + ISA + kernel + POSIX); 第 8 组成原理横跨 1-5 (硬件视角); 第 12 AI/ML 纵跨 4-10 (训练靠 GPU + PyTorch 运行时 + 模型本身).
• 纵看一列: 某抽象层被哪些部分讲解. 例: 第 4 层 microarch 主要由第 8 部分讲, 第 10 与第 11 部分做硬件级桥接 (Spectre 在第 10 侧信道里用, 第 11 LDPC/Polar Tanner 图里涉及微架构并发结构).
• 空白诊断: 你接到一份任务, 想"我不熟第 X 层", 纵列扫立刻找到对应部分.

三、14 部分 × 形态演进 矩阵

怎么用:

• 一行告诉你这部分笔记主要面向哪种形态设计.
• 例: 第 4 DB 在 Mainframe / Mini 时代主战, Cloud/Web 时代仍是后端核心; 第 12 AI/ML 几乎只在 AI/XPU 段才出现 (其前身可追到 1957 Rosenblatt perceptron, 但没 XPU 算力就上不了规模).
• DSA / 计算理论 / 元抽象与硬件形态弱关联, 它们是"平台无关的抽象研究".

四、14 部分 × 历史年代 矩阵

符号: ◆ 该年代此部分是其最热的研究方向之一.

怎么用:

• 纵看一列告诉你"在那个年代里跟上主流要读哪几章".
• 例 2024-26 列: 主线 8 (XPU+HBM4) + 12 (AI/ML 大模型推理) + 7 (Operator+MCP) + 6 (分布式训练) + 5 (MLIR) 各章合 AI 故事; 11 (信息论深化) + 10 (PQC 抗量子) + 13 (元抽象) 给补底.
• 横看一行告诉你"这部分在哪几段是 hot, 哪几段是支撑".

五、四类典型读者画像的纵贯走法

不同背景的人读完导论, 推荐的"主线缩短" 路径不同. 这里给 4 个画像 + 各自 4 视图的"主题必看" 与 "纵贯加速":

5.1 画像 A: Web 后端工程师

• 你已熟: HTTP / SQL / Docker / K8s / 微服务
• 你要补:
  • 横切主线: 第 3 网络 (networking/README.md) — 隧道深入 TCP/QUIC; 第 4 DB (databases/README.md); 第 6 分布式 (distributed/README.md); 第 7 系统设计 (system-design/README.md)
  • AI 主轴: 第 0 数学 → 线代 → 概率 → 第 12 AI/ML (ai-ml/README.md) (训练 + 推理服务)
  • 纵贯加速: 第 2 OS (os/README.md) — linux 内核 epoll / io_uring 会让你 RPC / DB 性能提升
  • 形态演进: 第 8 组成原理里的 interconnects / memory-hierarchy — 知道 AWS Nitro / 阿里 CIPU 与 NVMe-of 在数据中心怎么排布
• 预估时间: 上述 4 部主学科加 2 部辅助 ≈ 30-40 小时

5.2 画像 B: 移动 / App 工程师

• 你已熟: Swift / Kotlin / Flutter / iOS / Android, app 架构
• 你要补:
  • 横切主线: 第 8 组成原理 (computer-arch/README.md) — ARM v9 / NPU; 第 12 AI/ML (ai-ml/README.md) — 端侧推理 / Apple Intelligence / NPU 模型
  • AI 主轴: 第 0 数学概率 + 微积分 (训练后小程序); 第 12 foundations/transformer (端侧推理)
  • 纵贯加速: 第 2 OS (os/net/README.md) — 移动 OS 实际是 Linux + libc / Apple Darwin; 第 5 编译 (compilers/codegen/jit.md) — V8 / HotSpot / Swift runtime
  • 形态演进: 第 5 节 mainframe-xpu §6 ARM/移动
• 预估时间: 30-50 小时

5.3 画像 C: ML 工程师

• 你已熟: PyTorch / Transformer / 模型 fine-tune
• 你要补:
  • 横切主线: 第 0 数学 ( пора → 已具备则 skip); 第 8 组成原理 (GPU SM / NPU / Tensor Core / HBM / 互联); 第 12 AI/ML 全部
  • 纵贯加速: 第 2 OS (NCCL / RDMA / GPU 隔离); 第 6 分布式 (ZeRO / Megatron / Pipeline 并行); 第 7 系统设计 (推理服务 + KV cache + 限流)
  • 承接链: 看 standing-on-shoulders §AI 主轴 — AI 训练不靠 Deng 基础承接链跑不动
  • 形态演进: AI/XPU 段全看 (mainframe-xpu.md#八阶段-7-ai--xpu-异构时代-2012-)
• 预估时间: 50-80 小时 (这条最长, 因为 ML 是横切最广的方向)

5.4 画像 D: 硬件 / 嵌入式工程师

• 你已熟: Verilog / RTL / MCU / 时序约束
• 你要补:
  • 横切主线: 第 8 组成原理 (cpu-pipeline / superscalar / memory-hierarchy / gpu / ai-accelerators 全部); 第 2 OS (os/README.md) 看到硬件 / 内核 / 驱动的对接; 第 10 密码学 (crypto/sidechannel.md) Spectre / Meltdown; 第 11 信息论 (info-theory/README.md)
  • AI 主轴: 第 0 数学线代 + 概率 → 第 12 AI/ML (要知道 attention 张量形状如何映射到 Tensor Core / NPU)
  • 纵贯加速: 第 5 编译 (compilers/sema/ssa.md) MLIR / SSA 是硬件描述顶层; 第 9 计算理论 (theory/automata.md) DFA / FSM 与 RTL 状态机对偶
  • 形态演进: 全段都看, 你要纵串了
• 预估时间: 60-80 小时

六、独立主线地图

6.1 横切 (按学科)

每部分一句话定位 + 入口页 + 推荐阅读时长:

总计: ≈ 200-280 小时通读全书完整深度 ≈ 11-15 周 (周 20 小时). 但你不必通读, 各画像只读对应 4-6 部即可入门.

6.2 纵贯线: 不同形态的"一台设备走通 14 部分"

形态演进每个段都给出"在那段你手中, 这套抽象层级怎么落下来":

A. Large-scale 训练集群 (2026 H100/H200/B200/GB200 pod)

物理 (1)       HGx 中心机房供电 200 MW; 水冷闭环; HBM4 stack 工艺
模拟 (2)       SRAM cell 在 SRAM cache bank
RTL  (3)       NVIDIA SM 内部 RTL; NV-HBI 双 die 互连; CXL 3.0 PHY
microarch(4)   SM + Tensor Core + Warp scheduler + 内存 pool; HBM3e/4
ISA   (5)      PTX + SASS; host x86-64 / ARM / GPU kernel
kernel(6)      Linux + NCCL 2.x + MOFED + eBPF + io_uring
POSIX (7)      GPU driver + RDMA verbs + epoll + io_uring_setup
运行时(8)      PyTorch (Python+Triton) + CUDA  + cuDNN + cuBLAS
应用 (9)       Megatron + DeepSpeed + Ray + Wandb 监控
AI   (10)      Transformer 训练 / 扩散 / VAE / 推理优化

涉及的本书部分: 8 + 2 + 5 + 6 + 7 + 12. 这条线就是 standing-on-shoulders §AI 主轴 的硬件对照版.

B. 你口袋的 iPhone / Android 手机 (2026)

物理 (1)       A18 / Snapdragon 8 Elite 3nm 工艺
模拟 (2)       LPDDR5X + PMIC + PMU + OMAP
RTL  (3)       Apple P-core + E-core + GPU + NPU RTL
microarch(4)   OoO + 深流水 + 共享 L2 + imprecise branch pred
ISA   (5)      ARM v9 / SVE2
kernel(6)      Darwin XNU / Linux 6.x + Android
POSIX (7)      bionic libc + Mach-O + libdispatch + ulib
运行时(8)      Swift / Kotlin / JNI + ART JIT + WebKit JIT
应用 (9)       iOS App / Android App; WebGPU in browser
AI   (10)      Apple Intelligence / Google Gemini Nano 端侧推理

涉及的部分: 8 + 2 + 5 + 12 + (3 网络部分, 因 app 都用 HTTPS). 这就是 mainframe-xpu §6 ARM/移动 一个具体例子.

C. 你公司后台的云原生服务 (2026)

物理 (1)      云数据中心; SSD / nvme-of
模拟 (2)      HBM on cache-LLC; DRAM
RTL  (3)      (N/A 该层工程几乎不接触)
microarch(4)  x86 / Graviton / Xeon-D 多核 + AVX-512 / AMX
ISA   (5)     x86-64 / ARM v9
kernel(6)     Linux + cgroup v2 + io_uring + eBPF
POSIX (7)     rsyscall + epoll_wait; gVisor / Firecracker
运行时(8)     Go runtime + Java Hot + V8 + containerd
应用 (9)      K8s + envoy + prometheus + gRPC + DB
AI   (10)     LLm tool use + RAG + 推理服务 + observability

涉及的部分: 2 + 3 + 4 + 6 + 7 + 12. 这是大多数 Web 后端工程师日常的纵贯.

D. 智能家电 / IoT 端节点 (2026)

物理 (1)    55nm MCU / 22nm RF SoC
模拟 (2)    ADC + DAC + LDO + RF front-end
RTL  (3)    Cortex-M33 RTL + BLE 控制器
microarch(4) 2-4 stage pipeline + FPU + TCM + NVIC
ISA   (5)   ARMv8-M / RISC-V RV32
kernel(6)   Zephyr / FreeRTOS / 无 OS
POSIX (7)    (部分实现 POSIX 子集)
运行时(8)   MicroPython / Rust no_std + embassy
应用 (9)    sensor 驱动 + MQTT 客户端; edge ML 推理
AI   (10)   小模型 on TFLite Micro / CMSIS-NN / NPU

涉及的部分: 8 + 2 + 5 (轻) + 12 (轻). 形态见 mainframe-xpu §5 单片机.

6.3 AI 主轴 (2024-2026 这三年最热路径)

0 数学 ─→ 8 组成原理 (GPU/NPU/HBM/互联) ─→ 2 OS (io_uring/RDMA)
                                                     │
                                                     ↓
5 编译(MLIR) ←─ 4 DB (vector DB) ←─ 6 分布式(ZeRO/Pipeline)
                                                     │
                                                     ↓
                          7 系统设计(推理服务) ─→ 12 AI/ML (训练+推理)
                                                     │
                                                     ↓
                                          13 元抽象 (hardware → software)

任意一段 missing 都读不下去. 这条线已经实际超过其他横切主线单条的总人数 (2024+ LLM / GenAI 工程师数 ~500 万 vs 传统 web 后端 ~1500 万, 但 AI 主轴增长更快).

七、看新资料归位的 SOP

下面是用这页矩阵给任意新文档归位的 5 步操作:

Step 1. 看"它讲的是什么主概念" → 在 §2 横切里挑 1-3 个匹配部分
Step 2. 看"它针对哪种设备 / 用户" → 在 §3 形态里挑 1-2 个匹配
Step 3. 看"它大致什么时代出现 / hot" → 在 §4 年代里挑 1 个匹配
Step 4. 看主要部分字:
  - "GPU/NPU/HBM/CXL"  → §8 + §12
  - "kernel / syscall / io_uring / eBPF" → §2
  - "TCP / QUIC / TLS / HTTP" → §3
  - "schema / SQL / WAL / MVCC / LSM" → §4
  - "AST / IR / SSA / register alloc" → §5
  - "Paxos / Raft / quorum / CRDT" → §6
  - "cache / queue / sharding / rate limit" → §7
  - "transistor / IS pipeline / SIMD" → §8
  - "DFA / PDA / P vs NP / Turing" → §9
  - "AES / RSA / ECC / ECDHE / ZKP" → §10
  - "entropy / capacity / LDPC / Polar" → §11
  - "softmax / Transformer / VAE / diffusion / Adam" → §12
  - "amortized vs worst / 为什么 deep net 可训" → §13
Step 5. 在矩阵上行+列打个 ●; 读完这页就画上 ●.

示例: 给你一份"Groq LPU 推理 7B 模型 benchmark 白皮书". 走完 5 步:

1. 主概念 = 推理 ASIC + LLM → §8 + §12
2. 设备 = XPU 数据中心 → §3 形态 AI/XPU
3. 时代 = 2024-26 → §4 年代号
4. 关键字 = "LPU / Tensor Core / 互联带宽" → §8
5. 矩阵定位 = (§8, §12 行 vs AI/XPU 列 vs 2024-26 列).

→ 立刻知道你必须先读第 8 组织原理响应章节 + 第 12 transformer 章节, 才不再卡白皮书里 "macro-op fusion vs VLIW" 类词.

八、阅读模型

读完导论 5 章, 你应该形成如下"心智图":

• 看一份新文档 / 论文 / 白皮书, 你能在 30 秒内:
  1. 把它的主题归类到某些部分 (横切)
  2. 把它的硬件代归类到某段形态 (纵贯)
  3. 把它入口处的定义对应到某个抽象层
  4. 识别它依赖的契约以及可能泄漏源

这就是"计算机基础知识体系"的本质 — 任何进步的动作都是"在一层抽象里看到一个新机制", 而不是凭着名词链条不停换字眼.

九、与导论各章的接口

十、给导论一份结束

• history: 时间轴 1936 → 2026
• abstraction-layers: 抽象层 10 层
• mainframe-xpu: 形态演进 7 段
• standing-on-shoulders: 承接链
• 本页 map: 交叉索引

读完导论 5 章, 你应该能在矩阵的 56 格 (14 部分 × 4 视图) 中为任意一份新材料归位, 再下钻各主题时不再"信息孤岛". 这就是这套笔记"由导论到 13 主题" 的阅读模型.

十一、结束 + 速查表

回主目录:

• 导论 README
• 全书 README

学习笔记 · 心得记录

随读随记：在正文任意位置用鼠标选中文字，就会出现"📝 记笔记"工具条；笔记锚定到选中文本，刷新页面后自动重新高亮。数据默认只存在你的浏览器 localStorage（不注册、无账号、无数据库、别人看不到）；需要沉淀时一键导出为 GitHub Issue，或复制 Markdown 粘贴到 Discussions / 任意笔记软件。

这个工具能做什么

高亮是怎么实现的

笔记保存时记录选中文字在正文 #content 里的字符起止偏移，刷新页面后按偏移重新包裹 <mark>。局限：

• 偏移基于当前页面文本；如果这本书的内容后来被修改（比如某章重写），旧笔记的偏移可能错位或不再高亮，但笔记内容和原文都还在面板里，复制/导出不受影响；
• 跨多个连续段落的选择会按文本节点分段高亮，显示为一段连续的黄色底纹。

数据存在哪

• localStorage：键为 cs-notes:v1:<页面路径>，只在你当前浏览器。换设备、清缓存、开无痕即不可见——它是"草稿区"，不是存档。
• GitHub Issues：导出后存在仓库 Issues 里，可搜索、打标签、转 PR，随仓库一起版本化。
• GitHub Discussions：GitHub 没有"预填新建讨论"的链接，所以这里用"复制 Markdown"代替——粘贴发布即可；若想"一键发 Discussion"，后续可以注册免费 OAuth App 走 GraphQL API（本工具暂不内置）。

把笔记变成正式章节

笔记面板里的内容只是草稿。想让它成为这本书的一部分（被搜索、随 GitHub Actions 部署、保留版本历史）：

1. 把内容整理成 Markdown，追加到对应部分的章节文件，或新建文件；
2. 挂进 SUMMARY.md；
3. commit + push，Actions 自动构建部署到 GitHub Pages。

实现与配置

• 组件：notes.js（无依赖原生 JS，样式内联）。
• 挂载：book.toml → [output.html] → additional-js = ["notes.js"]。
• 目标仓库：notes.js 顶部的 GITHUB_REPO 常量，导出 Issue 时指向该仓库。

心得日志

把"想明白的时刻"沉淀成条目。这里的每条心得都是提交进仓库的正式内容（和 localStorage 草稿不同），会随书一起部署并保留版本历史——适合作为长期回顾的思考档案。

怎么写一条心得

### YYYY-MM-DD · <一句话主题>

- **触发**: 读到 / 遇到什么问题
- **结论**: 想明白的那件事（一句话点破质变）
- **反例 / 坑**: 曾经错在哪、被什么误导
- **链接**: 相关章节 / 页面

条目

2026-08-02 · 示例：从"看历史"到"看契约"

• 触发: 读导论卷 history时，发现 2025-2026 的内容需要按 2026-08 公开资料核对。
• 结论: 每个时代节点的质变不在新硬件 / 新模型本身，而在它改写了哪条"契约"——例如 HBM4 把单 stack 带宽从 ~1.2 TB/s 抬到 ~2 TB/s，改变的是 memory-bound 训练的边界。
• 反例 / 坑: 凭记忆写"单 stack 384 GB/s"和"~100 logical qubit 已抵达"都错了；落笔前先查原厂 release note / 论文。
• 链接: prologue/history.md、发展史 TL;DR 对应 2025-2026 小节。

后续条目直接往"## 条目"下追加即可。格式不限，能让自己三个月后回看时重新想起来就够了。

第零部分 · 工程数学与离散数学基础

一句话

这份笔记剩下十二部分——从 DSA 的复杂度、OS 的排队论、DB 的概率代价模型、Compiler 的图论支配点, 到 Crypto 的数论/有限域、信息论的 Shannon 熵、未来 Transformer 章节的张量微积分与反向传播——反复在用同一组数学: 离散结构 + 线性代数 + 概率统计 + 微积分/优化. 把这四件工具抽到一处讲透, 后面每章节用到时只管引用, 数学再也不是瓶颈. 本部分不做教材复读机, 只覆盖读后面 CS 主线 + 读 Transformer / 信息论 / 密码学原论文必需的下限, 每个概念都标明喂给哪一章.

思想链

[你在 DSA 章里看到 "Master Theorem: T(n) = a T(n/b) + f(n)"]
  └─> 这是递推 + 指对数变换 → 离散数学篇的 "递推与生成函数" 讲透
        └─> [在 Compiler 章看到 "支配树 (dominator tree) 是 DAG"]
              └─> 图论 + 偏序集 → 离散数学篇的 "图与关系" 讲透
                    └─> [在 DB 章看到 "选择度cardinality estimation 用 sampling"]
                          └─> 概率分布 + 估计理论 → 概率篇讲透
                                └─> [在 Crypto 章看到 "椭圆曲线群上的离散对数难"]
                                      └─> 群/环/域 + 模运算 → 离散代数 → 离散篇讲透
                                            └─> [在信息论章看到 "I(X;Y) = H(X) − H(X|Y)"]
                                                  └─> 期望 + 凸函数 → 概率篇讲透
                                                        └─> [你将来读 Transformer 原文]
                                                              └─> softmax · 雅可比 · 链式法则 · KL 散度
                                                                    └─> 张量 · SVD · Hessian · 凸优化
                                                                          └─> 全部在本部分四篇里
                                                                                └─> 读完此部分, 后续数学不是瓶颈

你将带走什么

读完应能:

1. 看到任意递推式 (Master / Akra-Bazzi) 立刻报出复杂度; 看见 $\sum$/$\prod$/$\binom{n}{k}$ 不再卡.
2. 把"集合 / 关系 / 函数 / 等价类 / 偏序 / 闭包" 当作同一组离散对象操作; 一条 SQL join、一个 git rebase 的偏序图、一个 type hierarchy 在你眼里是同构的.
3. 看到任意矩阵 $A \in \mathbb{R}^{m \times n}$ 能立刻说: 它的秩 / 列空间 / 零空间 / SVD / 谱范数是什么; 看见 "$A$ 是正定" 就知道所有几何与优化推论.
4. 给一个概率模型能直接写: 似然 $\mathcal{L}(\theta)$、MLE 闭式解、MAP 的先验怎么选、KL 散度方向. 大数定律、中心极限定理不背书能推.
5. 拿一个 loss 函数能徒手做反向传播: 链式法则 → 雅可比 → 梯度. 看到 Hessian 知道曲率与收敛速度, 看到 KL 知道信息几何度量.
6. 看见论文里的 $\nabla_\theta \mathcal{L}$, $\mathbb{E}{z \sim q\phi}$, $\arg\max$, $\mathrm{softmax}(x_i) = \frac{e^{x_i}}{\sum_j e^{x_j}}$ 不再绕路查, 直接进语义.

章节结构

• 开篇: 工程数学 + 离散数学为什么放最前 ← 当前
• 1. 离散数学: 逻辑 / 集合 / 关系 / 图 / 组合 / 递推 / 代数结构
• 2. 线性代数: 向量空间 / 矩阵 / 谱 / SVD / 张量
• 3. 概率统计: 分布 / 贝叶斯 / MLE / MAP / 极限 / KL
• 4. 微积分与最优化: 链式法则 / 雅可比 / Hessian / 凸优化 / 信息几何

一句话定位各篇

与后续各部分的接口表

数学记号约定

本部分及后续章节统一:

历史 1: 数学从「展演」到「工具」

直到 19 世纪末, 数学主要被看作「展演正确性」的几何 (Euclid, Hill-bert纲领). 转折来自:

• Cantor (1874) 集合论, 把"对象"抽象成元素归类, 离散与连续统一描述.
• Boole (1847) 把命题逻辑符号化; Frege (1879) 量词引入谓词逻辑.
• Galois (1832) 把方程根的对称性抽象成"群", 开启代数结构时代.
• Shannon (1937) 在硕士论文用 Boole 描述电路, 把逻辑与硬件从此打通.
• von Neumann (1945) 用矩阵描述量子; 后续与 Turing/Gödel 把可计算性数学化.

几乎所有"现代"概念——状态机、加密、调度、神经元——本质都是上述四个抽象在不同语境的复用.

历史 2: 计算机"故意"用最少的数学

计算机绕开重数学的几次关键:

• Dijkstra 把分布算法从微积分里抽出来, 用 == 不变式与最弱前置条件证明.
• Turing 把"计算"压成纸带符号集, 所以 TM 用最基本集合+函数即可定义.
• Curry-Howard 把逻辑证明和程序等价, ML 派系不需要范畴论也能用.
• Cloud Native 用声明式 schema (YAML/HCL) 把不变式显式化, 无需要证.

→ 结论: 本部分讲解数学, 不为「让你在每行注释里推演」, 而为「让你看懂前面十二部分为何能这样设计, 并在未来读论文时不在记号处卡住」.

阅读路径推荐

按背景三选一:

1. DSA 已熟 + 看论文吃力: 先看 2 线性代数 与 3 概率统计, 再看 4 微积分.
2. 应用背景 + 没系统学过理论: 从 1 离散数学 入, 它最贴近 DSA 与 Compiler.
3. 学习 Transformer 优先: 走 2 → 3 → 4 这条线, 离散可以暂时跳过.

与 TODO 的关系

TODO.md 中列的"未来可继续扩展方向 AI/ML 理论与实践（含 attention/Transformer 数学）"的前半——attention 数学——的预备知识全在本部分. 未来 ML 章节直接引用本部分 §2/§3/§4 即可, 不再重头讲线代与反向传播.

下一篇: 1. 离散数学: 逻辑 / 集合 / 关系 / 图 / 组合 / 递推 / 代数结构.

1. 离散数学: 逻辑 / 集合 / 关系 / 图 / 组合 / 递推 / 代数结构

TL;DR

计算机里几乎所有"结构"——状态、链接、调度、协议、类型、密钥——都是离散对象 + 关系。这一篇覆盖 7 个相互串接的核心:

1. 命题与谓词逻辑 — 程序不变式、Hoare 三元组的语言.
2. 集合 — 元素 + 隶属; 一切数据结构的最朴素的容器.
3. 关系与函数 — git rebase、外键、MRO 看似无关其实同构.
4. 图 — DSA 第 5 章、OS 调度、Compiler CFG、Distributed 一致性都靠它.
5. 组合计数 — $\binom{n}{k}$、$\sum$、容斥; DSA 与概率论的中间地带.
6. 递推与生成函数 — 复杂度主定理、Fibonacci、Catalan 的统一视角.
7. 代数结构: 群环域 — Crypto 全部、信息论 BCH/RS 编码的硬基础.

目标: 让你看 DFA、git merge-base、 FOREIGN KEY、ECDSA over secp256k1、Master Theorem 时不再"知道但说不清".

一、命题与谓词逻辑

1.1 命题联结词

工程翻译:

• if (P) {...} 的前置条件是 $\neg P$ 表示"程序不变式未维护".
• &&, || 短路求值 ($P \land Q$ 在 P 假时 Q 不必算) ⊆ 严格命题逻辑.
• 异或 $\oplus$ 是密码学奇偶检验、FEC parity、CRC 的核心.

1.2 关键恒等式

$$ P \Rightarrow Q ;\equiv; \neg P \lor Q ;\equiv; \neg Q \Rightarrow \neg P \quad (\text{逆否}) $$

$$ \neg(P \land Q) ;\equiv; \neg P \lor \neg Q \qquad \text{(De Morgan)} $$

$$ \neg(P \lor Q) ;\equiv; \neg P \land \neg Q $$

$$ (P \Rightarrow Q) \land (P \Rightarrow R) ;\equiv; P \Rightarrow (Q \land R) $$

1.3 谓词逻辑: 量词

加入"对所有 / 存在":

• $\forall x \in S: P(x)$ — 对所有 $x$ 满足.
• $\exists x \in S: P(x)$ — 至少一个满足.

否定翻转量词 (这是最容易出错的):

$$ \neg \big( \forall x: P(x) \big) ;\equiv; \exists x: \neg P(x) $$ $$ \neg \big( \exists x: P(x) \big) ;\equiv; \forall x: \neg P(x) $$

例: $\forall T \in \text{Threads}: \text{safe}(T)$ 的反面是"$\exists T$ 不safe", 即"有 bug 时的反例".

1.4 与程序的不变式

Hoare 三元组 ${P}\ S\ {Q}$: 若执行前 $P$ 真, 则 $S$ 终止后 $Q$ 真.

最弱前置条件 $\mathrm{wp}(S, Q)$ 是所有使 $S$ 终止后满足 $Q$ 的最弱前置. Dijkstra 用它做了程序演算, 把程序证明转为公式演算.

二、集合

2.1 基本定义

• 元素 $a \in A$, 空集 $\emptyset = {}$.
• 子集 $A \subseteq B$: $\forall x \in A \Rightarrow x \in B$.
• 真子集 $A \subsetneq B$: 子集且 $A \neq B$.
• 集合大小 $|A|$, 幂集 $\mathcal{P}(A) = 2^A$, $|2^A| = 2^{|A|}$.

2.2 集合运算

$$ |A \cup B| = |A| + |B| - |A \cap B| \quad (\text{容斥}) $$

2.3 与类型的关系

类型系统里的 Set<T> / Option<T> / &'a T 都可视为带约束的集合:

• Option<T> ≡ ${\bot} \cup T$.
• enum ≡ 不相交并 (tagged union).
• struct { A, B } ≡ 笛卡尔积.
• &'a T ≡ $T$ 受 lifetime 'a 约束子集.

三、关系与函数

3.1 关系 (二元关系)

$R \subseteq A \times B$ 是一个二元关系. 当 $A = B$, 称 $R$ 是 $A$ 上的关系. 记 $a R b$ 表 $(a, b) \in R$.

五大性质:

3.2 三种关键关系

• 等价关系: 自反 + 对称 + 传递 → 把集合拆成不相交等价类. 商集 $A / R$ 即等价类集合.
  • 例: 整数模 $n$ 的同余 $\equiv_n$ → $\mathbb{Z}/n\mathbb{Z}$.
  • 例: Rust Hash + Eq 把同一桶当成等价类.
• 偏序 (partial order): 自反 + 反对称 + 传递. 记 $\leq$.
  • 例: git commits 的祖先关系 ($\text{merge-base}$ 是下确界).
  • 例: 多继承 MRO (C3 linearization) 即偏序的拓扑序.
  • 例: 集合包含 $\subseteq$.
• 全序: 偏序 + 任两元素可比. 例: $\leq$ on $\mathbb{Z}$.

3.3 闭包

最小扩 $R$ 以满足某性质的最小关系:

• 自反闭包: 加 ${(a, a) : a \in A}$.
• 对称闭包: 加 ${(b, a) : (a, b) \in R}$.
• 传递闭包: $R^+ = \bigcup_{k \geq 1} R^k$ (关系合成 $k$ 次).

3.4 函数

$f: A \to B$ 是 $A \times B$ 的特殊关系: 每一 $a \in A$ 恰有一个 $b = f(a) \in B$.

• 单射 (injective): 不同 $a$ 映到不同 $b$.
• 满射 (surjective): $f(A) = B$.
• 双射 (bijective): 单 + 满; 存在逆 $f^{-1}$.

例: 哈希函数 h: Key → Slot 不是单射 (满射/碰撞), 退化为多值; 完美哈希才是双射.

四、图

4.1 形式化

图 $G = (V, E)$, $E \subseteq V \times V$ (有向) 或 $E \subseteq \binom{V}{2}$ (无向). 加权则 $w: E \to \mathbb{R}$.

几种特殊图:

4.2 关键概念

• 度: $d(v)$ = 邻接边数; $\sum_{v \in V} d(v) = 2|E|$. (握手引理)
• 路径与环: 路径不重复边 = trail; 不重复点 = simple.
• 连通分量: 无向图的最大连通子图.
• 生成树: 连通图的极小连通子图; $|T| = |V| - 1$.
• 强连通分量 (SCC): 有向图里每两点互达; Tarjan $O(V+E)$.
• 入度/出度: 有向图; $d_{\text{in}}(v), d_{\text{out}}(v)$.
• 拓扑序: DAG 上 $\forall (u, v) \in E: u <_{\text{topo}} v$.

4.3 图表示与遍历

按工程取舍选择:

遍历:

• DFS 用栈 / 递归; 可判连通、拓扑序、SCC. $\Theta(V + E)$.
• BFS 用队列; 给最短路 (无权) 与层序. $\Theta(V + E)$.

4.4 经典定理: 欧拉回路判定

判定: 连通图存在欧拉回路 $\Leftrightarrow$ 每点度偶数; 存在欧拉路径 $\Leftrightarrow$ 恰 0 或 2 点奇度.

应用: DNA 片段拼接 (de Bruijn graph)、LeetCode "reconstruct itinerary".

4.5 二部图与匹配

• 二部图判定: BFS / DFS 二着色 (无奇环).
• 最大匹配在二部图 = Hopcroft-Karp $O(E \sqrt V)$; 无向一般图 = Edmonds blossom $O(V^2 E)$.
• 最大流模型统一 matches、assignment、Hall 婚姻定理.

五、组合计数

5.1 四大基本法则

5.2 排列与组合

• 排列 (有顺序): $A_n^k = P(n, k) = \dfrac{n!}{(n-k)!}$.
• 组合 (无序): $\binom{n}{k} = \dfrac{n!}{k!(n-k)!}$.
• $k$-可重组合 (放回抽样): $\binom{n+k-1}{k}$.
• 全排列: $n!$; $k$-可重排列: $n^k$.

重要恒等 (Pascal):

$$ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} $$

Vandermonde:

$$ \binom{m+n}{k} = \sum_{i=0}^k \binom{m}{i}\binom{n}{k-i} $$

5.3 高级工具

• 生成函数: 数列 ${a_n}$ 的普通生成函数 $G(x) = \sum_n a_n x^n$. 组合恒等可代数推导.
• 指数生成函数: $E(x) = \sum_n a_n \dfrac{x^n}{n!}$; 排列场景.
• 容斥原理: 子集加减交错, 解决 "恰 k 个性质" 问题.

5.4 重要组合数

5.5 朴素思路估复杂度

六、递推与生成函数

6.1 解递推的三大工具

6.2 主定理 (记忆版)

设 $T(n) = a T(n/b) + f(n)$, $a \geq 1, b > 1$, 定义 $n^{\log_b a}$:

1. $f(n) = O(n^{\log_b a - \epsilon}) \Rightarrow T(n) = \Theta(n^{\log_b a})$ — 叶子主导.
2. $f(n) = \Theta(n^{\log_b a} \log^k n) \Rightarrow T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$ — 同阶.
3. $f(n) = \Omega(n^{\log_b a + \epsilon})$ 且正则条件 $\Rightarrow T(n) = \Theta(f(n))$ — 根主导.

查表(熟记即可秒定):

6.3 通过生成函数解 Fibonacci

设 $F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$. 生成函数:

$$ G(x) = \sum_n F_n x^n = \frac{x}{1 - x - x^2} $$

分母 $1 - x - x^2 = (1 - \varphi_+ x)(1 - \varphi_- x)$, 其中 $\varphi_\pm = \dfrac{1 \pm \sqrt 5}{2}$.

部分分式 → 闭式 (Binet):

$$ F_n = \frac{1}{\sqrt 5}\left(\varphi_+^n - \varphi_-^n\right), \quad F_n = \Theta(\varphi_+^n) \approx \Theta(1.618^n) $$

工程含义: 普通递归 Fibonacci 是指数级. 用 memoization / DP 后 $O(n)$; 用矩阵快速幂 $O(\log n)$.

def fib_fast(n: int) -> int:
    # 矩阵快速幂: [[1,1],[1,0]]^n = [[F_{n+1}, F_n],[F_n, F_{n-1}]]
    def mul(A, B):
        return [[A[0][0]*B[0][0] + A[0][1]*B[1][0],
                 A[0][0]*B[0][1] + A[0][1]*B[1][1]],
                [A[1][0]*B[0][0] + A[1][1]*B[1][0],
                 A[1][0]*B[0][1] + A[1][1]*B[1][1]]]
    def pow_mat(M, k):
        R = [[1,0],[0,1]]
        while k:
            if k & 1: R = mul(R, M)
            M = mul(M, M); k >>= 1
        return R
    return pow_mat([[1,1],[1,0]], n)[0][1]

# 复杂度: 乘法 O(M(大数位数)) → 总 O(n 位 · log n)
# 这里 n 是步数, 内部 M(数字位数) 可视为常数

export function fibFast(n: number): number {
  // 同上矩阵快速幂;BigInt 在 n 较大时必需
  type Mat = [bigint, bigint, bigint, bigint];
  const mul = (A: Mat, B: Mat): Mat => [
    A[0]*B[0] + A[1]*B[2], A[0]*B[1] + A[1]*B[3],
    A[2]*B[0] + A[3]*B[2], A[2]*B[1] + A[3]*B[3],
  ];
  let R: Mat = [1n, 0n, 0n, 1n];
  let M: Mat = [1n, 1n, 1n, 0n];
  let k = n;
  while (k > 0) {
    if (k & 1) R = mul(R, M);
    M = mul(M, M); k >>= 1;
  }
  return Number(R[1]);
}

6.4 生成函数速查

七、代数结构: 群 / 环 / 域

这一小节是 Crypto 第十部分 与 信息论 BCH/RS 的硬前置.

7.1 三层结构

群的四条公理:

1. 封闭性: $\forall a, b \in G: a \cdot b \in G$.
2. 结合律: $(a \cdot b) \cdot c = a \cdot (b \cdot c)$.
3. 幺元: $\exists e: a \cdot e = e \cdot a = a$.
4. 逆元: $\forall a: \exists a^{-1}: a \cdot a^{-1} = e$.

可交换群 (Abelian): $\forall a, b: a b = b a$.

7.2 子群 / 陪集 / Lagrange

子群 $H \leq G$: $H \subseteq G$ 且自身成群. 陪集 $a H = {a h : h \in H}$.

Lagrange 定理: $|G| = |H| \cdot [G : H]$, 即子群大小整除群大小.

→ 推论: 素数阶群无非平凡子群; 元素的阶整除群阶。

7.3 环与域

环 $(R, +, \cdot)$: $(R, +)$ 是 Abelian 群, $(R, \cdot)$ 半群, 分配律.

域 $(\mathbb{F}, +, \cdot)$: $(\mathbb{F}^*, \cdot)$ 也是 Abelian 群 (非零元可逆). 即"能做加减乘除".

关键例:

• $\mathbb{Q}, \mathbb{R}, \mathbb{C}$ 无限域.
• $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$ ($p$ 素): 最常用的有限域.
• $\mathbb{F}{p^k}$ (扩展域): BCH / RS 码用 $\mathbb{F}{2^8}$.
• 椭圆曲线 $\mathbb{F}_p$ 上点的加群.

7.4 模运算

$\mathbb{Z}_n = {0, 1, \ldots, n-1}$ 加法模 $n$. 它是环; $\mathbb{Z}_p$ ($p$ 素) 是域.

重要定理 (Fermat 小定理): $a^{p-1} \equiv 1 \pmod p$ ($a \not\equiv 0$).

def mod_pow(base: int, exp: int, mod: int) -> int:
    # 平方乘: O(log exp) 次乘法, 全程 mod
    result = 1
    base %= mod
    while exp > 0:
        if exp & 1:
            result = result * base % mod
        base = base * base % mod
        exp >>= 1
    return result

# Crypto 中 RSA 取 d 使 ed ≡ 1 (mod φ(n));
# 这把 pow(x, ed, n) → x 还原 RSA

7.5 离散对数 = Crypto 的硬假设

定义: 给定 $g$ 与 $h = g^x$ in 群 $G$, 求 $x$ = DLP.

• 在 $\mathbb{Z}_p^*$ 上, $x$ 大 (e.g. $p = 2^{256}$) 时, DLP ~ $O(\sqrt p)$ (Pollard rho), 仍硬.
• 在椭圆曲线群 $\mathbb{F}_p$ 上, DLP ~ $O(\sqrt N)$; 无 sub-exponential 算法 → 同长更安全 → secp256k1, Curve25519.

7.6 与"离散"和"传统"的对比

计算机世界本质就是"离散为主, 连续为辅"——但优化、信号处理某些处需要"连续数学版" (见 §2 线代 §3 概率 §4 微积分).

八、结束 + 速查表

下一篇: 2. 线性代数: 向量空间 / 矩阵 / 谱 / SVD / 张量.

2. 线性代数: 向量空间 / 矩阵 / 谱 / SVD / 张量

TL;DR

线性代数是计算机里所有"高维空间"的总称——一份 1B 参数权重、一帧图像的像素张量、一次 attention 的 $Q K V$ 矩阵、PageRank 的转移矩阵, 在数学上完全等价于一组线性变换. 这一篇覆盖六件工具:

1. 向量空间: 集合 + 加 + 数乘; 列向量是 $\mathbb{R}^n$ 的元素.
2. 矩阵 = 线性变换: 乘法、秩、迹、行列式.
3. 特征分解: $A v = \lambda v$; 不变子空间.
4. SVD: 任意 $m \times n$ 矩阵的"正交对角"分解, 几乎是工程 (PageRank / PCA / 推荐系统 / LoRA) 的瑞士军刀.
5. 正定矩阵与范数: 几何度量 / 内积 / 投影.
6. 张量: 从向量到矩阵到 3 阶 4 阶; Transformer 里 $\mathrm{softmax}, \text{attention}$ 全是张量收缩.

目标: 看论文里 $Q K^\top \in \mathbb{R}^{n \times n}$ / softmax over axis=-1 / rank-$r$ approximation 不再绕路查.

一、向量空间

1.1 定义

向量空间 $V$ 在域 $\mathbb{F}$ (默认 $\mathbb{R}$) 上: 元素 $u, v \in V$ 满足加法+数乘封闭, 且遵循 8 条公理 (加法系 Abelian 群 + 数乘结合/分配).

工程直觉: $\mathbb{R}^n$ 是最熟悉的实例; 一张 $28 \times 28$ 图像是 $\mathbb{R}^{784}$ 的一个点; 一个 768 维 embedding 也是.

1.2 线性无关 / 维数

• 一组向量 ${v_1, \ldots, v_k}$ 线性无关: $\sum c_i v_i = 0 \iff c_i = 0$.
• 极大无关组叫基; 基的大小叫维数 $\dim V$.
• 子空间 $W \subseteq V$: 自身成空间.

1.3 四个核心子空间 (任意矩阵)

矩阵 $A \in \mathbb{R}^{m \times n}$ 自动定义四个子空间:

1.4 内积与范数

内积 $\langle u, v \rangle = \sum u_i v_i = u^\top v$. 诱导范数:

$$ |u|_2 = \sqrt{\langle u, u\rangle}, \quad |u|1 = \sum |u_i|, \quad |u|\infty = \max |u_i| $$

• 柯西-施瓦茨: $|\langle u, v\rangle| \leq |u|_2 |v|_2$.
• 三角不等式: $|u + v| \leq |u| + |v|$.
• 余弦相似度: $\cos \theta = \frac{\langle u, v\rangle}{|u| |v|}$, 这是 embedding 检索的核心度量.

二、矩阵与线性变换

2.1 矩阵 = 线性变换

矩阵 $A \in \mathbb{R}^{m \times n}$ 表示 $\mathbb{R}^n \to \mathbb{R}^m$ 的线性变换: $x \mapsto A x$.

叠加性: $A(u + v) = A u + A v$; $A(c u) = c A(u)$ 一旦满足即线性.

关键矩阵:

2.2 矩阵运算

$$ (AB)^\top = B^\top A^\top, \quad (AB)^{-1} = B^{-1} A^{-1}, \quad \operatorname{tr}(AB) = \operatorname{tr}(BA) $$

$$ \det(AB) = \det(A) \det(B), \quad \det(A^{-1}) = 1/\det(A) $$

迹性质: $\operatorname{tr}(A) = \sum_i A_{ii} = \sum \lambda_i$ (任意方阵特征值和). 行列式: $\det A = \prod \lambda_i$; 几何意 = 列向量张成平行多面体体积.

2.3 秩与可逆

$\operatorname{rank} A$ = 列空间 (行空间) 维数.

• $A$ 可逆 $\Leftrightarrow$ 满秩; $A^\top A$ 正定 $\Leftrightarrow A$ 列满秩.
• 秩-零度定理: $\operatorname{rank} A + \dim \mathcal{N}(A) = n$.

2.4 矩阵分解速查

工程上"求逆/解方程"通常先做分解:

import numpy as np
A = np.random.randn(5, 3)
U, s, Vt = np.linalg.svd(A)            # 任意 A 都是 U Σ V^T
print(U.shape, s.shape, Vt.shape)        # (5,5) (3,) (3,3)
# 列空间 = U[:, :3] 张成; 奇异值 = s
# 奇异值越大 → 该方向越"重" → 用于压缩

三、特征值与特征向量

3.1 定义

$$ A v = \lambda v \quad (v \neq 0) $$

$\lambda$ 称 $A$ 的特征值, $v$ 对应特征向量. 组合起来 ${(\lambda_i, v_i)}$ 即 $A$ 的谱.

特征值几何意: 在 $v$ 方向上, $A$ 只缩放 (不改变方向); 矩阵的整体"行为"分布在各方向上的缩放因子.

3.2 关键性质

• $A$ 对称 ⇒ 特征值全实 + 特征向量可正交选取.
• $\det A = \prod_i \lambda_i$; $\operatorname{tr} A = \sum_i \lambda_i$.
• $A^k$ 的特征值 = $\lambda_i^k$; 一句话推出 PageRank 一致收敛.
• 谱半径 $\rho(A) = \max |\lambda_i|$; 决定 $A^k$ 是否发散.

3.3 谱定理 (实对称矩阵)

对称矩阵 $A$ 永远正交对角化:

$$ A = Q \Lambda Q^\top, \quad Q^\top Q = I, \quad \Lambda = \operatorname{diag}(\lambda_i) $$

含义: 对称矩阵只是"沿正交方向独立缩放"。这是 PCA、谱聚类、协方差分析的根; 也解释为什么 np.cov 是对称的.

3.4 应用: Markov 链 + PageRank

设 $A$ 是行随机矩阵; $\lambda_1 = 1$ 是最大特征值, 对应特征向量是平稳分布. PageRank 即:

$$ r = \alpha S r + (1 - \alpha) \frac{\mathbf{1}}{n} $$

幂迭代 $r_{k+1} = \alpha S r_k + \cdots$ 收敛到唯一平稳分布, 由 Perron-Frobenius 保证.

四、SVD: 通用瑞士军刀

4.1 定理

任意 $A \in \mathbb{R}^{m \times n}$ 可分解为:

$$ A = U \Sigma V^\top, \quad U \in \mathbb{R}^{m \times m}, V \in \mathbb{R}^{n \times n}, \Sigma = \operatorname{diag}(\sigma_1, \ldots, \sigma_{\min(m,n)}) $$

• $U, V$ 正交, $\Sigma$ 唯一对角奇异值 $\sigma_1 \geq \ldots \geq 0$.
• $\sigma_i = \sqrt{\lambda_i(A^\top A)} = \sqrt{\lambda_i(A A^\top)}$.
• $\operatorname{rank} A = $ 非零奇异值个数.

4.2 低秩近似 (Eckart-Young)

$$ A_k = \sum_{i=1}^k \sigma_i u_i v_i^\top $$

是所有秩-$k$ 矩阵中最佳 (Frobenius 与 $L_2$ 范数) 近似 $A$.

应用:

• PCA: 把协方差矩阵做 $A U$ 投影到主分量, 数据压缩 $k \ll n$.
• LSA: 搜索引擎把词-文档矩阵 SVD 取 top-$k$ 维.
• 推荐系统 (collaborative filtering 的 baseline): 评分矩阵 SVD.
• LoRA: $W = W_0 + B A$, $A, B$ 低秩 → 参数省至 $r \cdot (m + n)$.

4.3 数值秩与极大秩近似的工程直觉

奇异值衰减快 ⇒ 矩阵"近似秩"小 ⇒ 可被低秩参数化压缩; 衰减慢 ⇒ 信息等分布在各方向.

→ 这就是 HuggingFace 上 LoRA 试不同 $r$ (通常 8 / 16 / 32) 的根源: $r$ 取多大决定能拟合多少"低秩修正".

五、正定矩阵与范数

5.1 正定矩阵

对称矩阵 $A \succeq 0$: $\forall x \neq 0: x^\top A x \geq 0$.

$A \succ 0$ (正定): $x^\top A x > 0$ 对任意 $x \neq 0$.

等价条件: 特征值全正; $A = L L^\top$ (Cholesky 存在); 行列式、主子式全正.

用途:

• 协方差矩阵是正定; KL 散度在海森度量下表现.
• 优化: Hessian 正定 ⇒ 局部极小是凸.
• Mahalanobis 距离 $d(x, \mu) = \sqrt{(x - \mu)^\top \Sigma^{-1}(x - \mu)}$ ⇒ 协方差逆度量.

5.2 矩阵范数

• Frobenius: $|A|F = \sqrt{\sum a{ij}^2} = \sqrt{\operatorname{tr}(A^\top A)}$.
• 谱范数 (2-范数): $|A|2 = \sigma{\max}(A)$.
• 1 范数: 列求和最大.
• $\infty$ 范数: 行求和最大.

六、张量: 从 2 阶到 N 阶

6.1 定义

张量 (此处指多维数组, 物理学晶格张量定义同源不同语境) 是矩阵的推广:

• 0 阶张量: 标量 $a$.
• 1 阶: 向量 $v \in \mathbb{R}^n$.
• 2 阶: 矩阵 $A \in \mathbb{R}^{m \times n}$.
• 3 阶: $T \in \mathbb{R}^{m \times n \times k}$ — 例如 batch × token × embedding.
• 4 阶: batch × channel × height × width (CNN 卷积核).

Transformer 维度速查:

6.2 张量收缩 (contraction)

矩阵乘法 $\sum_k A_{ik} B_{kj} = (AB)_{ij}$ 是 2 阶张量沿 $k$ 阶的收缩. 高阶张量收缩 = 在 N 阶任意选定一对轴求和.

例 (Self-attention 核心):

$$ \mathrm{Att}(Q,K,V) = \mathrm{softmax}\left(\frac{Q K^\top}{\sqrt{d_k}}\right) V $$

• $Q K^\top$: [B, T, d_h] × [B, d_h, T] → [B, T, T] (batched matmul).
• softmax 沿 last axis: $[\sum_j e^{s_{ij}} = 1]$.
• 再 $\times V$ → [B, T, d_h].

工程上 PyTorch / JAX 的 torch.einsum('btd,bhd->bth', X, W) 就是把任意张量收缩按 Einstein 求和约定写出来.

import torch
# Multi-head self-attention 的核心一步
# X: [B, T, d]; Wq/Wk/Wv: [d, H, d_h]
def attention(X, Wq, Wk, Wv):
    Q = torch.einsum('btd,dhs->bhts', X, Wq)    # [B, H, T, d_h]
    K = torch.einsum('btd,dhs->bhts', X, Wk)
    V = torch.einsum('btd,dhs->bhts', X, Wv)
    scores = Q @ K.transpose(-2, -1) / (Q.shape[-1] ** 0.5)  # [B,H,T,T]
    alpha = scores.softmax(dim=-1)
    return alpha @ V                              # [B, H, T, d_h]

// 纯 TS 教学版: 单头注意力, 假装 d=64, T=16
function softmaxRows(M: number[][]): number[][] {
  return M.map(row => {
    const m = Math.max(...row);
    const e = row.map(x => Math.exp(x - m));
    const Z = e.reduce((a, b) => a + b, 0);
    return e.map(x => x / Z);
  });
}
function attention(Q: number[][], K: number[][], V: number[][]): number[][] {
  // Q, K, V 皆为 [T, d]
  const d = Q[0].length;
  const T = Q.length;
  const scores: number[][] = Array.from({ length: T }, () => Array(T).fill(0));
  for (let i = 0; i < T; i++)
    for (let j = 0; j < T; j++) {
      let s = 0;
      for (let k = 0; k < d; k++) s += Q[i][k] * K[j][k];
      scores[i][j] = s / Math.sqrt(d);
    }
  const alpha = softmaxRows(scores);          // [T,T], 行和=1
  const out: number[][] = Array.from({ length: T }, () => Array(d).fill(0));
  for (let i = 0; i < T; i++)
    for (let j = 0; j < T; j++) {
      const a = alpha[i][j];
      for (let k = 0; k < d; k++) out[i][k] += a * V[j][k];
    }
  return out;
}

6.3 广播 (broadcasting)

NumPy / PyTorch 的广播规则:

1. 形状从右往左对齐.
2. 缺轴视为 1; 维度 1 沿该轴复制.
3. 不同维且 >1 ⇒ 报错.

七、四个工程界必备"小公式"

7.1 ML / Optimization 反复出现的恒等

$$ \frac{\partial}{\partial X} \mathbf{1}^\top X \boldsymbol{w} = \boldsymbol{w} \boldsymbol{1}^\top $$

$$ \frac{\partial}{\partial W} (X W) = X^\top \cdot (\text{梯度对 } XW) $$

记忆法: "梯度比原式少一个 W 的轴, 求导后留下 X 转置". 这是反向传播 (§4 微积分) 的本质.

7.2 矩阵微分三件套

forward                          backward (相同链路反向)
X -> XW -> P = softmax(XW)  -> loss   P - y   (对 score 的梯度)
                               ^^^
 W 的梯度 = X^T @ (P - y)        (链式法则的"收缩")

7.3 列 / 行视图相同

$Ax = b$ 可视为:

• 列视图: $b$ 是 A 列的线性组合, 权重 = $x$ 的对应元素.
• 行视图: 每行是一个超平面方程, 解 = 所有超平面交点.

→ 在 ML 里 列视图 是特征聚合, 行视图 是样本边界判别. 这是 SVM 与 PCA 的对偶视角.

7.4 投影

正交投影到列空间 $\mathcal{R}(A)$ 的矩阵:

$$ P_A = A (A^\top A)^{-1} A^\top $$

最小二乘解 $x = (A^\top A)^{-1} A^\top y$ 给出"投影后的坐标".

八、结束 + 速查表

下一篇: 3. 概率统计: 分布 / 贝叶斯 / MLE / MAP / 极限 / KL.

3. 概率统计: 分布 / 贝叶斯 / MLE / MAP / 极限 / KL

TL;DR

工程里的"概率"是刻画不确定性的语言: 你不知道这台机器 next minute 崩不崩, 但你能给一个分布; 你不知道 key 碰撞概率, 但你能算 bound; 你不知道 transformer 学到的 embedding 集中在哪儿, 但你能用 KL 散度告诉它"靠近分布 $P$ 别乱漂". 这一篇覆盖:

1. 概率空间与随机变量 — PSPACE / 离散 vs 连续 / pmf vs pdf / CDF.
2. 期望 / 方差 / 协方差 — 随机变量的"代数".
3. 核心分布家族 — Bernoulli / Binomial / Geometric / Poisson / Uniform / Exponential / Normal / Categorical / Multinomial.
4. 联合、条件、贝叶斯 — $\Pr(A|B) = \Pr(B|A)\Pr(A)/\Pr(B)$; 一句话逼回去重写不少系统.
5. MLE / MAP / EM — 数据 → 参数的反推; ML 训练就是 MLE 大写版.
6. 极限定理: LLN / CLT / 大偏差 — "为什么 N=30 够了 / 为什么 4-sigma rarely".
7. 熵 / 交叉熵 / KL 散度 — 信息论与 ML 的最小公因子, 见信息论章节.
8. 万一线性 GC 不可解的不确定: Concentration inequalities — Markov / Chebyshev / Hoeffding.

目标: 看到 "$\arg\max_\theta \prod_i p(x_i|\theta)$" 与 "$\arg\max_\theta \mathbb{E}_{z \sim q}[\ldots]$" 不再绕路查.

一、概率空间与随机变量

1.1 三件套 (Kolmogorov 公理)

概率空间 $(\Omega, \mathcal{F}, \Pr)$:

• $\Omega$ = 样本空间 (一切可能结果).
• $\mathcal{F} \subseteq 2^\Omega$ = 事件 $\sigma$-代数 (对补、可数并封闭).
• $\Pr: \mathcal{F} \to [0, 1]$ 满足:
  1. $\Pr(\Omega) = 1$.
  2. $\Pr(E) \geq 0$.
  3. 可数可加: 不相交 $E_i$ ⇒ $\Pr(\bigcup E_i) = \sum \Pr(E_i)$.

随机变量 $X: \Omega \to \mathbb{R}$, 它把"实验结果"映射成数值. $X$ 决定概率分布 $\Pr_X(S) = \Pr(X^{-1}(S))$.

1.2 离散 vs 连续

• 离散: 概率质量函数 (pmf) $p_X(x) = \Pr(X = x)$.
• 连续: 概率密度函数 (pdf) $f_X$; $\Pr(a \leq X \leq b) = \int_a^b f_X(x) dx$; pdf 可 > 1.

累计分布 (CDF): $F_X(t) = \Pr(X \leq t)$. 单调非降, 右连续, $\lim_{t\to-\infty}F=0$, $\lim_{t\to\infty}F=1$.

1.3 联合 / 边缘 / 条件

• 联合 pmf/pdf: $p_{X,Y}(x, y)$ 或 $f_{X,Y}(x, y)$.
• 边缘: $p_X(x) = \sum_y p_{X,Y}(x, y)$ (离散) 或 $\int f_{X,Y}(x, y) dy$ (连续).
• 条件: $p(x | y) = p(x, y) / p(y)$.

二、期望与方差

2.1 期望

$$ \mathbb{E}[X] = \begin{cases} \sum_x x , p(x) & \text{离散} \ \int x , f(x), dx & \text{连续} \end{cases} $$

线性性 (无论是否独立): $\mathbb{E}[aX + bY] = a \mathbb{E}[X] + b \mathbb{E}[Y]$.

乘积: $\mathbb{E}[XY] = \mathbb{E}[X]\mathbb{E}[Y]$ 仅当 $X, Y$ 独立.

Jensen 不等式: $\varphi$ 凸 ⇒ $\mathbb{E}[\varphi(X)] \geq \varphi(\mathbb{E}[X])$.

2.2 方差与协方差

$$ \operatorname{Var}(X) = \mathbb{E}[(X - \mu)^2] = \mathbb{E}[X^2] - (\mathbb{E}[X])^2 $$

$$ \operatorname{Cov}(X, Y) = \mathbb{E}[(X - \mathbb{E}X)(Y - \mathbb{E}Y)] = \mathbb{E}[XY] - \mathbb{E}X\mathbb{E}Y $$

$$ \operatorname{Cov}(aX, Y) = a \operatorname{Cov}(X, Y), \quad \operatorname{Var}(X \pm Y) = \operatorname{Var}X + \operatorname{Var}Y \pm 2\operatorname{Cov}(X, Y) $$

独立 ⇒ 协方差为 0 (逆命题不成立). 反例: $Y = X^2$, $X$ 取 ±1.

相关系数 $\rho = \mathrm{Cov}/(\sigma_X \sigma_Y) \in [-1, 1]$.

2.3 标准化与 z-score

$$ z = \frac{X - \mu}{\sigma} $$

→ 标准化的 $z$ 期望 0, 方差 1. Six-Sigma / Grubbs 检验 / 异常点检测都基于这个.

三、核心分布家族

3.1 离散

Poisson 公式直觉: 当 $n \to \infty, p \to 0, np \to \lambda$ 时, $\mathrm{Bin}(n, p) \to \mathrm{Poi}(\lambda)$. 这就是网络中"罕见事件计数"为何都用 Poisson.

3.2 连续

3.3 正态分布皇冠属性

$$ \mathcal{N}(\mu, \sigma^2): X = \mu + \sigma Z, Z \sim \mathcal{N}(0, 1) $$

• 68-95-99.7 法则: 1/2/3-sigma 范围内概率.
• 标准 $Z = (X - \mu)/\sigma$.
• $\mathrm{Poi}(\lambda), \lambda \to \infty$ 渐近 $\mathcal{N}(\lambda, \lambda)$.
• 独立正态之和仍正态 (稳定性).

3.4 多元正态 (MVN)

$$ X \sim \mathcal{N}(\boldsymbol\mu, \Sigma), \quad f(\boldsymbol x) = \frac{1}{(2\pi)^{d/2}|\Sigma|^{1/2}} e^{-\frac{1}{2}(\boldsymbol x - \boldsymbol\mu)^\top \Sigma^{-1}(\boldsymbol x - \boldsymbol\mu)} $$

• $|\Sigma|$ 是协方差矩阵行列式.
• $\Sigma$ 正定 ⇒ 可写为 $\Sigma = L L^\top$, $X = \mu + L Z$ (采样技巧).
• 边缘任意正态也是正态; 条件正态也是正态 (Bayesian inference 的便利).

四、贝叶斯定理与全概率

4.1 三段式

$$ \Pr(A | B) = \frac{\Pr(B | A) \Pr(A)}{\Pr(B)} $$

展开 $\Pr(B) = \sum_i \Pr(B | A_i) \Pr(A_i)$ 即全概率公式, 用于把"原因"$A_i$ 关联到"观察"$B$.

4.2 语言版图

$$ \text{posterior} \propto \text{likelihood} \cdot \text{prior} $$

4.3 经典例: 罕见病阳性

发病率 $0.1%$, 检测阳性准确率 $99%$ (sensitivity=specificity=0.99). 你阳, 真病概率?

$$ \Pr(\text{sick} | +) = \frac{0.99 \cdot 0.001}{0.99 \cdot 0.001 + 0.01 \cdot 0.999} \approx \frac{0.00099}{0.010989} \approx 9% $$

4.4 共轭先验速查

→ LDA / 主题模型几乎全在这张表上演, 见后续 ML 章节.

五、MLE / MAP / EM

5.1 最大似然估计 (MLE)

给定 i.i.d. 观测 $x_1, \ldots, x_n$, 取 $f(x; \theta)$ 的参数 $\theta$ 使观察到的数据最有说服力:

$$ \hat\theta_{\text{MLE}} = \arg\max_\theta \prod_{i=1}^n f(x_i; \theta) $$

工程上取 log 化为 sum:

$$ \hat\theta_{\text{MLE}} = \arg\max_\theta \sum_i \log f(x_i; \theta) $$

5.2 几个经典 MLE

Bernoulli: $\hat p = \frac{1}{n} \sum x_i$ (样本均值).

Normal (未知 $\mu, \sigma^2$): $\hat\mu = \bar x$, $\hat\sigma^2 = \frac{1}{n}\sum (x_i - \bar x)^2$.

Uniform $U(0, \theta)$: $\hat\theta = \max x_i$. 注意 MLE 有偏 ($\mathbb{E}[\max] = \frac{n}{n+1}\theta$).

5.3 MAP = MLE + Prior

$$ \hat\theta_{\text{MAP}} = \arg\max_\theta ; \prod f(x_i | \theta) \cdot p(\theta) $$

MLE 即先验均匀的 MAP. 加入先验等同于正则化:

• 似然 $\mathcal{N}(\bar x, \cdots)$ + 先验 $\theta \sim \mathcal{N}(0, \tau^2)$ ⇒ $\arg\min_\theta |y - X\theta|^2 + \frac{\sigma^2}{\tau^2} |\theta|^2$, 即 ridge regression.
• Laplacian 先验 ⇒ L1 = LASSO.

5.4 EM 算法 (Expectation-Maximization)

数据有隐变量 $z$ 时, 直接解 MLE 解不出. EM 迭代:

1. E 步: 写完整似然关于当前隐变量后验的期望 $$ Q(\theta | \theta^{(t)}) = \mathbb{E}_{z | x, \theta^{(t)}}[\log p(x, z | \theta)] $$
2. M 步: $\theta^{(t+1)} = \arg\max_\theta Q(\theta | \theta^{(t)})$.

应用: GMM (高斯混合), HMM (Baum-Welch), K-means (硬分版本).

5.5 ELBO 与变分下界

$$ \log p(x) = \log \int p(x, z) dz \geq \mathbb{E}{z \sim q}[\log p(x, z)] - \mathbb{E}{z \sim q}[\log q(z)] $$

右侧即 ELBO (Evidence Lower Bound), 见后续变分推断与 VAE. 最大化 ELBO ⇔ 最小化 $\mathrm{KL}(q | p)$.

六、极限定理

6.1 大数定律 (LLN)

样本均值 $\bar X_n = \frac{1}{n}\sum X_i$ 几乎处处收敛到期望 $\mu$:

$$ \bar X_n \xrightarrow{\text{a.s.}} \mu $$

实践: Monte Carlo 取样本越多越逼近. 没有"无法估计方差 → 我就多采样"的工程路径就靠它.

6.2 中心极限定理 (CLT)

i.i.d. 期望 $\mu$ 方差 $\sigma^2$:

$$ \sqrt n \cdot \frac{\bar X_n - \mu}{\sigma} \xrightarrow{d} \mathcal{N}(0, 1) $$

含义: 无论原分布, 样本均值经标准化渐近正态. 这就是正态分布"伞覆盖了一切"的成因; 也是 Bayes 不能免先验的 freq 默认.

例: 一枚硬币 $100$ 次, 头数近似正态, $\mu = 50, \sigma = 5$. 大概率落在 $[40, 60]$.

6.3 大偏差 (Chernoff / Hoeffding)

LLN 说"最终到 $\mu$". 但要量化"偏离 $\epsilon$ 的概率多小":

Hoeffding 不等式 (有界 $X_i \in [a_i, b_i]$):

$$ \Pr\left[ \bar X_n - \mu \geq t \right] \leq \exp\left(-\frac{2 n^2 t^2}{\sum (b_i - a_i)^2}\right) $$

Chernoff bound (Bernoulli): $\Pr[\bar X_n \geq (p + \epsilon) n] \leq e^{-2 n \epsilon^2}$.

→ 这就是"为什么 100 次抛硬币正反偏离 0.5 不超过 0.1 是 ~5%".

6.4 Markov / Chebyshev / 推导链

Markov (最弱):    P[X ≥ a] ≤ E[X] / a               (X ≥ 0)
Chebyshev:        P[|X - μ| ≥ t] ≤ Var X / t²
Hoeffding:        exp(-2 n t²/(b-a)²)                 (i.i.d. 有界)
Chernoff:         exp(-2 n ε²)                          (Bernoulli)

工程代码: 越往下用, 越用得上紧 (依赖越强 → bound 越松).

6.5 Concentration 在 ML / Distributed 的使用

• ML 中"经验风险 vs 真实风险" gap 用 Hoeffding 量化 (generalization).
• Distributed 中 quorum W+R>N 的"读到最新写"概率 = majority 经 Chernoff 上界.
• 测算 hash 冲撞概率 = birthday bound (鸽巢变体).

七、信息论三件: 熵 / 交叉熵 / KL

7.1 熵 (重申信息论章 §1)

$$ H(X) = -\sum_x p(x) \log p(x), \quad H(X, Y), \quad H(X | Y), \quad I(X; Y) = H(X) - H(X | Y) $$

链式法则: $H(X, Y) = H(X) + H(Y | X)$.

7.2 KL 散度

测两个分布 $p$ 与 $q$ 的"差异":

$$ \mathrm{KL}(p | q) = \sum_x p(x) \log \frac{p(x)}{q(x)} $$

• $\mathrm{KL} \geq 0$, 等 0 当且仅当 $p = q$ a.s.
• 不对称: $\mathrm{KL}(p | q) \neq \mathrm{KL}(q | p)$. 选择方向决定 forward / reverse mode.
• Forward $\mathrm{KL}(p | q)$: $q$ 必须覆盖 $p$ 全支撑; 倾向 mode-seeking 忽略低概率区.
• Reverse $\mathrm{KL}(q | p)$: $q$ 倾向 mass-covering (mean-seeking), VAE 用这个.

7.3 交叉熵 = 熵 + KL

$$ H(p, q) = H(p) + \mathrm{KL}(p | q) $$

由于 $H(p)$ 对 $\theta$ 常量, 最小化交叉熵 ⇔ 最小化 KL, ML 分类损失几乎全部用这个:

$$ \mathcal{L}_{\text{CE}} = -\sum_i y_i \log \hat y_i $$

7.4 JS 散度 = 对称化 KL

$$ \mathrm{JS}(p | q) = \frac{1}{2}\mathrm{KL}(p | m) + \frac{1}{2}\mathrm{KL}(q | m), ; m = (p+q)/2 $$

GAN 的原始损失 = JS 的反向最大化.

八、随机过程初步

8.1 Markov 链

状态空间 $S$, 转移 $P_{ij} = \Pr(X_{t+1} = j | X_t = i)$. 无记忆性:

$$ \Pr(X_{t+1} | X_t, \ldots, X_0) = \Pr(X_{t+1} | X_t) $$

平稳分布 $\pi$: $\pi P = \pi$. 不可约+非周期 ⇒ 唯一, $P^k \to \mathbf{1}\pi^\top$.

应用: MCMC (Metropolis-Hastings / Gibbs), PageRank, HMM, 强化学习 (MDP 基础).

8.2 Poisson 过程

事件到达速率 $\lambda$, 间隔 $\sim \mathrm{Exp}(\lambda)$ i.i.d.. 计数 $N(t) \sim \mathrm{Poi}(\lambda t)$.

应用: OS 排队论、CDN 缓存命中率、DB 连接池、限流桶.

8.3 排队论 (M/M/1)

到达 Poisson, 服务 Exp, 1 个服务台:

$$ \rho = \frac{\lambda}{\mu}, \quad L_q = \frac{\rho^2}{1-\rho}, \quad W_q = \frac{\rho/\mu}{1 - \rho} $$

→ 资源利用率 $\rho \to 0.8$ 时队列开始爆炸, 这就是 SRE 不敢 < 50% buffer 的原因.

九、采样与估计实践

9.1 Monte Carlo

要算 $\mathbb{E}[f(X)]$ 没闭式 → 采样: $\frac{1}{n}\sum f(X_i)$, LLN 保证收敛, Hoeffding 给误差.

import numpy as np
def estimate_pi(n: int = 10_000_000) -> float:
    x = np.random.random(n); y = np.random.random(n)
    return 4 * (x*x + y*y < 1).mean()    # Naïve MC, σ ~ 0.5/√n
# n=1e6 → π ≈ 3.1416 ± 5e-4

9.2 重要采样 (Importance Sampling)

问题: 想算 $\mathbb{E}_p[f]$, 但只能从 $q$ 采样:

$$ \mathbb{E}_p[f] = \mathbb{E}_q\left[f(x) \cdot \frac{p(x)}{q(x)}\right] $$

→ 在 Off-policy RL / 罕见事件估计里必备. 也是 Transformer 推理"speculative decoding"的概率基础.

9.3 拒绝采样 + Metropolis

• 拒绝采样: 找一个易采的 envelope $M q(x) \geq p(x)$, 采 $x \sim q$ 接受概率 $p(x)/(M q(x))$.
• Metropolis-Hastings: 当前 $x$, 提议 $x'$, 接受概率 $\min(1, \frac{p(x')q(x | x')}{p(x)q(x' | x)})$.

十、结束 + 速查表

下一篇: 4. 微积分与最优化: 链式法则 / 雅可比 / Hessian / 凸优化 / 信息几何.

4. 微积分与最优化: 链式法则 / 雅可比 / Hessian / 凸优化 / 信息几何

TL;DR

优化是计算机科学里"反向"的一面: 用前向 (compiles 哪些到哪些) 算"loss", 再用反向 (链式法则) 算"该怎么改参数让 loss 更小". Transformer、信息论容量推导、调度器最短作业先选、HP 计算代价模型本质都是同一件事: 在光滑空间里取梯度. 这一篇覆盖:

1. 极限与导数 — 微分与差分的连续 / 离散切换.
2. 链式法则 + 多元函数 + 雅可比矩阵 — Transformer 反向传播的硬公式.
3. Hessian + 泰勒展开 + 二阶方法 — 极值附近的曲率信号.
4. 凸函数 / 凸优化 — 优化领域的"快 + 全局最优"区间.
5. 梯度下降 / Stochastic / Momentum / Adam — 工业优化器谱系.
6. 拉格朗日 + KKT — 带约束优化的标准框架.
7. 信息几何 — 用 KL / Fisher 度量把"分布空间"做成流形, 推出自然梯度与变分推断.

目标: 看到 Adam、EM、$\nabla_\phi \mathbb{E}[\ldots]$、$\Lambda \succeq 0$ 不再卡.

一、极限、连续、可导

1.1 极限

$\lim_{x \to a} f(x) = L$ 表任意 $\epsilon > 0$, 存在 $\delta$ 使 $0 < |x-a| < \delta \Rightarrow |f(x) - L| < \epsilon$ (Cauchy-Weierstrass 定义).

工程上渐近等价记号 $f(x) \sim g(x)$: $\lim_{x \to \infty} f/g = 1$. 与 DSA 中 $O/\Theta/\Omega$ 同根. 例如 $n! \sim \sqrt{2\pi n} (n/e)^n$ (Stling 公式) 是计算组合数 log 的钥匙.

1.2 导数

$$ f'(x) = \lim_{h \to 0} \frac{f(x+h) - f(x)}{h} $$

几何含义: 切线斜率. 物理含义: 瞬时速率.

关键四件:

• 链式: $(g \circ f)' = g'(f(x)) \cdot f'(x)$.
• 乘法: $(fg)' = f'g + fg'$.
• 商: $(f/g)' = (f'g - fg')/g^2$.
• 反函数: $(f^{-1})'(y) = 1/f'(x)$ where $y = f(x)$.

1.3 几个重要函数的导数

softmax 雅可比尤其重要, 见 §2.

1.4 积分

$$ \int_a^b f(x), dx = \lim_{n \to \infty} \sum_{i=0}^{n-1} f\left(a + i \frac{b-a}{n}\right) \cdot \frac{b-a}{n} $$

微积分基本定理:

$$ \int_a^b f(x), dx = F(b) - F(a), \quad F' = f $$

• 分部积分: $\int u, dv = uv - \int v, du$.
• 换元: $\int f(g(x)) g'(x) dx = \int f(u), du$.
• 概率积分 $\int e^{-x^2} dx$ 全空间 = $\sqrt{\pi}$, 这是 Gaussian 归一化常数.

二、多元与链式法则 (Transformer 必备)

2.1 偏导数与方向导数

$f: \mathbb{R}^n \to \mathbb{R}$ 的偏导 $\partial f / \partial x_i$. 梯度:

$$ \nabla f(\boldsymbol x) = \left(\frac{\partial f}{\partial x_1}, \ldots, \frac{\partial f}{\partial x_n}\right)^\top $$

方向 $\boldsymbol v$ 上的方向导数 = $\nabla f \cdot \boldsymbol v / |\boldsymbol v|$; 沿梯度方向取最大. 即"梯度下降合理性"的数学.

2.2 复合与雅可比

设 $g: \mathbb{R}^n \to \mathbb{R}^m$, $f: \mathbb{R}^m \to \mathbb{R}$. 复合 $h = f \circ g: \mathbb{R}^n \to \mathbb{R}$:

$$ \frac{\partial h}{\partial \boldsymbol x} = \underbrace{\nabla f(g(\boldsymbol x))^\top}{1 \times m} \cdot \underbrace{J_g(\boldsymbol x)}{m \times n} $$

$J_g$ 即雅可比矩阵, $[J_g]_{ij} = \partial g_i / \partial x_j$.

Transformer 反向传播就是矩阵化 + 反序的链式法则: 每一层的"loss 对输入梯度"= 该层输出梯度乘该层权重梯度.

2.3 softmax 雅可比

$\boldsymbol s = \mathrm{softmax}(\boldsymbol z)$:

$$ \frac{\partial s_i}{\partial z_j} = \begin{cases} s_i (1 - s_i) & i = j \ -s_i s_j & i \neq j \end{cases} $$

向量形式 $J_{\mathrm{softmax}} = \mathrm{diag}(s) - s s^\top$.

工程意义: 反向传 $(\boldsymbol{ds}) = J \cdot \boldsymbol{dz}$ 即 $\boldsymbol{ds} = s \odot (\boldsymbol{dz} - (s^\top \boldsymbol{dz})\mathbf{1})$.

2.4 反向传播 (autograd 模式)

import numpy as np
# 简化的两层数值梯度校验
def softmax_ce(logits, y):
    z = logits - logits.max(axis=-1, keepdims=True)
    e = np.exp(z); s = e / e.sum(axis=-1, keepdims=True)
    return -np.log(s[y] + 1e-12)

def grad_softmax_ce(logits, y):
    s = np.exp(logits - logits.max()) / np.exp(logits - logits.max()).sum()
    g = s.copy(); g[y] -= 1
    return g    # 简化: 对 logit 的导数 = (σ - onehot)

关键观察: 交叉熵 + softmax 的反传结果是 $(s - \mathbf{1}_y)$, 这条公式出现在每个 softmax 分类器里. 记下来一辈子省试错.

2.5 数值方法: 自动求导

• 前向模式 AD: 一个变量求偏导链, O(n) 算一个分量.
• 反向模式 AD: 一次反向跑出所有偏导, O(1) 算 loss 对所有参数 (gradient). 这就是 PyTorch 默认反向 (TensorFlow tf.GradientTape).

三、Hessian 与二阶

3.1 二阶偏导

$$ H_f(\boldsymbol x)_{ij} = \frac{\partial^2 f}{\partial x_i \partial x_j} $$

$H$ 是对称矩阵 (若 $f$ 充分光滑). 在 stationary $\nabla f = 0$ 处:

• $H \succ 0$ ⇒ 局部最小.
• $H \prec 0$ ⇒ 局部最大.
• 不定 ⇒ 鞍点.
• 半正定/半负定 ⇒ 二阶检验不足, 需高阶.

3.2 泰勒展开 (2D 局部)

$$ f(\boldsymbol x + \boldsymbol h) \approx f(\boldsymbol x) + \nabla f(\boldsymbol x)^\top \boldsymbol h + \frac{1}{2} \boldsymbol h^\top H_f(\boldsymbol x) \boldsymbol h $$

含义: 沿一阶方向线性近似; 二阶项表达曲率. 这就是 Newton 法、Trust-region、CG、BFGS 的全部来源.

3.3 Newton 迭代

$$ \boldsymbol x_{k+1} = \boldsymbol x_k - H_f^{-1}(\boldsymbol x_k) \nabla f(\boldsymbol x_k) $$

优点: 二次收玫 (近最优时极快). 缺点: 求 $(n \times n) H^{-1}$ 太贵, $H$ 可能 ill-conditioned. 工程变体:

• 拟牛顿 BFGS / L-BFGS: 用历史梯度更新 $H^{-1}$ 近似.
• 共轭梯度 CG: 只需 $H$ × 向量乘法.

3.4 为什么深度学习不用 Newton?

• 参数维度 $n \sim 10^9$, $H \in \mathbb{R}^{10^9 \times 10^9}$ 显然太贵.
• 非凸+随机性 ⇒ 一阶 SGD 经验反而更好+可 scale.
• 反向传播比求逆便宜太多.

→ 这就是 Adam 之类一阶方法的现实位置.

四、凸优化

4.1 凸函数

凸集 $S \subseteq \mathbb{R}^n$: $\forall \boldsymbol x, \boldsymbol y \in S, \lambda \in [0, 1]$: $\lambda \boldsymbol x + (1-\lambda) \boldsymbol y \in S$.

凸函数 $f: S \to \mathbb{R}$:

$$ f(\lambda \boldsymbol x + (1-\lambda)\boldsymbol y) \leq \lambda f(\boldsymbol x) + (1-\lambda)f(\boldsymbol y) $$

判定: 一阶 (凸) $\nabla^2 f \succeq 0$.

凸优化强:

• 任何局部最小 = 全局最小.
• KKT 条件充要 (约束情形).
• 多项式时间可达 $\epsilon$-optimal (Interior Point).

4.2 典型凸损失

4.3 拉格朗日对偶

原问题 $\min f(\boldsymbol x) \text{ s.t. } g_i(\boldsymbol x) \leq 0, h_j(\boldsymbol x) = 0$:

$$ \mathcal{L}(\boldsymbol x, \boldsymbol\lambda, \boldsymbol\nu) = f(\boldsymbol x) + \sum_i \lambda_i g_i(\boldsymbol x) + \sum_j \nu_j h_j(\boldsymbol x) $$

对偶函数 $g(\lambda, \nu) = \inf_x \mathcal{L}$. главная trick: 最大化对偶 ⇒ 上界原问题最优. 弱对偶恒, 强对偶凸+slater 条件.

4.4 KKT 条件

最优 $\boldsymbol x^*$ 满足:

1. Stationarity: $\nabla f + \sum_i \lambda_i \nabla g_i + \sum_j \nu_j \nabla h_j = 0$.
2. Primal feasibility: $g_i \leq 0, h_j = 0$.
3. Dual feasibility: $\lambda_i \geq 0$.
4. Complementary slackness: $\lambda_i g_i(\boldsymbol x^*) = 0$.

→ SVM 的推导从这里来; 因凸, KKT 充要.

4.5 LP / QP / SDP

LP:  min c^T x  s.t. Ax = b, x ≥ 0            (单纯形 / interior point)
QP:  min (1/2)x^T Q x + c^T x  s.t.  linear  (Q ≥ 0 ⇒ 凸)
SDP: min c^T x  s.t. F_0 + Σx_i F_i ⪰ 0      (矩阵半正定约束)

应用: LP 调度/路由; QP 投资组合 / SVM; SDP 控制论 / PhyLayer 检验扩展 Lyapunov.

五、迭代一阶优化器谱系

5.1 梯度下降 (GD)

$$ \boldsymbol x_{k+1} = \boldsymbol x_k - \eta \nabla f(\boldsymbol x_k) $$

• $\eta$ 小 ⇒ 慢但稳; 大 ⇒ 震荡可能发散.
• 收敛分析: $\eta \leq 1/L$ 时凸 $L$-smooth ⇒ $f_k - f^* = O(1/k)$.

5.2 SGD (Robbins-Monro 1951)

每次用 mini-batch 估计 $\nabla f \approx \hat g_k$:

$$ \boldsymbol x_{k+1} = \boldsymbol x_k - \eta_k \hat g_k $$

学习速率 schedule: $\sum \eta_k = \infty, \sum \eta_k^2 < \infty$ ⇒ a.s. 收敛 (Robbins-Monro).

5.3 Momentum / Nesterov

Momentum 在梯度方向添加"惯性":

$$ v_{k+1} = \beta v_k - \eta \nabla f(\boldsymbol x_k), \quad \boldsymbol x_{k+1} = \boldsymbol x_k + v_{k+1} $$

Nesterov 加速: 先用 $\boldsymbol x_k + \beta v_k$ 评估梯度.

直觉: 沿一致方向加速, 沿高频噪声阻尼. 凸情形 Nesterov 给最优 $O(1/k^2)$ 速率.

5.4 RMSProp

$$ \mathbb{E}[g^2]k = \alpha \mathbb{E}[g^2]{k-1} + (1-\alpha) g_k^2, \quad \boldsymbol x_{k+1} = \boldsymbol x_k - \frac{\eta}{\sqrt{\mathbb{E}[g^2]_k + \epsilon}} g_k $$

关键观察: 不同参数维度, 不同尺度梯度自适应 → Adam 接近 "1 个 axis 1 个步长".

5.5 Adam (Kingma & Ba 2014)

$$ m_k = \beta_1 m_{k-1} + (1-\beta_1) g_k $$ $$ v_k = \beta_2 v_{k-1} + (1-\beta_2) g_k^2 $$ $$ \hat m_k = \frac{m_k}{1 - \beta_1^k}, \quad \hat v_k = \frac{v_k}{1-\beta_2^k} $$ $$ \boldsymbol x_{k+1} = \boldsymbol x_k - \eta \frac{\hat m_k}{\sqrt{\hat v_k} + \epsilon} $$

• 默认 $\beta_1 = 0.9, \beta_2 = 0.999, \epsilon = 10^{-8}$.
• 动量 + RMSprop 合一; bias correction 针对初始时刻.
• ML 中 99% 任务用 Adam 即可跑出 baseline.

def adam_update(params, grads, m, v, t, lr=1e-3, b1=0.9, b2=0.999, eps=1e-8):
    for p, g in zip(params, grads):
        m[p] = b1 * m[p] + (1 - b1) * g
        v[p] = b2 * v[p] + (1 - b2) * g * g
        m_hat = m[p] / (1 - b1 ** t)
        v_hat = v[p] / (1 - b2 ** t)
        p -= lr * m_hat / (v_hat.sqrt() + eps)   # 高级 pseudocode
    return params, m, v

5.6 Optimizer 速查

六、信息几何

6.1 分布空间作流形

参数族 ${p_\theta: \theta \in \Theta}$, 一个分布对应一个参数点. Fisher 信息矩阵:

$$ \mathcal{I}(\theta){ij} = \mathbb{E}{x \sim p_\theta}\left[\frac{\partial \log p_\theta}{\partial \theta_i} \frac{\partial \log p_\theta}{\partial \theta_j}\right] $$

直觉: Fisher 信息 = "你能用数据区分参数变化的灵敏度". 实际 $\mathcal{I} = -\mathbb{E}[H_{\log p}]$ (期望负 Hessian).

6.2 KL 看作曲率

对参数 $\theta$ 微扰 $d\theta$, KL 散度局部展开:

$$ \mathrm{KL}(p_\theta | p_{\theta + d\theta}) = \frac{1}{2} d\theta^\top \mathcal{I}(\theta) d\theta + o(|d\theta|^2) $$

→ Fisher 矩阵就是分布参数空间的黎曼度量.

6.3 自然梯度

普通梯度下降不看度量; 用 Fisher 修正:

$$ \theta_{k+1} = \theta_k - \eta \cdot \mathcal{I}_k^{-1} g_k $$

直觉: 让"参数行进一步"在分布空间等价 (而不是欧式). 在 KL 时 $\theta$ 的大变化不一定 = $p$ 的大变化, 自然梯度把它校正.

→-policy gradient 变体如 TRPO / PPO 的原理, 自然梯度约束 $\mathrm{KL} \leq \delta$.

6.4 ELBO = KL 反向最小

变分推断要找近似 $q_\phi$ 拟合 $p(z | x)$. 写 ELBO:

$$ \mathcal{L}(\phi) = \mathbb{E}{q\phi}[\log p(x, z)] - \mathbb{E}{q\phi}[\log q_\phi(z)] $$

最大化 $\mathcal{L}$ ⇔ 最小化 $\mathrm{KL}(q_\phi | p_{z|x})$. VAE 解码器就是这么训.

七、其他常用工具

7.1 Logistic 函数 vs Softmax

$$ \sigma(x) = \frac{1}{1 + e^{-x}} = \mathrm{softmax}_+[x, 0] $$

→ 二分类 softmax = Logistic; $K$-分类是 softmax.

7.2 SVD 协助 PCA (重申线代)

PCA = 数据协方差矩阵 $\Sigma = (X - \bar X)^\top (X - \bar X)/n$ 做特征分解. 取 top-$k$ 特征向量方向. 等价: 数据矩阵 SVD 左奇异向量.

→ 推荐用 svd 而非 eig (数值更稳).

7.3 对偶: 极大熵分布

满足某些矩约束 $\mathbb{E}_p[g_i(x)] = c_i$ 的所有 $p$ 中, 熵最大的 $p^*$ 是指数族:

$$ p^*(x) = \frac{1}{Z} \exp\left(\sum_i \lambda_i g_i(x)\right) $$

→ Logistic 回归就是均值给定下熵最大的伯努利. 这是 Logistic 给"伯努利 + 高斯先验 → 应用最广"的数学根.

7.4 重要公式速查

八、结束 + 速查表

回主目录: 第零部分 · 工程数学与离散数学基础 README. 下一篇系统正文: 第一部分 · DSA 开篇.

工程化实践轴 · 让代码真正跑进生产

一句话

前面 14 个部分（导论 / 数学 / 13 主题）讲的是**"计算机是什么、为什么这样设计"；这一轴补另一半——"作为 1-20 年的工程师，你怎么把代码安全、可测、可发布、可观测、可维护地交到生产环境"**。它不重复任何一部的原理（Git 讲透但不重讲 DSA），而是把工程师每天面对的手艺活系统化：版本控制、测试、CI/CD、性能工程、应用安全、代码质量、可观测性。

思想链

[你写完了 feature 代码]
  └─> Git 分支 + 提交规范 + code review
        └─> CI 跑测试（单元/集成/契约/E2E）
              └─> 构建产物 → 镜像 → 发布（蓝绿/金丝雀）
                    └─> 上线后 metrics/logs/traces 三件套观测
                          └─> 性能劣化 → profiling 定位 → 优化
                                └─> 安全：OWASP + 认证授权 + 供应链
                                      └─> 回头重构 → 代码质量维持
                                            └─> 这就是工程化的完整闭环

每一环都依赖前面 14 部分的原理（Git 基于 DAG/哈希、CI 基于 shell、性能基于组成原理的 cache/IO），但方法本身是独立的手艺——这正是"工程化实践"和"计算机基础"的互补关系。

章节结构

• 开篇: 工程化 = 让代码跑进生产的手艺 ← 当前
• 1. Git 与版本控制: 原理 / 分支模型 / 合并策略 / 进阶命令
• 2. 测试工程: 测试金字塔 / 单元/集成/契约/E2E / mock / flaky 治理
• 3. CI/CD 与发布工程: 管线 / 镜像 / 蓝绿金丝雀 / IaC
• 4. 性能工程: profiling / 火焰图 / 缓存与批处理方法论
• 5. 应用安全: OWASP Top 10 / 认证授权 / 数据安全 / 供应链
• 6. 代码质量: 重构 / code review / 复杂度治理 / DDD 落地
• 7. 可观测性实操: metrics/logs/traces 打点 / OpenTelemetry / SLO
• 8. GitHub Actions 实战: workflow / expression / 缓存 / 矩阵 / reusable / 自托管
• 9. 云原生发布与 GitOps: K8s 应用 / Helm / ArgoCD / Flux / 服务网格
• 10. SRE 工程: 错误预算 / 容量 / 变更 / 事件响应 / 生产就绪

与其余各部分的接口表

这轴不是什么

• 不是重复原理章节（不重讲 B+树 / TCP / 哈希）。它假设你已经会，讲的是怎么用、怎么落地、怎么诊断。
• 不是某一门语言的教程（不教 Go 语法）。例子用 Go/Python/TS 等，但方法通用。
• 不是工程管理/软技能（不谈绩效、团队协作）。
• 不是某一家云厂商/单一平台的完整文档（GitHub Actions / K8s 为实例，但方法论通用）。

阅读路径

• 1-5 年工程师：§1 Git → §2 测试 → §3 CI/CD → §8 GitHub Actions → §5 应用安全（先建立规范直觉）
• 5-15 年工程师：§4 性能 → §6 代码质量 → §7 可观测性 → §9 GitOps → §10 SRE（深入到方法学）
• 想横通：按 Git → 测试 → CI/CD → Actions → 发布/GitOps → 可观测 → 性能 → 安全 → 重构 → SRE 的交付闭环顺序走

下一篇: 1. Git 与版本控制: 原理 / 分支模型 / 合并策略 / 进阶命令.

1. Git 与版本控制: 原理 / 分支模型 / 合并策略 / 进阶命令

TL;DR

Git 是工程师每天用最多、却最容易被"记命令"蒙混过的工具。理解 Git 的底层模型（内容寻址 DAG）后，几乎所有"诡异行为"都能推理出来，而不是靠背 git reset --hard。这一章讲透：

1. 对象模型：blob / tree / commit / tag 都是什么，Git 为什么是"内容寻址存储"。
2. 引用与 HEAD：branch / tag / HEAD 的真相，detached HEAD 是什么。
3. 暂存区与工作区：add/commit/checkout/reset 到底在动什么。
4. 分支模型：GitFlow / GitHub Flow / Trunk-Based 对比，怎么选。
5. 合并与变基：merge vs rebase vs cherry-pick，冲突解决。
6. 回滚与恢复：reset 三种模式、revert、reflog 救命。
7. 团队协作：pull request / 保护分支 / 语义化提交。

读完应能：不慌任何 Git 场景——合并冲突、误删、改错分支、把 WIP 弄丢、多分支拉错。

一、Git 的对象模型（一切的根）

1.1 四个对象类型

1.2 内容寻址

所有对象都用 SHA-1/SHA-256 哈希（内容哈希）作为地址。同样的内容永远得到同样的哈希——这是 Git 一切特性（去重、快照、不可变）的根。

commit  (哈希 = f(内容))
  ├─→ tree      (整个目录快照)
  │     ├─→ blob "main.go"     (文件内容)
  │     └─→ tree "pkg/"
  └─→ parent commit (父提交, 可多个 = merge)

1.3 为什么 Git 快

• 快照而非 diff：每个 commit 存整棵 tree，但 blob 按内容去重——没改的文件复用同一 blob 哈希，只存一次。
• 不可变：commit 生成后内容不变，新提交只新增。这保证历史可信任、可审计。

二、引用、HEAD 与三区

2.1 三区模型

工作区  --git add-->  暂存区  --git commit-->  仓库
  ↑                     ↑                        ↑
git checkout          git reset (mixed)       git reset --hard

2.2 引用（refs）与 HEAD

• branch 是一个指向 commit 的指针（.git/refs/heads/xxx）。
• HEAD 是一个特殊指针，指向"当前在哪个分支/commit"。
• 分支不是"装提交的容器"，只是会移动的指针——commit 本身在全球共享的 DAG 里。

2.3 detached HEAD

当 HEAD 不指向任何分支（git checkout <commit>）时进入 detached 状态：你可以在任何 commit 上工作，但新提交不挂在任何分支名下，切走就可能"丢"（其实 reflog 里还在）。

三、分支模型：三种主流

3.1 GitFlow（经典但重）

master ───────────────────────────────
         \                    /
          \ develop ─────────/──────
                \       /
                 \ feature

• master 只接受 release；develop 是集成分支；feature/release/hotfix 围绕它。
• 适用：固定发布周期、版本化产品（传统企业）。
• 问题：分支多、合并复杂，对持续发布偏重。

3.2 GitHub Flow（轻量主流）

• 只有 main，永远可部署；每个改动开短命分支 → PR → 合并回 main。
• 适用：持续交付的互联网产品（主流现代团队）。
• 特点：PR 即审核 + CI + 自动部署。

3.3 Trunk-Based（极致 CI）

• 所有人直接往 main 提交（或短命分支 < 1 天），靠 feature flag 控制上线。
• 适用：强 CI/CD、Google/Netflix 风格、高频发布。
• 特点：集成冲突最少、但要求测试覆盖与自动化极强。

四、合并策略：merge / rebase / cherry-pick

4.1 merge（保留历史分叉）

git switch main && git merge feature

产生一个 merge commit，历史保留两分支的真实形状。历史忠实但分叉多。

4.2 rebase（线性化历史）

git switch feature && git rebase main

把 feature 的提交"搬到" main 顶端重新应用，产生线性历史。

4.3 cherry-pick（挑单个提交）

git cherry-pick <commit-hash>

把别的分支上的单个提交应用到当前分支。用于热修复、挑某个修复进 release。

4.4 冲突解决

冲突标记：<<<<<<< HEAD / 你的代码 / ======= / 对方的代码 / >>>>>>> branch。

git merge main          # 报冲突
# 编辑文件解决冲突 → 删除冲突标记
git add 文件
git commit              # merge 场景：直接 commit 完成

五、回滚与恢复：reset / revert / reflog

5.1 reset 三模式

git reset --soft  <commit>   # 只移 HEAD, 暂存区和工作区不动
git reset        <commit>   # mixed: 移 HEAD + 清暂存区, 工作区不动（默认）
git reset --hard <commit>   # 全清: 工作区也丢弃改动 ⚠️危险

5.2 revert（安全回滚，推荐用于已推送）

git revert <commit>

产生一个"反向提交"，不改历史，只是加一个新提交抵消那个提交的改动。适合已 push / 公共分支，因为不动历史，别人 pull 无冲突。

5.3 reflog（救命日志）

git reflog     # 列出 HEAD 移动的全部记录（含被删的分支/commit）
git reflog --all
git reset --hard HEAD@{5}   # 回到 5 步前的状态

六、团队协作实践

6.1 Pull Request 流程（GitHub Flow 标配）

feature 分支 → git push origin feature
→ 开 PR → CI 跑测试 → code review → 合并（squash / merge / rebase-merge）

三种合并方式：

6.2 保护分支（protected branch）

main 应设置：不允许直接 push、必须有 PR + 至少 1 人 approve、CI 必须通过、线性历史。这是团队的"最后防线"。

6.3 语义化提交（Conventional Commits）

feat(api): 新增用户查询接口
fix(cache): 修复 key 过期竞态
docs(readme): 更新部署说明
refactor(db): 拆分连接池

feat/fix 直接驱动 changelog 和语义化版本（semver）：feat → minor，fix → patch，BREAKING CHANGE → major。让提交消息变成机器可读的元数据。

6.4 子模块与 monorepo

• monorepo：全代码一个仓（Google/字节模式），靠 build system 隔离，PR 全局可见。
• submodule：嵌套仓库，但要小心（子模块不自动跟随父仓 checkout）。
• 现在更多团队用 workspace（pnpm/yarn workspaces、Go workspaces）替代 submodule。

七、常用命令速查

# 诊断
git status / git log --oneline --graph / git diff / git diff --staged
git branch -a / git remote -v

# 提交
git add -p           # 交互式分块暂存
git commit --amend   # 修改上一次提交消息（未推送时）
git stash / git stash pop    # 暂存 WIP
git stash list / git stash drop

# 分支
git switch -c feature    # 建并切换
git branch -d feature    # 删已合并分支
git fetch --prune        # 清理远端已删分支

# 撤销
git restore 文件         # 丢弃工作区改动（替代 checkout -- 文件）
git restore --staged 文件 # 取消暂存
git reset --hard HEAD    # 丢弃全部未提交（小心）

# 高级
git blame 文件           # 谁改的
git log -S 字符串        # 找哪次提交加了/删了该字符串
git bisect start         # 二分找引入 bug 的提交
git clean -fd            # 清理未跟踪文件（小心）
git filter-repo          # 重写历史（慎用）

八、实战场景

8.1 场景 1：改错了分支

# 在 main 上改了 feature 的代码，还没提交
git stash                          # 暂存改动
git switch feature
git stash pop                      # 恢复改动到 feature

8.2 场景 2：提交到 main 想挪到 feature

# 已有 commit 在 main
git switch -c feature              # 分支带上当前状态
git switch main
git reset --hard HEAD~1            # main 后退一提交（本地）
git push origin main --force-with-lease   # 覆盖远端（注意：只对没共享的分支）

8.3 场景 3：误删分支 / 丢失提交

git reflog          # 找到那个提交的哈希
git branch -c <哈希> recovered   # 从哈希建回分支

8.4 场景 4：WIP 弄丢

git fsck --lost-found        # 找 dangling 对象
# 或 reflog 找 stash 记录
git stash list && git stash apply stash@{0}

九、结束 + 速查表

下一篇: 2. 测试工程: 测试金字塔 / 单元/集成/契约/E2E / mock / flaky 治理.

2. 测试工程: 测试金字塔 / 单元/集成/契约/E2E / mock / flaky 治理

TL;DR

测试不是"写几个 assert"，而是一套控制回归风险的系统。这一章把测试从"会写"提升到"会设计"：知道测什么、在哪一层测、用什么替身、怎么让测试不 flaky、怎么用覆盖率做决策（而不是当指标）。

读完应能：

1. 说清测试金字塔为什么是对的，以及它不适用时的例外。
2. 区分单元 / 集成 / 契约 / E2E 四种测试的职责与成本。
3. 正确使用 mock/stub/fake/spy，知道"过度 mock"的病。
4. 诊断并治理 flaky 测试。
5. 用测试覆盖率的正确用法辅助重构决策。

一、测试金字塔

1.1 分层与成本

        / E2E \           数量少（几十）
       /  契约  \         数量中（几百）
      /   集成    \       数量多（几千）
     /    单元      \     数量最多（几万）
    /________________\

原则：越往上数量越少。金字塔的几何形状就是最优成本结构——把多数测试放在快而稳定的底部。

1.2 反模式

• 倒金字塔：全 E2E，慢、flaky、难定位 → 是测试最贵且最没用的形态。
• 冰淇淋筒：上面 E2E 多、中间少、底部 mock 一堆 → 单元测试全是 mock，集成空缺。
• 无测试：靠手动 QA → 回归全靠人肉，无法持续发布。

1.3 覆盖策略（Test Pyramid 的落地）

每个功能改动的理想测试分布（Google 实践）：

单元: 70-80%   — 覆盖所有分支/错误路径（快、密集）
集成: 15-20%   — 覆盖模块组合、真实 DB/依赖
E2E : 2-5%     — 关键 happy path 冒烟
契约: 按服务边界补 — 微服务间接口防破坏

二、四种测试的职责

2.1 单元测试（Unit）

• 测一个函数/类的单一行为，不跨模块、不碰 IO。
• 目标：逻辑正确、边界处理、错误路径、性能敏感函数。
• 关键：测行为不测实现（改实现不该破坏测试）。

// Go 单元测试示例
func TestCalculateTotal(t *testing.T) {
    items := []Item{{Price: 10, Qty: 2}, {Price: 5, Qty: 1}}
    got := CalculateTotal(items)
    if got != 25 {
        t.Errorf("got %v want 25", got)
    }
}

# Python 单元测试
def test_calculate_total():
    assert calculate_total([("a", 10, 2), ("b", 5, 1)]) == 25

def test_empty_cart():
    assert calculate_total([]) == 0

2.2 集成测试（Integration）

• 测模块之间的真实协作，包括真实 DB、真实网络、真实文件系统。
• 捕获的问题：API 签名不匹配、类型/编码转换、事务边界、并发竞态。
• 手段：真实依赖（Testcontainers 起真实 DB/redis）+ 少用 mock。

# 用 Testcontainers 起真实 Postgres
def test_user_persistence():
    with Testcontainers("postgres:16").running() as pg:
        repo = UserRepo(pg.get_connection_url())
        repo.create(User("alice"))
        assert repo.find("alice").name == "alice"

2.3 契约测试（Contract）

• 微服务间：消费方（consumer）与提供方（provider）各持一份契约，独立验证。
• Pact 思路：consumer 生成契约（它期望的请求/响应），provider 验证自己满足契约。
• 价值：两端独立部署也不会悄悄破坏接口——比 E2E 快得多，且精准定位是哪端破坏。

消费者 (consumer)                     提供者 (provider)
   └─ 期望: GET /user/1 → {id:1}       └─ 验证: 我确实返回 {id:1}
        生成契约文件 pact.json ──────→  provider 测试跑契约

2.4 E2E 测试

• 模拟真实用户完整路径：登录 → 操作 → 结果，跑在完整部署上（浏览器/真实 API）。
• 工具：Playwright / Cypress / Selenium。
• 定位：冒烟（关键路径别挂）+ 少量核心流程，不是全覆盖。

// Playwright E2E
import { test, expect } from '@playwright/test';

test('用户能下单', async ({ page }) => {
  await page.goto('/');
  await page.getByText('添加购物车').click();
  await page.getByRole('button', { name: '结算' }).click();
  await expect(page).toHaveURL(/\/checkout/);
  await expect(page.getByText('订单成功')).toBeVisible();
});

三、测试替身（Test Double）：mock / stub / fake / spy

3.1 四种替身

3.2 过度 mock 的问题

# ❌ 过度 mock：测试的是 mock 自己，不是代码
def test_order(mocker):
    db = mocker.patch("app.db.query")      # mock 了 DB
    cache = mocker.patch("app.cache.get")  # mock 了缓存
    notify = mocker.patch("app.notify")    # mock 了通知
    # ... 三个全 mock 后，测的其实是胶水，业务逻辑没测到

# ✅ 更真实：保留逻辑层，mock 只在 IO 边界
def test_order_flow(test_db):
    repo = UserRepo(test_db)              # 真实 DB（fakeredis / testcontainers）
    result = place_order(repo, cart)
    assert result.status == "paid"

判断标准：如果 mock 掉的东西越多、断言越细，测试就越脆。只在"边界 IO"（外部服务、时间、随机）处 mock，业务逻辑用真实实现。

3.3 依赖注入让测试容易

# 设计上支持替换依赖
def send_notification(sender: Notifier, msg: str):   # 传入接口
    sender.push(msg)

# 测试时传 Fake
class FakeNotifier(Notifier):
    def __init__(self): self.sent = []
    def push(self, msg): self.sent.append(msg)

def test_send():
    fake = FakeNotifier()
    send_notification(fake, "hi")
    assert fake.sent == ["hi"]

四、Flaky 测试治理

4.1 什么是 flaky

同一份代码，跑两次结果不同——一次过一次挂。Flaky 是持续交付的最大敌人：它让 CI 信号不可信，开发开始忽略红。

4.2 常见根因

4.3 反例：sleep 是罪魁

# ❌ sleep 猜测时序
response = api.start_async_job()
time.sleep(5)                     # 5 秒后应该完成了
assert response.done

# ✅ 显式等待直到条件满足
def wait_until(predicate, timeout=10):
    deadline = time.monotonic() + timeout
    while time.monotonic() < deadline:
        if predicate(): return True
        time.sleep(0.1)
    raise TimeoutError()

assert wait_until(lambda: api.job_status(job_id).done)

4.4 治理流程

1. 复现：用 --count=100 反复跑（pytest: --count, go test: -count=100）
2. 隔离：找到 flaky 的最小复现
3. 定位：加日志 / 用 go test -race / pytest-timeout
4. 修复：消除根因（上面表）
5. 防再发：把修复用例留成回归；加 CI 的 retry 是最后手段，不是解法

五、覆盖率：正确使用

5.1 覆盖率不是目标

• 覆盖率高 ≠ 测试好：可以 100% 覆盖而全是无效断言。
• 但覆盖率低几乎总是坏（除非是新代码区）。
• 正确用法：辅助发现"没测的路径"，而不是 KPI。

5.2 有用的度量

5.3 覆盖率的正确决策流

写代码 → 写测试 → 看 diff coverage
  ↓ 低分支覆盖
  → 补分支：错误路径 / 边界 / 空值
  ↓ 高覆盖但测试很脆
  → 检查：是否在测实现细节？是否需要重构测试？

六、测试策略落地（团队层面）

6.1 CI 里的测试分层执行

PR 阶段（快，必跑）:
  - 单元测试（毫秒级，全部跑）
  - Lint + 类型检查
  - 变更文件的 diff coverage 检查

合并后（慢，异步）:
  - 集成测试（Testcontainers）
  - 契约测试（Pact）
  - E2E 冒烟（部署到 staging）

6.2 测试金字塔的健康检查

• 单元测试跑 < 1 分钟 → 正常；> 5 分钟 → 该拆测试或并行。
• E2E 占总量 > 5% → 危险，该下移。
• 大量测试需要 mock 数据库 → 架构耦合问题。
• 测试常"修一下就好"（改断言不测逻辑）→ 测试在测实现，不是行为。

6.3 先写测试 vs 后写测试

• TDD（先写失败测试）：适合纯逻辑、算法、规则引擎。
• 后写测试：适合探索性代码、UI、集成层。
• 关键不是"谁先"，而是每段代码离开手前都要有测试覆盖。

七、结束 + 速查表

下一篇: 3. CI/CD 与发布工程: 管线 / 镜像 / 蓝绿金丝雀 / IaC.

3. CI/CD 与发布工程: 管线 / 镜像 / 蓝绿金丝雀 / IaC

TL;DR

CI/CD 是把代码从提交到生产的一条自动化流水线。CI（持续集成）保证每次提交都能构建+测试通过；CD（持续交付/部署）把通过的产品可靠地发布出去。这一章讲的不是某个平台（GitHub Actions/GitLab CI/Jenkins）的教程，而是发布工程的通用模型——管线怎么设计、产物怎么管理、发布怎么无痛、基础设施怎么管理。

读完应能：

1. 画出 CI/CD 管线的完整阶段（提交 → 构建 → 测试 → 产物 → 部署 → 验证 → 回滚）。
2. 理解镜像/不可变产物与"代码即配置"的区别。
3. 讲清蓝绿、金丝雀、滚动、重建四种部署策略的取舍。
4. 知道 IaC（Infrastructure as Code）怎么做、为什么必须。
5. 设计一个"小步快速失败"的发布流程。

一、CI/CD 是什么

1.1 CI：持续集成

每次提交（或 PR 合并）自动执行：

提交 → 检出 → 构建 → 单元测试 → Lint → 集成测试 → 产物 → 报告

目的：尽快暴露"集成问题"。核心指标：合并到主干的 commit 到 CI 变绿的时间，应该以分钟计。

1.2 CD：持续交付/部署

• 持续交付：通过 CI 的产物随时可以发布到生产（但发布是人为按钮）。
• 持续部署：通过所有关卡后自动发布到生产。

区别就是"要不要人按发布键"。

1.3 为什么重要

• 发布频率越高、每次改动越小 → 故障定位越容易 → 回滚越简单。
• 反例：半年发一次大版本，一次带 500 个 commit，出事无法定位。

二、管线设计：一个标准流水线

┌────────────────────────────────────────────────────────────┐
│ Stage 1: 检出 + 依赖                                       │
│   git checkout; install deps (go mod / npm ci / pip)       │
├────────────────────────────────────────────────────────────┤
│ Stage 2: 静态检查                                          │
│   lint / 类型检查 / 格式 / 依赖漏洞扫描 (govulncheck/npm audit)│
├────────────────────────────────────────────────────────────┤
│ Stage 3: 测试（快）                                        │
│   单元测试 + 覆盖率（diff coverage 门槛）                    │
├────────────────────────────────────────────────────────────┤
│ Stage 4: 构建产物（不可变）                                 │
│   编译 → 生成镜像/二进制 → 打上唯一 tag (git sha) → push    │
├────────────────────────────────────────────────────────────┤
│ Stage 5: 测试（慢，可并行）                                 │
│   集成测试 / 契约测试 / E2E 冒烟                            │
├────────────────────────────────────────────────────────────┤
│ Stage 6: 部署到 staging                                    │
│   预览环境 → 人工/自动验收                                  │
├────────────────────────────────────────────────────────────┤
│ Stage 7: 发布到生产                                         │
│   蓝绿 / 金丝雀 / 滚动 → 健康检查 → 观察指标 → 完成          │
│   失败 → 自动回滚                                          │
└────────────────────────────────────────────────────────────┘

关键设计原则：

• 每一 stage 的输入是上一 stage 的产物，不是重新构建（保证测试的就是要部署的）。
• 产物不可变 + 唯一可追溯（tag = git sha + 时间），"代码可复现到任意发布版本"。
• 快失败前置：慢的测试永远排在快的后面。

三、产物与镜像

3.1 不可变产物（Immutable Artifact）

"你测试的东西，就是你要发布的东西。一旦构建，永不改变。"

• 每次构建生成唯一可追溯产物（app-<gitsha>-<timestamp>）。
• 构建一次，测试、部署、回滚都复用同一产物。
• 反例：生产上重新 go build / npm install（每次结果可能不同）→ 不可复现。

3.2 容器镜像

• 镜像 = 运行环境 + 代码 + 依赖的快照，跨环境一致（这是为什么 Docker 火）。
• 生产部署 = 拉镜像 → 跑容器，不再有"本地能跑线上不能跑"。

# 多阶段构建：build 阶段产二进制，run 阶段只带二进制（小镜像）
FROM golang:1.22 AS build
WORKDIR /app
COPY go.mod go.sum ./
RUN go mod download
COPY . .
RUN CGO_ENABLED=0 go build -o app .

FROM gcr.io/distroless/static
COPY --from=build /app/app /app
EXPOSE 8080
ENTRYPOINT ["/app"]

3.3 镜像仓库与版本

app:v1.2.3                          # 语义化版本
app:git-abc1234                     # git sha（唯一可追溯）
app:latest                          # ❌ 避免：不可追溯，别用生产

四、部署策略

4.1 四种主流

滚动 (Rolling):       逐个替换旧实例 → 新实例，不停机
蓝绿 (Blue-Green):    两套环境 (blue 旧, green 新)，切流量到 green
金丝雀 (Canary):      先给 5-10% 流量，观察没问题再全量
重建 (Recreate):      先停旧的再起新的（有停机窗口）

4.2 对比表

4.3 蓝绿 vs 金丝雀实战

蓝绿（K8s 手动版）：

blue (v1)  ← 生产流量
green (v2) ← 新部署，验证健康
流量切换: 把 LB 指向 green（秒级）
异常: 切回 blue（秒级回滚）

金丝雀（K8s 渐进式）：

canary (v2) 接 5% 流量 → 观察错误率/延迟
指标健康 → 升到 50% → 100%
指标异常 → 自动切回 (自动回滚)

4.4 K8s 部署示例

apiVersion: apps/v1
kind: Deployment
metadata:
  name: app
spec:
  replicas: 3
  strategy:
    type: RollingUpdate
    rollingUpdate:
      maxUnavailable: 1        # 最多同时不可用 1 个
      maxSurge: 1              # 最多多起 1 个
  selector: { matchLabels: { app: app } }
  template:
    metadata: { labels: { app: app } }
    spec:
      containers:
      - name: app
        image: registry/app:git-abc1234   # 不可变 tag
        readinessProbe: { httpGet: { path: /healthz, port: 8080 } }

五、IaC（Infrastructure as Code）

5.1 为什么必须

手工配置服务器 = 状态不可知、不可复现、漂移。IaC 把基础设施当代码管理：版本控制、可 review、可回滚、可复现。

5.2 两派

声明式是主流：terraform plan 显示 diff，apply 收敛到目标状态。

5.3 Terraform 示例

# main.tf
terraform {
  required_providers {
    aws = { source = "hashicorp/aws" }
  }
}

resource "aws_instance" "web" {
  ami           = "ami-1234"
  instance_type = "t3.micro"
  tags = { Name = "web-prod" }
}

terraform init    # 初始化
terraform plan    # 显示将要做什么（diff）
terraform apply   # 执行
terraform destroy # 删除

5.4 K8s 的 IaC（GitOps）

GitOps = git 是唯一的真相源，集群状态持续收敛到 git 里的声明：

git (期望状态) → 拉取 → 对比集群 → 应用差异 → 汇报

工具：ArgoCD / Flux。价值：代码 review 即基础设施 review；回滚 = git revert；审计 = git log。

六、发布与回滚流程设计

6.1 发布清单（Checklist）

一个可靠的发布流程应有：

[ ] 测试全绿（单元/集成/契约/E2E 冒烟）
[ ] 产物不可变 + 可追溯（git sha tag）
[ ] 数据库迁移安全（向前兼容 / 可回滚）
[ ] 配置项有默认值且向后兼容
[ ] 健康检查 / 就绪探针就位
[ ] 监控指标有基线（错误率/延迟/P95）
[ ] 回滚计划写好了（不是事故时才想）
[ ] 金丝雀/蓝绿的流量切换步骤

6.2 数据库迁移（发布最大风险）

发布中最常"卡住回滚"的是 DB schema 变更。原则：

• 向前兼容：新代码能读旧 schema，旧代码也能读新 schema（兼容窗口）。
• 分两步：先加列/放宽约束（兼容）→ 部署新代码 → 再删旧列（不兼容改动）。
• 工具：Flyway / Liquibase / golang-migrate，迁移文件进版本控制。

不兼容改动必须拆分：
Step1: 加新列 (兼容)  → 部署新代码
Step2: 迁移数据
Step3: 删旧列 (不兼容, 代码已不用)

6.3 回滚策略

发布后观察期 (10-30 分钟):
  - 错误率 / 延迟 / 5xx 超阈值 → 触发回滚
回滚方式:
  - 金丝雀/蓝绿: 切回旧版本 (秒级)
  - 滚动: 重新部署旧镜像 (分钟级)
  - DB: 若 schema 有破坏性变更, 需要先回滚迁移 (所以迁移要可逆)

七、CI/CD 平台示例（GitHub Actions）

name: CI
on:
  pull_request:
  push: { branches: [main] }

jobs:
  test:
    runs-on: ubuntu-latest
    steps:
      - uses: actions/checkout@v4
      - uses: actions/setup-go@v5
        with: { go-version: '1.22' }
      - run: go build ./...
      - run: go test ./... -race -count=1
      - run: golangci-lint run

  deploy:
    if: github.ref == 'refs/heads/main'
    needs: test
    runs-on: ubuntu-latest
    steps:
      - uses: actions/checkout@v4
      - name: Build & push image
        run: |
          docker build -t registry/app:git-${{ github.sha }} .
          docker push registry/app:git-${{ github.sha }}
      - name: Deploy
        run: kubectl set image deployment/app app=registry/app:git-${{ github.sha }}

八、结束 + 速查表

下一篇: 4. 性能工程: profiling / 火焰图 / 缓存与批处理方法论.

4. 性能工程: profiling / 火焰图 / 缓存与批处理方法论

TL;DR

性能优化最怕两件事：不看证据瞎猜，和为了优化而优化。这一章给一套科学的方法论——先测量、再定位、后优化、最后验证，并给出实际工具（pprof / perf / async-profiler / flamegraph）与常见优化手段（缓存、批处理、索引、并发）的适用场景。

读完应能：

1. 用"测量 → 定位 → 优化 → 验证"四步走完一次性能优化，不靠猜。
2. 读懂火焰图，知道 CPU / 内存 / IO / 锁四种瓶颈怎么看。
3. 判断该用缓存 / 批处理 / 索引 / 并发哪个，而不是全上。
4. 识别最常见的性能反模式（N+1 查询、循环里做 IO、没缓存重复计算）。

一、性能工程的科学方法

1.1 四步循环

1. 测量    —— 量化现状（基线）：latency / throughput / 资源利用率
2. 定位    —— 找到瓶颈（profiling）：是 CPU? 内存? IO? 锁? 网络?
3. 优化    —— 针对根因下手（改算法/缓存/批处理/并发/索引）
4. 验证    —— 对比优化前后，确认有效且没引入新问题

1.2 关键度量

1.3 P50 vs P95 vs P99

• 均值会骗人（99% 快 1ms，1% 慢 10s，均值还是 1.1ms）。
• P99 代表"最差用户体验"——很多"系统挂了"其实是 P99 爆表。
• 优化目标常是"P95/P99"，不是均值。

二、定位瓶颈：四大类

2.1 CPU 瓶颈

现象：CPU 100%、吞吐上不去、延迟随负载线性涨。

手段：CPU profiler（采样），找热函数。

pprof 火焰图
  顶部 = 实际执行中的函数（宽 = 占比高）
  向下 = 调用栈
  最宽的那条 = 热点

工具：

• Go: pprof（net/http/pprof 或 benchmark）
• C/C++/Rust: perf record + perf report
• JVM: async-profiler + flamegraph
• Python: cProfile / py-spy（生产无侵入采样）

// Go: 开启 pprof 端点
import _ "net/http/pprof"
// 然后: go tool pprof http://localhost:6060/debug/pprof/profile

2.2 内存瓶颈

现象：内存飙高、GC 频繁、OOM、Swap。

手段：内存 profiler + heap 分析。

Go:  go tool pprof -inuse_space   # 当前驻留内存
     go tool pprof -alloc_space   # 累计分配（找分配热点）
JVM: jmap + MAT / async-profiler alloc

常见内存反模式：

• 大对象反复创建（没复用 buffer）
• 切片/数组预分配不足导致反复扩容
• 缓存无上限（LRU 缺失）
• 逃逸分析失败导致频繁堆分配

2.3 IO 瓶颈（磁盘/网络）

现象：CPU 不高但慢、io wait 高、吞吐低。

手段：IO profiler + 观察系统层。

iostat -x 1        # 磁盘利用率 / await / svctm
pidstat -d 1       # 每进程 IO
sar -n DEV 1       # 网络吞吐

判断：await 高 = 磁盘慢；%util 100% = 磁盘饱和。

2.4 锁 / 并发瓶颈

现象：核多但用不满、延迟随核数先降后升（争用）、CPU 有 idle 但吞吐低。

手段：锁 / 阻塞 profiler。

Go:  pprof mutex / block profile
JVM: async-profiler -e wall 看阻塞线程

判断：火焰图里很多 sync.Mutex.Lock / parked → 锁争用。

三、读懂火焰图

3.1 火焰图怎么读

      ____________
    __| funcC      |__      ← 最宽的横条 = 占 CPU 最多
  _|__| funcB      |___
 _|___| funcA      |______
|  main()          |       ← 栈底 = 入口

• 横轴 = 采样时间占比（宽度），纵轴 = 调用栈深度。
• 最宽处 = 瓶颈。顺最宽路径往上，就是"为什么这么慢"的根因链。
• 看自己代码而不是库函数——如果最宽是 memcpy/json.Marshal，说明热点在被调用的库上。

3.2 四种典型形态

3.3 生成火焰图

# Go
go tool pprof -raw http://localhost:6060/debug/pprof/profile > cpu.raw
go tool pprof -proto http://localhost:6060/debug/pprof/profile > cpu.pb.gz
# 用 https://speedscope.app 或 flamegraph.pl 可视化

四、常见性能反模式（先自查这些）

五、优化手段：什么时候用哪个

5.1 缓存（Cache）

适用：同一结果被反复读取、数据变化不频繁、读远多于写。

代价：一致性（stale）、失效复杂度、内存占用。

关键决策：

• 本地缓存（单进程，LRU）vs 分布式缓存（Redis，跨节点）
• 失效：TTL / 主动失效 / 版本号
• 缓存一致性：cache-aside / write-through（见系统设计 §cache）

// Go: 简单 LRU 缓存（sync.Map 或 bigcache）
var cache = make(map[string]*Entry)  // 生产用 lru 库
func Get(key string) *Entry {
    if e, ok := cache[key]; ok { return e }  // hit
    e := loadFromDB(key)                      // miss → 加载
    cache[key] = e
    return e
}

5.2 批处理（Batching）

适用：大量小操作（网络请求、DB 写入、消息发送）、往返延迟占主导。

代价：延迟增加（凑批要等）、错误影响面变大。

# ❌ 逐个发送（N 次网络往返）
for msg in messages:
    send(msg)

# ✅ 批量（1 次往返）
send_batch(messages)

5.3 索引（数据库）

适用：查询慢、全表扫描。

关键：

• WHERE/JOIN/ORDER BY 用到的列建索引
• 覆盖索引（列都包含）避免回表
• 复合索引的列序（最左前缀）
• 见数据库 §indexing

5.4 并发（Concurrency）

适用：多个独立任务可并行、有闲置资源、IO 等待为主。

代价：锁争用、调度开销、复杂度。

// Go: 扇出 + WaitGroup
var wg sync.WaitGroup
results := make([]Result, len(urls))
for i, u := range urls {
    wg.Add(1)
    go func(i int, u string) {
        defer wg.Done()
        results[i] = fetch(u)
    }(i, u)
}
wg.Wait()

5.5 算法/数据结构

• 从 O(n²) 改 O(n log n)（哈希表替代线性查找）
• 见 DSA 全部——这是"性能工程"的底层工具箱。

六、性能优化的优先级判断

6.1 80/20 法则

• 通常 20% 的代码占 80% 的时间。只优化 hot path，别优化冷路径。
• 先 profile 找到那 20%，再动手。

6.2 先确认瓶颈在"该层"吗

延迟高 → 是应用慢? 网络慢? DB 慢? 还是依赖服务慢?
  - 应用慢 → 上 profiler
  - DB 慢 → EXPLAIN + 索引
  - 网络慢 → 测 RTT、看是不是跨区域
  - 依赖慢 → 看上游 P99, 加超时熔断

6.3 优化后验证

# 优化前后对比 (Go benchmark)
go test -bench=. -benchmem ./...
# 观察 P99 变化: 从 500ms → 80ms, 就是有效

七、结束 + 速查表

下一篇: 5. 应用安全: OWASP Top 10 / 认证授权 / 数据安全 / 供应链.

5. 应用安全: OWASP Top 10 / 认证授权 / 数据安全 / 供应链

TL;DR

密码学部分（第十部分）讲的是"加密算法怎么工作"；这一章讲应用层安全——你的 Web 服务怎么被攻击、怎么防御。攻击不是靠破解 AES，而是靠应用逻辑漏洞（注入、越权、逻辑绕过）。这一章以 OWASP Top 10 为主线，覆盖最常见攻击面 + 认证授权 + 数据安全 + 供应链安全。

读完应能：

1. 说清 OWASP Top 10 每一项的漏洞原理、攻击方式、防御手段。
2. 理解认证（你是谁）vs 授权（你能干嘛）的区别，会设计会话/JWT/角色权限。
3. 知道常见数据安全实践（加密/掩码/合规）。
4. 意识到底层依赖（供应链）也是攻击面。

一、威胁模型与信任边界

1.1 先想清楚"谁在攻击谁"

安全设计的第一步不是堆防护，而是威胁建模（Threat Modeling）：

信任边界 1: 用户 vs 公网         → 认证、输入校验
信任边界 2: 公网服务 vs 内部服务  → 内网隔离、mTLS
信任边界 3: 服务 vs 数据库        → 最小权限、加密连接
信任边界 4: 开发 vs 生产          → 密钥管理、环境隔离

每一条边界都要问：跨这条边界的数据/调用，怎么被滥用？

1.2 安全三原则

• 纵深防御（Defense in Depth）：不只一层防护，层层都设防。
• 最小权限（Least Privilege）：只给完成任务所需的最小权限。
• 默认安全（Secure by Default）：默认关闭，需要才开。

二、OWASP Top 10（核心）

2.1 总览

2.2 A03 注入：SQL 注入（最经典）

漏洞：把用户输入直接拼进 SQL。

# ❌ 危险：字符串拼接
query = f"SELECT * FROM users WHERE name = '{username}'"
# 输入: username = "admin' --" → 查询变成:
# SELECT * FROM users WHERE name = 'admin' --'
# 注掉后面所有条件 → 越权登录!

# ✅ 参数化查询
cursor.execute("SELECT * FROM users WHERE name = %s", (username,))

防御：永远用参数化查询/预编译语句，绝不用字符串拼接。ORM 通常默认参数化，但要小心 raw query。

2.3 A01 访问控制破坏：IDOR（越权）

漏洞：用户直接访问 GET /order/12345，没检查"这个订单是不是他的"。

# ❌ 只按 id 查，不校验归属
def get_order(order_id):
    return db.fetch("SELECT * FROM orders WHERE id = %s", (order_id,))

# ✅ 校验归属
def get_order(user_id, order_id):
    row = db.fetch("SELECT * FROM orders WHERE id = %s AND user_id = %s",
                   (order_id, user_id))
    if row is None: raise Forbidden()   # 不归属 → 拒绝
    return row

防御：服务端每次都必须校验资源归属，不能只靠前端隐藏。用不可枚举的 ID（UUID 而非自增）只是缓解，不是修复。

2.4 A02 加密失败（敏感数据保护）

• 传输：全站 HTTPS（TLS），绝不允许 HTTP 明文。
• 存储：
  • 密码 → 哈希（bcrypt/argon2/scrypt），绝不明文，绝不存可逆。
  • 信用卡/身份证 → 加密存储（AES-256）或 token 化。
  • 日志里不打敏感字段（手机号、身份证、token）。

# 密码必须哈希，绝不加密（不需要解密回来）
import hashlib, secrets
# 用 bcrypt/argon2, 别用裸 sha256（太快）
# from argon2 import PasswordHasher
# ph = PasswordHasher()
# ph.hash(password)          # 存这个
# ph.verify(hash, password)  # 校验

2.5 A10 SSRF（服务端请求伪造）

漏洞：用户控制的 URL 被服务端去请求。

# ❌ 用户能传 url 让服务端去访问
def fetch_image(url):
    return requests.get(url).content
# 攻击: url = "http://169.254.169.254/latest/meta-data/" → 访问云元数据(可能拿到密钥!)

防御：服务端不发用户可控 URL；若必须，白名单协议/域名、禁止内网 IP、过滤回环地址。

2.6 A06 易受攻击组件（供应链）

• 每个依赖库都可能有 CVE，依赖扫描是 CI 的一部分（govulncheck / npm audit / Dependabot）。
• 攻击载体：package-lock.json / go.sum 应锁定版本并签名校验。
• 不只是依赖：基础镜像（Docker base image）、Terraform 模块、NPM 包都是供应链。

三、认证与授权

3.1 认证（Authentication）vs 授权（Authorization）

认证: 你是谁?  → 登录/口令/SSO/MFA
授权: 你能做什么? → 角色/权限/策略

经典错误：只做了认证忘了授权 → "能登录 = 能访问一切"（IDOR 的根源）。

3.2 会话管理（Session）

• 登录成功后服务端生成 session（随机高熵 id），存服务端，客户端拿 cookie。
• 安全要点：
  • session id 用加密安全随机数（crypto/rand）
  • cookie 加 HttpOnly（防 XSS 读）、Secure（仅 HTTPS）、SameSite
  • session 过期 + 登出使失效

3.3 Token 方案（JWT）

JWT（JSON Web Token）= header.payload.signature，无状态（服务端不存）。

header:  {"alg": "HS256", "typ": "JWT"}
payload: {"sub": "user123", "role": "admin", "exp": 1700000000}
signature: HMAC-SHA256(header.payload, secret)

安全要点：

• alg 必须白名单（防 alg=none 绕过）
• secret 用强随机 + 环境变量/密钥管理，不进代码
• 必须校验 exp
• 放授权信息在 JWT 里要小心：改 role 后要能强制失效（因为无状态，无法吊销）

3.4 授权模型

# OPA 策略示例: 用户只能改自己的订单
allow {
  input.method == "PATCH"
  input.path == ["orders", order_id]
  order_id == input.user_id
}

3.5 会话固定 / 重放 / 爆破

• 爆破：限流 + 失败锁定 + 验证码。
• 会话固定：登录成功后轮换 session id。
• 重放：请求加时间戳/nonce，服务端校验。

四、常见 Web 攻击（补充 OWASP）

4.1 XSS（跨站脚本）

• 存储型/反射型/DOM 型；用户输入当 HTML/JS 执行。
• 防御：输出转义（html.escape）、CSP 头、HttpOnly cookie、输入过滤。

# ❌ 把用户评论直接插进 HTML
return f"<div>{comment}</div>"   # 用户输入 <script>alert(1)</script>

# ✅ 转义输出
import html
return f"<div>{html.escape(comment)}</div>"

4.2 CSRF（跨站请求伪造）

• 攻击者让受害者浏览器向你的站点发请求（带 cookie）。
• 防御：CSRF token、SameSite=Strict/Lax cookie、自定义 header。

4.3 开放重定向 / 点击劫持 / 文件上传

• 文件上传：校验 MIME + 扩展名 + 大小，存储隔离，禁执行目录。
• 点击劫持：X-Frame-Options: DENY / CSP frame-ancestors。

五、数据安全与合规

5.1 数据生命周期

采集 → 传输(加密) → 存储(加密) → 使用(最小权限) → 归档 → 删除(合规)

5.2 分类与脱敏

• 敏感数据（PII：手机号/身份证/邮箱）要有分类标记。
• 日志/测试环境脱敏（掩码 138****1234）。
• 备份同样加密。

5.3 合规（GDPR / 个保法）

• 数据最小化（只采集需要的）
• 用户有"被遗忘权"（删除请求）
• 跨境传输需评估
• 日志保留期限有上限

六、安全工程实践（落地）

6.1 密钥管理

• 绝不把密钥写进代码（硬编码是头号漏洞）。
• 用密钥管理服务：AWS Secrets Manager / HashiCorp Vault / K8s Secret。
• 环境变量分离 + 部署时注入。
• 密钥轮转 + 审计。

# ❌ 硬编码
DB_PASSWORD="abc123"

# ✅ 从环境/密钥管理读取
export DB_PASSWORD=$(vault read -field=value secret/db)

6.2 安全头（HTTP 层）

Strict-Transport-Security: max-age=31536000; includeSubDomains
Content-Security-Policy: default-src 'self'
X-Content-Type-Options: nosniff
X-Frame-Options: DENY
Referrer-Policy: no-referrer

6.3 依赖与 CI 安全

CI 步骤:
  - 依赖漏洞扫描 (govulncheck / npm audit / trivy)
  - 镜像扫描 (trivy / grype)
  - SAST 静态分析 (semgrep / gosec)
  - 密钥扫描 (git-secrets / gitleaks)
  - 依赖锁定 + 签名校验

6.4 安全清单（上线前）

[ ] 全部用 HTTPS
[ ] 参数化查询（无字符串拼接 SQL）
[ ] 所有资源访问校验归属（防 IDOR）
[ ] 密码 bcrypt/argon2 哈希
[ ] 会话: HttpOnly/Secure/SameSite cookie
[ ] 依赖扫描通过
[ ] 密钥在密钥管理, 不在代码
[ ] 安全头配好
[ ] 日志不记敏感字段
[ ] 权限最小化（DB/服务/云）

七、与第十部分密码学的衔接

应用安全是密码学的工程落地；密码学给应用安全提供原语。

八、结束 + 速查表

下一篇: 6. 代码质量: 重构 / code review / 复杂度治理 / DDD 落地.

6. 代码质量: 重构 / code review / 复杂度治理 / DDD 落地

TL;DR

代码质量决定的是"软件 5 年后还能不能改"。这一章把"好代码"从玄学变成可操作的方法：重构是有纪律的语义等价变换，code review 是质量门禁而非走过场，复杂度治理让代码不被技术债压垮，DDD 让复杂业务领域保持清晰。

读完应能：

1. 用"坏味道清单"发现代码问题，用安全的重构手法（保持行为不变）改进。
2. 知道 code review 该看什么、怎么给反馈、怎么不让人难受。
3. 用量化手段（圈复杂度等）治理复杂度，而不是靠感觉。
4. 理解 DDD 的核心战术（实体/值对象/聚合/领域服务）何时用。

一、什么是"好代码"

1.1 质量的本质：可修改性

代码质量 = 改它需要多少成本 + 多少风险。好代码 = 低成本、低风险地满足新需求。

不是"优雅""花哨"，而是：

• 可读：5 分钟后/5 个月后/别人能看懂。
• 可测：能写测试（依赖注入、边界清晰）。
• 可改：加功能不破坏其他部分（低耦合）。
• 可维护：出问题能快速定位。

1.2 四个质量维度

二、代码坏味道清单（先发现）

2.1 命名与结构

• 魔法数字/字符串：if (x > 86400) → 提取常量 ONE_DAY_SECONDS。
• 烂命名：d、temp、data2 → 用意图命名。
• 长函数：> 30-50 行 → 拆成有名字的小函数。
• 重复代码（DRY 违规）：两处相似逻辑 → 提取。
• 长参数列表：> 4 个参数 → 参数对象。

2.2 结构与耦合

• 上帝对象：一个类做所有事 → 拆分职责。
• 深耦合：A 知道 B 的内部细节 → 减少暴露。
• 散弹式修改：改一个需求要动 10 个文件 → 关注点没聚合。
• 过度耦合到具体实现：依赖接口而非具体类。

2.3 行为问题

• 注释撒谎：注释和代码不符 → 改注释或改代码。
• 死代码：没被调用 → 删。
• 隐藏依赖：函数依赖全局状态但签名看不出 → 参数显式传。
• 副作用隐藏在 getter 里：getName() 居然改状态 → 命名撒谎。

三、重构：有纪律的改进

3.1 重构的定义

重构 = 不改变外部行为，只改进内部结构，每一步都有测试兜底。

"我顺手改了一下"不算重构——重构必须每一步都能跑测试验证行为没变。

3.2 经典手法

3.3 重构的安全流程

1. 先补/跑测试（建立安全网）
2. 一次只做一个微重构（小步）
3. 每步跑测试（确认行为没变）
4. 全部绿 → 继续下一步；红 → 回退

3.4 示例：Extract Function

# ❌ 一个函数做三件事（校验、计算、格式化）
def process_order(order):
    # 校验
    if order.status != "pending":
        raise ValueError("invalid status")
    if order.total <= 0:
        raise ValueError("invalid total")
    # 计算
    total = order.total
    discount = 0.1 if total > 1000 else 0
    final = total * (1 - discount)
    # 格式化
    return f"ORDER-{order.id}-{final:.2f}"

# ✅ 拆成三个有名字的函数
def _validate_order(order): ...
def _calculate_total(order): ...
def _format_result(order_id, total): ...

def process_order(order):
    _validate_order(order)
    final = _calculate_total(order)
    return _format_result(order.id, final)

四、Code Review：质量门禁

4.1 看什么

Review 不是"找茬"，是理解 + 把关：

4.2 反馈的原则

• 对代码不对人：说"这个函数有问题"不说"你写错了"。
• 解释为什么：不只说"这里不对"，说"这里可能在 X 场景下崩，因为 Y"。
• 区分阻塞 vs 建议：明确"必须改"和"可以讨论"。
• 给方向不给答案：问"这里是不是该提取个函数？"优于直接贴代码。
• 关注重要的事：安全/正确性/性能 > 命名/格式（格式交给 linter）。

4.3 Review 的规模

• PR 太大（> 400 行）→ Review 质量急剧下降，应拆小。
• 每 PR 建议 200-400 行改动，一次审 < 60 分钟。
• Review 速度重要：拖 3 天的 review 比没有 review 更糟（阻塞交付）。目标 < 24h 反馈。

4.4 自动化的边界

交给工具: 格式 / lint / 类型 / 常见 bug（gosec/semgrep/staticcheck）
留给人:   设计 / 语义 / 权衡 / 业务正确性 / 一致性

五、复杂度治理

5.1 圈复杂度（Cyclomatic Complexity）

定义：代码中独立路径的数量 = 1 + 分支数(if/for/case/&&/||)。

def f(x):
    if x > 0: return "pos"    # +1
    elif x < 0: return "neg"  # +1
    return "zero"             # 基础 1
# 圈复杂度 = 3

治理标准：

• ≤ 10：正常
• 11-20：需要解释，考虑拆分

• 20：必须重构（几乎不可测）

工具：radon（Python）、gocyclo（Go）、SonarQube（通用）。

5.2 其他复杂度信号

5.3 复杂度的平衡

复杂度治理不是"越简单越好"——过度抽象（掉进简化主义）也是复杂度。平衡点：

• 代码是要读懂的（可读性优先），不是要"最短/最聪明"。
• 一个 5 行的 if 分支，比一个需要跳 3 个文件的抽象类更简单。
• "三法则"（Rule of Three）：代码用到第三次才提取抽象。前两次复制粘贴是合理的。

六、DDD（领域驱动设计）落地

6.1 DDD 解决什么

复杂业务领域（电商、金融、医疗）里，代码和业务语言脱节 → 沟通成本高、实现和需求漂移。DDD 让代码说业务的语言。

6.2 战略设计（宏观）

• 限界上下文（Bounded Context）：把业务切成独立领域（订单、库存、支付各一个上下文），各自有语言和模型。
• 上下文映射：上下文间的关系（防腐层 ACL、共享内核等）。
• 通用语言（Ubiquitous Language）：领域术语在代码里和业务里用同一个词。

6.3 战术设计（微观）

6.4 何时该用 DDD

七、落地：工程实践清单

[ ] 代码有测试（单元覆盖关键逻辑）
[ ] 命名表达意图（无魔法数/烂名/死代码）
[ ] 函数短小、单一职责
[ ] 圈复杂度可控（< 15 主要函数）
[ ] 无上帝对象、无深耦合
[ ] 重复代码已提取（Rule of Three）
[ ] code review 是门禁不是走过场
[ ] PR 小步（< 400 行）、Review 快（< 24h）
[ ] 重构与功能开发分开 commit
[ ] 复杂领域有清晰模型（DDD 或分层）

八、结束 + 速查表

下一篇: 7. 可观测性实操: metrics/logs/traces 打点 / OpenTelemetry / SLO.

7. 可观测性实操: metrics/logs/traces 打点 / OpenTelemetry / SLO

TL;DR

"能上线"不等于"能 debug"。可观测性（Observability）是让生产系统的行为可以被理解的能力——不是单指监控，而是 metrics（数字）/ logs（事件）/ traces（链路）三件套。system-design 部分讲了理论（SLO/SLI 框架），这一章落到怎么打点、怎么选指标、怎么用 OTel、怎么把 SLO 和告警接起来。

读完应能：

1. 区分 metrics/logs/traces 各自适合什么、怎么协同。
2. 给自己的服务打上正确的指标（RED/USE 方法）。
3. 用 OpenTelemetry 做跨服务链路追踪。
4. 设计合理的 SLO/SLI 并接到告警上，避免告警疲劳。

一、三件套（Pillars）

1.1 各自是什么

1.2 三件套的关系（经典示例）

问题: "下单变慢了"
  Metrics: 下单 P99 从 200ms → 2s (发现问题)
  Traces:  链路显示 80% 时间花在「库存服务」调用 (定位)
  Logs:    库存服务日志显示连接池耗尽报错 (根因)

二、Metrics：怎么选指标

2.1 两种经典方法论

RED（服务层，微服务）：

USE（资源层，基础设施）：

2.2 必须有的基础指标

# 服务层 (RED)
http_requests_total{method,path,status}
http_request_duration_seconds{le=...}      # histogram
http_errors_total

# 资源层 (USE)
cpu_usage_ratio
memory_usage_bytes
disk_io_bytes
connection_pool_usage

# 业务层 (视系统)
order_created_total
checkout_duration_seconds

2.3 用 Histogram 看分位数

P99 不能直接存（要排序），用 Histogram（分桶计数）：

from prometheus_client import Histogram

request_duration = Histogram(
    "http_request_duration_seconds",
    "HTTP request duration",
    buckets=[0.01, 0.05, 0.1, 0.25, 0.5, 1, 2.5, 5, 10],  # 桶边界
)

@request_duration.time()
def handler():
    ...

PromQL 查 P99：

histogram_quantile(0.99, sum(rate(http_request_duration_seconds_bucket[5m])) by (le))

2.4 打点要点

• cardinality 控制：标签维度不能太散（path 带 user_id 会爆炸）。URL 要先归一化成 GET /orders/:id。
• rate 而非 counter 裸值：counter 要 rate() 看变化率。
• histogram 比 summary 好：可聚合、可跨维度求分位。

三、Logs：结构化日志

3.1 结构化（JSON）而非散文本

{"ts":"2026-01-01T12:00:00Z","level":"error","msg":"db timeout",
 "service":"orders","trace_id":"abc123","user_id":42,"db_latency_ms":5200}

为什么 JSON：可被工具（Loki/ES）索引、可按字段查询、可加 context。

3.2 日志级别与采样

DEBUG < INFO < WARN < ERROR < FATAL

• 生产默认 INFO，DEBUG 开在调试时。
• 高流量路径（每请求多行）要采样（记 1%），否则日志系统崩。
• 错误日志要带上下文（trace_id + 关联 id），不然无法关联。

3.3 别打敏感信息

日志会长期保存，不打 token/密码/手机号/身份证（见应用安全章节）。用掩码。

四、Traces：链路追踪

4.1 什么是 span / trace

trace_id: 4bf92f3577b34da6a3ce929d0e0e4736
┌─ root span (HTTP GET /checkout)
│   ├─ span: 认证服务  (200ms)
│   ├─ span: 订单服务  (1500ms)
│   │    └─ span: 数据库查询 (1200ms)  ← 热点在这
│   └─ span: 库存服务  (300ms)

• trace = 一次完整请求。
• span = 一次服务调用（有 parent-child 关系）。
• 每个服务在入口创建/接收 trace，传播 trace_id + span_id。

4.2 传播（Propagation）

跨服务要传 trace 上下文（HTTP header）：

X-Trace-Id: 4bf92f3577b34da6a3ce929d0e0e4736
X-Span-Id: 1f2e...

网关/入口生成 trace_id，每个服务把自己作为子 span 挂上去。

4.3 OpenTelemetry（业界标准）

OTel = 统一的遥测采集 + 传播标准（SDK + API + 协议），兼容 Prometheus/Jaeger/云平台。

// Go OTel 初始化
import (
    "go.opentelemetry.io/otel"
    "go.opentelemetry.io/otel/exporters/otlp/otlptrace/otlptracehttp"
    "go.opentelemetry.io/otel/sdk/trace"
)

func initTracer() {
    exporter, _ := otlptracehttp.New(context.Background(),
        otlptracehttp.WithEndpoint("otel-collector:4318"))
    tp := trace.NewTracerProvider(trace.WithBatcher(exporter))
    otel.SetTracerProvider(tp)
}

# Python: 自动埋点 HTTP + DB + 框架
from opentelemetry import trace
from opentelemetry.sdk.trace import TracerProvider
from opentelemetry.instrumentation.flask import FlaskInstrumentor
from opentelemetry.instrumentation.requests import RequestsInstrumentor

provider = TracerProvider()
trace.set_tracer_provider(provider)
FlaskInstrumentor().instrument()
RequestsInstrumentor().instrument()

4.4 采样策略

• 头部采样（head-based）：进网关时按概率决定整条链路采不采（1-10%）。
• 尾部采样（tail-based）：先全采、后端按需（错误链路全采）——贵但准。
• 高流量系统：默认 1% + 错误 100% 采样。

五、SLO / SLI / 告警

5.1 SLI / SLO / Error Budget

SLI (Service Level Indicator): 怎么量 — 可用性% / 延迟P99 / 错误率
SLO (Service Level Objective):  目标值 — P99 < 500ms / 可用性 99.9%
Error Budget (错误预算):       100% - SLO — 一年可犯错的量（3 个九=8.7小时/年）

5.2 设计 SLI/SLO

SLI 示例: 请求成功率 = 成功请求 / 总请求 (可用性 SLI)
         latency SLI = 满足延迟阈值(如 500ms)的请求比例
SLO 示例: 99.9% 的请求 < 500ms (按月评估)

5.3 告警：别告警疲劳

坏告警：告警比处理速度快、告警没有 actionable 信息、全部 p0。

好告警原则：

• 只告警可行动的事：告警了你要能做事，否则就删掉。
• 用错误预算驱动：Error Budget 没耗尽 → 不告警（SLO 内波动是正常的）。
• burn rate 告警：按"预算消耗速度"告警——30 分钟内烧完 2% 预算 → p1；烧 14.4% → 严重。

SLO 99.9% (月预算 43min):
  burn rate 1  = 每月 30 天正好烧完
  burn rate 14.4 = 2 小时内烧 14.4% → p1 立即响应

• 告警必须带runbook（怎么排查/怎么处理）。

六、完整落地架构

应用 (服务 A/B/C)
  │  OTel SDK (自动埋点 HTTP/DB/gRPC)
  ▼
OTel Collector (统一采集: metrics/logs/traces, 采样, 脱敏)
  ├─▶ Prometheus (metrics 存储 + 查询)
  │       └─▶ AlertManager (告警 → 通知)
  ├─▶ Loki (logs 存储, 关联 trace_id)
  └─▶ Tempo/Jaeger (traces 存储)
         │
         └─▶ Grafana (统一 Dashboard + 关联查询)

关键组件职责：

• OTel Collector：统一入口，做采样、标签、脱敏、路由。
• Prometheus：pull 模型抓 metrics，PromQL 查询。
• Loki：标签索引日志，低开销。
• Tempo/Jaeger：trace 存储与搜索。
• Grafana：三件套统一可视化 + 告警。

七、生产排查实战流程

1. 收到告警 (metrics 异常: 错误率↑ / P99↑)
2. 打开 Grafana: 看 RED 指标确认范围 (哪些 path/service)
3. 看 Traces: 找到异常 trace, 定位到哪个服务哪次调用慢
4. 下钻到该服务: 看 span 里 DB/网络/外部调用耗时
5. 看 Logs: 按 trace_id 过滤, 找根因 (错误堆栈/超时/连接池)
6. 修复 → 部署 → 观察指标回落 → 关闭告警

这套流程把"系统乱成一锅粥时的救火"变成"有据可依的排查"——这就是可观测性的价值。

八、结束 + 速查表

回主目录: 工程化实践轴 README. 下一篇系统正文: 导论卷回到主目录 或任选下面章节。

8. GitHub Actions 实战: workflow / expression / 缓存 / 矩阵 / reusable / 自托管

TL;DR

GitHub Actions 是 CI/CD 的事实标准之一（尤其开源项目）。上一章 CI/CD 讲了通用管线模型，这一章手把手落到 GitHub Actions：语法、环境、expression、缓存、矩阵构建、可复用 workflow、自托管 runner、安全（权限/secret）。看完能自己搭一条生产级 pipeline。

读完应能：

1. 读懂任意 .github/workflows/*.yml 并写出自己的。
2. 用 expression、条件、矩阵、缓存优化 CI 速度和正确性。
3. 用 reusable workflow 消除跨仓库重复。
4. 正确配置权限和 secret，不踩常见安全坑。

一、核心概念

1.1 三要素

event (触发器) → job (任务, 独立 runner) → step (步骤, 同一 runner 顺序执行)

• workflow：一个 .github/workflows/xxx.yml 文件。
• job：workflow 里的一个任务，跑在独立 runner 上（可并行）。
• step：job 里的一步（一个命令或一个 action），顺序执行、共享 shell。

1.2 关键文件路径

.github/
  workflows/
    ci.yml            # 每个文件 = 一个 workflow

1.3 最小 workflow

name: CI
on: push           # 触发：push 到任何分支

jobs:
  build:
    runs-on: ubuntu-latest
    steps:
      - uses: actions/checkout@v4    # 检出代码
      - uses: actions/setup-go@v5
        with:
          go-version: '1.22'
      - run: go build ./...
      - run: go test ./...

二、触发器（Event）

2.1 常用触发

on:
  push:
    branches: [main]            # 只推 main
    paths:
      - 'src/**'                # 只当 src 变化时（避免无关触发）
      - 'go.mod'
      - '!docs/**'              # 排除 docs
  pull_request:
    types: [opened, synchronize, reopened]   # synchronize = 新提交
  schedule:
    - cron: '0 2 * * *'        # 每天 2 点（UTC）
  workflow_dispatch:            # 手动触发（必须加这个按钮才会出现）

2.2 触发规则要点

• push 和 pull_request 常搭配（PR 阶段 + 合并后各跑一遍）。
• paths 过滤器避免"只改 README 也跑全量 CI"。
• workflow_dispatch + inputs 可做手动参数化触发。

on:
  workflow_dispatch:
    inputs:
      environment:
        description: '部署环境'
        required: true
        default: 'staging'
        type: choice
        options: [staging, prod]

三、上下文与 Expression

3.1 关键上下文（Context）

3.2 Expression 语法

# 表达式用 ${{ }} 包裹，在字符串里也可插值
- run: echo "sha is ${{ github.sha }}"
- if: ${{ github.ref == 'refs/heads/main' }}
- if: ${{ !cancelled() }}       # 前序失败也跑（清理用）
- if: ${{ success() }}          # 默认: 全成功才跑
- if: ${{ failure() }}          # 失败才跑

3.3 条件操作符

==  !=  &&  ||  !  ( )  contains()  startsWith()  endsWith()

- name: 只在 PR 且改动 src 时跑集成测试
  if: github.event_name == 'pull_request' && contains(github.event.pull_request.files.*.filename, 'src/')

四、Job 依赖与并行

4.1 needs（依赖）

jobs:
  test:
    runs-on: ubuntu-latest
  deploy:
    needs: test                  # 等 test 成功后
    runs-on: ubuntu-latest

4.2 并发控制（防止重复发布）

concurrency:
  group: deploy-${{ github.ref }}   # 同 ref 的任务互斥
  cancel-in-progress: true          # 新任务顶掉旧任务

4.3 超时与失败容错

jobs:
  test:
    timeout-minutes: 10          # job 级超时
    steps:
      - run: sleep 100000
        timeout-minutes: 2       # step 级超时
  cleanup:
    if: ${{ always() }}          # 无论成败都跑
    runs-on: ubuntu-latest
    needs: [test, deploy]

五、矩阵构建（Matrix）

5.1 多版本/多平台

jobs:
  test:
    strategy:
      matrix:
        go: ['1.21', '1.22']
        os: [ubuntu-latest, macos-latest]
    runs-on: ${{ matrix.os }}
    steps:
      - uses: actions/setup-go@v5
        with: { go-version: ${{ matrix.go }} }
      - run: go test ./...

→ 自动生成 2 × 2 = 4 个并行 job。

5.2 排除组合

strategy:
  matrix:
    os: [ubuntu-latest, windows-latest]
    go: ['1.21', '1.22']
    exclude:
      - os: windows-latest    # windows 只测一个版本
        go: '1.21'

5.3 include（加额外组合）

matrix:
  include:
    - os: ubuntu-latest
      go: '1.23'    # 额外加一个

5.4 矩阵产物汇总

多个 OS 的产物要上传再合并：

- name: Upload artifact
  uses: actions/upload-artifact@v4
  with:
    name: dist-${{ matrix.os }}
    path: dist/

# 汇总 job
publish:
  needs: build        # 等所有矩阵 job
  steps:
    - uses: actions/download-artifact@v4
      with: { pattern: dist-* }

六、缓存与提速

6.1 缓存依赖

- name: Cache go modules
  uses: actions/cache@v4
  with:
    path: ~/.cache/go-build
    key: go-cache-${{ runner.os }}-${{ hashFiles('go.sum') }}
    restore-keys: |
      go-cache-${{ runner.os }}-

• key 变化（依赖变了）才重新缓存。
• restore-keys 提供"找不到精确 key 时用相近的"。

6.2 各生态缓存

# Go
actions/cache  →  ~/.cache/go-build,  key=hashFiles('go.sum')

# Python
actions/setup-python@v5 自带 cache: pip
  with: { python-version: '3.12', cache: 'pip' }

# Node
actions/setup-node@v4
  with: { node-version: 20, cache: 'npm' }

# Rust
Swatinem/rust-cache@v2    # 自动处理 target/

6.3 加速技巧

• 用 actions/setup-* 的 cache 参数（自动）。
• 只装依赖不改就复用层（Docker layer caching）。
• 矩阵并行 > 单 job 里并行步骤。
• 慢测试拆分到独立 job 并行。

七、可复用 Workflow（Reusable）

7.1 为什么