05 · BlockManager：分页 KV Cache

KV Cache 为什么会成为瓶颈

自回归生成中，每一层 Attention 都需要读取历史 token 的 Key 和 Value。随着上下文增长，KV Cache 也持续增长。若为每个请求预留一块“最大长度连续显存”，会产生大量浪费；若频繁申请不同大小连续区域，又会出现外部碎片。

PagedAttention 的核心思想来自操作系统虚拟内存：把 KV Cache 切成固定大小 block，让每个 Sequence 通过 block table 把逻辑位置映射到任意物理 block。

BlockManager 的数据结构

• blocks：所有 block 对象。
• free_block_ids：空闲 block 队列。
• used_block_ids：已使用 block 集合。
• hash_to_block_id：用于 Prefix Cache 的 hash 索引。
• ref_count：一个 block 被多少 Sequence 共享。

分配与释放

_allocate_block() 从空闲队列取一个 id，重置 block，并加入 used 集合。释放时引用计数减到 0，block id 回到空闲队列。

分页不会消除所有浪费：每个 Sequence 的最后一个 block 可能没有填满，这叫内部碎片。但它显著减少了“必须连续”和大规模预留带来的浪费。

新 token 何时需要新 block

当追加 token 后恰好跨入一个新逻辑 block，can_append() 会检查是否至少还有一个空闲 block；may_append() 再真正分配。

注意源码中的边界判断与 append 时机紧密相关。阅读时要把 len(seq) % block_size 和“新 token 已经 / 尚未追加”一起考虑，不能孤立看一个条件。

PagedAttention 不是只有内存管理

仅有 block table 还不够。Attention kernel 必须能够根据 block table 从离散物理位置读取 K/V。nano-vLLM 在 Decode 路径把 block_tables 与 context_lens 传给带 KV Cache 支持的 FlashAttention 调用。

HTML INTERACTIVE LAB05 · BlockManager：分页 KV Cache

单独打开 ↗

课后习题等待完成

分页 KV Cache 主要减少哪一种问题？

动手任务

设 block_size=4，分别为长度 3、5、9 的三个请求计算所需 block 数和最后一个 block 的空闲 token 位。

下一节：Prefix Cache