Month 2 · PagedAttention ★
皇冠章节。这一个月学透，后面所有内容都顺。
这是 vLLM 之所以是 vLLM 的核心 idea。论文（Kwon et al., SOSP'23）的副标题是 "Efficient Memory Management for Large Language Model Serving with PagedAttention"。 注意是 Memory Management——这是一篇系统论文，不是机器学习论文。 作者用 OS 虚拟内存做类比，把 KV cache 的利用率从 ~40% 拉到 ~96%。
驱动问题
在 LLM 推理时，每生成一个 token，模型每一层 attention 都要看"之前所有 token 的 K 和 V"。
把它们缓存（KV cache）下来是必须的。
问：如果给每个请求预分配 max_len × hidden_size 的连续显存来存 KV，会出什么问题？至少说 3 个。
写下你的 3 个回答，再展开
- 内部碎片 · 大部分请求实际 token 数远小于 max_len，未用的槽位浪费。
- 外部碎片 · 请求结束释放出来的"洞"未必能装下下一个声明 max_len 更大的请求。
- 无法共享 · 两个请求 prefix 相同（system prompt 一样），KV 没法复用。
- (隐藏奖励) 不能动态长度 · 同一个 batch 里如果不同请求当前长度差距大，没法 vectorize。
这四个问题——任何看过 OS 教材的人都会脱口而出："这就是早期 OS 给进程分配内存的痛苦"。
01OS 虚拟内存：你已经会的部分
这一节是必要的 prerequisite。如果你完全没接触过虚拟内存，下面这段速通； 如果你学过，扫一眼当复习。后面的对应才能立刻生效。
虚拟内存解决的问题
1960 年代的计算机：每个程序看到的是物理内存的连续段。运行多个程序很难，因为它们要竞争同一块物理 RAM 的不同区段。
解法 = 把"程序看到的地址" 和 "实际物理位置" 解耦：
虚拟页连续、物理页分散，靠页表桥接。代价是每次访问要查表（TLB 缓存这个）。
关键带走的 3 点：
- 固定大小的页（4KB）让分配 / 释放变简单 —— 永远只对齐到 page boundary，外部碎片消失。
- 页表是 indirection 层 —— 应用看到的连续地址不是真的连续。
- 页可以共享 —— 两个进程的页表项指向同一个物理页（典型场景：共享库、COW fork）。
💡 速补虚拟内存
没系统学过的，直接读 OSTEP 第 13、15、18、21、22 章（共 ~80 页）。
免费在线。
这是 6 个月里你需要"啃书"的唯一章节。
02PagedAttention：把上面这套搬到 KV cache
vLLM 的做法结构上完全平行：
两个序列、各自的 block table、共享物理块池。注意 P3/P7 被两个序列同时引用——这就是 prefix caching。
把 OS 概念逐行映射到 vLLM
| OS | vLLM | 说明 |
|---|---|---|
| virtual address space | sequence 的 token 序列 | 程序眼中的"连续" |
| virtual page (4KB) | logical block (16 tokens) | 固定大小切片 |
| physical frame | physical block | 显存里实际的存储槽 |
| page table | block table | 每 sequence 一份，记录 L → P 映射 |
| page fault | 新 token 跨入下一个 block 时分配 | vLLM 是"懒分配" |
| shared page (COW) | prefix cache 命中的共享 block | "复制时分裂"做法不同 |
| page replacement (LRU) | prefix cache eviction | see Month 3 |
| swap to disk | swap to host RAM / NVMe | see Month 3 |
| TLB | (没有专门的——block table 已在 GPU 内存) | 查找开销直接在 kernel 里 |
03读源码 · KV cache manager
下面的 anchors 是这个月的主菜。按顺序读，期间随时回头看上面的图。
读 ① · 2 小时 · 整体结构
这是 v1 引擎里 KV cache 的总管。看 KVCacheManager class 的方法签名：allocate_slots()、free()、get_cached_blocks()。
"allocate" 在 vLLM 里是什么动作？跟 malloc 区别在哪？
读 ② · 1 小时 · 块池
实际的 free list + hash-based 共享。看 BlockPool 和它的 cached_block_hash_to_block dict。
两个 sequence 怎么发现它们 prefix 相同？hash 怎么算的（看
hash_block_tokens）？读 ③ · 1 小时 · 每序列管理
"每个序列的 block table 是怎么存的"。看每次新增 token 是怎么决定 "需不需要再申请一块"。
block size 是 16 token，意味着每 16 个 token 才会"翻页"。这个数字为啥不能更大或更小？
读 ④ · 30 分钟 · 走到 GPU 端
Worker 怎么把 block table 喂给 attention kernel。搜 block_table、slot_mapping 这两个变量。
attention kernel 拿到一个 query token 后，怎么找到它对应的所有 KV？这两个变量分别答了什么问题？
04Prefix caching · "page cache" 的现代版
OS 里 page cache 是："读过的磁盘块缓存在内存，下次再读直接命中"。 vLLM 里 prefix cache 是："算过的 prompt 的 KV 缓存在显存，下个共享 prompt 的请求直接命中"。
请求 1 prompt: [system: 你是一个客服] + [user: 怎么退货?]
─────────────── 16 tokens ─────────────── + ─── 5 tokens ───
请求 2 prompt: [system: 你是一个客服] + [user: 怎么改地址?]
─────────────── 16 tokens ─────────────── + ─── 6 tokens ───
前 16 tokens 的 KV 完全相同
→ 请求 1 算完后，把 P3 这块标记为可共享
→ 请求 2 进来 hash 一对：命中！直接引用 P3，跳过 prefill
→ 延迟降低、显存少占这是 prefix caching 的"快乐路径"。但还有几个细节：
- 什么时候 evict：显存有限。LRU 还是别的策略？(看
BlockPool的 free list 实现) - 什么时候 invalidate：被引用的块不能 evict。引用计数怎么做？(
BlockPool.ref_cnt) - 怎么 hash：两段 token 序列相同时 hash 才能撞。怎么避免 hash 碰撞？(prefix-aware hash chain)
这些都是 OS 里 page cache 已经解决过的问题。差别在于：
| OS page cache | vLLM prefix cache | |
|---|---|---|
| cache key | (file inode, offset) | hash(token sequence) |
| 命中粒度 | 4KB 页 | 16 tokens 块 |
| 失效 | 写文件、删除 | 显存压力下被 evict |
| 读延迟收益 | SSD →几 µs | 跳过整个 prefill 阶段，几十 ms |
05动手 · 复现碎片对比
这是本月的硬核作业。跑通它，PagedAttention 就刻进肌肉里了。
- 启动 vLLM 时打开日志：能看到 "GPU KV cache size: X tokens / 显存利用率: Y%"。
- 用
benchmarks/benchmark_serving.py跑两种 workload：- workload A: 100 个请求，prompt 50 tokens，max_tokens=10 (短)
- workload B: 100 个请求，prompt 50 tokens，max_tokens=2000 (长)
- 记录两组的 throughput、TTFT (time to first token)、平均显存利用率。
- 对比一个关闭 prefix caching 的 vLLM (用
--no-enable-prefix-caching)，看 throughput 差多少。
✓ 期待结果
Workload A 比 B 在 throughput 上高 3-5×（B 显存压力大、动态分配 + eviction 多）。
Prefix caching 在 system prompt 重复场景下 throughput 翻倍。如果数字没出来，回去看你的 prompt 是不是真的有共享 prefix。
06常见误解
"PagedAttention 就是一个新的 attention 算子"
错。PagedAttention 是 kernel + memory layout 的协同设计。
Kernel 是普通的 attention，唯一区别是它能从非连续地址聚集 K 和 V。
真正的 idea 在 memory layout。
"block size 越小越好，碎片越少"
错。block 太小 → block table 太大、TLB 类似的 lookup 开销爆炸、kernel 难写 vectorize。
16 是 vLLM 实验出来的 sweet spot。
"prefix caching 总是开着是赚的"
几乎是，但代价是 hash + 引用计数的 CPU 开销。
在 prompt 完全没重复的场景（个性化高的 chat），收益接近 0、开销仍在。
vLLM 默认开是因为大部分线上场景有 system prompt。
07本月 PR 候选方向
Month 2 的 KPI 是一个内存子系统相关的 PR。候选：
- 给
BlockPool加一个 metric（free block 数、cache hit rate）暴露到 Prometheus。 - 修一个 prefix cache hash 的 edge case（搜 issue tracker
prefix-cachelabel）。 - 给
kv_cache_manager.py写测试覆盖某未测函数。 - improve 某条错误信息（"failed to allocate X blocks"，但没说总池子有多大）。