KV Cache 还有空间为何新请求却进不来？PagedAttention 的块表与碎片控制

上一篇用 FlashAttention 避免把 $L\times L$ 中间矩阵写回 HBM。到了自回归服务，attention 每次只生成一个新 token，却必须读取此前所有 Key/Value；KV Cache（键值缓存）因此随每个请求的实际长度增长。

若为每个请求一次预留 max_model_len 的连续空间，短回答浪费尾部，长回答又可能找不到足够大的连续洞。PagedAttention（分页注意力）把 KV Cache 切成固定 token 数的 blocks（块），用 block table（块表）把逻辑连续序列映射到任意物理块。

01 KV Cache 一条请求到底占多少？#

设层数为 $N_l$ ，KV heads 数为 $H_{kv}$ ，每头维度 $D_h$ ，序列长度 $T$ ，每元素 $b$ bytes。Key 与 Value 各一份，所以

M_{KV}=2N_lH_{kv}D_hTb.

例如 $N_l=32,H_{kv}=8,D_h=128$ 、BF16 的 $b=2$ ，每 token 是

2\times32\times8\times128\times2=131072\text{ bytes}=128\text{ KiB}.

一个 8K-token 请求仅 KV 就约 1 GiB。并发 40 个请求的长度还在每轮变化，管理方式直接决定可容纳 batch 大小。

02 连续预留会产生哪两种碎片？#

假设最大长度 16 tokens，而请求 A 实际只用 5 个。若预留 16 个槽，11 个槽直到请求结束都不能给别人，这是 internal fragmentation（内部碎片/预留浪费）。

若每次按实际长度扩展连续数组，旧请求释放后会留下大小不同的洞；总空闲量足够，却没有某个足够大的连续区，这是 external fragmentation（外部碎片）。搬迁并压紧 KV 成本很高，还会打断延迟敏感的 decode。

连续预留: [AAAAA...........] [BBBBBBBBBB......]
物理显存: 已用 + 请求独占但尚未使用的尾部

分页分配: [A0][B0][A1][free][B1][free]...
逻辑顺序: A0 -> A1；物理上无需相邻

text

03 块表怎样把逻辑位置翻译成物理地址？#

令 block size $B=4$ tokens。请求 A 的 7 个 token 需要两个逻辑块，块表为 [7, 1]，表示逻辑块 0 在物理块 7，逻辑块 1 在物理块 1。

对逻辑 token 位置 $t$ ：

j=\lfloor t/B\rfloor,\qquad r=t\bmod B,

p=\text{block\_table}[j],

其中 $j$ 是逻辑块号， $r$ 是块内偏移， $p$ 是物理块号。于是：

逻辑位置 $t$	逻辑块 $j$	块内偏移 $r$	物理位置
0	0	0	block 7, slot 0
3	0	3	block 7, slot 3
4	1	0	block 1, slot 0
6	1	2	block 1, slot 2

Attention kernel 按块表读取物理块 7 再读物理块 1，在数学上仍把它们当作连续的前 7 个 token。

04 新 token 到来时只需按需扩一块#

请求 A 当前长度为 7，物理块 1 还剩一个 slot。第 8 个 token 的 KV 直接写入 (block 1, slot 3)；第 9 个 token 到来时，才从 free list 分配一个新物理块，例如 block 3，并把块表扩成 [7,1,3]。

flowchart LR
  T7[length=7<br/>table 7,1] --> W8[写 block 1 / slot 3]
  W8 --> FULL[length=8<br/>末块已满]
  FULL --> ALLOC[free list 分配 block 3]
  ALLOC --> W9[写 block 3 / slot 0<br/>table 7,1,3]

mermaid

因此每个请求最多只浪费最后一个物理块中的 $B-1$ 个 token slots，不需要为未知输出长度提前预留全部空间。

05 一个教学版 Block Manager#

下面只管理 token slots，不存真实 KV。输入是物理块总数与 block size；输出是每个请求的块表。

from collections import deque

class BlockManager:
    def __init__(self, num_blocks: int, block_size: int):
        self.block_size = block_size
        self.free = deque(range(num_blocks))
        self.tables: dict[str, list[int]] = {}
        self.lengths: dict[str, int] = {}

    def append_slot(self, request_id: str) -> tuple[int, int]:
        table = self.tables.setdefault(request_id, [])
        length = self.lengths.get(request_id, 0)
        logical_block, offset = divmod(length, self.block_size)
        if logical_block == len(table):
            if not self.free:
                raise MemoryError("no free KV block")
            table.append(self.free.popleft())
        self.lengths[request_id] = length + 1
        return table[logical_block], offset

    def release(self, request_id: str) -> None:
        for physical_block in self.tables.pop(request_id, []):
            self.free.append(physical_block)
        self.lengths.pop(request_id, None)

python

测试时交错执行 A,A,B,A,B...，确认 A、B 的物理块可以不连续，逻辑位置却不会串请求。真实系统还需要引用计数、GPU/CPU 元数据一致性、批量分配、抢占与多层多 head 的地址计算。

06 真实 KV 张量的 shape 与寻址#

一种便于理解的物理布局是

K_cache: [N_layers, N_blocks, B, H_kv, D_h]
V_cache: [N_layers, N_blocks, B, H_kv, D_h]
block_table: [N_sequences, max_blocks_per_sequence]
context_lens: [N_sequences]

text

对于某层、某序列、逻辑位置 $t$ ，kernel 先由 block_table[seq, t // B] 取物理块，再用 t % B 定位 slot。生产 kernel 常为向量化读取而调整维度顺序，不能据此假定 vLLM 内部的精确 stride；不变的是逻辑到物理的两级寻址契约。

若使用 Grouped Query Attention（分组查询注意力，GQA）， $H_q$ 可大于 $H_{kv}$ ；KV Cache 按 $H_{kv}$ 而非 query heads 数计算。容量估算误用 $H_q$ 会高估显存，反过来误用过小 head 数则会在运行时 OOM。

07 PagedAttention 怎样计算当前 query？#

对 decode 时的 query $q_i\in\mathbb R^{H_q\times D_h}$ ，它需关注逻辑位置 $0\ldots i$ 。PagedAttention 逐个读取块表指向的 $K_j,V_j$ ，计算

s_t=q_i^\top k_t/\sqrt{D_h},\qquad o_i=\sum_{t=0}^{i}\operatorname{softmax}(s)_t v_t.

块在物理上不连续，不影响位置、causal 范围或 Softmax 分母。kernel 可像上一篇一样用分块在线 Softmax 合并不同物理块；额外代价是块表寻址、分支以及不规则访存。

08 Copy-on-Write 怎样共享前缀？#

并行采样或 beam search 的多个分支共享同一 prompt。若直接复制 prompt KV，分支数为 $k$ 时浪费 $k$ 份显存。分页后，多个逻辑块表可以指向同一物理块，并给该块维护 reference count（引用计数）。

beam A table: [7, 1]
beam B table: [7, 1]     refcount(7)=2, refcount(1)=2

text

若两者要向尚未填满的物理块 1 写不同 token，必须 Copy-on-Write（写时复制）：为其中一个分支分配新块，复制已有 slots，再写入分叉 token。已填满且永不修改的前缀块可以一直共享。

引用计数错误有两种危险：过早释放导致另一个请求读到已复用内容；忘记递减则产生显存泄漏。必须用请求完成、取消、超时、抢占和异常路径做状态机测试。

09 Block Size 是延迟与浪费的折中#

块越小，末块内部碎片上界越低，也更容易共享细粒度前缀；但块表更长、分配与寻址更多，GPU 读取并行度可能不足。块越大，元数据和 kernel 调度更友好，却可能为大量短请求浪费尾部。

不要照搬论文中的默认值。真实选择取决于模型、dtype、head shape、硬件、prompt/output 长度分布和 kernel。应对候选 block size 同时测：

有效 KV bytes / 已分配 KV bytes；
可同时驻留的 sequence 数与 token 数；
decode tokens/s、time per output token 和 P99 latency；
块分配频率、prefix cache hit、preemption 与 recomputation 次数。

10 Scheduler 为什么也是算法的一部分？#

每轮 decode 前，scheduler 选择本轮进入 continuous batching（连续批处理）的请求，并为可能增长的序列预留新块。若 free blocks 不足，系统必须拒绝新请求、延后调度、抢占低优先级序列，或通过重算/交换恢复空间。

一个安全顺序是：先计算本轮所需新块并原子式预留，再启动 GPU kernel，成功后提交新长度。若部分 worker 分配成功、部分失败，不能让块表和实际 KV 写入各走各的。多 GPU Tensor Parallel 下，各 rank 的同一请求必须保持一致的逻辑块状态，即使物理地址不同。

11 Prefill 与 Decode 的内核目标不同#

Prefill（预填充）一次处理 prompt 的多个 query，矩阵较大，常适合 FlashAttention 一类高吞吐 kernel；decode 每个序列通常只有一个新 query，却读取长 KV，更偏 memory-bound，并且各序列长度不同。

prefill: [许多新 Q] × [prompt K/V] -> 建立整段 KV
decode : [每序列 1 个新 Q] × [各自历史 paged K/V] -> 追加 1 个 KV slot

text

两阶段可以共享同一块管理器，却不应假设使用相同 kernel 或优化指标。只测长 prompt 的 prefill tokens/s，不能代表聊天服务的 inter-token latency。

12 如何接入当前 vLLM 而不依赖内部私有类？#

vLLM 的 paged KV cache 与 scheduler 是执行引擎内部契约，内部类和 kernel signature 会快速演进。业务代码应使用公开的 vllm serve OpenAI-compatible server 或公开 LLM 接口，把内部 block table 当作可观测实现而非自行调用的稳定 API。

from vllm import LLM, SamplingParams

llm = LLM(model="your-model-id", max_model_len=8192)
params = SamplingParams(temperature=0.0, max_tokens=128)
outputs = llm.generate(
    ["解释分页式 KV Cache", "给出一个极小例子"],
    params,
)

for output in outputs:
    print(output.outputs[0].text)

python

模型 ID、tensor parallel size、KV cache dtype、最大上下文和显存利用率属于部署配置；升级版本时以当前官方文档和启动日志为准。不要从旧博客复制已删除的 BlockManager 构造参数。

13 一条可执行的正确性验证路径#

单请求、短序列、greedy decoding，与不分页的连续 KV 基线比较每步 logits 和 token。
用 block size 2 强迫频繁跨块，覆盖长度 1、2、3、4、5。
两请求交错增长并反复释放，给每个 KV slot 写唯一 (request,position) 哨兵值。
两个 beam 共享前缀后分叉，验证 Copy-on-Write 前共享、写入后隔离。
模拟无 free block、请求取消和 worker 异常，检查所有引用计数与 free list 守恒。

守恒式尤其有用：

N_{free}+N_{allocated}=N_{total},

且所有块引用计数为正的集合必须恰好等于已分配集合。每轮调度后都可在 debug 模式断言。

14 常见错误与最短调试路径#

症状	常见原因	最短检查
跨块边界后文本突然错乱	`t//B` 或 `t%B`、长度提交时机错	用 block size 2 和哨兵 KV 打印地址
取消请求后显存不回升	异常路径未释放或引用计数泄漏	逐事件记录 alloc/free/refcount
一个 beam 改坏另一个	对共享未满块原地写，缺少 COW	分叉前后比较物理块 ID
有空闲显存仍拒绝请求	容量预算、free list 或多 worker 状态不一致	对账 free blocks 与各表引用集合
吞吐升高但 P99 爆炸	scheduler 过度批处理或频繁抢占	联合画 queue、batch、preemption 时间线
修改 block size 反而更慢	元数据/访存开销压过碎片收益	对工作负载分布做端到端 sweep

15 失败场景与相近方法边界#

PagedAttention 主要提高 KV 容量利用率，不能减少单个 query 对长历史的 $O(T)$ 读取，也不能解决模型权重放不进显存。若服务始终只有一个固定长度请求，分页寻址可能只有额外开销。

FlashAttention 优化一次 attention 的 IO；PagedAttention 管理跨请求、跨时间增长的 KV 地址。Prefix Caching（前缀缓存）决定哪些请求可复用已算 KV；continuous batching 决定每轮让哪些请求一起执行；quantized KV cache 则减少每个 slot bytes。它们互补但解决不同瓶颈。

16 今天真正需要记住什么？#

自回归服务的 KV Cache 随实际 token 增长，按最大长度连续预留会产生严重浪费与碎片。
固定大小物理块加 block table，使逻辑连续序列可落在非连续显存，按需增长且每请求最多浪费一个末块。
引用计数与 Copy-on-Write 让并行采样、beam 和公共前缀共享 KV，同时保持分叉后的写隔离。
PagedAttention 的收益必须与 scheduler、block size 和真实请求长度分布一起测，而不是只测一个 attention kernel。

17 思考题与小练习#

物理块大小为 4，块表 [5,2,9]。写出逻辑位置 0、6、11 的物理块与块内偏移；若长度为 10，末块浪费几个 slots？
使用前文模型配置，block size 16。计算一个物理块跨全部层的 KV bytes；若有 20 GiB 可用于 KV，理论最多多少块？
扩展教学版 BlockManager：加入引用计数与 fork(request,new_id)，并为 Copy-on-Write 设计三个断言。

18 下一篇预告#

分页让更多变长请求同时留在显存，但每个 decode step 仍可能被少量超长请求拖慢。下一篇将进入 continuous batching：scheduler 如何在吞吐、首 token 延迟、逐 token 延迟与抢占之间做可测量的取舍。

01 KV Cache 一条请求到底占多少？#

02 连续预留会产生哪两种碎片？#

03 块表怎样把逻辑位置翻译成物理地址？#

04 新 token 到来时只需按需扩一块#

05 一个教学版 Block Manager#

06 真实 KV 张量的 shape 与寻址#

07 PagedAttention 怎样计算当前 query？#

08 Copy-on-Write 怎样共享前缀？#

09 Block Size 是延迟与浪费的折中#

10 Scheduler 为什么也是算法的一部分？#

11 Prefill 与 Decode 的内核目标不同#

12 如何接入当前 vLLM 而不依赖内部私有类？#

13 一条可执行的正确性验证路径#

14 常见错误与最短调试路径#

15 失败场景与相近方法边界#

16 今天真正需要记住什么？#

17 思考题与小练习#

相关工作#

18 下一篇预告#