推理与 KV Cache 02：分页、共享与回收如何协作

PagedAttention 将序列拆成固定大小的逻辑块，再通过 Block Table 映射到缓存池，使请求能够逐块增长和共享前缀。本文以统一的 Dense KV 缓存组为例，说明块、Token Slot、前缀索引与引用计数的分工，以及缓存何时可以回收。

一个请求最终会生成多少 Token，通常要到执行结束才知道。若一开始按最大长度分配连续 KV 空间，短请求会浪费容量；若随着长度增长不断扩容，又需要处理搬迁和碎片。

从一个位置找到缓存块

设每块容纳 $K=4$ 个 Token，请求当前有 10 个 Token。它包含 3 个逻辑块：第一个放位置 0–3，第二个放 4–7，最后一个只用了位置 8–9。

对位置 $t$ ：

\text{logical block}=\left\lfloor t/K\right\rfloor, \qquad \text{offset in block}=t\bmod K

请求的 Block Table 可以记录如下映射：

逻辑块	Token 位置	缓存池中的 Physical Block ID
B0	0–3	P7
B1	4–7	P1
B2	8–9	P5

逻辑块连续，缓存池编号可以不连续。P7 表示软件缓存池中的块编号；要找到某层、某个 Head 的具体字节，还需要 Tensor 布局。

Token 位置如何映射到缓存池

B0 · 位置 0–3

Block Table → P7

4 个位置已使用

B1 · 位置 4–7

Block Table → P1

4 个位置已使用

B2 · 位置 8–9

Block Table → P5

2 个位置已使用 · 2 个空位

追踪位置 2：逻辑块 B0 → 物理块 P7 → 块内偏移 2 → Token Slot 30

K = 4。逻辑顺序保持不变，物理块编号可以离散；Slot 仍是软件索引。

“Slot”在源码中也有不同粒度。若指展平后的 Token Slot，常见计算方式为：

\text{token slot}=\text{physical block id}\times K+\text{offset in block}

按整块分配，会多占多少空间

请求有 $N$ 个 Token 时，需要 $\lceil N/K\rceil$ 个块，总共预留 $\lceil N/K\rceil K$ 个 Token 位置。沿用上一篇的每 Token 160 KiB，10 个 Token 的有效数据为 1.5625 MiB；按 4 个 Token 一块分配，实际预留 12 个位置，占 1.875 MiB。

末块未使用的两个位置属于内部碎片。分页允许不连续分配，减轻连续大块分配的困难，但尾块仍可能没填满。

请求长度	每块 Token 数	分配块数	未使用的 Token 位置
100	4	25	0
100	16	7	12

小块通常有利于细粒度分配与共享；大块减少部分索引和传输管理开销。实际选择还受 Attention 内核、传输路径和模型缓存结构约束。

前缀索引与 Block Table 各查什么

假设两个请求都以相同的系统提示开头。第一个请求已经计算出这段前缀的 KV，第二个请求便有机会直接复用。

这涉及两类映射：

映射	输入	回答的问题
Prefix Cache Index	Token 前缀及计算身份	有没有可复用的缓存对象？
Request Block Table	请求内的逻辑块号	本请求应访问缓存池中的哪个块？

新请求先查询前缀索引，再将命中的块写入自己的 Block Table。两个请求可以各有一张表，同时指向 P7。

先以“只共享完整块”的策略理解粒度：若两个请求有 6 个相同的前缀 Token，每块 4 个 Token，则可共享前 4 个，余下两个要按该策略继续计算。部分块的复用、追加与写时复制需要另外的管理规则。

命中后省去的是命中前缀的重复 Prefill。新后缀仍需读前缀 KV，后续 Decode 也要执行 Attention；仅保存 KV 的系统还可能需要计算末尾位置来获得首个输出的 logits。

请求结束后，缓存会立刻消失吗

设 A、B 同时使用 P7，它的活跃请求引用数为 2。A 结束后变为 1；B 结束后变为 0。只要还有活跃使用者，这个块就不能被重用为别的数据。

以 vLLM v0.30.0 文档描述的 Block Pool 为例，引用归零的缓存块可以进入 Free Block Queue，同时仍存在于前缀缓存索引中。若它在被重用前再次命中，系统将它从队列移出并增加引用。若分配器选中它来保存新内容，则先移除旧哈希映射。

状态	活跃请求可使用	新请求可前缀命中	可被重新分配
有活跃引用的有效缓存块	是	满足匹配条件时可以	否
无活跃引用、旧缓存仍有效	当前无人使用	满足匹配条件时可以	可以，但须先撤销旧身份
已驱逐、等待或正在保存新内容	由新所有者决定	不能再命中旧内容	由分配状态决定

显存里的旧字节是否还在，无法单独说明缓存是否有效。有效性由对象身份、完成状态和管理元数据共同决定。释放 Block 通常也只改变缓存池里的使用权，整个预分配 Tensor 未必随之返还给设备分配器。

用 Radix Tree 组织前缀，用 LRU 选择淘汰对象

哈希与 Radix Tree 都可以服务于前缀查找。Radix Tree 把共同前缀组织在同一路径上，让多个请求共享路径中的节点。

LRU 解决另一件事：空间不足时，优先驱逐哪些候选对象。它可以与 Radix Tree 一起使用。读代码时，先看查找如何得到最长驻留前缀，再看哪些节点允许被驱逐，会比把二者当成互斥方案更容易理解。

PCS 的本地版本 712002d2 提供了一个可读的例子：match_path() 查找并保护命中路径，insert_path() 插入对象，release() 解除保护，enforce_capacity() 执行容量约束。它的 Leaf-only LRU 只从未锁定的驻留叶节点中选择，删除叶节点后，父节点可能成为新的候选。

这里的保护区间对应仿真的 Restore/Prefill；不能直接推断成真实引擎会保护到完整 Decode 结束。PCS 还用合成前缀组生成稳定的对象 ID，没有执行真实 Token 序列的模型计算。沿这条路径读源码，学到的是“查找—保护—插入—释放—驱逐”的职责划分。

参考：PagedAttention 论文、vLLM 前缀缓存设计、PCS 源码。

上一篇：从一次生成理解 KV Cache 与容量 · 下一篇：从 Block ID 到字节地址：KV Cache 内存布局。