打造好服务的计算机科学 — 用测量重新学习教科书概念
先测量再选择：数据结构、并发、缓存与时钟
중급 · 课时 30 · 实验 10
课程大纲
用实测确认复杂度
- 别背大 O，把输入翻倍来测 reading
- 用倍增实验找出并修复隐藏的二次复杂度 lab
- 测验：用实测看复杂度 quiz
数据结构的选择会改变延迟与成本 — 哈希、树、堆
- 问什么决定选什么结构 — 用探测次数与高度预先计数 reading
- 亲手实现并统计哈希、树与堆 lab
- 测验：如何选择哈希、树与堆 quiz
亲手实现 LRU 缓存与布隆过滤器
- LRU 相信最近，布隆过滤器只确定“没有” reading
- 实现并测量 LRU 与布隆过滤器 lab
- 测验：LRU 与布隆过滤器 quiz
竞态条件在 await 之间也会发生 — 线程、GIL 与 asyncio
内存与 GC 造成延迟长尾
- 引用计数、循环回收器与不断增长的那一行 reading
- 用数字找出 GC 暂停与泄漏的代码行 lab
- 测验：内存与 GC 造成的延迟长尾 quiz
字符串有三种长度 — 字节、码位、字符，还有时区
- 字符串有三种长度，而今天是哪里的今天 reading
- 用 360 个昵称敲定长度、截断、相等与日期 lab
- 测验：字符串长度与时区 quiz
浮点数欺骗服务的地方
- 浮点数是“接近”的约定 — 求和、比较、ID、方差、百分比 reading
- 堵住浮点数在求和、比较、ID、方差和百分比中的漏洞 lab
- 测验：浮点数泄漏的地方 quiz
缓存比数据库撒谎更久的时刻 — 缓存一致性
- 失效顺序造成的陈旧值 reading
- 按交错顺序测量缓存的谎言 lab
- 测验：缓存一致性与交错 quiz
时钟与顺序 — Lamport 时钟、向量时钟与重试
- 编号守住因果，向量识别并发 reading
- 加上 Lamport 与向量时钟，统计丢失的更新与重试 lab
- 测验：时钟与顺序 quiz
不变量由数据库守护 — 约束与重试循环
- 先检查再写入会出错，用约束就能守住 reading
- 用约束阻止，只重试 40001 lab
- 测验：不变量由数据库守护 quiz