数据截至 2026-08-27(上游 commit f25c580af159)

01 · PagedAttention 与 KV cache 块管理

这一章讲什么： vLLM 的成名作。先讲清 KV cache 为什么是推理的显存杀手，再讲 PagedAttention「按块分页」的核心思想，最后落到本 commit 里的三块真实代码：KVCacheBlock 块对象、BlockPool 块池、KVCacheManager 分配器，以及前缀缓存怎么靠链式哈希命中。

1. 它要解决的小问题

自回归生成每多一个 token，注意力就要重读它前面所有 token 的 Key/Value 向量。为了不重复计算，这些向量被缓存下来——这就是 KV cache。

问题在于它的形状：长度只有在生成结束那一刻才知道。传统实现为每条请求预留一段能装下 max_model_len 的连续显存，于是出现两种浪费：

浪费	来源
内部碎片	预留 4096 个 token 的位置，实际只用了 300 个，剩下的谁也用不了
外部碎片	显存被切成大小不一的占用段，加起来够、连续的不够
重复存储	一千条请求共享同一个系统提示词，前缀的 KV 被存了一千份

PagedAttention 论文（vLLM 的出处，arXiv:2309.06180）给出的判断是：这就是操作系统几十年前解决过的问题——内存分页。本 commit 里的 vllm/v1/core/ 就是这套思想在 V1 引擎里的完整实现。

2. 思路：把「显存页 + 页表 + 页面缓存」整套搬过来

直觉对应关系非常干净：

操作系统	vLLM
物理页框（固定大小）	KV cache 块（固定 `block_size` 个 token 的 K/V 槽位）
页表（虚拟→物理）	块表（block table）：每条请求一串逻辑块号 → 物理块 id
按需分页	生成到第 n 块才分配第 n 块，不预留
写时复制 / 共享页	相同前缀的请求引用同一块，引用计数 +1
页面缓存（page cache）	释放的块不急着清，带哈希留着，下次命中直接用

一句话：显存里永远只装「真实存在的 token」，逻辑上的连续性由块表维持，物理块爱在哪在哪。

注意力 kernel 侧的配合是：不再假设一条序列的 KV 连续存放，而是拿着块表去「按块_gather_」——这是 PagedAttention kernel 的本职；V1 中这部分由各注意力后端（FlashAttention/FlashInfer/MLA 等，见 vllm/v1/attention/backends/）以块表为输入完成，比如 FlashAttention 后端元数据里的 block_table: torch.Tensor（vllm/v1/attention/backends/flash_attn.py:262）。

图示：块表寻址

请求 A:"把这首诗续写下去..."        请求 B(同前缀,采样 n=2 时典型)
┌───────────────────────┐          ┌───────────────────────┐
│ 逻辑块 0 1 2 3        │          │ 逻辑块 0 1 2 3         │
└───┬───┬───┬───┬───────┘          └───┬───┬───┬───┬───────┘
    │   │   │   │                      │   │   │   │
    ▼   ▼   ▼   ▼                      └───┴───┘   ▼
  物理块[7][3][9][12]                 共享 [7][3]   [15]
       ▲                                  ▲
       └── GPU 上一整块显存池,按 block_size 等分,块即槽位 ──┘

怎么读这张图： 每条请求手里是一张「逻辑块 → 物理块」的映射表（块表）；两个请求的前两个逻辑块映射到同一对物理块——这就是前缀共享。物理块是显存池里等大的槽位，分配时从空闲链表摘一个下来。

3. 原理演示：一个最小块池

下面这段把 BlockPool 的核心想法演出来（分配、释放后按哈希留缓存、命中复用）：

# 示意,非源码
class Block:
    def __init__(self, block_id):
        self.block_id = block_id
        self.ref_cnt = 0
        self.block_hash = None   # 只在「装满且已缓存」时有值

class BlockPool:
    def __init__(self, num_blocks):
        self.blocks = [Block(i) for i in range(num_blocks)]
        self.free_queue = list(self.blocks)      # 实际是双向链表,LRU 序
        self.hash_to_block = {}                  # 前缀缓存索引

    def allocate(self, n):
        out = []
        for _ in range(n):
            blk = self.free_queue.pop(0)          # 拿最久未用的
            if blk.block_hash is not None:
                del self.hash_to_block[blk.block_hash]  # 旧缓存身份作废(驱逐)
            blk.ref_cnt = 1
            out.append(blk)
        return out

    def free(self, blocks):
        for blk in reversed(blocks):              # 尾部先还,LRU 友好
            blk.ref_cnt -= 1
            if blk.ref_cnt == 0:
                self.free_queue.append(blk)       # 带哈希回池:仍可被命中

    def lookup(self, block_hash):
        blk = self.hash_to_block.get(block_hash)
        if blk:
            blk.ref_cnt += 1                      # 命中即共享
            self.free_queue.remove(blk)
        return blk

重点看两点：分配和驱逐是同一个动作（拿到一个空闲块，顺手把它的旧缓存身份废掉）；释放不是销毁（块带着哈希回池，在 hash 表里继续可被查到）。

4. 真实实现

4.1 块对象：`KVCacheBlock`

定义在 vllm/v1/core/kv_cache_utils.py:163（KVCacheBlock），一个块只有这几样元数据：

字段	含义
`block_id`	物理块号，0..num_gpu_blocks-1
`ref_cnt`	引用计数；0 表示在空闲链表里（可被驱逐/复用）
`_block_hash` + `_block_hash_num_tokens`	缓存身份：块满且入缓存后才有
`prev_free_block` / `next_free_block`	空闲双向链表的指针
`is_null`	「空块」标记：占位、永不入缓存（滑窗/mamba 等场景补位用）

注意它不含数据本身——真实的 K/V 张量是 worker 侧按层分配的大张量（allocate_kv_cache，vllm/v1/worker/utils.py:379），块对象只是调度侧的「账本」。调度器（CPU 进程）和 worker（GPU 进程）只靠 block_id 对齐视角。

4.2 空闲链表：`FreeKVCacheBlockQueue`

在 vllm/v1/core/kv_cache_utils.py:229。没有用 Python 的 deque，而是直接操作块对象的 prev_free_block/next_free_block 指针，原因写在 docstring 里：支持 O(1) 中间摘除（前缀缓存命中时要把块从空闲链表中间拿走），且避免分配 Python 对象。

排序规则（同文件 docstring）：队首是最该被驱逐的——最久未用的在前；同一时间释放的，含哈希 token 更多的（块链尾部）在前。这个顺序由 free_blocks 里「逆序归还」维持。

4.3 块池：`BlockPool`

在 vllm/v1/core/block_pool.py:143（BlockPool）。三个动作最关键：

分配 = popleft + 驱逐。 get_new_blocks（vllm/v1/core/block_pool.py:647）从空闲链表头摘块，每摘一个就调 _maybe_evict_cached_block（同文件 :679）把它在哈希表里的旧缓存记录清掉——所以「缓存命中」只能发生在块还没被复用之前，这就是 LRU 缓存语义的来源。

命中 = touch。 touch（vllm/v1/core/block_pool.py:702）把命中块的 ref_cnt +1；若它正躺在空闲链表（ref_cnt == 0），先从链表里摘除。

释放 = 分两堆归还。 free_blocks（vllm/v1/core/block_pool.py:723）把 ref_cnt 减到 0 的块分两类：没哈希的（不可能再被前缀命中）插到队首优先复用（LIFO，GPU 局部性好）；带哈希的插到队尾（FIFO，尽量活得久一点等命中）。注释里写得很直白："LIFO reuse of non-cached blocks for better GPU locality / FIFO reuse of cached blocks for LRU eviction behavior"。

4.4 前缀缓存的钥匙：链式哈希

块哈希由 hash_block_tokens（vllm/v1/core/kv_cache_utils.py:621）计算，输入三样：

父块哈希（第一个块用全局 NONE_HASH）；
本块的 token id 序列；
额外 key（如多模态输入的哈希）。

输出是 BlockHash（vllm/v1/core/kv_cache_utils.py:48，本质是 bytes）。默认算法是 sha256（prefix_caching_hash_algo 默认值见 vllm/config/cache.py:140）。

「链式」是关键设计：第 i 块的哈希覆盖了第 0..i-1 块的全部内容（通过父哈希递归带入）。于是：

命中判断只能从前往后连续匹配——第 i 块命中蕴含 0..i-1 全命中；
实现上体现为 find_longest_cache_hit 的 Phase 1 注释（vllm/v1/core/single_type_kv_cache_manager.py:735）："A missing block implies every later block misses too (chained hashes)"，遇到第一个 miss 就 break；
请求创建/追加 token 时就增量算好整条哈希链，存在 Request.block_hashes（vllm/v1/request.py:219，由 update_block_hashes 维护，同文件 :278），调度时无需重算。

查找入口是 KVCacheManager.get_computed_blocks（vllm/v1/core/kv_cache_manager.py:228），它转调 coordinator 的 find_longest_cache_hit；全注意力的实现 FullAttentionManager.find_longest_cache_hit 在 vllm/v1/core/single_type_kv_cache_manager.py:686。

4.5 分配器：`KVCacheManager.allocate_slots`

调度器每个 step 通过 allocate_slots（vllm/v1/core/kv_cache_manager.py:343）为请求补块。它的 docstring 里有一张精确的块布局图，值得记住：

----------------------------------------------------------------------
| < comp > | < new_comp > | < ext_comp >  | < new >  | < lookahead > |
----------------------------------------------------------------------
  已算过的      本次前缀缓存    外部连接器已算    本次要算    投机解码预留
              新命中的        的(P/D 场景)

三个阶段（docstring 原文）：先释放 comp 里不再需要的块（如滑出窗口的）并检查空闲块够不够；再处理前缀区（comp + new_comp + ext_comp）；最后为待计算的 new + lookahead 分配新块。空闲块不够就返回 None——调度器据此触发抢占（下一章讲）。

另外两个容易忽略的细节：

命中上限是 num_tokens - 1（vllm/v1/core/kv_cache_manager.py:258）：即使整条 prompt 都在缓存里，最后一个 token 也必须重算——否则拿不到 logits，无从采样。
多 KV cache group 时块大小取 LCM：混合模型（注意力 + Mamba）各组块大小不同，调度侧统一对齐到最小公倍数，哈希粒度取 GCD，见 resolve_kv_cache_block_sizes（vllm/v1/core/kv_cache_utils.py:678）。

5. 关键细节与坑

null_block 是块 0。 BlockPool.__init__ 把块 0 从空闲链表中摘出当「空块」（vllm/v1/core/block_pool.py:190），用于滑窗/稀疏注意力里「这个位置不该有 KV」的占位；它的 ref_cnt 不被维护，docstring 特意警告「needs special care to avoid freeing it」。
驱逐是懒惰的。 块释放后哈希仍在、仍在哈希表里可查，直到被 get_new_blocks 复用那一刻才真正失效。所以「前缀缓存容量」≈ 全部空闲块，不需要单独的缓存区。
共享前缀只在「满块」粒度成立。 不满一块的尾部没有哈希、不参与缓存（V1 起另有 partial block 缓存机制 cache_partial_block，vllm/v1/core/block_pool.py:445，但主线命中仍以满块为单位）。
非因果注意力直接禁用这两个特性。 _initialize_kv_caches 里检测到任何层 non_causal=True 就关掉 chunked prefill 和 prefix caching（vllm/v1/engine/core.py:269-280）——因为这两个优化都假设因果注意力。
块大小是性能旋钮。 默认由后端决定（常见 16）；多 group 时的 LCM 对齐意味着混合模型的有效块大小可能比你想的大，直接稀释前缀缓存命中率。

1. 它要解决的小问题​

2. 思路：把「显存页 + 页表 + 页面缓存」整套搬过来​

图示：块表寻址​

3. 原理演示：一个最小块池​

4. 真实实现​

4.1 块对象：KVCacheBlock​

4.2 空闲链表：FreeKVCacheBlockQueue​

4.3 块池：BlockPool​

4.4 前缀缓存的钥匙：链式哈希​

4.5 分配器：KVCacheManager.allocate_slots​

5. 关键细节与坑​